LLVM API Documentation

GVN.cpp

Go to the documentation of this file.
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 }