LLVM Interface | DominatorTree

Tech, LLVM
Page content

LLVM infrastructure provides numerous interfaces to meet various requirements. However, lots of interfaces lack clear documents and example code. It is time-consuming for newcomers, including me, to find the ideal APIs and figure out their usage. To tackle this, I will write a series of articles that contain LLVM Interface in titles focusing on the useful APIs for program analysis. The contents of them will be short and concentrate more on concrete use cases than internal principles.

This blog discusses the class DominatorTree. In computer science, a node d of a control-flow graph dominates a node n if every path from the entry node to n must go through d. The class DominatorTree is designed to express the dominance relationships in code.

Methods

Ref

bool dominates

This method returns a boolean value to indicate whether the first argument dominates the second argument. The most common usage is to pass two BasicBlock * as the arguments. However, this method also supports the variables in types Instruction *, BasicBlockEdge * and so on as the arguments. Please refer to unittests/IR/DominatorTreeTest.cpp.

bool isReachableFromEntry(const NodeT *A) const

This method returns a boolean value to indicate whether the argument is reachable from the function entry.

void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const

This method retrieves all the nodes dominated by R and stores them in Result.

Example

Here we present a code example of calculating Fibonacci sequence written in LLVM IR. Then we apply the aforementioned methods to this function, as shown below.

#include "llvm/IR/Module.h"
#include "llvm/Support/SourceMgr.h"
#include "llvm/AsmParser/Parser.h"
#include "llvm/IR/Dominators.h"

using namespace std;
using namespace llvm;

unique_ptr<Module> makeLLVMModule(LLVMContext &Context, StringRef Str) {
    SMDiagnostic Err;
    unique_ptr<Module> M = parseAssemblyString(Str, Err, Context);
    assert(M && "Bad assembly?");
    return M;
}

int main(void) {
    StringRef I = R"(
    define i32 @factorial(i32 %0) {
        entry:
          %eq = icmp eq i32 %0, 0
          br i1 %eq, label %then, label %else

        then:                                             ; preds = %entry
          br label %ifcont

        else:                                             ; preds = %entry
          %sub = sub i32 %0, 1
          %1 = call i32 @factorial(i32 %sub)
          %mult = mul i32 %0, %1
          br label %ifcont

        ifcont:                                           ; preds = %else, %then
          %iftmp = phi i32 [ 1, %then ], [ %mult, %else ]
          ret i32 %iftmp

        dead:
          br label %entry
    }
    )";
    LLVMContext Context;
    unique_ptr<Module> M = makeLLVMModule(Context, I);

    Function *F = M->getFunction("factorial");
    DominatorTree DT(*F);

    for (BasicBlock &B : *F) {
        for (BasicBlock &Blk : *F) {
            errs() << B.getName() << "->" << Blk.getName() << ": ";
            if (DT.dominates(&B, &Blk)) {
                errs() << "dominate\n";
            } else {
                errs() << "not dominate\n";
            }
        }
    }

    for (BasicBlock &B : *F) {
        if(!DT.isReachableFromEntry(&B)) {
            errs() << B.getName() << " is not reachable\n";
        }
    }

    BasicBlock &BEntry = *(F->begin());
    SmallVector<BasicBlock*, 8> SV;
    DT.getDescendants(&BEntry, SV);
    errs() << "== Basic blocks dominated by entry: ==\n";
    for (BasicBlock *B : SV) {
        errs() << B->getName() << "\n";
    }

    return 0;
}

The output is shown below:

entry->entry: dominate
entry->then: dominate
entry->else: dominate
entry->ifcont: dominate
entry->dead: dominate
then->entry: not dominate
then->then: dominate
then->else: not dominate
then->ifcont: not dominate
then->dead: dominate
else->entry: not dominate
else->then: not dominate
else->else: dominate
else->ifcont: not dominate
else->dead: dominate
ifcont->entry: not dominate
ifcont->then: not dominate
ifcont->else: not dominate
ifcont->ifcont: dominate
ifcont->dead: dominate
dead->entry: not dominate
dead->then: not dominate
dead->else: not dominate
dead->ifcont: not dominate
dead->dead: dominate
dead is not reachable
== Basic blocks dominated by entry: ==
entry
else
ifcont
then