X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FIPConstantPropagation.cpp;h=4ac1dfc09682884d92745620b59e9773681a4fea;hb=0b8c9a80f20772c3793201ab5b251d3520b9cea3;hp=bb21f11ffc3e88b16b64cdb7e4e3338cf3b4a6a2;hpb=2e56dd82b3b3ab9dde8cc55c06df78cec4dbd3b7;p=oota-llvm.git diff --git a/lib/Transforms/IPO/IPConstantPropagation.cpp b/lib/Transforms/IPO/IPConstantPropagation.cpp index bb21f11ffc3..4ac1dfc0968 100644 --- a/lib/Transforms/IPO/IPConstantPropagation.cpp +++ b/lib/Transforms/IPO/IPConstantPropagation.cpp @@ -1,10 +1,10 @@ //===-- IPConstantPropagation.cpp - Propagate constants through calls -----===// -// +// // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// //===----------------------------------------------------------------------===// // // This pass implements an _extremely_ simple interprocedural constant @@ -15,99 +15,265 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "ipconstprop" #include "llvm/Transforms/IPO.h" -#include "llvm/Module.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" #include "llvm/Pass.h" -#include "llvm/Constants.h" #include "llvm/Support/CallSite.h" -#include "Support/Statistic.h" +using namespace llvm; -namespace { - Statistic<> NumArgumentsProped("ipconstprop", - "Number of args turned into constants"); +STATISTIC(NumArgumentsProped, "Number of args turned into constants"); +STATISTIC(NumReturnValProped, "Number of return values turned into constants"); +namespace { /// IPCP - The interprocedural constant propagation pass /// - struct IPCP : public Pass { - bool run(Module &M); + struct IPCP : public ModulePass { + static char ID; // Pass identification, replacement for typeid + IPCP() : ModulePass(ID) { + initializeIPCPPass(*PassRegistry::getPassRegistry()); + } + + bool runOnModule(Module &M); private: - bool processFunction(Function &F); + bool PropagateConstantsIntoArguments(Function &F); + bool PropagateConstantReturn(Function &F); }; - RegisterOpt X("ipconstprop", "Interprocedural constant propagation"); } -Pass *createIPConstantPropagationPass() { return new IPCP(); } +char IPCP::ID = 0; +INITIALIZE_PASS(IPCP, "ipconstprop", + "Interprocedural constant propagation", false, false) + +ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); } -bool IPCP::run(Module &M) { +bool IPCP::runOnModule(Module &M) { bool Changed = false; - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (!I->isExternal() && I->hasInternalLinkage()) - Changed |= processFunction(*I); + bool LocalChange = true; + + // FIXME: instead of using smart algorithms, we just iterate until we stop + // making changes. + while (LocalChange) { + LocalChange = false; + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + if (!I->isDeclaration()) { + // Delete any klingons. + I->removeDeadConstantUsers(); + if (I->hasLocalLinkage()) + LocalChange |= PropagateConstantsIntoArguments(*I); + Changed |= PropagateConstantReturn(*I); + } + Changed |= LocalChange; + } return Changed; } -/// processFunction - Look at all uses of the specified function. If all uses -/// are direct call sites, and all pass a particular constant in for an -/// argument, propagate that constant in as the argument. +/// PropagateConstantsIntoArguments - Look at all uses of the specified +/// function. If all uses are direct call sites, and all pass a particular +/// constant in for an argument, propagate that constant in as the argument. /// -bool IPCP::processFunction(Function &F) { - if (F.aempty() || F.use_empty()) return false; // No arguments? Early exit. +bool IPCP::PropagateConstantsIntoArguments(Function &F) { + if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit. - std::vector > ArgumentConstants; - ArgumentConstants.resize(F.asize()); + // For each argument, keep track of its constant value and whether it is a + // constant or not. The bool is driven to true when found to be non-constant. + SmallVector, 16> ArgumentConstants; + ArgumentConstants.resize(F.arg_size()); unsigned NumNonconstant = 0; + for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { + User *U = *UI; + // Ignore blockaddress uses. + if (isa(U)) continue; + + // Used by a non-instruction, or not the callee of a function, do not + // transform. + if (!isa(U) && !isa(U)) + return false; + + CallSite CS(cast(U)); + if (!CS.isCallee(UI)) + return false; - for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) - if (!isa(*I)) - return false; // Used by a non-instruction, do not transform - else { - CallSite CS = CallSite::get(cast(*I)); - if (CS.getInstruction() == 0 || - CS.getCalledFunction() != &F) - return false; // Not a direct call site? + // Check out all of the potentially constant arguments. Note that we don't + // inspect varargs here. + CallSite::arg_iterator AI = CS.arg_begin(); + Function::arg_iterator Arg = F.arg_begin(); + for (unsigned i = 0, e = ArgumentConstants.size(); i != e; + ++i, ++AI, ++Arg) { - // Check out all of the potentially constant arguments - CallSite::arg_iterator AI = CS.arg_begin(); - for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) { - if (*AI == &F) return false; // Passes the function into itself - - if (!ArgumentConstants[i].second) { - if (isa(*AI) || isa(*AI)) { - Constant *C = dyn_cast(*AI); - if (!C) C = ConstantPointerRef::get(cast(*AI)); - - if (!ArgumentConstants[i].first) - ArgumentConstants[i].first = C; - else if (ArgumentConstants[i].first != C) { - // Became non-constant - ArgumentConstants[i].second = true; - ++NumNonconstant; - if (NumNonconstant == ArgumentConstants.size()) return false; + // If this argument is known non-constant, ignore it. + if (ArgumentConstants[i].second) + continue; + + Constant *C = dyn_cast(*AI); + if (C && ArgumentConstants[i].first == 0) { + ArgumentConstants[i].first = C; // First constant seen. + } else if (C && ArgumentConstants[i].first == C) { + // Still the constant value we think it is. + } else if (*AI == &*Arg) { + // Ignore recursive calls passing argument down. + } else { + // Argument became non-constant. If all arguments are non-constant now, + // give up on this function. + if (++NumNonconstant == ArgumentConstants.size()) + return false; + ArgumentConstants[i].second = true; + } + } + } + + // If we got to this point, there is a constant argument! + assert(NumNonconstant != ArgumentConstants.size()); + bool MadeChange = false; + Function::arg_iterator AI = F.arg_begin(); + for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) { + // Do we have a constant argument? + if (ArgumentConstants[i].second || AI->use_empty() || + (AI->hasByValAttr() && !F.onlyReadsMemory())) + continue; + + Value *V = ArgumentConstants[i].first; + if (V == 0) V = UndefValue::get(AI->getType()); + AI->replaceAllUsesWith(V); + ++NumArgumentsProped; + MadeChange = true; + } + return MadeChange; +} + + +// Check to see if this function returns one or more constants. If so, replace +// all callers that use those return values with the constant value. This will +// leave in the actual return values and instructions, but deadargelim will +// clean that up. +// +// Additionally if a function always returns one of its arguments directly, +// callers will be updated to use the value they pass in directly instead of +// using the return value. +bool IPCP::PropagateConstantReturn(Function &F) { + if (F.getReturnType()->isVoidTy()) + return false; // No return value. + + // If this function could be overridden later in the link stage, we can't + // propagate information about its results into callers. + if (F.mayBeOverridden()) + return false; + + // Check to see if this function returns a constant. + SmallVector RetVals; + StructType *STy = dyn_cast(F.getReturnType()); + if (STy) + for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) + RetVals.push_back(UndefValue::get(STy->getElementType(i))); + else + RetVals.push_back(UndefValue::get(F.getReturnType())); + + unsigned NumNonConstant = 0; + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) + if (ReturnInst *RI = dyn_cast(BB->getTerminator())) { + for (unsigned i = 0, e = RetVals.size(); i != e; ++i) { + // Already found conflicting return values? + Value *RV = RetVals[i]; + if (!RV) + continue; + + // Find the returned value + Value *V; + if (!STy) + V = RI->getOperand(0); + else + V = FindInsertedValue(RI->getOperand(0), i); + + if (V) { + // Ignore undefs, we can change them into anything + if (isa(V)) + continue; + + // Try to see if all the rets return the same constant or argument. + if (isa(V) || isa(V)) { + if (isa(RV)) { + // No value found yet? Try the current one. + RetVals[i] = V; + continue; } - } else { - // This is not a constant argument. Mark the argument as - // non-constant. - ArgumentConstants[i].second = true; - ++NumNonconstant; - if (NumNonconstant == ArgumentConstants.size()) return false; + // Returning the same value? Good. + if (RV == V) + continue; } } + // Different or no known return value? Don't propagate this return + // value. + RetVals[i] = 0; + // All values non constant? Stop looking. + if (++NumNonConstant == RetVals.size()) + return false; } } - // If we got to this point, there is a constant argument! - assert(NumNonconstant != ArgumentConstants.size()); - Function::aiterator AI = F.abegin(); - for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) - // Do we have a constant argument!? - if (!ArgumentConstants[i].second) { - assert(ArgumentConstants[i].first && "Unknown constant value!"); - Value *V = ArgumentConstants[i].first; - if (ConstantPointerRef *CPR = dyn_cast(V)) - V = CPR->getValue(); - AI->replaceAllUsesWith(V); - ++NumArgumentsProped; + // If we got here, the function returns at least one constant value. Loop + // over all users, replacing any uses of the return value with the returned + // constant. + bool MadeChange = false; + for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { + CallSite CS(*UI); + Instruction* Call = CS.getInstruction(); + + // Not a call instruction or a call instruction that's not calling F + // directly? + if (!Call || !CS.isCallee(UI)) + continue; + + // Call result not used? + if (Call->use_empty()) + continue; + + MadeChange = true; + + if (STy == 0) { + Value* New = RetVals[0]; + if (Argument *A = dyn_cast(New)) + // Was an argument returned? Then find the corresponding argument in + // the call instruction and use that. + New = CS.getArgument(A->getArgNo()); + Call->replaceAllUsesWith(New); + continue; + } + + for (Value::use_iterator I = Call->use_begin(), E = Call->use_end(); + I != E;) { + Instruction *Ins = cast(*I); + + // Increment now, so we can remove the use + ++I; + + // Find the index of the retval to replace with + int index = -1; + if (ExtractValueInst *EV = dyn_cast(Ins)) + if (EV->hasIndices()) + index = *EV->idx_begin(); + + // If this use uses a specific return value, and we have a replacement, + // replace it. + if (index != -1) { + Value *New = RetVals[index]; + if (New) { + if (Argument *A = dyn_cast(New)) + // Was an argument returned? Then find the corresponding argument in + // the call instruction and use that. + New = CS.getArgument(A->getArgNo()); + Ins->replaceAllUsesWith(New); + Ins->eraseFromParent(); + } + } } - return true; + } + + if (MadeChange) ++NumReturnValProped; + return MadeChange; }