X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FConstantProp.cpp;h=664c3f6a222f7df19f6ddd74bb03da8780059abf;hb=827454e6e28cfed93db990b03b720ef7c23e6917;hp=9d70d842bedf5c8803bf0a841b14748ec51355c2;hpb=531450d8a6fb79f34a33033ca24e8554469aa3a8;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/ConstantProp.cpp b/lib/Transforms/Scalar/ConstantProp.cpp index 9d70d842bed..664c3f6a222 100644 --- a/lib/Transforms/Scalar/ConstantProp.cpp +++ b/lib/Transforms/Scalar/ConstantProp.cpp @@ -1,223 +1,91 @@ -//===- ConstantProp.cpp - Code to perform Constant Propogation ------------===// +//===- ConstantProp.cpp - Code to perform Simple Constant Propagation -----===// // -// This file implements constant propogation and merging: +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements constant propagation and merging: // // Specifically, this: -// * Folds multiple identical constants in the constant pool together -// Note that if one is named and the other is not, that the result gets the -// original name. -// * Converts instructions like "add int %1, %2" into a direct def of %3 in -// the constant pool -// * Converts conditional branches on a constant boolean value into direct -// branches. -// * Converts phi nodes with one incoming def to the incoming def directly -// . Converts switch statements with one entry into a test & conditional -// branch -// . Converts switches on constant values into an unconditional branch. +// * Converts instructions like "add int 1, 2" into 3 // // Notice that: // * This pass has a habit of making definitions be dead. It is a good idea -// to to run a DCE pass sometime after running this pass. +// to run a DIE pass sometime after running this pass. // //===----------------------------------------------------------------------===// -#include "llvm/Module.h" -#include "llvm/Method.h" -#include "llvm/BasicBlock.h" -#include "llvm/iTerminators.h" -#include "llvm/iOther.h" -#include "llvm/ConstPoolVals.h" -#include "llvm/ConstantPool.h" -#include "llvm/Opt/AllOpts.h" -#include "llvm/Opt/ConstantHandling.h" - -// Merge identical constant values in the constant pool. -// -// TODO: We can do better than this simplistic N^2 algorithm... -// -bool DoConstantPoolMerging(Method *M) { - return DoConstantPoolMerging(M->getConstantPool()); -} - -bool DoConstantPoolMerging(ConstantPool &CP) { - bool Modified = false; - for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI) { - for (ConstantPool::PlaneType::iterator I = (*PI)->begin(); - I != (*PI)->end(); ++I) { - ConstPoolVal *C = *I; - - ConstantPool::PlaneType::iterator J = I; - for (++J; J != (*PI)->end(); ++J) { - if (C->equals(*J)) { - Modified = true; - // Okay we know that *I == *J. So now we need to make all uses of *I - // point to *J. - // - C->replaceAllUsesWith(*J); - - (*PI)->remove(I); // Remove C from constant pool... - - if (C->hasName() && !(*J)->hasName()) // The merged constant inherits - (*J)->setName(C->getName()); // the old name... - - delete C; // Delete the constant itself. - break; // Break out of inner for loop - } - } +#define DEBUG_TYPE "constprop" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Constant.h" +#include "llvm/Instruction.h" +#include "llvm/Pass.h" +#include "llvm/Support/InstIterator.h" +#include "llvm/ADT/Statistic.h" +#include +using namespace llvm; + +STATISTIC(NumInstKilled, "Number of instructions killed"); + +namespace { + struct ConstantPropagation : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + ConstantPropagation() : FunctionPass(ID) { + initializeConstantPropagationPass(*PassRegistry::getPassRegistry()); } - } - return Modified; -} - -inline static bool -ConstantFoldUnaryInst(Method *M, Method::inst_iterator &DI, - UnaryOperator *Op, ConstPoolVal *D) { - ConstPoolVal *ReplaceWith = - ConstantFoldUnaryInstruction(Op->getInstType(), D); - - if (!ReplaceWith) return false; // Nothing new to change... - - - // Add the new value to the constant pool... - M->getConstantPool().insert(ReplaceWith); - - // Replaces all of the uses of a variable with uses of the constant. - Op->replaceAllUsesWith(ReplaceWith); - - // Remove the operator from the list of definitions... - Op->getParent()->getInstList().remove(DI.getInstructionIterator()); - - // The new constant inherits the old name of the operator... - if (Op->hasName()) ReplaceWith->setName(Op->getName()); - - // Delete the operator now... - delete Op; - return true; -} - -inline static bool -ConstantFoldBinaryInst(Method *M, Method::inst_iterator &DI, - BinaryOperator *Op, - ConstPoolVal *D1, ConstPoolVal *D2) { - ConstPoolVal *ReplaceWith = - ConstantFoldBinaryInstruction(Op->getInstType(), D1, D2); - if (!ReplaceWith) return false; // Nothing new to change... - - // Add the new value to the constant pool... - M->getConstantPool().insert(ReplaceWith); - - // Replaces all of the uses of a variable with uses of the constant. - Op->replaceAllUsesWith(ReplaceWith); - - // Remove the operator from the list of definitions... - Op->getParent()->getInstList().remove(DI.getInstructionIterator()); - - // The new constant inherits the old name of the operator... - if (Op->hasName()) ReplaceWith->setName(Op->getName()); - - // Delete the operator now... - delete Op; - return true; -} -inline static bool ConstantFoldTerminator(TerminatorInst *T) { - // Branch - See if we are conditional jumping on constant - if (T->getInstType() == Instruction::Br) { - BranchInst *BI = (BranchInst*)T; - if (!BI->isUnconditional() && // Are we branching on constant? - BI->getOperand(2)->isConstant()) { - // YES. Change to unconditional branch... - ConstPoolBool *Cond = (ConstPoolBool*)BI->getOperand(2); - Value *Destination = BI->getOperand(Cond->getValue() ? 0 : 1); + bool runOnFunction(Function &F); - BI->setOperand(0, Destination); // Set the unconditional destination - BI->setOperand(1, 0); // Clear the conditional destination - BI->setOperand(2, 0); // Clear the condition... - return true; + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); } - } - return false; + }; } -// ConstantFoldInstruction - If an instruction references constants, try to fold -// them together... -// -inline static bool -ConstantFoldInstruction(Method *M, Method::inst_iterator &II) { - Instruction *Inst = *II; - if (Inst->isBinaryOp()) { - ConstPoolVal *D1 = Inst->getOperand(0)->castConstant(); - ConstPoolVal *D2 = Inst->getOperand(1)->castConstant(); - - if (D1 && D2) - return ConstantFoldBinaryInst(M, II, (BinaryOperator*)Inst, D1, D2); - - } else if (Inst->isUnaryOp()) { - ConstPoolVal *D = Inst->getOperand(0)->castConstant(); - if (D) return ConstantFoldUnaryInst(M, II, (UnaryOperator*)Inst, D); - } else if (Inst->isTerminator()) { - return ConstantFoldTerminator((TerminatorInst*)Inst); +char ConstantPropagation::ID = 0; +INITIALIZE_PASS(ConstantPropagation, "constprop", + "Simple constant propagation", false, false) - } else if (Inst->isPHINode()) { - PHINode *PN = (PHINode*)Inst; // If it's a PHI node and only has one operand - // Then replace it directly with that operand. - assert(PN->getOperand(0) && "PHI Node must have at least one operand!"); - if (PN->getOperand(1) == 0) { // If the PHI Node has exactly 1 operand - Value *V = PN->getOperand(0); - PN->replaceAllUsesWith(V); // Replace all uses of this PHI - // Unlink from basic block - PN->getParent()->getInstList().remove(II.getInstructionIterator()); - if (PN->hasName()) V->setName(PN->getName()); // Inherit PHINode name - delete PN; // Finally, delete the node... - return true; - } - } - return false; +FunctionPass *llvm::createConstantPropagationPass() { + return new ConstantPropagation(); } -// DoConstPropPass - Propogate constants and do constant folding on instructions -// this returns true if something was changed, false if nothing was changed. -// -static bool DoConstPropPass(Method *M) { - bool SomethingChanged = false; - -#if 1 - Method::inst_iterator It = M->inst_begin(); - while (It != M->inst_end()) - if (ConstantFoldInstruction(M, It)) { - SomethingChanged = true; // If returned true, iter is already incremented - - // Incrementing the iterator in an unchecked manner could mess up the - // internals of 'It'. To make sure everything is happy, tell it we might - // have broken it. - It.resyncInstructionIterator(); - } else { - ++It; - } -#else - for (Method::iterator BBIt = M->begin(); BBIt != M->end(); ++BBIt) { - BasicBlock *BB = *BBIt; - reduce_apply_bool(BB->begin(), BB->end(), - bind1st(ConstantFoldInstruction, M)); +bool ConstantPropagation::runOnFunction(Function &F) { + // Initialize the worklist to all of the instructions ready to process... + std::set WorkList; + for(inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { + WorkList.insert(&*i); } -#endif - return SomethingChanged; -} - - -// returns true on failure, false on success... -// -bool DoConstantPropogation(Method *M) { - bool Modified = false; - - // Fold constants until we make no progress... - while (DoConstPropPass(M)) Modified = true; - - // Merge identical constants last: this is important because we may have just - // introduced constants that already exist! - // - Modified |= DoConstantPoolMerging(M->getConstantPool()); - - return Modified; + bool Changed = false; + + while (!WorkList.empty()) { + Instruction *I = *WorkList.begin(); + WorkList.erase(WorkList.begin()); // Get an element from the worklist... + + if (!I->use_empty()) // Don't muck with dead instructions... + if (Constant *C = ConstantFoldInstruction(I)) { + // Add all of the users of this instruction to the worklist, they might + // be constant propagatable now... + for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); + UI != UE; ++UI) + WorkList.insert(cast(*UI)); + + // Replace all of the uses of a variable with uses of the constant. + I->replaceAllUsesWith(C); + + // Remove the dead instruction. + WorkList.erase(I); + I->eraseFromParent(); + + // We made a change to the function... + Changed = true; + ++NumInstKilled; + } + } + return Changed; }