lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp

   1 /* Title:   MethodLiveVarInfo.cpp
   2    Author:  Ruchira Sasanka
   3    Date:    Jun 30, 01
   4    Purpose:
   5
   6    This is the interface for live variable info of a method that is required
   7    by any other part of the compiler.
   8
   9 */
  10
  11
  12 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
  13 #include "llvm/CodeGen/MachineInstr.h"
  14
  15
  16
  17 /************************** Constructor/Destructor ***************************/
  18
  19
  20 MethodLiveVarInfo::MethodLiveVarInfo(const Method *const M) : Meth(M),
  21                                                               BB2BBLVMap()
  22 {
  23   assert(! M->isExternal() );           // cannot be a prototype decleration
  24   HasAnalyzed = false;                  // still we haven't called analyze()
  25 }
  26
  27
  28
  29 MethodLiveVarInfo:: ~MethodLiveVarInfo()
  30 {
  31   // hash map iterator
  32   BBToBBLiveVarMapType::iterator HMI = BB2BBLVMap.begin();
  33
  34   for( ; HMI != BB2BBLVMap.end() ; HMI ++ ) {
  35     if( (*HMI).first )                  // delete all LiveVarSets in BB2BBLVMap
  36       delete (*HMI).second;
  37    }
  38 }
  39
  40
  41 // -------------------------- support functions -------------------------------
  42
  43
  44
  45 // constructs BBLiveVars and init Def and In sets
  46 void MethodLiveVarInfo::constructBBs()
  47 {
  48   unsigned int POId = 0;                // Reverse Depth-first Order ID
  49
  50   cfg::po_const_iterator BBI = cfg::po_begin(Meth);
  51
  52   for(  ; BBI != cfg::po_end(Meth) ; ++BBI, ++POId)
  53   {
  54
  55     if(DEBUG_LV) cout << " For BB " << (*BBI)->getName() << ":" << endl ;
  56
  57     const BasicBlock *BB = *BBI;        // get the current BB
  58                                         // create a new BBLiveVar
  59     BBLiveVar * LVBB = new BBLiveVar( BB, POId );
  60
  61     BB2BBLVMap[ BB ] = LVBB;            // insert the pair to Map
  62
  63     LVBB->calcDefUseSets();             // calculates the def and in set
  64
  65     if(DEBUG_LV)
  66       LVBB->printAllSets();
  67   }
  68 }
  69
  70
  71
  72 // do one backward pass over the CFG
  73 bool MethodLiveVarInfo::doSingleBackwardPass()
  74 {
  75   bool ResultFlow, NeedAnotherIteration = false;
  76
  77   if(DEBUG_LV)
  78     cout << endl <<  " After Backward Pass ..." << endl;
  79
  80   cfg::po_const_iterator BBI = cfg::po_begin(Meth);
  81
  82   for( ; BBI != cfg::po_end(Meth) ; ++BBI)
  83   {
  84
  85     BBLiveVar* LVBB = BB2BBLVMap[*BBI];
  86     assert( LVBB );
  87
  88     if(DEBUG_LV) cout << " For BB " << (*BBI)->getName() << ":"  << endl;
  89     // cout << " (POId=" << LVBB->getPOId() << ")" << endl ;
  90
  91     ResultFlow = false;
  92
  93     if( LVBB->isOutSetChanged() )
  94       LVBB->applyTransferFunc();        // apply the Tran Func to calc InSet
  95
  96     if( LVBB->isInSetChanged() )        // to calc Outsets of preds
  97       ResultFlow = LVBB->applyFlowFunc(BB2BBLVMap);
  98
  99     if(DEBUG_LV) LVBB->printInOutSets();
 100
 101
 102     if( ResultFlow ) NeedAnotherIteration = true;
 103
 104   }
 105
 106   // true if we need to reiterate over the CFG
 107   return NeedAnotherIteration;
 108 }
 109
 110
 111
 112
 113
 114 // performs live var anal for a method
 115 void MethodLiveVarInfo::analyze()
 116 {
 117   // Don't analyze the same method twice!
 118   // Later, we need to add change notification here.
 119   if (HasAnalyzed)
 120     return;
 121
 122   if( DEBUG_LV) cout << "Analysing live variables ..." << endl;
 123
 124   // create and initialize all the BBLiveVars of the CFG
 125   constructBBs();
 126
 127   bool NeedAnotherIteration = false;
 128   do {                                // do one  pass over  CFG
 129     NeedAnotherIteration = doSingleBackwardPass( );
 130   } while (NeedAnotherIteration );    // repeat until we need more iterations
 131
 132
 133   HasAnalyzed  = true;                // finished analysing
 134
 135   if( DEBUG_LV) cout << "Live Variable Analysis complete!" << endl;
 136 }
 137
 138
 139
 140
 141 /* Thsese functions will give the LiveVar info for any machine instruction in
 142    a method. It should be called after a call to analyze().
 143
 144    Thsese functions calucluates live var info for all the machine instrs in a
 145    BB when LVInfo for one inst is requested. Hence, this function is useful
 146    when live var info is required for many (or all) instructions in a basic
 147    block. Also, the arguments to this method does not require specific
 148    iterators.
 149 */
 150
 151
 152 const LiveVarSet *
 153 MethodLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *const MInst,
 154                                             const BasicBlock *const CurBB)
 155 {
 156   const LiveVarSet *LVSet = MInst2LVSetBI[MInst];
 157
 158   if( LVSet  ) return LVSet;              // if found, just return the set
 159   else {
 160     calcLiveVarSetsForBB( CurBB );        // else, calc for all instrs in BB
 161     assert( MInst2LVSetBI[ MInst ] );
 162     return  MInst2LVSetBI[ MInst ];
 163   }
 164 }
 165
 166
 167 const LiveVarSet *
 168 MethodLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *const MInst,
 169                                             const BasicBlock *const CurBB)
 170 {
 171   const LiveVarSet *LVSet = MInst2LVSetAI[MInst];
 172
 173   if( LVSet  ) return LVSet;              // if found, just return the set
 174   else {
 175     calcLiveVarSetsForBB( CurBB );        // else, calc for all instrs in BB
 176     assert( MInst2LVSetAI[ MInst ] );
 177     return  MInst2LVSetAI[ MInst ];
 178   }
 179 }
 180
 181
 182 void MethodLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *const BB)
 183 {
 184   const MachineCodeForBasicBlock& MIVec = BB->getMachineInstrVec();
 185   MachineCodeForBasicBlock::const_reverse_iterator
 186     MInstIterator = MIVec.rbegin();
 187
 188   LiveVarSet *CurSet = new LiveVarSet();
 189   const LiveVarSet *SetAI = getOutSetOfBB(BB); // init SetAI with OutSet
 190   CurSet->setUnion(SetAI);                     // CurSet now contains OutSet
 191
 192   // iterate over all the machine instructions in BB
 193   for( ; MInstIterator != MIVec.rend(); MInstIterator++) {
 194
 195     // MInst is cur machine inst
 196     const MachineInstr * MInst  = *MInstIterator;
 197
 198     MInst2LVSetAI[MInst] = SetAI;              // record in After Inst map
 199
 200     CurSet->applyTranferFuncForMInst( MInst ); // apply the transfer Func
 201     LiveVarSet *NewSet = new LiveVarSet();     // create a new set and
 202     NewSet->setUnion( CurSet );                // copy the set after T/F to it
 203
 204     MInst2LVSetBI[MInst] = NewSet;             // record in Before Inst map
 205
 206     // SetAI will be used in the next iteration
 207     SetAI = NewSet;
 208   }
 209
 210 }
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227