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/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"
34 ConstantFoldUnaryInst(Method *M, Method::inst_iterator &DI,
35 UnaryOperator *Op, ConstPoolVal *D) {
36 ConstPoolVal *ReplaceWith =
37 opt::ConstantFoldUnaryInstruction(Op->getOpcode(), D);
39 if (!ReplaceWith) return false; // Nothing new to change...
41 // Replaces all of the uses of a variable with uses of the constant.
42 Op->replaceAllUsesWith(ReplaceWith);
44 // Remove the operator from the list of definitions...
45 Op->getParent()->getInstList().remove(DI.getInstructionIterator());
47 // The new constant inherits the old name of the operator...
49 ReplaceWith->setName(Op->getName(), M->getSymbolTableSure());
51 // Delete the operator now...
57 ConstantFoldBinaryInst(Method *M, Method::inst_iterator &DI,
59 ConstPoolVal *D1, ConstPoolVal *D2) {
60 ConstPoolVal *ReplaceWith =
61 opt::ConstantFoldBinaryInstruction(Op->getOpcode(), D1, D2);
62 if (!ReplaceWith) return false; // Nothing new to change...
64 // Replaces all of the uses of a variable with uses of the constant.
65 Op->replaceAllUsesWith(ReplaceWith);
67 // Remove the operator from the list of definitions...
68 Op->getParent()->getInstList().remove(DI.getInstructionIterator());
70 // The new constant inherits the old name of the operator...
72 ReplaceWith->setName(Op->getName(), M->getSymbolTableSure());
74 // Delete the operator now...
79 // ConstantFoldTerminator - If a terminator instruction is predicated on a
80 // constant value, convert it into an unconditional branch to the constant
83 bool opt::ConstantFoldTerminator(TerminatorInst *T) {
84 // Branch - See if we are conditional jumping on constant
85 if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
86 if (BI->isUnconditional()) return false; // Can't optimize uncond branch
87 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
88 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
90 if (ConstPoolBool *Cond = dyn_cast<ConstPoolBool>(BI->getCondition())) {
91 // Are we branching on constant?
92 // YES. Change to unconditional branch...
93 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
94 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1;
96 //cerr << "Method: " << T->getParent()->getParent()
97 // << "\nRemoving branch from " << T->getParent()
98 // << "\n\nTo: " << OldDest << endl;
100 // Let the basic block know that we are letting go of it. Based on this,
101 // it will adjust it's PHI nodes.
102 assert(BI->getParent() && "Terminator not inserted in block!");
103 OldDest->removePredecessor(BI->getParent());
105 // Set the unconditional destination, and change the insn to be an
106 // unconditional branch.
107 BI->setUnconditionalDest(Destination);
111 // FIXME: TODO: This doesn't work if the destination has PHI nodes with
112 // different incoming values on each branch!
114 else if (Dest2 == Dest1) { // Conditional branch to same location?
115 // This branch matches something like this:
116 // br bool %cond, label %Dest, label %Dest
117 // and changes it into: br label %Dest
119 // Let the basic block know that we are letting go of one copy of it.
120 assert(BI->getParent() && "Terminator not inserted in block!");
121 Dest1->removePredecessor(BI->getParent());
123 // Change a conditional branch to unconditional.
124 BI->setUnconditionalDest(Dest1);
132 // ConstantFoldInstruction - If an instruction references constants, try to fold
136 ConstantFoldInstruction(Method *M, Method::inst_iterator &II) {
137 Instruction *Inst = *II;
138 if (BinaryOperator *BInst = dyn_cast<BinaryOperator>(Inst)) {
139 ConstPoolVal *D1 = dyn_cast<ConstPoolVal>(Inst->getOperand(0));
140 ConstPoolVal *D2 = dyn_cast<ConstPoolVal>(Inst->getOperand(1));
143 return ConstantFoldBinaryInst(M, II, cast<BinaryOperator>(Inst), D1, D2);
145 } else if (UnaryOperator *UInst = dyn_cast<UnaryOperator>(Inst)) {
146 ConstPoolVal *D = dyn_cast<ConstPoolVal>(UInst->getOperand(0));
147 if (D) return ConstantFoldUnaryInst(M, II, UInst, D);
148 } else if (TerminatorInst *TInst = dyn_cast<TerminatorInst>(Inst)) {
149 return opt::ConstantFoldTerminator(TInst);
151 } else if (PHINode *PN = dyn_cast<PHINode>(Inst)) {
152 // If it's a PHI node and only has one operand
153 // Then replace it directly with that operand.
154 assert(PN->getOperand(0) && "PHI Node must have at least one operand!");
155 if (PN->getNumOperands() == 1) { // If the PHI Node has exactly 1 operand
156 Value *V = PN->getOperand(0);
157 PN->replaceAllUsesWith(V); // Replace all uses of this PHI
158 // Unlink from basic block
159 PN->getParent()->getInstList().remove(II.getInstructionIterator());
160 if (PN->hasName()) // Inherit PHINode name
161 V->setName(PN->getName(), M->getSymbolTableSure());
162 delete PN; // Finally, delete the node...
169 // DoConstPropPass - Propogate constants and do constant folding on instructions
170 // this returns true if something was changed, false if nothing was changed.
172 static bool DoConstPropPass(Method *M) {
173 bool SomethingChanged = false;
176 Method::inst_iterator It = M->inst_begin();
177 while (It != M->inst_end())
178 if (ConstantFoldInstruction(M, It)) {
179 SomethingChanged = true; // If returned true, iter is already incremented
181 // Incrementing the iterator in an unchecked manner could mess up the
182 // internals of 'It'. To make sure everything is happy, tell it we might
184 It.resyncInstructionIterator();
189 for (Method::iterator BBIt = M->begin(); BBIt != M->end(); ++BBIt) {
190 BasicBlock *BB = *BBIt;
192 reduce_apply_bool(BB->begin(), BB->end(),
193 bind1st(ConstantFoldInstruction, M));
196 return SomethingChanged;
200 // returns true on failure, false on success...
202 bool opt::ConstantPropogation::doConstantPropogation(Method *M) {
203 bool Modified = false;
205 // Fold constants until we make no progress...
206 while (DoConstPropPass(M)) Modified = true;