ConstantProp.cpp revision 968ddc921e70d098923a6dc585f86b6ebc3fd13e 
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#include "llvm/ConstantVals.h"
34
35inline static bool
36ConstantFoldUnaryInst(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
57inline static bool
58ConstantFoldCast(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
79inline static bool
80ConstantFoldBinaryInst(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//
105bool 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//
159bool 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//
199static 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
213namespace {
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
226Pass *createConstantPropogationPass() {
227  return new ConstantPropogation();
228}
229
230