====================== Live Variable Analysis ====================== 1. Introduction =============== Purpose: This file contains implementation information about live variable analysis. Author : Ruchira Sasanka Date : Dec 8, 2001 2. Entry Point ============== The class MethodLiveVarInfo (declared in MethodLiveVarInfo.h and implemented in MethodLiveVarInfo.cpp) is the main entry point of live variable analysis. This class performs live variable analysis of one method. This class implements iterative live variable analysis. 3. Usage ======== This class must be used like: MethodLiveVarInfo MLVI( Mehtod *); // initializes data structures MLVI.analyze(); // do the actual live variable anal After the live variable analysis is complete, the user can call methods to get (1) InSet/OutSet of any BasicBlock: (a) MethodLiveVarInfo::getOutSetOfBB (b) MethodLiveVarInfo::getInSetOfBB (2) Any LiveVarSet before/after a machine instruction in method: (a) MethodLiveVarInfo::getLiveVarSetBeforeMInst (b) MethodLiveVarInfo::getLiveVarSetBeforeMInst See MethodLiveVarInfo.h for interface methods. Note: ---- The live var set before an instruction can be obtained in 2 ways: 1. Use the method getLiveVarSetAfterInst(Instruction *) to get the LV Info just after an instruction. (also exists getLiveVarSetBeforeInst(..)) This function calculates the LV info for a BB only once and caches that info. If the cache does not contain the LV info of the instruction, it calculates the LV info for the whole BB and caches them. Getting liveVar info this way uses more memory since, LV info should be cached. However, if you need LV info of nearly all the instructions of a BB, this is the best and simplest interface. 2. Use the OutSet and applyTranferFuncForInst(const Instruction *const Inst) declared in LiveVarSet and traverse the instructions of a basic block in reverse (using const_reverse_iterator in the BB class). This is the most memory efficient method if you need LV info for only several instructions in a BasicBlock. An example is given below: LiveVarSet LVSet; // this will be the set used to traverse through each BB // Initialize LVSet so that it is the same as OutSet of the BB LVSet.setUnion( LVI->getOutSetOfBB( *BBI ) ); BasicBlock::InstListType::const_reverse_iterator InstIterator = InstListInBB.rbegin(); // get the rev iter for inst in BB // iterate over all the instructions in BB in reverse for( ; InstIterator != InstListInBB.rend(); InstIterator++) { //...... all code here which uses LVSet ........ LVSet.applyTranferFuncForInst(*InstIterator); // Now LVSet contains live vars ABOVE the current instruction } See buildInterferenceGraph() in ../llvm/lib/CodeGen/RegAlloc/ for the above example. 4. Input and Preconditions ========================== Live variable analysis is done using machine instructions. The constructor to the class takes a pointer to a method, and machine instructions must be already available for this method before calling the constructor. The preconditions are: 1. Instruction selection is complete (i.e., machine instructions are generated) for the method before the live variable analysis 5. Assumptions ============== 1. There may be dummy phi machine instructions in the machine code. The code works with and without dummy phi instructions (i.e., this code can be called before or after phi elimination). Currently, it is called without phi instructions. 2. Only the basic blocks that can be reached by the post-order iterator will be analyzed (i.e., basic blocks for dead code will not be analyzed). The live variable sets returned for such basic blocks is not defined. 6. Data Structures, Classes and Main Objects ============================================ LiveVarSet: This class implements a basic live variable set. It contains a set of Value objects. BBLiveVar: This class is used to keep live variable information like the inset, outset, etc. about a basic block. We create one object of this type for each basic block in the original method in MethodLiveVarInfo::constructBBs(). This class is declared in BBLiveVar.h BBToBBLiveVarMapType: This class is used to create a map between the original basic blocks in the method and new BBLiveVar objects created for each original basic block. There is only one object of this type called BB2BBLVMap in class MethodLiveVarInfo. MInstToLiveVarSetMapType: This class is used to create a map between a machine instruction and a LiveVarSet before/after that machine instruction. There are two objects of this type: MInst2LVSetBI and MInst2LVSetAI, declared in class is declared in BBLiveVar.h. Both these objects are used as caches. When a user of class MethodLiveVarInfo requests a LiveVarSet before/after a machine' instruction, these two caches are used to find the those live variable sets quickly. See MethodLiveVarInfo::calcLiveVarSetsForBB for implementation. 7. Algorithms ============= 7.1 LiveVaraible Analysis Algorithm ------------------------------------ Live variable analysis is done using iterative analysis. The main steps are: 1. Construct BBLiveVar objects for each BasicBlock in the method. 2. While OutSets change do one pass over the entire CFG The above algorithm is implemented in: MethodLiveVarInfo::analyze() MethodLiveVarInfo::doSingleBackwardPass() 7.2 Algorithm for obtaining LiveVarSets before/after a machine instruction -------------------------------------------------------------------------- LiveVarSets before/after a machine instruction can be obtained using: (a) MethodLiveVarInfo::getLiveVarSetBeforeMInst (b) MethodLiveVarInfo::getLiveVarSetBeforeMInst The basic algorithm is: 1. When a LiveVarSet before/after a machine instruction is requested, look in the MInst2LVSetBI/MInst2LVSetAI to see whether a LiveVarSet is calculated and already entered in the corresponding cache. If yes, just return the LiveVarSet from the cache Else call MethodLiveVarInfo::calcLiveVarSetsForBB to calculate live variable sets for ALL machine instructions in a BasicBlock and to enter all those calculated LiveVarSets in caches ( MInst2LVSetBI/MInst2LVSetAI) 8. Future work ============== If it is necessary to do live variable analysis using LLVM instructions rather than using machine instructions, it is easy to modify the existing code to do so. Current implementation use isDef() to find any MachineOperand is a definition or a use. We just need to change all the places that check whether a particular Value is a definition/use with MachineInstr. Instead, we would check whether an LLVM value is a def/use using LLVM instructions. All the underlying data structures will remain the same. However, iterators that go over machine instructions must be changed to the corresponding iterators that go over the LLVM instructions. The logic to support Phi's in LLVM instructions is already there. In fact, live variable analysis was first done using LLVM instructions and later changed to use machine instructions. Hence, it is quite straightforward to revert it to LLVM instructions if necessary.