X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FIPConstantPropagation.cpp;h=af541d1552545b3641426dcb320110e697cf6849;hb=5a81e143850a8e9dfa2cab9153b24f0464aa7837;hp=dc8698e1622d13179a5edc9e5813a4820ccafcd9;hpb=d358e6fed51113b216756ea08fa361bb82022df2;p=oota-llvm.git diff --git a/lib/Transforms/IPO/IPConstantPropagation.cpp b/lib/Transforms/IPO/IPConstantPropagation.cpp index dc8698e1622..af541d15525 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 @@ -16,95 +16,264 @@ //===----------------------------------------------------------------------===// #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/CallSite.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"); +#define DEBUG_TYPE "ipconstprop" +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) override; 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 (Use &U : F.uses()) { + User *UR = U.getUser(); + // Ignore blockaddress uses. + if (isa(UR)) continue; + + // Used by a non-instruction, or not the callee of a function, do not + // transform. + if (!isa(UR) && !isa(UR)) + return false; + + CallSite CS(cast(UR)); + if (!CS.isCallee(&U)) + 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 == nullptr) { + 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->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory())) + continue; + + Value *V = ArgumentConstants[i].first; + if (!V) 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] = nullptr; + // 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!"); - AI->replaceAllUsesWith(ArgumentConstants[i].first); - ++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 (Use &U : F.uses()) { + CallSite CS(U.getUser()); + Instruction* Call = CS.getInstruction(); + + // Not a call instruction or a call instruction that's not calling F + // directly? + if (!Call || !CS.isCallee(&U)) + continue; + + // Call result not used? + if (Call->use_empty()) + continue; + + MadeChange = true; + + if (!STy) { + 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; } - return true; + + for (auto I = Call->user_begin(), E = Call->user_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(); + } + } + } + } + + if (MadeChange) ++NumReturnValProped; + return MadeChange; }