Analysis of failures on Julia 1.10

[timholy]

This package's tests pass on Julia 1.9 and fail on Julia 1.10. Because the cause and likely resolutions are somewhat complex, I'm opening this issue to document the state of my analysis so far.

TL;DR summary

In Julia 1.10, changes to the lowering of Core.get_binding_type made control-flow graphs much more complicated, and the current way of ensuring correct propagation of flow is overly eager: it marks too many statements, breaking selective evaluation.

In detail

Let's take a small modification of an example in the docs and tests:

ex = quote
    s11 = 0
    k11 = 5
    for i = 1:3
        global s11, k11
        s11 += rand(1:5)
        k11 += i
    end
end

This example is used to illustrate selective evaluation, identifying just the statements needed to evaluate s11 but not k11. (This capability is essential for Revise, which needs to be able to compute all the method signatures that will be generated without evaluating the method definition itself.)

Here's an analysis script (the dependencies are obvious from the first line):

using LoweredCodeUtils, Graphs, GLMakie, GraphMakie, NetworkLayout
using LoweredCodeUtils.JuliaInterpreter

module ModSelective end
frame = Frame(ModSelective, ex)
src = frame.framecode.src
edges = CodeEdges(src)
isrequired = lines_required(:s11, frame.framecode.src, edges)
LoweredCodeUtils.print_with_code(stdout, src, isrequired)
cfg = Core.Compiler.compute_basic_blocks(src.code)
g = SimpleDiGraph(length(cfg.blocks))
for (i, bb) in enumerate(cfg.blocks)
    for j in bb.preds
        add_edge!(g, i => j)
    end
end
graphplot(g; layout=Stress(; dim=2), nlabels=string.(1:nv(g)), nlabels_fontsize=18)

Julia 1.9

The output from print_with_code yields

julia> LoweredCodeUtils.print_with_code(stdout, src, isrequired)
 1 t 1 ─ %1  = Core.get_binding_type(Main.ModSelective, :s11)
 2 t │   %2  = Base.convert(%1, 0)
 3 t │   %3  = Core.typeassert(%2, %1)
 4 t │         s11 = %3
 5 f │   %5  = Core.get_binding_type(Main.ModSelective, :k11)
 6 f │   %6  = Base.convert(%5, 5)
 7 f │   %7  = Core.typeassert(%6, %5)
 8 f │         k11 = %7
 9 t │   %9  = 1:3
10 t │         _1 = Base.iterate(%9)
11 t │   %11 = _1 === nothing
12 t │   %12 = ($(QuoteNode(Core.Intrinsics.not_int)))(%11)
13 t └──       goto #4 if not %12
14 t 2 ┄ %14 = _1
15 f │         _2 = Core.getfield(%14, 1)
16 t │   %16 = Core.getfield(%14, 2)
17 f │         global k11
18 f │         global s11
19 t │   %19 = s11
20 t │   %20 = 1:5
21 t │   %21 = rand(%20)
22 t │   %22 = %19 + %21
23 t │   %23 = Core.get_binding_type(Main.ModSelective, :s11)
24 t │   %24 = Base.convert(%23, %22)
25 t │   %25 = Core.typeassert(%24, %23)
26 t │         s11 = %25
27 f │   %27 = k11 + _2
28 f │   %28 = Core.get_binding_type(Main.ModSelective, :k11)
29 f │   %29 = Base.convert(%28, %27)
30 f │   %30 = Core.typeassert(%29, %28)
31 f │         k11 = %30
32 t │         _1 = Base.iterate(%9, %16)
33 t │   %33 = _1 === nothing
34 t │   %34 = ($(QuoteNode(Core.Intrinsics.not_int)))(%33)
35 t └──       goto #4 if not %34
36 t 3 ─       goto #2
37 f 4 ┄       return nothing

The basic-block structure is quite simple:

julia> cfg
CFG with 4 blocks:
  bb 1 (stmts 1:13) → bb 4, 2
  bb 2 (stmts 14:35) → bb 4, 3
  bb 3 (stmt 36) → bb 2
  bb 4 (stmt 37)

with corresponding graph representation

Follow the direction of arrows (from successor to predecessor) to notice that basic blocks 2 and 3 form a cycle.

Currently, the way that we ensure full execution is that we mark the final line of each basic block as required, and then fill in any dependencies (e.g., evaluation of the conditional in a GotoIfNot). Specifically, here we mark the final statement of blocks 2 (statement %35) and 3 (statement %36), and marking these eventually leads to marking the entire iterate loop. Note, however, that k11 does not participate in the branching in any way, and thus this strategy does not force evaluation of k11 (all statements associated with k11 are marked f).

Julia 1.10

The lowering affiliated with get_binding_type has changed significantly:

 1 f 1 ──       Core.NewvarNode(:(_1))
 2 t │    %2  = Core.get_binding_type(Main.ModSelective, :s11)
 3 t │          _3 = 0
 4 t │    %4  = _3 isa %2
 5 t └───       goto #3 if not %4
 6 t 2 ──       goto #4
 7 t 3 ──       _3 = Base.convert(%2, _3)
 8 t 4 ┄─       s11 = _3
 9 t │    %9  = Core.get_binding_type(Main.ModSelective, :k11)
10 t │          _4 = 5
11 t │    %11 = _4 isa %9
12 t └───       goto #6 if not %11
13 t 5 ──       goto #7
14 t 6 ──       _4 = Base.convert(%9, _4)
15 t 7 ┄─       k11 = _4
16 t │    %16 = 1:3
17 t │          _1 = Base.iterate(%16)
18 t │    %18 = _1 === nothing
19 t │    %19 = ($(QuoteNode(Core.Intrinsics.not_int)))(%18)
20 t └───       goto #16 if not %19
21 t 8 ┄─ %21 = _1
22 t │          _2 = Core.getfield(%21, 1)
23 t │    %23 = Core.getfield(%21, 2)
24 f │          global k11
25 f │          global s11
26 t │    %26 = s11
27 t │    %27 = 1:5
28 t │    %28 = rand(%27)
29 t │    %29 = %26 + %28
30 t │    %30 = Core.get_binding_type(Main.ModSelective, :s11)
31 t │          _5 = %29
32 t │    %32 = _5 isa %30
33 t └───       goto #10 if not %32
34 t 9 ──       goto #11
35 t 10 ─       _5 = Base.convert(%30, _5)
36 t 11 ┄       s11 = _5
37 t │    %37 = k11 + _2
38 t │    %38 = Core.get_binding_type(Main.ModSelective, :k11)
39 t │          _6 = %37
40 t │    %40 = _6 isa %38
41 t └───       goto #13 if not %40
42 t 12 ─       goto #14
43 t 13 ─       _6 = Base.convert(%38, _6)
44 t 14 ┄       k11 = _6
45 t │          _1 = Base.iterate(%16, %23)
46 t │    %46 = _1 === nothing
47 t │    %47 = ($(QuoteNode(Core.Intrinsics.not_int)))(%46)
48 t └───       goto #16 if not %47
49 t 15 ─       goto #8
50 f 16 ┄       return nothing

You can see that almost all the lines (including ones for k11) are marked t, unlike in Julia 1.9. This happens because we have a much more complicated graph of basic blocks:

julia> cfg
CFG with 16 blocks:
  bb 1 (stmts 1:5) → bb 3, 2
  bb 2 (stmt 6) → bb 4
  bb 3 (stmt 7) → bb 4
  bb 4 (stmts 8:12) → bb 6, 5
  bb 5 (stmt 13) → bb 7
  bb 6 (stmt 14) → bb 7
  bb 7 (stmts 15:20) → bb 16, 8
  bb 8 (stmts 21:33) → bb 10, 9
  bb 9 (stmt 34) → bb 11
  bb 10 (stmt 35) → bb 11
  bb 11 (stmts 36:41) → bb 13, 12
  bb 12 (stmt 42) → bb 14
  bb 13 (stmt 43) → bb 14
  bb 14 (stmts 44:48) → bb 16, 15
  bb 15 (stmt 49) → bb 8
  bb 16 (stmt 50)

Basic blocks 8, 9, 11, 14, and 15 participate in the loop. This more complicated structure reveals that the old strategy of marking the exit of each "needed" basic block is too simple. Consider the case of block 11, for which the first statement (%36) is s11 = _5 (assign from slot 5). Clearly this is a statement we must execute in order to evaluate s11. However, the remainder of block 11 deals with k11, and in particular marking the exit statement (%41) forces analysis of the conditional which forces evaluation of k11 itself.

If we are to selectively evaluate s11, we have to "fall through" blocks like 11 without executing their control flow. Doing this in a way that doesn't risk omitting "necessary" control-flow like loops is not feasible with the current implementation of selective evaluation.