8 Purpose: This file contains implementation information about live variable
10 Author : Ruchira Sasanka
17 The class MethodLiveVarInfo (declared in MethodLiveVarInfo.h and implemented in
18 MethodLiveVarInfo.cpp) is the main entry point of live variable analysis. This
19 class performs live variable analysis of one method. This class implements
20 iterative live variable analysis.
25 This class must be used like:
27 MethodLiveVarInfo MLVI( Mehtod *); // initializes data structures
28 MLVI.analyze(); // do the actual live variable anal
31 After the live variable analysis is complete, the user can call methods to get
33 (1) InSet/OutSet of any BasicBlock:
35 (a) MethodLiveVarInfo::getOutSetOfBB
36 (b) MethodLiveVarInfo::getInSetOfBB
38 (2) Any LiveVarSet before/after a machine instruction in method:
40 (a) MethodLiveVarInfo::getLiveVarSetBeforeMInst
41 (b) MethodLiveVarInfo::getLiveVarSetBeforeMInst
43 See MethodLiveVarInfo.h for interface methods.
48 The live var set before an instruction can be obtained in 2 ways:
50 1. Use the method getLiveVarSetAfterInst(Instruction *) to get the LV Info
51 just after an instruction. (also exists getLiveVarSetBeforeInst(..))
53 This function calculates the LV info for a BB only once and caches that
54 info. If the cache does not contain the LV info of the instruction, it
55 calculates the LV info for the whole BB and caches them.
57 Getting liveVar info this way uses more memory since, LV info should be
58 cached. However, if you need LV info of nearly all the instructions of a
59 BB, this is the best and simplest interface.
62 2. Use the OutSet and applyTranferFuncForInst(const Instruction *const Inst)
63 declared in LiveVarSet and traverse the instructions of a basic block in
64 reverse (using const_reverse_iterator in the BB class).
66 This is the most memory efficient method if you need LV info for
67 only several instructions in a BasicBlock. An example is given below:
70 LiveVarSet LVSet; // this will be the set used to traverse through each BB
72 // Initialize LVSet so that it is the same as OutSet of the BB
73 LVSet.setUnion( LVI->getOutSetOfBB( *BBI ) );
75 BasicBlock::InstListType::const_reverse_iterator
76 InstIterator = InstListInBB.rbegin(); // get the rev iter for inst in BB
78 // iterate over all the instructions in BB in reverse
79 for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
81 //...... all code here which uses LVSet ........
83 LVSet.applyTranferFuncForInst(*InstIterator);
85 // Now LVSet contains live vars ABOVE the current instruction
88 See buildInterferenceGraph() in ../llvm/lib/CodeGen/RegAlloc/ for the
92 4. Input and Preconditions
93 ==========================
95 Live variable analysis is done using machine instructions. The constructor
96 to the class takes a pointer to a method, and machine instructions must be
97 already available for this method before calling the constructor.
99 The preconditions are:
101 1. Instruction selection is complete (i.e., machine instructions are
102 generated) for the method before the live variable analysis
108 1. There may be dummy phi machine instructions in the machine code. The code
109 works with and without dummy phi instructions (i.e., this code can be
110 called before or after phi elimination). Currently, it is called without
113 2. Only the basic blocks that can be reached by the post-order iterator will
114 be analyzed (i.e., basic blocks for dead code will not be analyzed). The
115 live variable sets returned for such basic blocks is not defined.
119 6. Data Structures, Classes and Main Objects
120 ============================================
122 LiveVarSet: This class implements a basic live variable set. It contains a
123 set of Value objects.
125 BBLiveVar: This class is used to keep live variable information like the inset,
126 outset, etc. about a basic block. We create one object of this type for each
127 basic block in the original method in MethodLiveVarInfo::constructBBs(). This
128 class is declared in BBLiveVar.h
131 BBToBBLiveVarMapType: This class is used to create a map between the original
132 basic blocks in the method and new BBLiveVar objects created for each original
133 basic block. There is only one object of this type called BB2BBLVMap in
134 class MethodLiveVarInfo.
136 MInstToLiveVarSetMapType: This class is used to create a map between a machine
137 instruction and a LiveVarSet before/after that machine instruction. There are
138 two objects of this type: MInst2LVSetBI and MInst2LVSetAI, declared in
139 class is declared in BBLiveVar.h. Both these objects are used as caches. When a
140 user of class MethodLiveVarInfo requests a LiveVarSet before/after a machine'
141 instruction, these two caches are used to find the those live variable sets
142 quickly. See MethodLiveVarInfo::calcLiveVarSetsForBB for implementation.
148 7.1 LiveVaraible Analysis Algorithm
149 ------------------------------------
151 Live variable analysis is done using iterative analysis. The main steps are:
153 1. Construct BBLiveVar objects for each BasicBlock in the method.
154 2. While OutSets change
155 do one pass over the entire CFG
158 The above algorithm is implemented in:
160 MethodLiveVarInfo::analyze()
161 MethodLiveVarInfo::doSingleBackwardPass()
165 7.2 Algorithm for obtaining LiveVarSets before/after a machine instruction
166 --------------------------------------------------------------------------
168 LiveVarSets before/after a machine instruction can be obtained using:
170 (a) MethodLiveVarInfo::getLiveVarSetBeforeMInst
171 (b) MethodLiveVarInfo::getLiveVarSetBeforeMInst
173 The basic algorithm is:
175 1. When a LiveVarSet before/after a machine instruction is requested, look
176 in the MInst2LVSetBI/MInst2LVSetAI to see whether a LiveVarSet is
177 calculated and already entered in the corresponding cache.
180 just return the LiveVarSet from the cache
182 call MethodLiveVarInfo::calcLiveVarSetsForBB to calculate live variable
183 sets for ALL machine instructions in a BasicBlock and to enter all
184 those calculated LiveVarSets in caches ( MInst2LVSetBI/MInst2LVSetAI)
189 If it is necessary to do live variable analysis using LLVM instructions rather
190 than using machine instructions, it is easy to modify the existing code to
191 do so. Current implementation use isDef() to find any MachineOperand is a
192 definition or a use. We just need to change all the places that check whether
193 a particular Value is a definition/use with MachineInstr. Instead, we
194 would check whether an LLVM value is a def/use using LLVM instructions. All
195 the underlying data structures will remain the same. However, iterators that
196 go over machine instructions must be changed to the corresponding iterators
197 that go over the LLVM instructions. The logic to support Phi's in LLVM
198 instructions is already there. In fact, live variable analysis was first
199 done using LLVM instructions and later changed to use machine instructions.
200 Hence, it is quite straightforward to revert it to LLVM instructions if