Graal: [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?

[gilles-duboscq]

I'm implementing a potential fix in #1330, if you have cases you'd like me to test, please share them in either issue.

[4ntoine]

Having it with just kotlin sequences in kotlin 1.3.31:

Call path from entry point to com.company.project.storage.FilterStorage$exportData$1.invokeSuspend(Object): 
    at com.company.project.storage.FilterStorage$exportData$1.invokeSuspend(FilterStorage.kt)
    at kotlin.coroutines.jvm.internal.BaseContinuationImpl.resumeWith(ContinuationImpl.kt:33)
    at kotlin.sequences.SequenceBuilderIterator.hasNext(SequenceBuilder.kt:140)
    at kotlin.sequences.SequencesKt___SequencesKt.toCollection(_Sequences.kt:702)
    at kotlin.sequences.SequencesKt___SequencesKt.toMutableList(_Sequences.kt:732)
    at kotlin.sequences.SequencesKt___SequencesKt.toList(_Sequences.kt:723)
    at com.company.project.storage.JvmIO.writeToFile(JvmIO.kt:32)

Does it mean kotlin sequenece is a blocker for graalvm?

[sdeleuze]

I tried to compile a Spring Boot 2.2 application with WebFlux and Coroutines, but it failed with a similar exception:

Error: Unsupported features in 2 methods
Detailed message:
Error: Non-reducible loop
Call path from entry point to kotlinx.coroutines.flow.FlowKt__ChannelsKt.emitAll(FlowCollector, ReceiveChannel, Continuation): 
    at kotlinx.coroutines.flow.FlowKt__ChannelsKt.emitAll(Channels.kt)
    at kotlinx.coroutines.flow.FlowKt.emitAll(Unknown Source)
    at kotlinx.coroutines.flow.internal.ChannelFlow$collect$2.invokeSuspend(ChannelFlow.kt:75)
    at kotlinx.coroutines.flow.internal.ChannelFlow$collect$2.invoke(ChannelFlow.kt)
    at kotlinx.coroutines.flow.internal.ChannelFlowKt.withContextUndispatched(ChannelFlow.kt:166)
    at com.oracle.svm.reflect.ChannelFlowKt_withContextUndispatched_2355bad4b1610d0e1c8d1976ddb8dde7e0df6f21_5203.invoke(Unknown Source)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at javax.xml.transform.TransformerException.printStackTrace(TransformerException.java:348)
    at javax.xml.transform.TransformerException.printStackTrace(TransformerException.java:282)
    at com.oracle.svm.jni.functions.JNIFunctions.ExceptionDescribe(JNIFunctions.java:761)
    at com.oracle.svm.core.code.IsolateEnterStub.JNIFunctions_ExceptionDescribe_b5412f7570bccae90b000bc37855f00408b2ad73(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:895)
    at org.graalvm.compiler.java.BciBlockMapping.build(BciBlockMapping.java:540)
    at org.graalvm.compiler.java.BciBlockMapping.create(BciBlockMapping.java:1150)
    at org.graalvm.compiler.java.BytecodeParser.build(BytecodeParser.java:892)
    at org.graalvm.compiler.java.BytecodeParser.buildRootMethod(BytecodeParser.java:870)
    at org.graalvm.compiler.java.GraphBuilderPhase$Instance.run(GraphBuilderPhase.java:84)
    at org.graalvm.compiler.phases.Phase.run(Phase.java:49)
    at org.graalvm.compiler.phases.BasePhase.apply(BasePhase.java:197)
    at org.graalvm.compiler.phases.Phase.apply(Phase.java:42)
    at org.graalvm.compiler.phases.Phase.apply(Phase.java:38)
    at com.oracle.graal.pointsto.flow.MethodTypeFlowBuilder.parse(MethodTypeFlowBuilder.java:221)
    at com.oracle.graal.pointsto.flow.MethodTypeFlowBuilder.apply(MethodTypeFlowBuilder.java:340)
    at com.oracle.graal.pointsto.flow.MethodTypeFlow.doParse(MethodTypeFlow.java:310)
    at com.oracle.graal.pointsto.flow.MethodTypeFlow.ensureParsed(MethodTypeFlow.java:300)
    at com.oracle.graal.pointsto.flow.MethodTypeFlow.addContext(MethodTypeFlow.java:107)
    at com.oracle.graal.pointsto.flow.StaticInvokeTypeFlow.update(InvokeTypeFlow.java:346)
    at com.oracle.graal.pointsto.BigBang$2.run(BigBang.java:510)
    at com.oracle.graal.pointsto.util.CompletionExecutor.lambda$execute$0(CompletionExecutor.java:171)
    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: Non-reducible loop
Call path from entry point to kotlinx.coroutines.reactive.PublisherAsFlow.collect(FlowCollector, Continuation): 
    at kotlinx.coroutines.reactive.PublisherAsFlow.collect(ReactiveFlow.kt)
    at kotlinx.coroutines.reactive.FlowSubscription.consumeFlow(ReactiveFlow.kt:233)
    at kotlinx.coroutines.reactive.FlowSubscription.flowProcessing(ReactiveFlow.kt:171)
    at kotlinx.coroutines.reactive.FlowSubscription$onStart$1.invoke(ReactiveFlow.kt:166)
    at kotlinx.coroutines.reactive.FlowSubscription$onStart$1.invoke(ReactiveFlow.kt:158)
    at kotlin.reflect.jvm.internal.impl.resolve.OverridingUtilsKt.selectMostSpecificInEachOverridableGroup(overridingUtils.kt:70)
    at com.oracle.svm.reflect.OverridingUtilsKt_selectMostSpecificInEachOverridableGroup_c99570ed3ada32227c43fac1c99c7c434e136120_5213.invoke(Unknown Source)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at javax.xml.transform.TransformerException.printStackTrace(TransformerException.java:348)
    at javax.xml.transform.TransformerException.printStackTrace(TransformerException.java:282)
    at com.oracle.svm.jni.functions.JNIFunctions.ExceptionDescribe(JNIFunctions.java:761)
    at com.oracle.svm.core.code.IsolateEnterStub.JNIFunctions_ExceptionDescribe_b5412f7570bccae90b000bc37855f00408b2ad73(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:895)
    at org.graalvm.compiler.java.BciBlockMapping.build(BciBlockMapping.java:540)
    at org.graalvm.compiler.java.BciBlockMapping.create(BciBlockMapping.java:1150)
    at org.graalvm.compiler.java.BytecodeParser.build(BytecodeParser.java:892)
    at org.graalvm.compiler.java.BytecodeParser.buildRootMethod(BytecodeParser.java:870)
    at org.graalvm.compiler.java.GraphBuilderPhase$Instance.run(GraphBuilderPhase.java:84)
    at org.graalvm.compiler.phases.Phase.run(Phase.java:49)
    at org.graalvm.compiler.phases.BasePhase.apply(BasePhase.java:197)
    at org.graalvm.compiler.phases.Phase.apply(Phase.java:42)
    at org.graalvm.compiler.phases.Phase.apply(Phase.java:38)
    at com.oracle.graal.pointsto.flow.MethodTypeFlowBuilder.parse(MethodTypeFlowBuilder.java:221)
    at com.oracle.graal.pointsto.flow.MethodTypeFlowBuilder.apply(MethodTypeFlowBuilder.java:340)
    at com.oracle.graal.pointsto.flow.MethodTypeFlow.doParse(MethodTypeFlow.java:310)
    at com.oracle.graal.pointsto.flow.MethodTypeFlow.ensureParsed(MethodTypeFlow.java:300)
    at com.oracle.graal.pointsto.flow.MethodTypeFlow.addContext(MethodTypeFlow.java:107)
    at com.oracle.graal.pointsto.DefaultAnalysisPolicy$DefaultVirtualInvokeTypeFlow.onObservedUpdate(DefaultAnalysisPolicy.java:191)
    at com.oracle.graal.pointsto.flow.TypeFlow.notifyObservers(TypeFlow.java:343)
    at com.oracle.graal.pointsto.flow.TypeFlow.update(TypeFlow.java:385)
    at com.oracle.graal.pointsto.BigBang$2.run(BigBang.java:510)
    at com.oracle.graal.pointsto.util.CompletionExecutor.lambda$execute$0(CompletionExecutor.java:171)
    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)

[sherl0cks]

@gilles-duboscq any further updates on this subject? It is really limiting for kotlin / graal native apps to the point that our team is considering giving up on the stack.

[gilles-duboscq]

I'll try to get this into 20.1 otherwise i'll just push transfer that to someone else.

[sherl0cks]

Great news. Please let us know if there is anything that can be done to help from the community.

[sbrannen]

@gilles-duboscq, having this in 20.1 would be great!

Keeping my fingers crossed... 🤞🏼

[gilles-duboscq]

This should be fixed by 4662877b8ce214528f09553f21776ab97e97c1a8. The fix is included in the latest 20.1 dev build (e.g., 20.1.0-dev-20200325_0537).

I tested that the original example from @rhencke now produces a working native-image.