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 a 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/Compiler.h"
  31 #include <algorithm>
  32 #include <map>
  33 #include <set>
  34 #include <cstdio>
  35 using namespace llvm;
  36
  37 namespace {
  38
  39   class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
  40     bool runOnFunction(Function &F);
  41   public:
  42     static char ID; // Pass identification, replacement for typeid
  43     GVNPRE() : FunctionPass((intptr_t)&ID) { nextValueNumber = 0; }
  44
  45   private:
  46     uint32_t nextValueNumber;
  47
  48     struct Expression {
  49       char opcode;
  50       Value* value;
  51       uint32_t lhs;
  52       uint32_t rhs;
  53
  54       bool operator<(const Expression& other) const {
  55         if (opcode < other.opcode)
  56           return true;
  57         else if (other.opcode < opcode)
  58           return false;
  59
  60         if (opcode == 0) {
  61           if (value < other.value)
  62             return true;
  63           else
  64             return false;
  65         } else {
  66           if (lhs < other.lhs)
  67             return true;
  68           else if (other.lhs < lhs)
  69             return true;
  70           else if (rhs < other.rhs)
  71             return true;
  72           else
  73             return false;
  74         }
  75       }
  76
  77       bool operator==(const Expression& other) const {
  78         if (opcode != other.opcode)
  79           return false;
  80
  81         if (value != other.value)
  82           return false;
  83
  84         if (lhs != other.lhs)
  85           return false;
  86
  87         if (rhs != other.rhs)
  88           return false;
  89
  90         return true;
  91       }
  92     };
  93
  94     typedef std::map<Expression, uint32_t> ValueTable;
  95
  96     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  97       AU.setPreservesCFG();
  98       AU.addRequired<DominatorTree>();
  99       AU.addRequired<PostDominatorTree>();
 100     }
 101
 102     // Helper fuctions
 103     // FIXME: eliminate or document these better
 104     void dump(ValueTable& VN, std::set<Expression>& s);
 105     void clean(ValueTable VN, std::set<Expression>& set);
 106     Expression add(ValueTable& VN, std::set<Expression>& MS, Instruction* V);
 107     ValueTable::iterator lookup(ValueTable& VN, Value* V);
 108     Expression buildExpression(ValueTable& VN, Value* V);
 109     std::set<Expression>::iterator find_leader(ValueTable VN,
 110                                                std::set<Expression>& vals,
 111                                                uint32_t v);
 112     void phi_translate(ValueTable& VN,
 113                        std::set<Expression>& anticIn, BasicBlock* B,
 114                        std::set<Expression>& out);
 115
 116     // For a given block, calculate the generated expressions, temporaries,
 117     // and the AVAIL_OUT set
 118     void CalculateAvailOut(ValueTable& VN, std::set<Expression>& MS,
 119                        DominatorTree::Node* DI,
 120                        std::set<Expression>& currExps,
 121                        std::set<PHINode*>& currPhis,
 122                        std::set<Expression>& currTemps,
 123                        std::set<Expression>& currAvail,
 124                        std::map<BasicBlock*, std::set<Expression> > availOut);
 125
 126   };
 127
 128   char GVNPRE::ID = 0;
 129
 130 }
 131
 132 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
 133
 134 RegisterPass<GVNPRE> X("gvnpre",
 135                        "Global Value Numbering/Partial Redundancy Elimination");
 136
 137 // Given a Value, build an Expression to represent it
 138 GVNPRE::Expression GVNPRE::buildExpression(ValueTable& VN, Value* V) {
 139   if (Instruction* I = dyn_cast<Instruction>(V)) {
 140     Expression e;
 141
 142     switch (I->getOpcode()) {
 143     case 7:
 144       e.opcode = 1; // ADD
 145       break;
 146     case 8:
 147       e.opcode = 2; // SUB
 148       break;
 149     case 9:
 150       e.opcode = 3; // MUL
 151       break;
 152     case 10:
 153       e.opcode = 4; // UDIV
 154       break;
 155     case 11:
 156       e.opcode = 5; // SDIV
 157       break;
 158     case 12:
 159       e.opcode = 6; // FDIV
 160       break;
 161     case 13:
 162       e.opcode = 7; // UREM
 163       break;
 164     case 14:
 165       e.opcode = 8; // SREM
 166       break;
 167     case 15:
 168       e.opcode = 9; // FREM
 169       break;
 170     default:
 171      e.opcode = 0; // OPAQUE
 172      e.lhs = 0;
 173      e.rhs = 0;
 174      e.value = V;
 175      return e;
 176     }
 177
 178     e.value = 0;
 179
 180     ValueTable::iterator lhs = lookup(VN, I->getOperand(0));
 181     if (lhs == VN.end()) {
 182       Expression lhsExp = buildExpression(VN, I->getOperand(0));
 183       VN.insert(std::make_pair(lhsExp, nextValueNumber));
 184       e.lhs = nextValueNumber;
 185       nextValueNumber++;
 186     } else
 187       e.lhs = lhs->second;
 188     ValueTable::iterator rhs = lookup(VN, I->getOperand(1));
 189     if (rhs == VN.end()) {
 190       Expression rhsExp = buildExpression(VN, I->getOperand(1));
 191       VN.insert(std::make_pair(rhsExp, nextValueNumber));
 192       e.rhs = nextValueNumber;
 193       nextValueNumber++;
 194     } else
 195       e.rhs = rhs->second;
 196
 197     return e;
 198   } else {
 199     Expression e;
 200     e.opcode = 0;
 201     e.value = V;
 202     e.lhs = 0;
 203     e.rhs = 0;
 204
 205     return e;
 206   }
 207 }
 208
 209 GVNPRE::Expression GVNPRE::add(ValueTable& VN, std::set<Expression>& MS,
 210                                Instruction* V) {
 211   Expression e = buildExpression(VN, V);
 212   if (VN.insert(std::make_pair(e, nextValueNumber)).second)
 213     nextValueNumber++;
 214   if (e.opcode != 0 || (e.opcode == 0 && isa<PHINode>(e.value)))
 215     MS.insert(e);
 216   return e;
 217 }
 218
 219 GVNPRE::ValueTable::iterator GVNPRE::lookup(ValueTable& VN, Value* V) {
 220   Expression e = buildExpression(VN, V);
 221   return VN.find(e);
 222 }
 223
 224 std::set<GVNPRE::Expression>::iterator GVNPRE::find_leader(GVNPRE::ValueTable VN,
 225                            std::set<GVNPRE::Expression>& vals,
 226                            uint32_t v) {
 227   for (std::set<Expression>::iterator I = vals.begin(), E = vals.end();
 228        I != E; ++I)
 229     if (VN[*I] == v)
 230       return I;
 231
 232   return vals.end();
 233 }
 234
 235 void GVNPRE::phi_translate(GVNPRE::ValueTable& VN,
 236                            std::set<GVNPRE::Expression>& anticIn, BasicBlock* B,
 237                            std::set<GVNPRE::Expression>& out) {
 238   BasicBlock* succ = B->getTerminator()->getSuccessor(0);
 239
 240   for (std::set<Expression>::iterator I = anticIn.begin(), E = anticIn.end();
 241        I != E; ++I) {
 242     if (I->opcode == 0) {
 243       Value *v = I->value;
 244       if (PHINode* p = dyn_cast<PHINode>(v))
 245         if (p->getParent() == succ) {
 246           out.insert(buildExpression(VN, p->getIncomingValueForBlock(B)));
 247           continue;
 248         }
 249     }
 250     //out.insert(*I);
 251   }
 252 }
 253
 254 // Remove all expressions whose operands are not themselves in the set
 255 void GVNPRE::clean(GVNPRE::ValueTable VN, std::set<GVNPRE::Expression>& set) {
 256   unsigned size = set.size();
 257   unsigned old = 0;
 258
 259   while (size != old) {
 260     old = size;
 261
 262     std::vector<Expression> worklist(set.begin(), set.end());
 263     while (!worklist.empty()) {
 264       Expression e = worklist.back();
 265       worklist.pop_back();
 266
 267       if (e.opcode == 0) // OPAQUE
 268         continue;
 269
 270       bool lhsValid = false;
 271       for (std::set<Expression>::iterator I = set.begin(), E = set.end();
 272            I != E; ++I)
 273         if (VN[*I] == e.lhs);
 274           lhsValid = true;
 275
 276       bool rhsValid = false;
 277       for (std::set<Expression>::iterator I = set.begin(), E = set.end();
 278            I != E; ++I)
 279         if (VN[*I] == e.rhs);
 280           rhsValid = true;
 281
 282       if (!lhsValid || !rhsValid)
 283         set.erase(e);
 284     }
 285
 286     size = set.size();
 287   }
 288 }
 289
 290 void GVNPRE::dump(GVNPRE::ValueTable& VN, std::set<GVNPRE::Expression>& s) {
 291   printf("{ ");
 292   for (std::set<Expression>::iterator I = s.begin(), E = s.end(); I != E; ++I) {
 293     printf("(%d, %s, value.%d, value.%d) ", I->opcode, I->value == 0 ? "0" : I->value->getName().c_str(), I->lhs, I->rhs);
 294   }
 295   printf("}\n\n");
 296 }
 297
 298 void GVNPRE::CalculateAvailOut(GVNPRE::ValueTable& VN, std::set<Expression>& MS,
 299                        DominatorTree::Node* DI,
 300                        std::set<Expression>& currExps,
 301                        std::set<PHINode*>& currPhis,
 302                        std::set<Expression>& currTemps,
 303                        std::set<Expression>& currAvail,
 304                        std::map<BasicBlock*, std::set<Expression> > availOut) {
 305
 306   BasicBlock* BB = DI->getBlock();
 307
 308   // A block inherits AVAIL_OUT from its dominator
 309   if (DI->getIDom() != 0)
 310   currAvail.insert(availOut[DI->getIDom()->getBlock()].begin(),
 311                    availOut[DI->getIDom()->getBlock()].end());
 312
 313
 314  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 315       BI != BE; ++BI) {
 316
 317     // Handle PHI nodes...
 318     if (PHINode* p = dyn_cast<PHINode>(BI)) {
 319       add(VN, MS, p);
 320       currPhis.insert(p);
 321
 322     // Handle binary ops...
 323     } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) {
 324       Expression leftValue = buildExpression(VN, BO->getOperand(0));
 325       Expression rightValue = buildExpression(VN, BO->getOperand(1));
 326
 327       Expression e = add(VN, MS, BO);
 328
 329       currExps.insert(leftValue);
 330       currExps.insert(rightValue);
 331       currExps.insert(e);
 332
 333       currTemps.insert(e);
 334
 335     // Handle unsupported ops
 336     } else {
 337       Expression e = add(VN, MS, BI);
 338       currTemps.insert(e);
 339     }
 340
 341     currAvail.insert(buildExpression(VN, BI));
 342   }
 343 }
 344
 345 bool GVNPRE::runOnFunction(Function &F) {
 346   ValueTable VN;
 347   std::set<Expression> maximalSet;
 348
 349   std::map<BasicBlock*, std::set<Expression> > generatedExpressions;
 350   std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
 351   std::map<BasicBlock*, std::set<Expression> > generatedTemporaries;
 352   std::map<BasicBlock*, std::set<Expression> > availableOut;
 353   std::map<BasicBlock*, std::set<Expression> > anticipatedIn;
 354
 355   DominatorTree &DT = getAnalysis<DominatorTree>();
 356
 357   // First Phase of BuildSets - calculate AVAIL_OUT
 358
 359   // Top-down walk of the dominator tree
 360   for (df_iterator<DominatorTree::Node*> DI = df_begin(DT.getRootNode()),
 361          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 362
 363     // Get the sets to update for this block
 364     std::set<Expression>& currExps = generatedExpressions[DI->getBlock()];
 365     std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
 366     std::set<Expression>& currTemps = generatedTemporaries[DI->getBlock()];
 367     std::set<Expression>& currAvail = availableOut[DI->getBlock()];
 368
 369     CalculateAvailOut(VN, maximalSet, *DI, currExps, currPhis,
 370                       currTemps, currAvail, availableOut);
 371   }
 372
 373   PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
 374
 375   // Second Phase of BuildSets - calculate ANTIC_IN
 376
 377   bool changed = true;
 378   unsigned iterations = 0;
 379   while (changed) {
 380     changed = false;
 381     std::set<Expression> anticOut;
 382
 383     // Top-down walk of the postdominator tree
 384     for (df_iterator<PostDominatorTree::Node*> PDI =
 385          df_begin(PDT.getRootNode()), E = df_end(DT.getRootNode());
 386          PDI != E; ++PDI) {
 387       BasicBlock* BB = PDI->getBlock();
 388
 389       std::set<Expression>& anticIn = anticipatedIn[BB];
 390       std::set<Expression> old (anticIn.begin(), anticIn.end());
 391
 392       if (BB->getTerminator()->getNumSuccessors() == 1) {
 393          phi_translate(VN, anticIn, BB, anticOut);
 394       } else if (BB->getTerminator()->getNumSuccessors() > 1) {
 395         for (unsigned i = 0; i < BB->getTerminator()->getNumSuccessors(); ++i) {
 396           BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
 397           std::set<Expression> temp;
 398           if (i == 0)
 399             temp.insert(maximalSet.begin(), maximalSet.end());
 400           else
 401             temp.insert(anticIn.begin(), anticIn.end());
 402
 403           anticIn.clear();
 404           std::insert_iterator<std::set<Expression> >  ai_ins(anticIn,
 405                                                        anticIn.begin());
 406
 407           std::set_difference(anticipatedIn[currSucc].begin(),
 408                               anticipatedIn[currSucc].end(),
 409                               temp.begin(),
 410                               temp.end(),
 411                               ai_ins);
 412         }
 413       }
 414
 415       std::set<Expression> S;
 416       std::insert_iterator<std::set<Expression> >  s_ins(S, S.begin());
 417       std::set_union(anticOut.begin(), anticOut.end(),
 418                      generatedExpressions[BB].begin(),
 419                      generatedExpressions[BB].end(),
 420                      s_ins);
 421
 422       anticIn.clear();
 423       std::insert_iterator<std::set<Expression> >  antic_ins(anticIn,
 424                                                              anticIn.begin());
 425       std::set_difference(S.begin(), S.end(),
 426                           generatedTemporaries[BB].begin(),
 427                           generatedTemporaries[BB].end(),
 428                           antic_ins);
 429
 430       clean(VN, anticIn);
 431
 432
 433
 434       if (old != anticIn)
 435         changed = true;
 436
 437       anticOut.clear();
 438     }
 439     iterations++;
 440   }
 441
 442   /* printf("Iterations: %d\n", iterations);
 443
 444   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 445     printf("Name: ");
 446     printf(I->getName().c_str());
 447     printf("\nTMP_GEN: ");
 448     dump(VN, generatedTemporaries[I]);
 449     printf("\nEXP_GEN: ");
 450     dump(VN, generatedExpressions[I]);
 451     //printf("\nANTIC_OUT: ");
 452     //dump(VN, anticipatedOut[I]);
 453     printf("\nANTIC_IN: \n");
 454     dump(VN, anticipatedIn[I]);
 455     printf("\n");
 456   } */
 457
 458   return false;
 459 }