lib/Transforms/Scalar/ConstantProp.cpp

   1 //===- ConstantProp.cpp - Code to perform Constant Propogation ------------===//
   2 //
   3 // This file implements constant propogation and merging:
   4 //
   5 // Specifically, this:
   6 //   * Folds multiple identical constants in the constant pool together
   7 //     Note that if one is named and the other is not, that the result gets the
   8 //     original name.
   9 //   * Converts instructions like "add int %1, %2" into a direct def of %3 in
  10 //     the constant pool
  11 //   * Converts conditional branches on a constant boolean value into direct
  12 //     branches.
  13 //   * Converts phi nodes with one incoming def to the incoming def directly
  14 //   . Converts switch statements with one entry into a test & conditional
  15 //     branch
  16 //   . Converts switches on constant values into an unconditional branch.
  17 //
  18 // Notice that:
  19 //   * This pass has a habit of making definitions be dead.  It is a good idea
  20 //     to to run a DCE pass sometime after running this pass.
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #include "llvm/Optimizations/ConstantProp.h"
  25 #include "llvm/Optimizations/ConstantHandling.h"
  26 #include "llvm/Module.h"
  27 #include "llvm/Method.h"
  28 #include "llvm/BasicBlock.h"
  29 #include "llvm/iTerminators.h"
  30 #include "llvm/iOther.h"
  31 #include "llvm/ConstPoolVals.h"
  32 #include "llvm/ConstantPool.h"
  33
  34 // Merge identical constant values in the constant pool.
  35 //
  36 // TODO: We can do better than this simplistic N^2 algorithm...
  37 //
  38 bool opt::DoConstantPoolMerging(Method *M) {
  39   return DoConstantPoolMerging(M->getConstantPool());
  40 }
  41
  42 bool opt::DoConstantPoolMerging(ConstantPool &CP) {
  43   bool Modified = false;
  44   for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI) {
  45     for (ConstantPool::PlaneType::iterator I = (*PI)->begin();
  46          I != (*PI)->end(); ++I) {
  47       ConstPoolVal *C = *I;
  48
  49       ConstantPool::PlaneType::iterator J = I;
  50       for (++J; J != (*PI)->end(); ++J) {
  51         if (C->equals(*J)) {
  52           Modified = true;
  53           // Okay we know that *I == *J.  So now we need to make all uses of *I
  54           // point to *J.
  55           //
  56           C->replaceAllUsesWith(*J);
  57
  58           (*PI)->remove(I); // Remove C from constant pool...
  59
  60           if (C->hasName() && !(*J)->hasName())  // The merged constant inherits
  61             (*J)->setName(C->getName());         // the old name...
  62
  63           delete C;                              // Delete the constant itself.
  64           break;  // Break out of inner for loop
  65         }
  66       }
  67     }
  68   }
  69   return Modified;
  70 }
  71
  72 inline static bool
  73 ConstantFoldUnaryInst(Method *M, Method::inst_iterator &DI,
  74                       UnaryOperator *Op, ConstPoolVal *D) {
  75   ConstPoolVal *ReplaceWith =
  76     opt::ConstantFoldUnaryInstruction(Op->getInstType(), D);
  77
  78   if (!ReplaceWith) return false;   // Nothing new to change...
  79
  80
  81   // Add the new value to the constant pool...
  82   M->getConstantPool().insert(ReplaceWith);
  83
  84   // Replaces all of the uses of a variable with uses of the constant.
  85   Op->replaceAllUsesWith(ReplaceWith);
  86
  87   // Remove the operator from the list of definitions...
  88   Op->getParent()->getInstList().remove(DI.getInstructionIterator());
  89
  90   // The new constant inherits the old name of the operator...
  91   if (Op->hasName()) ReplaceWith->setName(Op->getName());
  92
  93   // Delete the operator now...
  94   delete Op;
  95   return true;
  96 }
  97
  98 inline static bool
  99 ConstantFoldBinaryInst(Method *M, Method::inst_iterator &DI,
 100                        BinaryOperator *Op,
 101                        ConstPoolVal *D1, ConstPoolVal *D2) {
 102   ConstPoolVal *ReplaceWith =
 103     opt::ConstantFoldBinaryInstruction(Op->getInstType(), D1, D2);
 104   if (!ReplaceWith) return false;   // Nothing new to change...
 105
 106   // Add the new value to the constant pool...
 107   M->getConstantPool().insert(ReplaceWith);
 108
 109   // Replaces all of the uses of a variable with uses of the constant.
 110   Op->replaceAllUsesWith(ReplaceWith);
 111
 112   // Remove the operator from the list of definitions...
 113   Op->getParent()->getInstList().remove(DI.getInstructionIterator());
 114
 115   // The new constant inherits the old name of the operator...
 116   if (Op->hasName()) ReplaceWith->setName(Op->getName());
 117
 118   // Delete the operator now...
 119   delete Op;
 120   return true;
 121 }
 122
 123 // ConstantFoldTerminator - If a terminator instruction is predicated on a
 124 // constant value, convert it into an unconditional branch to the constant
 125 // destination.
 126 //
 127 bool opt::ConstantFoldTerminator(TerminatorInst *T) {
 128   // Branch - See if we are conditional jumping on constant
 129   if (T->getInstType() == Instruction::Br) {
 130     BranchInst *BI = (BranchInst*)T;
 131     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
 132     BasicBlock *Dest1 = BI->getOperand(0)->castBasicBlockAsserting();
 133     BasicBlock *Dest2 = BI->getOperand(1)->castBasicBlockAsserting();
 134
 135     if (BI->getOperand(2)->isConstant()) {    // Are we branching on constant?
 136       // YES.  Change to unconditional branch...
 137       ConstPoolBool *Cond = (ConstPoolBool*)BI->getOperand(2);
 138       BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
 139       BasicBlock *OldDest     = Cond->getValue() ? Dest2 : Dest1;
 140
 141       //cerr << "Method: " << T->getParent()->getParent()
 142       //     << "\nRemoving branch from " << T->getParent()
 143       //     << "\n\nTo: " << OldDest << endl;
 144
 145       // Let the basic block know that we are letting go of it.  Based on this,
 146       // it will adjust it's PHI nodes.
 147       assert(BI->getParent() && "Terminator not inserted in block!");
 148       OldDest->removePredecessor(BI->getParent());
 149
 150       BI->setOperand(0, Destination);  // Set the unconditional destination
 151       BI->setOperand(1, 0);            // Clear the conditional destination
 152       BI->setOperand(2, 0);            // Clear the condition...
 153       return true;
 154     } else if (Dest2 == Dest1) {       // Conditional branch to same location?
 155       // This branch matches something like this:
 156       //     br bool %cond, label %Dest, label %Dest
 157       // and changes it into:  br label %Dest
 158
 159       // Let the basic block know that we are letting go of one copy of it.
 160       assert(BI->getParent() && "Terminator not inserted in block!");
 161       Dest1->removePredecessor(BI->getParent());
 162
 163       // Nuke the second destination, and the use of the condition variable
 164       BI->setOperand(1, 0);            // Clear the conditional destination
 165       BI->setOperand(2, 0);            // Clear the condition...
 166       return true;
 167     }
 168   }
 169   return false;
 170 }
 171
 172 // ConstantFoldInstruction - If an instruction references constants, try to fold
 173 // them together...
 174 //
 175 inline static bool
 176 ConstantFoldInstruction(Method *M, Method::inst_iterator &II) {
 177   Instruction *Inst = *II;
 178   if (Inst->isBinaryOp()) {
 179     ConstPoolVal *D1 = Inst->getOperand(0)->castConstant();
 180     ConstPoolVal *D2 = Inst->getOperand(1)->castConstant();
 181
 182     if (D1 && D2)
 183       return ConstantFoldBinaryInst(M, II, (BinaryOperator*)Inst, D1, D2);
 184
 185   } else if (Inst->isUnaryOp()) {
 186     ConstPoolVal *D = Inst->getOperand(0)->castConstant();
 187     if (D) return ConstantFoldUnaryInst(M, II, (UnaryOperator*)Inst, D);
 188   } else if (Inst->isTerminator()) {
 189     return opt::ConstantFoldTerminator((TerminatorInst*)Inst);
 190
 191   } else if (Inst->isPHINode()) {
 192     PHINode *PN = (PHINode*)Inst; // If it's a PHI node and only has one operand
 193                                   // Then replace it directly with that operand.
 194     assert(PN->getOperand(0) && "PHI Node must have at least one operand!");
 195     if (PN->getOperand(1) == 0) {       // If the PHI Node has exactly 1 operand
 196       Value *V = PN->getOperand(0);
 197       PN->replaceAllUsesWith(V);                 // Replace all uses of this PHI
 198                                                  // Unlink from basic block
 199       PN->getParent()->getInstList().remove(II.getInstructionIterator());
 200       if (PN->hasName()) V->setName(PN->getName()); // Inherit PHINode name
 201       delete PN;                                 // Finally, delete the node...
 202       return true;
 203     }
 204   }
 205   return false;
 206 }
 207
 208 // DoConstPropPass - Propogate constants and do constant folding on instructions
 209 // this returns true if something was changed, false if nothing was changed.
 210 //
 211 static bool DoConstPropPass(Method *M) {
 212   bool SomethingChanged = false;
 213
 214 #if 1
 215   Method::inst_iterator It = M->inst_begin();
 216   while (It != M->inst_end())
 217     if (ConstantFoldInstruction(M, It)) {
 218       SomethingChanged = true;  // If returned true, iter is already incremented
 219
 220       // Incrementing the iterator in an unchecked manner could mess up the
 221       // internals of 'It'.  To make sure everything is happy, tell it we might
 222       // have broken it.
 223       It.resyncInstructionIterator();
 224     } else {
 225       ++It;
 226     }
 227 #else
 228   for (Method::iterator BBIt = M->begin(); BBIt != M->end(); ++BBIt) {
 229     BasicBlock *BB = *BBIt;
 230
 231     reduce_apply_bool(BB->begin(), BB->end(),
 232                       bind1st(ConstantFoldInstruction, M));
 233   }
 234 #endif
 235   return SomethingChanged;
 236 }
 237
 238
 239 // returns true on failure, false on success...
 240 //
 241 bool opt::DoConstantPropogation(Method *M) {
 242   bool Modified = false;
 243
 244   // Fold constants until we make no progress...
 245   while (DoConstPropPass(M)) Modified = true;
 246
 247   // Merge identical constants last: this is important because we may have just
 248   // introduced constants that already exist!
 249   //
 250   Modified |= DoConstantPoolMerging(M->getConstantPool());
 251
 252   return Modified;
 253 }