//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "argpromotion"
#include "llvm/Transforms/IPO.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
-#include "llvm/Support/CFG.h"
-#include "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <set>
using namespace llvm;
+#define DEBUG_TYPE "argpromotion"
+
STATISTIC(NumArgumentsPromoted , "Number of pointer arguments promoted");
STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted");
STATISTIC(NumByValArgsPromoted , "Number of byval arguments promoted");
/// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
///
struct ArgPromotion : public CallGraphSCCPass {
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<AliasAnalysis>();
CallGraphSCCPass::getAnalysisUsage(AU);
}
- virtual bool runOnSCC(CallGraphSCC &SCC);
+ bool runOnSCC(CallGraphSCC &SCC) override;
static char ID; // Pass identification, replacement for typeid
explicit ArgPromotion(unsigned maxElements = 3)
- : CallGraphSCCPass(ID), maxElements(maxElements) {
+ : CallGraphSCCPass(ID), DL(nullptr), maxElements(maxElements) {
initializeArgPromotionPass(*PassRegistry::getPassRegistry());
}
/// A vector used to hold the indices of a single GEP instruction
typedef std::vector<uint64_t> IndicesVector;
+ const DataLayout *DL;
private:
CallGraphNode *PromoteArguments(CallGraphNode *CGN);
bool isSafeToPromoteArgument(Argument *Arg, bool isByVal) const;
CallGraphNode *DoPromotion(Function *F,
- SmallPtrSet<Argument*, 8> &ArgsToPromote,
- SmallPtrSet<Argument*, 8> &ByValArgsToTransform);
+ SmallPtrSetImpl<Argument*> &ArgsToPromote,
+ SmallPtrSetImpl<Argument*> &ByValArgsToTransform);
+
+ using llvm::Pass::doInitialization;
+ bool doInitialization(CallGraph &CG) override;
/// The maximum number of elements to expand, or 0 for unlimited.
unsigned maxElements;
+ DenseMap<const Function *, DISubprogram> FunctionDIs;
};
}
INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion",
"Promote 'by reference' arguments to scalars", false, false)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
-INITIALIZE_AG_DEPENDENCY(CallGraph)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_END(ArgPromotion, "argpromotion",
"Promote 'by reference' arguments to scalars", false, false)
bool ArgPromotion::runOnSCC(CallGraphSCC &SCC) {
bool Changed = false, LocalChange;
+ DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
+ DL = DLP ? &DLP->getDataLayout() : nullptr;
+
do { // Iterate until we stop promoting from this SCC.
LocalChange = false;
// Attempt to promote arguments from all functions in this SCC.
Function *F = CGN->getFunction();
// Make sure that it is local to this module.
- if (!F || !F->hasLocalLinkage()) return 0;
+ if (!F || !F->hasLocalLinkage()) return nullptr;
// First check: see if there are any pointer arguments! If not, quick exit.
- SmallVector<std::pair<Argument*, unsigned>, 16> PointerArgs;
- unsigned ArgNo = 0;
- for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
- I != E; ++I, ++ArgNo)
+ SmallVector<Argument*, 16> PointerArgs;
+ for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
if (I->getType()->isPointerTy())
- PointerArgs.push_back(std::pair<Argument*, unsigned>(I, ArgNo));
- if (PointerArgs.empty()) return 0;
+ PointerArgs.push_back(I);
+ if (PointerArgs.empty()) return nullptr;
// Second check: make sure that all callers are direct callers. We can't
// transform functions that have indirect callers. Also see if the function
// is self-recursive.
bool isSelfRecursive = false;
- for (Value::use_iterator UI = F->use_begin(), E = F->use_end();
- UI != E; ++UI) {
- CallSite CS(*UI);
+ for (Use &U : F->uses()) {
+ CallSite CS(U.getUser());
// Must be a direct call.
- if (CS.getInstruction() == 0 || !CS.isCallee(UI)) return 0;
+ if (CS.getInstruction() == nullptr || !CS.isCallee(&U)) return nullptr;
if (CS.getInstruction()->getParent()->getParent() == F)
isSelfRecursive = true;
}
+ // Don't promote arguments for variadic functions. Adding, removing, or
+ // changing non-pack parameters can change the classification of pack
+ // parameters. Frontends encode that classification at the call site in the
+ // IR, while in the callee the classification is determined dynamically based
+ // on the number of registers consumed so far.
+ if (F->isVarArg()) return nullptr;
+
// Check to see which arguments are promotable. If an argument is promotable,
// add it to ArgsToPromote.
SmallPtrSet<Argument*, 8> ArgsToPromote;
SmallPtrSet<Argument*, 8> ByValArgsToTransform;
- for (unsigned i = 0; i != PointerArgs.size(); ++i) {
- bool isByVal=F->getAttributes().
- hasAttribute(PointerArgs[i].second+1, Attribute::ByVal);
- Argument *PtrArg = PointerArgs[i].first;
+ for (unsigned i = 0, e = PointerArgs.size(); i != e; ++i) {
+ Argument *PtrArg = PointerArgs[i];
Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
// If this is a byval argument, and if the aggregate type is small, just
- // pass the elements, which is always safe.
- if (isByVal) {
+ // pass the elements, which is always safe. This does not apply to
+ // inalloca.
+ if (PtrArg->hasByValAttr()) {
if (StructType *STy = dyn_cast<StructType>(AgTy)) {
if (maxElements > 0 && STy->getNumElements() > maxElements) {
DEBUG(dbgs() << "argpromotion disable promoting argument '"
}
// Otherwise, see if we can promote the pointer to its value.
- if (isSafeToPromoteArgument(PtrArg, isByVal))
+ if (isSafeToPromoteArgument(PtrArg, PtrArg->hasByValOrInAllocaAttr()))
ArgsToPromote.insert(PtrArg);
}
// No promotable pointer arguments.
if (ArgsToPromote.empty() && ByValArgsToTransform.empty())
- return 0;
+ return nullptr;
return DoPromotion(F, ArgsToPromote, ByValArgsToTransform);
}
/// AllCallersPassInValidPointerForArgument - Return true if we can prove that
/// all callees pass in a valid pointer for the specified function argument.
-static bool AllCallersPassInValidPointerForArgument(Argument *Arg) {
+static bool AllCallersPassInValidPointerForArgument(Argument *Arg,
+ const DataLayout *DL) {
Function *Callee = Arg->getParent();
- unsigned ArgNo = std::distance(Callee->arg_begin(),
- Function::arg_iterator(Arg));
+ unsigned ArgNo = Arg->getArgNo();
// Look at all call sites of the function. At this pointer we know we only
// have direct callees.
- for (Value::use_iterator UI = Callee->use_begin(), E = Callee->use_end();
- UI != E; ++UI) {
- CallSite CS(*UI);
+ for (User *U : Callee->users()) {
+ CallSite CS(U);
assert(CS && "Should only have direct calls!");
- if (!CS.getArgument(ArgNo)->isDereferenceablePointer())
+ if (!CS.getArgument(ArgNo)->isDereferenceablePointer(DL))
return false;
}
return true;
/// This method limits promotion of aggregates to only promote up to three
/// elements of the aggregate in order to avoid exploding the number of
/// arguments passed in.
-bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const {
+bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg,
+ bool isByValOrInAlloca) const {
typedef std::set<IndicesVector> GEPIndicesSet;
// Quick exit for unused arguments
//
// This set will contain all sets of indices that are loaded in the entry
// block, and thus are safe to unconditionally load in the caller.
+ //
+ // This optimization is also safe for InAlloca parameters, because it verifies
+ // that the address isn't captured.
GEPIndicesSet SafeToUnconditionallyLoad;
// This set contains all the sets of indices that we are planning to promote.
GEPIndicesSet ToPromote;
// If the pointer is always valid, any load with first index 0 is valid.
- if (isByVal || AllCallersPassInValidPointerForArgument(Arg))
+ if (isByValOrInAlloca || AllCallersPassInValidPointerForArgument(Arg, DL))
SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
// First, iterate the entry block and mark loads of (geps of) arguments as
// not (GEP+)loads, or any (GEP+)loads that are not safe to promote.
SmallVector<LoadInst*, 16> Loads;
IndicesVector Operands;
- for (Value::use_iterator UI = Arg->use_begin(), E = Arg->use_end();
- UI != E; ++UI) {
- User *U = *UI;
+ for (Use &U : Arg->uses()) {
+ User *UR = U.getUser();
Operands.clear();
- if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
+ if (LoadInst *LI = dyn_cast<LoadInst>(UR)) {
// Don't hack volatile/atomic loads
if (!LI->isSimple()) return false;
Loads.push_back(LI);
// Direct loads are equivalent to a GEP with a zero index and then a load.
Operands.push_back(0);
- } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
+ } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) {
if (GEP->use_empty()) {
// Dead GEP's cause trouble later. Just remove them if we run into
// them.
// TODO: This runs the above loop over and over again for dead GEPs
// Couldn't we just do increment the UI iterator earlier and erase the
// use?
- return isSafeToPromoteArgument(Arg, isByVal);
+ return isSafeToPromoteArgument(Arg, isByValOrInAlloca);
}
// Ensure that all of the indices are constants.
return false; // Not a constant operand GEP!
// Ensure that the only users of the GEP are load instructions.
- for (Value::use_iterator UI = GEP->use_begin(), E = GEP->use_end();
- UI != E; ++UI)
- if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
+ for (User *GEPU : GEP->users())
+ if (LoadInst *LI = dyn_cast<LoadInst>(GEPU)) {
// Don't hack volatile/atomic loads
if (!LI->isSimple()) return false;
Loads.push_back(LI);
// loading block.
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
BasicBlock *P = *PI;
- for (idf_ext_iterator<BasicBlock*, SmallPtrSet<BasicBlock*, 16> >
- I = idf_ext_begin(P, TranspBlocks),
- E = idf_ext_end(P, TranspBlocks); I != E; ++I)
- if (AA.canBasicBlockModify(**I, Loc))
+ for (BasicBlock *TranspBB : inverse_depth_first_ext(P, TranspBlocks))
+ if (AA.canBasicBlockModify(*TranspBB, Loc))
return false;
}
}
/// arguments, and returns the new function. At this point, we know that it's
/// safe to do so.
CallGraphNode *ArgPromotion::DoPromotion(Function *F,
- SmallPtrSet<Argument*, 8> &ArgsToPromote,
- SmallPtrSet<Argument*, 8> &ByValArgsToTransform) {
+ SmallPtrSetImpl<Argument*> &ArgsToPromote,
+ SmallPtrSetImpl<Argument*> &ByValArgsToTransform) {
// Start by computing a new prototype for the function, which is the same as
// the old function, but has modified arguments.
// OriginalLoads - Keep track of a representative load instruction from the
// original function so that we can tell the alias analysis implementation
// what the new GEP/Load instructions we are inserting look like.
- std::map<IndicesVector, LoadInst*> OriginalLoads;
+ // We need to keep the original loads for each argument and the elements
+ // of the argument that are accessed.
+ std::map<std::pair<Argument*, IndicesVector>, LoadInst*> OriginalLoads;
// Attribute - Keep track of the parameter attributes for the arguments
// that we are *not* promoting. For the ones that we do promote, the parameter
// attributes are lost
- SmallVector<AttributeWithIndex, 8> AttributesVec;
+ SmallVector<AttributeSet, 8> AttributesVec;
const AttributeSet &PAL = F->getAttributes();
// Add any return attributes.
if (PAL.hasAttributes(AttributeSet::ReturnIndex))
- AttributesVec.push_back(AttributeWithIndex::get(AttributeSet::ReturnIndex,
- PAL.getRetAttributes()));
+ AttributesVec.push_back(AttributeSet::get(F->getContext(),
+ PAL.getRetAttributes()));
// First, determine the new argument list
unsigned ArgIndex = 1;
} else if (!ArgsToPromote.count(I)) {
// Unchanged argument
Params.push_back(I->getType());
- Attribute attrs = PAL.getParamAttributes(ArgIndex);
- if (attrs.hasAttributes())
- AttributesVec.push_back(AttributeWithIndex::get(Params.size(), attrs));
+ AttributeSet attrs = PAL.getParamAttributes(ArgIndex);
+ if (attrs.hasAttributes(ArgIndex)) {
+ AttrBuilder B(attrs, ArgIndex);
+ AttributesVec.
+ push_back(AttributeSet::get(F->getContext(), Params.size(), B));
+ }
} else if (I->use_empty()) {
// Dead argument (which are always marked as promotable)
++NumArgumentsDead;
// In this table, we will track which indices are loaded from the argument
// (where direct loads are tracked as no indices).
ScalarizeTable &ArgIndices = ScalarizedElements[I];
- for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
- ++UI) {
- Instruction *User = cast<Instruction>(*UI);
- assert(isa<LoadInst>(User) || isa<GetElementPtrInst>(User));
+ for (User *U : I->users()) {
+ Instruction *UI = cast<Instruction>(U);
+ assert(isa<LoadInst>(UI) || isa<GetElementPtrInst>(UI));
IndicesVector Indices;
- Indices.reserve(User->getNumOperands() - 1);
+ Indices.reserve(UI->getNumOperands() - 1);
// Since loads will only have a single operand, and GEPs only a single
// non-index operand, this will record direct loads without any indices,
// and gep+loads with the GEP indices.
- for (User::op_iterator II = User->op_begin() + 1, IE = User->op_end();
+ for (User::op_iterator II = UI->op_begin() + 1, IE = UI->op_end();
II != IE; ++II)
Indices.push_back(cast<ConstantInt>(*II)->getSExtValue());
// GEPs with a single 0 index can be merged with direct loads
Indices.clear();
ArgIndices.insert(Indices);
LoadInst *OrigLoad;
- if (LoadInst *L = dyn_cast<LoadInst>(User))
+ if (LoadInst *L = dyn_cast<LoadInst>(UI))
OrigLoad = L;
else
// Take any load, we will use it only to update Alias Analysis
- OrigLoad = cast<LoadInst>(User->use_back());
- OriginalLoads[Indices] = OrigLoad;
+ OrigLoad = cast<LoadInst>(UI->user_back());
+ OriginalLoads[std::make_pair(I, Indices)] = OrigLoad;
}
// Add a parameter to the function for each element passed in.
// Add any function attributes.
if (PAL.hasAttributes(AttributeSet::FunctionIndex))
- AttributesVec.push_back(AttributeWithIndex::get(FTy->getContext(),
- AttributeSet::FunctionIndex,
- PAL.getFnAttributes()));
+ AttributesVec.push_back(AttributeSet::get(FTy->getContext(),
+ PAL.getFnAttributes()));
Type *RetTy = FTy->getReturnType();
Function *NF = Function::Create(NFTy, F->getLinkage(), F->getName());
NF->copyAttributesFrom(F);
-
+ // Patch the pointer to LLVM function in debug info descriptor.
+ auto DI = FunctionDIs.find(F);
+ if (DI != FunctionDIs.end()) {
+ DISubprogram SP = DI->second;
+ SP.replaceFunction(NF);
+ FunctionDIs.erase(DI);
+ FunctionDIs[NF] = SP;
+ }
+
DEBUG(dbgs() << "ARG PROMOTION: Promoting to:" << *NF << "\n"
<< "From: " << *F);
// Get the callgraph information that we need to update to reflect our
// changes.
- CallGraph &CG = getAnalysis<CallGraph>();
-
+ CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+
// Get a new callgraph node for NF.
CallGraphNode *NF_CGN = CG.getOrInsertFunction(NF);
//
SmallVector<Value*, 16> Args;
while (!F->use_empty()) {
- CallSite CS(F->use_back());
+ CallSite CS(F->user_back());
assert(CS.getCalledFunction() == F);
Instruction *Call = CS.getInstruction();
const AttributeSet &CallPAL = CS.getAttributes();
// Add any return attributes.
if (CallPAL.hasAttributes(AttributeSet::ReturnIndex))
- AttributesVec.push_back(AttributeWithIndex::get(AttributeSet::ReturnIndex,
- CallPAL.getRetAttributes()));
+ AttributesVec.push_back(AttributeSet::get(F->getContext(),
+ CallPAL.getRetAttributes()));
// Loop over the operands, inserting GEP and loads in the caller as
// appropriate.
if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) {
Args.push_back(*AI); // Unmodified argument
- Attribute Attrs = CallPAL.getParamAttributes(ArgIndex);
- if (Attrs.hasAttributes())
- AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs));
-
+ if (CallPAL.hasAttributes(ArgIndex)) {
+ AttrBuilder B(CallPAL, ArgIndex);
+ AttributesVec.
+ push_back(AttributeSet::get(F->getContext(), Args.size(), B));
+ }
} else if (ByValArgsToTransform.count(I)) {
// Emit a GEP and load for each element of the struct.
Type *AgTy = cast<PointerType>(I->getType())->getElementType();
StructType *STy = cast<StructType>(AgTy);
Value *Idxs[2] = {
- ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), 0 };
+ ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), nullptr };
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i);
Value *Idx = GetElementPtrInst::Create(*AI, Idxs,
for (ScalarizeTable::iterator SI = ArgIndices.begin(),
E = ArgIndices.end(); SI != E; ++SI) {
Value *V = *AI;
- LoadInst *OrigLoad = OriginalLoads[*SI];
+ LoadInst *OrigLoad = OriginalLoads[std::make_pair(I, *SI)];
if (!SI->empty()) {
Ops.reserve(SI->size());
Type *ElTy = V->getType();
// of the previous load.
LoadInst *newLoad = new LoadInst(V, V->getName()+".val", Call);
newLoad->setAlignment(OrigLoad->getAlignment());
- // Transfer the TBAA info too.
- newLoad->setMetadata(LLVMContext::MD_tbaa,
- OrigLoad->getMetadata(LLVMContext::MD_tbaa));
+ // Transfer the AA info too.
+ AAMDNodes AAInfo;
+ OrigLoad->getAAMetadata(AAInfo);
+ newLoad->setAAMetadata(AAInfo);
+
Args.push_back(newLoad);
AA.copyValue(OrigLoad, Args.back());
}
// Push any varargs arguments on the list.
for (; AI != CS.arg_end(); ++AI, ++ArgIndex) {
Args.push_back(*AI);
- Attribute Attrs = CallPAL.getParamAttributes(ArgIndex);
- if (Attrs.hasAttributes())
- AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs));
+ if (CallPAL.hasAttributes(ArgIndex)) {
+ AttrBuilder B(CallPAL, ArgIndex);
+ AttributesVec.
+ push_back(AttributeSet::get(F->getContext(), Args.size(), B));
+ }
}
// Add any function attributes.
if (CallPAL.hasAttributes(AttributeSet::FunctionIndex))
- AttributesVec.push_back(AttributeWithIndex::get(Call->getContext(),
- AttributeSet::FunctionIndex,
- CallPAL.getFnAttributes()));
+ AttributesVec.push_back(AttributeSet::get(Call->getContext(),
+ CallPAL.getFnAttributes()));
Instruction *New;
if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
if (cast<CallInst>(Call)->isTailCall())
cast<CallInst>(New)->setTailCall();
}
+ New->setDebugLoc(Call->getDebugLoc());
Args.clear();
AttributesVec.clear();
// Just add all the struct element types.
Type *AgTy = cast<PointerType>(I->getType())->getElementType();
- Value *TheAlloca = new AllocaInst(AgTy, 0, "", InsertPt);
+ Value *TheAlloca = new AllocaInst(AgTy, nullptr, "", InsertPt);
StructType *STy = cast<StructType>(AgTy);
Value *Idxs[2] = {
- ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), 0 };
+ ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), nullptr };
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i);
I->replaceAllUsesWith(TheAlloca);
TheAlloca->takeName(I);
AA.replaceWithNewValue(I, TheAlloca);
+
+ // If the alloca is used in a call, we must clear the tail flag since
+ // the callee now uses an alloca from the caller.
+ for (User *U : TheAlloca->users()) {
+ CallInst *Call = dyn_cast<CallInst>(U);
+ if (!Call)
+ continue;
+ Call->setTailCall(false);
+ }
continue;
}
ScalarizeTable &ArgIndices = ScalarizedElements[I];
while (!I->use_empty()) {
- if (LoadInst *LI = dyn_cast<LoadInst>(I->use_back())) {
+ if (LoadInst *LI = dyn_cast<LoadInst>(I->user_back())) {
assert(ArgIndices.begin()->empty() &&
"Load element should sort to front!");
I2->setName(I->getName()+".val");
DEBUG(dbgs() << "*** Promoted load of argument '" << I->getName()
<< "' in function '" << F->getName() << "'\n");
} else {
- GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->use_back());
+ GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->user_back());
IndicesVector Operands;
Operands.reserve(GEP->getNumIndices());
for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
// All of the uses must be load instructions. Replace them all with
// the argument specified by ArgNo.
while (!GEP->use_empty()) {
- LoadInst *L = cast<LoadInst>(GEP->use_back());
+ LoadInst *L = cast<LoadInst>(GEP->user_back());
L->replaceAllUsesWith(TheArg);
AA.replaceWithNewValue(L, TheArg);
L->eraseFromParent();
return NF_CGN;
}
+
+bool ArgPromotion::doInitialization(CallGraph &CG) {
+ FunctionDIs = makeSubprogramMap(CG.getModule());
+ return CallGraphSCCPass::doInitialization(CG);
+}