LLVM API Documentation
00001 //===- GVN.cpp - Eliminate redundant values and loads ---------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass performs global value numbering to eliminate fully redundant 00011 // instructions. It also performs simple dead load elimination. 00012 // 00013 // Note that this pass does the value numbering itself; it does not use the 00014 // ValueNumbering analysis passes. 00015 // 00016 //===----------------------------------------------------------------------===// 00017 00018 #define DEBUG_TYPE "gvn" 00019 #include "llvm/Transforms/Scalar.h" 00020 #include "llvm/BasicBlock.h" 00021 #include "llvm/Constants.h" 00022 #include "llvm/DerivedTypes.h" 00023 #include "llvm/Function.h" 00024 #include "llvm/IntrinsicInst.h" 00025 #include "llvm/LLVMContext.h" 00026 #include "llvm/Value.h" 00027 #include "llvm/ADT/DenseMap.h" 00028 #include "llvm/ADT/DepthFirstIterator.h" 00029 #include "llvm/ADT/PostOrderIterator.h" 00030 #include "llvm/ADT/SmallPtrSet.h" 00031 #include "llvm/ADT/SmallVector.h" 00032 #include "llvm/ADT/Statistic.h" 00033 #include "llvm/Analysis/Dominators.h" 00034 #include "llvm/Analysis/AliasAnalysis.h" 00035 #include "llvm/Analysis/MemoryDependenceAnalysis.h" 00036 #include "llvm/Support/CFG.h" 00037 #include "llvm/Support/CommandLine.h" 00038 #include "llvm/Support/Compiler.h" 00039 #include "llvm/Support/Debug.h" 00040 #include "llvm/Support/ErrorHandling.h" 00041 #include "llvm/Support/raw_ostream.h" 00042 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00043 #include "llvm/Transforms/Utils/Local.h" 00044 #include <cstdio> 00045 using namespace llvm; 00046 00047 STATISTIC(NumGVNInstr, "Number of instructions deleted"); 00048 STATISTIC(NumGVNLoad, "Number of loads deleted"); 00049 STATISTIC(NumGVNPRE, "Number of instructions PRE'd"); 00050 STATISTIC(NumGVNBlocks, "Number of blocks merged"); 00051 STATISTIC(NumPRELoad, "Number of loads PRE'd"); 00052 00053 static cl::opt<bool> EnablePRE("enable-pre", 00054 cl::init(true), cl::Hidden); 00055 static cl::opt<bool> EnableLoadPRE("enable-load-pre", cl::init(true)); 00056 00057 //===----------------------------------------------------------------------===// 00058 // ValueTable Class 00059 //===----------------------------------------------------------------------===// 00060 00061 /// This class holds the mapping between values and value numbers. It is used 00062 /// as an efficient mechanism to determine the expression-wise equivalence of 00063 /// two values. 00064 namespace { 00065 struct VISIBILITY_HIDDEN Expression { 00066 enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL, 00067 UDIV, SDIV, FDIV, UREM, SREM, 00068 FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 00069 ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 00070 ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 00071 FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 00072 FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 00073 FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT, 00074 SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI, 00075 FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 00076 PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT, 00077 EMPTY, TOMBSTONE }; 00078 00079 ExpressionOpcode opcode; 00080 const Type* type; 00081 uint32_t firstVN; 00082 uint32_t secondVN; 00083 uint32_t thirdVN; 00084 SmallVector<uint32_t, 4> varargs; 00085 Value* function; 00086 00087 Expression() { } 00088 Expression(ExpressionOpcode o) : opcode(o) { } 00089 00090 bool operator==(const Expression &other) const { 00091 if (opcode != other.opcode) 00092 return false; 00093 else if (opcode == EMPTY || opcode == TOMBSTONE) 00094 return true; 00095 else if (type != other.type) 00096 return false; 00097 else if (function != other.function) 00098 return false; 00099 else if (firstVN != other.firstVN) 00100 return false; 00101 else if (secondVN != other.secondVN) 00102 return false; 00103 else if (thirdVN != other.thirdVN) 00104 return false; 00105 else { 00106 if (varargs.size() != other.varargs.size()) 00107 return false; 00108 00109 for (size_t i = 0; i < varargs.size(); ++i) 00110 if (varargs[i] != other.varargs[i]) 00111 return false; 00112 00113 return true; 00114 } 00115 } 00116 00117 bool operator!=(const Expression &other) const { 00118 return !(*this == other); 00119 } 00120 }; 00121 00122 class VISIBILITY_HIDDEN ValueTable { 00123 private: 00124 DenseMap<Value*, uint32_t> valueNumbering; 00125 DenseMap<Expression, uint32_t> expressionNumbering; 00126 AliasAnalysis* AA; 00127 MemoryDependenceAnalysis* MD; 00128 DominatorTree* DT; 00129 00130 uint32_t nextValueNumber; 00131 00132 Expression::ExpressionOpcode getOpcode(BinaryOperator* BO); 00133 Expression::ExpressionOpcode getOpcode(CmpInst* C); 00134 Expression::ExpressionOpcode getOpcode(CastInst* C); 00135 Expression create_expression(BinaryOperator* BO); 00136 Expression create_expression(CmpInst* C); 00137 Expression create_expression(ShuffleVectorInst* V); 00138 Expression create_expression(ExtractElementInst* C); 00139 Expression create_expression(InsertElementInst* V); 00140 Expression create_expression(SelectInst* V); 00141 Expression create_expression(CastInst* C); 00142 Expression create_expression(GetElementPtrInst* G); 00143 Expression create_expression(CallInst* C); 00144 Expression create_expression(Constant* C); 00145 public: 00146 ValueTable() : nextValueNumber(1) { } 00147 uint32_t lookup_or_add(Value* V); 00148 uint32_t lookup(Value* V) const; 00149 void add(Value* V, uint32_t num); 00150 void clear(); 00151 void erase(Value* v); 00152 unsigned size(); 00153 void setAliasAnalysis(AliasAnalysis* A) { AA = A; } 00154 AliasAnalysis *getAliasAnalysis() const { return AA; } 00155 void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } 00156 void setDomTree(DominatorTree* D) { DT = D; } 00157 uint32_t getNextUnusedValueNumber() { return nextValueNumber; } 00158 void verifyRemoved(const Value *) const; 00159 }; 00160 } 00161 00162 namespace llvm { 00163 template <> struct DenseMapInfo<Expression> { 00164 static inline Expression getEmptyKey() { 00165 return Expression(Expression::EMPTY); 00166 } 00167 00168 static inline Expression getTombstoneKey() { 00169 return Expression(Expression::TOMBSTONE); 00170 } 00171 00172 static unsigned getHashValue(const Expression e) { 00173 unsigned hash = e.opcode; 00174 00175 hash = e.firstVN + hash * 37; 00176 hash = e.secondVN + hash * 37; 00177 hash = e.thirdVN + hash * 37; 00178 00179 hash = ((unsigned)((uintptr_t)e.type >> 4) ^ 00180 (unsigned)((uintptr_t)e.type >> 9)) + 00181 hash * 37; 00182 00183 for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), 00184 E = e.varargs.end(); I != E; ++I) 00185 hash = *I + hash * 37; 00186 00187 hash = ((unsigned)((uintptr_t)e.function >> 4) ^ 00188 (unsigned)((uintptr_t)e.function >> 9)) + 00189 hash * 37; 00190 00191 return hash; 00192 } 00193 static bool isEqual(const Expression &LHS, const Expression &RHS) { 00194 return LHS == RHS; 00195 } 00196 static bool isPod() { return true; } 00197 }; 00198 } 00199 00200 //===----------------------------------------------------------------------===// 00201 // ValueTable Internal Functions 00202 //===----------------------------------------------------------------------===// 00203 Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) { 00204 switch(BO->getOpcode()) { 00205 default: // THIS SHOULD NEVER HAPPEN 00206 llvm_unreachable("Binary operator with unknown opcode?"); 00207 case Instruction::Add: return Expression::ADD; 00208 case Instruction::FAdd: return Expression::FADD; 00209 case Instruction::Sub: return Expression::SUB; 00210 case Instruction::FSub: return Expression::FSUB; 00211 case Instruction::Mul: return Expression::MUL; 00212 case Instruction::FMul: return Expression::FMUL; 00213 case Instruction::UDiv: return Expression::UDIV; 00214 case Instruction::SDiv: return Expression::SDIV; 00215 case Instruction::FDiv: return Expression::FDIV; 00216 case Instruction::URem: return Expression::UREM; 00217 case Instruction::SRem: return Expression::SREM; 00218 case Instruction::FRem: return Expression::FREM; 00219 case Instruction::Shl: return Expression::SHL; 00220 case Instruction::LShr: return Expression::LSHR; 00221 case Instruction::AShr: return Expression::ASHR; 00222 case Instruction::And: return Expression::AND; 00223 case Instruction::Or: return Expression::OR; 00224 case Instruction::Xor: return Expression::XOR; 00225 } 00226 } 00227 00228 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) { 00229 if (isa<ICmpInst>(C)) { 00230 switch (C->getPredicate()) { 00231 default: // THIS SHOULD NEVER HAPPEN 00232 llvm_unreachable("Comparison with unknown predicate?"); 00233 case ICmpInst::ICMP_EQ: return Expression::ICMPEQ; 00234 case ICmpInst::ICMP_NE: return Expression::ICMPNE; 00235 case ICmpInst::ICMP_UGT: return Expression::ICMPUGT; 00236 case ICmpInst::ICMP_UGE: return Expression::ICMPUGE; 00237 case ICmpInst::ICMP_ULT: return Expression::ICMPULT; 00238 case ICmpInst::ICMP_ULE: return Expression::ICMPULE; 00239 case ICmpInst::ICMP_SGT: return Expression::ICMPSGT; 00240 case ICmpInst::ICMP_SGE: return Expression::ICMPSGE; 00241 case ICmpInst::ICMP_SLT: return Expression::ICMPSLT; 00242 case ICmpInst::ICMP_SLE: return Expression::ICMPSLE; 00243 } 00244 } else { 00245 switch (C->getPredicate()) { 00246 default: // THIS SHOULD NEVER HAPPEN 00247 llvm_unreachable("Comparison with unknown predicate?"); 00248 case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ; 00249 case FCmpInst::FCMP_OGT: return Expression::FCMPOGT; 00250 case FCmpInst::FCMP_OGE: return Expression::FCMPOGE; 00251 case FCmpInst::FCMP_OLT: return Expression::FCMPOLT; 00252 case FCmpInst::FCMP_OLE: return Expression::FCMPOLE; 00253 case FCmpInst::FCMP_ONE: return Expression::FCMPONE; 00254 case FCmpInst::FCMP_ORD: return Expression::FCMPORD; 00255 case FCmpInst::FCMP_UNO: return Expression::FCMPUNO; 00256 case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ; 00257 case FCmpInst::FCMP_UGT: return Expression::FCMPUGT; 00258 case FCmpInst::FCMP_UGE: return Expression::FCMPUGE; 00259 case FCmpInst::FCMP_ULT: return Expression::FCMPULT; 00260 case FCmpInst::FCMP_ULE: return Expression::FCMPULE; 00261 case FCmpInst::FCMP_UNE: return Expression::FCMPUNE; 00262 } 00263 } 00264 } 00265 00266 Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) { 00267 switch(C->getOpcode()) { 00268 default: // THIS SHOULD NEVER HAPPEN 00269 llvm_unreachable("Cast operator with unknown opcode?"); 00270 case Instruction::Trunc: return Expression::TRUNC; 00271 case Instruction::ZExt: return Expression::ZEXT; 00272 case Instruction::SExt: return Expression::SEXT; 00273 case Instruction::FPToUI: return Expression::FPTOUI; 00274 case Instruction::FPToSI: return Expression::FPTOSI; 00275 case Instruction::UIToFP: return Expression::UITOFP; 00276 case Instruction::SIToFP: return Expression::SITOFP; 00277 case Instruction::FPTrunc: return Expression::FPTRUNC; 00278 case Instruction::FPExt: return Expression::FPEXT; 00279 case Instruction::PtrToInt: return Expression::PTRTOINT; 00280 case Instruction::IntToPtr: return Expression::INTTOPTR; 00281 case Instruction::BitCast: return Expression::BITCAST; 00282 } 00283 } 00284 00285 Expression ValueTable::create_expression(CallInst* C) { 00286 Expression e; 00287 00288 e.type = C->getType(); 00289 e.firstVN = 0; 00290 e.secondVN = 0; 00291 e.thirdVN = 0; 00292 e.function = C->getCalledFunction(); 00293 e.opcode = Expression::CALL; 00294 00295 for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end(); 00296 I != E; ++I) 00297 e.varargs.push_back(lookup_or_add(*I)); 00298 00299 return e; 00300 } 00301 00302 Expression ValueTable::create_expression(BinaryOperator* BO) { 00303 Expression e; 00304 00305 e.firstVN = lookup_or_add(BO->getOperand(0)); 00306 e.secondVN = lookup_or_add(BO->getOperand(1)); 00307 e.thirdVN = 0; 00308 e.function = 0; 00309 e.type = BO->getType(); 00310 e.opcode = getOpcode(BO); 00311 00312 return e; 00313 } 00314 00315 Expression ValueTable::create_expression(CmpInst* C) { 00316 Expression e; 00317 00318 e.firstVN = lookup_or_add(C->getOperand(0)); 00319 e.secondVN = lookup_or_add(C->getOperand(1)); 00320 e.thirdVN = 0; 00321 e.function = 0; 00322 e.type = C->getType(); 00323 e.opcode = getOpcode(C); 00324 00325 return e; 00326 } 00327 00328 Expression ValueTable::create_expression(CastInst* C) { 00329 Expression e; 00330 00331 e.firstVN = lookup_or_add(C->getOperand(0)); 00332 e.secondVN = 0; 00333 e.thirdVN = 0; 00334 e.function = 0; 00335 e.type = C->getType(); 00336 e.opcode = getOpcode(C); 00337 00338 return e; 00339 } 00340 00341 Expression ValueTable::create_expression(ShuffleVectorInst* S) { 00342 Expression e; 00343 00344 e.firstVN = lookup_or_add(S->getOperand(0)); 00345 e.secondVN = lookup_or_add(S->getOperand(1)); 00346 e.thirdVN = lookup_or_add(S->getOperand(2)); 00347 e.function = 0; 00348 e.type = S->getType(); 00349 e.opcode = Expression::SHUFFLE; 00350 00351 return e; 00352 } 00353 00354 Expression ValueTable::create_expression(ExtractElementInst* E) { 00355 Expression e; 00356 00357 e.firstVN = lookup_or_add(E->getOperand(0)); 00358 e.secondVN = lookup_or_add(E->getOperand(1)); 00359 e.thirdVN = 0; 00360 e.function = 0; 00361 e.type = E->getType(); 00362 e.opcode = Expression::EXTRACT; 00363 00364 return e; 00365 } 00366 00367 Expression ValueTable::create_expression(InsertElementInst* I) { 00368 Expression e; 00369 00370 e.firstVN = lookup_or_add(I->getOperand(0)); 00371 e.secondVN = lookup_or_add(I->getOperand(1)); 00372 e.thirdVN = lookup_or_add(I->getOperand(2)); 00373 e.function = 0; 00374 e.type = I->getType(); 00375 e.opcode = Expression::INSERT; 00376 00377 return e; 00378 } 00379 00380 Expression ValueTable::create_expression(SelectInst* I) { 00381 Expression e; 00382 00383 e.firstVN = lookup_or_add(I->getCondition()); 00384 e.secondVN = lookup_or_add(I->getTrueValue()); 00385 e.thirdVN = lookup_or_add(I->getFalseValue()); 00386 e.function = 0; 00387 e.type = I->getType(); 00388 e.opcode = Expression::SELECT; 00389 00390 return e; 00391 } 00392 00393 Expression ValueTable::create_expression(GetElementPtrInst* G) { 00394 Expression e; 00395 00396 e.firstVN = lookup_or_add(G->getPointerOperand()); 00397 e.secondVN = 0; 00398 e.thirdVN = 0; 00399 e.function = 0; 00400 e.type = G->getType(); 00401 e.opcode = Expression::GEP; 00402 00403 for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end(); 00404 I != E; ++I) 00405 e.varargs.push_back(lookup_or_add(*I)); 00406 00407 return e; 00408 } 00409 00410 //===----------------------------------------------------------------------===// 00411 // ValueTable External Functions 00412 //===----------------------------------------------------------------------===// 00413 00414 /// add - Insert a value into the table with a specified value number. 00415 void ValueTable::add(Value* V, uint32_t num) { 00416 valueNumbering.insert(std::make_pair(V, num)); 00417 } 00418 00419 /// lookup_or_add - Returns the value number for the specified value, assigning 00420 /// it a new number if it did not have one before. 00421 uint32_t ValueTable::lookup_or_add(Value* V) { 00422 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 00423 if (VI != valueNumbering.end()) 00424 return VI->second; 00425 00426 if (CallInst* C = dyn_cast<CallInst>(V)) { 00427 if (AA->doesNotAccessMemory(C)) { 00428 Expression e = create_expression(C); 00429 00430 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00431 if (EI != expressionNumbering.end()) { 00432 valueNumbering.insert(std::make_pair(V, EI->second)); 00433 return EI->second; 00434 } else { 00435 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00436 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00437 00438 return nextValueNumber++; 00439 } 00440 } else if (AA->onlyReadsMemory(C)) { 00441 Expression e = create_expression(C); 00442 00443 if (expressionNumbering.find(e) == expressionNumbering.end()) { 00444 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00445 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00446 return nextValueNumber++; 00447 } 00448 00449 MemDepResult local_dep = MD->getDependency(C); 00450 00451 if (!local_dep.isDef() && !local_dep.isNonLocal()) { 00452 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00453 return nextValueNumber++; 00454 } 00455 00456 if (local_dep.isDef()) { 00457 CallInst* local_cdep = cast<CallInst>(local_dep.getInst()); 00458 00459 if (local_cdep->getNumOperands() != C->getNumOperands()) { 00460 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00461 return nextValueNumber++; 00462 } 00463 00464 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 00465 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 00466 uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); 00467 if (c_vn != cd_vn) { 00468 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00469 return nextValueNumber++; 00470 } 00471 } 00472 00473 uint32_t v = lookup_or_add(local_cdep); 00474 valueNumbering.insert(std::make_pair(V, v)); 00475 return v; 00476 } 00477 00478 // Non-local case. 00479 const MemoryDependenceAnalysis::NonLocalDepInfo &deps = 00480 MD->getNonLocalCallDependency(CallSite(C)); 00481 // FIXME: call/call dependencies for readonly calls should return def, not 00482 // clobber! Move the checking logic to MemDep! 00483 CallInst* cdep = 0; 00484 00485 // Check to see if we have a single dominating call instruction that is 00486 // identical to C. 00487 for (unsigned i = 0, e = deps.size(); i != e; ++i) { 00488 const MemoryDependenceAnalysis::NonLocalDepEntry *I = &deps[i]; 00489 // Ignore non-local dependencies. 00490 if (I->second.isNonLocal()) 00491 continue; 00492 00493 // We don't handle non-depedencies. If we already have a call, reject 00494 // instruction dependencies. 00495 if (I->second.isClobber() || cdep != 0) { 00496 cdep = 0; 00497 break; 00498 } 00499 00500 CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->second.getInst()); 00501 // FIXME: All duplicated with non-local case. 00502 if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){ 00503 cdep = NonLocalDepCall; 00504 continue; 00505 } 00506 00507 cdep = 0; 00508 break; 00509 } 00510 00511 if (!cdep) { 00512 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00513 return nextValueNumber++; 00514 } 00515 00516 if (cdep->getNumOperands() != C->getNumOperands()) { 00517 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00518 return nextValueNumber++; 00519 } 00520 for (unsigned i = 1; i < C->getNumOperands(); ++i) { 00521 uint32_t c_vn = lookup_or_add(C->getOperand(i)); 00522 uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); 00523 if (c_vn != cd_vn) { 00524 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00525 return nextValueNumber++; 00526 } 00527 } 00528 00529 uint32_t v = lookup_or_add(cdep); 00530 valueNumbering.insert(std::make_pair(V, v)); 00531 return v; 00532 00533 } else { 00534 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00535 return nextValueNumber++; 00536 } 00537 } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) { 00538 Expression e = create_expression(BO); 00539 00540 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00541 if (EI != expressionNumbering.end()) { 00542 valueNumbering.insert(std::make_pair(V, EI->second)); 00543 return EI->second; 00544 } else { 00545 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00546 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00547 00548 return nextValueNumber++; 00549 } 00550 } else if (CmpInst* C = dyn_cast<CmpInst>(V)) { 00551 Expression e = create_expression(C); 00552 00553 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00554 if (EI != expressionNumbering.end()) { 00555 valueNumbering.insert(std::make_pair(V, EI->second)); 00556 return EI->second; 00557 } else { 00558 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00559 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00560 00561 return nextValueNumber++; 00562 } 00563 } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) { 00564 Expression e = create_expression(U); 00565 00566 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00567 if (EI != expressionNumbering.end()) { 00568 valueNumbering.insert(std::make_pair(V, EI->second)); 00569 return EI->second; 00570 } else { 00571 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00572 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00573 00574 return nextValueNumber++; 00575 } 00576 } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) { 00577 Expression e = create_expression(U); 00578 00579 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00580 if (EI != expressionNumbering.end()) { 00581 valueNumbering.insert(std::make_pair(V, EI->second)); 00582 return EI->second; 00583 } else { 00584 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00585 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00586 00587 return nextValueNumber++; 00588 } 00589 } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) { 00590 Expression e = create_expression(U); 00591 00592 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00593 if (EI != expressionNumbering.end()) { 00594 valueNumbering.insert(std::make_pair(V, EI->second)); 00595 return EI->second; 00596 } else { 00597 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00598 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00599 00600 return nextValueNumber++; 00601 } 00602 } else if (SelectInst* U = dyn_cast<SelectInst>(V)) { 00603 Expression e = create_expression(U); 00604 00605 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00606 if (EI != expressionNumbering.end()) { 00607 valueNumbering.insert(std::make_pair(V, EI->second)); 00608 return EI->second; 00609 } else { 00610 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00611 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00612 00613 return nextValueNumber++; 00614 } 00615 } else if (CastInst* U = dyn_cast<CastInst>(V)) { 00616 Expression e = create_expression(U); 00617 00618 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00619 if (EI != expressionNumbering.end()) { 00620 valueNumbering.insert(std::make_pair(V, EI->second)); 00621 return EI->second; 00622 } else { 00623 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00624 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00625 00626 return nextValueNumber++; 00627 } 00628 } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) { 00629 Expression e = create_expression(U); 00630 00631 DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e); 00632 if (EI != expressionNumbering.end()) { 00633 valueNumbering.insert(std::make_pair(V, EI->second)); 00634 return EI->second; 00635 } else { 00636 expressionNumbering.insert(std::make_pair(e, nextValueNumber)); 00637 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00638 00639 return nextValueNumber++; 00640 } 00641 } else { 00642 valueNumbering.insert(std::make_pair(V, nextValueNumber)); 00643 return nextValueNumber++; 00644 } 00645 } 00646 00647 /// lookup - Returns the value number of the specified value. Fails if 00648 /// the value has not yet been numbered. 00649 uint32_t ValueTable::lookup(Value* V) const { 00650 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V); 00651 assert(VI != valueNumbering.end() && "Value not numbered?"); 00652 return VI->second; 00653 } 00654 00655 /// clear - Remove all entries from the ValueTable 00656 void ValueTable::clear() { 00657 valueNumbering.clear(); 00658 expressionNumbering.clear(); 00659 nextValueNumber = 1; 00660 } 00661 00662 /// erase - Remove a value from the value numbering 00663 void ValueTable::erase(Value* V) { 00664 valueNumbering.erase(V); 00665 } 00666 00667 /// verifyRemoved - Verify that the value is removed from all internal data 00668 /// structures. 00669 void ValueTable::verifyRemoved(const Value *V) const { 00670 for (DenseMap<Value*, uint32_t>::iterator 00671 I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) { 00672 assert(I->first != V && "Inst still occurs in value numbering map!"); 00673 } 00674 } 00675 00676 //===----------------------------------------------------------------------===// 00677 // GVN Pass 00678 //===----------------------------------------------------------------------===// 00679 00680 namespace { 00681 struct VISIBILITY_HIDDEN ValueNumberScope { 00682 ValueNumberScope* parent; 00683 DenseMap<uint32_t, Value*> table; 00684 00685 ValueNumberScope(ValueNumberScope* p) : parent(p) { } 00686 }; 00687 } 00688 00689 namespace { 00690 00691 class VISIBILITY_HIDDEN GVN : public FunctionPass { 00692 bool runOnFunction(Function &F); 00693 public: 00694 static char ID; // Pass identification, replacement for typeid 00695 GVN() : FunctionPass(&ID) { } 00696 00697 private: 00698 MemoryDependenceAnalysis *MD; 00699 DominatorTree *DT; 00700 00701 ValueTable VN; 00702 DenseMap<BasicBlock*, ValueNumberScope*> localAvail; 00703 00704 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType; 00705 PhiMapType phiMap; 00706 00707 00708 // This transformation requires dominator postdominator info 00709 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00710 AU.addRequired<DominatorTree>(); 00711 AU.addRequired<MemoryDependenceAnalysis>(); 00712 AU.addRequired<AliasAnalysis>(); 00713 00714 AU.addPreserved<DominatorTree>(); 00715 AU.addPreserved<AliasAnalysis>(); 00716 } 00717 00718 // Helper fuctions 00719 // FIXME: eliminate or document these better 00720 bool processLoad(LoadInst* L, 00721 SmallVectorImpl<Instruction*> &toErase); 00722 bool processInstruction(Instruction* I, 00723 SmallVectorImpl<Instruction*> &toErase); 00724 bool processNonLocalLoad(LoadInst* L, 00725 SmallVectorImpl<Instruction*> &toErase); 00726 bool processBlock(BasicBlock* BB); 00727 Value *GetValueForBlock(BasicBlock *BB, Instruction* orig, 00728 DenseMap<BasicBlock*, Value*> &Phis, 00729 bool top_level = false); 00730 void dump(DenseMap<uint32_t, Value*>& d); 00731 bool iterateOnFunction(Function &F); 00732 Value* CollapsePhi(PHINode* p); 00733 bool isSafeReplacement(PHINode* p, Instruction* inst); 00734 bool performPRE(Function& F); 00735 Value* lookupNumber(BasicBlock* BB, uint32_t num); 00736 bool mergeBlockIntoPredecessor(BasicBlock* BB); 00737 Value* AttemptRedundancyElimination(Instruction* orig, unsigned valno); 00738 void cleanupGlobalSets(); 00739 void verifyRemoved(const Instruction *I) const; 00740 }; 00741 00742 char GVN::ID = 0; 00743 } 00744 00745 // createGVNPass - The public interface to this file... 00746 FunctionPass *llvm::createGVNPass() { return new GVN(); } 00747 00748 static RegisterPass<GVN> X("gvn", 00749 "Global Value Numbering"); 00750 00751 void GVN::dump(DenseMap<uint32_t, Value*>& d) { 00752 printf("{\n"); 00753 for (DenseMap<uint32_t, Value*>::iterator I = d.begin(), 00754 E = d.end(); I != E; ++I) { 00755 printf("%d\n", I->first); 00756 I->second->dump(); 00757 } 00758 printf("}\n"); 00759 } 00760 00761 Value* GVN::CollapsePhi(PHINode* p) { 00762 Value* constVal = p->hasConstantValue(); 00763 if (!constVal) return 0; 00764 00765 Instruction* inst = dyn_cast<Instruction>(constVal); 00766 if (!inst) 00767 return constVal; 00768 00769 if (DT->dominates(inst, p)) 00770 if (isSafeReplacement(p, inst)) 00771 return inst; 00772 return 0; 00773 } 00774 00775 bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) { 00776 if (!isa<PHINode>(inst)) 00777 return true; 00778 00779 for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end(); 00780 UI != E; ++UI) 00781 if (PHINode* use_phi = dyn_cast<PHINode>(UI)) 00782 if (use_phi->getParent() == inst->getParent()) 00783 return false; 00784 00785 return true; 00786 } 00787 00788 /// GetValueForBlock - Get the value to use within the specified basic block. 00789 /// available values are in Phis. 00790 Value *GVN::GetValueForBlock(BasicBlock *BB, Instruction* orig, 00791 DenseMap<BasicBlock*, Value*> &Phis, 00792 bool top_level) { 00793 00794 // If we have already computed this value, return the previously computed val. 00795 DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB); 00796 if (V != Phis.end() && !top_level) return V->second; 00797 00798 // If the block is unreachable, just return undef, since this path 00799 // can't actually occur at runtime. 00800 if (!DT->isReachableFromEntry(BB)) 00801 return Phis[BB] = UndefValue::get(orig->getType()); 00802 00803 if (BasicBlock *Pred = BB->getSinglePredecessor()) { 00804 Value *ret = GetValueForBlock(Pred, orig, Phis); 00805 Phis[BB] = ret; 00806 return ret; 00807 } 00808 00809 // Get the number of predecessors of this block so we can reserve space later. 00810 // If there is already a PHI in it, use the #preds from it, otherwise count. 00811 // Getting it from the PHI is constant time. 00812 unsigned NumPreds; 00813 if (PHINode *ExistingPN = dyn_cast<PHINode>(BB->begin())) 00814 NumPreds = ExistingPN->getNumIncomingValues(); 00815 else 00816 NumPreds = std::distance(pred_begin(BB), pred_end(BB)); 00817 00818 // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so 00819 // now, then get values to fill in the incoming values for the PHI. 00820 PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle", 00821 BB->begin()); 00822 PN->reserveOperandSpace(NumPreds); 00823 00824 Phis.insert(std::make_pair(BB, PN)); 00825 00826 // Fill in the incoming values for the block. 00827 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 00828 Value* val = GetValueForBlock(*PI, orig, Phis); 00829 PN->addIncoming(val, *PI); 00830 } 00831 00832 VN.getAliasAnalysis()->copyValue(orig, PN); 00833 00834 // Attempt to collapse PHI nodes that are trivially redundant 00835 Value* v = CollapsePhi(PN); 00836 if (!v) { 00837 // Cache our phi construction results 00838 if (LoadInst* L = dyn_cast<LoadInst>(orig)) 00839 phiMap[L->getPointerOperand()].insert(PN); 00840 else 00841 phiMap[orig].insert(PN); 00842 00843 return PN; 00844 } 00845 00846 PN->replaceAllUsesWith(v); 00847 if (isa<PointerType>(v->getType())) 00848 MD->invalidateCachedPointerInfo(v); 00849 00850 for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(), 00851 E = Phis.end(); I != E; ++I) 00852 if (I->second == PN) 00853 I->second = v; 00854 00855 DEBUG(errs() << "GVN removed: " << *PN << '\n'); 00856 MD->removeInstruction(PN); 00857 PN->eraseFromParent(); 00858 DEBUG(verifyRemoved(PN)); 00859 00860 Phis[BB] = v; 00861 return v; 00862 } 00863 00864 /// IsValueFullyAvailableInBlock - Return true if we can prove that the value 00865 /// we're analyzing is fully available in the specified block. As we go, keep 00866 /// track of which blocks we know are fully alive in FullyAvailableBlocks. This 00867 /// map is actually a tri-state map with the following values: 00868 /// 0) we know the block *is not* fully available. 00869 /// 1) we know the block *is* fully available. 00870 /// 2) we do not know whether the block is fully available or not, but we are 00871 /// currently speculating that it will be. 00872 /// 3) we are speculating for this block and have used that to speculate for 00873 /// other blocks. 00874 static bool IsValueFullyAvailableInBlock(BasicBlock *BB, 00875 DenseMap<BasicBlock*, char> &FullyAvailableBlocks) { 00876 // Optimistically assume that the block is fully available and check to see 00877 // if we already know about this block in one lookup. 00878 std::pair<DenseMap<BasicBlock*, char>::iterator, char> IV = 00879 FullyAvailableBlocks.insert(std::make_pair(BB, 2)); 00880 00881 // If the entry already existed for this block, return the precomputed value. 00882 if (!IV.second) { 00883 // If this is a speculative "available" value, mark it as being used for 00884 // speculation of other blocks. 00885 if (IV.first->second == 2) 00886 IV.first->second = 3; 00887 return IV.first->second != 0; 00888 } 00889 00890 // Otherwise, see if it is fully available in all predecessors. 00891 pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 00892 00893 // If this block has no predecessors, it isn't live-in here. 00894 if (PI == PE) 00895 goto SpeculationFailure; 00896 00897 for (; PI != PE; ++PI) 00898 // If the value isn't fully available in one of our predecessors, then it 00899 // isn't fully available in this block either. Undo our previous 00900 // optimistic assumption and bail out. 00901 if (!IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 00902 goto SpeculationFailure; 00903 00904 return true; 00905 00906 // SpeculationFailure - If we get here, we found out that this is not, after 00907 // all, a fully-available block. We have a problem if we speculated on this and 00908 // used the speculation to mark other blocks as available. 00909 SpeculationFailure: 00910 char &BBVal = FullyAvailableBlocks[BB]; 00911 00912 // If we didn't speculate on this, just return with it set to false. 00913 if (BBVal == 2) { 00914 BBVal = 0; 00915 return false; 00916 } 00917 00918 // If we did speculate on this value, we could have blocks set to 1 that are 00919 // incorrect. Walk the (transitive) successors of this block and mark them as 00920 // 0 if set to one. 00921 SmallVector<BasicBlock*, 32> BBWorklist; 00922 BBWorklist.push_back(BB); 00923 00924 while (!BBWorklist.empty()) { 00925 BasicBlock *Entry = BBWorklist.pop_back_val(); 00926 // Note that this sets blocks to 0 (unavailable) if they happen to not 00927 // already be in FullyAvailableBlocks. This is safe. 00928 char &EntryVal = FullyAvailableBlocks[Entry]; 00929 if (EntryVal == 0) continue; // Already unavailable. 00930 00931 // Mark as unavailable. 00932 EntryVal = 0; 00933 00934 for (succ_iterator I = succ_begin(Entry), E = succ_end(Entry); I != E; ++I) 00935 BBWorklist.push_back(*I); 00936 } 00937 00938 return false; 00939 } 00940 00941 /// processNonLocalLoad - Attempt to eliminate a load whose dependencies are 00942 /// non-local by performing PHI construction. 00943 bool GVN::processNonLocalLoad(LoadInst *LI, 00944 SmallVectorImpl<Instruction*> &toErase) { 00945 // Find the non-local dependencies of the load. 00946 SmallVector<MemoryDependenceAnalysis::NonLocalDepEntry, 64> Deps; 00947 MD->getNonLocalPointerDependency(LI->getOperand(0), true, LI->getParent(), 00948 Deps); 00949 //DEBUG(errs() << "INVESTIGATING NONLOCAL LOAD: " 00950 // << Deps.size() << *LI << '\n'); 00951 00952 // If we had to process more than one hundred blocks to find the 00953 // dependencies, this load isn't worth worrying about. Optimizing 00954 // it will be too expensive. 00955 if (Deps.size() > 100) 00956 return false; 00957 00958 // If we had a phi translation failure, we'll have a single entry which is a 00959 // clobber in the current block. Reject this early. 00960 if (Deps.size() == 1 && Deps[0].second.isClobber()) { 00961 DEBUG( 00962 errs() << "GVN: non-local load "; 00963 WriteAsOperand(errs(), LI); 00964 errs() << " is clobbered by " << *Deps[0].second.getInst() << '\n'; 00965 ); 00966 return false; 00967 } 00968 00969 // Filter out useless results (non-locals, etc). Keep track of the blocks 00970 // where we have a value available in repl, also keep track of whether we see 00971 // dependencies that produce an unknown value for the load (such as a call 00972 // that could potentially clobber the load). 00973 SmallVector<std::pair<BasicBlock*, Value*>, 16> ValuesPerBlock; 00974 SmallVector<BasicBlock*, 16> UnavailableBlocks; 00975 00976 for (unsigned i = 0, e = Deps.size(); i != e; ++i) { 00977 BasicBlock *DepBB = Deps[i].first; 00978 MemDepResult DepInfo = Deps[i].second; 00979 00980 if (DepInfo.isClobber()) { 00981 UnavailableBlocks.push_back(DepBB); 00982 continue; 00983 } 00984 00985 Instruction *DepInst = DepInfo.getInst(); 00986 00987 // Loading the allocation -> undef. 00988 if (isa<AllocationInst>(DepInst)) { 00989 ValuesPerBlock.push_back(std::make_pair(DepBB, 00990 UndefValue::get(LI->getType()))); 00991 continue; 00992 } 00993 00994 if (StoreInst* S = dyn_cast<StoreInst>(DepInst)) { 00995 // Reject loads and stores that are to the same address but are of 00996 // different types. 00997 // NOTE: 403.gcc does have this case (e.g. in readonly_fields_p) because 00998 // of bitfield access, it would be interesting to optimize for it at some 00999 // point. 01000 if (S->getOperand(0)->getType() != LI->getType()) { 01001 UnavailableBlocks.push_back(DepBB); 01002 continue; 01003 } 01004 01005 ValuesPerBlock.push_back(std::make_pair(DepBB, S->getOperand(0))); 01006 01007 } else if (LoadInst* LD = dyn_cast<LoadInst>(DepInst)) { 01008 if (LD->getType() != LI->getType()) { 01009 UnavailableBlocks.push_back(DepBB); 01010 continue; 01011 } 01012 ValuesPerBlock.push_back(std::make_pair(DepBB, LD)); 01013 } else { 01014 UnavailableBlocks.push_back(DepBB); 01015 continue; 01016 } 01017 } 01018 01019 // If we have no predecessors that produce a known value for this load, exit 01020 // early. 01021 if (ValuesPerBlock.empty()) return false; 01022 01023 // If all of the instructions we depend on produce a known value for this 01024 // load, then it is fully redundant and we can use PHI insertion to compute 01025 // its value. Insert PHIs and remove the fully redundant value now. 01026 if (UnavailableBlocks.empty()) { 01027 // Use cached PHI construction information from previous runs 01028 SmallPtrSet<Instruction*, 4> &p = phiMap[LI->getPointerOperand()]; 01029 // FIXME: What does phiMap do? Are we positive it isn't getting invalidated? 01030 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 01031 I != E; ++I) { 01032 if ((*I)->getParent() == LI->getParent()) { 01033 DEBUG(errs() << "GVN REMOVING NONLOCAL LOAD #1: " << *LI << '\n'); 01034 LI->replaceAllUsesWith(*I); 01035 if (isa<PointerType>((*I)->getType())) 01036 MD->invalidateCachedPointerInfo(*I); 01037 toErase.push_back(LI); 01038 NumGVNLoad++; 01039 return true; 01040 } 01041 01042 ValuesPerBlock.push_back(std::make_pair((*I)->getParent(), *I)); 01043 } 01044 01045 DEBUG(errs() << "GVN REMOVING NONLOCAL LOAD: " << *LI << '\n'); 01046 01047 DenseMap<BasicBlock*, Value*> BlockReplValues; 01048 BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 01049 // Perform PHI construction. 01050 Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 01051 LI->replaceAllUsesWith(v); 01052 01053 if (isa<PHINode>(v)) 01054 v->takeName(LI); 01055 if (isa<PointerType>(v->getType())) 01056 MD->invalidateCachedPointerInfo(v); 01057 toErase.push_back(LI); 01058 NumGVNLoad++; 01059 return true; 01060 } 01061 01062 if (!EnablePRE || !EnableLoadPRE) 01063 return false; 01064 01065 // Okay, we have *some* definitions of the value. This means that the value 01066 // is available in some of our (transitive) predecessors. Lets think about 01067 // doing PRE of this load. This will involve inserting a new load into the 01068 // predecessor when it's not available. We could do this in general, but 01069 // prefer to not increase code size. As such, we only do this when we know 01070 // that we only have to insert *one* load (which means we're basically moving 01071 // the load, not inserting a new one). 01072 01073 SmallPtrSet<BasicBlock *, 4> Blockers; 01074 for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i) 01075 Blockers.insert(UnavailableBlocks[i]); 01076 01077 // Lets find first basic block with more than one predecessor. Walk backwards 01078 // through predecessors if needed. 01079 BasicBlock *LoadBB = LI->getParent(); 01080 BasicBlock *TmpBB = LoadBB; 01081 01082 bool isSinglePred = false; 01083 bool allSingleSucc = true; 01084 while (TmpBB->getSinglePredecessor()) { 01085 isSinglePred = true; 01086 TmpBB = TmpBB->getSinglePredecessor(); 01087 if (!TmpBB) // If haven't found any, bail now. 01088 return false; 01089 if (TmpBB == LoadBB) // Infinite (unreachable) loop. 01090 return false; 01091 if (Blockers.count(TmpBB)) 01092 return false; 01093 if (TmpBB->getTerminator()->getNumSuccessors() != 1) 01094 allSingleSucc = false; 01095 } 01096 01097 assert(TmpBB); 01098 LoadBB = TmpBB; 01099 01100 // If we have a repl set with LI itself in it, this means we have a loop where 01101 // at least one of the values is LI. Since this means that we won't be able 01102 // to eliminate LI even if we insert uses in the other predecessors, we will 01103 // end up increasing code size. Reject this by scanning for LI. 01104 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 01105 if (ValuesPerBlock[i].second == LI) 01106 return false; 01107 01108 if (isSinglePred) { 01109 bool isHot = false; 01110 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 01111 if (Instruction *I = dyn_cast<Instruction>(ValuesPerBlock[i].second)) 01112 // "Hot" Instruction is in some loop (because it dominates its dep. 01113 // instruction). 01114 if (DT->dominates(LI, I)) { 01115 isHot = true; 01116 break; 01117 } 01118 01119 // We are interested only in "hot" instructions. We don't want to do any 01120 // mis-optimizations here. 01121 if (!isHot) 01122 return false; 01123 } 01124 01125 // Okay, we have some hope :). Check to see if the loaded value is fully 01126 // available in all but one predecessor. 01127 // FIXME: If we could restructure the CFG, we could make a common pred with 01128 // all the preds that don't have an available LI and insert a new load into 01129 // that one block. 01130 BasicBlock *UnavailablePred = 0; 01131 01132 DenseMap<BasicBlock*, char> FullyAvailableBlocks; 01133 for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) 01134 FullyAvailableBlocks[ValuesPerBlock[i].first] = true; 01135 for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i) 01136 FullyAvailableBlocks[UnavailableBlocks[i]] = false; 01137 01138 for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); 01139 PI != E; ++PI) { 01140 if (IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks)) 01141 continue; 01142 01143 // If this load is not available in multiple predecessors, reject it. 01144 if (UnavailablePred && UnavailablePred != *PI) 01145 return false; 01146 UnavailablePred = *PI; 01147 } 01148 01149 assert(UnavailablePred != 0 && 01150 "Fully available value should be eliminated above!"); 01151 01152 // If the loaded pointer is PHI node defined in this block, do PHI translation 01153 // to get its value in the predecessor. 01154 Value *LoadPtr = LI->getOperand(0)->DoPHITranslation(LoadBB, UnavailablePred); 01155 01156 // Make sure the value is live in the predecessor. If it was defined by a 01157 // non-PHI instruction in this block, we don't know how to recompute it above. 01158 if (Instruction *LPInst = dyn_cast<Instruction>(LoadPtr)) 01159 if (!DT->dominates(LPInst->getParent(), UnavailablePred)) { 01160 DEBUG(errs() << "COULDN'T PRE LOAD BECAUSE PTR IS UNAVAILABLE IN PRED: " 01161 << *LPInst << '\n' << *LI << "\n"); 01162 return false; 01163 } 01164 01165 // We don't currently handle critical edges :( 01166 if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) { 01167 DEBUG(errs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '" 01168 << UnavailablePred->getName() << "': " << *LI << '\n'); 01169 return false; 01170 } 01171 01172 // Make sure it is valid to move this load here. We have to watch out for: 01173 // @1 = getelementptr (i8* p, ... 01174 // test p and branch if == 0 01175 // load @1 01176 // It is valid to have the getelementptr before the test, even if p can be 0, 01177 // as getelementptr only does address arithmetic. 01178 // If we are not pushing the value through any multiple-successor blocks 01179 // we do not have this case. Otherwise, check that the load is safe to 01180 // put anywhere; this can be improved, but should be conservatively safe. 01181 if (!allSingleSucc && 01182 !isSafeToLoadUnconditionally(LoadPtr, UnavailablePred->getTerminator())) 01183 return false; 01184 01185 // Okay, we can eliminate this load by inserting a reload in the predecessor 01186 // and using PHI construction to get the value in the other predecessors, do 01187 // it. 01188 DEBUG(errs() << "GVN REMOVING PRE LOAD: " << *LI << '\n'); 01189 01190 Value *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false, 01191 LI->getAlignment(), 01192 UnavailablePred->getTerminator()); 01193 01194 SmallPtrSet<Instruction*, 4> &p = phiMap[LI->getPointerOperand()]; 01195 for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end(); 01196 I != E; ++I) 01197 ValuesPerBlock.push_back(std::make_pair((*I)->getParent(), *I)); 01198 01199 DenseMap<BasicBlock*, Value*> BlockReplValues; 01200 BlockReplValues.insert(ValuesPerBlock.begin(), ValuesPerBlock.end()); 01201 BlockReplValues[UnavailablePred] = NewLoad; 01202 01203 // Perform PHI construction. 01204 Value* v = GetValueForBlock(LI->getParent(), LI, BlockReplValues, true); 01205 LI->replaceAllUsesWith(v); 01206 if (isa<PHINode>(v)) 01207 v->takeName(LI); 01208 if (isa<PointerType>(v->getType())) 01209 MD->invalidateCachedPointerInfo(v); 01210 toErase.push_back(LI); 01211 NumPRELoad++; 01212 return true; 01213 } 01214 01215 /// processLoad - Attempt to eliminate a load, first by eliminating it 01216 /// locally, and then attempting non-local elimination if that fails. 01217 bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) { 01218 if (L->isVolatile()) 01219 return false; 01220 01221 Value* pointer = L->getPointerOperand(); 01222 01223 // ... to a pointer that has been loaded from before... 01224 MemDepResult dep = MD->getDependency(L); 01225 01226 // If the value isn't available, don't do anything! 01227 if (dep.isClobber()) { 01228 DEBUG( 01229 // fast print dep, using operator<< on instruction would be too slow 01230 errs() << "GVN: load "; 01231 WriteAsOperand(errs(), L); 01232 Instruction *I = dep.getInst(); 01233 errs() << " is clobbered by " << *I << '\n'; 01234 ); 01235 return false; 01236 } 01237 01238 // If it is defined in another block, try harder. 01239 if (dep.isNonLocal()) 01240 return processNonLocalLoad(L, toErase); 01241 01242 Instruction *DepInst = dep.getInst(); 01243 if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) { 01244 // Only forward substitute stores to loads of the same type. 01245 // FIXME: Could do better! 01246 if (DepSI->getPointerOperand()->getType() != pointer->getType()) 01247 return false; 01248 01249 // Remove it! 01250 L->replaceAllUsesWith(DepSI->getOperand(0)); 01251 if (isa<PointerType>(DepSI->getOperand(0)->getType())) 01252 MD->invalidateCachedPointerInfo(DepSI->getOperand(0)); 01253 toErase.push_back(L); 01254 NumGVNLoad++; 01255 return true; 01256 } 01257 01258 if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) { 01259 // Only forward substitute stores to loads of the same type. 01260 // FIXME: Could do better! load i32 -> load i8 -> truncate on little endian. 01261 if (DepLI->getType() != L->getType()) 01262 return false; 01263 01264 // Remove it! 01265 L->replaceAllUsesWith(DepLI); 01266 if (isa<PointerType>(DepLI->getType())) 01267 MD->invalidateCachedPointerInfo(DepLI); 01268 toErase.push_back(L); 01269 NumGVNLoad++; 01270 return true; 01271 } 01272 01273 // If this load really doesn't depend on anything, then we must be loading an 01274 // undef value. This can happen when loading for a fresh allocation with no 01275 // intervening stores, for example. 01276 if (isa<AllocationInst>(DepInst)) { 01277 L->replaceAllUsesWith(UndefValue::get(L->getType())); 01278 toErase.push_back(L); 01279 NumGVNLoad++; 01280 return true; 01281 } 01282 01283 return false; 01284 } 01285 01286 Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { 01287 DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB); 01288 if (I == localAvail.end()) 01289 return 0; 01290 01291 ValueNumberScope* locals = I->second; 01292 01293 while (locals) { 01294 DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num); 01295 if (I != locals->table.end()) 01296 return I->second; 01297 else 01298 locals = locals->parent; 01299 } 01300 01301 return 0; 01302 } 01303 01304 /// AttemptRedundancyElimination - If the "fast path" of redundancy elimination 01305 /// by inheritance from the dominator fails, see if we can perform phi 01306 /// construction to eliminate the redundancy. 01307 Value* GVN::AttemptRedundancyElimination(Instruction* orig, unsigned valno) { 01308 BasicBlock* BaseBlock = orig->getParent(); 01309 01310 SmallPtrSet<BasicBlock*, 4> Visited; 01311 SmallVector<BasicBlock*, 8> Stack; 01312 Stack.push_back(BaseBlock); 01313 01314 DenseMap<BasicBlock*, Value*> Results; 01315 01316 // Walk backwards through our predecessors, looking for instances of the 01317 // value number we're looking for. Instances are recorded in the Results 01318 // map, which is then used to perform phi construction. 01319 while (!Stack.empty()) { 01320 BasicBlock* Current = Stack.back(); 01321 Stack.pop_back(); 01322 01323 // If we've walked all the way to a proper dominator, then give up. Cases 01324 // where the instance is in the dominator will have been caught by the fast 01325 // path, and any cases that require phi construction further than this are 01326 // probably not worth it anyways. Note that this is a SIGNIFICANT compile 01327 // time improvement. 01328 if (DT->properlyDominates(Current, orig->getParent())) return 0; 01329 01330 DenseMap<BasicBlock*, ValueNumberScope*>::iterator LA = 01331 localAvail.find(Current); 01332 if (LA == localAvail.end()) return 0; 01333 DenseMap<uint32_t, Value*>::iterator V = LA->second->table.find(valno); 01334 01335 if (V != LA->second->table.end()) { 01336 // Found an instance, record it. 01337 Results.insert(std::make_pair(Current, V->second)); 01338 continue; 01339 } 01340 01341 // If we reach the beginning of the function, then give up. 01342 if (pred_begin(Current) == pred_end(Current)) 01343 return 0; 01344 01345 for (pred_iterator PI = pred_begin(Current), PE = pred_end(Current); 01346 PI != PE; ++PI) 01347 if (Visited.insert(*PI)) 01348 Stack.push_back(*PI); 01349 } 01350 01351 // If we didn't find instances, give up. Otherwise, perform phi construction. 01352 if (Results.size() == 0) 01353 return 0; 01354 else 01355 return GetValueForBlock(BaseBlock, orig, Results, true); 01356 } 01357 01358 /// processInstruction - When calculating availability, handle an instruction 01359 /// by inserting it into the appropriate sets 01360 bool GVN::processInstruction(Instruction *I, 01361 SmallVectorImpl<Instruction*> &toErase) { 01362 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 01363 bool changed = processLoad(L, toErase); 01364 01365 if (!changed) { 01366 unsigned num = VN.lookup_or_add(L); 01367 localAvail[I->getParent()]->table.insert(std::make_pair(num, L)); 01368 } 01369 01370 return changed; 01371 } 01372 01373 uint32_t nextNum = VN.getNextUnusedValueNumber(); 01374 unsigned num = VN.lookup_or_add(I); 01375 01376 if (BranchInst* BI = dyn_cast<BranchInst>(I)) { 01377 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 01378 01379 if (!BI->isConditional() || isa<Constant>(BI->getCondition())) 01380 return false; 01381 01382 Value* branchCond = BI->getCondition(); 01383 uint32_t condVN = VN.lookup_or_add(branchCond); 01384 01385 BasicBlock* trueSucc = BI->getSuccessor(0); 01386 BasicBlock* falseSucc = BI->getSuccessor(1); 01387 01388 if (trueSucc->getSinglePredecessor()) 01389 localAvail[trueSucc]->table[condVN] = 01390 ConstantInt::getTrue(trueSucc->getContext()); 01391 if (falseSucc->getSinglePredecessor()) 01392 localAvail[falseSucc]->table[condVN] = 01393 ConstantInt::getFalse(trueSucc->getContext()); 01394 01395 return false; 01396 01397 // Allocations are always uniquely numbered, so we can save time and memory 01398 // by fast failing them. 01399 } else if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) { 01400 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 01401 return false; 01402 } 01403 01404 // Collapse PHI nodes 01405 if (PHINode* p = dyn_cast<PHINode>(I)) { 01406 Value* constVal = CollapsePhi(p); 01407 01408 if (constVal) { 01409 for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end(); 01410 PI != PE; ++PI) 01411 PI->second.erase(p); 01412 01413 p->replaceAllUsesWith(constVal); 01414 if (isa<PointerType>(constVal->getType())) 01415 MD->invalidateCachedPointerInfo(constVal); 01416 VN.erase(p); 01417 01418 toErase.push_back(p); 01419 } else { 01420 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 01421 } 01422 01423 // If the number we were assigned was a brand new VN, then we don't 01424 // need to do a lookup to see if the number already exists 01425 // somewhere in the domtree: it can't! 01426 } else if (num == nextNum) { 01427 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 01428 01429 // Perform fast-path value-number based elimination of values inherited from 01430 // dominators. 01431 } else if (Value* repl = lookupNumber(I->getParent(), num)) { 01432 // Remove it! 01433 VN.erase(I); 01434 I->replaceAllUsesWith(repl); 01435 if (isa<PointerType>(repl->getType())) 01436 MD->invalidateCachedPointerInfo(repl); 01437 toErase.push_back(I); 01438 return true; 01439 01440 #if 0 01441 // Perform slow-pathvalue-number based elimination with phi construction. 01442 } else if (Value* repl = AttemptRedundancyElimination(I, num)) { 01443 // Remove it! 01444 VN.erase(I); 01445 I->replaceAllUsesWith(repl); 01446 if (isa<PointerType>(repl->getType())) 01447 MD->invalidateCachedPointerInfo(repl); 01448 toErase.push_back(I); 01449 return true; 01450 #endif 01451 } else { 01452 localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); 01453 } 01454 01455 return false; 01456 } 01457 01458 /// runOnFunction - This is the main transformation entry point for a function. 01459 bool GVN::runOnFunction(Function& F) { 01460 MD = &getAnalysis<MemoryDependenceAnalysis>(); 01461 DT = &getAnalysis<DominatorTree>(); 01462 VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>()); 01463 VN.setMemDep(MD); 01464 VN.setDomTree(DT); 01465 01466 bool changed = false; 01467 bool shouldContinue = true; 01468 01469 // Merge unconditional branches, allowing PRE to catch more 01470 // optimization opportunities. 01471 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { 01472 BasicBlock* BB = FI; 01473 ++FI; 01474 bool removedBlock = MergeBlockIntoPredecessor(BB, this); 01475 if (removedBlock) NumGVNBlocks++; 01476 01477 changed |= removedBlock; 01478 } 01479 01480 unsigned Iteration = 0; 01481 01482 while (shouldContinue) { 01483 DEBUG(errs() << "GVN iteration: " << Iteration << "\n"); 01484 shouldContinue = iterateOnFunction(F); 01485 changed |= shouldContinue; 01486 ++Iteration; 01487 } 01488 01489 if (EnablePRE) { 01490 bool PREChanged = true; 01491 while (PREChanged) { 01492 PREChanged = performPRE(F); 01493 changed |= PREChanged; 01494 } 01495 } 01496 // FIXME: Should perform GVN again after PRE does something. PRE can move 01497 // computations into blocks where they become fully redundant. Note that 01498 // we can't do this until PRE's critical edge splitting updates memdep. 01499 // Actually, when this happens, we should just fully integrate PRE into GVN. 01500 01501 cleanupGlobalSets(); 01502 01503 return changed; 01504 } 01505 01506 01507 bool GVN::processBlock(BasicBlock* BB) { 01508 // FIXME: Kill off toErase by doing erasing eagerly in a helper function (and 01509 // incrementing BI before processing an instruction). 01510 SmallVector<Instruction*, 8> toErase; 01511 bool changed_function = false; 01512 01513 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 01514 BI != BE;) { 01515 changed_function |= processInstruction(BI, toErase); 01516 if (toErase.empty()) { 01517 ++BI; 01518 continue; 01519 } 01520 01521 // If we need some instructions deleted, do it now. 01522 NumGVNInstr += toErase.size(); 01523 01524 // Avoid iterator invalidation. 01525 bool AtStart = BI == BB->begin(); 01526 if (!AtStart) 01527 --BI; 01528 01529 for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(), 01530 E = toErase.end(); I != E; ++I) { 01531 DEBUG(errs() << "GVN removed: " << **I << '\n'); 01532 MD->removeInstruction(*I); 01533 (*I)->eraseFromParent(); 01534 DEBUG(verifyRemoved(*I)); 01535 } 01536 toErase.clear(); 01537 01538 if (AtStart) 01539 BI = BB->begin(); 01540 else 01541 ++BI; 01542 } 01543 01544 return changed_function; 01545 } 01546 01547 /// performPRE - Perform a purely local form of PRE that looks for diamond 01548 /// control flow patterns and attempts to perform simple PRE at the join point. 01549 bool GVN::performPRE(Function& F) { 01550 bool Changed = false; 01551 SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit; 01552 DenseMap<BasicBlock*, Value*> predMap; 01553 for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()), 01554 DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { 01555 BasicBlock* CurrentBlock = *DI; 01556 01557 // Nothing to PRE in the entry block. 01558 if (CurrentBlock == &F.getEntryBlock()) continue; 01559 01560 for (BasicBlock::iterator BI = CurrentBlock->begin(), 01561 BE = CurrentBlock->end(); BI != BE; ) { 01562 Instruction *CurInst = BI++; 01563 01564 if (isa<AllocationInst>(CurInst) || isa<TerminatorInst>(CurInst) || 01565 isa<PHINode>(CurInst) || 01566 (CurInst->getType() == Type::getVoidTy(F.getContext())) || 01567 CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() || 01568 isa<DbgInfoIntrinsic>(CurInst)) 01569 continue; 01570 01571 uint32_t valno = VN.lookup(CurInst); 01572 01573 // Look for the predecessors for PRE opportunities. We're 01574 // only trying to solve the basic diamond case, where 01575 // a value is computed in the successor and one predecessor, 01576 // but not the other. We also explicitly disallow cases 01577 // where the successor is its own predecessor, because they're 01578 // more complicated to get right. 01579 unsigned numWith = 0; 01580 unsigned numWithout = 0; 01581 BasicBlock* PREPred = 0; 01582 predMap.clear(); 01583 01584 for (pred_iterator PI = pred_begin(CurrentBlock), 01585 PE = pred_end(CurrentBlock); PI != PE; ++PI) { 01586 // We're not interested in PRE where the block is its 01587 // own predecessor, on in blocks with predecessors 01588 // that are not reachable. 01589 if (*PI == CurrentBlock) { 01590 numWithout = 2; 01591 break; 01592 } else if (!localAvail.count(*PI)) { 01593 numWithout = 2; 01594 break; 01595 } 01596 01597 DenseMap<uint32_t, Value*>::iterator predV = 01598 localAvail[*PI]->table.find(valno); 01599 if (predV == localAvail[*PI]->table.end()) { 01600 PREPred = *PI; 01601 numWithout++; 01602 } else if (predV->second == CurInst) { 01603 numWithout = 2; 01604 } else { 01605 predMap[*PI] = predV->second; 01606 numWith++; 01607 } 01608 } 01609 01610 // Don't do PRE when it might increase code size, i.e. when 01611 // we would need to insert instructions in more than one pred. 01612 if (numWithout != 1 || numWith == 0) 01613 continue; 01614 01615 // We can't do PRE safely on a critical edge, so instead we schedule 01616 // the edge to be split and perform the PRE the next time we iterate 01617 // on the function. 01618 unsigned succNum = 0; 01619 for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors(); 01620 i != e; ++i) 01621 if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) { 01622 succNum = i; 01623 break; 01624 } 01625 01626 if (isCriticalEdge(PREPred->getTerminator(), succNum)) { 01627 toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum)); 01628 continue; 01629 } 01630 01631 // Instantiate the expression the in predecessor that lacked it. 01632 // Because we are going top-down through the block, all value numbers 01633 // will be available in the predecessor by the time we need them. Any 01634 // that weren't original present will have been instantiated earlier 01635 // in this loop. 01636 Instruction* PREInstr = CurInst->clone(CurInst->getContext()); 01637 bool success = true; 01638 for (unsigned i = 0, e = CurInst->getNumOperands(); i != e; ++i) { 01639 Value *Op = PREInstr->getOperand(i); 01640 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op)) 01641 continue; 01642 01643 if (Value *V = lookupNumber(PREPred, VN.lookup(Op))) { 01644 PREInstr->setOperand(i, V); 01645 } else { 01646 success = false; 01647 break; 01648 } 01649 } 01650 01651 // Fail out if we encounter an operand that is not available in 01652 // the PRE predecessor. This is typically because of loads which 01653 // are not value numbered precisely. 01654 if (!success) { 01655 delete PREInstr; 01656 DEBUG(verifyRemoved(PREInstr)); 01657 continue; 01658 } 01659 01660 PREInstr->insertBefore(PREPred->getTerminator()); 01661 PREInstr->setName(CurInst->getName() + ".pre"); 01662 predMap[PREPred] = PREInstr; 01663 VN.add(PREInstr, valno); 01664 NumGVNPRE++; 01665 01666 // Update the availability map to include the new instruction. 01667 localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr)); 01668 01669 // Create a PHI to make the value available in this block. 01670 PHINode* Phi = PHINode::Create(CurInst->getType(), 01671 CurInst->getName() + ".pre-phi", 01672 CurrentBlock->begin()); 01673 for (pred_iterator PI = pred_begin(CurrentBlock), 01674 PE = pred_end(CurrentBlock); PI != PE; ++PI) 01675 Phi->addIncoming(predMap[*PI], *PI); 01676 01677 VN.add(Phi, valno); 01678 localAvail[CurrentBlock]->table[valno] = Phi; 01679 01680 CurInst->replaceAllUsesWith(Phi); 01681 if (isa<PointerType>(Phi->getType())) 01682 MD->invalidateCachedPointerInfo(Phi); 01683 VN.erase(CurInst); 01684 01685 DEBUG(errs() << "GVN PRE removed: " << *CurInst << '\n'); 01686 MD->removeInstruction(CurInst); 01687 CurInst->eraseFromParent(); 01688 DEBUG(verifyRemoved(CurInst)); 01689 Changed = true; 01690 } 01691 } 01692 01693 for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator 01694 I = toSplit.begin(), E = toSplit.end(); I != E; ++I) 01695 SplitCriticalEdge(I->first, I->second, this); 01696 01697 return Changed || toSplit.size(); 01698 } 01699 01700 /// iterateOnFunction - Executes one iteration of GVN 01701 bool GVN::iterateOnFunction(Function &F) { 01702 cleanupGlobalSets(); 01703 01704 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 01705 DE = df_end(DT->getRootNode()); DI != DE; ++DI) { 01706 if (DI->getIDom()) 01707 localAvail[DI->getBlock()] = 01708 new ValueNumberScope(localAvail[DI->getIDom()->getBlock()]); 01709 else 01710 localAvail[DI->getBlock()] = new ValueNumberScope(0); 01711 } 01712 01713 // Top-down walk of the dominator tree 01714 bool changed = false; 01715 #if 0 01716 // Needed for value numbering with phi construction to work. 01717 ReversePostOrderTraversal<Function*> RPOT(&F); 01718 for (ReversePostOrderTraversal<Function*>::rpo_iterator RI = RPOT.begin(), 01719 RE = RPOT.end(); RI != RE; ++RI) 01720 changed |= processBlock(*RI); 01721 #else 01722 for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()), 01723 DE = df_end(DT->getRootNode()); DI != DE; ++DI) 01724 changed |= processBlock(DI->getBlock()); 01725 #endif 01726 01727 return changed; 01728 } 01729 01730 void GVN::cleanupGlobalSets() { 01731 VN.clear(); 01732 phiMap.clear(); 01733 01734 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 01735 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) 01736 delete I->second; 01737 localAvail.clear(); 01738 } 01739 01740 /// verifyRemoved - Verify that the specified instruction does not occur in our 01741 /// internal data structures. 01742 void GVN::verifyRemoved(const Instruction *Inst) const { 01743 VN.verifyRemoved(Inst); 01744 01745 // Walk through the PHI map to make sure the instruction isn't hiding in there 01746 // somewhere. 01747 for (PhiMapType::iterator 01748 I = phiMap.begin(), E = phiMap.end(); I != E; ++I) { 01749 assert(I->first != Inst && "Inst is still a key in PHI map!"); 01750 01751 for (SmallPtrSet<Instruction*, 4>::iterator 01752 II = I->second.begin(), IE = I->second.end(); II != IE; ++II) { 01753 assert(*II != Inst && "Inst is still a value in PHI map!"); 01754 } 01755 } 01756 01757 // Walk through the value number scope to make sure the instruction isn't 01758 // ferreted away in it. 01759 for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator 01760 I = localAvail.begin(), E = localAvail.end(); I != E; ++I) { 01761 const ValueNumberScope *VNS = I->second; 01762 01763 while (VNS) { 01764 for (DenseMap<uint32_t, Value*>::iterator 01765 II = VNS->table.begin(), IE = VNS->table.end(); II != IE; ++II) { 01766 assert(II->second != Inst && "Inst still in value numbering scope!"); 01767 } 01768 01769 VNS = VNS->parent; 01770 } 01771 } 01772 }