Analyses

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

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

julia> fundefine i32 @example(i1 %cond, i32 %val) {entry:  br i1 %cond, label %foo, label %barfoo:                                              ; preds = %entry  %ret = add i32 %val, 1  br label %barbar:                                              ; preds = %foo, %entry  ret i32 %ret}julia> tree = DomTree(fun);julia> dominates(tree, first(entry.instructions), first(foo.instructions))truejulia> dominates(tree, first(foo.instructions), first(bar.instructions))falsejulia> tree = PostDomTree(fun);julia> dominates(tree, first(bar.instructions), first(foo.instructions))truejulia> 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_max0x0000000000000063julia> 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 falseend

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.