analyses.md

Analyses

DocTestSetup = quote
    using LLVM, LLVM.IR, LLVM.Build, LLVM.Passes, LLVM.Analysis, LLVM.ORC

    if context(; throw_error=false) === nothing
        Context()
    end
end

LLVM.jl provides access to several of LLVM's analyses, which are part of the LLVM.Analysis vocabulary. Most of them are available to custom passes, through the analysis manager of a pass pipeline (see FunctionAnalysisManager).

IR verification

IR contained in modules and functions can be verified using the verify function, throwing a Julia exception when the IR is invalid:

julia> mod = parse(LLVM.Module,  """
         define i32 @example(i1 %cond, i32 %val) {
         entry:
           br i1 %cond, label %foo, label %bar
         foo:
           %ret = add i32 %val, 1
           br label %bar
         bar:
           ret i32 %ret
         }""");

julia> verify(mod)
ERROR: LLVM error: Instruction does not dominate all uses!
  %ret = add i32 %val, 1
  ret i32 %ret

Functions can be verified in the same way, using verify(f). To handle invalid IR without catching an exception, e.g., to report it with more context, use verification_error, which returns the verifier's message, or nothing if the IR is valid.

Dominator and post-dominator

DocTestSetup = quote
    using LLVM, LLVM.IR, LLVM.Build, LLVM.Passes, LLVM.Analysis, LLVM.ORC

    if context(; throw_error=false) === nothing
        Context()
    end

    ir = """
      define i32 @example(i1 %cond, i32 %val) {
      entry:
        br i1 %cond, label %foo, label %bar
      foo:
        %ret = add i32 %val, 1
        br label %bar
      bar:
        ret i32 %ret
      }"""
    mod = parse(LLVM.Module, ir)
    fun = only(mod.functions)
    entry, foo, bar = fun.blocks
end

Dominator and post-dominator analyses can be performed on functions by constructing respectively a DomTree and PostDomTree object, and using the dominates function:

julia> fun
define i32 @example(i1 %cond, i32 %val) {
entry:
  br i1 %cond, label %foo, label %bar

foo:                                              ; preds = %entry
  %ret = add i32 %val, 1
  br label %bar

bar:                                              ; preds = %foo, %entry
  ret i32 %ret
}

julia> tree = DomTree(fun);

julia> dominates(tree, first(entry.instructions), first(foo.instructions))
true
julia> dominates(tree, first(foo.instructions), first(bar.instructions))
false

julia> tree = PostDomTree(fun);

julia> dominates(tree, first(bar.instructions), first(foo.instructions))
true

julia> dominates(tree, first(foo.instructions), first(entry.instructions))
false

Constant ranges and known bits

Many analyses describe the possible values of integers as a range, or as the bits that are known to be zero or one. These are represented by the ConstantRange and KnownBits values, which can also be used on their own. Computations on them are performed by LLVM:

julia> r = ConstantRange(64, 0, 100)
ConstantRange(64, 0, 100)

julia> r.unsigned_max
0x0000000000000063

julia> r * ConstantRange(64, 4) + ConstantRange(64, 1)
ConstantRange(64, 1, 398)

julia> intersect_with(r, ConstantRange(64, 50, 200))
ConstantRange(64, 50, 100)

julia> ConstantRange(KnownBits(64, ~UInt64(0xff), 0))
ConstantRange(64, 0, 256)

The range and known bits of an integer value can be computed using LLVM's value tracking, by passing the value to the ConstantRange or KnownBits constructor. To also use the assumptions (llvm.assume calls) that hold at a certain point, pass the instruction at that point together with the function's assumption cache and dominator tree, which are typically obtained from the analysis manager of a custom pass:

function my_pass!(f::LLVM.Function, am)
    ac, dt = am[AssumptionCache], am[DomTree]
    for bb in f.blocks, inst in bb.instructions
        inst isa GetElementPtrInst || continue
        idx = last(inst.operands)
        r = ConstantRange(idx; at=inst, assumptions=ac, domtree=dt)
        # ...
    end
    return false
end

Loops and scalar evolution

The loops of a function are described by the LoopInfo analysis, which iterates over the outermost loops of a function. Each Loop has properties for its structure, like its header, latch, preheader, exit_blocks and nested subloops. LLVM's scalar evolution analysis (ScalarEvolution) represents integer values as symbolic expressions (SCEVs), e.g., an induction variable as an add recurrence {start,+,step}<loop>. It can compute the number of times a loop's backedge is taken (backedge_taken_count) and the step of an induction variable (step_recurrence). Both analyses are obtained from the analysis manager of a custom pass:

julia> function trip_counts!(f::LLVM.Function, am)
         li, se = am[LoopInfo], am[ScalarEvolution]
         for loop in li
           println(loop.header.name, " (depth ", loop.depth, "): ",
                   backedge_taken_count(se, loop))
           for inst in loop.header.instructions
             inst isa PHIInst || continue
             s = se[inst]
             println("  ", inst.name, " = ", s, ", step ", step_recurrence(se, s))
           end
         end
         return PreservedAnalyses(AllAnalyses)
       end;

julia> mod = parse(LLVM.Module, """
         define void @count(i64 %n) {
         entry:
           br label %loop
         loop:
           %i = phi i64 [ 0, %entry ], [ %next, %loop ]
           %next = add nuw nsw i64 %i, 2
           %done = icmp uge i64 %next, %n
           br i1 %done, label %exit, label %loop
         exit:
           ret void
         }""");

julia> run!(FunctionPass("trip-counts", trip_counts!; analyses=true), mod)
loop (depth 1): SCEVUDivExpr(((-1 + (2 umax %n)) /u 2))
  i = SCEVAddRecExpr({0,+,2}<nuw><nsw><%loop>), step SCEVConstant(2)

Like other analysis results, loops and expressions are owned by the analysis manager, and must not be used after the pass returns.