lib/Analysis/LiveVar/README

   1                         ======================
   2                         Live Variable Analysis
   3                         ======================
   4
   5 1. Introduction
   6 ===============
   7
   8 Purpose: This file contains implementation information about live variable
   9          analysis.
  10 Author : Ruchira Sasanka
  11 Date   : Dec 8, 2001
  12
  13
  14
  15 2. Entry Point
  16 ==============
  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.
  21
  22
  23 3. Usage
  24 ========
  25 This class must be used like:
  26
  27        MethodLiveVarInfo MLVI( Mehtod *);  // initializes data structures
  28        MLVI.analyze();                     // do the actual live variable anal
  29
  30
  31 After the live variable analysis is complete, the user can call methods to get
  32
  33 (1) InSet/OutSet of any BasicBlock:
  34
  35      (a) MethodLiveVarInfo::getOutSetOfBB
  36      (b) MethodLiveVarInfo::getInSetOfBB
  37
  38 (2) Any LiveVarSet before/after a machine instruction in method:
  39
  40      (a) MethodLiveVarInfo::getLiveVarSetBeforeMInst
  41      (b) MethodLiveVarInfo::getLiveVarSetBeforeMInst
  42
  43  See MethodLiveVarInfo.h for interface methods.
  44
  45
  46  Note:
  47  ----
  48  The live var set before an instruction can be obtained in 2 ways:
  49
  50  1. Use the method getLiveVarSetAfterInst(Instruction *) to get the LV Info
  51     just after an instruction. (also exists getLiveVarSetBeforeInst(..))
  52
  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.
  56
  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.
  60
  61
  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).
  65
  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:
  68
  69
  70     LiveVarSet LVSet;  // this will be the set used to traverse through each BB
  71
  72     // Initialize LVSet so that it is the same as OutSet of the BB
  73     LVSet.setUnion( LVI->getOutSetOfBB( *BBI ) );
  74
  75     BasicBlock::InstListType::const_reverse_iterator
  76       InstIterator = InstListInBB.rbegin(); // get the rev iter for inst in BB
  77
  78       // iterate over all the instructions in BB in reverse
  79     for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
  80
  81       //...... all  code here which uses LVSet ........
  82
  83       LVSet.applyTranferFuncForInst(*InstIterator);
  84
  85       // Now LVSet contains live vars ABOVE the current instruction
  86     }
  87
  88     See buildInterferenceGraph() in ../llvm/lib/CodeGen/RegAlloc/ for the
  89     above example.
  90
  91
  92 4. Input and Preconditions
  93 ==========================
  94
  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.
  98
  99 The preconditions are:
 100
 101 1. Instruction selection is complete (i.e., machine instructions are
 102    generated) for the method before the live variable analysis
 103
 104
 105
 106 5. Assumptions
 107 ==============
 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
 111    phi instructions.
 112
 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.
 116
 117
 118
 119 6. Data Structures, Classes and Main Objects
 120 ============================================
 121
 122 LiveVarSet: This class implements a basic live variable set. It contains a
 123 set of Value objects.
 124
 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
 129
 130
 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.
 135
 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.
 143
 144
 145 7. Algorithms
 146 =============
 147
 148 7.1 LiveVaraible Analysis Algorithm
 149 ------------------------------------
 150
 151 Live variable analysis is done using iterative analysis. The main steps are:
 152
 153 1. Construct BBLiveVar objects for each BasicBlock in the method.
 154 2. While OutSets change
 155      do one pass over the entire CFG
 156
 157
 158 The above algorithm is implemented in:
 159
 160         MethodLiveVarInfo::analyze()
 161         MethodLiveVarInfo::doSingleBackwardPass()
 162
 163
 164
 165 7.2 Algorithm for obtaining LiveVarSets before/after a machine instruction
 166 --------------------------------------------------------------------------
 167
 168  LiveVarSets before/after a machine instruction can be obtained using:
 169
 170      (a) MethodLiveVarInfo::getLiveVarSetBeforeMInst
 171      (b) MethodLiveVarInfo::getLiveVarSetBeforeMInst
 172
 173  The basic algorithm is:
 174
 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.
 178
 179    If yes,
 180         just return the LiveVarSet from the cache
 181    Else
 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)
 185
 186
 187 8. Future work
 188 ==============
 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
 201 necessary.
 202
 203
 204
 205
 206
 207
 208