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