Further on in this chapter, we will be looking into register allocation. Before we head to that, however, you must understand the concepts of live variable and live interval. By live intervals, we mean the range in which a variable is live, that is, from the point where a variable is defined to its last use. For this, we need to calculate the set of registers that are immediately dead after the instruction (the last use of a variable), and the set of registers that are used by the instruction but not after the instruction. We calculate live variable information for each virtual register and physical register in the function. Using SSA to sparsely compute the lifetime information for the virtual registers enables us to only track the physical registers within a block. Before register allocation, LLVM assumes that physical registers are live only within a single basic block. This enables it to perform a single, local analysis to resolve physical register lifetimes within each basic block. After performing the live variable analysis, we have the information required for performing live interval analysis and building live intervals. For this, we start numbering the basic block and machine instructions. After that live-in values, typically arguments in registers are handled. Live intervals for virtual registers are computed for some ordering of the machine instructions (1, N). A live interval is an interval (i, j) for which a variable is live, where 1 >= i >= j > N.
In this recipe, we will take a sample program and see how we can list down the live intervals for that program. We will look at how LLVM works to calculate these intervals.
To get started, we need a piece of test code on which we will be performing live interval analysis. For simplicity, we will use C code and then convert it into LLVM IR:
- Write a test program with an
if-elseblock:$ cat interval.c void donothing(int a) { return; } int func(int i) { int a = 5; donothing(a); int m = a; donothing(m); a = 9; if (i < 5) { int b = 3; donothing(b); int z = b; donothing(z); } else { int k = a; donothing(k); } return m; }
- Use Clang to convert the C code into IR, and then view the generated IR using the
catcommand:$ clang -cc1 -emit-llvm interval.c $ cat interval.ll ; ModuleID = 'interval.c' target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" ; Function Attrs: nounwind define void @donothing(i32 %a) #0 { %1 = alloca i32, align 4 store i32 %a, i32* %1, align 4 ret void } ; Function Attrs: nounwind define i32 @func(i32 %i) #0 { %1 = alloca i32, align 4 %a = alloca i32, align 4 %m = alloca i32, align 4 %b = alloca i32, align 4 %z = alloca i32, align 4 %k = alloca i32, align 4 store i32 %i, i32* %1, align 4 store i32 5, i32* %a, align 4 %2 = load i32, i32* %a, align 4 call void @donothing(i32 %2) %3 = load i32, i32* %a, align 4 store i32 %3, i32* %m, align 4 %4 = load i32, i32* %m, align 4 call void @donothing(i32 %4) store i32 9, i32* %a, align 4 %5 = load i32, i32* %1, align 4 %6 = icmp slt i32 %5, 5 br i1 %6, label %7, label %11 ; <label>:7 ; preds = %0 store i32 3, i32* %b, align 4 %8 = load i32, i32* %b, align 4 call void @donothing(i32 %8) %9 = load i32, i32* %b, align 4 store i32 %9, i32* %z, align 4 %10 = load i32, i32* %z, align 4 call void @donothing(i32 %10) br label %14 ; <label>:11 ; preds = %0 %12 = load i32, i32* %a, align 4 store i32 %12, i32* %k, align 4 %13 = load i32, i32* %k, align 4 call void @donothing(i32 %13) br label %14 ; <label>:14 ; preds = %11, %7 %15 = load i32, i32* %m, align 4 ret i32 %15 } attributes #0 = { nounwind "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-realign-stack" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } !llvm.ident = !{!0} !0 = !{!"clang version 3.7.0 (trunk 234045)"}
- To list the live intervals, we will need to modify the code of the
LiveIntervalAnalysis.cppfile by adding code to print the live intervals. We will add the following lines (marked with a+symbol before each added line):void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { assert(LRCalc && "LRCalc not initialized."); assert(LI.empty() && "Should only compute empty intervals."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg)); computeDeadValues(LI, nullptr); /**** add the following code ****/ + llvm::outs() << "********** INTERVALS ********** "; // Dump the regunits. + for (unsigned i = 0, e = RegUnitRanges.size(); i != e; ++i) + if (LiveRange *LR = RegUnitRanges[i]) + llvm::outs() << PrintRegUnit(i, TRI) << ' ' << *LR << ' '; // Dump the virtregs. + llvm::outs() << "virtregs:"; + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (hasInterval(Reg)) + llvm::outs() << getInterval(Reg) << ' '; + } - Build LLVM after modifying the preceding source file, and install it on the path.
- Now compile the test code in the IR form using the
llccommand. You will get the live intervals:$ llc interval.ll ********** INTERVALS ********** virtregs:%vreg0 [16r,32r:0) 0@16r ********** INTERVALS ********** virtregs:%vreg0 [16r,32r:0) 0@16r ********** INTERVALS ********** virtregs:%vreg0 [16r,32r:0) 0@16r %vreg1 [80r,96r:0) 0@80r ********** INTERVALS ********** virtregs:%vreg0 [16r,32r:0) 0@16r %vreg1 [80r,96r:0) 0@80r %vreg2 [144r,192r:0) 0@144r ********** INTERVALS ********** virtregs:%vreg0 [16r,32r:0) 0@16r %vreg1 [80r,96r:0) 0@80r %vreg2 [144r,192r:0) 0@144r %vreg5 [544r,592r:0) 0@544r ********** INTERVALS ********** virtregs:%vreg0 [16r,32r:0) 0@16r %vreg1 [80r,96r:0) 0@80r %vreg2 [144r,192r:0) 0@144r %vreg5 [544r,592r:0) 0@544r %vreg6 [352r,368r:0) 0@352r ********** INTERVALS ********** virtregs:%vreg0 [16r,32r:0) 0@16r %vreg1 [80r,96r:0) 0@80r %vreg2 [144r,192r:0) 0@144r %vreg5 [544r,592r:0) 0@544r %vreg6 [352r,368r:0) 0@352r %vreg7 [416r,464r:0) 0@416r ********** INTERVALS ********** virtregs:%vreg0 [16r,32r:0) 0@16r %vreg1 [80r,96r:0) 0@80r %vreg2 [144r,192r:0) 0@144r %vreg5 [544r,592r:0) 0@544r %vreg6 [352r,368r:0) 0@352r %vreg7 [416r,464r:0) 0@416r %vreg8 [656r,672r:0) 0@656r
In the preceding example, we saw how live intervals are associated with each virtual register. The program points at the beginning and the end of live intervals are marked in square brackets. The process of generating these live intervals starts from the LiveVariables::runOnMachineFunction(MachineFunction
&mf) function in the lib/CodeGen/LiveVariables.cpp file, where it assigns the definition and usage of the registers using the HandleVirtRegUse and HandleVirtRegDef functions. It gets the VarInfo object for the given virtual register using the getVarInfo function.
The LiveInterval and LiveRange classes are defined in LiveInterval.cpp. The functions in this file takes the information on the liveliness of each variable and then checks whether they overlap or not.
In the LiveIntervalAnalysis.cpp file, we have the implementation of the live interval analysis pass, which scans the basic blocks (ordered in a linear fashion) in depth-first order, and creates a live interval for each virtual and physical register. This analysis is used by the register allocators, which will be discussed in next recipe.
- If you want to see in detail how the virtual registers for different basic blocks get generated, and see the lifetime of these virtual registers, use the
–debug-only=regalloccommand-line option with thellctool when compiling the test case. You need a debug build of the LLVM for this. - To get more detail on live intervals, go through these code files:
Lib/CodeGen/ LiveInterval.cppLib/CodeGen/ LiveIntervalAnalysis.cppLib/CodeGen/ LiveVariables.cpp