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