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