lib/Analysis/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 BBLiveVar::GetFromBB(*BB)->getOutSet();
  51 }
  52       ValueSet &FunctionLiveVarInfo::getOutSetOfBB(const BasicBlock *BB)       {
  53   return BBLiveVar::GetFromBB(*BB)->getOutSet();
  54 }
  55
  56 // gets InSet of a BB
  57 const ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB) const {
  58   return BBLiveVar::GetFromBB(*BB)->getInSet();
  59 }
  60       ValueSet &FunctionLiveVarInfo::getInSetOfBB(const BasicBlock *BB)       {
  61   return BBLiveVar::GetFromBB(*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 = BBLiveVar::CreateOnBB(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 = BBLiveVar::CreateOnBB(BB, *I, ++POId);
 114     }
 115
 116     if (DEBUG_LV)
 117       LVBB->printAllSets();
 118   }
 119 }
 120
 121
 122 //-----------------------------------------------------------------------------
 123 // do one backward pass over the CFG (for iterative analysis)
 124 //-----------------------------------------------------------------------------
 125
 126 bool FunctionLiveVarInfo::doSingleBackwardPass(const Function *M,
 127                                                unsigned iter) {
 128   if (DEBUG_LV) std::cerr << "\n After Backward Pass " << iter << "...\n";
 129
 130   bool NeedAnotherIteration = false;
 131   for (po_iterator<const Function*> BBI = po_begin(M), BBE = po_end(M);
 132        BBI != BBE; ++BBI) {
 133     BBLiveVar *LVBB = BBLiveVar::GetFromBB(**BBI);
 134     assert(LVBB && "BasicBlock information not set for block!");
 135
 136     if (DEBUG_LV) std::cerr << " For BB " << (*BBI)->getName() << ":\n";
 137
 138     // InSets are initialized to "GenSet". Recompute only if OutSet changed.
 139     if(LVBB->isOutSetChanged())
 140       LVBB->applyTransferFunc();        // apply the Tran Func to calc InSet
 141
 142     // OutSets are initialized to EMPTY.  Recompute on first iter or if InSet
 143     // changed.
 144     if (iter == 0 || LVBB->isInSetChanged())        // to calc Outsets of preds
 145       NeedAnotherIteration |= LVBB->applyFlowFunc();
 146
 147     if (DEBUG_LV) LVBB->printInOutSets();
 148   }
 149
 150   // true if we need to reiterate over the CFG
 151   return NeedAnotherIteration;
 152 }
 153
 154
 155 void FunctionLiveVarInfo::releaseMemory() {
 156   // First remove all BBLiveVar annotations created in constructBBs().
 157   if (M)
 158     for (Function::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
 159       BBLiveVar::RemoveFromBB(*I);
 160   M = 0;
 161
 162   // Then delete all objects of type ValueSet created in calcLiveVarSetsForBB
 163   // and entered into MInst2LVSetBI and MInst2LVSetAI (these are caches
 164   // to return ValueSet's before/after a machine instruction quickly).
 165   // We do not need to free up ValueSets in MInst2LVSetAI because it holds
 166   // pointers to the same sets as in MInst2LVSetBI (for all instructions
 167   // except the last one in a BB) or in BBLiveVar (for the last instruction).
 168   //
 169   for (hash_map<const MachineInstr*, ValueSet*>::iterator
 170          MI = MInst2LVSetBI.begin(),
 171          ME = MInst2LVSetBI.end(); MI != ME; ++MI)
 172     delete MI->second;           // delete all ValueSets in  MInst2LVSetBI
 173
 174   MInst2LVSetBI.clear();
 175   MInst2LVSetAI.clear();
 176 }
 177
 178
 179
 180
 181 //-----------------------------------------------------------------------------
 182 // Following functions will give the LiveVar info for any machine instr in
 183 // a function. It should be called after a call to analyze().
 184 //
 185 // These functions calculate live var info for all the machine instrs in a
 186 // BB when LVInfo for one inst is requested. Hence, this function is useful
 187 // when live var info is required for many (or all) instructions in a basic
 188 // block. Also, the arguments to this function does not require specific
 189 // iterators.
 190 //-----------------------------------------------------------------------------
 191
 192 //-----------------------------------------------------------------------------
 193 // Gives live variable information before a machine instruction
 194 //-----------------------------------------------------------------------------
 195
 196 const ValueSet &
 197 FunctionLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *MI,
 198                                               const BasicBlock *BB) {
 199   ValueSet* &LVSet = MInst2LVSetBI[MI]; // ref. to map entry
 200   if (LVSet == NULL && BB != NULL) {    // if not found and BB provided
 201     calcLiveVarSetsForBB(BB);           // calc LVSet for all instrs in BB
 202     assert(LVSet != NULL);
 203   }
 204   return *LVSet;
 205 }
 206
 207
 208 //-----------------------------------------------------------------------------
 209 // Gives live variable information after a machine instruction
 210 //-----------------------------------------------------------------------------
 211
 212 const ValueSet &
 213 FunctionLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *MI,
 214                                              const BasicBlock *BB) {
 215
 216   ValueSet* &LVSet = MInst2LVSetAI[MI]; // ref. to map entry
 217   if (LVSet == NULL && BB != NULL) {    // if not found and BB provided
 218     calcLiveVarSetsForBB(BB);           // calc LVSet for all instrs in BB
 219     assert(LVSet != NULL);
 220   }
 221   return *LVSet;
 222 }
 223
 224 // This function applies a machine instr to a live var set (accepts OutSet) and
 225 // makes necessary changes to it (produces InSet). Note that two for loops are
 226 // used to first kill all defs and then to add all uses. This is because there
 227 // can be instructions like Val = Val + 1 since we allow multiple defs to a
 228 // machine instruction operand.
 229 //
 230 static void applyTranferFuncForMInst(ValueSet &LVS, const MachineInstr *MInst) {
 231   for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 232          OpE = MInst->end(); OpI != OpE; ++OpI) {
 233     if (OpI.isDefOnly() || OpI.isDefAndUse()) // kill if this operand is a def
 234       LVS.erase(*OpI);                        // this definition kills any uses
 235   }
 236
 237   // do for implicit operands as well
 238   for (unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
 239     if (MInst->getImplicitOp(i).opIsDefOnly() ||
 240         MInst->getImplicitOp(i).opIsDefAndUse())
 241       LVS.erase(MInst->getImplicitRef(i));
 242   }
 243
 244   for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 245          OpE = MInst->end(); OpI != OpE; ++OpI) {
 246     if (!isa<BasicBlock>(*OpI))      // don't process labels
 247       // add only if this operand is a use
 248       if (!OpI.isDefOnly() || OpI.isDefAndUse() )
 249         LVS.insert(*OpI);            // An operand is a use - so add to use set
 250   }
 251
 252   // do for implicit operands as well
 253   for (unsigned i = 0, e = MInst->getNumImplicitRefs(); i != e; ++i)
 254     if (MInst->getImplicitOp(i).opIsUse() ||
 255         MInst->getImplicitOp(i).opIsDefAndUse())
 256       LVS.insert(MInst->getImplicitRef(i));
 257 }
 258
 259 //-----------------------------------------------------------------------------
 260 // This method calculates the live variable information for all the
 261 // instructions in a basic block and enter the newly constructed live
 262 // variable sets into a the caches (MInst2LVSetAI, MInst2LVSetBI)
 263 //-----------------------------------------------------------------------------
 264
 265 void FunctionLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *BB) {
 266   BBLiveVar *BBLV = BBLiveVar::GetFromBB(*BB);
 267   assert(BBLV && "BBLiveVar annotation doesn't exist?");
 268   const MachineBasicBlock &MIVec = BBLV->getMachineBasicBlock();
 269   const MachineFunction &MF = MachineFunction::get(M);
 270   const TargetMachine &TM = MF.getTarget();
 271
 272   if (DEBUG_LV >= LV_DEBUG_Instr)
 273     std::cerr << "\n======For BB " << BB->getName()
 274               << ": Live var sets for instructions======\n";
 275
 276   ValueSet *SetAI = &getOutSetOfBB(BB);         // init SetAI with OutSet
 277   ValueSet CurSet(*SetAI);                      // CurSet now contains OutSet
 278
 279   // iterate over all the machine instructions in BB
 280   for (MachineBasicBlock::const_reverse_iterator MII = MIVec.rbegin(),
 281          MIE = MIVec.rend(); MII != MIE; ++MII) {
 282     // MI is cur machine inst
 283     const MachineInstr *MI = *MII;
 284
 285     MInst2LVSetAI[MI] = SetAI;                 // record in After Inst map
 286
 287     applyTranferFuncForMInst(CurSet, MI);      // apply the transfer Func
 288     ValueSet *NewSet = new ValueSet(CurSet);   // create a new set with a copy
 289                                                // of the set after T/F
 290     MInst2LVSetBI[MI] = NewSet;                // record in Before Inst map
 291
 292     // If the current machine instruction has delay slots, mark values
 293     // used by this instruction as live before and after each delay slot
 294     // instruction (After(MI) is the same as Before(MI+1) except for last MI).
 295     if (unsigned DS = TM.getInstrInfo().getNumDelaySlots(MI->getOpCode())) {
 296       MachineBasicBlock::const_iterator fwdMII = MII.base(); // ptr to *next* MI
 297       for (unsigned i = 0; i < DS; ++i, ++fwdMII) {
 298         assert(fwdMII != MIVec.end() && "Missing instruction in delay slot?");
 299         MachineInstr* DelaySlotMI = *fwdMII;
 300         if (! TM.getInstrInfo().isNop(DelaySlotMI->getOpCode())) {
 301           set_union(*MInst2LVSetBI[DelaySlotMI], *NewSet);
 302           if (i+1 == DS)
 303             set_union(*MInst2LVSetAI[DelaySlotMI], *NewSet);
 304         }
 305       }
 306     }
 307
 308     if (DEBUG_LV >= LV_DEBUG_Instr) {
 309       std::cerr << "\nLive var sets before/after instruction " << *MI;
 310       std::cerr << "  Before: ";   printSet(*NewSet);  std::cerr << "\n";
 311       std::cerr << "  After : ";   printSet(*SetAI);   std::cerr << "\n";
 312     }
 313
 314     // SetAI will be used in the next iteration
 315     SetAI = NewSet;
 316   }
 317 }