How does LLVM perform Liveness Analysis?

user_12929067 0
Viewed 1341

I'm a beginner who just studied the basics of compiler.

While digging LLVM, I'm not sure where to lookup the liveness analysis part.

From my understanding, the program that turned into LLVM IR turns into DAG and then to MIR.

This slides introduces liveness tracking, and I assumed that the liveness analysis occurs at MIR.

So I'm looking upon the source codes like LiveVariables.cpp, LiveIntervalAnalysis.cpp, but I'm not sure how where does the code defines stuffs like def, kill, imp-use.

Can anyone tell me where I can find those codes and how to dump information during the process?

Thanks,

Jake

analysis llvm compiler-construction
1 Answers

LLVM uses an SSA-form intermediate representation. SSA-form IR means that each variable is defined exactly once and every use is dominated by its definition. Domination is a concept in graph theory that essentially means that every path to the use in the control flow graph must pass through its definition. There is plenty of information about SSA and how to construct SSA from a traditional IR out there on the web if you look.

In practice, this choice makes traditional liveness analysis based on dataflow equations unnecessary. Instead of computing the live-in set of every basic block, SSA compilers merely provide a function to answer the question "is this variable live at this location?"

LLVM's liveness analysis for the purposes of register allocation is done in the target-independent code generator, which means that much of the code can be found in the lib/CodeGen directory. In particular you are probably interested in MachineBasicBlock::computeRegisterLiveness as well as lib/CodeGen/LiveVariables.cpp

user_98486420
Related