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:
if
- else
block:$ 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; }
cat
command:$ 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)"}
LiveIntervalAnalysis.cpp
file 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) << ' '; + }
llc
command. 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.
–debug-only=regalloc
command-line option with the llc
tool when compiling the test case. You need a debug build of the LLVM for this.Lib/CodeGen/ LiveInterval.cpp
Lib/CodeGen/ LiveIntervalAnalysis.cpp
Lib/CodeGen/ LiveVariables.cpp
18.118.9.197