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.
  46
  47 namespace {
  48   class VISIBILITY_HIDDEN ValueTable {
  49     public:
  50       struct Expression {
  51         enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
  52                               FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
  53                               ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
  54                               ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
  55                               FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
  56                               FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
  57                               FCMPULT, FCMPULE, FCMPUNE };
  58
  59         ExpressionOpcode opcode;
  60         uint32_t leftVN;
  61         uint32_t rightVN;
  62
  63         bool operator< (const Expression& other) const {
  64           if (opcode < other.opcode)
  65             return true;
  66           else if (opcode > other.opcode)
  67             return false;
  68           else if (leftVN < other.leftVN)
  69             return true;
  70           else if (leftVN > other.leftVN)
  71             return false;
  72           else if (rightVN < other.rightVN)
  73             return true;
  74           else if (rightVN > other.rightVN)
  75             return false;
  76           else
  77             return false;
  78         }
  79       };
  80
  81     private:
  82       DenseMap<Value*, uint32_t> valueNumbering;
  83       std::map<Expression, uint32_t> expressionNumbering;
  84
  85       std::set<Expression> maximalExpressions;
  86       std::set<Value*> maximalValues;
  87
  88       uint32_t nextValueNumber;
  89
  90       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
  91       Expression::ExpressionOpcode getOpcode(CmpInst* C);
  92     public:
  93       ValueTable() { nextValueNumber = 1; }
  94       uint32_t lookup_or_add(Value* V);
  95       uint32_t lookup(Value* V);
  96       void add(Value* V, uint32_t num);
  97       void clear();
  98       std::set<Expression>& getMaximalExpressions() {
  99         return maximalExpressions;
 100
 101       }
 102       std::set<Value*>& getMaximalValues() { return maximalValues; }
 103       Expression create_expression(BinaryOperator* BO);
 104       Expression create_expression(CmpInst* C);
 105       void erase(Value* v);
 106   };
 107 }
 108
 109 ValueTable::Expression::ExpressionOpcode
 110                                      ValueTable::getOpcode(BinaryOperator* BO) {
 111   switch(BO->getOpcode()) {
 112     case Instruction::Add:
 113       return Expression::ADD;
 114     case Instruction::Sub:
 115       return Expression::SUB;
 116     case Instruction::Mul:
 117       return Expression::MUL;
 118     case Instruction::UDiv:
 119       return Expression::UDIV;
 120     case Instruction::SDiv:
 121       return Expression::SDIV;
 122     case Instruction::FDiv:
 123       return Expression::FDIV;
 124     case Instruction::URem:
 125       return Expression::UREM;
 126     case Instruction::SRem:
 127       return Expression::SREM;
 128     case Instruction::FRem:
 129       return Expression::FREM;
 130     case Instruction::Shl:
 131       return Expression::SHL;
 132     case Instruction::LShr:
 133       return Expression::LSHR;
 134     case Instruction::AShr:
 135       return Expression::ASHR;
 136     case Instruction::And:
 137       return Expression::AND;
 138     case Instruction::Or:
 139       return Expression::OR;
 140     case Instruction::Xor:
 141       return Expression::XOR;
 142
 143     // THIS SHOULD NEVER HAPPEN
 144     default:
 145       assert(0 && "Binary operator with unknown opcode?");
 146       return Expression::ADD;
 147   }
 148 }
 149
 150 ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 151   if (C->getOpcode() == Instruction::ICmp) {
 152     switch (C->getPredicate()) {
 153       case ICmpInst::ICMP_EQ:
 154         return Expression::ICMPEQ;
 155       case ICmpInst::ICMP_NE:
 156         return Expression::ICMPNE;
 157       case ICmpInst::ICMP_UGT:
 158         return Expression::ICMPUGT;
 159       case ICmpInst::ICMP_UGE:
 160         return Expression::ICMPUGE;
 161       case ICmpInst::ICMP_ULT:
 162         return Expression::ICMPULT;
 163       case ICmpInst::ICMP_ULE:
 164         return Expression::ICMPULE;
 165       case ICmpInst::ICMP_SGT:
 166         return Expression::ICMPSGT;
 167       case ICmpInst::ICMP_SGE:
 168         return Expression::ICMPSGE;
 169       case ICmpInst::ICMP_SLT:
 170         return Expression::ICMPSLT;
 171       case ICmpInst::ICMP_SLE:
 172         return Expression::ICMPSLE;
 173
 174       // THIS SHOULD NEVER HAPPEN
 175       default:
 176         assert(0 && "Comparison with unknown predicate?");
 177         return Expression::ICMPEQ;
 178     }
 179   } else {
 180     switch (C->getPredicate()) {
 181       case FCmpInst::FCMP_OEQ:
 182         return Expression::FCMPOEQ;
 183       case FCmpInst::FCMP_OGT:
 184         return Expression::FCMPOGT;
 185       case FCmpInst::FCMP_OGE:
 186         return Expression::FCMPOGE;
 187       case FCmpInst::FCMP_OLT:
 188         return Expression::FCMPOLT;
 189       case FCmpInst::FCMP_OLE:
 190         return Expression::FCMPOLE;
 191       case FCmpInst::FCMP_ONE:
 192         return Expression::FCMPONE;
 193       case FCmpInst::FCMP_ORD:
 194         return Expression::FCMPORD;
 195       case FCmpInst::FCMP_UNO:
 196         return Expression::FCMPUNO;
 197       case FCmpInst::FCMP_UEQ:
 198         return Expression::FCMPUEQ;
 199       case FCmpInst::FCMP_UGT:
 200         return Expression::FCMPUGT;
 201       case FCmpInst::FCMP_UGE:
 202         return Expression::FCMPUGE;
 203       case FCmpInst::FCMP_ULT:
 204         return Expression::FCMPULT;
 205       case FCmpInst::FCMP_ULE:
 206         return Expression::FCMPULE;
 207       case FCmpInst::FCMP_UNE:
 208         return Expression::FCMPUNE;
 209
 210       // THIS SHOULD NEVER HAPPEN
 211       default:
 212         assert(0 && "Comparison with unknown predicate?");
 213         return Expression::FCMPOEQ;
 214     }
 215   }
 216 }
 217
 218 uint32_t ValueTable::lookup_or_add(Value* V) {
 219   maximalValues.insert(V);
 220
 221   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 222   if (VI != valueNumbering.end())
 223     return VI->second;
 224
 225
 226   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 227     Expression e = create_expression(BO);
 228
 229     std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 230     if (EI != expressionNumbering.end()) {
 231       valueNumbering.insert(std::make_pair(V, EI->second));
 232       return EI->second;
 233     } else {
 234       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 235       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 236
 237       return nextValueNumber++;
 238     }
 239   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 240     Expression e = create_expression(C);
 241
 242     std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 243     if (EI != expressionNumbering.end()) {
 244       valueNumbering.insert(std::make_pair(V, EI->second));
 245       return EI->second;
 246     } else {
 247       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 248       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 249
 250       return nextValueNumber++;
 251     }
 252   } else {
 253     valueNumbering.insert(std::make_pair(V, nextValueNumber));
 254     return nextValueNumber++;
 255   }
 256 }
 257
 258 uint32_t ValueTable::lookup(Value* V) {
 259   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 260   if (VI != valueNumbering.end())
 261     return VI->second;
 262   else
 263     assert(0 && "Value not numbered?");
 264
 265   return 0;
 266 }
 267
 268 void ValueTable::add(Value* V, uint32_t num) {
 269   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 270   if (VI != valueNumbering.end())
 271     valueNumbering.erase(VI);
 272   valueNumbering.insert(std::make_pair(V, num));
 273 }
 274
 275 ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
 276   Expression e;
 277
 278   e.leftVN = lookup_or_add(BO->getOperand(0));
 279   e.rightVN = lookup_or_add(BO->getOperand(1));
 280   e.opcode = getOpcode(BO);
 281
 282   maximalExpressions.insert(e);
 283
 284   return e;
 285 }
 286
 287 ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
 288   Expression e;
 289
 290   e.leftVN = lookup_or_add(C->getOperand(0));
 291   e.rightVN = lookup_or_add(C->getOperand(1));
 292   e.opcode = getOpcode(C);
 293
 294   maximalExpressions.insert(e);
 295
 296   return e;
 297 }
 298
 299 void ValueTable::clear() {
 300   valueNumbering.clear();
 301   expressionNumbering.clear();
 302   maximalExpressions.clear();
 303   maximalValues.clear();
 304   nextValueNumber = 1;
 305 }
 306
 307 void ValueTable::erase(Value* V) {
 308   maximalValues.erase(V);
 309   valueNumbering.erase(V);
 310   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V))
 311     maximalExpressions.erase(create_expression(BO));
 312   else if (CmpInst* C = dyn_cast<CmpInst>(V))
 313     maximalExpressions.erase(create_expression(C));
 314 }
 315
 316 namespace {
 317
 318   class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
 319     bool runOnFunction(Function &F);
 320   public:
 321     static char ID; // Pass identification, replacement for typeid
 322     GVNPRE() : FunctionPass((intptr_t)&ID) { }
 323
 324   private:
 325     ValueTable VN;
 326     std::vector<Instruction*> createdExpressions;
 327
 328     std::map<BasicBlock*, std::set<Value*> > availableOut;
 329     std::map<BasicBlock*, std::set<Value*> > anticipatedIn;
 330     std::map<User*, bool> invokeDep;
 331
 332     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 333       AU.setPreservesCFG();
 334       AU.addRequired<DominatorTree>();
 335       AU.addRequired<PostDominatorTree>();
 336     }
 337
 338     // Helper fuctions
 339     // FIXME: eliminate or document these better
 340     void dump(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(bool& changed_function);
 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::elimination(bool& changed_function) {
 660   DOUT << "\n\nPhase 3: Elimination\n\n";
 661
 662   std::vector<std::pair<Instruction*, Value*> > replace;
 663   std::vector<Instruction*> erase;
 664
 665   DominatorTree& DT = getAnalysis<DominatorTree>();
 666
 667   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 668          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 669     BasicBlock* BB = DI->getBlock();
 670
 671     DOUT << "Block: " << BB->getName() << "\n";
 672     dump(availableOut[BB]);
 673     DOUT << "\n\n";
 674
 675     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 676          BI != BE; ++BI) {
 677
 678       if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
 679          Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
 680
 681         if (leader != 0)
 682           if (Instruction* Instr = dyn_cast<Instruction>(leader))
 683             if (Instr->getParent() != 0 && Instr != BI) {
 684               replace.push_back(std::make_pair(BI, leader));
 685               erase.push_back(BI);
 686               ++NumEliminated;
 687             }
 688       }
 689     }
 690   }
 691
 692   while (!replace.empty()) {
 693     std::pair<Instruction*, Value*> rep = replace.back();
 694     replace.pop_back();
 695     rep.first->replaceAllUsesWith(rep.second);
 696     changed_function = true;
 697   }
 698
 699   for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
 700        I != E; ++I)
 701      (*I)->eraseFromParent();
 702 }
 703
 704
 705 void GVNPRE::cleanup() {
 706   while (!createdExpressions.empty()) {
 707     Instruction* I = createdExpressions.back();
 708     createdExpressions.pop_back();
 709
 710     delete I;
 711   }
 712 }
 713
 714 bool GVNPRE::runOnFunction(Function &F) {
 715   VN.clear();
 716   createdExpressions.clear();
 717   availableOut.clear();
 718   anticipatedIn.clear();
 719   invokeDep.clear();
 720
 721   bool changed_function = false;
 722
 723   std::map<BasicBlock*, std::set<Value*> > generatedExpressions;
 724   std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
 725   std::map<BasicBlock*, std::set<Value*> > generatedTemporaries;
 726
 727
 728   DominatorTree &DT = getAnalysis<DominatorTree>();
 729
 730   // Phase 1: BuildSets
 731
 732   // Phase 1, Part 1: calculate AVAIL_OUT
 733
 734   // Top-down walk of the dominator tree
 735   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 736          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 737
 738     // Get the sets to update for this block
 739     std::set<Value*>& currExps = generatedExpressions[DI->getBlock()];
 740     std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
 741     std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()];
 742     std::set<Value*>& currAvail = availableOut[DI->getBlock()];
 743
 744     BasicBlock* BB = DI->getBlock();
 745
 746     // A block inherits AVAIL_OUT from its dominator
 747     if (DI->getIDom() != 0)
 748     currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
 749                      availableOut[DI->getIDom()->getBlock()].end());
 750
 751
 752     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 753          BI != BE; ++BI) {
 754
 755       // Handle PHI nodes...
 756       if (PHINode* p = dyn_cast<PHINode>(BI)) {
 757         VN.lookup_or_add(p);
 758         currPhis.insert(p);
 759
 760       // Handle binary ops...
 761       } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) {
 762         Value* leftValue = BO->getOperand(0);
 763         Value* rightValue = BO->getOperand(1);
 764
 765         VN.lookup_or_add(BO);
 766
 767         if (isa<Instruction>(leftValue))
 768           val_insert(currExps, leftValue);
 769         if (isa<Instruction>(rightValue))
 770           val_insert(currExps, rightValue);
 771         val_insert(currExps, BO);
 772
 773       // Handle cmp ops...
 774       } else if (CmpInst* C = dyn_cast<CmpInst>(BI)) {
 775         Value* leftValue = C->getOperand(0);
 776         Value* rightValue = C->getOperand(1);
 777
 778         VN.lookup_or_add(C);
 779
 780         if (isa<Instruction>(leftValue))
 781           val_insert(currExps, leftValue);
 782         if (isa<Instruction>(rightValue))
 783           val_insert(currExps, rightValue);
 784         val_insert(currExps, C);
 785
 786       // Handle unsupported ops
 787       } else if (!BI->isTerminator()){
 788         VN.lookup_or_add(BI);
 789         currTemps.insert(BI);
 790       }
 791
 792       if (!BI->isTerminator())
 793         val_insert(currAvail, BI);
 794     }
 795   }
 796
 797   DOUT << "Maximal Set: ";
 798   dump(VN.getMaximalValues());
 799   DOUT << "\n";
 800
 801   // If function has no exit blocks, only perform GVN
 802   PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
 803   if (PDT[&F.getEntryBlock()] == 0) {
 804     elimination(changed_function);
 805     cleanup();
 806
 807     return true;
 808   }
 809
 810
 811   // Phase 1, Part 2: calculate ANTIC_IN
 812
 813   std::set<BasicBlock*> visited;
 814
 815   bool changed = true;
 816   unsigned iterations = 0;
 817   while (changed) {
 818     changed = false;
 819     std::set<Value*> anticOut;
 820
 821     // Top-down walk of the postdominator tree
 822     for (df_iterator<DomTreeNode*> PDI =
 823          df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
 824          PDI != E; ++PDI) {
 825       BasicBlock* BB = PDI->getBlock();
 826       if (BB == 0)
 827         continue;
 828
 829       DOUT << "Block: " << BB->getName() << "\n";
 830       DOUT << "TMP_GEN: ";
 831       dump(generatedTemporaries[BB]);
 832       DOUT << "\n";
 833
 834       DOUT << "EXP_GEN: ";
 835       dump(generatedExpressions[BB]);
 836       visited.insert(BB);
 837
 838       std::set<Value*>& anticIn = anticipatedIn[BB];
 839       std::set<Value*> old (anticIn.begin(), anticIn.end());
 840
 841       if (BB->getTerminator()->getNumSuccessors() == 1) {
 842          if (visited.find(BB->getTerminator()->getSuccessor(0)) ==
 843              visited.end())
 844            phi_translate_set(VN.getMaximalValues(), BB,
 845                              BB->getTerminator()->getSuccessor(0),
 846                              anticOut);
 847          else
 848           phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
 849                             BB,  BB->getTerminator()->getSuccessor(0),
 850                             anticOut);
 851       } else if (BB->getTerminator()->getNumSuccessors() > 1) {
 852         BasicBlock* first = BB->getTerminator()->getSuccessor(0);
 853         anticOut.insert(anticipatedIn[first].begin(),
 854                         anticipatedIn[first].end());
 855         for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
 856           BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
 857           std::set<Value*>& succAnticIn = anticipatedIn[currSucc];
 858
 859           std::set<Value*> temp;
 860           std::insert_iterator<std::set<Value*> >  temp_ins(temp,
 861                                                             temp.begin());
 862           std::set_intersection(anticOut.begin(), anticOut.end(),
 863                                 succAnticIn.begin(), succAnticIn.end(),
 864                                 temp_ins);
 865
 866           anticOut.clear();
 867           anticOut.insert(temp.begin(), temp.end());
 868         }
 869       }
 870
 871       DOUT << "ANTIC_OUT: ";
 872       dump(anticOut);
 873       DOUT << "\n";
 874
 875       std::set<Value*> S;
 876       std::insert_iterator<std::set<Value*> >  s_ins(S, S.begin());
 877       std::set_difference(anticOut.begin(), anticOut.end(),
 878                      generatedTemporaries[BB].begin(),
 879                      generatedTemporaries[BB].end(),
 880                      s_ins);
 881
 882       anticIn.clear();
 883       std::insert_iterator<std::set<Value*> >  ai_ins(anticIn, anticIn.begin());
 884       std::set_difference(generatedExpressions[BB].begin(),
 885                      generatedExpressions[BB].end(),
 886                      generatedTemporaries[BB].begin(),
 887                      generatedTemporaries[BB].end(),
 888                      ai_ins);
 889
 890       for (std::set<Value*>::iterator I = S.begin(), E = S.end();
 891            I != E; ++I) {
 892         // For non-opaque values, we should already have a value numbering.
 893         // However, for opaques, such as constants within PHI nodes, it is
 894         // possible that they have not yet received a number.  Make sure they do
 895         // so now.
 896         uint32_t valNum = 0;
 897         if (isa<BinaryOperator>(*I) || isa<CmpInst>(*I))
 898           valNum = VN.lookup(*I);
 899         else
 900           valNum = VN.lookup_or_add(*I);
 901         if (find_leader(anticIn, valNum) == 0)
 902           val_insert(anticIn, *I);
 903       }
 904
 905       clean(anticIn);
 906
 907       DOUT << "ANTIC_IN: ";
 908       dump(anticIn);
 909       DOUT << "\n";
 910
 911       if (old.size() != anticIn.size())
 912         changed = true;
 913
 914       anticOut.clear();
 915     }
 916
 917     iterations++;
 918   }
 919
 920   DOUT << "Iterations: " << iterations << "\n";
 921
 922   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 923     DOUT << "Name: " << I->getName().c_str() << "\n";
 924
 925     DOUT << "TMP_GEN: ";
 926     dump(generatedTemporaries[I]);
 927     DOUT << "\n";
 928
 929     DOUT << "EXP_GEN: ";
 930     dump(generatedExpressions[I]);
 931     DOUT << "\n";
 932
 933     DOUT << "ANTIC_IN: ";
 934     dump(anticipatedIn[I]);
 935     DOUT << "\n";
 936
 937     DOUT << "AVAIL_OUT: ";
 938     dump(availableOut[I]);
 939     DOUT << "\n";
 940   }
 941
 942   // Phase 2: Insert
 943   DOUT<< "\nPhase 2: Insertion\n";
 944
 945   std::map<BasicBlock*, std::set<Value*> > new_sets;
 946   unsigned i_iterations = 0;
 947   bool new_stuff = true;
 948   while (new_stuff) {
 949     new_stuff = false;
 950     DOUT << "Iteration: " << i_iterations << "\n\n";
 951     for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 952          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 953       BasicBlock* BB = DI->getBlock();
 954
 955       if (BB == 0)
 956         continue;
 957
 958       std::set<Value*>& new_set = new_sets[BB];
 959       std::set<Value*>& availOut = availableOut[BB];
 960       std::set<Value*>& anticIn = anticipatedIn[BB];
 961
 962       new_set.clear();
 963
 964       // Replace leaders with leaders inherited from dominator
 965       if (DI->getIDom() != 0) {
 966         std::set<Value*>& dom_set = new_sets[DI->getIDom()->getBlock()];
 967         for (std::set<Value*>::iterator I = dom_set.begin(),
 968              E = dom_set.end(); I != E; ++I) {
 969           new_set.insert(*I);
 970           val_replace(availOut, *I);
 971         }
 972       }
 973
 974       // If there is more than one predecessor...
 975       if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
 976         std::vector<Value*> workList;
 977         topo_sort(anticIn, workList);
 978
 979         DOUT << "Merge Block: " << BB->getName() << "\n";
 980         DOUT << "ANTIC_IN: ";
 981         dump(anticIn);
 982         DOUT << "\n";
 983
 984         for (unsigned i = 0; i < workList.size(); ++i) {
 985           Value* e = workList[i];
 986
 987           if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
 988             if (find_leader(availableOut[DI->getIDom()->getBlock()], VN.lookup(e)) != 0)
 989               continue;
 990
 991             std::map<BasicBlock*, Value*> avail;
 992             bool by_some = false;
 993             int num_avail = 0;
 994
 995             for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
 996                  ++PI) {
 997               Value *e2 = phi_translate(e, *PI, BB);
 998               Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
 999
1000               if (e3 == 0) {
1001                 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1002                 if (av != avail.end())
1003                   avail.erase(av);
1004                 avail.insert(std::make_pair(*PI, e2));
1005               } else {
1006                 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1007                 if (av != avail.end())
1008                   avail.erase(av);
1009                 avail.insert(std::make_pair(*PI, e3));
1010
1011                 by_some = true;
1012                 num_avail++;
1013               }
1014             }
1015
1016             if (by_some &&
1017                 num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1018               DOUT << "Processing Value: ";
1019               DEBUG(e->dump());
1020               DOUT << "\n\n";
1021
1022               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1023                    PI != PE; ++PI) {
1024                 Value* e2 = avail[*PI];
1025                 if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
1026                   User* U = cast<User>(e2);
1027
1028                   Value* s1 = 0;
1029                   if (isa<BinaryOperator>(U->getOperand(0)) ||
1030                       isa<CmpInst>(U->getOperand(0)))
1031                     s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1032                   else
1033                     s1 = U->getOperand(0);
1034
1035                   Value* s2 = 0;
1036                   if (isa<BinaryOperator>(U->getOperand(1)) ||
1037                       isa<CmpInst>(U->getOperand(1)))
1038                     s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1039                   else
1040                     s2 = U->getOperand(1);
1041
1042                   Value* newVal = 0;
1043                   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1044                     newVal = BinaryOperator::create(BO->getOpcode(),
1045                                              s1, s2,
1046                                              BO->getName()+".gvnpre",
1047                                              (*PI)->getTerminator());
1048                   else if (CmpInst* C = dyn_cast<CmpInst>(U))
1049                     newVal = CmpInst::create(C->getOpcode(),
1050                                              C->getPredicate(),
1051                                              s1, s2,
1052                                              C->getName()+".gvnpre",
1053                                              (*PI)->getTerminator());
1054
1055                   changed_function = true;
1056
1057                   VN.add(newVal, VN.lookup(U));
1058
1059                   std::set<Value*>& predAvail = availableOut[*PI];
1060                   val_replace(predAvail, newVal);
1061
1062                   DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n";
1063
1064                   std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1065                   if (av != avail.end())
1066                     avail.erase(av);
1067                   avail.insert(std::make_pair(*PI, newVal));
1068
1069                   ++NumInsertedVals;
1070                 }
1071               }
1072
1073               PHINode* p = 0;
1074
1075               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1076                    PI != PE; ++PI) {
1077                 if (p == 0)
1078                   p = new PHINode(avail[*PI]->getType(), "gvnpre-join",
1079                                   BB->begin());
1080
1081                 p->addIncoming(avail[*PI], *PI);
1082               }
1083
1084               changed_function = true;
1085
1086               VN.add(p, VN.lookup(e));
1087               DOUT << "Creating value: " << std::hex << p << std::dec << "\n";
1088
1089               val_replace(availOut, p);
1090               availOut.insert(p);
1091
1092               new_stuff = true;
1093
1094               DOUT << "Preds After Processing: ";
1095               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1096                    PI != PE; ++PI)
1097                 DEBUG((*PI)->dump());
1098               DOUT << "\n\n";
1099
1100               DOUT << "Merge Block After Processing: ";
1101               DEBUG(BB->dump());
1102               DOUT << "\n\n";
1103
1104               new_set.insert(p);
1105
1106               ++NumInsertedPhis;
1107             }
1108           }
1109         }
1110       }
1111     }
1112     i_iterations++;
1113   }
1114
1115   // Phase 3: Eliminate
1116   elimination(changed_function);
1117
1118   // Phase 4: Cleanup
1119   cleanup();
1120
1121   return changed_function;
1122 }