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/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"
35 ConstantFoldUnaryInst(BasicBlock *BB, BasicBlock::iterator &II,
36 UnaryOperator *Op, Constant *D) {
37 Constant *ReplaceWith = 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(II);
47 // The new constant inherits the old name of the operator...
49 ReplaceWith->setName(Op->getName(), BB->getParent()->getSymbolTableSure());
51 // Delete the operator now...
57 ConstantFoldCast(BasicBlock *BB, BasicBlock::iterator &II,
58 CastInst *CI, Constant *D) {
59 Constant *ReplaceWith = ConstantFoldCastInstruction(D, CI->getType());
61 if (!ReplaceWith) return false; // Nothing new to change...
63 // Replaces all of the uses of a variable with uses of the constant.
64 CI->replaceAllUsesWith(ReplaceWith);
66 // Remove the cast from the list of definitions...
67 CI->getParent()->getInstList().remove(II);
69 // The new constant inherits the old name of the cast...
71 ReplaceWith->setName(CI->getName(), BB->getParent()->getSymbolTableSure());
73 // Delete the cast now...
79 ConstantFoldBinaryInst(BasicBlock *BB, BasicBlock::iterator &II,
81 Constant *D1, Constant *D2) {
82 Constant *ReplaceWith = ConstantFoldBinaryInstruction(Op->getOpcode(), D1,D2);
83 if (!ReplaceWith) return false; // Nothing new to change...
85 // Replaces all of the uses of a variable with uses of the constant.
86 Op->replaceAllUsesWith(ReplaceWith);
88 // Remove the operator from the list of definitions...
89 Op->getParent()->getInstList().remove(II);
91 // The new constant inherits the old name of the operator...
93 ReplaceWith->setName(Op->getName(), BB->getParent()->getSymbolTableSure());
95 // Delete the operator now...
101 ConstantFoldShiftInst(BasicBlock *BB, BasicBlock::iterator &II,
103 Constant *D1, Constant *D2) {
104 Constant *ReplaceWith = ConstantFoldShiftInstruction(Op->getOpcode(), D1,D2);
105 if (!ReplaceWith) return false; // Nothing new to change...
107 // Replaces all of the uses of a variable with uses of the constant.
108 Op->replaceAllUsesWith(ReplaceWith);
110 // Remove the operator from the list of definitions...
111 Op->getParent()->getInstList().remove(II);
113 // The new constant inherits the old name of the operator...
115 ReplaceWith->setName(Op->getName(), BB->getParent()->getSymbolTableSure());
117 // Delete the operator now...
122 // ConstantFoldTerminator - If a terminator instruction is predicated on a
123 // constant value, convert it into an unconditional branch to the constant
126 bool ConstantFoldTerminator(BasicBlock *BB, BasicBlock::iterator &II,
128 // Branch - See if we are conditional jumping on constant
129 if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
130 if (BI->isUnconditional()) return false; // Can't optimize uncond branch
131 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
132 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
134 if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
135 // Are we branching on constant?
136 // YES. Change to unconditional branch...
137 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
138 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1;
140 //cerr << "Function: " << T->getParent()->getParent()
141 // << "\nRemoving branch from " << T->getParent()
142 // << "\n\nTo: " << OldDest << endl;
144 // Let the basic block know that we are letting go of it. Based on this,
145 // it will adjust it's PHI nodes.
146 assert(BI->getParent() && "Terminator not inserted in block!");
147 OldDest->removePredecessor(BI->getParent());
149 // Set the unconditional destination, and change the insn to be an
150 // unconditional branch.
151 BI->setUnconditionalDest(Destination);
152 II = BB->end()-1; // Update instruction iterator!
156 // FIXME: TODO: This doesn't work if the destination has PHI nodes with
157 // different incoming values on each branch!
159 else if (Dest2 == Dest1) { // Conditional branch to same location?
160 // This branch matches something like this:
161 // br bool %cond, label %Dest, label %Dest
162 // and changes it into: br label %Dest
164 // Let the basic block know that we are letting go of one copy of it.
165 assert(BI->getParent() && "Terminator not inserted in block!");
166 Dest1->removePredecessor(BI->getParent());
168 // Change a conditional branch to unconditional.
169 BI->setUnconditionalDest(Dest1);
177 // ConstantFoldInstruction - If an instruction references constants, try to fold
180 bool doConstantPropogation(BasicBlock *BB, BasicBlock::iterator &II) {
181 Instruction *Inst = *II;
182 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Inst)) {
183 Constant *D1 = dyn_cast<Constant>(BO->getOperand(0));
184 Constant *D2 = dyn_cast<Constant>(BO->getOperand(1));
187 return ConstantFoldBinaryInst(BB, II, BO, D1, D2);
189 } else if (CastInst *CI = dyn_cast<CastInst>(Inst)) {
190 Constant *D = dyn_cast<Constant>(CI->getOperand(0));
191 if (D) return ConstantFoldCast(BB, II, CI, D);
193 } else if (UnaryOperator *UInst = dyn_cast<UnaryOperator>(Inst)) {
194 Constant *D = dyn_cast<Constant>(UInst->getOperand(0));
195 if (D) return ConstantFoldUnaryInst(BB, II, UInst, D);
196 } else if (TerminatorInst *TInst = dyn_cast<TerminatorInst>(Inst)) {
197 return ConstantFoldTerminator(BB, II, TInst);
199 } else if (PHINode *PN = dyn_cast<PHINode>(Inst)) {
200 // If it's a PHI node and only has one operand
201 // Then replace it directly with that operand.
202 assert(PN->getNumOperands() && "PHI Node must have at least one operand!");
203 if (PN->getNumOperands() == 1) { // If the PHI Node has exactly 1 operand
204 Value *V = PN->getOperand(0);
205 PN->replaceAllUsesWith(V); // Replace all uses of this PHI
206 // Unlink from basic block
207 PN->getParent()->getInstList().remove(II);
208 if (PN->hasName()) // Inherit PHINode name
209 V->setName(PN->getName(), BB->getParent()->getSymbolTableSure());
210 delete PN; // Finally, delete the node...
213 } else if (ShiftInst *SI = dyn_cast<ShiftInst>(Inst)) {
214 Constant *D1 = dyn_cast<Constant>(SI->getOperand(0));
215 Constant *D2 = dyn_cast<Constant>(SI->getOperand(1));
218 return ConstantFoldShiftInst(BB, II, SI, D1, D2);
224 // DoConstPropPass - Propogate constants and do constant folding on instructions
225 // this returns true if something was changed, false if nothing was changed.
227 static bool DoConstPropPass(Function *F) {
228 bool SomethingChanged = false;
230 for (Function::iterator BBI = F->begin(); BBI != F->end(); ++BBI) {
231 BasicBlock *BB = *BBI;
232 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); )
233 if (doConstantPropogation(BB, I))
234 SomethingChanged = true;
238 return SomethingChanged;
242 struct ConstantPropogation : public FunctionPass {
243 const char *getPassName() const { return "Simple Constant Propogation"; }
245 inline bool runOnFunction(Function *F) {
246 bool Modified = false;
248 // Fold constants until we make no progress...
249 while (DoConstPropPass(F)) Modified = true;
254 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
255 // FIXME: This pass does not preserve the CFG because it folds terminator
262 Pass *createConstantPropogationPass() {
263 return new ConstantPropogation();