LLVM API Documentation
00001 //===-- BBLiveVar.cpp - Live Variable Analysis for a BasicBlock -----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This is a wrapper class for BasicBlock which is used by live var analysis. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "BBLiveVar.h" 00015 #include "FunctionLiveVarInfo.h" 00016 #include "llvm/CodeGen/MachineInstr.h" 00017 #include "llvm/CodeGen/MachineBasicBlock.h" 00018 #include "llvm/Support/CFG.h" 00019 #include "llvm/ADT/SetOperations.h" 00020 #include "../SparcV9Internals.h" 00021 #include <iostream> 00022 00023 namespace llvm { 00024 00025 BBLiveVar::BBLiveVar(const BasicBlock &bb, 00026 const MachineBasicBlock &mbb, 00027 unsigned id) 00028 : BB(bb), MBB(mbb), POID(id) { 00029 InSetChanged = OutSetChanged = false; 00030 00031 calcDefUseSets(); 00032 } 00033 00034 //----------------------------------------------------------------------------- 00035 // calculates def and use sets for each BB 00036 // There are two passes over operands of a machine instruction. This is 00037 // because, we can have instructions like V = V + 1, since we no longer 00038 // assume single definition. 00039 //----------------------------------------------------------------------------- 00040 00041 void BBLiveVar::calcDefUseSets() { 00042 // iterate over all the machine instructions in BB 00043 for (MachineBasicBlock::const_reverse_iterator MII = MBB.rbegin(), 00044 MIE = MBB.rend(); MII != MIE; ++MII) { 00045 const MachineInstr *MI = &*MII; 00046 00047 if (DEBUG_LV >= LV_DEBUG_Verbose) { 00048 std::cerr << " *Iterating over machine instr "; 00049 MI->dump(); 00050 std::cerr << "\n"; 00051 } 00052 00053 // iterate over MI operands to find defs 00054 for (MachineInstr::const_val_op_iterator OpI = MI->begin(), OpE = MI->end(); 00055 OpI != OpE; ++OpI) 00056 if (OpI.isDef()) // add to Defs if this operand is a def 00057 addDef(*OpI); 00058 00059 // do for implicit operands as well 00060 for (unsigned i = 0; i < MI->getNumImplicitRefs(); ++i) 00061 if (MI->getImplicitOp(i).isDef()) 00062 addDef(MI->getImplicitRef(i)); 00063 00064 // iterate over MI operands to find uses 00065 for (MachineInstr::const_val_op_iterator OpI = MI->begin(), OpE = MI->end(); 00066 OpI != OpE; ++OpI) { 00067 const Value *Op = *OpI; 00068 00069 if (isa<BasicBlock>(Op)) 00070 continue; // don't process labels 00071 00072 if (OpI.isUse()) { // add to Uses only if this operand is a use 00073 // 00074 // *** WARNING: The following code for handling dummy PHI machine 00075 // instructions is untested. The previous code was broken and I 00076 // fixed it, but it turned out to be unused as long as Phi 00077 // elimination is performed during instruction selection. 00078 // 00079 // Put Phi operands in UseSet for the incoming edge, not node. 00080 // They must not "hide" later defs, and must be handled specially 00081 // during set propagation over the CFG. 00082 if (MI->getOpcode() == V9::PHI) { // for a phi node 00083 const Value *ArgVal = Op; 00084 const BasicBlock *PredBB = cast<BasicBlock>(*++OpI); // next ptr is BB 00085 00086 PredToEdgeInSetMap[PredBB].insert(ArgVal); 00087 00088 if (DEBUG_LV >= LV_DEBUG_Verbose) 00089 std::cerr << " - phi operand " << RAV(ArgVal) << " came from BB " 00090 << RAV(PredBB) << "\n"; 00091 } // if( IsPhi ) 00092 else { 00093 // It is not a Phi use: add to regular use set and remove later defs. 00094 addUse(Op); 00095 } 00096 } // if a use 00097 } // for all operands 00098 00099 // do for implicit operands as well 00100 for (unsigned i = 0; i < MI->getNumImplicitRefs(); ++i) { 00101 assert(MI->getOpcode() != V9::PHI && "Phi cannot have implicit operands"); 00102 const Value *Op = MI->getImplicitRef(i); 00103 00104 if (Op->getType() == Type::LabelTy) // don't process labels 00105 continue; 00106 00107 if (MI->getImplicitOp(i).isUse()) 00108 addUse(Op); 00109 } 00110 } // for all machine instructions 00111 } 00112 00113 00114 00115 //----------------------------------------------------------------------------- 00116 // To add an operand which is a def 00117 //----------------------------------------------------------------------------- 00118 void BBLiveVar::addDef(const Value *Op) { 00119 DefSet.insert(Op); // operand is a def - so add to def set 00120 InSet.erase(Op); // this definition kills any later uses 00121 InSetChanged = true; 00122 00123 if (DEBUG_LV >= LV_DEBUG_Verbose) std::cerr << " +Def: " << RAV(Op) << "\n"; 00124 } 00125 00126 00127 //----------------------------------------------------------------------------- 00128 // To add an operand which is a use 00129 //----------------------------------------------------------------------------- 00130 void BBLiveVar::addUse(const Value *Op) { 00131 InSet.insert(Op); // An operand is a use - so add to use set 00132 DefSet.erase(Op); // remove if there is a def below this use 00133 InSetChanged = true; 00134 00135 if (DEBUG_LV >= LV_DEBUG_Verbose) std::cerr << " Use: " << RAV(Op) << "\n"; 00136 } 00137 00138 00139 //----------------------------------------------------------------------------- 00140 // Applies the transfer function to a basic block to produce the InSet using 00141 // the OutSet. 00142 //----------------------------------------------------------------------------- 00143 00144 bool BBLiveVar::applyTransferFunc() { 00145 // IMPORTANT: caller should check whether the OutSet changed 00146 // (else no point in calling) 00147 00148 ValueSet OutMinusDef = set_difference(OutSet, DefSet); 00149 InSetChanged = set_union(InSet, OutMinusDef); 00150 00151 OutSetChanged = false; // no change to OutSet since transf func applied 00152 return InSetChanged; 00153 } 00154 00155 00156 //----------------------------------------------------------------------------- 00157 // calculates Out set using In sets of the successors 00158 //----------------------------------------------------------------------------- 00159 00160 bool BBLiveVar::setPropagate(ValueSet *OutSet, const ValueSet *InSet, 00161 const BasicBlock *PredBB) { 00162 bool Changed = false; 00163 00164 // merge all members of InSet into OutSet of the predecessor 00165 for (ValueSet::const_iterator InIt = InSet->begin(), InE = InSet->end(); 00166 InIt != InE; ++InIt) 00167 if ((OutSet->insert(*InIt)).second) 00168 Changed = true; 00169 00170 // 00171 //**** WARNING: The following code for handling dummy PHI machine 00172 // instructions is untested. See explanation above. 00173 // 00174 // then merge all members of the EdgeInSet for the predecessor into the OutSet 00175 const ValueSet& EdgeInSet = PredToEdgeInSetMap[PredBB]; 00176 for (ValueSet::const_iterator InIt = EdgeInSet.begin(), InE = EdgeInSet.end(); 00177 InIt != InE; ++InIt) 00178 if ((OutSet->insert(*InIt)).second) 00179 Changed = true; 00180 // 00181 //**** 00182 00183 return Changed; 00184 } 00185 00186 00187 //----------------------------------------------------------------------------- 00188 // propagates in set to OutSets of PREDECESSORs 00189 //----------------------------------------------------------------------------- 00190 00191 bool BBLiveVar::applyFlowFunc(hash_map<const BasicBlock*, 00192 BBLiveVar*> &BBLiveVarInfo) { 00193 // IMPORTANT: caller should check whether inset changed 00194 // (else no point in calling) 00195 00196 // If this BB changed any OutSets of preds whose POID is lower, than we need 00197 // another iteration... 00198 // 00199 bool needAnotherIt = false; 00200 00201 for (pred_const_iterator PI = pred_begin(&BB), PE = pred_end(&BB); 00202 PI != PE ; ++PI) { 00203 BBLiveVar *PredLVBB = BBLiveVarInfo[*PI]; 00204 00205 // do set union 00206 if (setPropagate(&PredLVBB->OutSet, &InSet, *PI)) { 00207 PredLVBB->OutSetChanged = true; 00208 00209 // if the predec POID is lower than mine 00210 if (PredLVBB->getPOId() <= POID) 00211 needAnotherIt = true; 00212 } 00213 } // for 00214 00215 return needAnotherIt; 00216 } 00217 00218 00219 00220 // ----------------- Methods For Debugging (Printing) ----------------- 00221 00222 void BBLiveVar::printAllSets() const { 00223 std::cerr << " Defs: "; printSet(DefSet); std::cerr << "\n"; 00224 std::cerr << " In: "; printSet(InSet); std::cerr << "\n"; 00225 std::cerr << " Out: "; printSet(OutSet); std::cerr << "\n"; 00226 } 00227 00228 void BBLiveVar::printInOutSets() const { 00229 std::cerr << " In: "; printSet(InSet); std::cerr << "\n"; 00230 std::cerr << " Out: "; printSet(OutSet); std::cerr << "\n"; 00231 } 00232 00233 } // End llvm namespace