Getting the use and def of an llvm instruction

Question

I am attempting to carry out liveness analysis and in order to do so I need to obtain the def and use sets for all of my nodes, where they are defined as follows:

def[n] = set of all variables defined at node n

use[n] = set of all variables used at node n

So for example in the line:

a = b + c

def[n] = {a}

use[n] = {b,c}

How can I do this?

Answer 1

http://llvm.org/docs/ProgrammersManual.html#iterating-over-def-use-use-def-chains

I hope this page can help you. User objects that access the user_begin (), user_end (), and users () methods in the Value object are those that use the Value object. The Instruction class is a subclass of the User class.

I may be wrong, but to get the def-use set in the IR level, the elements of the set should be Value objects, and each node should be an Instruction object.
Therefore, the def set for each node will be the Value object returned by the instruction(There is a possible case that the instruction doesn't return. And that case, def set is empty set.), and the use set will be the User object accessed through the user_iterator of the instruction.

Answer 2

Basically, when we define a local variable in LLVM it uses AllocaInst. Here's the example that you have put up:

a=b+c

in C code:

int a;
int b=10;
int c=10;
a=b+c;

In LLVM IR compiled with -g (debug mode):

%a = alloca i32, align 4
%b = alloca i32, align 4
%c = alloca i32, align 4
call void @llvm.dbg.declare(metadata i32* %a, metadata !14, metadata !16),
... !dbg !17
call void @llvm.dbg.declare(metadata i32* %b, metadata !18, metadata !16),
... !dbg !19
store i32 10, i32* %b, align 4, !dbg !19
call void @llvm.dbg.declare(metadata i32* %c, metadata !20, metadata !16),
... !dbg !21
store i32 10, i32* %c, align 4, !dbg !21
%0 = load i32, i32* %b, align 4, !dbg !22
%1 = load i32, i32* %c, align 4, !dbg !23
%add = add nsw i32 %0, %1, !dbg !24
store i32 %add, i32* %a, align 4, !dbg !25

Let's see how to use the LLVM API to collect def-use chains. It is easy as LLVM has an in-house built-in API at function level for this one:

bool runOnFunction(Function &F){
    errs() << "digraph " + F.getName() + "{\n";
    errs() << "\n";
    for (auto block = F.getBasicBlockList().begin(); block != F.getBasicBlockList().end(); block++) {
        for (auto inst = block->begin(); inst != block->end(); inst++) {
            for (Use &U:inst->operands()) {
                Value *v = U.get();
                if (dyn_cast<Instruction>(v)) {
                    errs() << "\"" << *dyn_cast<Instruction>(v) << "\"" << " -> " << "\"" << *inst << "\"" << ";\n";
                }
                if (v->getName() != "") {
                    errs() << "\"" << v->getName() << "\"" << " -> " << "\"" << *inst << "\"" << ";\n";
                    errs() << "\"" << v->getName() << "\"" << " [ color = red ]\n";
                }
            }
        }
    }
    errs() << "\n}\n";
}

For def-use chains, simple tract alloca and user.

This will generate a PDG.

The code taken from https://github.com/DengMinghua/LLVM-Program-Dependency-Graph-Generator

Hope this helps.