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