lib/Transforms/Scalar/SCCVN.cpp

   1 //===- SCCVN.cpp - Eliminate redundant values -----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass performs global value numbering to eliminate fully redundant
  11 // instructions.  This is based on the paper "SCC-based Value Numbering"
  12 // by Cooper, et al.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "sccvn"
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/BasicBlock.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/LLVMContext.h"
  23 #include "llvm/Operator.h"
  24 #include "llvm/Value.h"
  25 #include "llvm/ADT/DenseMap.h"
  26 #include "llvm/ADT/DepthFirstIterator.h"
  27 #include "llvm/ADT/PostOrderIterator.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/ADT/SmallVector.h"
  30 #include "llvm/ADT/SparseBitVector.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include "llvm/Analysis/Dominators.h"
  33 #include "llvm/Support/CFG.h"
  34 #include "llvm/Support/CommandLine.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/ErrorHandling.h"
  37 #include "llvm/Transforms/Utils/SSAUpdater.h"
  38 #include <cstdio>
  39 using namespace llvm;
  40
  41 STATISTIC(NumSCCVNInstr,  "Number of instructions deleted by SCCVN");
  42 STATISTIC(NumSCCVNPhi,  "Number of phis deleted by SCCVN");
  43
  44 //===----------------------------------------------------------------------===//
  45 //                         ValueTable Class
  46 //===----------------------------------------------------------------------===//
  47
  48 /// This class holds the mapping between values and value numbers.  It is used
  49 /// as an efficient mechanism to determine the expression-wise equivalence of
  50 /// two values.
  51 namespace {
  52   struct Expression {
  53     enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
  54                             UDIV, SDIV, FDIV, UREM, SREM,
  55                             FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
  56                             ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
  57                             ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
  58                             FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
  59                             FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
  60                             FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
  61                             SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
  62                             FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
  63                             PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT,
  64                             INSERTVALUE, EXTRACTVALUE, EMPTY, TOMBSTONE };
  65
  66     ExpressionOpcode opcode;
  67     const Type* type;
  68     SmallVector<uint32_t, 4> varargs;
  69
  70     Expression() { }
  71     Expression(ExpressionOpcode o) : opcode(o) { }
  72
  73     bool operator==(const Expression &other) const {
  74       if (opcode != other.opcode)
  75         return false;
  76       else if (opcode == EMPTY || opcode == TOMBSTONE)
  77         return true;
  78       else if (type != other.type)
  79         return false;
  80       else {
  81         if (varargs.size() != other.varargs.size())
  82           return false;
  83
  84         for (size_t i = 0; i < varargs.size(); ++i)
  85           if (varargs[i] != other.varargs[i])
  86             return false;
  87
  88         return true;
  89       }
  90     }
  91
  92     bool operator!=(const Expression &other) const {
  93       return !(*this == other);
  94     }
  95   };
  96
  97   class ValueTable {
  98     private:
  99       DenseMap<Value*, uint32_t> valueNumbering;
 100       DenseMap<Expression, uint32_t> expressionNumbering;
 101       DenseMap<Value*, uint32_t> constantsNumbering;
 102
 103       uint32_t nextValueNumber;
 104
 105       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
 106       Expression::ExpressionOpcode getOpcode(CmpInst* C);
 107       Expression::ExpressionOpcode getOpcode(CastInst* C);
 108       Expression create_expression(BinaryOperator* BO);
 109       Expression create_expression(CmpInst* C);
 110       Expression create_expression(ShuffleVectorInst* V);
 111       Expression create_expression(ExtractElementInst* C);
 112       Expression create_expression(InsertElementInst* V);
 113       Expression create_expression(SelectInst* V);
 114       Expression create_expression(CastInst* C);
 115       Expression create_expression(GetElementPtrInst* G);
 116       Expression create_expression(CallInst* C);
 117       Expression create_expression(Constant* C);
 118       Expression create_expression(ExtractValueInst* C);
 119       Expression create_expression(InsertValueInst* C);
 120     public:
 121       ValueTable() : nextValueNumber(1) { }
 122       uint32_t computeNumber(Value *V);
 123       uint32_t lookup(Value *V);
 124       void add(Value *V, uint32_t num);
 125       void clear();
 126       void clearExpressions();
 127       void erase(Value *v);
 128       unsigned size();
 129       void verifyRemoved(const Value *) const;
 130   };
 131 }
 132
 133 namespace llvm {
 134 template <> struct DenseMapInfo<Expression> {
 135   static inline Expression getEmptyKey() {
 136     return Expression(Expression::EMPTY);
 137   }
 138
 139   static inline Expression getTombstoneKey() {
 140     return Expression(Expression::TOMBSTONE);
 141   }
 142
 143   static unsigned getHashValue(const Expression e) {
 144     unsigned hash = e.opcode;
 145
 146     hash = ((unsigned)((uintptr_t)e.type >> 4) ^
 147             (unsigned)((uintptr_t)e.type >> 9));
 148
 149     for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
 150          E = e.varargs.end(); I != E; ++I)
 151       hash = *I + hash * 37;
 152
 153     return hash;
 154   }
 155   static bool isEqual(const Expression &LHS, const Expression &RHS) {
 156     return LHS == RHS;
 157   }
 158   static bool isPod() { return true; }
 159 };
 160 }
 161
 162 //===----------------------------------------------------------------------===//
 163 //                     ValueTable Internal Functions
 164 //===----------------------------------------------------------------------===//
 165 Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) {
 166   switch(BO->getOpcode()) {
 167   default: // THIS SHOULD NEVER HAPPEN
 168     llvm_unreachable("Binary operator with unknown opcode?");
 169   case Instruction::Add:  return Expression::ADD;
 170   case Instruction::FAdd: return Expression::FADD;
 171   case Instruction::Sub:  return Expression::SUB;
 172   case Instruction::FSub: return Expression::FSUB;
 173   case Instruction::Mul:  return Expression::MUL;
 174   case Instruction::FMul: return Expression::FMUL;
 175   case Instruction::UDiv: return Expression::UDIV;
 176   case Instruction::SDiv: return Expression::SDIV;
 177   case Instruction::FDiv: return Expression::FDIV;
 178   case Instruction::URem: return Expression::UREM;
 179   case Instruction::SRem: return Expression::SREM;
 180   case Instruction::FRem: return Expression::FREM;
 181   case Instruction::Shl:  return Expression::SHL;
 182   case Instruction::LShr: return Expression::LSHR;
 183   case Instruction::AShr: return Expression::ASHR;
 184   case Instruction::And:  return Expression::AND;
 185   case Instruction::Or:   return Expression::OR;
 186   case Instruction::Xor:  return Expression::XOR;
 187   }
 188 }
 189
 190 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 191   if (isa<ICmpInst>(C)) {
 192     switch (C->getPredicate()) {
 193     default:  // THIS SHOULD NEVER HAPPEN
 194       llvm_unreachable("Comparison with unknown predicate?");
 195     case ICmpInst::ICMP_EQ:  return Expression::ICMPEQ;
 196     case ICmpInst::ICMP_NE:  return Expression::ICMPNE;
 197     case ICmpInst::ICMP_UGT: return Expression::ICMPUGT;
 198     case ICmpInst::ICMP_UGE: return Expression::ICMPUGE;
 199     case ICmpInst::ICMP_ULT: return Expression::ICMPULT;
 200     case ICmpInst::ICMP_ULE: return Expression::ICMPULE;
 201     case ICmpInst::ICMP_SGT: return Expression::ICMPSGT;
 202     case ICmpInst::ICMP_SGE: return Expression::ICMPSGE;
 203     case ICmpInst::ICMP_SLT: return Expression::ICMPSLT;
 204     case ICmpInst::ICMP_SLE: return Expression::ICMPSLE;
 205     }
 206   } else {
 207     switch (C->getPredicate()) {
 208     default: // THIS SHOULD NEVER HAPPEN
 209       llvm_unreachable("Comparison with unknown predicate?");
 210     case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ;
 211     case FCmpInst::FCMP_OGT: return Expression::FCMPOGT;
 212     case FCmpInst::FCMP_OGE: return Expression::FCMPOGE;
 213     case FCmpInst::FCMP_OLT: return Expression::FCMPOLT;
 214     case FCmpInst::FCMP_OLE: return Expression::FCMPOLE;
 215     case FCmpInst::FCMP_ONE: return Expression::FCMPONE;
 216     case FCmpInst::FCMP_ORD: return Expression::FCMPORD;
 217     case FCmpInst::FCMP_UNO: return Expression::FCMPUNO;
 218     case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ;
 219     case FCmpInst::FCMP_UGT: return Expression::FCMPUGT;
 220     case FCmpInst::FCMP_UGE: return Expression::FCMPUGE;
 221     case FCmpInst::FCMP_ULT: return Expression::FCMPULT;
 222     case FCmpInst::FCMP_ULE: return Expression::FCMPULE;
 223     case FCmpInst::FCMP_UNE: return Expression::FCMPUNE;
 224     }
 225   }
 226 }
 227
 228 Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) {
 229   switch(C->getOpcode()) {
 230   default: // THIS SHOULD NEVER HAPPEN
 231     llvm_unreachable("Cast operator with unknown opcode?");
 232   case Instruction::Trunc:    return Expression::TRUNC;
 233   case Instruction::ZExt:     return Expression::ZEXT;
 234   case Instruction::SExt:     return Expression::SEXT;
 235   case Instruction::FPToUI:   return Expression::FPTOUI;
 236   case Instruction::FPToSI:   return Expression::FPTOSI;
 237   case Instruction::UIToFP:   return Expression::UITOFP;
 238   case Instruction::SIToFP:   return Expression::SITOFP;
 239   case Instruction::FPTrunc:  return Expression::FPTRUNC;
 240   case Instruction::FPExt:    return Expression::FPEXT;
 241   case Instruction::PtrToInt: return Expression::PTRTOINT;
 242   case Instruction::IntToPtr: return Expression::INTTOPTR;
 243   case Instruction::BitCast:  return Expression::BITCAST;
 244   }
 245 }
 246
 247 Expression ValueTable::create_expression(CallInst* C) {
 248   Expression e;
 249
 250   e.type = C->getType();
 251   e.opcode = Expression::CALL;
 252
 253   e.varargs.push_back(lookup(C->getCalledFunction()));
 254   for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
 255        I != E; ++I)
 256     e.varargs.push_back(lookup(*I));
 257
 258   return e;
 259 }
 260
 261 Expression ValueTable::create_expression(BinaryOperator* BO) {
 262   Expression e;
 263   e.varargs.push_back(lookup(BO->getOperand(0)));
 264   e.varargs.push_back(lookup(BO->getOperand(1)));
 265   e.type = BO->getType();
 266   e.opcode = getOpcode(BO);
 267
 268   return e;
 269 }
 270
 271 Expression ValueTable::create_expression(CmpInst* C) {
 272   Expression e;
 273
 274   e.varargs.push_back(lookup(C->getOperand(0)));
 275   e.varargs.push_back(lookup(C->getOperand(1)));
 276   e.type = C->getType();
 277   e.opcode = getOpcode(C);
 278
 279   return e;
 280 }
 281
 282 Expression ValueTable::create_expression(CastInst* C) {
 283   Expression e;
 284
 285   e.varargs.push_back(lookup(C->getOperand(0)));
 286   e.type = C->getType();
 287   e.opcode = getOpcode(C);
 288
 289   return e;
 290 }
 291
 292 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
 293   Expression e;
 294
 295   e.varargs.push_back(lookup(S->getOperand(0)));
 296   e.varargs.push_back(lookup(S->getOperand(1)));
 297   e.varargs.push_back(lookup(S->getOperand(2)));
 298   e.type = S->getType();
 299   e.opcode = Expression::SHUFFLE;
 300
 301   return e;
 302 }
 303
 304 Expression ValueTable::create_expression(ExtractElementInst* E) {
 305   Expression e;
 306
 307   e.varargs.push_back(lookup(E->getOperand(0)));
 308   e.varargs.push_back(lookup(E->getOperand(1)));
 309   e.type = E->getType();
 310   e.opcode = Expression::EXTRACT;
 311
 312   return e;
 313 }
 314
 315 Expression ValueTable::create_expression(InsertElementInst* I) {
 316   Expression e;
 317
 318   e.varargs.push_back(lookup(I->getOperand(0)));
 319   e.varargs.push_back(lookup(I->getOperand(1)));
 320   e.varargs.push_back(lookup(I->getOperand(2)));
 321   e.type = I->getType();
 322   e.opcode = Expression::INSERT;
 323
 324   return e;
 325 }
 326
 327 Expression ValueTable::create_expression(SelectInst* I) {
 328   Expression e;
 329
 330   e.varargs.push_back(lookup(I->getCondition()));
 331   e.varargs.push_back(lookup(I->getTrueValue()));
 332   e.varargs.push_back(lookup(I->getFalseValue()));
 333   e.type = I->getType();
 334   e.opcode = Expression::SELECT;
 335
 336   return e;
 337 }
 338
 339 Expression ValueTable::create_expression(GetElementPtrInst* G) {
 340   Expression e;
 341
 342   e.varargs.push_back(lookup(G->getPointerOperand()));
 343   e.type = G->getType();
 344   e.opcode = Expression::GEP;
 345
 346   for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
 347        I != E; ++I)
 348     e.varargs.push_back(lookup(*I));
 349
 350   return e;
 351 }
 352
 353 Expression ValueTable::create_expression(ExtractValueInst* E) {
 354   Expression e;
 355
 356   e.varargs.push_back(lookup(E->getAggregateOperand()));
 357   for (ExtractValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
 358        II != IE; ++II)
 359     e.varargs.push_back(*II);
 360   e.type = E->getType();
 361   e.opcode = Expression::EXTRACTVALUE;
 362
 363   return e;
 364 }
 365
 366 Expression ValueTable::create_expression(InsertValueInst* E) {
 367   Expression e;
 368
 369   e.varargs.push_back(lookup(E->getAggregateOperand()));
 370   e.varargs.push_back(lookup(E->getInsertedValueOperand()));
 371   for (InsertValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
 372        II != IE; ++II)
 373     e.varargs.push_back(*II);
 374   e.type = E->getType();
 375   e.opcode = Expression::INSERTVALUE;
 376
 377   return e;
 378 }
 379
 380 //===----------------------------------------------------------------------===//
 381 //                     ValueTable External Functions
 382 //===----------------------------------------------------------------------===//
 383
 384 /// add - Insert a value into the table with a specified value number.
 385 void ValueTable::add(Value *V, uint32_t num) {
 386   valueNumbering[V] = num;
 387 }
 388
 389 /// computeNumber - Returns the value number for the specified value, assigning
 390 /// it a new number if it did not have one before.
 391 uint32_t ValueTable::computeNumber(Value *V) {
 392   if (uint32_t v = valueNumbering[V])
 393     return v;
 394   else if (uint32_t v= constantsNumbering[V])
 395     return v;
 396
 397   if (!isa<Instruction>(V)) {
 398     constantsNumbering[V] = nextValueNumber;
 399     return nextValueNumber++;
 400   }
 401
 402   Instruction* I = cast<Instruction>(V);
 403   Expression exp;
 404   switch (I->getOpcode()) {
 405     case Instruction::Add:
 406     case Instruction::FAdd:
 407     case Instruction::Sub:
 408     case Instruction::FSub:
 409     case Instruction::Mul:
 410     case Instruction::FMul:
 411     case Instruction::UDiv:
 412     case Instruction::SDiv:
 413     case Instruction::FDiv:
 414     case Instruction::URem:
 415     case Instruction::SRem:
 416     case Instruction::FRem:
 417     case Instruction::Shl:
 418     case Instruction::LShr:
 419     case Instruction::AShr:
 420     case Instruction::And:
 421     case Instruction::Or :
 422     case Instruction::Xor:
 423       exp = create_expression(cast<BinaryOperator>(I));
 424       break;
 425     case Instruction::ICmp:
 426     case Instruction::FCmp:
 427       exp = create_expression(cast<CmpInst>(I));
 428       break;
 429     case Instruction::Trunc:
 430     case Instruction::ZExt:
 431     case Instruction::SExt:
 432     case Instruction::FPToUI:
 433     case Instruction::FPToSI:
 434     case Instruction::UIToFP:
 435     case Instruction::SIToFP:
 436     case Instruction::FPTrunc:
 437     case Instruction::FPExt:
 438     case Instruction::PtrToInt:
 439     case Instruction::IntToPtr:
 440     case Instruction::BitCast:
 441       exp = create_expression(cast<CastInst>(I));
 442       break;
 443     case Instruction::Select:
 444       exp = create_expression(cast<SelectInst>(I));
 445       break;
 446     case Instruction::ExtractElement:
 447       exp = create_expression(cast<ExtractElementInst>(I));
 448       break;
 449     case Instruction::InsertElement:
 450       exp = create_expression(cast<InsertElementInst>(I));
 451       break;
 452     case Instruction::ShuffleVector:
 453       exp = create_expression(cast<ShuffleVectorInst>(I));
 454       break;
 455     case Instruction::ExtractValue:
 456       exp = create_expression(cast<ExtractValueInst>(I));
 457       break;
 458     case Instruction::InsertValue:
 459       exp = create_expression(cast<InsertValueInst>(I));
 460       break;
 461     case Instruction::GetElementPtr:
 462       exp = create_expression(cast<GetElementPtrInst>(I));
 463       break;
 464     default:
 465       valueNumbering[V] = nextValueNumber;
 466       return nextValueNumber++;
 467   }
 468
 469   uint32_t& e = expressionNumbering[exp];
 470   if (!e) e = nextValueNumber++;
 471   valueNumbering[V] = e;
 472
 473   return e;
 474 }
 475
 476 /// lookup - Returns the value number of the specified value. Returns 0 if
 477 /// the value has not yet been numbered.
 478 uint32_t ValueTable::lookup(Value *V) {
 479   if (!isa<Instruction>(V)) {
 480     if (!constantsNumbering.count(V))
 481       constantsNumbering[V] = nextValueNumber++;
 482     return constantsNumbering[V];
 483   }
 484
 485   return valueNumbering[V];
 486 }
 487
 488 /// clear - Remove all entries from the ValueTable
 489 void ValueTable::clear() {
 490   valueNumbering.clear();
 491   expressionNumbering.clear();
 492   constantsNumbering.clear();
 493   nextValueNumber = 1;
 494 }
 495
 496 void ValueTable::clearExpressions() {
 497   expressionNumbering.clear();
 498   constantsNumbering.clear();
 499   nextValueNumber = 1;
 500 }
 501
 502 /// erase - Remove a value from the value numbering
 503 void ValueTable::erase(Value *V) {
 504   valueNumbering.erase(V);
 505 }
 506
 507 /// verifyRemoved - Verify that the value is removed from all internal data
 508 /// structures.
 509 void ValueTable::verifyRemoved(const Value *V) const {
 510   for (DenseMap<Value*, uint32_t>::const_iterator
 511          I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
 512     assert(I->first != V && "Inst still occurs in value numbering map!");
 513   }
 514 }
 515
 516 //===----------------------------------------------------------------------===//
 517 //                              SCCVN Pass
 518 //===----------------------------------------------------------------------===//
 519
 520 namespace {
 521
 522   struct ValueNumberScope {
 523     ValueNumberScope* parent;
 524     DenseMap<uint32_t, Value*> table;
 525     SparseBitVector<128> availIn;
 526     SparseBitVector<128> availOut;
 527
 528     ValueNumberScope(ValueNumberScope* p) : parent(p) { }
 529   };
 530
 531   class SCCVN : public FunctionPass {
 532     bool runOnFunction(Function &F);
 533   public:
 534     static char ID; // Pass identification, replacement for typeid
 535     SCCVN() : FunctionPass(&ID) { }
 536
 537   private:
 538     ValueTable VT;
 539     DenseMap<BasicBlock*, ValueNumberScope*> BBMap;
 540
 541     // This transformation requires dominator postdominator info
 542     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 543       AU.addRequired<DominatorTree>();
 544
 545       AU.addPreserved<DominatorTree>();
 546       AU.setPreservesCFG();
 547     }
 548   };
 549
 550   char SCCVN::ID = 0;
 551 }
 552
 553 // createSCCVNPass - The public interface to this file...
 554 FunctionPass *llvm::createSCCVNPass() { return new SCCVN(); }
 555
 556 static RegisterPass<SCCVN> X("sccvn",
 557                               "SCC Value Numbering");
 558
 559 static Value *lookupNumber(ValueNumberScope *Locals, uint32_t num) {
 560   while (Locals) {
 561     DenseMap<uint32_t, Value*>::iterator I = Locals->table.find(num);
 562     if (I != Locals->table.end())
 563       return I->second;
 564     Locals = Locals->parent;
 565   }
 566
 567   return 0;
 568 }
 569
 570 bool SCCVN::runOnFunction(Function& F) {
 571   // Implement the RPO version of the SCCVN algorithm.  Conceptually,
 572   // we optimisitically assume that all instructions with the same opcode have
 573   // the same VN.  Then we deepen our comparison by one level, to all
 574   // instructions whose operands have the same opcodes get the same VN.  We
 575   // iterate this process until the partitioning stops changing, at which
 576   // point we have computed a full numbering.
 577   ReversePostOrderTraversal<Function*> RPOT(&F);
 578   bool done = false;
 579   while (!done) {
 580     done = true;
 581     VT.clearExpressions();
 582     for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
 583          E = RPOT.end(); I != E; ++I) {
 584       BasicBlock* BB = *I;
 585       for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 586            BI != BE; ++BI) {
 587          uint32_t origVN = VT.lookup(BI);
 588          uint32_t newVN = VT.computeNumber(BI);
 589          if (origVN != newVN)
 590            done = false;
 591       }
 592     }
 593   }
 594
 595   // Now, do a dominator walk, eliminating simple, dominated redundancies as we
 596   // go.  Also, build the ValueNumberScope structure that will be used for
 597   // computing full availability.
 598   DominatorTree& DT = getAnalysis<DominatorTree>();
 599   bool changed = false;
 600   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 601        DE = df_end(DT.getRootNode()); DI != DE; ++DI) {
 602     BasicBlock* BB = DI->getBlock();
 603     if (DI->getIDom())
 604       BBMap[BB] = new ValueNumberScope(BBMap[DI->getIDom()->getBlock()]);
 605     else
 606       BBMap[BB] = new ValueNumberScope(0);
 607
 608     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 609       uint32_t num = VT.lookup(I);
 610       Value* repl = lookupNumber(BBMap[BB], num);
 611
 612       if (repl) {
 613         if (isa<PHINode>(I))
 614           ++NumSCCVNPhi;
 615         else
 616           ++NumSCCVNInstr;
 617         I->replaceAllUsesWith(repl);
 618         Instruction* OldInst = I;
 619         ++I;
 620         BBMap[BB]->table[num] = repl;
 621         OldInst->eraseFromParent();
 622         changed = true;
 623       } else {
 624         BBMap[BB]->table[num] = I;
 625         BBMap[BB]->availOut.set(num);
 626
 627         ++I;
 628       }
 629     }
 630   }
 631
 632   // Perform a forward data-flow to compute availability at all points on
 633   // the CFG.
 634   do {
 635     changed = false;
 636     for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
 637          E = RPOT.end(); I != E; ++I) {
 638       BasicBlock* BB = *I;
 639       ValueNumberScope *VNS = BBMap[BB];
 640
 641       SparseBitVector<128> preds;
 642       bool first = true;
 643       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 644            PI != PE; ++PI) {
 645         if (first) {
 646           preds = BBMap[*PI]->availOut;
 647           first = false;
 648         } else {
 649           preds &= BBMap[*PI]->availOut;
 650         }
 651       }
 652
 653       changed |= (VNS->availIn |= preds);
 654       changed |= (VNS->availOut |= preds);
 655     }
 656   } while (changed);
 657
 658   // Use full availability information to perform non-dominated replacements.
 659   SSAUpdater SSU;
 660   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
 661     if (!BBMap.count(FI)) continue;
 662     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
 663          BI != BE; ) {
 664       uint32_t num = VT.lookup(BI);
 665       if (!BBMap[FI]->availIn.test(num)) {
 666         ++BI;
 667         continue;
 668       }
 669
 670       SSU.Initialize(BI);
 671
 672       SmallPtrSet<BasicBlock*, 8> visited;
 673       SmallVector<BasicBlock*, 8> stack;
 674       visited.insert(FI);
 675       for (pred_iterator PI = pred_begin(FI), PE = pred_end(FI);
 676            PI != PE; ++PI)
 677         if (!visited.count(*PI))
 678           stack.push_back(*PI);
 679
 680       while (!stack.empty()) {
 681         BasicBlock* CurrBB = stack.back();
 682         stack.pop_back();
 683         visited.insert(CurrBB);
 684
 685         ValueNumberScope* S = BBMap[CurrBB];
 686         if (S->table.count(num)) {
 687           SSU.AddAvailableValue(CurrBB, S->table[num]);
 688         } else {
 689           for (pred_iterator PI = pred_begin(CurrBB), PE = pred_end(CurrBB);
 690                PI != PE; ++PI)
 691             if (!visited.count(*PI))
 692               stack.push_back(*PI);
 693         }
 694       }
 695
 696       Value* repl = SSU.GetValueInMiddleOfBlock(FI);
 697       BI->replaceAllUsesWith(repl);
 698       Instruction* CurInst = BI;
 699       ++BI;
 700       BBMap[FI]->table[num] = repl;
 701       if (isa<PHINode>(CurInst))
 702         ++NumSCCVNPhi;
 703       else
 704         ++NumSCCVNInstr;
 705
 706       CurInst->eraseFromParent();
 707     }
 708   }
 709
 710   VT.clear();
 711   for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
 712        I = BBMap.begin(), E = BBMap.end(); I != E; ++I)
 713     delete I->second;
 714   BBMap.clear();
 715
 716   return changed;
 717 }