LLVM API Documentation

GVNPRE.cpp

Go to the documentation of this file.
00001 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
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 a hybrid of global value numbering and partial redundancy
00011 // elimination, known as GVN-PRE.  It performs partial redundancy elimination on
00012 // values, rather than lexical expressions, allowing a more comprehensive view 
00013 // the optimization.  It replaces redundant values with uses of earlier 
00014 // occurences of the same value.  While this is beneficial in that it eliminates
00015 // unneeded computation, it also increases register pressure by creating large
00016 // live ranges, and should be used with caution on platforms that are very 
00017 // sensitive to register pressure.
00018 //
00019 // Note that this pass does the value numbering itself, it does not use the
00020 // ValueNumbering analysis passes.
00021 //
00022 //===----------------------------------------------------------------------===//
00023 
00024 #define DEBUG_TYPE "gvnpre"
00025 #include "llvm/Value.h"
00026 #include "llvm/Transforms/Scalar.h"
00027 #include "llvm/Instructions.h"
00028 #include "llvm/Function.h"
00029 #include "llvm/DerivedTypes.h"
00030 #include "llvm/Analysis/Dominators.h"
00031 #include "llvm/ADT/BitVector.h"
00032 #include "llvm/ADT/DenseMap.h"
00033 #include "llvm/ADT/DepthFirstIterator.h"
00034 #include "llvm/ADT/PostOrderIterator.h"
00035 #include "llvm/ADT/SmallPtrSet.h"
00036 #include "llvm/ADT/SmallVector.h"
00037 #include "llvm/ADT/Statistic.h"
00038 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
00039 #include "llvm/Support/CFG.h"
00040 #include "llvm/Support/Compiler.h"
00041 #include "llvm/Support/Debug.h"
00042 #include "llvm/Support/ErrorHandling.h"
00043 #include <algorithm>
00044 #include <deque>
00045 #include <map>
00046 using namespace llvm;
00047 
00048 //===----------------------------------------------------------------------===//
00049 //                         ValueTable Class
00050 //===----------------------------------------------------------------------===//
00051 
00052 namespace {
00053 
00054 /// This class holds the mapping between values and value numbers.  It is used
00055 /// as an efficient mechanism to determine the expression-wise equivalence of
00056 /// two values.
00057 
00058 struct Expression {
00059   enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
00060                           UDIV, SDIV, FDIV, UREM, SREM,
00061                           FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ, 
00062                           ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE, 
00063                           ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ, 
00064                           FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE, 
00065                           FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE, 
00066                           FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
00067                           SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
00068                           FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT, 
00069                           PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
00070                           TOMBSTONE };
00071 
00072   ExpressionOpcode opcode;
00073   const Type* type;
00074   uint32_t firstVN;
00075   uint32_t secondVN;
00076   uint32_t thirdVN;
00077   SmallVector<uint32_t, 4> varargs;
00078   
00079   Expression() { }
00080   explicit Expression(ExpressionOpcode o) : opcode(o) { }
00081   
00082   bool operator==(const Expression &other) const {
00083     if (opcode != other.opcode)
00084       return false;
00085     else if (opcode == EMPTY || opcode == TOMBSTONE)
00086       return true;
00087     else if (type != other.type)
00088       return false;
00089     else if (firstVN != other.firstVN)
00090       return false;
00091     else if (secondVN != other.secondVN)
00092       return false;
00093     else if (thirdVN != other.thirdVN)
00094       return false;
00095     else {
00096       if (varargs.size() != other.varargs.size())
00097         return false;
00098       
00099       for (size_t i = 0; i < varargs.size(); ++i)
00100         if (varargs[i] != other.varargs[i])
00101           return false;
00102     
00103       return true;
00104     }
00105   }
00106   
00107   bool operator!=(const Expression &other) const {
00108     if (opcode != other.opcode)
00109       return true;
00110     else if (opcode == EMPTY || opcode == TOMBSTONE)
00111       return false;
00112     else if (type != other.type)
00113       return true;
00114     else if (firstVN != other.firstVN)
00115       return true;
00116     else if (secondVN != other.secondVN)
00117       return true;
00118     else if (thirdVN != other.thirdVN)
00119       return true;
00120     else {
00121       if (varargs.size() != other.varargs.size())
00122         return true;
00123       
00124       for (size_t i = 0; i < varargs.size(); ++i)
00125         if (varargs[i] != other.varargs[i])
00126           return true;
00127     
00128       return false;
00129     }
00130   }
00131 };
00132 
00133 }
00134 
00135 namespace {
00136   class VISIBILITY_HIDDEN ValueTable {
00137     private:
00138       DenseMap<Value*, uint32_t> valueNumbering;
00139       DenseMap<Expression, uint32_t> expressionNumbering;
00140   
00141       uint32_t nextValueNumber;
00142     
00143       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
00144       Expression::ExpressionOpcode getOpcode(CmpInst* C);
00145       Expression::ExpressionOpcode getOpcode(CastInst* C);
00146       Expression create_expression(BinaryOperator* BO);
00147       Expression create_expression(CmpInst* C);
00148       Expression create_expression(ShuffleVectorInst* V);
00149       Expression create_expression(ExtractElementInst* C);
00150       Expression create_expression(InsertElementInst* V);
00151       Expression create_expression(SelectInst* V);
00152       Expression create_expression(CastInst* C);
00153       Expression create_expression(GetElementPtrInst* G);
00154     public:
00155       ValueTable() { nextValueNumber = 1; }
00156       uint32_t lookup_or_add(Value* V);
00157       uint32_t lookup(Value* V) const;
00158       void add(Value* V, uint32_t num);
00159       void clear();
00160       void erase(Value* v);
00161       unsigned size();
00162   };
00163 }
00164 
00165 namespace llvm {
00166 template <> struct DenseMapInfo<Expression> {
00167   static inline Expression getEmptyKey() {
00168     return Expression(Expression::EMPTY);
00169   }
00170   
00171   static inline Expression getTombstoneKey() {
00172     return Expression(Expression::TOMBSTONE);
00173   }
00174   
00175   static unsigned getHashValue(const Expression e) {
00176     unsigned hash = e.opcode;
00177     
00178     hash = e.firstVN + hash * 37;
00179     hash = e.secondVN + hash * 37;
00180     hash = e.thirdVN + hash * 37;
00181     
00182     hash = ((unsigned)((uintptr_t)e.type >> 4) ^
00183             (unsigned)((uintptr_t)e.type >> 9)) +
00184            hash * 37;
00185     
00186     for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
00187          E = e.varargs.end(); I != E; ++I)
00188       hash = *I + hash * 37;
00189     
00190     return hash;
00191   }
00192   static bool isEqual(const Expression &LHS, const Expression &RHS) {
00193     return LHS == RHS;
00194   }
00195   static bool isPod() { return true; }
00196 };
00197 }
00198 
00199 //===----------------------------------------------------------------------===//
00200 //                     ValueTable Internal Functions
00201 //===----------------------------------------------------------------------===//
00202 Expression::ExpressionOpcode 
00203                              ValueTable::getOpcode(BinaryOperator* BO) {
00204   switch(BO->getOpcode()) {
00205     case Instruction::Add:
00206       return Expression::ADD;
00207     case Instruction::FAdd:
00208       return Expression::FADD;
00209     case Instruction::Sub:
00210       return Expression::SUB;
00211     case Instruction::FSub:
00212       return Expression::FSUB;
00213     case Instruction::Mul:
00214       return Expression::MUL;
00215     case Instruction::FMul:
00216       return Expression::FMUL;
00217     case Instruction::UDiv:
00218       return Expression::UDIV;
00219     case Instruction::SDiv:
00220       return Expression::SDIV;
00221     case Instruction::FDiv:
00222       return Expression::FDIV;
00223     case Instruction::URem:
00224       return Expression::UREM;
00225     case Instruction::SRem:
00226       return Expression::SREM;
00227     case Instruction::FRem:
00228       return Expression::FREM;
00229     case Instruction::Shl:
00230       return Expression::SHL;
00231     case Instruction::LShr:
00232       return Expression::LSHR;
00233     case Instruction::AShr:
00234       return Expression::ASHR;
00235     case Instruction::And:
00236       return Expression::AND;
00237     case Instruction::Or:
00238       return Expression::OR;
00239     case Instruction::Xor:
00240       return Expression::XOR;
00241     
00242     // THIS SHOULD NEVER HAPPEN
00243     default:
00244       llvm_unreachable("Binary operator with unknown opcode?");
00245       return Expression::ADD;
00246   }
00247 }
00248 
00249 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
00250   if (C->getOpcode() == Instruction::ICmp) {
00251     switch (C->getPredicate()) {
00252       case ICmpInst::ICMP_EQ:
00253         return Expression::ICMPEQ;
00254       case ICmpInst::ICMP_NE:
00255         return Expression::ICMPNE;
00256       case ICmpInst::ICMP_UGT:
00257         return Expression::ICMPUGT;
00258       case ICmpInst::ICMP_UGE:
00259         return Expression::ICMPUGE;
00260       case ICmpInst::ICMP_ULT:
00261         return Expression::ICMPULT;
00262       case ICmpInst::ICMP_ULE:
00263         return Expression::ICMPULE;
00264       case ICmpInst::ICMP_SGT:
00265         return Expression::ICMPSGT;
00266       case ICmpInst::ICMP_SGE:
00267         return Expression::ICMPSGE;
00268       case ICmpInst::ICMP_SLT:
00269         return Expression::ICMPSLT;
00270       case ICmpInst::ICMP_SLE:
00271         return Expression::ICMPSLE;
00272       
00273       // THIS SHOULD NEVER HAPPEN
00274       default:
00275         llvm_unreachable("Comparison with unknown predicate?");
00276         return Expression::ICMPEQ;
00277     }
00278   } else {
00279     switch (C->getPredicate()) {
00280       case FCmpInst::FCMP_OEQ:
00281         return Expression::FCMPOEQ;
00282       case FCmpInst::FCMP_OGT:
00283         return Expression::FCMPOGT;
00284       case FCmpInst::FCMP_OGE:
00285         return Expression::FCMPOGE;
00286       case FCmpInst::FCMP_OLT:
00287         return Expression::FCMPOLT;
00288       case FCmpInst::FCMP_OLE:
00289         return Expression::FCMPOLE;
00290       case FCmpInst::FCMP_ONE:
00291         return Expression::FCMPONE;
00292       case FCmpInst::FCMP_ORD:
00293         return Expression::FCMPORD;
00294       case FCmpInst::FCMP_UNO:
00295         return Expression::FCMPUNO;
00296       case FCmpInst::FCMP_UEQ:
00297         return Expression::FCMPUEQ;
00298       case FCmpInst::FCMP_UGT:
00299         return Expression::FCMPUGT;
00300       case FCmpInst::FCMP_UGE:
00301         return Expression::FCMPUGE;
00302       case FCmpInst::FCMP_ULT:
00303         return Expression::FCMPULT;
00304       case FCmpInst::FCMP_ULE:
00305         return Expression::FCMPULE;
00306       case FCmpInst::FCMP_UNE:
00307         return Expression::FCMPUNE;
00308       
00309       // THIS SHOULD NEVER HAPPEN
00310       default:
00311         llvm_unreachable("Comparison with unknown predicate?");
00312         return Expression::FCMPOEQ;
00313     }
00314   }
00315 }
00316 
00317 Expression::ExpressionOpcode 
00318                              ValueTable::getOpcode(CastInst* C) {
00319   switch(C->getOpcode()) {
00320     case Instruction::Trunc:
00321       return Expression::TRUNC;
00322     case Instruction::ZExt:
00323       return Expression::ZEXT;
00324     case Instruction::SExt:
00325       return Expression::SEXT;
00326     case Instruction::FPToUI:
00327       return Expression::FPTOUI;
00328     case Instruction::FPToSI:
00329       return Expression::FPTOSI;
00330     case Instruction::UIToFP:
00331       return Expression::UITOFP;
00332     case Instruction::SIToFP:
00333       return Expression::SITOFP;
00334     case Instruction::FPTrunc:
00335       return Expression::FPTRUNC;
00336     case Instruction::FPExt:
00337       return Expression::FPEXT;
00338     case Instruction::PtrToInt:
00339       return Expression::PTRTOINT;
00340     case Instruction::IntToPtr:
00341       return Expression::INTTOPTR;
00342     case Instruction::BitCast:
00343       return Expression::BITCAST;
00344     
00345     // THIS SHOULD NEVER HAPPEN
00346     default:
00347       llvm_unreachable("Cast operator with unknown opcode?");
00348       return Expression::BITCAST;
00349   }
00350 }
00351 
00352 Expression ValueTable::create_expression(BinaryOperator* BO) {
00353   Expression e;
00354     
00355   e.firstVN = lookup_or_add(BO->getOperand(0));
00356   e.secondVN = lookup_or_add(BO->getOperand(1));
00357   e.thirdVN = 0;
00358   e.type = BO->getType();
00359   e.opcode = getOpcode(BO);
00360   
00361   return e;
00362 }
00363 
00364 Expression ValueTable::create_expression(CmpInst* C) {
00365   Expression e;
00366     
00367   e.firstVN = lookup_or_add(C->getOperand(0));
00368   e.secondVN = lookup_or_add(C->getOperand(1));
00369   e.thirdVN = 0;
00370   e.type = C->getType();
00371   e.opcode = getOpcode(C);
00372   
00373   return e;
00374 }
00375 
00376 Expression ValueTable::create_expression(CastInst* C) {
00377   Expression e;
00378     
00379   e.firstVN = lookup_or_add(C->getOperand(0));
00380   e.secondVN = 0;
00381   e.thirdVN = 0;
00382   e.type = C->getType();
00383   e.opcode = getOpcode(C);
00384   
00385   return e;
00386 }
00387 
00388 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
00389   Expression e;
00390     
00391   e.firstVN = lookup_or_add(S->getOperand(0));
00392   e.secondVN = lookup_or_add(S->getOperand(1));
00393   e.thirdVN = lookup_or_add(S->getOperand(2));
00394   e.type = S->getType();
00395   e.opcode = Expression::SHUFFLE;
00396   
00397   return e;
00398 }
00399 
00400 Expression ValueTable::create_expression(ExtractElementInst* E) {
00401   Expression e;
00402     
00403   e.firstVN = lookup_or_add(E->getOperand(0));
00404   e.secondVN = lookup_or_add(E->getOperand(1));
00405   e.thirdVN = 0;
00406   e.type = E->getType();
00407   e.opcode = Expression::EXTRACT;
00408   
00409   return e;
00410 }
00411 
00412 Expression ValueTable::create_expression(InsertElementInst* I) {
00413   Expression e;
00414     
00415   e.firstVN = lookup_or_add(I->getOperand(0));
00416   e.secondVN = lookup_or_add(I->getOperand(1));
00417   e.thirdVN = lookup_or_add(I->getOperand(2));
00418   e.type = I->getType();
00419   e.opcode = Expression::INSERT;
00420   
00421   return e;
00422 }
00423 
00424 Expression ValueTable::create_expression(SelectInst* I) {
00425   Expression e;
00426     
00427   e.firstVN = lookup_or_add(I->getCondition());
00428   e.secondVN = lookup_or_add(I->getTrueValue());
00429   e.thirdVN = lookup_or_add(I->getFalseValue());
00430   e.type = I->getType();
00431   e.opcode = Expression::SELECT;
00432   
00433   return e;
00434 }
00435 
00436 Expression ValueTable::create_expression(GetElementPtrInst* G) {
00437   Expression e;
00438     
00439   e.firstVN = lookup_or_add(G->getPointerOperand());
00440   e.secondVN = 0;
00441   e.thirdVN = 0;
00442   e.type = G->getType();
00443   e.opcode = Expression::GEP;
00444   
00445   for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
00446        I != E; ++I)
00447     e.varargs.push_back(lookup_or_add(*I));
00448   
00449   return e;
00450 }
00451 
00452 //===----------------------------------------------------------------------===//
00453 //                     ValueTable External Functions
00454 //===----------------------------------------------------------------------===//
00455 
00456 /// lookup_or_add - Returns the value number for the specified value, assigning
00457 /// it a new number if it did not have one before.
00458 uint32_t ValueTable::lookup_or_add(Value* V) {
00459   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
00460   if (VI != valueNumbering.end())
00461     return VI->second;
00462   
00463   
00464   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
00465     Expression e = create_expression(BO);
00466     
00467     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
00468     if (EI != expressionNumbering.end()) {
00469       valueNumbering.insert(std::make_pair(V, EI->second));
00470       return EI->second;
00471     } else {
00472       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
00473       valueNumbering.insert(std::make_pair(V, nextValueNumber));
00474       
00475       return nextValueNumber++;
00476     }
00477   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
00478     Expression e = create_expression(C);
00479     
00480     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
00481     if (EI != expressionNumbering.end()) {
00482       valueNumbering.insert(std::make_pair(V, EI->second));
00483       return EI->second;
00484     } else {
00485       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
00486       valueNumbering.insert(std::make_pair(V, nextValueNumber));
00487       
00488       return nextValueNumber++;
00489     }
00490   } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
00491     Expression e = create_expression(U);
00492     
00493     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
00494     if (EI != expressionNumbering.end()) {
00495       valueNumbering.insert(std::make_pair(V, EI->second));
00496       return EI->second;
00497     } else {
00498       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
00499       valueNumbering.insert(std::make_pair(V, nextValueNumber));
00500       
00501       return nextValueNumber++;
00502     }
00503   } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
00504     Expression e = create_expression(U);
00505     
00506     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
00507     if (EI != expressionNumbering.end()) {
00508       valueNumbering.insert(std::make_pair(V, EI->second));
00509       return EI->second;
00510     } else {
00511       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
00512       valueNumbering.insert(std::make_pair(V, nextValueNumber));
00513       
00514       return nextValueNumber++;
00515     }
00516   } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
00517     Expression e = create_expression(U);
00518     
00519     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
00520     if (EI != expressionNumbering.end()) {
00521       valueNumbering.insert(std::make_pair(V, EI->second));
00522       return EI->second;
00523     } else {
00524       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
00525       valueNumbering.insert(std::make_pair(V, nextValueNumber));
00526       
00527       return nextValueNumber++;
00528     }
00529   } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
00530     Expression e = create_expression(U);
00531     
00532     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
00533     if (EI != expressionNumbering.end()) {
00534       valueNumbering.insert(std::make_pair(V, EI->second));
00535       return EI->second;
00536     } else {
00537       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
00538       valueNumbering.insert(std::make_pair(V, nextValueNumber));
00539       
00540       return nextValueNumber++;
00541     }
00542   } else if (CastInst* U = dyn_cast<CastInst>(V)) {
00543     Expression e = create_expression(U);
00544     
00545     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
00546     if (EI != expressionNumbering.end()) {
00547       valueNumbering.insert(std::make_pair(V, EI->second));
00548       return EI->second;
00549     } else {
00550       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
00551       valueNumbering.insert(std::make_pair(V, nextValueNumber));
00552       
00553       return nextValueNumber++;
00554     }
00555   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
00556     Expression e = create_expression(U);
00557     
00558     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
00559     if (EI != expressionNumbering.end()) {
00560       valueNumbering.insert(std::make_pair(V, EI->second));
00561       return EI->second;
00562     } else {
00563       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
00564       valueNumbering.insert(std::make_pair(V, nextValueNumber));
00565       
00566       return nextValueNumber++;
00567     }
00568   } else {
00569     valueNumbering.insert(std::make_pair(V, nextValueNumber));
00570     return nextValueNumber++;
00571   }
00572 }
00573 
00574 /// lookup - Returns the value number of the specified value. Fails if
00575 /// the value has not yet been numbered.
00576 uint32_t ValueTable::lookup(Value* V) const {
00577   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
00578   if (VI != valueNumbering.end())
00579     return VI->second;
00580   else
00581     llvm_unreachable("Value not numbered?");
00582   
00583   return 0;
00584 }
00585 
00586 /// add - Add the specified value with the given value number, removing
00587 /// its old number, if any
00588 void ValueTable::add(Value* V, uint32_t num) {
00589   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
00590   if (VI != valueNumbering.end())
00591     valueNumbering.erase(VI);
00592   valueNumbering.insert(std::make_pair(V, num));
00593 }
00594 
00595 /// clear - Remove all entries from the ValueTable
00596 void ValueTable::clear() {
00597   valueNumbering.clear();
00598   expressionNumbering.clear();
00599   nextValueNumber = 1;
00600 }
00601 
00602 /// erase - Remove a value from the value numbering
00603 void ValueTable::erase(Value* V) {
00604   valueNumbering.erase(V);
00605 }
00606 
00607 /// size - Return the number of assigned value numbers
00608 unsigned ValueTable::size() {
00609   // NOTE: zero is never assigned
00610   return nextValueNumber;
00611 }
00612 
00613 namespace {
00614 
00615 //===----------------------------------------------------------------------===//
00616 //                       ValueNumberedSet Class
00617 //===----------------------------------------------------------------------===//
00618 
00619 class ValueNumberedSet {
00620   private:
00621     SmallPtrSet<Value*, 8> contents;
00622     BitVector numbers;
00623   public:
00624     ValueNumberedSet() { numbers.resize(1); }
00625     ValueNumberedSet(const ValueNumberedSet& other) {
00626       numbers = other.numbers;
00627       contents = other.contents;
00628     }
00629     
00630     typedef SmallPtrSet<Value*, 8>::iterator iterator;
00631     
00632     iterator begin() { return contents.begin(); }
00633     iterator end() { return contents.end(); }
00634     
00635     bool insert(Value* v) { return contents.insert(v); }
00636     void insert(iterator I, iterator E) { contents.insert(I, E); }
00637     void erase(Value* v) { contents.erase(v); }
00638     unsigned count(Value* v) { return contents.count(v); }
00639     size_t size() { return contents.size(); }
00640     
00641     void set(unsigned i)  {
00642       if (i >= numbers.size())
00643         numbers.resize(i+1);
00644       
00645       numbers.set(i);
00646     }
00647     
00648     void operator=(const ValueNumberedSet& other) {
00649       contents = other.contents;
00650       numbers = other.numbers;
00651     }
00652     
00653     void reset(unsigned i)  {
00654       if (i < numbers.size())
00655         numbers.reset(i);
00656     }
00657     
00658     bool test(unsigned i)  {
00659       if (i >= numbers.size())
00660         return false;
00661       
00662       return numbers.test(i);
00663     }
00664     
00665     void clear() {
00666       contents.clear();
00667       numbers.clear();
00668     }
00669 };
00670 
00671 }
00672 
00673 //===----------------------------------------------------------------------===//
00674 //                         GVNPRE Pass
00675 //===----------------------------------------------------------------------===//
00676 
00677 namespace {
00678 
00679   class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
00680     bool runOnFunction(Function &F);
00681   public:
00682     static char ID; // Pass identification, replacement for typeid
00683     GVNPRE() : FunctionPass(&ID) {}
00684 
00685   private:
00686     ValueTable VN;
00687     SmallVector<Instruction*, 8> createdExpressions;
00688     
00689     DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
00690     DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
00691     DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
00692     
00693     // This transformation requires dominator postdominator info
00694     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00695       AU.setPreservesCFG();
00696       AU.addRequiredID(BreakCriticalEdgesID);
00697       AU.addRequired<UnifyFunctionExitNodes>();
00698       AU.addRequired<DominatorTree>();
00699     }
00700   
00701     // Helper fuctions
00702     // FIXME: eliminate or document these better
00703     void dump(ValueNumberedSet& s) const ;
00704     void clean(ValueNumberedSet& set) ;
00705     Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
00706     Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
00707     void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
00708                            BasicBlock* succ, ValueNumberedSet& out) ;
00709     
00710     void topo_sort(ValueNumberedSet& set,
00711                    SmallVector<Value*, 8>& vec) ;
00712     
00713     void cleanup() ;
00714     bool elimination() ;
00715     
00716     void val_insert(ValueNumberedSet& s, Value* v) ;
00717     void val_replace(ValueNumberedSet& s, Value* v) ;
00718     bool dependsOnInvoke(Value* V) ;
00719     void buildsets_availout(BasicBlock::iterator I,
00720                             ValueNumberedSet& currAvail,
00721                             ValueNumberedSet& currPhis,
00722                             ValueNumberedSet& currExps,
00723                             SmallPtrSet<Value*, 16>& currTemps);
00724     bool buildsets_anticout(BasicBlock* BB,
00725                             ValueNumberedSet& anticOut,
00726                             SmallPtrSet<BasicBlock*, 8>& visited);
00727     unsigned buildsets_anticin(BasicBlock* BB,
00728                            ValueNumberedSet& anticOut,
00729                            ValueNumberedSet& currExps,
00730                            SmallPtrSet<Value*, 16>& currTemps,
00731                            SmallPtrSet<BasicBlock*, 8>& visited);
00732     void buildsets(Function& F) ;
00733     
00734     void insertion_pre(Value* e, BasicBlock* BB,
00735                        DenseMap<BasicBlock*, Value*>& avail,
00736                        std::map<BasicBlock*,ValueNumberedSet>& new_set);
00737     unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
00738                                   df_iterator<DomTreeNode*>& D,
00739                       std::map<BasicBlock*, ValueNumberedSet>& new_set);
00740     bool insertion(Function& F) ;
00741   
00742   };
00743   
00744   char GVNPRE::ID = 0;
00745   
00746 }
00747 
00748 // createGVNPREPass - The public interface to this file...
00749 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
00750 
00751 static RegisterPass<GVNPRE> X("gvnpre",
00752                       "Global Value Numbering/Partial Redundancy Elimination");
00753 
00754 
00755 STATISTIC(NumInsertedVals, "Number of values inserted");
00756 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
00757 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
00758 
00759 /// find_leader - Given a set and a value number, return the first
00760 /// element of the set with that value number, or 0 if no such element
00761 /// is present
00762 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
00763   if (!vals.test(v))
00764     return 0;
00765   
00766   for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
00767        I != E; ++I)
00768     if (v == VN.lookup(*I))
00769       return *I;
00770   
00771   llvm_unreachable("No leader found, but present bit is set?");
00772   return 0;
00773 }
00774 
00775 /// val_insert - Insert a value into a set only if there is not a value
00776 /// with the same value number already in the set
00777 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
00778   uint32_t num = VN.lookup(v);
00779   if (!s.test(num))
00780     s.insert(v);
00781 }
00782 
00783 /// val_replace - Insert a value into a set, replacing any values already in
00784 /// the set that have the same value number
00785 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
00786   if (s.count(v)) return;
00787   
00788   uint32_t num = VN.lookup(v);
00789   Value* leader = find_leader(s, num);
00790   if (leader != 0)
00791     s.erase(leader);
00792   s.insert(v);
00793   s.set(num);
00794 }
00795 
00796 /// phi_translate - Given a value, its parent block, and a predecessor of its
00797 /// parent, translate the value into legal for the predecessor block.  This 
00798 /// means translating its operands (and recursively, their operands) through
00799 /// any phi nodes in the parent into values available in the predecessor
00800 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
00801   if (V == 0)
00802     return 0;
00803     
00804   LLVMContext &Context = V->getContext();
00805   
00806   // Unary Operations
00807   if (CastInst* U = dyn_cast<CastInst>(V)) {
00808     Value* newOp1 = 0;
00809     if (isa<Instruction>(U->getOperand(0)))
00810       newOp1 = phi_translate(U->getOperand(0), pred, succ);
00811     else
00812       newOp1 = U->getOperand(0);
00813     
00814     if (newOp1 == 0)
00815       return 0;
00816     
00817     if (newOp1 != U->getOperand(0)) {
00818       Instruction* newVal = 0;
00819       if (CastInst* C = dyn_cast<CastInst>(U))
00820         newVal = CastInst::Create(C->getOpcode(),
00821                                   newOp1, C->getType(),
00822                                   C->getName()+".expr");
00823       
00824       uint32_t v = VN.lookup_or_add(newVal);
00825       
00826       Value* leader = find_leader(availableOut[pred], v);
00827       if (leader == 0) {
00828         createdExpressions.push_back(newVal);
00829         return newVal;
00830       } else {
00831         VN.erase(newVal);
00832         delete newVal;
00833         return leader;
00834       }
00835     }
00836   
00837   // Binary Operations
00838   } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) || 
00839       isa<ExtractElementInst>(V)) {
00840     User* U = cast<User>(V);
00841     
00842     Value* newOp1 = 0;
00843     if (isa<Instruction>(U->getOperand(0)))
00844       newOp1 = phi_translate(U->getOperand(0), pred, succ);
00845     else
00846       newOp1 = U->getOperand(0);
00847     
00848     if (newOp1 == 0)
00849       return 0;
00850     
00851     Value* newOp2 = 0;
00852     if (isa<Instruction>(U->getOperand(1)))
00853       newOp2 = phi_translate(U->getOperand(1), pred, succ);
00854     else
00855       newOp2 = U->getOperand(1);
00856     
00857     if (newOp2 == 0)
00858       return 0;
00859     
00860     if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
00861       Instruction* newVal = 0;
00862       if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
00863         newVal = BinaryOperator::Create(BO->getOpcode(),
00864                                         newOp1, newOp2,
00865                                         BO->getName()+".expr");
00866       else if (CmpInst* C = dyn_cast<CmpInst>(U))
00867         newVal = CmpInst::Create(Context, C->getOpcode(),
00868                                  C->getPredicate(),
00869                                  newOp1, newOp2,
00870                                  C->getName()+".expr");
00871       else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
00872         newVal = ExtractElementInst::Create(newOp1, newOp2, 
00873                                             E->getName()+".expr");
00874       
00875       uint32_t v = VN.lookup_or_add(newVal);
00876       
00877       Value* leader = find_leader(availableOut[pred], v);
00878       if (leader == 0) {
00879         createdExpressions.push_back(newVal);
00880         return newVal;
00881       } else {
00882         VN.erase(newVal);
00883         delete newVal;
00884         return leader;
00885       }
00886     }
00887   
00888   // Ternary Operations
00889   } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
00890              isa<SelectInst>(V)) {
00891     User* U = cast<User>(V);
00892     
00893     Value* newOp1 = 0;
00894     if (isa<Instruction>(U->getOperand(0)))
00895       newOp1 = phi_translate(U->getOperand(0), pred, succ);
00896     else
00897       newOp1 = U->getOperand(0);
00898     
00899     if (newOp1 == 0)
00900       return 0;
00901     
00902     Value* newOp2 = 0;
00903     if (isa<Instruction>(U->getOperand(1)))
00904       newOp2 = phi_translate(U->getOperand(1), pred, succ);
00905     else
00906       newOp2 = U->getOperand(1);
00907     
00908     if (newOp2 == 0)
00909       return 0;
00910     
00911     Value* newOp3 = 0;
00912     if (isa<Instruction>(U->getOperand(2)))
00913       newOp3 = phi_translate(U->getOperand(2), pred, succ);
00914     else
00915       newOp3 = U->getOperand(2);
00916     
00917     if (newOp3 == 0)
00918       return 0;
00919     
00920     if (newOp1 != U->getOperand(0) ||
00921         newOp2 != U->getOperand(1) ||
00922         newOp3 != U->getOperand(2)) {
00923       Instruction* newVal = 0;
00924       if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
00925         newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
00926                                        S->getName() + ".expr");
00927       else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
00928         newVal = InsertElementInst::Create(newOp1, newOp2, newOp3,
00929                                            I->getName() + ".expr");
00930       else if (SelectInst* I = dyn_cast<SelectInst>(U))
00931         newVal = SelectInst::Create(newOp1, newOp2, newOp3,
00932                                     I->getName() + ".expr");
00933       
00934       uint32_t v = VN.lookup_or_add(newVal);
00935       
00936       Value* leader = find_leader(availableOut[pred], v);
00937       if (leader == 0) {
00938         createdExpressions.push_back(newVal);
00939         return newVal;
00940       } else {
00941         VN.erase(newVal);
00942         delete newVal;
00943         return leader;
00944       }
00945     }
00946   
00947   // Varargs operators
00948   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
00949     Value* newOp1 = 0;
00950     if (isa<Instruction>(U->getPointerOperand()))
00951       newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
00952     else
00953       newOp1 = U->getPointerOperand();
00954     
00955     if (newOp1 == 0)
00956       return 0;
00957     
00958     bool changed_idx = false;
00959     SmallVector<Value*, 4> newIdx;
00960     for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
00961          I != E; ++I)
00962       if (isa<Instruction>(*I)) {
00963         Value* newVal = phi_translate(*I, pred, succ);
00964         newIdx.push_back(newVal);
00965         if (newVal != *I)
00966           changed_idx = true;
00967       } else {
00968         newIdx.push_back(*I);
00969       }
00970     
00971     if (newOp1 != U->getPointerOperand() || changed_idx) {
00972       Instruction* newVal =
00973           GetElementPtrInst::Create(newOp1,
00974                                     newIdx.begin(), newIdx.end(),
00975                                     U->getName()+".expr");
00976       
00977       uint32_t v = VN.lookup_or_add(newVal);
00978       
00979       Value* leader = find_leader(availableOut[pred], v);
00980       if (leader == 0) {
00981         createdExpressions.push_back(newVal);
00982         return newVal;
00983       } else {
00984         VN.erase(newVal);
00985         delete newVal;
00986         return leader;
00987       }
00988     }
00989   
00990   // PHI Nodes
00991   } else if (PHINode* P = dyn_cast<PHINode>(V)) {
00992     if (P->getParent() == succ)
00993       return P->getIncomingValueForBlock(pred);
00994   }
00995   
00996   return V;
00997 }
00998 
00999 /// phi_translate_set - Perform phi translation on every element of a set
01000 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
01001                               BasicBlock* pred, BasicBlock* succ,
01002                               ValueNumberedSet& out) {
01003   for (ValueNumberedSet::iterator I = anticIn.begin(),
01004        E = anticIn.end(); I != E; ++I) {
01005     Value* V = phi_translate(*I, pred, succ);
01006     if (V != 0 && !out.test(VN.lookup_or_add(V))) {
01007       out.insert(V);
01008       out.set(VN.lookup(V));
01009     }
01010   }
01011 }
01012 
01013 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of 
01014 /// whose inputs is an invoke instruction.  If this is true, we cannot safely
01015 /// PRE the instruction or anything that depends on it.
01016 bool GVNPRE::dependsOnInvoke(Value* V) {
01017   if (PHINode* p = dyn_cast<PHINode>(V)) {
01018     for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
01019       if (isa<InvokeInst>(*I))
01020         return true;
01021     return false;
01022   } else {
01023     return false;
01024   }
01025 }
01026 
01027 /// clean - Remove all non-opaque values from the set whose operands are not
01028 /// themselves in the set, as well as all values that depend on invokes (see 
01029 /// above)
01030 void GVNPRE::clean(ValueNumberedSet& set) {
01031   SmallVector<Value*, 8> worklist;
01032   worklist.reserve(set.size());
01033   topo_sort(set, worklist);
01034   
01035   for (unsigned i = 0; i < worklist.size(); ++i) {
01036     Value* v = worklist[i];
01037     
01038     // Handle unary ops
01039     if (CastInst* U = dyn_cast<CastInst>(v)) {
01040       bool lhsValid = !isa<Instruction>(U->getOperand(0));
01041       lhsValid |= set.test(VN.lookup(U->getOperand(0)));
01042       if (lhsValid)
01043         lhsValid = !dependsOnInvoke(U->getOperand(0));
01044       
01045       if (!lhsValid) {
01046         set.erase(U);
01047         set.reset(VN.lookup(U));
01048       }
01049     
01050     // Handle binary ops
01051     } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
01052         isa<ExtractElementInst>(v)) {
01053       User* U = cast<User>(v);
01054       
01055       bool lhsValid = !isa<Instruction>(U->getOperand(0));
01056       lhsValid |= set.test(VN.lookup(U->getOperand(0)));
01057       if (lhsValid)
01058         lhsValid = !dependsOnInvoke(U->getOperand(0));
01059     
01060       bool rhsValid = !isa<Instruction>(U->getOperand(1));
01061       rhsValid |= set.test(VN.lookup(U->getOperand(1)));
01062       if (rhsValid)
01063         rhsValid = !dependsOnInvoke(U->getOperand(1));
01064       
01065       if (!lhsValid || !rhsValid) {
01066         set.erase(U);
01067         set.reset(VN.lookup(U));
01068       }
01069     
01070     // Handle ternary ops
01071     } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
01072                isa<SelectInst>(v)) {
01073       User* U = cast<User>(v);
01074     
01075       bool lhsValid = !isa<Instruction>(U->getOperand(0));
01076       lhsValid |= set.test(VN.lookup(U->getOperand(0)));
01077       if (lhsValid)
01078         lhsValid = !dependsOnInvoke(U->getOperand(0));
01079       
01080       bool rhsValid = !isa<Instruction>(U->getOperand(1));
01081       rhsValid |= set.test(VN.lookup(U->getOperand(1)));
01082       if (rhsValid)
01083         rhsValid = !dependsOnInvoke(U->getOperand(1));
01084       
01085       bool thirdValid = !isa<Instruction>(U->getOperand(2));
01086       thirdValid |= set.test(VN.lookup(U->getOperand(2)));
01087       if (thirdValid)
01088         thirdValid = !dependsOnInvoke(U->getOperand(2));
01089     
01090       if (!lhsValid || !rhsValid || !thirdValid) {
01091         set.erase(U);
01092         set.reset(VN.lookup(U));
01093       }
01094     
01095     // Handle varargs ops
01096     } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
01097       bool ptrValid = !isa<Instruction>(U->getPointerOperand());
01098       ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
01099       if (ptrValid)
01100         ptrValid = !dependsOnInvoke(U->getPointerOperand());
01101       
01102       bool varValid = true;
01103       for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
01104            I != E; ++I)
01105         if (varValid) {
01106           varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
01107           varValid &= !dependsOnInvoke(*I);
01108         }
01109     
01110       if (!ptrValid || !varValid) {
01111         set.erase(U);
01112         set.reset(VN.lookup(U));
01113       }
01114     }
01115   }
01116 }
01117 
01118 /// topo_sort - Given a set of values, sort them by topological
01119 /// order into the provided vector.
01120 void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
01121   SmallPtrSet<Value*, 16> visited;
01122   SmallVector<Value*, 8> stack;
01123   for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
01124        I != E; ++I) {
01125     if (visited.count(*I) == 0)
01126       stack.push_back(*I);
01127     
01128     while (!stack.empty()) {
01129       Value* e = stack.back();
01130       
01131       // Handle unary ops
01132       if (CastInst* U = dyn_cast<CastInst>(e)) {
01133         Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
01134     
01135         if (l != 0 && isa<Instruction>(l) &&
01136             visited.count(l) == 0)
01137           stack.push_back(l);
01138         else {
01139           vec.push_back(e);
01140           visited.insert(e);
01141           stack.pop_back();
01142         }
01143       
01144       // Handle binary ops
01145       } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
01146           isa<ExtractElementInst>(e)) {
01147         User* U = cast<User>(e);
01148         Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
01149         Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
01150     
01151         if (l != 0 && isa<Instruction>(l) &&
01152             visited.count(l) == 0)
01153           stack.push_back(l);
01154         else if (r != 0 && isa<Instruction>(r) &&
01155                  visited.count(r) == 0)
01156           stack.push_back(r);
01157         else {
01158           vec.push_back(e);
01159           visited.insert(e);
01160           stack.pop_back();
01161         }
01162       
01163       // Handle ternary ops
01164       } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
01165                  isa<SelectInst>(e)) {
01166         User* U = cast<User>(e);
01167         Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
01168         Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
01169         Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
01170       
01171         if (l != 0 && isa<Instruction>(l) &&
01172             visited.count(l) == 0)
01173           stack.push_back(l);
01174         else if (r != 0 && isa<Instruction>(r) &&
01175                  visited.count(r) == 0)
01176           stack.push_back(r);
01177         else if (m != 0 && isa<Instruction>(m) &&
01178                  visited.count(m) == 0)
01179           stack.push_back(m);
01180         else {
01181           vec.push_back(e);
01182           visited.insert(e);
01183           stack.pop_back();
01184         }
01185       
01186       // Handle vararg ops
01187       } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
01188         Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
01189         
01190         if (p != 0 && isa<Instruction>(p) &&
01191             visited.count(p) == 0)
01192           stack.push_back(p);
01193         else {
01194           bool push_va = false;
01195           for (GetElementPtrInst::op_iterator I = U->idx_begin(),
01196                E = U->idx_end(); I != E; ++I) {
01197             Value * v = find_leader(set, VN.lookup(*I));
01198             if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
01199               stack.push_back(v);
01200               push_va = true;
01201             }
01202           }
01203           
01204           if (!push_va) {
01205             vec.push_back(e);
01206             visited.insert(e);
01207             stack.pop_back();
01208           }
01209         }
01210       
01211       // Handle opaque ops
01212       } else {
01213         visited.insert(e);
01214         vec.push_back(e);
01215         stack.pop_back();
01216       }
01217     }
01218     
01219     stack.clear();
01220   }
01221 }
01222 
01223 /// dump - Dump a set of values to standard error
01224 void GVNPRE::dump(ValueNumberedSet& s) const {
01225   DOUT << "{ ";
01226   for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
01227        I != E; ++I) {
01228     DOUT << "" << VN.lookup(*I) << ": ";
01229     DEBUG((*I)->dump());
01230   }
01231   DOUT << "}\n\n";
01232 }
01233 
01234 /// elimination - Phase 3 of the main algorithm.  Perform full redundancy 
01235 /// elimination by walking the dominator tree and removing any instruction that 
01236 /// is dominated by another instruction with the same value number.
01237 bool GVNPRE::elimination() {
01238   bool changed_function = false;
01239   
01240   SmallVector<std::pair<Instruction*, Value*>, 8> replace;
01241   SmallVector<Instruction*, 8> erase;
01242   
01243   DominatorTree& DT = getAnalysis<DominatorTree>();
01244   
01245   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
01246          E = df_end(DT.getRootNode()); DI != E; ++DI) {
01247     BasicBlock* BB = DI->getBlock();
01248     
01249     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
01250          BI != BE; ++BI) {
01251 
01252       if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
01253           isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
01254           isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
01255           isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
01256         
01257         if (availableOut[BB].test(VN.lookup(BI)) &&
01258             !availableOut[BB].count(BI)) {
01259           Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
01260           if (Instruction* Instr = dyn_cast<Instruction>(leader))
01261             if (Instr->getParent() != 0 && Instr != BI) {
01262               replace.push_back(std::make_pair(BI, leader));
01263               erase.push_back(BI);
01264               ++NumEliminated;
01265             }
01266         }
01267       }
01268     }
01269   }
01270   
01271   while (!replace.empty()) {
01272     std::pair<Instruction*, Value*> rep = replace.back();
01273     replace.pop_back();
01274     rep.first->replaceAllUsesWith(rep.second);
01275     changed_function = true;
01276   }
01277     
01278   for (SmallVector<Instruction*, 8>::iterator I = erase.begin(),
01279        E = erase.end(); I != E; ++I)
01280      (*I)->eraseFromParent();
01281   
01282   return changed_function;
01283 }
01284 
01285 /// cleanup - Delete any extraneous values that were created to represent
01286 /// expressions without leaders.
01287 void GVNPRE::cleanup() {
01288   while (!createdExpressions.empty()) {
01289     Instruction* I = createdExpressions.back();
01290     createdExpressions.pop_back();
01291     
01292     delete I;
01293   }
01294 }
01295 
01296 /// buildsets_availout - When calculating availability, handle an instruction
01297 /// by inserting it into the appropriate sets
01298 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
01299                                 ValueNumberedSet& currAvail,
01300                                 ValueNumberedSet& currPhis,
01301                                 ValueNumberedSet& currExps,
01302                                 SmallPtrSet<Value*, 16>& currTemps) {
01303   // Handle PHI nodes
01304   if (PHINode* p = dyn_cast<PHINode>(I)) {
01305     unsigned num = VN.lookup_or_add(p);
01306     
01307     currPhis.insert(p);
01308     currPhis.set(num);
01309   
01310   // Handle unary ops
01311   } else if (CastInst* U = dyn_cast<CastInst>(I)) {
01312     Value* leftValue = U->getOperand(0);
01313     
01314     unsigned num = VN.lookup_or_add(U);
01315       
01316     if (isa<Instruction>(leftValue))
01317       if (!currExps.test(VN.lookup(leftValue))) {
01318         currExps.insert(leftValue);
01319         currExps.set(VN.lookup(leftValue));
01320       }
01321     
01322     if (!currExps.test(num)) {
01323       currExps.insert(U);
01324       currExps.set(num);
01325     }
01326   
01327   // Handle binary ops
01328   } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
01329              isa<ExtractElementInst>(I)) {
01330     User* U = cast<User>(I);
01331     Value* leftValue = U->getOperand(0);
01332     Value* rightValue = U->getOperand(1);
01333     
01334     unsigned num = VN.lookup_or_add(U);
01335       
01336     if (isa<Instruction>(leftValue))
01337       if (!currExps.test(VN.lookup(leftValue))) {
01338         currExps.insert(leftValue);
01339         currExps.set(VN.lookup(leftValue));
01340       }
01341     
01342     if (isa<Instruction>(rightValue))
01343       if (!currExps.test(VN.lookup(rightValue))) {
01344         currExps.insert(rightValue);
01345         currExps.set(VN.lookup(rightValue));
01346       }
01347     
01348     if (!currExps.test(num)) {
01349       currExps.insert(U);
01350       currExps.set(num);
01351     }
01352     
01353   // Handle ternary ops
01354   } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
01355              isa<SelectInst>(I)) {
01356     User* U = cast<User>(I);
01357     Value* leftValue = U->getOperand(0);
01358     Value* rightValue = U->getOperand(1);
01359     Value* thirdValue = U->getOperand(2);
01360       
01361     VN.lookup_or_add(U);
01362     
01363     unsigned num = VN.lookup_or_add(U);
01364     
01365     if (isa<Instruction>(leftValue))
01366       if (!currExps.test(VN.lookup(leftValue))) {
01367         currExps.insert(leftValue);
01368         currExps.set(VN.lookup(leftValue));
01369       }
01370     if (isa<Instruction>(rightValue))
01371       if (!currExps.test(VN.lookup(rightValue))) {
01372         currExps.insert(rightValue);
01373         currExps.set(VN.lookup(rightValue));
01374       }
01375     if (isa<Instruction>(thirdValue))
01376       if (!currExps.test(VN.lookup(thirdValue))) {
01377         currExps.insert(thirdValue);
01378         currExps.set(VN.lookup(thirdValue));
01379       }
01380     
01381     if (!currExps.test(num)) {
01382       currExps.insert(U);
01383       currExps.set(num);
01384     }
01385     
01386   // Handle vararg ops
01387   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
01388     Value* ptrValue = U->getPointerOperand();
01389       
01390     VN.lookup_or_add(U);
01391     
01392     unsigned num = VN.lookup_or_add(U);
01393     
01394     if (isa<Instruction>(ptrValue))
01395       if (!currExps.test(VN.lookup(ptrValue))) {
01396         currExps.insert(ptrValue);
01397         currExps.set(VN.lookup(ptrValue));
01398       }
01399     
01400     for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
01401          OI != OE; ++OI)
01402       if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
01403         currExps.insert(*OI);
01404         currExps.set(VN.lookup(*OI));
01405       }
01406     
01407     if (!currExps.test(VN.lookup(U))) {
01408       currExps.insert(U);
01409       currExps.set(num);
01410     }
01411     
01412   // Handle opaque ops
01413   } else if (!I->isTerminator()){
01414     VN.lookup_or_add(I);
01415     
01416     currTemps.insert(I);
01417   }
01418     
01419   if (!I->isTerminator())
01420     if (!currAvail.test(VN.lookup(I))) {
01421       currAvail.insert(I);
01422       currAvail.set(VN.lookup(I));
01423     }
01424 }
01425 
01426 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
01427 /// set as a function of the ANTIC_IN set of the block's predecessors
01428 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
01429                                 ValueNumberedSet& anticOut,
01430                                 SmallPtrSet<BasicBlock*, 8>& visited) {
01431   if (BB->getTerminator()->getNumSuccessors() == 1) {
01432     if (BB->getTerminator()->getSuccessor(0) != BB &&
01433         visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
01434       return true;
01435     }
01436     else {
01437       phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
01438                         BB,  BB->getTerminator()->getSuccessor(0), anticOut);
01439     }
01440   } else if (BB->getTerminator()->getNumSuccessors() > 1) {
01441     BasicBlock* first = BB->getTerminator()->getSuccessor(0);
01442     for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
01443          E = anticipatedIn[first].end(); I != E; ++I) {
01444       anticOut.insert(*I);
01445       anticOut.set(VN.lookup(*I));
01446     }
01447     
01448     for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
01449       BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
01450       ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
01451       
01452       SmallVector<Value*, 16> temp;
01453       
01454       for (ValueNumberedSet::iterator I = anticOut.begin(),
01455            E = anticOut.end(); I != E; ++I)
01456         if (!succAnticIn.test(VN.lookup(*I)))
01457           temp.push_back(*I);
01458 
01459       for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
01460            I != E; ++I) {
01461         anticOut.erase(*I);
01462         anticOut.reset(VN.lookup(*I));
01463       }
01464     }
01465   }
01466   
01467   return false;
01468 }
01469 
01470 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
01471 /// each block.  ANTIC_IN is then a function of ANTIC_OUT and the GEN
01472 /// sets populated in buildsets_availout
01473 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
01474                                ValueNumberedSet& anticOut,
01475                                ValueNumberedSet& currExps,
01476                                SmallPtrSet<Value*, 16>& currTemps,
01477                                SmallPtrSet<BasicBlock*, 8>& visited) {
01478   ValueNumberedSet& anticIn = anticipatedIn[BB];
01479   unsigned old = anticIn.size();
01480       
01481   bool defer = buildsets_anticout(BB, anticOut, visited);
01482   if (defer)
01483     return 0;
01484   
01485   anticIn.clear();
01486   
01487   for (ValueNumberedSet::iterator I = anticOut.begin(),
01488        E = anticOut.end(); I != E; ++I) {
01489     anticIn.insert(*I);
01490     anticIn.set(VN.lookup(*I));
01491   }
01492   for (ValueNumberedSet::iterator I = currExps.begin(),
01493        E = currExps.end(); I != E; ++I) {
01494     if (!anticIn.test(VN.lookup(*I))) {
01495       anticIn.insert(*I);
01496       anticIn.set(VN.lookup(*I));
01497     }
01498   } 
01499   
01500   for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
01501        E = currTemps.end(); I != E; ++I) {
01502     anticIn.erase(*I);
01503     anticIn.reset(VN.lookup(*I));
01504   }
01505   
01506   clean(anticIn);
01507   anticOut.clear();
01508   
01509   if (old != anticIn.size())
01510     return 2;
01511   else
01512     return 1;
01513 }
01514 
01515 /// buildsets - Phase 1 of the main algorithm.  Construct the AVAIL_OUT
01516 /// and the ANTIC_IN sets.
01517 void GVNPRE::buildsets(Function& F) {
01518   DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
01519   DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
01520 
01521   DominatorTree &DT = getAnalysis<DominatorTree>();   
01522   
01523   // Phase 1, Part 1: calculate AVAIL_OUT
01524   
01525   // Top-down walk of the dominator tree
01526   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
01527          E = df_end(DT.getRootNode()); DI != E; ++DI) {
01528     
01529     // Get the sets to update for this block
01530     ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
01531     ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
01532     SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
01533     ValueNumberedSet& currAvail = availableOut[DI->getBlock()];     
01534     
01535     BasicBlock* BB = DI->getBlock();
01536   
01537     // A block inherits AVAIL_OUT from its dominator
01538     if (DI->getIDom() != 0)
01539       currAvail = availableOut[DI->getIDom()->getBlock()];
01540 
01541     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
01542          BI != BE; ++BI)
01543       buildsets_availout(BI, currAvail, currPhis, currExps,
01544                          currTemps);
01545       
01546   }
01547 
01548   // Phase 1, Part 2: calculate ANTIC_IN
01549   
01550   SmallPtrSet<BasicBlock*, 8> visited;
01551   SmallPtrSet<BasicBlock*, 4> block_changed;
01552   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
01553     block_changed.insert(FI);
01554   
01555   bool changed = true;
01556   unsigned iterations = 0;
01557   
01558   while (changed) {
01559     changed = false;
01560     ValueNumberedSet anticOut;
01561     
01562     // Postorder walk of the CFG
01563     for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
01564          BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
01565       BasicBlock* BB = *BBI;
01566       
01567       if (block_changed.count(BB) != 0) {
01568         unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
01569                                          generatedTemporaries[BB], visited);
01570       
01571         if (ret == 0) {
01572           changed = true;
01573           continue;
01574         } else {
01575           visited.insert(BB);
01576         
01577           if (ret == 2)
01578            for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
01579                  PI != PE; ++PI) {
01580               block_changed.insert(*PI);
01581            }
01582           else
01583             block_changed.erase(BB);
01584         
01585           changed |= (ret == 2);
01586         }
01587       }
01588     }
01589     
01590     iterations++;
01591   }
01592 }
01593 
01594 /// insertion_pre - When a partial redundancy has been identified, eliminate it
01595 /// by inserting appropriate values into the predecessors and a phi node in
01596 /// the main block
01597 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
01598                            DenseMap<BasicBlock*, Value*>& avail,
01599                     std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
01600   LLVMContext &Context = e->getContext();
01601   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
01602     Value* e2 = avail[*PI];
01603     if (!availableOut[*PI].test(VN.lookup(e2))) {
01604       User* U = cast<User>(e2);
01605       
01606       Value* s1 = 0;
01607       if (isa<BinaryOperator>(U->getOperand(0)) || 
01608           isa<CmpInst>(U->getOperand(0)) ||
01609           isa<ShuffleVectorInst>(U->getOperand(0)) ||
01610           isa<ExtractElementInst>(U->getOperand(0)) ||
01611           isa<InsertElementInst>(U->getOperand(0)) ||
01612           isa<SelectInst>(U->getOperand(0)) ||
01613           isa<CastInst>(U->getOperand(0)) ||
01614           isa<GetElementPtrInst>(U->getOperand(0)))
01615         s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
01616       else
01617         s1 = U->getOperand(0);
01618       
01619       Value* s2 = 0;
01620       
01621       if (isa<BinaryOperator>(U) || 
01622           isa<CmpInst>(U) ||
01623           isa<ShuffleVectorInst>(U) ||
01624           isa<ExtractElementInst>(U) ||
01625           isa<InsertElementInst>(U) ||
01626           isa<SelectInst>(U)) {
01627         if (isa<BinaryOperator>(U->getOperand(1)) || 
01628             isa<CmpInst>(U->getOperand(1)) ||
01629             isa<ShuffleVectorInst>(U->getOperand(1)) ||
01630             isa<ExtractElementInst>(U->getOperand(1)) ||
01631             isa<InsertElementInst>(U->getOperand(1)) ||
01632             isa<SelectInst>(U->getOperand(1)) ||
01633             isa<CastInst>(U->getOperand(1)) ||
01634             isa<GetElementPtrInst>(U->getOperand(1))) {
01635           s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
01636         } else {
01637           s2 = U->getOperand(1);
01638         }
01639       }
01640       
01641       // Ternary Operators
01642       Value* s3 = 0;
01643       if (isa<ShuffleVectorInst>(U) ||
01644           isa<InsertElementInst>(U) ||
01645           isa<SelectInst>(U)) {
01646         if (isa<BinaryOperator>(U->getOperand(2)) || 
01647             isa<CmpInst>(U->getOperand(2)) ||
01648             isa<ShuffleVectorInst>(U->getOperand(2)) ||
01649             isa<ExtractElementInst>(U->getOperand(2)) ||
01650             isa<InsertElementInst>(U->getOperand(2)) ||
01651             isa<SelectInst>(U->getOperand(2)) ||
01652             isa<CastInst>(U->getOperand(2)) ||
01653             isa<GetElementPtrInst>(U->getOperand(2))) {
01654           s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
01655         } else {
01656           s3 = U->getOperand(2);
01657         }
01658       }
01659       
01660       // Vararg operators
01661       SmallVector<Value*, 4> sVarargs;
01662       if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
01663         for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
01664              OE = G->idx_end(); OI != OE; ++OI) {
01665           if (isa<BinaryOperator>(*OI) || 
01666               isa<CmpInst>(*OI) ||
01667               isa<ShuffleVectorInst>(*OI) ||
01668               isa<ExtractElementInst>(*OI) ||
01669               isa<InsertElementInst>(*OI) ||
01670               isa<SelectInst>(*OI) ||
01671               isa<CastInst>(*OI) ||
01672               isa<GetElementPtrInst>(*OI)) {
01673             sVarargs.push_back(find_leader(availableOut[*PI], 
01674                                VN.lookup(*OI)));
01675           } else {
01676             sVarargs.push_back(*OI);
01677           }
01678         }
01679       }
01680       
01681       Value* newVal = 0;
01682       if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
01683         newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2,
01684                                         BO->getName()+".gvnpre",
01685                                         (*PI)->getTerminator());
01686       else if (CmpInst* C = dyn_cast<CmpInst>(U))
01687         newVal = CmpInst::Create(Context, C->getOpcode(),
01688                                  C->getPredicate(), s1, s2,
01689                                  C->getName()+".gvnpre", 
01690                                  (*PI)->getTerminator());
01691       else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
01692         newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
01693                                        (*PI)->getTerminator());
01694       else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
01695         newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre",
01696                                            (*PI)->getTerminator());
01697       else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
01698         newVal = ExtractElementInst::Create(s1, s2, S->getName()+".gvnpre",
01699                                         (*PI)->getTerminator());
01700       else if (SelectInst* S = dyn_cast<SelectInst>(U))
01701         newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre",
01702                                     (*PI)->getTerminator());
01703       else if (CastInst* C = dyn_cast<CastInst>(U))
01704         newVal = CastInst::Create(C->getOpcode(), s1, C->getType(),
01705                                   C->getName()+".gvnpre", 
01706                                   (*PI)->getTerminator());
01707       else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
01708         newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(),
01709                                            G->getName()+".gvnpre", 
01710                                            (*PI)->getTerminator());
01711 
01712       VN.add(newVal, VN.lookup(U));
01713                   
01714       ValueNumberedSet& predAvail = availableOut[*PI];
01715       val_replace(predAvail, newVal);
01716       val_replace(new_sets[*PI], newVal);
01717       predAvail.set(VN.lookup(newVal));
01718             
01719       DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
01720       if (av != avail.end())
01721         avail.erase(av);
01722       avail.insert(std::make_pair(*PI, newVal));
01723                   
01724       ++NumInsertedVals;
01725     }
01726   }
01727               
01728   PHINode* p = 0;
01729               
01730   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
01731     if (p == 0)
01732       p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin());
01733     
01734     p->addIncoming(avail[*PI], *PI);
01735   }
01736 
01737   VN.add(p, VN.lookup(e));
01738   val_replace(availableOut[BB], p);
01739   availableOut[BB].set(VN.lookup(e));
01740   generatedPhis[BB].insert(p);
01741   generatedPhis[BB].set(VN.lookup(e));
01742   new_sets[BB].insert(p);
01743   new_sets[BB].set(VN.lookup(e));
01744               
01745   ++NumInsertedPhis;
01746 }
01747 
01748 /// insertion_mergepoint - When walking the dom tree, check at each merge
01749 /// block for the possibility of a partial redundancy.  If present, eliminate it
01750 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
01751                                       df_iterator<DomTreeNode*>& D,
01752                     std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
01753   bool changed_function = false;
01754   bool new_stuff = false;
01755   
01756   BasicBlock* BB = D->getBlock();
01757   for (unsigned i = 0; i < workList.size(); ++i) {
01758     Value* e = workList[i];
01759           
01760     if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
01761         isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
01762         isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
01763         isa<GetElementPtrInst>(e)) {
01764       if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
01765         continue;
01766             
01767       DenseMap<BasicBlock*, Value*> avail;
01768       bool by_some = false;
01769       bool all_same = true;
01770       Value * first_s = 0;
01771             
01772       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
01773            ++PI) {
01774         Value *e2 = phi_translate(e, *PI, BB);
01775         Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
01776               
01777         if (e3 == 0) {
01778           DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
01779           if (av != avail.end())
01780             avail.erase(av);
01781           avail.insert(std::make_pair(*PI, e2));
01782           all_same = false;
01783         } else {
01784           DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
01785           if (av != avail.end())
01786             avail.erase(av);
01787           avail.insert(std::make_pair(*PI, e3));
01788                 
01789           by_some = true;
01790           if (first_s == 0)
01791             first_s = e3;
01792           else if (first_s != e3)
01793             all_same = false;
01794         }
01795       }
01796             
01797       if (by_some && !all_same &&
01798           !generatedPhis[BB].test(VN.lookup(e))) {
01799         insertion_pre(e, BB, avail, new_sets);
01800               
01801         changed_function = true;
01802         new_stuff = true;
01803       }
01804     }
01805   }
01806   
01807   unsigned retval = 0;
01808   if (changed_function)
01809     retval += 1;
01810   if (new_stuff)
01811     retval += 2;
01812   
01813   return retval;
01814 }
01815 
01816 /// insert - Phase 2 of the main algorithm.  Walk the dominator tree looking for
01817 /// merge points.  When one is found, check for a partial redundancy.  If one is
01818 /// present, eliminate it.  Repeat this walk until no changes are made.
01819 bool GVNPRE::insertion(Function& F) {
01820   bool changed_function = false;
01821 
01822   DominatorTree &DT = getAnalysis<DominatorTree>();  
01823   
01824   std::map<BasicBlock*, ValueNumberedSet> new_sets;
01825   bool new_stuff = true;
01826   while (new_stuff) {
01827     new_stuff = false;
01828     for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
01829          E = df_end(DT.getRootNode()); DI != E; ++DI) {
01830       BasicBlock* BB = DI->getBlock();
01831       
01832       if (BB == 0)
01833         continue;
01834       
01835       ValueNumberedSet& availOut = availableOut[BB];
01836       ValueNumberedSet& anticIn = anticipatedIn[BB];
01837       
01838       // Replace leaders with leaders inherited from dominator
01839       if (DI->getIDom() != 0) {
01840         ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
01841         for (ValueNumberedSet::iterator I = dom_set.begin(),
01842              E = dom_set.end(); I != E; ++I) {
01843           val_replace(new_sets[BB], *I);
01844           val_replace(availOut, *I);
01845         }
01846       }
01847       
01848       // If there is more than one predecessor...
01849       if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
01850         SmallVector<Value*, 8> workList;
01851         workList.reserve(anticIn.size());
01852         topo_sort(anticIn, workList);
01853         
01854         unsigned result = insertion_mergepoint(workList, DI, new_sets);
01855         if (result & 1)
01856           changed_function = true;
01857         if (result & 2)
01858           new_stuff = true;
01859       }
01860     }
01861   }
01862   
01863   return changed_function;
01864 }
01865 
01866 // GVNPRE::runOnFunction - This is the main transformation entry point for a
01867 // function.
01868 //
01869 bool GVNPRE::runOnFunction(Function &F) {
01870   // Clean out global sets from any previous functions
01871   VN.clear();
01872   createdExpressions.clear();
01873   availableOut.clear();
01874   anticipatedIn.clear();
01875   generatedPhis.clear();
01876  
01877   bool changed_function = false;
01878   
01879   // Phase 1: BuildSets
01880   // This phase calculates the AVAIL_OUT and ANTIC_IN sets
01881   buildsets(F);
01882   
01883   // Phase 2: Insert
01884   // This phase inserts values to make partially redundant values
01885   // fully redundant
01886   changed_function |= insertion(F);
01887   
01888   // Phase 3: Eliminate
01889   // This phase performs trivial full redundancy elimination
01890   changed_function |= elimination();
01891   
01892   // Phase 4: Cleanup
01893   // This phase cleans up values that were created solely
01894   // as leaders for expressions
01895   cleanup();
01896   
01897   return changed_function;
01898 }