lib/Transforms/Scalar/GCSE.cpp

   1 //===-- GCSE.cpp - SSA based Global Common Subexpr Elimination ------------===//
   2 //
   3 // This pass is designed to be a very quick global transformation that
   4 // eliminates global common subexpressions from a function.  It does this by
   5 // examining the SSA value graph of the function, instead of doing slow, dense,
   6 // bit-vector computations.
   7 //
   8 // This pass works best if it is proceeded with a simple constant propogation
   9 // pass and an instruction combination pass because this pass does not do any
  10 // value numbering (in order to be speedy).
  11 //
  12 // This pass does not attempt to CSE load instructions, because it does not use
  13 // pointer analysis to determine when it is safe.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/InstrTypes.h"
  19 #include "llvm/iMemory.h"
  20 #include "llvm/Analysis/Dominators.h"
  21 #include "llvm/Support/InstVisitor.h"
  22 #include "llvm/Support/InstIterator.h"
  23 #include <algorithm>
  24
  25 namespace {
  26   class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> {
  27     set<Instruction*> WorkList;
  28     DominatorSet        *DomSetInfo;
  29     ImmediateDominators *ImmDominator;
  30   public:
  31     const char *getPassName() const {
  32       return "Global Common Subexpression Elimination";
  33     }
  34
  35     virtual bool runOnFunction(Function *F);
  36
  37     // Visitation methods, these are invoked depending on the type of
  38     // instruction being checked.  They should return true if a common
  39     // subexpression was folded.
  40     //
  41     bool visitUnaryOperator(Instruction *I);
  42     bool visitBinaryOperator(Instruction *I);
  43     bool visitGetElementPtrInst(GetElementPtrInst *I);
  44     bool visitCastInst(CastInst *I){return visitUnaryOperator((Instruction*)I);}
  45     bool visitShiftInst(ShiftInst *I) {
  46       return visitBinaryOperator((Instruction*)I);
  47     }
  48     bool visitInstruction(Instruction *) { return false; }
  49
  50   private:
  51     void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
  52     void CommonSubExpressionFound(Instruction *I, Instruction *Other);
  53
  54     // This transformation requires dominator and immediate dominator info
  55     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  56       AU.preservesCFG();
  57       AU.addRequired(DominatorSet::ID);
  58       AU.addRequired(ImmediateDominators::ID);
  59     }
  60   };
  61 }
  62
  63 // createGCSEPass - The public interface to this file...
  64 Pass *createGCSEPass() { return new GCSE(); }
  65
  66
  67 // GCSE::runOnFunction - This is the main transformation entry point for a
  68 // function.
  69 //
  70 bool GCSE::runOnFunction(Function *F) {
  71   bool Changed = false;
  72
  73   DomSetInfo = &getAnalysis<DominatorSet>();
  74   ImmDominator = &getAnalysis<ImmediateDominators>();
  75
  76   // Step #1: Add all instructions in the function to the worklist for
  77   // processing.  All of the instructions are considered to be our
  78   // subexpressions to eliminate if possible.
  79   //
  80   WorkList.insert(inst_begin(F), inst_end(F));
  81
  82   // Step #2: WorkList processing.  Iterate through all of the instructions,
  83   // checking to see if there are any additionally defined subexpressions in the
  84   // program.  If so, eliminate them!
  85   //
  86   while (!WorkList.empty()) {
  87     Instruction *I = *WorkList.begin();  // Get an instruction from the worklist
  88     WorkList.erase(WorkList.begin());
  89
  90     // Visit the instruction, dispatching to the correct visit function based on
  91     // the instruction type.  This does the checking.
  92     //
  93     Changed |= visit(I);
  94   }
  95
  96   // When the worklist is empty, return whether or not we changed anything...
  97   return Changed;
  98 }
  99
 100
 101 // ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all
 102 // uses of the instruction use First now instead.
 103 //
 104 void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) {
 105   Instruction *Second = *SI;
 106
 107   //cerr << "DEL " << (void*)Second << Second;
 108
 109   // Add the first instruction back to the worklist
 110   WorkList.insert(First);
 111
 112   // Add all uses of the second instruction to the worklist
 113   for (Value::use_iterator UI = Second->use_begin(), UE = Second->use_end();
 114        UI != UE; ++UI)
 115     WorkList.insert(cast<Instruction>(*UI));
 116
 117   // Make all users of 'Second' now use 'First'
 118   Second->replaceAllUsesWith(First);
 119
 120   // Erase the second instruction from the program
 121   delete Second->getParent()->getInstList().remove(SI);
 122 }
 123
 124 // CommonSubExpressionFound - The two instruction I & Other have been found to
 125 // be common subexpressions.  This function is responsible for eliminating one
 126 // of them, and for fixing the worklist to be correct.
 127 //
 128 void GCSE::CommonSubExpressionFound(Instruction *I, Instruction *Other) {
 129   // I has already been removed from the worklist, Other needs to be.
 130   assert(I != Other && WorkList.count(I) == 0 && "I shouldn't be on worklist!");
 131
 132   WorkList.erase(Other); // Other may not actually be on the worklist anymore...
 133
 134   // Handle the easy case, where both instructions are in the same basic block
 135   BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
 136   if (BB1 == BB2) {
 137     // Eliminate the second occuring instruction.  Add all uses of the second
 138     // instruction to the worklist.
 139     //
 140     // Scan the basic block looking for the "first" instruction
 141     BasicBlock::iterator BI = BB1->begin();
 142     while (*BI != I && *BI != Other) {
 143       ++BI;
 144       assert(BI != BB1->end() && "Instructions not found in parent BB!");
 145     }
 146
 147     // Keep track of which instructions occurred first & second
 148     Instruction *First = *BI;
 149     Instruction *Second = I != First ? I : Other; // Get iterator to second inst
 150     BI = find(BI, BB1->end(), Second);
 151     assert(BI != BB1->end() && "Second instruction not found in parent block!");
 152
 153     // Destroy Second, using First instead.
 154     ReplaceInstWithInst(First, BI);
 155
 156     // Otherwise, the two instructions are in different basic blocks.  If one
 157     // dominates the other instruction, we can simply use it
 158     //
 159   } else if (DomSetInfo->dominates(BB1, BB2)) {    // I dom Other?
 160     BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other);
 161     assert(BI != BB2->end() && "Other not in parent basic block!");
 162     ReplaceInstWithInst(I, BI);
 163   } else if (DomSetInfo->dominates(BB2, BB1)) {    // Other dom I?
 164     BasicBlock::iterator BI = find(BB1->begin(), BB1->end(), I);
 165     assert(BI != BB1->end() && "I not in parent basic block!");
 166     ReplaceInstWithInst(Other, BI);
 167   } else {
 168     // Handle the most general case now.  In this case, neither I dom Other nor
 169     // Other dom I.  Because we are in SSA form, we are guaranteed that the
 170     // operands of the two instructions both dominate the uses, so we _know_
 171     // that there must exist a block that dominates both instructions (if the
 172     // operands of the instructions are globals or constants, worst case we
 173     // would get the entry node of the function).  Search for this block now.
 174     //
 175
 176     // Search up the immediate dominator chain of BB1 for the shared dominator
 177     BasicBlock *SharedDom = (*ImmDominator)[BB1];
 178     while (!DomSetInfo->dominates(SharedDom, BB2))
 179       SharedDom = (*ImmDominator)[SharedDom];
 180
 181     // At this point, shared dom must dominate BOTH BB1 and BB2...
 182     assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) &&
 183            DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!");
 184
 185     // Rip 'I' out of BB1, and move it to the end of SharedDom.
 186     BB1->getInstList().remove(I);
 187     SharedDom->getInstList().insert(SharedDom->end()-1, I);
 188
 189     // Eliminate 'Other' now.
 190     BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other);
 191     assert(BI != BB2->end() && "I not in parent basic block!");
 192     ReplaceInstWithInst(I, BI);
 193   }
 194 }
 195
 196 //===----------------------------------------------------------------------===//
 197 //
 198 // Visitation methods, these are invoked depending on the type of instruction
 199 // being checked.  They should return true if a common subexpression was folded.
 200 //
 201 //===----------------------------------------------------------------------===//
 202
 203 bool GCSE::visitUnaryOperator(Instruction *I) {
 204   Value *Op = I->getOperand(0);
 205   Function *F = I->getParent()->getParent();
 206
 207   for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
 208        UI != UE; ++UI)
 209     if (Instruction *Other = dyn_cast<Instruction>(*UI))
 210       // Check to see if this new binary operator is not I, but same operand...
 211       if (Other != I && Other->getOpcode() == I->getOpcode() &&
 212           Other->getOperand(0) == Op &&     // Is the operand the same?
 213           // Is it embeded in the same function?  (This could be false if LHS
 214           // is a constant or global!)
 215           Other->getParent()->getParent() == F &&
 216
 217           // Check that the types are the same, since this code handles casts...
 218           Other->getType() == I->getType()) {
 219
 220         // These instructions are identical.  Handle the situation.
 221         CommonSubExpressionFound(I, Other);
 222         return true;   // One instruction eliminated!
 223       }
 224
 225   return false;
 226 }
 227
 228 bool GCSE::visitBinaryOperator(Instruction *I) {
 229   Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
 230   Function *F = I->getParent()->getParent();
 231
 232   for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
 233        UI != UE; ++UI)
 234     if (Instruction *Other = dyn_cast<Instruction>(*UI))
 235       // Check to see if this new binary operator is not I, but same operand...
 236       if (Other != I && Other->getOpcode() == I->getOpcode() &&
 237           // Are the LHS and RHS the same?
 238           Other->getOperand(0) == LHS && Other->getOperand(1) == RHS &&
 239           // Is it embeded in the same function?  (This could be false if LHS
 240           // is a constant or global!)
 241           Other->getParent()->getParent() == F) {
 242
 243         // These instructions are identical.  Handle the situation.
 244         CommonSubExpressionFound(I, Other);
 245         return true;   // One instruction eliminated!
 246       }
 247
 248   return false;
 249 }
 250
 251 bool GCSE::visitGetElementPtrInst(GetElementPtrInst *I) {
 252   Value *Op = I->getOperand(0);
 253   Function *F = I->getParent()->getParent();
 254
 255   for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
 256        UI != UE; ++UI)
 257     if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI))
 258       // Check to see if this new binary operator is not I, but same operand...
 259       if (Other != I && Other->getParent()->getParent() == F &&
 260           Other->getType() == I->getType()) {
 261
 262         // Check to see that all operators past the 0th are the same...
 263         unsigned i = 1, e = I->getNumOperands();
 264         for (; i != e; ++i)
 265           if (I->getOperand(i) != Other->getOperand(i)) break;
 266
 267         if (i == e) {
 268           // These instructions are identical.  Handle the situation.
 269           CommonSubExpressionFound(I, Other);
 270           return true;   // One instruction eliminated!
 271         }
 272       }
 273
 274   return false;
 275 }