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/Transforms/Scalar/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 #include "llvm/ConstantVals.h"
  34
  35 inline static bool
  36 ConstantFoldUnaryInst(BasicBlock *BB, BasicBlock::iterator &II,
  37                       UnaryOperator *Op, Constant *D) {
  38   Constant *ReplaceWith = 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, Constant *D) {
  60   Constant *ReplaceWith = ConstantFoldCastInstruction(D, CI->getType());
  61
  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   CI->replaceAllUsesWith(ReplaceWith);
  66
  67   // Remove the cast from the list of definitions...
  68   CI->getParent()->getInstList().remove(II);
  69
  70   // The new constant inherits the old name of the cast...
  71   if (CI->hasName())
  72     ReplaceWith->setName(CI->getName(), BB->getParent()->getSymbolTableSure());
  73
  74   // Delete the cast now...
  75   delete CI;
  76   return true;
  77 }
  78
  79 inline static bool
  80 ConstantFoldBinaryInst(BasicBlock *BB, BasicBlock::iterator &II,
  81                        BinaryOperator *Op,
  82                        Constant *D1, Constant *D2) {
  83   Constant *ReplaceWith = ConstantFoldBinaryInstruction(Op->getOpcode(), D1,D2);
  84   if (!ReplaceWith) return false;   // Nothing new to change...
  85
  86   // Replaces all of the uses of a variable with uses of the constant.
  87   Op->replaceAllUsesWith(ReplaceWith);
  88
  89   // Remove the operator from the list of definitions...
  90   Op->getParent()->getInstList().remove(II);
  91
  92   // The new constant inherits the old name of the operator...
  93   if (Op->hasName())
  94     ReplaceWith->setName(Op->getName(), BB->getParent()->getSymbolTableSure());
  95
  96   // Delete the operator now...
  97   delete Op;
  98   return true;
  99 }
 100
 101 // ConstantFoldTerminator - If a terminator instruction is predicated on a
 102 // constant value, convert it into an unconditional branch to the constant
 103 // destination.
 104 //
 105 bool ConstantFoldTerminator(BasicBlock *BB, BasicBlock::iterator &II,
 106                             TerminatorInst *T) {
 107   // Branch - See if we are conditional jumping on constant
 108   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
 109     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
 110     BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
 111     BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
 112
 113     if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
 114       // Are we branching on constant?
 115       // YES.  Change to unconditional branch...
 116       BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
 117       BasicBlock *OldDest     = Cond->getValue() ? Dest2 : Dest1;
 118
 119       //cerr << "Function: " << T->getParent()->getParent()
 120       //     << "\nRemoving branch from " << T->getParent()
 121       //     << "\n\nTo: " << OldDest << endl;
 122
 123       // Let the basic block know that we are letting go of it.  Based on this,
 124       // it will adjust it's PHI nodes.
 125       assert(BI->getParent() && "Terminator not inserted in block!");
 126       OldDest->removePredecessor(BI->getParent());
 127
 128       // Set the unconditional destination, and change the insn to be an
 129       // unconditional branch.
 130       BI->setUnconditionalDest(Destination);
 131       II = BB->end()-1;  // Update instruction iterator!
 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 doConstantPropogation(BasicBlock *BB, BasicBlock::iterator &II) {
 160   Instruction *Inst = *II;
 161   if (isa<BinaryOperator>(Inst)) {
 162     Constant *D1 = dyn_cast<Constant>(Inst->getOperand(0));
 163     Constant *D2 = dyn_cast<Constant>(Inst->getOperand(1));
 164
 165     if (D1 && D2)
 166       return ConstantFoldBinaryInst(BB, II, cast<BinaryOperator>(Inst), D1, D2);
 167
 168   } else if (CastInst *CI = dyn_cast<CastInst>(Inst)) {
 169     Constant *D = dyn_cast<Constant>(CI->getOperand(0));
 170     if (D) return ConstantFoldCast(BB, II, CI, D);
 171
 172   } else if (UnaryOperator *UInst = dyn_cast<UnaryOperator>(Inst)) {
 173     Constant *D = dyn_cast<Constant>(UInst->getOperand(0));
 174     if (D) return ConstantFoldUnaryInst(BB, II, UInst, D);
 175   } else if (TerminatorInst *TInst = dyn_cast<TerminatorInst>(Inst)) {
 176     return ConstantFoldTerminator(BB, II, TInst);
 177
 178   } else if (PHINode *PN = dyn_cast<PHINode>(Inst)) {
 179     // If it's a PHI node and only has one operand
 180     // Then replace it directly with that operand.
 181     assert(PN->getNumOperands() && "PHI Node must have at least one operand!");
 182     if (PN->getNumOperands() == 1) {    // If the PHI Node has exactly 1 operand
 183       Value *V = PN->getOperand(0);
 184       PN->replaceAllUsesWith(V);                 // Replace all uses of this PHI
 185                                                  // Unlink from basic block
 186       PN->getParent()->getInstList().remove(II);
 187       if (PN->hasName())                         // Inherit PHINode name
 188         V->setName(PN->getName(), BB->getParent()->getSymbolTableSure());
 189       delete PN;                                 // Finally, delete the node...
 190       return true;
 191     }
 192   }
 193   return false;
 194 }
 195
 196 // DoConstPropPass - Propogate constants and do constant folding on instructions
 197 // this returns true if something was changed, false if nothing was changed.
 198 //
 199 static bool DoConstPropPass(Function *F) {
 200   bool SomethingChanged = false;
 201
 202   for (Method::iterator BBI = F->begin(); BBI != F->end(); ++BBI) {
 203     BasicBlock *BB = *BBI;
 204     for (BasicBlock::iterator I = BB->begin(); I != BB->end(); )
 205       if (doConstantPropogation(BB, I))
 206         SomethingChanged = true;
 207       else
 208         ++I;
 209   }
 210   return SomethingChanged;
 211 }
 212
 213 namespace {
 214   struct ConstantPropogation : public MethodPass {
 215     inline bool runOnMethod(Function *F) {
 216       bool Modified = false;
 217
 218       // Fold constants until we make no progress...
 219       while (DoConstPropPass(F)) Modified = true;
 220
 221       return Modified;
 222     }
 223   };
 224 }
 225
 226 Pass *createConstantPropogationPass() {
 227   return new ConstantPropogation();
 228 }
 229