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