ConstantProp.cpp revision 2fbfdcffd3e0cf41422aaa6c526c37cb02b81341
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/Transforms/Scalar/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