Further elimination of references

[penelopeysm]

In #220 and #221 I implemented an optimisation pass on the IR that cut down the number of references carried in the tape (sometimes quite drastically). The fundamental idea is that, if a ref that was written to was never read in any other basic block, the ref could be completely eliminated and replaced with a normal SSA value. See also #193 for previous context.

In fact, this can be pushed even further. Consider the following:

julia> using Libtask

julia> function f(x)
           a = x + 1
           b = if a > 0
               a + 1
           else
               a - 1
           end
           produce(b)
           return nothing
       end
f (generic function with 1 method)

julia> Libtask.generate_ir(:optimised_bb, f, 1.0)
BBCode (3 args, 6 blocks)
#49 ─
│   %48 = Libtask.resume_block_is(_1, 27)
│   %50 = nothing
└── switch %48 => #27, fallthrough #24
#24 ─
│   %14 = Base.add_float(_3, 1.0)::Float64
│   %30 = Libtask.set_ref_at!(_1, 1, %14)
│   %15 = Base.lt_float(0.0, %14)::Bool
│   %16 = Base.or_int(%15, false)::Bool
└── goto #26 if not %16
#25 ─
│   %37 = Libtask.get_ref_at(_1, 1)
│   %18 = Base.add_float(%37, 1.0)::Float64
│   %38 = Libtask.set_ref_at!(_1, 2, %18)
└── goto #29
#26 ─
│   %39 = Libtask.get_ref_at(_1, 1)
│   %20 = Base.sub_float(%39, 1.0)::Float64
│   %40 = Libtask.set_ref_at!(_1, 3, %20)
└── goto #29
#29 ─
│   %41 = φ (#25 => Libtask.TupleRef(2), #26 => Libtask.TupleRef(3))
│   %21 = Libtask.deref_phi(_1, %41, Float64)
│   %43 = Libtask.set_resume_block!(_1, 27)
│   %45 = Libtask.ProducedValue(%21)
└── return %45
#27 ─
│   %47 = Libtask.set_resume_block!(_1, -1)
└── return Main.nothing

Here, we still have three references that are being set:

• ref 1 corresponds to the value of a;
• ref 2 corresponds to the value of b in the if-branch;
• ref 3 corresponds to the value of b in the else-branch.

The current optimisation pass does not recognise these as dead refs because the control flow causes the sets and gets to be placed in different basic blocks. In fact, all the refs can be removed, as demonstrated by the following (hand-optimised) IR.

BBCode (3 args, 6 blocks)
#49 ─
│   %48 = Libtask.resume_block_is(_1, 27)
│   %50 = nothing
└── switch %48 => #27, fallthrough #24
#24 ─
│   %14 = Base.add_float(_3, 1.0)::Float64
│   %15 = Base.lt_float(0.0, %14)::Bool
│   %16 = Base.or_int(%15, false)::Bool
└── goto #26 if not %16
#25 ─
│   %18 = Base.add_float(%14, 1.0)::Float64
└── goto #29
#26 ─
│   %20 = Base.sub_float(%14, 1.0)::Float64
└── goto #29
#29 ─
│   %41 = φ (#25 => %18, #26 => %20)
│   %43 = Libtask.set_resume_block!(_1, 27)
│   %45 = Libtask.ProducedValue(%41)
└── return %45
#27 ─
│   %47 = Libtask.set_resume_block!(_1, -1)
└── return Main.nothing

Furthermore, notice that since we remove the TupleRefs in the phi node, we can even get rid of deref_phi calls. Right now this isn't possible, because all phi nodes occur at the start of a basic block, and thus the definition / setting must have been in a (transitive) predecessor basic block, which precludes the ref from being eliminated.

In other words, the current optimisation is still too conservative. Fixing this would require a more detailed analysis of the IR that doesn't just use the existing CFG, but rather the exact return / resume boundaries, in order to figure out exactly when refs can be eliminated.