lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp

   1 //===-- FunctionLiveVarInfo.cpp - Live Variable Analysis for a Function ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This is the interface to function level live variable information that is
  11 // provided by live variable analysis.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "FunctionLiveVarInfo.h"
  16 #include "llvm/CodeGen/MachineInstr.h"
  17 #include "llvm/CodeGen/MachineFunction.h"
  18 #include "llvm/Target/TargetMachine.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Support/CFG.h"
  21 #include "Support/PostOrderIterator.h"
  22 #include "Support/SetOperations.h"
  23 #include "Support/CommandLine.h"
  24 #include "BBLiveVar.h"
  25 #include <iostream>
  26
  27 namespace llvm {
  28
  29 static RegisterAnalysis<FunctionLiveVarInfo>
  30 X("livevar", "Live Variable Analysis");
  31
  32 LiveVarDebugLevel_t DEBUG_LV;
  33
  34 static cl::opt<LiveVarDebugLevel_t, true>
  35 DEBUG_LV_opt("dlivevar", cl::Hidden, cl::location(DEBUG_LV),
  36              cl::desc("enable live-variable debugging information"),
  37              cl::values(
  38 clEnumValN(LV_DEBUG_None   , "n", "disable debug output"),
  39 clEnumValN(LV_DEBUG_Normal , "y", "enable debug output"),
  40 clEnumValN(LV_DEBUG_Instr,   "i", "print live-var sets before/after "
  41            "every machine instrn"),
  42 clEnumValN(LV_DEBUG_Verbose, "v", "print def, use sets for every instrn also"),
  43                         clEnumValEnd));
  44
  45
  46
  47 //-----------------------------------------------------------------------------
  48 // Accessor Functions
  49 //-----------------------------------------------------------------------------
  50
  51 // gets OutSet of a BB
  52 const ValueSet &FunctionLiveVarInfo::getOutSetOfBB(const BasicBlock *BB) const {
  53   return BBLiveVarInfo.find(BB)->second->getOutSet();
  54 }
  55       ValueSet &FunctionLiveVarInfo::getOutSetOfBB(const BasicBlock *BB)       {
  56   return BBLiveVarInfo[BB]->getOutSet();
  57 }
  58
  59 // gets InSet of a BB
  60 const ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const {
  61   return BBLiveVarInfo.find(BB)->second->getInSet();
  62 }
  63 ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB) {
  64   return BBLiveVarInfo[BB]->getInSet();
  65 }
  66
  67
  68 //-----------------------------------------------------------------------------
  69 // Performs live var analysis for a function
  70 //-----------------------------------------------------------------------------
  71
  72 bool FunctionLiveVarInfo::runOnFunction(Function &F) {
  73   M = &F;
  74   if (DEBUG_LV) std::cerr << "Analysing live variables ...\n";
  75
  76   // create and initialize all the BBLiveVars of the CFG
  77   constructBBs(M);
  78
  79   unsigned int iter=0;
  80   while (doSingleBackwardPass(M, iter++))
  81     ; // Iterate until we are done.
  82
  83   if (DEBUG_LV) std::cerr << "Live Variable Analysis complete!\n";
  84   return false;
  85 }
  86
  87
  88 //-----------------------------------------------------------------------------
  89 // constructs BBLiveVars and init Def and In sets
  90 //-----------------------------------------------------------------------------
  91
  92 void FunctionLiveVarInfo::constructBBs(const Function *F) {
  93   unsigned POId = 0;                // Reverse Depth-first Order ID
  94   std::map<const BasicBlock*, unsigned> PONumbering;
  95
  96   for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
  97       BBI != BBE; ++BBI)
  98     PONumbering[*BBI] = POId++;
  99
 100   MachineFunction &MF = MachineFunction::get(F);
 101   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 102     const BasicBlock &BB = *I->getBasicBlock();        // get the current BB
 103     if (DEBUG_LV) std::cerr << " For BB " << RAV(BB) << ":\n";
 104
 105     BBLiveVar *LVBB;
 106     std::map<const BasicBlock*, unsigned>::iterator POI = PONumbering.find(&BB);
 107     if (POI != PONumbering.end()) {
 108       // create a new BBLiveVar
 109       LVBB = new BBLiveVar(BB, *I, POId);
 110     } else {
 111       // The PO iterator does not discover unreachable blocks, but the random
 112       // iterator later may access these blocks.  We must make sure to
 113       // initialize unreachable blocks as well.  However, LV info is not correct
 114       // for those blocks (they are not analyzed)
 115       //
 116       LVBB = new BBLiveVar(BB, *I, ++POId);
 117     }
 118     BBLiveVarInfo[&BB] = LVBB;
 119
 120     if (DEBUG_LV)
 121       LVBB->printAllSets();
 122   }
 123 }
 124
 125
 126 //-----------------------------------------------------------------------------
 127 // do one backward pass over the CFG (for iterative analysis)
 128 //-----------------------------------------------------------------------------
 129
 130 bool FunctionLiveVarInfo::doSingleBackwardPass(const Function *M,
 131                                                unsigned iter) {
 132   if (DEBUG_LV) std::cerr << "\n After Backward Pass " << iter << "...\n";
 133
 134   bool NeedAnotherIteration = false;
 135   for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
 136        BBI != BBE; ++BBI) {
 137     BBLiveVar *LVBB = BBLiveVarInfo[*BBI];
 138     assert(LVBB && "BasicBlock information not set for block!");
 139
 140     if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n";
 141
 142     // InSets are initialized to "GenSet". Recompute only if OutSet changed.
 143     if(LVBB->isOutSetChanged())
 144       LVBB->applyTransferFunc();        // apply the Tran Func to calc InSet
 145
 146     // OutSets are initialized to EMPTY.  Recompute on first iter or if InSet
 147     // changed.
 148     if (iter == 0 || LVBB->isInSetChanged())        // to calc Outsets of preds
 149       NeedAnotherIteration |= LVBB->applyFlowFunc(BBLiveVarInfo);
 150
 151     if (DEBUG_LV) LVBB->printInOutSets();
 152   }
 153
 154   // true if we need to reiterate over the CFG
 155   return NeedAnotherIteration;
 156 }
 157
 158
 159 void FunctionLiveVarInfo::releaseMemory() {
 160   // First remove all BBLiveVars created in constructBBs().
 161   if (M) {
 162     for (Function::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
 163       delete BBLiveVarInfo[I];
 164     BBLiveVarInfo.clear();
 165   }
 166   M = 0;
 167
 168   // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB
 169   // and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches
 170   // to return ValueSet's before/after a machine instruction quickly).
 171   // We do not need to free up ValueSets in MInst2LVSetAI because it holds
 172   // pointers to the same sets as in MInst2LVSetBI (for all instructions
 173   // except the last one in a BB) or in BBLiveVar (for the last instruction).
 174   //
 175   for (hash_map<const MachineInstr*, ValueSet*>::iterator
 176          MI = MInst2LVSetBI.begin(),
 177          ME = MInst2LVSetBI.end(); MI != ME; ++MI)
 178     delete MI->second;           // delete all ValueSets in  MInst2LVSetBI
 179
 180   MInst2LVSetBI.clear();
 181   MInst2LVSetAI.clear();
 182 }
 183
 184
 185
 186
 187 //-----------------------------------------------------------------------------
 188 // Following functions will give the LiveVar info for any machine instr in
 189 // a function. It should be called after a call to analyze().
 190 //
 191 // These functions calculate live var info for all the machine instrs in a
 192 // BB when LVInfo for one inst is requested. Hence, this function is useful
 193 // when live var info is required for many (or all) instructions in a basic
 194 // block. Also, the arguments to this function does not require specific
 195 // iterators.
 196 //-----------------------------------------------------------------------------
 197
 198 //-----------------------------------------------------------------------------
 199 // Gives live variable information before a machine instruction
 200 //-----------------------------------------------------------------------------
 201
 202 const ValueSet &
 203 FunctionLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MI,
 204                                               const BasicBlock *BB) {
 205   ValueSet* &LVSet = MInst2LVSetBI[MI]; // ref. to map entry
 206   if (LVSet == NULL && BB != NULL) {    // if not found and BB provided
 207     calcLiveVarSetsForBB(BB);           // calc LVSet for all instrs in BB
 208     assert(LVSet != NULL);
 209   }
 210   return *LVSet;
 211 }
 212
 213
 214 //-----------------------------------------------------------------------------
 215 // Gives live variable information after a machine instruction
 216 //-----------------------------------------------------------------------------
 217
 218 const ValueSet &
 219 FunctionLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
 220                                              const BasicBlock *BB) {
 221
 222   ValueSet* &LVSet = MInst2LVSetAI[MI]; // ref. to map entry
 223   if (LVSet == NULL && BB != NULL) {    // if not found and BB provided
 224     calcLiveVarSetsForBB(BB);           // calc LVSet for all instrs in BB
 225     assert(LVSet != NULL);
 226   }
 227   return *LVSet;
 228 }
 229
 230 // This function applies a machine instr to a live var set (accepts OutSet) and
 231 // makes necessary changes to it (produces InSet). Note that two for loops are
 232 // used to first kill all defs and then to add all uses. This is because there
 233 // can be instructions like Val = Val + 1 since we allow multiple defs to a
 234 // machine instruction operand.
 235 //
 236 static void applyTranferFuncForMInst(ValueSet &LVS, const MachineInstr *MInst) {
 237   for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 238          OpE = MInst->end(); OpI != OpE; ++OpI) {
 239     if (OpI.isDef())                          // kill if this operand is a def
 240       LVS.erase(*OpI);                        // this definition kills any uses
 241   }
 242
 243   // do for implicit operands as well
 244   for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
 245     if (MInst->getImplicitOp(i).isDef())
 246       LVS.erase(MInst->getImplicitRef(i));
 247   }
 248
 249   for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 250          OpE = MInst->end(); OpI != OpE; ++OpI) {
 251     if (!isa<BasicBlock>(*OpI))      // don't process labels
 252       // add only if this operand is a use
 253       if (OpI.isUse())
 254         LVS.insert(*OpI);            // An operand is a use - so add to use set
 255   }
 256
 257   // do for implicit operands as well
 258   for (unsigned i = 0, e = MInst->getNumImplicitRefs(); i != e; ++i)
 259     if (MInst->getImplicitOp(i).isUse())
 260       LVS.insert(MInst->getImplicitRef(i));
 261 }
 262
 263 //-----------------------------------------------------------------------------
 264 // This method calculates the live variable information for all the
 265 // instructions in a basic block and enter the newly constructed live
 266 // variable sets into a the caches (MInst2LVSetAI, MInst2LVSetBI)
 267 //-----------------------------------------------------------------------------
 268
 269 void FunctionLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
 270   BBLiveVar *BBLV = BBLiveVarInfo[BB];
 271   assert(BBLV && "BBLiveVar annotation doesn't exist?");
 272   const MachineBasicBlock &MIVec = BBLV->getMachineBasicBlock();
 273   const MachineFunction &MF = MachineFunction::get(M);
 274   const TargetMachine &TM = MF.getTarget();
 275
 276   if (DEBUG_LV >= LV_DEBUG_Instr)
 277     std::cerr << "\n======For BB " << BB->getName()
 278               << ": Live var sets for instructions======\n";
 279
 280   ValueSet *SetAI = &getOutSetOfBB(BB);         // init SetAI with OutSet
 281   ValueSet CurSet(*SetAI);                      // CurSet now contains OutSet
 282
 283   // iterate over all the machine instructions in BB
 284   for (MachineBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
 285          MIE = MIVec.rend(); MII != MIE; ++MII) {
 286     // MI is cur machine inst
 287     const MachineInstr *MI = &*MII;
 288
 289     MInst2LVSetAI[MI] = SetAI;                 // record in After Inst map
 290
 291     applyTranferFuncForMInst(CurSet, MI);      // apply the transfer Func
 292     ValueSet *NewSet = new ValueSet(CurSet);   // create a new set with a copy
 293                                                // of the set after T/F
 294     MInst2LVSetBI[MI] = NewSet;                // record in Before Inst map
 295
 296     // If the current machine instruction has delay slots, mark values
 297     // used by this instruction as live before and after each delay slot
 298     // instruction (After(MI) is the same as Before(MI+1) except for last MI).
 299     if (unsigned DS = TM.getInstrInfo()->getNumDelaySlots(MI->getOpcode())) {
 300       MachineBasicBlock::const_iterator fwdMII = MII.base(); // ptr to *next* MI
 301       for (unsigned i = 0; i < DS; ++i, ++fwdMII) {
 302         assert(fwdMII != MIVec.end() && "Missing instruction in delay slot?");
 303         const MachineInstr* DelaySlotMI = fwdMII;
 304         if (! TM.getInstrInfo()->isNop(DelaySlotMI->getOpcode())) {
 305           set_union(*MInst2LVSetBI[DelaySlotMI], *NewSet);
 306           if (i+1 == DS)
 307             set_union(*MInst2LVSetAI[DelaySlotMI], *NewSet);
 308         }
 309       }
 310     }
 311
 312     if (DEBUG_LV >= LV_DEBUG_Instr) {
 313       std::cerr << "\nLive var sets before/after instruction " << *MI;
 314       std::cerr << "  Before: ";   printSet(*NewSet);  std::cerr << "\n";
 315       std::cerr << "  After : ";   printSet(*SetAI);   std::cerr << "\n";
 316     }
 317
 318     // SetAI will be used in the next iteration
 319     SetAI = NewSet;
 320   }
 321 }
 322
 323 } // End llvm namespace