lib/Transforms/Scalar/GVNPRE.cpp

   1 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the Owen Anderson and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass performs a hybrid of global value numbering and partial redundancy
  11 // elimination, known as GVN-PRE.  It performs partial redundancy elimination on
  12 // values, rather than lexical expressions, allowing a more comprehensive view
  13 // the optimization.  It replaces redundant values with uses of earlier
  14 // occurences of the same value.  While this is beneficial in that it eliminates
  15 // unneeded computation, it also increases register pressure by creating large
  16 // live ranges, and should be used with caution on platforms that are very
  17 // sensitive to register pressure.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #define DEBUG_TYPE "gvnpre"
  22 #include "llvm/Value.h"
  23 #include "llvm/Transforms/Scalar.h"
  24 #include "llvm/Instructions.h"
  25 #include "llvm/Function.h"
  26 #include "llvm/Analysis/Dominators.h"
  27 #include "llvm/Analysis/PostDominators.h"
  28 #include "llvm/ADT/DenseMap.h"
  29 #include "llvm/ADT/DepthFirstIterator.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/Support/CFG.h"
  32 #include "llvm/Support/Compiler.h"
  33 #include "llvm/Support/Debug.h"
  34 #include <algorithm>
  35 #include <deque>
  36 #include <map>
  37 #include <vector>
  38 #include <set>
  39 using namespace llvm;
  40
  41 //===----------------------------------------------------------------------===//
  42 //                         ValueTable Class
  43 //===----------------------------------------------------------------------===//
  44
  45 /// This class holds the mapping between values and value numbers.  It is used
  46 /// as an efficient mechanism to determine the expression-wise equivalence of
  47 /// two values.
  48
  49 namespace {
  50   class VISIBILITY_HIDDEN ValueTable {
  51     public:
  52       struct Expression {
  53         enum ExpressionOpcode { ADD, SUB, MUL, 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 };
  60
  61         ExpressionOpcode opcode;
  62         uint32_t leftVN;
  63         uint32_t rightVN;
  64
  65         bool operator< (const Expression& other) const {
  66           if (opcode < other.opcode)
  67             return true;
  68           else if (opcode > other.opcode)
  69             return false;
  70           else if (leftVN < other.leftVN)
  71             return true;
  72           else if (leftVN > other.leftVN)
  73             return false;
  74           else if (rightVN < other.rightVN)
  75             return true;
  76           else if (rightVN > other.rightVN)
  77             return false;
  78           else
  79             return false;
  80         }
  81       };
  82
  83     private:
  84       DenseMap<Value*, uint32_t> valueNumbering;
  85       std::map<Expression, uint32_t> expressionNumbering;
  86
  87       std::set<Expression> maximalExpressions;
  88       std::set<Value*> maximalValues;
  89
  90       uint32_t nextValueNumber;
  91
  92       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
  93       Expression::ExpressionOpcode getOpcode(CmpInst* C);
  94       Expression create_expression(BinaryOperator* BO);
  95       Expression create_expression(CmpInst* C);
  96     public:
  97       ValueTable() { nextValueNumber = 1; }
  98       uint32_t lookup_or_add(Value* V);
  99       uint32_t lookup(Value* V);
 100       void add(Value* V, uint32_t num);
 101       void clear();
 102       std::set<Expression>& getMaximalExpressions() {
 103         return maximalExpressions;
 104
 105       }
 106       std::set<Value*>& getMaximalValues() { return maximalValues; }
 107       void erase(Value* v);
 108   };
 109 }
 110
 111 //===----------------------------------------------------------------------===//
 112 //                     ValueTable Internal Functions
 113 //===----------------------------------------------------------------------===//
 114 ValueTable::Expression::ExpressionOpcode
 115                              ValueTable::getOpcode(BinaryOperator* BO) {
 116   switch(BO->getOpcode()) {
 117     case Instruction::Add:
 118       return Expression::ADD;
 119     case Instruction::Sub:
 120       return Expression::SUB;
 121     case Instruction::Mul:
 122       return Expression::MUL;
 123     case Instruction::UDiv:
 124       return Expression::UDIV;
 125     case Instruction::SDiv:
 126       return Expression::SDIV;
 127     case Instruction::FDiv:
 128       return Expression::FDIV;
 129     case Instruction::URem:
 130       return Expression::UREM;
 131     case Instruction::SRem:
 132       return Expression::SREM;
 133     case Instruction::FRem:
 134       return Expression::FREM;
 135     case Instruction::Shl:
 136       return Expression::SHL;
 137     case Instruction::LShr:
 138       return Expression::LSHR;
 139     case Instruction::AShr:
 140       return Expression::ASHR;
 141     case Instruction::And:
 142       return Expression::AND;
 143     case Instruction::Or:
 144       return Expression::OR;
 145     case Instruction::Xor:
 146       return Expression::XOR;
 147
 148     // THIS SHOULD NEVER HAPPEN
 149     default:
 150       assert(0 && "Binary operator with unknown opcode?");
 151       return Expression::ADD;
 152   }
 153 }
 154
 155 ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 156   if (C->getOpcode() == Instruction::ICmp) {
 157     switch (C->getPredicate()) {
 158       case ICmpInst::ICMP_EQ:
 159         return Expression::ICMPEQ;
 160       case ICmpInst::ICMP_NE:
 161         return Expression::ICMPNE;
 162       case ICmpInst::ICMP_UGT:
 163         return Expression::ICMPUGT;
 164       case ICmpInst::ICMP_UGE:
 165         return Expression::ICMPUGE;
 166       case ICmpInst::ICMP_ULT:
 167         return Expression::ICMPULT;
 168       case ICmpInst::ICMP_ULE:
 169         return Expression::ICMPULE;
 170       case ICmpInst::ICMP_SGT:
 171         return Expression::ICMPSGT;
 172       case ICmpInst::ICMP_SGE:
 173         return Expression::ICMPSGE;
 174       case ICmpInst::ICMP_SLT:
 175         return Expression::ICMPSLT;
 176       case ICmpInst::ICMP_SLE:
 177         return Expression::ICMPSLE;
 178
 179       // THIS SHOULD NEVER HAPPEN
 180       default:
 181         assert(0 && "Comparison with unknown predicate?");
 182         return Expression::ICMPEQ;
 183     }
 184   } else {
 185     switch (C->getPredicate()) {
 186       case FCmpInst::FCMP_OEQ:
 187         return Expression::FCMPOEQ;
 188       case FCmpInst::FCMP_OGT:
 189         return Expression::FCMPOGT;
 190       case FCmpInst::FCMP_OGE:
 191         return Expression::FCMPOGE;
 192       case FCmpInst::FCMP_OLT:
 193         return Expression::FCMPOLT;
 194       case FCmpInst::FCMP_OLE:
 195         return Expression::FCMPOLE;
 196       case FCmpInst::FCMP_ONE:
 197         return Expression::FCMPONE;
 198       case FCmpInst::FCMP_ORD:
 199         return Expression::FCMPORD;
 200       case FCmpInst::FCMP_UNO:
 201         return Expression::FCMPUNO;
 202       case FCmpInst::FCMP_UEQ:
 203         return Expression::FCMPUEQ;
 204       case FCmpInst::FCMP_UGT:
 205         return Expression::FCMPUGT;
 206       case FCmpInst::FCMP_UGE:
 207         return Expression::FCMPUGE;
 208       case FCmpInst::FCMP_ULT:
 209         return Expression::FCMPULT;
 210       case FCmpInst::FCMP_ULE:
 211         return Expression::FCMPULE;
 212       case FCmpInst::FCMP_UNE:
 213         return Expression::FCMPUNE;
 214
 215       // THIS SHOULD NEVER HAPPEN
 216       default:
 217         assert(0 && "Comparison with unknown predicate?");
 218         return Expression::FCMPOEQ;
 219     }
 220   }
 221 }
 222
 223 ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
 224   Expression e;
 225
 226   e.leftVN = lookup_or_add(BO->getOperand(0));
 227   e.rightVN = lookup_or_add(BO->getOperand(1));
 228   e.opcode = getOpcode(BO);
 229
 230   maximalExpressions.insert(e);
 231
 232   return e;
 233 }
 234
 235 ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
 236   Expression e;
 237
 238   e.leftVN = lookup_or_add(C->getOperand(0));
 239   e.rightVN = lookup_or_add(C->getOperand(1));
 240   e.opcode = getOpcode(C);
 241
 242   maximalExpressions.insert(e);
 243
 244   return e;
 245 }
 246
 247 //===----------------------------------------------------------------------===//
 248 //                     ValueTable External Functions
 249 //===----------------------------------------------------------------------===//
 250
 251 /// lookup_or_add - Returns the value number for the specified value, assigning
 252 /// it a new number if it did not have one before.
 253 uint32_t ValueTable::lookup_or_add(Value* V) {
 254   maximalValues.insert(V);
 255
 256   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 257   if (VI != valueNumbering.end())
 258     return VI->second;
 259
 260
 261   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 262     Expression e = create_expression(BO);
 263
 264     std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 265     if (EI != expressionNumbering.end()) {
 266       valueNumbering.insert(std::make_pair(V, EI->second));
 267       return EI->second;
 268     } else {
 269       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 270       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 271
 272       return nextValueNumber++;
 273     }
 274   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 275     Expression e = create_expression(C);
 276
 277     std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 278     if (EI != expressionNumbering.end()) {
 279       valueNumbering.insert(std::make_pair(V, EI->second));
 280       return EI->second;
 281     } else {
 282       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 283       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 284
 285       return nextValueNumber++;
 286     }
 287   } else {
 288     valueNumbering.insert(std::make_pair(V, nextValueNumber));
 289     return nextValueNumber++;
 290   }
 291 }
 292
 293 /// lookup - Returns the value number of the specified value. Fails if
 294 /// the value has not yet been numbered.
 295 uint32_t ValueTable::lookup(Value* V) {
 296   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 297   if (VI != valueNumbering.end())
 298     return VI->second;
 299   else
 300     assert(0 && "Value not numbered?");
 301
 302   return 0;
 303 }
 304
 305 /// add - Add the specified value with the given value number, removing
 306 /// its old number, if any
 307 void ValueTable::add(Value* V, uint32_t num) {
 308   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 309   if (VI != valueNumbering.end())
 310     valueNumbering.erase(VI);
 311   valueNumbering.insert(std::make_pair(V, num));
 312 }
 313
 314 /// clear - Remove all entries from the ValueTable and the maximal sets
 315 void ValueTable::clear() {
 316   valueNumbering.clear();
 317   expressionNumbering.clear();
 318   maximalExpressions.clear();
 319   maximalValues.clear();
 320   nextValueNumber = 1;
 321 }
 322
 323 /// erase - Remove a value from the value numbering and maximal sets
 324 void ValueTable::erase(Value* V) {
 325   maximalValues.erase(V);
 326   valueNumbering.erase(V);
 327   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V))
 328     maximalExpressions.erase(create_expression(BO));
 329   else if (CmpInst* C = dyn_cast<CmpInst>(V))
 330     maximalExpressions.erase(create_expression(C));
 331 }
 332
 333 //===----------------------------------------------------------------------===//
 334 //                         GVNPRE Pass
 335 //===----------------------------------------------------------------------===//
 336
 337 namespace {
 338
 339   class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
 340     bool runOnFunction(Function &F);
 341   public:
 342     static char ID; // Pass identification, replacement for typeid
 343     GVNPRE() : FunctionPass((intptr_t)&ID) { }
 344
 345   private:
 346     ValueTable VN;
 347     std::vector<Instruction*> createdExpressions;
 348
 349     std::map<BasicBlock*, std::set<Value*> > availableOut;
 350     std::map<BasicBlock*, std::set<Value*> > anticipatedIn;
 351
 352     // This transformation requires dominator postdominator info
 353     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 354       AU.setPreservesCFG();
 355       AU.addRequired<DominatorTree>();
 356       AU.addRequired<PostDominatorTree>();
 357     }
 358
 359     // Helper fuctions
 360     // FIXME: eliminate or document these better
 361     void dump(const std::set<Value*>& s) const;
 362     void clean(std::set<Value*>& set);
 363     Value* find_leader(std::set<Value*>& vals,
 364                        uint32_t v);
 365     Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ);
 366     void phi_translate_set(std::set<Value*>& anticIn, BasicBlock* pred,
 367                            BasicBlock* succ, std::set<Value*>& out);
 368
 369     void topo_sort(std::set<Value*>& set,
 370                    std::vector<Value*>& vec);
 371
 372     void cleanup();
 373     bool elimination();
 374
 375     void val_insert(std::set<Value*>& s, Value* v);
 376     void val_replace(std::set<Value*>& s, Value* v);
 377     bool dependsOnInvoke(Value* V);
 378     void buildsets_availout(BasicBlock::iterator I,
 379                             std::set<Value*>& currAvail,
 380                             std::set<PHINode*>& currPhis,
 381                             std::set<Value*>& currExps,
 382                             std::set<Value*>& currTemps);
 383     void buildsets_anticout(BasicBlock* BB,
 384                             std::set<Value*>& anticOut,
 385                             std::set<BasicBlock*>& visited);
 386     bool buildsets_anticin(BasicBlock* BB,
 387                            std::set<Value*>& anticOut,
 388                            std::set<Value*>& currExps,
 389                            std::set<Value*>& currTemps,
 390                            std::set<BasicBlock*>& visited);
 391     unsigned buildsets(Function& F);
 392
 393     void insertion_pre(Value* e, BasicBlock* BB,
 394                        std::map<BasicBlock*, Value*>& avail,
 395                        std::set<Value*>& new_set);
 396     unsigned insertion_mergepoint(std::vector<Value*>& workList,
 397                                   df_iterator<DomTreeNode*> D,
 398                                   std::set<Value*>& new_set);
 399     bool insertion(Function& F);
 400
 401   };
 402
 403   char GVNPRE::ID = 0;
 404
 405 }
 406
 407 // createGVNPREPass - The public interface to this file...
 408 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
 409
 410 RegisterPass<GVNPRE> X("gvnpre",
 411                        "Global Value Numbering/Partial Redundancy Elimination");
 412
 413
 414 STATISTIC(NumInsertedVals, "Number of values inserted");
 415 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
 416 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
 417
 418 /// find_leader - Given a set and a value number, return the first
 419 /// element of the set with that value number, or 0 if no such element
 420 /// is present
 421 Value* GVNPRE::find_leader(std::set<Value*>& vals, uint32_t v) {
 422   for (std::set<Value*>::iterator I = vals.begin(), E = vals.end();
 423        I != E; ++I)
 424     if (v == VN.lookup(*I))
 425       return *I;
 426
 427   return 0;
 428 }
 429
 430 /// val_insert - Insert a value into a set only if there is not a value
 431 /// with the same value number already in the set
 432 void GVNPRE::val_insert(std::set<Value*>& s, Value* v) {
 433   uint32_t num = VN.lookup(v);
 434   Value* leader = find_leader(s, num);
 435   if (leader == 0)
 436     s.insert(v);
 437 }
 438
 439 /// val_replace - Insert a value into a set, replacing any values already in
 440 /// the set that have the same value number
 441 void GVNPRE::val_replace(std::set<Value*>& s, Value* v) {
 442   uint32_t num = VN.lookup(v);
 443   Value* leader = find_leader(s, num);
 444   while (leader != 0) {
 445     s.erase(leader);
 446     leader = find_leader(s, num);
 447   }
 448   s.insert(v);
 449 }
 450
 451 /// phi_translate - Given a value, its parent block, and a predecessor of its
 452 /// parent, translate the value into legal for the predecessor block.  This
 453 /// means translating its operands (and recursively, their operands) through
 454 /// any phi nodes in the parent into values available in the predecessor
 455 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
 456   if (V == 0)
 457     return 0;
 458
 459   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 460     Value* newOp1 = 0;
 461     if (isa<Instruction>(BO->getOperand(0)))
 462       newOp1 = phi_translate(find_leader(anticipatedIn[succ],
 463                                          VN.lookup(BO->getOperand(0))),
 464                              pred, succ);
 465     else
 466       newOp1 = BO->getOperand(0);
 467
 468     if (newOp1 == 0)
 469       return 0;
 470
 471     Value* newOp2 = 0;
 472     if (isa<Instruction>(BO->getOperand(1)))
 473       newOp2 = phi_translate(find_leader(anticipatedIn[succ],
 474                                          VN.lookup(BO->getOperand(1))),
 475                              pred, succ);
 476     else
 477       newOp2 = BO->getOperand(1);
 478
 479     if (newOp2 == 0)
 480       return 0;
 481
 482     if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
 483       Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
 484                                              newOp1, newOp2,
 485                                              BO->getName()+".expr");
 486
 487       uint32_t v = VN.lookup_or_add(newVal);
 488
 489       Value* leader = find_leader(availableOut[pred], v);
 490       if (leader == 0) {
 491         createdExpressions.push_back(newVal);
 492         return newVal;
 493       } else {
 494         VN.erase(newVal);
 495         delete newVal;
 496         return leader;
 497       }
 498     }
 499   } else if (PHINode* P = dyn_cast<PHINode>(V)) {
 500     if (P->getParent() == succ)
 501       return P->getIncomingValueForBlock(pred);
 502   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 503     Value* newOp1 = 0;
 504     if (isa<Instruction>(C->getOperand(0)))
 505       newOp1 = phi_translate(find_leader(anticipatedIn[succ],
 506                                          VN.lookup(C->getOperand(0))),
 507                              pred, succ);
 508     else
 509       newOp1 = C->getOperand(0);
 510
 511     if (newOp1 == 0)
 512       return 0;
 513
 514     Value* newOp2 = 0;
 515     if (isa<Instruction>(C->getOperand(1)))
 516       newOp2 = phi_translate(find_leader(anticipatedIn[succ],
 517                                          VN.lookup(C->getOperand(1))),
 518                              pred, succ);
 519     else
 520       newOp2 = C->getOperand(1);
 521
 522     if (newOp2 == 0)
 523       return 0;
 524
 525     if (newOp1 != C->getOperand(0) || newOp2 != C->getOperand(1)) {
 526       Instruction* newVal = CmpInst::create(C->getOpcode(),
 527                                             C->getPredicate(),
 528                                              newOp1, newOp2,
 529                                              C->getName()+".expr");
 530
 531       uint32_t v = VN.lookup_or_add(newVal);
 532
 533       Value* leader = find_leader(availableOut[pred], v);
 534       if (leader == 0) {
 535         createdExpressions.push_back(newVal);
 536         return newVal;
 537       } else {
 538         VN.erase(newVal);
 539         delete newVal;
 540         return leader;
 541       }
 542     }
 543   }
 544
 545   return V;
 546 }
 547
 548 /// phi_translate_set - Perform phi translation on every element of a set
 549 void GVNPRE::phi_translate_set(std::set<Value*>& anticIn,
 550                               BasicBlock* pred, BasicBlock* succ,
 551                               std::set<Value*>& out) {
 552   for (std::set<Value*>::iterator I = anticIn.begin(),
 553        E = anticIn.end(); I != E; ++I) {
 554     Value* V = phi_translate(*I, pred, succ);
 555     if (V != 0)
 556       out.insert(V);
 557   }
 558 }
 559
 560 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
 561 /// whose inputs is an invoke instruction.  If this is true, we cannot safely
 562 /// PRE the instruction or anything that depends on it.
 563 bool GVNPRE::dependsOnInvoke(Value* V) {
 564   if (PHINode* p = dyn_cast<PHINode>(V)) {
 565     for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
 566       if (isa<InvokeInst>(*I))
 567         return true;
 568     return false;
 569   } else {
 570     return false;
 571   }
 572 }
 573
 574 /// clean - Remove all non-opaque values from the set whose operands are not
 575 /// themselves in the set, as well as all values that depend on invokes (see
 576 /// above)
 577 void GVNPRE::clean(std::set<Value*>& set) {
 578   std::vector<Value*> worklist;
 579   topo_sort(set, worklist);
 580
 581   for (unsigned i = 0; i < worklist.size(); ++i) {
 582     Value* v = worklist[i];
 583
 584     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
 585       bool lhsValid = !isa<Instruction>(BO->getOperand(0));
 586       if (!lhsValid)
 587         for (std::set<Value*>::iterator I = set.begin(), E = set.end();
 588              I != E; ++I)
 589           if (VN.lookup(*I) == VN.lookup(BO->getOperand(0))) {
 590             lhsValid = true;
 591             break;
 592           }
 593       if (lhsValid)
 594         lhsValid = !dependsOnInvoke(BO->getOperand(0));
 595
 596       bool rhsValid = !isa<Instruction>(BO->getOperand(1));
 597       if (!rhsValid)
 598         for (std::set<Value*>::iterator I = set.begin(), E = set.end();
 599              I != E; ++I)
 600           if (VN.lookup(*I) == VN.lookup(BO->getOperand(1))) {
 601             rhsValid = true;
 602             break;
 603           }
 604       if (rhsValid)
 605         rhsValid = !dependsOnInvoke(BO->getOperand(1));
 606
 607       if (!lhsValid || !rhsValid)
 608         set.erase(BO);
 609     } else if (CmpInst* C = dyn_cast<CmpInst>(v)) {
 610       bool lhsValid = !isa<Instruction>(C->getOperand(0));
 611       if (!lhsValid)
 612         for (std::set<Value*>::iterator I = set.begin(), E = set.end();
 613              I != E; ++I)
 614           if (VN.lookup(*I) == VN.lookup(C->getOperand(0))) {
 615             lhsValid = true;
 616             break;
 617           }
 618       if (lhsValid)
 619         lhsValid = !dependsOnInvoke(C->getOperand(0));
 620
 621       bool rhsValid = !isa<Instruction>(C->getOperand(1));
 622       if (!rhsValid)
 623       for (std::set<Value*>::iterator I = set.begin(), E = set.end();
 624            I != E; ++I)
 625         if (VN.lookup(*I) == VN.lookup(C->getOperand(1))) {
 626           rhsValid = true;
 627           break;
 628         }
 629       if (rhsValid)
 630         rhsValid = !dependsOnInvoke(C->getOperand(1));
 631
 632       if (!lhsValid || !rhsValid)
 633         set.erase(C);
 634     }
 635   }
 636 }
 637
 638 /// topo_sort - Given a set of values, sort them by topological
 639 /// order into the provided vector.
 640 void GVNPRE::topo_sort(std::set<Value*>& set, std::vector<Value*>& vec) {
 641   std::set<Value*> toErase;
 642   for (std::set<Value*>::iterator I = set.begin(), E = set.end();
 643        I != E; ++I) {
 644     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
 645       for (std::set<Value*>::iterator SI = set.begin(); SI != E; ++SI) {
 646         if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
 647             VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
 648           toErase.insert(*SI);
 649         }
 650       }
 651     else if (CmpInst* C = dyn_cast<CmpInst>(*I))
 652       for (std::set<Value*>::iterator SI = set.begin(); SI != E; ++SI) {
 653         if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
 654             VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
 655           toErase.insert(*SI);
 656         }
 657       }
 658   }
 659
 660   std::vector<Value*> Q;
 661   for (std::set<Value*>::iterator I = set.begin(), E = set.end();
 662        I != E; ++I) {
 663     if (toErase.find(*I) == toErase.end())
 664       Q.push_back(*I);
 665   }
 666
 667   std::set<Value*> visited;
 668   while (!Q.empty()) {
 669     Value* e = Q.back();
 670
 671     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
 672       Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
 673       Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
 674
 675       if (l != 0 && isa<Instruction>(l) &&
 676           visited.find(l) == visited.end())
 677         Q.push_back(l);
 678       else if (r != 0 && isa<Instruction>(r) &&
 679                visited.find(r) == visited.end())
 680         Q.push_back(r);
 681       else {
 682         vec.push_back(e);
 683         visited.insert(e);
 684         Q.pop_back();
 685       }
 686     } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
 687       Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
 688       Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
 689
 690       if (l != 0 && isa<Instruction>(l) &&
 691           visited.find(l) == visited.end())
 692         Q.push_back(l);
 693       else if (r != 0 && isa<Instruction>(r) &&
 694                visited.find(r) == visited.end())
 695         Q.push_back(r);
 696       else {
 697         vec.push_back(e);
 698         visited.insert(e);
 699         Q.pop_back();
 700       }
 701     } else {
 702       visited.insert(e);
 703       vec.push_back(e);
 704       Q.pop_back();
 705     }
 706   }
 707 }
 708
 709 /// dump - Dump a set of values to standard error
 710 void GVNPRE::dump(const std::set<Value*>& s) const {
 711   DOUT << "{ ";
 712   for (std::set<Value*>::iterator I = s.begin(), E = s.end();
 713        I != E; ++I) {
 714     DEBUG((*I)->dump());
 715   }
 716   DOUT << "}\n\n";
 717 }
 718
 719 /// elimination - Phase 3 of the main algorithm.  Perform full redundancy
 720 /// elimination by walking the dominator tree and removing any instruction that
 721 /// is dominated by another instruction with the same value number.
 722 bool GVNPRE::elimination() {
 723   DOUT << "\n\nPhase 3: Elimination\n\n";
 724
 725   bool changed_function = false;
 726
 727   std::vector<std::pair<Instruction*, Value*> > replace;
 728   std::vector<Instruction*> erase;
 729
 730   DominatorTree& DT = getAnalysis<DominatorTree>();
 731
 732   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 733          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 734     BasicBlock* BB = DI->getBlock();
 735
 736     DOUT << "Block: " << BB->getName() << "\n";
 737     dump(availableOut[BB]);
 738     DOUT << "\n\n";
 739
 740     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 741          BI != BE; ++BI) {
 742
 743       if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
 744          Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
 745
 746         if (leader != 0)
 747           if (Instruction* Instr = dyn_cast<Instruction>(leader))
 748             if (Instr->getParent() != 0 && Instr != BI) {
 749               replace.push_back(std::make_pair(BI, leader));
 750               erase.push_back(BI);
 751               ++NumEliminated;
 752             }
 753       }
 754     }
 755   }
 756
 757   while (!replace.empty()) {
 758     std::pair<Instruction*, Value*> rep = replace.back();
 759     replace.pop_back();
 760     rep.first->replaceAllUsesWith(rep.second);
 761     changed_function = true;
 762   }
 763
 764   for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
 765        I != E; ++I)
 766      (*I)->eraseFromParent();
 767
 768   return changed_function;
 769 }
 770
 771 /// cleanup - Delete any extraneous values that were created to represent
 772 /// expressions without leaders.
 773 void GVNPRE::cleanup() {
 774   while (!createdExpressions.empty()) {
 775     Instruction* I = createdExpressions.back();
 776     createdExpressions.pop_back();
 777
 778     delete I;
 779   }
 780 }
 781
 782 /// buildsets_availout - When calculating availability, handle an instruction
 783 /// by inserting it into the appropriate sets
 784 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
 785                                 std::set<Value*>& currAvail,
 786                                 std::set<PHINode*>& currPhis,
 787                                 std::set<Value*>& currExps,
 788                                 std::set<Value*>& currTemps) {
 789   // Handle PHI nodes...
 790   if (PHINode* p = dyn_cast<PHINode>(I)) {
 791     VN.lookup_or_add(p);
 792     currPhis.insert(p);
 793
 794   // Handle binary ops...
 795   } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(I)) {
 796     Value* leftValue = BO->getOperand(0);
 797     Value* rightValue = BO->getOperand(1);
 798
 799     VN.lookup_or_add(BO);
 800
 801     if (isa<Instruction>(leftValue))
 802       val_insert(currExps, leftValue);
 803     if (isa<Instruction>(rightValue))
 804       val_insert(currExps, rightValue);
 805     val_insert(currExps, BO);
 806
 807   // Handle cmp ops...
 808   } else if (CmpInst* C = dyn_cast<CmpInst>(I)) {
 809     Value* leftValue = C->getOperand(0);
 810     Value* rightValue = C->getOperand(1);
 811
 812     VN.lookup_or_add(C);
 813
 814     if (isa<Instruction>(leftValue))
 815       val_insert(currExps, leftValue);
 816     if (isa<Instruction>(rightValue))
 817       val_insert(currExps, rightValue);
 818     val_insert(currExps, C);
 819
 820   // Handle unsupported ops
 821   } else if (!I->isTerminator()){
 822     VN.lookup_or_add(I);
 823     currTemps.insert(I);
 824   }
 825
 826   if (!I->isTerminator())
 827     val_insert(currAvail, I);
 828 }
 829
 830 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
 831 /// set as a function of the ANTIC_IN set of the block's predecessors
 832 void GVNPRE::buildsets_anticout(BasicBlock* BB,
 833                                 std::set<Value*>& anticOut,
 834                                 std::set<BasicBlock*>& visited) {
 835   if (BB->getTerminator()->getNumSuccessors() == 1) {
 836     if (visited.find(BB->getTerminator()->getSuccessor(0)) == visited.end())
 837       phi_translate_set(VN.getMaximalValues(), BB,
 838                         BB->getTerminator()->getSuccessor(0), anticOut);
 839     else
 840       phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
 841                         BB,  BB->getTerminator()->getSuccessor(0), anticOut);
 842   } else if (BB->getTerminator()->getNumSuccessors() > 1) {
 843     BasicBlock* first = BB->getTerminator()->getSuccessor(0);
 844     anticOut.insert(anticipatedIn[first].begin(), anticipatedIn[first].end());
 845
 846     for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
 847       BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
 848       std::set<Value*>& succAnticIn = anticipatedIn[currSucc];
 849
 850       std::set<Value*> temp;
 851       std::insert_iterator<std::set<Value*> >  temp_ins(temp, temp.begin());
 852       std::set_intersection(anticOut.begin(), anticOut.end(),
 853                             succAnticIn.begin(), succAnticIn.end(), temp_ins);
 854
 855       anticOut.clear();
 856       anticOut.insert(temp.begin(), temp.end());
 857     }
 858   }
 859 }
 860
 861 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
 862 /// each block.  ANTIC_IN is then a function of ANTIC_OUT and the GEN
 863 /// sets populated in buildsets_availout
 864 bool GVNPRE::buildsets_anticin(BasicBlock* BB,
 865                                std::set<Value*>& anticOut,
 866                                std::set<Value*>& currExps,
 867                                std::set<Value*>& currTemps,
 868                                std::set<BasicBlock*>& visited) {
 869   std::set<Value*>& anticIn = anticipatedIn[BB];
 870   std::set<Value*> old (anticIn.begin(), anticIn.end());
 871
 872   buildsets_anticout(BB, anticOut, visited);
 873
 874   std::set<Value*> S;
 875   std::insert_iterator<std::set<Value*> >  s_ins(S, S.begin());
 876   std::set_difference(anticOut.begin(), anticOut.end(),
 877                       currTemps.begin(), currTemps.end(), s_ins);
 878
 879   anticIn.clear();
 880   std::insert_iterator<std::set<Value*> >  ai_ins(anticIn, anticIn.begin());
 881   std::set_difference(currExps.begin(), currExps.end(),
 882                       currTemps.begin(), currTemps.end(), ai_ins);
 883
 884   for (std::set<Value*>::iterator I = S.begin(), E = S.end();
 885        I != E; ++I) {
 886     // For non-opaque values, we should already have a value numbering.
 887     // However, for opaques, such as constants within PHI nodes, it is
 888     // possible that they have not yet received a number.  Make sure they do
 889     // so now.
 890     uint32_t valNum = 0;
 891     if (isa<BinaryOperator>(*I) || isa<CmpInst>(*I))
 892       valNum = VN.lookup(*I);
 893     else
 894       valNum = VN.lookup_or_add(*I);
 895     if (find_leader(anticIn, valNum) == 0)
 896       val_insert(anticIn, *I);
 897   }
 898
 899   clean(anticIn);
 900   anticOut.clear();
 901
 902   if (old.size() != anticIn.size())
 903     return true;
 904   else
 905     return false;
 906 }
 907
 908 /// buildsets - Phase 1 of the main algorithm.  Construct the AVAIL_OUT
 909 /// and the ANTIC_IN sets.
 910 unsigned GVNPRE::buildsets(Function& F) {
 911   std::map<BasicBlock*, std::set<Value*> > generatedExpressions;
 912   std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
 913   std::map<BasicBlock*, std::set<Value*> > generatedTemporaries;
 914
 915   DominatorTree &DT = getAnalysis<DominatorTree>();
 916
 917   // Phase 1, Part 1: calculate AVAIL_OUT
 918
 919   // Top-down walk of the dominator tree
 920   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 921          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 922
 923     // Get the sets to update for this block
 924     std::set<Value*>& currExps = generatedExpressions[DI->getBlock()];
 925     std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
 926     std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()];
 927     std::set<Value*>& currAvail = availableOut[DI->getBlock()];
 928
 929     BasicBlock* BB = DI->getBlock();
 930
 931     // A block inherits AVAIL_OUT from its dominator
 932     if (DI->getIDom() != 0)
 933     currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
 934                      availableOut[DI->getIDom()->getBlock()].end());
 935
 936
 937     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 938          BI != BE; ++BI)
 939       buildsets_availout(BI, currAvail, currPhis, currExps, currTemps);
 940
 941   }
 942
 943   // If function has no exit blocks, only perform GVN
 944   PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
 945   if (PDT[&F.getEntryBlock()] == 0) {
 946     bool changed_function = elimination();
 947     cleanup();
 948
 949     if (changed_function)
 950       return 2;  // Bailed early, made changes
 951     else
 952       return 1;  // Bailed early, no changes
 953   }
 954
 955
 956   // Phase 1, Part 2: calculate ANTIC_IN
 957
 958   std::set<BasicBlock*> visited;
 959
 960   bool changed = true;
 961   unsigned iterations = 0;
 962   while (changed) {
 963     changed = false;
 964     std::set<Value*> anticOut;
 965
 966     // Top-down walk of the postdominator tree
 967     for (df_iterator<DomTreeNode*> PDI =
 968          df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
 969          PDI != E; ++PDI) {
 970       BasicBlock* BB = PDI->getBlock();
 971       if (BB == 0)
 972         continue;
 973
 974       visited.insert(BB);
 975
 976       changed |= buildsets_anticin(BB, anticOut, generatedTemporaries[BB],
 977                                    generatedExpressions[BB], visited);
 978     }
 979
 980     iterations++;
 981   }
 982
 983   return 0; // No bail, no changes
 984 }
 985
 986 /// insertion_pre - When a partial redundancy has been identified, eliminate it
 987 /// by inserting appropriate values into the predecessors and a phi node in
 988 /// the main block
 989 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
 990                            std::map<BasicBlock*, Value*>& avail,
 991                            std::set<Value*>& new_set) {
 992   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
 993     Value* e2 = avail[*PI];
 994     if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
 995       User* U = cast<User>(e2);
 996
 997       Value* s1 = 0;
 998       if (isa<BinaryOperator>(U->getOperand(0)) ||
 999           isa<CmpInst>(U->getOperand(0)))
1000         s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1001       else
1002         s1 = U->getOperand(0);
1003
1004       Value* s2 = 0;
1005       if (isa<BinaryOperator>(U->getOperand(1)) ||
1006           isa<CmpInst>(U->getOperand(1)))
1007         s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1008       else
1009         s2 = U->getOperand(1);
1010
1011       Value* newVal = 0;
1012       if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1013         newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1014                                         BO->getName()+".gvnpre",
1015                                         (*PI)->getTerminator());
1016       else if (CmpInst* C = dyn_cast<CmpInst>(U))
1017         newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1018                                  C->getName()+".gvnpre",
1019                                  (*PI)->getTerminator());
1020
1021       VN.add(newVal, VN.lookup(U));
1022
1023       std::set<Value*>& predAvail = availableOut[*PI];
1024       val_replace(predAvail, newVal);
1025
1026       std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1027       if (av != avail.end())
1028         avail.erase(av);
1029       avail.insert(std::make_pair(*PI, newVal));
1030
1031       ++NumInsertedVals;
1032     }
1033   }
1034
1035   PHINode* p = 0;
1036
1037   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1038     if (p == 0)
1039       p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1040
1041     p->addIncoming(avail[*PI], *PI);
1042   }
1043
1044   VN.add(p, VN.lookup(e));
1045   val_replace(availableOut[BB], p);
1046   new_set.insert(p);
1047
1048   ++NumInsertedPhis;
1049 }
1050
1051 /// insertion_mergepoint - When walking the dom tree, check at each merge
1052 /// block for the possibility of a partial redundancy.  If present, eliminate it
1053 unsigned GVNPRE::insertion_mergepoint(std::vector<Value*>& workList,
1054                                       df_iterator<DomTreeNode*> D,
1055                                       std::set<Value*>& new_set) {
1056   bool changed_function = false;
1057   bool new_stuff = false;
1058
1059   BasicBlock* BB = D->getBlock();
1060   for (unsigned i = 0; i < workList.size(); ++i) {
1061     Value* e = workList[i];
1062
1063     if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
1064       if (find_leader(availableOut[D->getIDom()->getBlock()],
1065                       VN.lookup(e)) != 0)
1066         continue;
1067
1068       std::map<BasicBlock*, Value*> avail;
1069       bool by_some = false;
1070       int num_avail = 0;
1071
1072       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1073            ++PI) {
1074         Value *e2 = phi_translate(e, *PI, BB);
1075         Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1076
1077         if (e3 == 0) {
1078           std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1079           if (av != avail.end())
1080             avail.erase(av);
1081           avail.insert(std::make_pair(*PI, e2));
1082         } else {
1083           std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1084           if (av != avail.end())
1085             avail.erase(av);
1086           avail.insert(std::make_pair(*PI, e3));
1087
1088           by_some = true;
1089           num_avail++;
1090         }
1091       }
1092
1093       if (by_some && num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1094         insertion_pre(e, BB, avail, new_set);
1095
1096         changed_function = true;
1097         new_stuff = true;
1098       }
1099     }
1100   }
1101
1102   unsigned retval = 0;
1103   if (changed_function)
1104     retval += 1;
1105   if (new_stuff)
1106     retval += 2;
1107
1108   return retval;
1109 }
1110
1111 /// insert - Phase 2 of the main algorithm.  Walk the dominator tree looking for
1112 /// merge points.  When one is found, check for a partial redundancy.  If one is
1113 /// present, eliminate it.  Repeat this walk until no changes are made.
1114 bool GVNPRE::insertion(Function& F) {
1115   bool changed_function = false;
1116
1117   DominatorTree &DT = getAnalysis<DominatorTree>();
1118
1119   std::map<BasicBlock*, std::set<Value*> > new_sets;
1120   bool new_stuff = true;
1121   while (new_stuff) {
1122     new_stuff = false;
1123     for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1124          E = df_end(DT.getRootNode()); DI != E; ++DI) {
1125       BasicBlock* BB = DI->getBlock();
1126
1127       if (BB == 0)
1128         continue;
1129
1130       std::set<Value*>& new_set = new_sets[BB];
1131       std::set<Value*>& availOut = availableOut[BB];
1132       std::set<Value*>& anticIn = anticipatedIn[BB];
1133
1134       new_set.clear();
1135
1136       // Replace leaders with leaders inherited from dominator
1137       if (DI->getIDom() != 0) {
1138         std::set<Value*>& dom_set = new_sets[DI->getIDom()->getBlock()];
1139         for (std::set<Value*>::iterator I = dom_set.begin(),
1140              E = dom_set.end(); I != E; ++I) {
1141           new_set.insert(*I);
1142           val_replace(availOut, *I);
1143         }
1144       }
1145
1146       // If there is more than one predecessor...
1147       if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1148         std::vector<Value*> workList;
1149         topo_sort(anticIn, workList);
1150
1151         DOUT << "Merge Block: " << BB->getName() << "\n";
1152         DOUT << "ANTIC_IN: ";
1153         dump(anticIn);
1154         DOUT << "\n";
1155
1156         unsigned result = insertion_mergepoint(workList, DI, new_set);
1157         if (result & 1)
1158           changed_function = true;
1159         if (result & 2)
1160           new_stuff = true;
1161       }
1162     }
1163   }
1164
1165   return changed_function;
1166 }
1167
1168 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1169 // function.
1170 //
1171 bool GVNPRE::runOnFunction(Function &F) {
1172   // Clean out global sets from any previous functions
1173   VN.clear();
1174   createdExpressions.clear();
1175   availableOut.clear();
1176   anticipatedIn.clear();
1177
1178   bool changed_function = false;
1179
1180   // Phase 1: BuildSets
1181   // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1182   // NOTE: If full postdom information is no available, this will bail
1183   // early, performing GVN but not PRE
1184   unsigned bail = buildsets(F);
1185   //If a bail occurred, terminate early
1186   if (bail != 0)
1187     return (bail == 2);
1188
1189   // Phase 2: Insert
1190   // This phase inserts values to make partially redundant values
1191   // fully redundant
1192   changed_function |= insertion(F);
1193
1194   // Phase 3: Eliminate
1195   // This phase performs trivial full redundancy elimination
1196   changed_function |= elimination();
1197
1198   // Phase 4: Cleanup
1199   // This phase cleans up values that were created solely
1200   // as leaders for expressions
1201   cleanup();
1202
1203   return changed_function;
1204 }