32 #define DEBUG_TYPE "argpromotion"
52 STATISTIC(NumArgumentsPromoted ,
"Number of pointer arguments promoted");
53 STATISTIC(NumAggregatesPromoted,
"Number of aggregate arguments promoted");
54 STATISTIC(NumByValArgsPromoted ,
"Number of byval arguments promoted");
55 STATISTIC(NumArgumentsDead ,
"Number of dead pointer args eliminated");
68 explicit ArgPromotion(
unsigned maxElements = 3)
74 typedef std::vector<uint64_t> IndicesVector;
78 bool isSafeToPromoteArgument(
Argument *Arg,
bool isByVal)
const;
89 "Promote 'by reference' arguments to scalars",
false,
false)
93 "Promote 'by reference' arguments to
scalars",
false, false)
96 return new ArgPromotion(maxElements);
100 bool Changed =
false, LocalChange;
111 Changed |= LocalChange;
112 }
while (LocalChange);
131 if (
I->getType()->isPointerTy())
133 if (PointerArgs.
empty())
return 0;
138 bool isSelfRecursive =
false;
143 if (CS.getInstruction() == 0 || !CS.isCallee(UI))
return 0;
145 if (CS.getInstruction()->getParent()->getParent() ==
F)
146 isSelfRecursive =
true;
153 for (
unsigned i = 0, e = PointerArgs.
size(); i != e; ++i) {
155 Type *AgTy = cast<PointerType>(PtrArg->
getType())->getElementType();
160 if (
StructType *STy = dyn_cast<StructType>(AgTy)) {
161 if (maxElements > 0 && STy->getNumElements() > maxElements) {
162 DEBUG(
dbgs() <<
"argpromotion disable promoting argument '"
163 << PtrArg->
getName() <<
"' because it would require adding more"
164 <<
" than " << maxElements <<
" arguments to the function.\n");
169 bool AllSimple =
true;
170 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
171 if (!STy->getElementType(i)->isSingleValueType()) {
181 ByValArgsToTransform.
insert(PtrArg);
189 if (isSelfRecursive) {
190 if (
StructType *STy = dyn_cast<StructType>(AgTy)) {
191 bool RecursiveType =
false;
192 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
193 if (STy->getElementType(i) == PtrArg->
getType()) {
194 RecursiveType =
true;
204 if (isSafeToPromoteArgument(PtrArg, PtrArg->
hasByValAttr()))
205 ArgsToPromote.
insert(PtrArg);
209 if (ArgsToPromote.
empty() && ByValArgsToTransform.
empty())
212 return DoPromotion(F, ArgsToPromote, ByValArgsToTransform);
227 assert(CS &&
"Should only have direct calls!");
241 const ArgPromotion::IndicesVector &Longer) {
242 if (Prefix.size() > Longer.size())
244 return std::equal(Prefix.begin(), Prefix.end(), Longer.begin());
249 static bool PrefixIn(
const ArgPromotion::IndicesVector &Indices,
250 std::set<ArgPromotion::IndicesVector> &Set) {
251 std::set<ArgPromotion::IndicesVector>::iterator Low;
252 Low = Set.upper_bound(Indices);
253 if (Low != Set.begin())
260 return Low != Set.end() &&
IsPrefix(*Low, Indices);
269 std::set<ArgPromotion::IndicesVector> &Safe) {
270 std::set<ArgPromotion::IndicesVector>::iterator Low;
271 Low = Safe.upper_bound(ToMark);
273 if (Low != Safe.begin())
278 if (Low != Safe.end()) {
288 Low = Safe.insert(Low, ToMark);
291 std::set<ArgPromotion::IndicesVector>::iterator End = Safe.end();
292 while (Low != End &&
IsPrefix(ToMark, *Low)) {
293 std::set<ArgPromotion::IndicesVector>::iterator Remove = Low;
304 bool ArgPromotion::isSafeToPromoteArgument(
Argument *Arg,
bool isByVal)
const {
305 typedef std::set<IndicesVector> GEPIndicesSet;
326 GEPIndicesSet SafeToUnconditionallyLoad;
330 GEPIndicesSet ToPromote;
334 SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
340 IndicesVector Indices;
344 Value *V =
LI->getPointerOperand();
346 V = GEP->getPointerOperand();
349 Indices.reserve(GEP->getNumIndices());
353 Indices.push_back(CI->getSExtValue());
363 }
else if (V == Arg) {
372 IndicesVector Operands;
379 if (!
LI->isSimple())
return false;
382 Operands.push_back(0);
384 if (GEP->use_empty()) {
387 getAnalysis<AliasAnalysis>().deleteValue(GEP);
388 GEP->eraseFromParent();
392 return isSafeToPromoteArgument(Arg, isByVal);
399 Operands.push_back(
C->getSExtValue());
408 if (!
LI->isSimple())
return false;
420 if (!
PrefixIn(Operands, SafeToUnconditionallyLoad))
426 if (ToPromote.find(Operands) == ToPromote.end()) {
427 if (maxElements > 0 && ToPromote.size() == maxElements) {
428 DEBUG(
dbgs() <<
"argpromotion not promoting argument '"
429 << Arg->
getName() <<
"' because it would require adding more "
430 <<
"than " << maxElements <<
" arguments to the function.\n");
435 ToPromote.insert(Operands);
439 if (Loads.
empty())
return true;
452 for (
unsigned i = 0, e = Loads.
size(); i != e; ++i) {
491 std::vector<Type*> Params;
493 typedef std::set<IndicesVector> ScalarizeTable;
502 std::map<Argument*, ScalarizeTable> ScalarizedElements;
509 std::map<std::pair<Argument*, IndicesVector>,
LoadInst*> OriginalLoads;
523 unsigned ArgIndex = 1;
526 if (ByValArgsToTransform.
count(
I)) {
528 Type *AgTy = cast<PointerType>(
I->getType())->getElementType();
532 ++NumByValArgsPromoted;
533 }
else if (!ArgsToPromote.
count(
I)) {
535 Params.push_back(
I->getType());
540 push_back(AttributeSet::get(F->
getContext(), Params.size(), B));
542 }
else if (
I->use_empty()) {
551 ScalarizeTable &ArgIndices = ScalarizedElements[
I];
555 assert(isa<LoadInst>(User) || isa<GetElementPtrInst>(User));
556 IndicesVector Indices;
563 Indices.push_back(cast<ConstantInt>(*II)->getSExtValue());
565 if (Indices.size() == 1 && Indices.front() == 0)
567 ArgIndices.insert(Indices);
569 if (
LoadInst *L = dyn_cast<LoadInst>(User))
573 OrigLoad = cast<LoadInst>(User->
use_back());
574 OriginalLoads[std::make_pair(
I, Indices)] = OrigLoad;
578 for (ScalarizeTable::iterator SI = ArgIndices.begin(),
579 E = ArgIndices.end(); SI != E; ++SI) {
582 assert(Params.back());
585 if (ArgIndices.size() == 1 && ArgIndices.begin()->empty())
586 ++NumArgumentsPromoted;
588 ++NumAggregatesPromoted;
607 DEBUG(
dbgs() <<
"ARG PROMOTION: Promoting to:" << *NF <<
"\n"
612 NF->setAttributes(AttributeSet::get(F->
getContext(), AttributesVec));
613 AttributesVec.
clear();
624 CallGraph &CG = getAnalysis<CallGraph>();
635 assert(CS.getCalledFunction() ==
F);
649 I != E; ++
I, ++AI, ++ArgIndex)
650 if (!ArgsToPromote.
count(
I) && !ByValArgsToTransform.
count(
I)) {
658 }
else if (ByValArgsToTransform.
count(
I)) {
660 Type *AgTy = cast<PointerType>(
I->getType())->getElementType();
667 (*AI)->getName()+
"."+
utostr(i),
672 }
else if (!
I->use_empty()) {
674 ScalarizeTable &ArgIndices = ScalarizedElements[
I];
677 std::vector<Value*> Ops;
678 for (ScalarizeTable::iterator SI = ArgIndices.begin(),
679 E = ArgIndices.end(); SI != E; ++SI) {
681 LoadInst *OrigLoad = OriginalLoads[std::make_pair(
I, *SI)];
683 Ops.reserve(SI->size());
685 for (IndicesVector::const_iterator II = SI->begin(),
686 IE = SI->end(); II !=
IE; ++II) {
694 ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(*II);
714 for (; AI != CS.arg_end(); ++AI, ++ArgIndex) {
725 AttributesVec.
push_back(AttributeSet::get(Call->getContext(),
729 if (
InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
732 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
733 cast<InvokeInst>(New)->setAttributes(AttributeSet::get(II->getContext(),
737 cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
738 cast<CallInst>(New)->setAttributes(AttributeSet::get(New->
getContext(),
740 if (cast<CallInst>(Call)->isTailCall())
741 cast<CallInst>(New)->setTailCall();
744 AttributesVec.
clear();
751 CallGraphNode *CalleeNode = CG[Call->getParent()->getParent()];
754 if (!Call->use_empty()) {
755 Call->replaceAllUsesWith(New);
761 Call->eraseFromParent();
773 I2 = NF->arg_begin();
I != E; ++
I) {
774 if (!ArgsToPromote.
count(
I) && !ByValArgsToTransform.
count(
I)) {
777 I->replaceAllUsesWith(I2);
784 if (ByValArgsToTransform.
count(
I)) {
790 Type *AgTy = cast<PointerType>(
I->getType())->getElementType();
807 I->replaceAllUsesWith(TheAlloca);
813 if (
I->use_empty()) {
821 ScalarizeTable &ArgIndices = ScalarizedElements[
I];
823 while (!
I->use_empty()) {
824 if (
LoadInst *
LI = dyn_cast<LoadInst>(
I->use_back())) {
825 assert(ArgIndices.begin()->empty() &&
826 "Load element should sort to front!");
827 I2->setName(
I->getName()+
".val");
828 LI->replaceAllUsesWith(I2);
830 LI->eraseFromParent();
831 DEBUG(
dbgs() <<
"*** Promoted load of argument '" <<
I->getName()
832 <<
"' in function '" << F->
getName() <<
"'\n");
835 IndicesVector Operands;
839 Operands.push_back(cast<ConstantInt>(*II)->getSExtValue());
842 if (Operands.size() == 1 && Operands.front() == 0)
846 for (ScalarizeTable::iterator It = ArgIndices.begin();
847 *It != Operands; ++It, ++TheArg) {
848 assert(It != ArgIndices.end() &&
"GEP not handled??");
851 std::string NewName =
I->getName();
852 for (
unsigned i = 0, e = Operands.size(); i != e; ++i) {
853 NewName +=
"." +
utostr(Operands[i]);
856 TheArg->setName(NewName);
858 DEBUG(
dbgs() <<
"*** Promoted agg argument '" << TheArg->getName()
859 <<
"' of function '" << NF->getName() <<
"'\n");
882 NF_CGN->stealCalledFunctionsFrom(CG[F]);
889 delete CG.removeFunctionFromModule(CGN);
void replaceWithNewValue(Value *Old, Value *New)
void push_back(const T &Elt)
LinkageTypes getLinkage() const
static PassRegistry * getPassRegistry()
LLVMContext & getContext() const
LLVM Argument representation.
AttributeSet getParamAttributes(unsigned Index) const
The attributes for the specified index are returned.
std::vector< CallGraphNode * >::const_iterator iterator
unsigned getNumOperands() const
Externally visible function.
bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc)
const Instruction & front() const
static IntegerType * getInt64Ty(LLVMContext &C)
unsigned getNumIndices() const
virtual void getAnalysisUsage(AnalysisUsage &Info) const
LoopInfoBase< BlockT, LoopT > * LI
ValTy * getArgument(unsigned ArgNo) const
AttributeSet getRetAttributes() const
The attributes for the ret value are returned.
StringRef getName() const
Function * getFunction() const
unsigned getNumReferences() const
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
static error_code advance(T &it, size_t Val)
void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode)
void initializeArgPromotionPass(PassRegistry &)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Pass * createArgumentPromotionPass(unsigned maxElements=3)
void setName(const Twine &Name)
void copyAttributesFrom(const GlobalValue *Src)
ID
LLVM Calling Convention Representation.
virtual void copyValue(Value *From, Value *To)
LLVMContext & getContext() const
getContext - Return the LLVMContext in which this type was uniqued.
bool count(PtrType Ptr) const
count - Return true if the specified pointer is in the set.
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
static std::string utostr(uint64_t X, bool isNeg=false)
void replaceAllUsesWith(Value *V)
User::op_iterator arg_iterator
LLVM Basic Block Representation.
const Function * getParent() const
Type * getElementType(unsigned N) const
idf_ext_iterator< T, SetTy > idf_ext_end(const T &G, SetTy &S)
static InvokeInst * Create(Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr="", Instruction *InsertBefore=0)
Interval::pred_iterator pred_begin(Interval *I)
iterator insert(iterator where, NodeTy *New)
Value * getOperand(unsigned i) const
Interval::pred_iterator pred_end(Interval *I)
Location - A description of a memory location.
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
void setAlignment(unsigned Align)
#define INITIALIZE_AG_DEPENDENCY(depName)
virtual void deleteValue(Value *V)
LLVMContext & getContext() const
All values hold a context through their type.
void setMetadata(unsigned KindID, MDNode *Node)
idf_ext_iterator< T, SetTy > idf_ext_begin(const T &G, SetTy &S)
static CallInst * Create(Value *Func, ArrayRef< Value * > Args, const Twine &NameStr="", Instruction *InsertBefore=0)
bool hasByValAttr() const
Return true if this argument has the byval attribute on it in its containing function.
const FunctionListType & getFunctionList() const
Get the Module's list of functions (constant).
const BasicBlockListType & getBasicBlockList() const
Class for constant integers.
MDNode * getMetadata(unsigned KindID) const
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
static GetElementPtrInst * Create(Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=0)
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
AttributeSet getAttributes() const
Return the attribute list for this Function.
Location getLocation(const LoadInst *LI)
bool isDereferenceablePointer() const
void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)
static IntegerType * getInt32Ty(LLVMContext &C)
bool hasAttributes(unsigned Index) const
Return true if attribute exists at the given index.
unsigned getAlignment() const
FunctionType * getFunctionType() const
bool hasLocalLinkage() const
Type * getReturnType() const
static Type * getIndexedType(Type *Ptr, ArrayRef< Value * > IdxList)
LLVM Value Representation.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, const Location &Loc)
unsigned getArgNo() const
Return the index of this formal argument in its containing function.
unsigned getNumElements() const
Random access to the elements.
const BasicBlock * getParent() const
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, const Twine &N="", Module *M=0)
AttributeSet getFnAttributes() const
The function attributes are returned.