ConstantProp.cpp revision 7061dc50b2513731d7b346ab16183cda4a44619f
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/iPHINode.h" 31#include "llvm/iOther.h" 32#include "llvm/ConstPoolVals.h" 33 34inline static bool 35ConstantFoldUnaryInst(BasicBlock *BB, BasicBlock::iterator &II, 36 UnaryOperator *Op, ConstPoolVal *D) { 37 ConstPoolVal *ReplaceWith = 38 opt::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, ConstPoolVal *D) { 60 ConstPoolVal *ReplaceWith = 61 opt::ConstantFoldCastInstruction(D, CI->getType()); 62 63 if (!ReplaceWith) return false; // Nothing new to change... 64 65 // Replaces all of the uses of a variable with uses of the constant. 66 CI->replaceAllUsesWith(ReplaceWith); 67 68 // Remove the cast from the list of definitions... 69 CI->getParent()->getInstList().remove(II); 70 71 // The new constant inherits the old name of the cast... 72 if (CI->hasName()) 73 ReplaceWith->setName(CI->getName(), BB->getParent()->getSymbolTableSure()); 74 75 // Delete the cast now... 76 delete CI; 77 return true; 78} 79 80inline static bool 81ConstantFoldBinaryInst(BasicBlock *BB, BasicBlock::iterator &II, 82 BinaryOperator *Op, 83 ConstPoolVal *D1, ConstPoolVal *D2) { 84 ConstPoolVal *ReplaceWith = 85 opt::ConstantFoldBinaryInstruction(Op->getOpcode(), D1, D2); 86 if (!ReplaceWith) return false; // Nothing new to change... 87 88 // Replaces all of the uses of a variable with uses of the constant. 89 Op->replaceAllUsesWith(ReplaceWith); 90 91 // Remove the operator from the list of definitions... 92 Op->getParent()->getInstList().remove(II); 93 94 // The new constant inherits the old name of the operator... 95 if (Op->hasName()) 96 ReplaceWith->setName(Op->getName(), BB->getParent()->getSymbolTableSure()); 97 98 // Delete the operator now... 99 delete Op; 100 return true; 101} 102 103// ConstantFoldTerminator - If a terminator instruction is predicated on a 104// constant value, convert it into an unconditional branch to the constant 105// destination. 106// 107bool opt::ConstantFoldTerminator(TerminatorInst *T) { 108 // Branch - See if we are conditional jumping on constant 109 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 110 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 111 BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); 112 BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); 113 114 if (ConstPoolBool *Cond = dyn_cast<ConstPoolBool>(BI->getCondition())) { 115 // Are we branching on constant? 116 // YES. Change to unconditional branch... 117 BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; 118 BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; 119 120 //cerr << "Method: " << T->getParent()->getParent() 121 // << "\nRemoving branch from " << T->getParent() 122 // << "\n\nTo: " << OldDest << endl; 123 124 // Let the basic block know that we are letting go of it. Based on this, 125 // it will adjust it's PHI nodes. 126 assert(BI->getParent() && "Terminator not inserted in block!"); 127 OldDest->removePredecessor(BI->getParent()); 128 129 // Set the unconditional destination, and change the insn to be an 130 // unconditional branch. 131 BI->setUnconditionalDest(Destination); 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 opt::ConstantPropogation::doConstantPropogation(BasicBlock *BB, 160 BasicBlock::iterator &II) { 161 Instruction *Inst = *II; 162 if (BinaryOperator *BInst = dyn_cast<BinaryOperator>(Inst)) { 163 ConstPoolVal *D1 = dyn_cast<ConstPoolVal>(Inst->getOperand(0)); 164 ConstPoolVal *D2 = dyn_cast<ConstPoolVal>(Inst->getOperand(1)); 165 166 if (D1 && D2) 167 return ConstantFoldBinaryInst(BB, II, cast<BinaryOperator>(Inst), D1, D2); 168 169 } else if (CastInst *CI = dyn_cast<CastInst>(Inst)) { 170 ConstPoolVal *D = dyn_cast<ConstPoolVal>(CI->getOperand(0)); 171 if (D) return ConstantFoldCast(BB, II, CI, D); 172 173 } else if (UnaryOperator *UInst = dyn_cast<UnaryOperator>(Inst)) { 174 ConstPoolVal *D = dyn_cast<ConstPoolVal>(UInst->getOperand(0)); 175 if (D) return ConstantFoldUnaryInst(BB, II, UInst, D); 176 } else if (TerminatorInst *TInst = dyn_cast<TerminatorInst>(Inst)) { 177 return opt::ConstantFoldTerminator(TInst); 178 179 } else if (PHINode *PN = dyn_cast<PHINode>(Inst)) { 180 // If it's a PHI node and only has one operand 181 // Then replace it directly with that operand. 182 assert(PN->getOperand(0) && "PHI Node must have at least one operand!"); 183 if (PN->getNumOperands() == 1) { // If the PHI Node has exactly 1 operand 184 Value *V = PN->getOperand(0); 185 PN->replaceAllUsesWith(V); // Replace all uses of this PHI 186 // Unlink from basic block 187 PN->getParent()->getInstList().remove(II); 188 if (PN->hasName()) // Inherit PHINode name 189 V->setName(PN->getName(), BB->getParent()->getSymbolTableSure()); 190 delete PN; // Finally, delete the node... 191 return true; 192 } 193 } 194 return false; 195} 196 197// DoConstPropPass - Propogate constants and do constant folding on instructions 198// this returns true if something was changed, false if nothing was changed. 199// 200static bool DoConstPropPass(Method *M) { 201 bool SomethingChanged = false; 202 203 for (Method::iterator BBI = M->begin(); BBI != M->end(); ++BBI) { 204 BasicBlock *BB = *BBI; 205 for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) 206 if (opt::ConstantPropogation::doConstantPropogation(BB, I)) 207 SomethingChanged = true; 208 else 209 ++I; 210 } 211 return SomethingChanged; 212} 213 214 215// returns whether or not the underlying method was modified 216// 217bool opt::ConstantPropogation::doConstantPropogation(Method *M) { 218 bool Modified = false; 219 220 // Fold constants until we make no progress... 221 while (DoConstPropPass(M)) Modified = true; 222 223 return Modified; 224} 225