lib/Analysis/LiveVar/BBLiveVar.cpp

   1 //===-- BBLiveVar.cpp - Live Variable Analysis for a BasicBlock -----------===//
   2 //
   3 // This is a wrapper class for BasicBlock which is used by live var analysis.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "BBLiveVar.h"
   8 #include "llvm/CodeGen/FunctionLiveVarInfo.h"
   9 #include "llvm/CodeGen/MachineInstr.h"
  10 #include "llvm/CodeGen/MachineBasicBlock.h"
  11 #include "llvm/Support/CFG.h"
  12 #include "Support/SetOperations.h"
  13
  14 /// BROKEN: Should not include sparc stuff directly into here
  15 #include "../../Target/Sparc/SparcInternals.h"  //  Only for PHI defn
  16
  17 using std::cerr;
  18
  19 static AnnotationID AID(AnnotationManager::getID("Analysis::BBLiveVar"));
  20
  21 BBLiveVar *BBLiveVar::CreateOnBB(const BasicBlock &BB, MachineBasicBlock &MBB,
  22                                  unsigned POID) {
  23   BBLiveVar *Result = new BBLiveVar(BB, MBB, POID);
  24   BB.addAnnotation(Result);
  25   return Result;
  26 }
  27
  28 BBLiveVar *BBLiveVar::GetFromBB(const BasicBlock &BB) {
  29   return (BBLiveVar*)BB.getAnnotation(AID);
  30 }
  31
  32 void BBLiveVar::RemoveFromBB(const BasicBlock &BB) {
  33   bool Deleted = BB.deleteAnnotation(AID);
  34   assert(Deleted && "BBLiveVar annotation did not exist!");
  35 }
  36
  37
  38 BBLiveVar::BBLiveVar(const BasicBlock &bb, MachineBasicBlock &mbb, unsigned id)
  39   : Annotation(AID), BB(bb), MBB(mbb), POID(id) {
  40   InSetChanged = OutSetChanged = false;
  41
  42   calcDefUseSets();
  43 }
  44
  45 //-----------------------------------------------------------------------------
  46 // calculates def and use sets for each BB
  47 // There are two passes over operands of a machine instruction. This is
  48 // because, we can have instructions like V = V + 1, since we no longer
  49 // assume single definition.
  50 //-----------------------------------------------------------------------------
  51
  52 void BBLiveVar::calcDefUseSets() {
  53   // iterate over all the machine instructions in BB
  54   for (MachineBasicBlock::const_reverse_iterator MII = MBB.rbegin(),
  55          MIE = MBB.rend(); MII != MIE; ++MII) {
  56     const MachineInstr *MI = *MII;
  57
  58     if (DEBUG_LV >= LV_DEBUG_Verbose) {
  59       cerr << " *Iterating over machine instr ";
  60       MI->dump();
  61       cerr << "\n";
  62     }
  63
  64     // iterate over  MI operands to find defs
  65     for (MachineInstr::const_val_op_iterator OpI = MI->begin(), OpE = MI->end();
  66          OpI != OpE; ++OpI)
  67       if (OpI.isDefOnly() || OpI.isDefAndUse()) // add to Defs if this operand is a def
  68         addDef(*OpI);
  69
  70     // do for implicit operands as well
  71     for (unsigned i = 0; i < MI->getNumImplicitRefs(); ++i)
  72       if (MI->getImplicitOp(i).opIsDefOnly() || MI->getImplicitOp(i).opIsDefAndUse())
  73         addDef(MI->getImplicitRef(i));
  74
  75     // iterate over MI operands to find uses
  76     for (MachineInstr::const_val_op_iterator OpI = MI->begin(), OpE = MI->end();
  77          OpI != OpE; ++OpI) {
  78       const Value *Op = *OpI;
  79
  80       if (isa<BasicBlock>(Op))
  81         continue;             // don't process labels
  82
  83       if (OpI.isUseOnly() || OpI.isDefAndUse()) {
  84                                 // add to Uses only if this operand is a use
  85         //
  86         // *** WARNING: The following code for handling dummy PHI machine
  87         //     instructions is untested.  The previous code was broken and I
  88         //     fixed it, but it turned out to be unused as long as Phi
  89         //     elimination is performed during instruction selection.
  90         //
  91         // Put Phi operands in UseSet for the incoming edge, not node.
  92         // They must not "hide" later defs, and must be handled specially
  93         // during set propagation over the CFG.
  94         if (MI->getOpCode() == V9::PHI) {         // for a phi node
  95           const Value *ArgVal = Op;
  96           const BasicBlock *PredBB = cast<BasicBlock>(*++OpI); // next ptr is BB
  97
  98           PredToEdgeInSetMap[PredBB].insert(ArgVal);
  99
 100           if (DEBUG_LV >= LV_DEBUG_Verbose)
 101             cerr << "   - phi operand " << RAV(ArgVal) << " came from BB "
 102                  << RAV(PredBB) << "\n";
 103         } // if( IsPhi )
 104         else {
 105           // It is not a Phi use: add to regular use set and remove later defs.
 106           addUse(Op);
 107         }
 108       } // if a use
 109     } // for all operands
 110
 111     // do for implicit operands as well
 112     for (unsigned i = 0; i < MI->getNumImplicitRefs(); ++i) {
 113       assert(MI->getOpCode() != V9::PHI && "Phi cannot have implicit operands");
 114       const Value *Op = MI->getImplicitRef(i);
 115
 116       if (Op->getType() == Type::LabelTy)             // don't process labels
 117         continue;
 118
 119       if (MI->getImplicitOp(i).opIsUse() || MI->getImplicitOp(i).opIsDefAndUse())
 120         addUse(Op);
 121     }
 122   } // for all machine instructions
 123 }
 124
 125
 126
 127 //-----------------------------------------------------------------------------
 128 // To add an operand which is a def
 129 //-----------------------------------------------------------------------------
 130 void BBLiveVar::addDef(const Value *Op) {
 131   DefSet.insert(Op);     // operand is a def - so add to def set
 132   InSet.erase(Op);       // this definition kills any later uses
 133   InSetChanged = true;
 134
 135   if (DEBUG_LV >= LV_DEBUG_Verbose) cerr << "  +Def: " << RAV(Op) << "\n";
 136 }
 137
 138
 139 //-----------------------------------------------------------------------------
 140 // To add an operand which is a use
 141 //-----------------------------------------------------------------------------
 142 void  BBLiveVar::addUse(const Value *Op) {
 143   InSet.insert(Op);   // An operand is a use - so add to use set
 144   DefSet.erase(Op);   // remove if there is a def below this use
 145   InSetChanged = true;
 146
 147   if (DEBUG_LV >= LV_DEBUG_Verbose) cerr << "   Use: " << RAV(Op) << "\n";
 148 }
 149
 150
 151 //-----------------------------------------------------------------------------
 152 // Applies the transfer function to a basic block to produce the InSet using
 153 // the OutSet.
 154 //-----------------------------------------------------------------------------
 155
 156 bool BBLiveVar::applyTransferFunc() {
 157   // IMPORTANT: caller should check whether the OutSet changed
 158   //           (else no point in calling)
 159
 160   ValueSet OutMinusDef = set_difference(OutSet, DefSet);
 161   InSetChanged = set_union(InSet, OutMinusDef);
 162
 163   OutSetChanged = false;      // no change to OutSet since transf func applied
 164   return InSetChanged;
 165 }
 166
 167
 168 //-----------------------------------------------------------------------------
 169 // calculates Out set using In sets of the successors
 170 //-----------------------------------------------------------------------------
 171
 172 bool BBLiveVar::setPropagate(ValueSet *OutSet, const ValueSet *InSet,
 173                              const BasicBlock *PredBB) {
 174   bool Changed = false;
 175
 176   // merge all members of InSet into OutSet of the predecessor
 177   for (ValueSet::const_iterator InIt = InSet->begin(), InE = InSet->end();
 178        InIt != InE; ++InIt)
 179     if ((OutSet->insert(*InIt)).second)
 180       Changed = true;
 181
 182   //
 183   //**** WARNING: The following code for handling dummy PHI machine
 184   //     instructions is untested.  See explanation above.
 185   //
 186   // then merge all members of the EdgeInSet for the predecessor into the OutSet
 187   const ValueSet& EdgeInSet = PredToEdgeInSetMap[PredBB];
 188   for (ValueSet::const_iterator InIt = EdgeInSet.begin(), InE = EdgeInSet.end();
 189        InIt != InE; ++InIt)
 190     if ((OutSet->insert(*InIt)).second)
 191       Changed = true;
 192   //
 193   //****
 194
 195   return Changed;
 196 }
 197
 198
 199 //-----------------------------------------------------------------------------
 200 // propagates in set to OutSets of PREDECESSORs
 201 //-----------------------------------------------------------------------------
 202
 203 bool BBLiveVar::applyFlowFunc() {
 204   // IMPORTANT: caller should check whether inset changed
 205   //            (else no point in calling)
 206
 207   // If this BB changed any OutSets of preds whose POID is lower, than we need
 208   // another iteration...
 209   //
 210   bool needAnotherIt = false;
 211
 212   for (pred_const_iterator PI = pred_begin(&BB), PE = pred_end(&BB);
 213        PI != PE ; ++PI) {
 214     BBLiveVar *PredLVBB = BBLiveVar::GetFromBB(**PI);
 215
 216     // do set union
 217     if (setPropagate(&PredLVBB->OutSet, &InSet, *PI)) {
 218       PredLVBB->OutSetChanged = true;
 219
 220       // if the predec POID is lower than mine
 221       if (PredLVBB->getPOId() <= POID)
 222         needAnotherIt = true;
 223     }
 224   }  // for
 225
 226   return needAnotherIt;
 227 }
 228
 229
 230
 231 // ----------------- Methods For Debugging (Printing) -----------------
 232
 233 void BBLiveVar::printAllSets() const {
 234   cerr << "  Defs: "; printSet(DefSet);  cerr << "\n";
 235   cerr << "  In: ";  printSet(InSet);  cerr << "\n";
 236   cerr << "  Out: "; printSet(OutSet);  cerr << "\n";
 237 }
 238
 239 void BBLiveVar::printInOutSets() const {
 240   cerr << "  In: ";   printSet(InSet);  cerr << "\n";
 241   cerr << "  Out: ";  printSet(OutSet);  cerr << "\n";
 242 }
 243
 244
 245
 246