1 //===- ConstantProp.cpp - Code to perform Constant Propogation ------------===//
3 // This file implements constant propogation and merging:
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
9 // * Converts instructions like "add int %1, %2" into a direct def of %3 in
11 // * Converts conditional branches on a constant boolean value into direct
13 // * Converts phi nodes with one incoming def to the incoming def directly
14 // . Converts switch statements with one entry into a test & conditional
16 // . Converts switches on constant values into an unconditional branch.
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.
22 //===----------------------------------------------------------------------===//
24 #include "llvm/Module.h"
25 #include "llvm/Method.h"
26 #include "llvm/BasicBlock.h"
27 #include "llvm/iTerminators.h"
28 #include "llvm/iOther.h"
29 #include "llvm/ConstPoolVals.h"
30 #include "llvm/ConstantPool.h"
31 #include "llvm/Opt/AllOpts.h"
32 #include "llvm/Opt/ConstantHandling.h"
34 // Merge identical constant values in the constant pool.
36 // TODO: We can do better than this simplistic N^2 algorithm...
38 bool DoConstantPoolMerging(Method *M) {
39 return DoConstantPoolMerging(M->getConstantPool());
42 bool 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) {
49 ConstantPool::PlaneType::iterator J = I;
50 for (++J; J != (*PI)->end(); ++J) {
53 // Okay we know that *I == *J. So now we need to make all uses of *I
56 C->replaceAllUsesWith(*J);
58 (*PI)->remove(I); // Remove C from constant pool...
60 if (C->hasName() && !(*J)->hasName()) // The merged constant inherits
61 (*J)->setName(C->getName()); // the old name...
63 delete C; // Delete the constant itself.
64 break; // Break out of inner for loop
73 ConstantFoldUnaryInst(Method *M, Method::inst_iterator &DI,
74 UnaryOperator *Op, ConstPoolVal *D) {
75 ConstPoolVal *ReplaceWith =
76 ConstantFoldUnaryInstruction(Op->getInstType(), D);
78 if (!ReplaceWith) return false; // Nothing new to change...
81 // Add the new value to the constant pool...
82 M->getConstantPool().insert(ReplaceWith);
84 // Replaces all of the uses of a variable with uses of the constant.
85 Op->replaceAllUsesWith(ReplaceWith);
87 // Remove the operator from the list of definitions...
88 Op->getParent()->getInstList().remove(DI.getInstructionIterator());
90 // The new constant inherits the old name of the operator...
91 if (Op->hasName()) ReplaceWith->setName(Op->getName());
93 // Delete the operator now...
99 ConstantFoldBinaryInst(Method *M, Method::inst_iterator &DI,
101 ConstPoolVal *D1, ConstPoolVal *D2) {
102 ConstPoolVal *ReplaceWith =
103 ConstantFoldBinaryInstruction(Op->getInstType(), D1, D2);
104 if (!ReplaceWith) return false; // Nothing new to change...
106 // Add the new value to the constant pool...
107 M->getConstantPool().insert(ReplaceWith);
109 // Replaces all of the uses of a variable with uses of the constant.
110 Op->replaceAllUsesWith(ReplaceWith);
112 // Remove the operator from the list of definitions...
113 Op->getParent()->getInstList().remove(DI.getInstructionIterator());
115 // The new constant inherits the old name of the operator...
116 if (Op->hasName()) ReplaceWith->setName(Op->getName());
118 // Delete the operator now...
123 // ConstantFoldTerminator - If a terminator instruction is predicated on a
124 // constant value, convert it into an unconditional branch to the constant
127 bool ConstantFoldTerminator(TerminatorInst *T) {
128 // Branch - See if we are conditional jumping on constant
129 if (T->getInstType() == 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();
135 if (BI->getOperand(2)->isConstant()) { // Are we branching on constant?
136 // YES. Change to unconditional branch...
137 ConstPoolBool *Cond = (ConstPoolBool*)BI->getOperand(2);
138 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
139 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1;
141 //cerr << "Method: " << T->getParent()->getParent()
142 // << "\nRemoving branch from " << T->getParent()
143 // << "\n\nTo: " << OldDest << endl;
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());
150 BI->setOperand(0, Destination); // Set the unconditional destination
151 BI->setOperand(1, 0); // Clear the conditional destination
152 BI->setOperand(2, 0); // Clear the condition...
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
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());
163 // Nuke the second destination, and the use of the condition variable
164 BI->setOperand(1, 0); // Clear the conditional destination
165 BI->setOperand(2, 0); // Clear the condition...
172 // ConstantFoldInstruction - If an instruction references constants, try to fold
176 ConstantFoldInstruction(Method *M, Method::inst_iterator &II) {
177 Instruction *Inst = *II;
178 if (Inst->isBinaryOp()) {
179 ConstPoolVal *D1 = Inst->getOperand(0)->castConstant();
180 ConstPoolVal *D2 = Inst->getOperand(1)->castConstant();
183 return ConstantFoldBinaryInst(M, II, (BinaryOperator*)Inst, D1, D2);
185 } else if (Inst->isUnaryOp()) {
186 ConstPoolVal *D = Inst->getOperand(0)->castConstant();
187 if (D) return ConstantFoldUnaryInst(M, II, (UnaryOperator*)Inst, D);
188 } else if (Inst->isTerminator()) {
189 return ConstantFoldTerminator((TerminatorInst*)Inst);
191 } else if (Inst->isPHINode()) {
192 PHINode *PN = (PHINode*)Inst; // If it's a PHI node and only has one operand
193 // Then replace it directly with that operand.
194 assert(PN->getOperand(0) && "PHI Node must have at least one operand!");
195 if (PN->getOperand(1) == 0) { // If the PHI Node has exactly 1 operand
196 Value *V = PN->getOperand(0);
197 PN->replaceAllUsesWith(V); // Replace all uses of this PHI
198 // Unlink from basic block
199 PN->getParent()->getInstList().remove(II.getInstructionIterator());
200 if (PN->hasName()) V->setName(PN->getName()); // Inherit PHINode name
201 delete PN; // Finally, delete the node...
208 // DoConstPropPass - Propogate constants and do constant folding on instructions
209 // this returns true if something was changed, false if nothing was changed.
211 static bool DoConstPropPass(Method *M) {
212 bool SomethingChanged = false;
215 Method::inst_iterator It = M->inst_begin();
216 while (It != M->inst_end())
217 if (ConstantFoldInstruction(M, It)) {
218 SomethingChanged = true; // If returned true, iter is already incremented
220 // Incrementing the iterator in an unchecked manner could mess up the
221 // internals of 'It'. To make sure everything is happy, tell it we might
223 It.resyncInstructionIterator();
228 for (Method::iterator BBIt = M->begin(); BBIt != M->end(); ++BBIt) {
229 BasicBlock *BB = *BBIt;
231 reduce_apply_bool(BB->begin(), BB->end(),
232 bind1st(ConstantFoldInstruction, M));
235 return SomethingChanged;
239 // returns true on failure, false on success...
241 bool DoConstantPropogation(Method *M) {
242 bool Modified = false;
244 // Fold constants until we make no progress...
245 while (DoConstPropPass(M)) Modified = true;
247 // Merge identical constants last: this is important because we may have just
248 // introduced constants that already exist!
250 Modified |= DoConstantPoolMerging(M->getConstantPool());