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