[native-image] Classes with loops inside Kotlin coroutines fail to generate native code

[rhencke]

Consider the following Kotlin code:

import kotlin.coroutines.experimental.buildIterator

fun main(args: Array<String>) {
    val iter = buildIterator {
        for (i in 1..10) {
            yield("hello")
        }
    }
    for (i in iter) {
        println(i)
    }
}

Compile it with the Kotlin compiler (kotlin-compiler-1.2.40.zip). (Assume the zip is extracted to a directory represented by $KOTLIN_HOME)

$KOTLIN_HOME/bin/kotlinc-jvm -Xcoroutines=enable Main.kt
native-image -cp .:$KOTLIN_HOME/lib/kotlin-runtime.jar MainKt

This will fail to generate a native image, showing the following error:

Build on Server(pid: 21549, port: 26682)
   classlist:     244.44 ms
       (cap):   1,900.67 ms
       setup:   2,409.13 ms
    analysis:   3,028.97 ms
error: Non-reducible loop
Detailed message:
Error: Non-reducible loop
Call path from entry point to MainKt$main$iter$1.doResume(Object, Throwable): 
        at MainKt$main$iter$1.doResume(Main.kt)
        at kotlin.coroutines.experimental.jvm.internal.CoroutineImpl.resume(CoroutineImpl.kt:54)
        at kotlin.coroutines.experimental.SequenceBuilderIterator.hasNext(SequenceBuilder.kt:129)
        at MainKt.main(Main.kt:9)
        at com.oracle.svm.reflect.proxies.Proxy_9_MainKt_main.invoke(Unknown Source)
        at java.lang.reflect.Method.invoke(Method.java:498)
        at com.oracle.svm.core.JavaMainWrapper.run(JavaMainWrapper.java:199)
        at Lcom/oracle/svm/core/code/CEntryPointCallStubs;.com_002eoracle_002esvm_002ecore_002eJavaMainWrapper_002erun_0028int_002corg_002egraalvm_002enativeimage_002ec_002etype_002eCCharPointerPointer_0029(generated:0)
Original exception that caused the problem: org.graalvm.compiler.core.common.PermanentBailoutException: Non-reducible loop
        at org.graalvm.compiler.java.BciBlockMapping.computeBlockOrder(BciBlockMapping.java:852)
        at org.graalvm.compiler.java.BciBlockMapping.build(BciBlockMapping.java:514)
        at org.graalvm.compiler.java.BciBlockMapping.create(BciBlockMapping.java:1079)
        at org.graalvm.compiler.java.BytecodeParser.build(BytecodeParser.java:796)
        at org.graalvm.compiler.java.BytecodeParser.buildRootMethod(BytecodeParser.java:774)
        at org.graalvm.compiler.java.GraphBuilderPhase$Instance.run(GraphBuilderPhase.java:93)
        at org.graalvm.compiler.phases.Phase.run(Phase.java:47)
        at org.graalvm.compiler.phases.BasePhase.apply(BasePhase.java:195)
        at org.graalvm.compiler.phases.Phase.apply(Phase.java:40)
        at org.graalvm.compiler.phases.Phase.apply(Phase.java:36)
        at com.oracle.graal.pointsto.flow.MethodTypeFlowBuilder.parse(MethodTypeFlowBuilder.java:195)
        at com.oracle.graal.pointsto.flow.MethodTypeFlowBuilder.apply(MethodTypeFlowBuilder.java:319)
        at com.oracle.graal.pointsto.flow.MethodTypeFlow.doParse(MethodTypeFlow.java:308)
        at com.oracle.graal.pointsto.flow.MethodTypeFlow.ensureParsed(MethodTypeFlow.java:298)
        at com.oracle.graal.pointsto.flow.MethodTypeFlow.addContext(MethodTypeFlow.java:105)
        at com.oracle.graal.pointsto.DefaultAnalysisPolicy$DefaultVirtualInvokeTypeFlow.onObservedUpdate(DefaultAnalysisPolicy.java:184)
        at com.oracle.graal.pointsto.flow.TypeFlow.notifyObservers(TypeFlow.java:345)
        at com.oracle.graal.pointsto.flow.TypeFlow.update(TypeFlow.java:387)
        at com.oracle.graal.pointsto.BigBang$2.run(BigBang.java:498)
        at com.oracle.graal.pointsto.util.CompletionExecutor.lambda$execute$0(CompletionExecutor.java:172)
        at java.util.concurrent.ForkJoinTask$RunnableExecuteAction.exec(ForkJoinTask.java:1402)
        at java.util.concurrent.ForkJoinTask.doExec(ForkJoinTask.java:289)
        at java.util.concurrent.ForkJoinPool$WorkQueue.runTask(ForkJoinPool.java:1056)
        at java.util.concurrent.ForkJoinPool.runWorker(ForkJoinPool.java:1692)
        at java.util.concurrent.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:157)

Error: Processing image build request failed

If you adjust the sample, and comment out the loop within the coroutine as follows, the code successfully generates a working native image:

import kotlin.coroutines.experimental.buildIterator

fun main(args: Array<String>) {
    val iter = buildIterator {
        // for (i in 1..10) {
            yield("hello")
        // }
    }
    for (i in iter) {
        println(i)
    }
}

[gilles-duboscq]

Hi @rhencke, thank you for the report and minimal reproducer.

At the moment, Graal does not support compilation of non-reducible loops (i.e., loops with multiple entry-points). This is fine on HotSpot as we can just delegate execution of such methods to either the interpreter or C1 and they are fairly rare (for example javac or scalac would never produce such code patterns).
However, as you have seen, there is no backup strategy available on SVM/native-image.

Structured loops at an important (an conscious) decision in the design of the Graal IR so i don't think we want to change that. However there are ways we could improve support for non-reducible loops that appear in bytecodes.

In particular we could select the entry point that we want to keep and then duplicate parts of the loop on the other entry path so that a single entry point remains. This would cause some increase in code size but at least it would allow Graal to better support Kotlin coroutines .

[soudmaijer]

I was trying to convert my ktor.io app to a native-image, but ktor uses kotlin coroutines under the hood. Stuck like the issue reporter unfortunately.

[sanity]

Also encountered with Ktor Kotlin project, Graal RC10.

[bradnewman]

I also encountered this with Ktor, and ended up creating a standalone project to do as @gilles-duboscq suggested and duplicate the irreducible loops. It should work in general for any Kotlin coroutines, not just Ktor applications, though a minimal Ktor application is included as an example. I've released it under MIT license: https://github.com/HewlettPackard/kraal

It would still be nice if it GraalVM or kotlinc could resolve this independently so they work together out of the box, but maybe others will find this useful as a stop-gap until then.

[sureshg]

I encounterd the same issue. Is this something graal native-image plans to fix in future?