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
  33 inline static bool
  34 ConstantFoldUnaryInst(Method *M, Method::inst_iterator &DI,
  35                       UnaryOperator *Op, ConstPoolVal *D) {
  36   ConstPoolVal *ReplaceWith =
  37     opt::ConstantFoldUnaryInstruction(Op->getOpcode(), D);
  38
  39   if (!ReplaceWith) return false;   // Nothing new to change...
  40
  41   // Replaces all of the uses of a variable with uses of the constant.
  42   Op->replaceAllUsesWith(ReplaceWith);
  43
  44   // Remove the operator from the list of definitions...
  45   Op->getParent()->getInstList().remove(DI.getInstructionIterator());
  46
  47   // The new constant inherits the old name of the operator...
  48   if (Op->hasName())
  49     ReplaceWith->setName(Op->getName(), M->getSymbolTableSure());
  50
  51   // Delete the operator now...
  52   delete Op;
  53   return true;
  54 }
  55
  56 inline static bool
  57 ConstantFoldBinaryInst(Method *M, Method::inst_iterator &DI,
  58                        BinaryOperator *Op,
  59                        ConstPoolVal *D1, ConstPoolVal *D2) {
  60   ConstPoolVal *ReplaceWith =
  61     opt::ConstantFoldBinaryInstruction(Op->getOpcode(), D1, D2);
  62   if (!ReplaceWith) return false;   // Nothing new to change...
  63
  64   // Replaces all of the uses of a variable with uses of the constant.
  65   Op->replaceAllUsesWith(ReplaceWith);
  66
  67   // Remove the operator from the list of definitions...
  68   Op->getParent()->getInstList().remove(DI.getInstructionIterator());
  69
  70   // The new constant inherits the old name of the operator...
  71   if (Op->hasName())
  72     ReplaceWith->setName(Op->getName(), M->getSymbolTableSure());
  73
  74   // Delete the operator now...
  75   delete Op;
  76   return true;
  77 }
  78
  79 // ConstantFoldTerminator - If a terminator instruction is predicated on a
  80 // constant value, convert it into an unconditional branch to the constant
  81 // destination.
  82 //
  83 bool opt::ConstantFoldTerminator(TerminatorInst *T) {
  84   // Branch - See if we are conditional jumping on constant
  85   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
  86     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
  87     BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
  88     BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
  89
  90     if (ConstPoolBool *Cond = dyn_cast<ConstPoolBool>(BI->getCondition())) {
  91       // Are we branching on constant?
  92       // YES.  Change to unconditional branch...
  93       BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
  94       BasicBlock *OldDest     = Cond->getValue() ? Dest2 : Dest1;
  95
  96       //cerr << "Method: " << T->getParent()->getParent()
  97       //     << "\nRemoving branch from " << T->getParent()
  98       //     << "\n\nTo: " << OldDest << endl;
  99
 100       // Let the basic block know that we are letting go of it.  Based on this,
 101       // it will adjust it's PHI nodes.
 102       assert(BI->getParent() && "Terminator not inserted in block!");
 103       OldDest->removePredecessor(BI->getParent());
 104
 105       // Set the unconditional destination, and change the insn to be an
 106       // unconditional branch.
 107       BI->setUnconditionalDest(Destination);
 108       return true;
 109     }
 110 #if 0
 111     // FIXME: TODO: This doesn't work if the destination has PHI nodes with
 112     // different incoming values on each branch!
 113     //
 114     else if (Dest2 == Dest1) {       // Conditional branch to same location?
 115       // This branch matches something like this:
 116       //     br bool %cond, label %Dest, label %Dest
 117       // and changes it into:  br label %Dest
 118
 119       // Let the basic block know that we are letting go of one copy of it.
 120       assert(BI->getParent() && "Terminator not inserted in block!");
 121       Dest1->removePredecessor(BI->getParent());
 122
 123       // Change a conditional branch to unconditional.
 124       BI->setUnconditionalDest(Dest1);
 125       return true;
 126     }
 127 #endif
 128   }
 129   return false;
 130 }
 131
 132 // ConstantFoldInstruction - If an instruction references constants, try to fold
 133 // them together...
 134 //
 135 inline static bool
 136 ConstantFoldInstruction(Method *M, Method::inst_iterator &II) {
 137   Instruction *Inst = *II;
 138   if (BinaryOperator *BInst = dyn_cast<BinaryOperator>(Inst)) {
 139     ConstPoolVal *D1 = dyn_cast<ConstPoolVal>(Inst->getOperand(0));
 140     ConstPoolVal *D2 = dyn_cast<ConstPoolVal>(Inst->getOperand(1));
 141
 142     if (D1 && D2)
 143       return ConstantFoldBinaryInst(M, II, cast<BinaryOperator>(Inst), D1, D2);
 144
 145   } else if (UnaryOperator *UInst = dyn_cast<UnaryOperator>(Inst)) {
 146     ConstPoolVal *D = dyn_cast<ConstPoolVal>(UInst->getOperand(0));
 147     if (D) return ConstantFoldUnaryInst(M, II, UInst, D);
 148   } else if (TerminatorInst *TInst = dyn_cast<TerminatorInst>(Inst)) {
 149     return opt::ConstantFoldTerminator(TInst);
 150
 151   } else if (PHINode *PN = dyn_cast<PHINode>(Inst)) {
 152     // If it's a PHI node and only has one operand
 153     // Then replace it directly with that operand.
 154     assert(PN->getOperand(0) && "PHI Node must have at least one operand!");
 155     if (PN->getNumOperands() == 1) {    // If the PHI Node has exactly 1 operand
 156       Value *V = PN->getOperand(0);
 157       PN->replaceAllUsesWith(V);                 // Replace all uses of this PHI
 158                                                  // Unlink from basic block
 159       PN->getParent()->getInstList().remove(II.getInstructionIterator());
 160       if (PN->hasName())                         // Inherit PHINode name
 161         V->setName(PN->getName(), M->getSymbolTableSure());
 162       delete PN;                                 // Finally, delete the node...
 163       return true;
 164     }
 165   }
 166   return false;
 167 }
 168
 169 // DoConstPropPass - Propogate constants and do constant folding on instructions
 170 // this returns true if something was changed, false if nothing was changed.
 171 //
 172 static bool DoConstPropPass(Method *M) {
 173   bool SomethingChanged = false;
 174
 175 #if 1
 176   Method::inst_iterator It = M->inst_begin();
 177   while (It != M->inst_end())
 178     if (ConstantFoldInstruction(M, It)) {
 179       SomethingChanged = true;  // If returned true, iter is already incremented
 180
 181       // Incrementing the iterator in an unchecked manner could mess up the
 182       // internals of 'It'.  To make sure everything is happy, tell it we might
 183       // have broken it.
 184       It.resyncInstructionIterator();
 185     } else {
 186       ++It;
 187     }
 188 #else
 189   for (Method::iterator BBIt = M->begin(); BBIt != M->end(); ++BBIt) {
 190     BasicBlock *BB = *BBIt;
 191
 192     reduce_apply_bool(BB->begin(), BB->end(),
 193                       bind1st(ConstantFoldInstruction, M));
 194   }
 195 #endif
 196   return SomethingChanged;
 197 }
 198
 199
 200 // returns true on failure, false on success...
 201 //
 202 bool opt::ConstantPropogation::doConstantPropogation(Method *M) {
 203   bool Modified = false;
 204
 205   // Fold constants until we make no progress...
 206   while (DoConstPropPass(M)) Modified = true;
 207
 208   return Modified;
 209 }