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