ConstantProp.cpp revision a41f50dea8573e4a610b5aa5e45b5c368559b084 
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#include "llvm/ConstantPool.h"
33
34// Merge identical constant values in the constant pool.
35//
36// TODO: We can do better than this simplistic N^2 algorithm...
37//
38bool opt::DoConstantPoolMerging(Method *M) {
39  return DoConstantPoolMerging(M->getConstantPool());
40}
41
42bool opt::DoConstantPoolMerging(ConstantPool &CP) {
43  bool Modified = false;
44  for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI) {
45    for (ConstantPool::PlaneType::iterator I = (*PI)->begin();
46	 I != (*PI)->end(); ++I) {
47      ConstPoolVal *C = *I;
48
49      ConstantPool::PlaneType::iterator J = I;
50      for (++J; J != (*PI)->end(); ++J) {
51	if (C->equals(*J)) {
52	  Modified = true;
53	  // Okay we know that *I == *J.  So now we need to make all uses of *I
54	  // point to *J.
55	  //
56	  C->replaceAllUsesWith(*J);
57
58	  (*PI)->remove(I); // Remove C from constant pool...
59
60	  if (C->hasName() && !(*J)->hasName())  // The merged constant inherits
61	    (*J)->setName(C->getName());         // the old name...
62
63	  delete C;                              // Delete the constant itself.
64	  break;  // Break out of inner for loop
65	}
66      }
67    }
68  }
69  return Modified;
70}
71
72inline static bool
73ConstantFoldUnaryInst(Method *M, Method::inst_iterator &DI,
74                      UnaryOperator *Op, ConstPoolVal *D) {
75  ConstPoolVal *ReplaceWith =
76    opt::ConstantFoldUnaryInstruction(Op->getOpcode(), D);
77
78  if (!ReplaceWith) return false;   // Nothing new to change...
79
80
81  // Add the new value to the constant pool...
82  M->getConstantPool().insert(ReplaceWith);
83
84  // Replaces all of the uses of a variable with uses of the constant.
85  Op->replaceAllUsesWith(ReplaceWith);
86
87  // Remove the operator from the list of definitions...
88  Op->getParent()->getInstList().remove(DI.getInstructionIterator());
89
90  // The new constant inherits the old name of the operator...
91  if (Op->hasName()) ReplaceWith->setName(Op->getName());
92
93  // Delete the operator now...
94  delete Op;
95  return true;
96}
97
98inline static bool
99ConstantFoldBinaryInst(Method *M, Method::inst_iterator &DI,
100		       BinaryOperator *Op,
101		       ConstPoolVal *D1, ConstPoolVal *D2) {
102  ConstPoolVal *ReplaceWith =
103    opt::ConstantFoldBinaryInstruction(Op->getOpcode(), D1, D2);
104  if (!ReplaceWith) return false;   // Nothing new to change...
105
106  // Add the new value to the constant pool...
107  M->getConstantPool().insert(ReplaceWith);
108
109  // Replaces all of the uses of a variable with uses of the constant.
110  Op->replaceAllUsesWith(ReplaceWith);
111
112  // Remove the operator from the list of definitions...
113  Op->getParent()->getInstList().remove(DI.getInstructionIterator());
114
115  // The new constant inherits the old name of the operator...
116  if (Op->hasName()) ReplaceWith->setName(Op->getName());
117
118  // Delete the operator now...
119  delete Op;
120  return true;
121}
122
123// ConstantFoldTerminator - If a terminator instruction is predicated on a
124// constant value, convert it into an unconditional branch to the constant
125// destination.
126//
127bool opt::ConstantFoldTerminator(TerminatorInst *T) {
128  // Branch - See if we are conditional jumping on constant
129  if (T->getOpcode() == Instruction::Br) {
130    BranchInst *BI = (BranchInst*)T;
131    if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
132    BasicBlock *Dest1 = BI->getOperand(0)->castBasicBlockAsserting();
133    BasicBlock *Dest2 = BI->getOperand(1)->castBasicBlockAsserting();
134
135    if (BI->getCondition()->isConstant()) {    // Are we branching on constant?
136      // YES.  Change to unconditional branch...
137      ConstPoolBool *Cond = (ConstPoolBool*)BI->getCondition();
138      BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
139      BasicBlock *OldDest     = Cond->getValue() ? Dest2 : Dest1;
140
141      //cerr << "Method: " << T->getParent()->getParent()
142      //     << "\nRemoving branch from " << T->getParent()
143      //     << "\n\nTo: " << OldDest << endl;
144
145      // Let the basic block know that we are letting go of it.  Based on this,
146      // it will adjust it's PHI nodes.
147      assert(BI->getParent() && "Terminator not inserted in block!");
148      OldDest->removePredecessor(BI->getParent());
149
150      // Set the unconditional destination, and change the insn to be an
151      // unconditional branch.
152      BI->setUnconditionalDest(Destination);
153      return true;
154    } else if (Dest2 == Dest1) {       // Conditional branch to same location?
155      // This branch matches something like this:
156      //     br bool %cond, label %Dest, label %Dest
157      // and changes it into:  br label %Dest
158
159      // Let the basic block know that we are letting go of one copy of it.
160      assert(BI->getParent() && "Terminator not inserted in block!");
161      Dest1->removePredecessor(BI->getParent());
162
163      // Change a conditional branch to unconditional.
164      BI->setUnconditionalDest(Dest1);
165      return true;
166    }
167  }
168  return false;
169}
170
171// ConstantFoldInstruction - If an instruction references constants, try to fold
172// them together...
173//
174inline static bool
175ConstantFoldInstruction(Method *M, Method::inst_iterator &II) {
176  Instruction *Inst = *II;
177  if (Inst->isBinaryOp()) {
178    ConstPoolVal *D1 = Inst->getOperand(0)->castConstant();
179    ConstPoolVal *D2 = Inst->getOperand(1)->castConstant();
180
181    if (D1 && D2)
182      return ConstantFoldBinaryInst(M, II, (BinaryOperator*)Inst, D1, D2);
183
184  } else if (Inst->isUnaryOp()) {
185    ConstPoolVal *D = Inst->getOperand(0)->castConstant();
186    if (D) return ConstantFoldUnaryInst(M, II, (UnaryOperator*)Inst, D);
187  } else if (Inst->isTerminator()) {
188    return opt::ConstantFoldTerminator((TerminatorInst*)Inst);
189
190  } else if (Inst->isPHINode()) {
191    PHINode *PN = (PHINode*)Inst; // If it's a PHI node and only has one operand
192                                  // Then replace it directly with that operand.
193    assert(PN->getOperand(0) && "PHI Node must have at least one operand!");
194    if (PN->getNumOperands() == 1) {    // If the PHI Node has exactly 1 operand
195      Value *V = PN->getOperand(0);
196      PN->replaceAllUsesWith(V);                 // Replace all uses of this PHI
197                                                 // Unlink from basic block
198      PN->getParent()->getInstList().remove(II.getInstructionIterator());
199      if (PN->hasName()) V->setName(PN->getName()); // Inherit PHINode name
200      delete PN;                                 // Finally, delete the node...
201      return true;
202    }
203  }
204  return false;
205}
206
207// DoConstPropPass - Propogate constants and do constant folding on instructions
208// this returns true if something was changed, false if nothing was changed.
209//
210static bool DoConstPropPass(Method *M) {
211  bool SomethingChanged = false;
212
213#if 1
214  Method::inst_iterator It = M->inst_begin();
215  while (It != M->inst_end())
216    if (ConstantFoldInstruction(M, It)) {
217      SomethingChanged = true;  // If returned true, iter is already incremented
218
219      // Incrementing the iterator in an unchecked manner could mess up the
220      // internals of 'It'.  To make sure everything is happy, tell it we might
221      // have broken it.
222      It.resyncInstructionIterator();
223    } else {
224      ++It;
225    }
226#else
227  for (Method::iterator BBIt = M->begin(); BBIt != M->end(); ++BBIt) {
228    BasicBlock *BB = *BBIt;
229
230    reduce_apply_bool(BB->begin(), BB->end(),
231		      bind1st(ConstantFoldInstruction, M));
232  }
233#endif
234  return SomethingChanged;
235}
236
237
238// returns true on failure, false on success...
239//
240bool opt::DoConstantPropogation(Method *M) {
241  bool Modified = false;
242
243  // Fold constants until we make no progress...
244  while (DoConstPropPass(M)) Modified = true;
245
246  // Merge identical constants last: this is important because we may have just
247  // introduced constants that already exist!
248  //
249  Modified |= DoConstantPoolMerging(M->getConstantPool());
250
251  return Modified;
252}
253