1//===- ArgumentPromotion.cpp - Promote by-reference arguments -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass promotes "by reference" arguments to be "by value" arguments. In
10// practice, this means looking for internal functions that have pointer
11// arguments. If it can prove, through the use of alias analysis, that an
12// argument is *only* loaded, then it can pass the value into the function
13// instead of the address of the value. This can cause recursive simplification
14// of code and lead to the elimination of allocas (especially in C++ template
15// code like the STL).
16//
17// This pass also handles aggregate arguments that are passed into a function,
18// scalarizing them if the elements of the aggregate are only loaded. Note that
19// by default it refuses to scalarize aggregates which would require passing in
20// more than three operands to the function, because passing thousands of
21// operands for a large array or structure is unprofitable! This limit can be
22// configured or disabled, however.
23//
24// Note that this transformation could also be done for arguments that are only
25// stored to (returning the value instead), but does not currently. This case
26// would be best handled when and if LLVM begins supporting multiple return
27// values from functions.
28//
29//===----------------------------------------------------------------------===//
30
31#include "llvm/Transforms/IPO/ArgumentPromotion.h"
32
33#include "llvm/ADT/DepthFirstIterator.h"
34#include "llvm/ADT/STLExtras.h"
35#include "llvm/ADT/ScopeExit.h"
36#include "llvm/ADT/SmallPtrSet.h"
37#include "llvm/ADT/SmallVector.h"
38#include "llvm/ADT/Statistic.h"
39#include "llvm/ADT/Twine.h"
40#include "llvm/Analysis/AssumptionCache.h"
41#include "llvm/Analysis/BasicAliasAnalysis.h"
42#include "llvm/Analysis/CallGraph.h"
43#include "llvm/Analysis/Loads.h"
44#include "llvm/Analysis/MemoryLocation.h"
45#include "llvm/Analysis/OptimizationRemarkEmitter.h"
46#include "llvm/Analysis/TargetTransformInfo.h"
47#include "llvm/Analysis/ValueTracking.h"
48#include "llvm/IR/Argument.h"
49#include "llvm/IR/Attributes.h"
50#include "llvm/IR/BasicBlock.h"
51#include "llvm/IR/CFG.h"
52#include "llvm/IR/Constants.h"
53#include "llvm/IR/DIBuilder.h"
54#include "llvm/IR/DataLayout.h"
55#include "llvm/IR/DerivedTypes.h"
56#include "llvm/IR/Dominators.h"
57#include "llvm/IR/Function.h"
58#include "llvm/IR/IRBuilder.h"
59#include "llvm/IR/InstrTypes.h"
60#include "llvm/IR/Instruction.h"
61#include "llvm/IR/Instructions.h"
62#include "llvm/IR/Metadata.h"
63#include "llvm/IR/Module.h"
64#include "llvm/IR/NoFolder.h"
65#include "llvm/IR/PassManager.h"
66#include "llvm/IR/Type.h"
67#include "llvm/IR/Use.h"
68#include "llvm/IR/User.h"
69#include "llvm/IR/Value.h"
70#include "llvm/Support/Casting.h"
71#include "llvm/Support/Debug.h"
72#include "llvm/Support/raw_ostream.h"
73#include "llvm/Transforms/Utils/Local.h"
74#include "llvm/Transforms/Utils/PromoteMemToReg.h"
75#include <algorithm>
76#include <cassert>
77#include <cstdint>
78#include <utility>
79#include <vector>
80
81using namespace llvm;
82
83#define DEBUG_TYPE "argpromotion"
84
85STATISTIC(NumArgumentsPromoted, "Number of pointer arguments promoted");
86STATISTIC(NumArgumentsDead, "Number of dead pointer args eliminated");
87
88namespace {
89
90struct ArgPart {
91 Type *Ty;
92 Align Alignment;
93 /// A representative guaranteed-executed load or store instruction for use by
94 /// metadata transfer.
95 Instruction *MustExecInstr;
96};
97
98using OffsetAndArgPart = std::pair<int64_t, ArgPart>;
99
100} // end anonymous namespace
101
102static Value *createByteGEP(IRBuilderBase &IRB, const DataLayout &DL,
103 Value *Ptr, int64_t Offset) {
104 if (Offset != 0)
105 Ptr = IRB.CreatePtrAddWithSignedOffset(Ptr, Offset);
106 return Ptr;
107}
108
109/// DoPromotion - This method actually performs the promotion of the specified
110/// arguments, and returns the new function. At this point, we know that it's
111/// safe to do so.
112static Function *
113doPromotion(Function *F, FunctionAnalysisManager &FAM,
114 const DenseMap<Argument *, SmallVector<OffsetAndArgPart, 4>>
115 &ArgsToPromote) {
116 // Start by computing a new prototype for the function, which is the same as
117 // the old function, but has modified arguments.
118 FunctionType *FTy = F->getFunctionType();
119 std::vector<Type *> Params;
120
121 // Attribute - Keep track of the parameter attributes for the arguments
122 // that we are *not* promoting. For the ones that we do promote, the parameter
123 // attributes are lost
124 SmallVector<AttributeSet, 8> ArgAttrVec;
125 // Mapping from old to new argument indices. -1 for promoted or removed
126 // arguments.
127 SmallVector<unsigned> NewArgIndices;
128 AttributeList PAL = F->getAttributes();
129 OptimizationRemarkEmitter ORE(F);
130
131 // First, determine the new argument list
132 unsigned ArgNo = 0, NewArgNo = 0;
133 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
134 ++I, ++ArgNo) {
135 auto It = ArgsToPromote.find(Val: &*I);
136 if (It == ArgsToPromote.end()) {
137 // Unchanged argument
138 Params.push_back(x: I->getType());
139 ArgAttrVec.push_back(Elt: PAL.getParamAttrs(ArgNo));
140 NewArgIndices.push_back(Elt: NewArgNo++);
141 } else if (I->use_empty()) {
142 // Dead argument (which are always marked as promotable)
143 ++NumArgumentsDead;
144 ORE.emit(RemarkBuilder: [&]() {
145 return OptimizationRemark(DEBUG_TYPE, "ArgumentRemoved", F)
146 << "eliminating argument " << ore::NV("ArgName", I->getName())
147 << "(" << ore::NV("ArgIndex", ArgNo) << ")";
148 });
149
150 NewArgIndices.push_back(Elt: (unsigned)-1);
151 } else {
152 const auto &ArgParts = It->second;
153 for (const auto &Pair : ArgParts) {
154 Params.push_back(x: Pair.second.Ty);
155 ArgAttrVec.push_back(Elt: AttributeSet());
156 }
157 ++NumArgumentsPromoted;
158 ORE.emit(RemarkBuilder: [&]() {
159 return OptimizationRemark(DEBUG_TYPE, "ArgumentPromoted", F)
160 << "promoting argument " << ore::NV("ArgName", I->getName())
161 << "(" << ore::NV("ArgIndex", ArgNo) << ")"
162 << " to pass by value";
163 });
164
165 NewArgIndices.push_back(Elt: (unsigned)-1);
166 NewArgNo += ArgParts.size();
167 }
168 }
169
170 Type *RetTy = FTy->getReturnType();
171
172 // Construct the new function type using the new arguments.
173 FunctionType *NFTy = FunctionType::get(Result: RetTy, Params, isVarArg: FTy->isVarArg());
174
175 // Create the new function body and insert it into the module.
176 Function *NF = Function::Create(Ty: NFTy, Linkage: F->getLinkage(), AddrSpace: F->getAddressSpace(),
177 N: F->getName());
178 NF->copyAttributesFrom(Src: F);
179 NF->copyMetadata(Src: F, Offset: 0);
180
181 // The new function will have the !dbg metadata copied from the original
182 // function. The original function may not be deleted, and dbg metadata need
183 // to be unique, so we need to drop it.
184 F->setSubprogram(nullptr);
185
186 LLVM_DEBUG(dbgs() << "ARG PROMOTION: Promoting to:" << *NF << "\n"
187 << "From: " << *F);
188
189 uint64_t LargestVectorWidth = 0;
190 for (auto *I : Params)
191 if (auto *VT = dyn_cast<llvm::VectorType>(Val: I))
192 LargestVectorWidth = std::max(
193 a: LargestVectorWidth, b: VT->getPrimitiveSizeInBits().getKnownMinValue());
194
195 // Recompute the parameter attributes list based on the new arguments for
196 // the function.
197 NF->setAttributes(AttributeList::get(C&: F->getContext(), FnAttrs: PAL.getFnAttrs(),
198 RetAttrs: PAL.getRetAttrs(), ArgAttrs: ArgAttrVec));
199
200 // Remap argument indices in allocsize attribute.
201 if (auto AllocSize = NF->getAttributes().getFnAttrs().getAllocSizeArgs()) {
202 unsigned Arg1 = NewArgIndices[AllocSize->first];
203 assert(Arg1 != (unsigned)-1 && "allocsize cannot be promoted argument");
204 std::optional<unsigned> Arg2;
205 if (AllocSize->second) {
206 Arg2 = NewArgIndices[*AllocSize->second];
207 assert(Arg2 != (unsigned)-1 && "allocsize cannot be promoted argument");
208 }
209 NF->addFnAttr(Attr: Attribute::getWithAllocSizeArgs(Context&: F->getContext(), ElemSizeArg: Arg1, NumElemsArg: Arg2));
210 }
211
212 AttributeFuncs::updateMinLegalVectorWidthAttr(Fn&: *NF, Width: LargestVectorWidth);
213 ArgAttrVec.clear();
214
215 F->getParent()->getFunctionList().insert(where: F->getIterator(), New: NF);
216 NF->takeName(V: F);
217
218 // Loop over all the callers of the function, transforming the call sites to
219 // pass in the loaded pointers.
220 SmallVector<Value *, 16> Args;
221 const DataLayout &DL = F->getDataLayout();
222 SmallVector<WeakTrackingVH, 16> DeadArgs;
223
224 while (!F->use_empty()) {
225 CallBase &CB = cast<CallBase>(Val&: *F->user_back());
226 assert(CB.getCalledFunction() == F);
227 const AttributeList &CallPAL = CB.getAttributes();
228 IRBuilder<NoFolder> IRB(&CB);
229
230 // Loop over the operands, inserting GEP and loads in the caller as
231 // appropriate.
232 auto *AI = CB.arg_begin();
233 ArgNo = 0;
234 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
235 ++I, ++AI, ++ArgNo) {
236 auto ArgIt = ArgsToPromote.find(Val: &*I);
237 if (ArgIt == ArgsToPromote.end()) {
238 Args.push_back(Elt: *AI); // Unmodified argument
239 ArgAttrVec.push_back(Elt: CallPAL.getParamAttrs(ArgNo));
240 } else if (!I->use_empty()) {
241 Value *V = *AI;
242 for (const auto &Pair : ArgIt->second) {
243 LoadInst *LI = IRB.CreateAlignedLoad(
244 Ty: Pair.second.Ty, Ptr: createByteGEP(IRB, DL, Ptr: V, Offset: Pair.first),
245 Align: Pair.second.Alignment, Name: V->getName() + ".val");
246 if (Pair.second.MustExecInstr) {
247 LI->setAAMetadata(Pair.second.MustExecInstr->getAAMetadata());
248 LI->copyMetadata(SrcInst: *Pair.second.MustExecInstr,
249 WL: {LLVMContext::MD_dereferenceable,
250 LLVMContext::MD_dereferenceable_or_null,
251 LLVMContext::MD_noundef,
252 LLVMContext::MD_nontemporal});
253 // Only transfer poison-generating metadata if we also have
254 // !noundef.
255 // TODO: Without !noundef, we could merge this metadata across
256 // all promoted loads.
257 if (LI->hasMetadata(KindID: LLVMContext::MD_noundef))
258 LI->copyMetadata(SrcInst: *Pair.second.MustExecInstr,
259 WL: Metadata::PoisonGeneratingIDs);
260 }
261 Args.push_back(Elt: LI);
262 ArgAttrVec.push_back(Elt: AttributeSet());
263 }
264 } else {
265 assert(I->use_empty());
266 DeadArgs.emplace_back(Args: AI->get());
267 }
268 }
269
270 // Push any varargs arguments on the list.
271 for (; AI != CB.arg_end(); ++AI, ++ArgNo) {
272 Args.push_back(Elt: *AI);
273 ArgAttrVec.push_back(Elt: CallPAL.getParamAttrs(ArgNo));
274 }
275
276 SmallVector<OperandBundleDef, 1> OpBundles;
277 CB.getOperandBundlesAsDefs(Defs&: OpBundles);
278
279 CallBase *NewCS = nullptr;
280 if (InvokeInst *II = dyn_cast<InvokeInst>(Val: &CB)) {
281 NewCS = InvokeInst::Create(Func: NF, IfNormal: II->getNormalDest(), IfException: II->getUnwindDest(),
282 Args, Bundles: OpBundles, NameStr: "", InsertBefore: CB.getIterator());
283 } else {
284 auto *NewCall =
285 CallInst::Create(Func: NF, Args, Bundles: OpBundles, NameStr: "", InsertBefore: CB.getIterator());
286 NewCall->setTailCallKind(cast<CallInst>(Val: &CB)->getTailCallKind());
287 NewCS = NewCall;
288 }
289 NewCS->setCallingConv(CB.getCallingConv());
290 NewCS->setAttributes(AttributeList::get(C&: F->getContext(),
291 FnAttrs: CallPAL.getFnAttrs(),
292 RetAttrs: CallPAL.getRetAttrs(), ArgAttrs: ArgAttrVec));
293 NewCS->copyProfileAndDebugMetadata(SrcInst: CB);
294 Args.clear();
295 ArgAttrVec.clear();
296
297 AttributeFuncs::updateMinLegalVectorWidthAttr(Fn&: *CB.getCaller(),
298 Width: LargestVectorWidth);
299
300 if (!CB.use_empty()) {
301 CB.replaceAllUsesWith(V: NewCS);
302 NewCS->takeName(V: &CB);
303 }
304
305 // Finally, remove the old call from the program, reducing the use-count of
306 // F.
307 CB.eraseFromParent();
308 }
309
310 RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts&: DeadArgs);
311
312 // Since we have now created the new function, splice the body of the old
313 // function right into the new function, leaving the old rotting hulk of the
314 // function empty.
315 NF->splice(ToIt: NF->begin(), FromF: F);
316
317 // We will collect all the new created allocas to promote them into registers
318 // after the following loop
319 SmallVector<AllocaInst *, 4> Allocas;
320
321 // Loop over the argument list, transferring uses of the old arguments over to
322 // the new arguments, also transferring over the names as well.
323 Function::arg_iterator I2 = NF->arg_begin();
324 for (Argument &Arg : F->args()) {
325 if (!ArgsToPromote.count(Val: &Arg)) {
326 // If this is an unmodified argument, move the name and users over to the
327 // new version.
328 Arg.replaceAllUsesWith(V: &*I2);
329 I2->takeName(V: &Arg);
330 ++I2;
331 continue;
332 }
333
334 // There potentially are metadata uses for things like llvm.dbg.value.
335 // Replace them with poison, after handling the other regular uses.
336 llvm::scope_exit RauwPoisonMetadata(
337 [&]() { Arg.replaceAllUsesWith(V: PoisonValue::get(T: Arg.getType())); });
338
339 if (Arg.use_empty())
340 continue;
341
342 // Otherwise, if we promoted this argument, we have to create an alloca in
343 // the callee for every promotable part and store each of the new incoming
344 // arguments into the corresponding alloca, what lets the old code (the
345 // store instructions if they are allowed especially) a chance to work as
346 // before.
347 assert(Arg.getType()->isPointerTy() &&
348 "Only arguments with a pointer type are promotable");
349
350 IRBuilder<NoFolder> IRB(&NF->begin()->front());
351
352 // Add only the promoted elements, so parts from ArgsToPromote
353 SmallDenseMap<int64_t, AllocaInst *> OffsetToAlloca;
354 for (const auto &Pair : ArgsToPromote.find(Val: &Arg)->second) {
355 int64_t Offset = Pair.first;
356 const ArgPart &Part = Pair.second;
357
358 Argument *NewArg = I2++;
359 NewArg->setName(Arg.getName() + "." + Twine(Offset) + ".val");
360
361 AllocaInst *NewAlloca = IRB.CreateAlloca(
362 Ty: Part.Ty, ArraySize: nullptr, Name: Arg.getName() + "." + Twine(Offset) + ".allc");
363 NewAlloca->setAlignment(Pair.second.Alignment);
364 IRB.CreateAlignedStore(Val: NewArg, Ptr: NewAlloca, Align: Pair.second.Alignment);
365
366 // Collect the alloca to retarget the users to
367 OffsetToAlloca.insert(KV: {Offset, NewAlloca});
368 }
369
370 auto GetAlloca = [&](Value *Ptr) {
371 APInt Offset(DL.getIndexTypeSizeInBits(Ty: Ptr->getType()), 0);
372 Ptr = Ptr->stripAndAccumulateConstantOffsets(DL, Offset,
373 /* AllowNonInbounds */ true);
374 assert(Ptr == &Arg && "Not constant offset from arg?");
375 return OffsetToAlloca.lookup(Val: Offset.getSExtValue());
376 };
377
378 // Cleanup the code from the dead instructions: GEPs and BitCasts in between
379 // the original argument and its users: loads and stores. Retarget every
380 // user to the new created alloca.
381 SmallVector<Value *, 16> Worklist(Arg.users());
382 SmallVector<Instruction *, 16> DeadInsts;
383 while (!Worklist.empty()) {
384 Value *V = Worklist.pop_back_val();
385 if (isa<GetElementPtrInst>(Val: V)) {
386 DeadInsts.push_back(Elt: cast<Instruction>(Val: V));
387 append_range(C&: Worklist, R: V->users());
388 continue;
389 }
390
391 if (auto *LI = dyn_cast<LoadInst>(Val: V)) {
392 Value *Ptr = LI->getPointerOperand();
393 LI->setOperand(i_nocapture: LoadInst::getPointerOperandIndex(), Val_nocapture: GetAlloca(Ptr));
394 continue;
395 }
396
397 if (auto *SI = dyn_cast<StoreInst>(Val: V)) {
398 assert(!SI->isVolatile() && "Volatile operations can't be promoted.");
399 Value *Ptr = SI->getPointerOperand();
400 SI->setOperand(i_nocapture: StoreInst::getPointerOperandIndex(), Val_nocapture: GetAlloca(Ptr));
401 continue;
402 }
403
404 llvm_unreachable("Unexpected user");
405 }
406
407 for (Instruction *I : DeadInsts) {
408 I->replaceAllUsesWith(V: PoisonValue::get(T: I->getType()));
409 I->eraseFromParent();
410 }
411
412 // Collect the allocas for promotion
413 for (const auto &Pair : OffsetToAlloca) {
414 assert(isAllocaPromotable(Pair.second) &&
415 "By design, only promotable allocas should be produced.");
416 Allocas.push_back(Elt: Pair.second);
417 }
418 }
419
420 LLVM_DEBUG(dbgs() << "ARG PROMOTION: " << Allocas.size()
421 << " alloca(s) are promotable by Mem2Reg\n");
422
423 if (!Allocas.empty()) {
424 // And we are able to call the `promoteMemoryToRegister()` function.
425 // Our earlier checks have ensured that PromoteMemToReg() will
426 // succeed.
427 auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: *NF);
428 auto &AC = FAM.getResult<AssumptionAnalysis>(IR&: *NF);
429 PromoteMemToReg(Allocas, DT, AC: &AC);
430 }
431
432 // If argument(s) are dead (hence removed) or promoted, the function probably
433 // does not follow the standard calling convention anymore. Add DW_CC_nocall
434 // to DISubroutineType to inform debugger that it may not be safe to call this
435 // function.
436 DISubprogram *SP = NF->getSubprogram();
437 if (SP) {
438 auto Temp = SP->getType()->cloneWithCC(CC: llvm::dwarf::DW_CC_nocall);
439 SP->replaceType(Ty: MDNode::replaceWithPermanent(N: std::move(Temp)));
440 }
441
442 return NF;
443}
444
445/// Return true if we can prove that all callees pass in a valid pointer for the
446/// specified function argument.
447static bool allCallersPassValidPointerForArgument(
448 Argument *Arg, SmallPtrSetImpl<CallBase *> &RecursiveCalls,
449 Align NeededAlign, uint64_t NeededDerefBytes) {
450 Function *Callee = Arg->getParent();
451 const DataLayout &DL = Callee->getDataLayout();
452 APInt Bytes(64, NeededDerefBytes);
453
454 // Check if the argument itself is marked dereferenceable and aligned.
455 if (isDereferenceableAndAlignedPointer(
456 V: Arg, Alignment: NeededAlign, Size: Bytes,
457 Q: SimplifyQuery(DL, &Callee->getEntryBlock().front())))
458 return true;
459
460 // Look at all call sites of the function. At this point we know we only have
461 // direct callees.
462 return all_of(Range: Callee->users(), P: [&](User *U) {
463 CallBase &CB = cast<CallBase>(Val&: *U);
464 // In case of functions with recursive calls, this check
465 // (isDereferenceableAndAlignedPointer) will fail when it tries to look at
466 // the first caller of this function. The caller may or may not have a load,
467 // incase it doesn't load the pointer being passed, this check will fail.
468 // So, it's safe to skip the check incase we know that we are dealing with a
469 // recursive call. For example we have a IR given below.
470 //
471 // def fun(ptr %a) {
472 // ...
473 // %loadres = load i32, ptr %a, align 4
474 // %res = call i32 @fun(ptr %a)
475 // ...
476 // }
477 //
478 // def bar(ptr %x) {
479 // ...
480 // %resbar = call i32 @fun(ptr %x)
481 // ...
482 // }
483 //
484 // Since we record processed recursive calls, we check if the current
485 // CallBase has been processed before. If yes it means that it is a
486 // recursive call and we can skip the check just for this call. So, just
487 // return true.
488 if (RecursiveCalls.contains(Ptr: &CB))
489 return true;
490
491 return isDereferenceableAndAlignedPointer(V: CB.getArgOperand(i: Arg->getArgNo()),
492 Alignment: NeededAlign, Size: Bytes,
493 Q: SimplifyQuery(DL, &CB));
494 });
495}
496
497// Try to prove that all Calls to F do not modify the memory pointed to by Arg,
498// using alias analysis local to each caller of F.
499static bool isArgUnmodifiedByAllCalls(Argument *Arg,
500 FunctionAnalysisManager &FAM) {
501 for (User *U : Arg->getParent()->users()) {
502
503 auto *Call = cast<CallBase>(Val: U);
504
505 MemoryLocation Loc =
506 MemoryLocation::getForArgument(Call, ArgIdx: Arg->getArgNo(), TLI: nullptr);
507
508 AAResults &AAR = FAM.getResult<AAManager>(IR&: *Call->getFunction());
509 // Bail as soon as we find a Call where Arg may be modified.
510 if (isModSet(MRI: AAR.getModRefInfo(I: Call, OptLoc: Loc)))
511 return false;
512 }
513
514 // All Users are Calls which do not modify the Arg.
515 return true;
516}
517
518/// Determine that this argument is safe to promote, and find the argument
519/// parts it can be promoted into.
520static bool findArgParts(Argument *Arg, const DataLayout &DL, AAResults &AAR,
521 unsigned MaxElements, bool IsRecursive,
522 SmallVectorImpl<OffsetAndArgPart> &ArgPartsVec,
523 FunctionAnalysisManager &FAM) {
524 // Quick exit for unused arguments
525 if (Arg->use_empty())
526 return true;
527
528 // We can only promote this argument if all the uses are loads at known
529 // offsets.
530 //
531 // Promoting the argument causes it to be loaded in the caller
532 // unconditionally. This is only safe if we can prove that either the load
533 // would have happened in the callee anyway (ie, there is a load in the entry
534 // block) or the pointer passed in at every call site is guaranteed to be
535 // valid.
536 // In the former case, invalid loads can happen, but would have happened
537 // anyway, in the latter case, invalid loads won't happen. This prevents us
538 // from introducing an invalid load that wouldn't have happened in the
539 // original code.
540
541 SmallDenseMap<int64_t, ArgPart, 4> ArgParts;
542 Align NeededAlign(1);
543 uint64_t NeededDerefBytes = 0;
544
545 // And if this is a byval argument we also allow to have store instructions.
546 // Only handle in such way arguments with specified alignment;
547 // if it's unspecified, the actual alignment of the argument is
548 // target-specific.
549 bool AreStoresAllowed = Arg->getParamByValType() && Arg->getParamAlign();
550
551 // An end user of a pointer argument is a load or store instruction.
552 // Returns std::nullopt if this load or store is not based on the argument.
553 // Return true if we can promote the instruction, false otherwise.
554 auto HandleEndUser = [&](auto *I, Type *Ty,
555 bool GuaranteedToExecute) -> std::optional<bool> {
556 // Don't promote volatile or atomic instructions.
557 if (!I->isSimple())
558 return false;
559
560 Value *Ptr = I->getPointerOperand();
561 APInt Offset(DL.getIndexTypeSizeInBits(Ty: Ptr->getType()), 0);
562 Ptr = Ptr->stripAndAccumulateConstantOffsets(DL, Offset,
563 /* AllowNonInbounds */ true);
564 if (Ptr != Arg)
565 return std::nullopt;
566
567 if (Offset.getSignificantBits() >= 64)
568 return false;
569
570 TypeSize Size = DL.getTypeStoreSize(Ty);
571 // Don't try to promote scalable types.
572 if (Size.isScalable())
573 return false;
574
575 // If this is a recursive function and one of the types is a pointer,
576 // then promoting it might lead to recursive promotion.
577 if (IsRecursive && Ty->isPointerTy())
578 return false;
579
580 int64_t Off = Offset.getSExtValue();
581 auto Pair = ArgParts.try_emplace(
582 Key: Off, Args: ArgPart{Ty, I->getAlign(), GuaranteedToExecute ? I : nullptr});
583 ArgPart &Part = Pair.first->second;
584 bool OffsetNotSeenBefore = Pair.second;
585
586 // We limit promotion to only promoting up to a fixed number of elements of
587 // the aggregate.
588 if (MaxElements > 0 && ArgParts.size() > MaxElements) {
589 LLVM_DEBUG(dbgs() << "ArgPromotion of " << *Arg << " failed: "
590 << "more than " << MaxElements << " parts\n");
591 return false;
592 }
593
594 // For now, we only support loading/storing one specific type at a given
595 // offset.
596 if (Part.Ty != Ty) {
597 LLVM_DEBUG(dbgs() << "ArgPromotion of " << *Arg << " failed: "
598 << "accessed as both " << *Part.Ty << " and " << *Ty
599 << " at offset " << Off << "\n");
600 return false;
601 }
602
603 // If this instruction is not guaranteed to execute, and we haven't seen a
604 // load or store at this offset before (or it had lower alignment), then we
605 // need to remember that requirement.
606 // Note that skipping instructions of previously seen offsets is only
607 // correct because we only allow a single type for a given offset, which
608 // also means that the number of accessed bytes will be the same.
609 if (!GuaranteedToExecute &&
610 (OffsetNotSeenBefore || Part.Alignment < I->getAlign())) {
611 // We won't be able to prove dereferenceability for negative offsets.
612 if (Off < 0)
613 return false;
614
615 // If the offset is not aligned, an aligned base pointer won't help.
616 if (!isAligned(I->getAlign(), Off))
617 return false;
618
619 NeededDerefBytes = std::max(a: NeededDerefBytes, b: Off + Size.getFixedValue());
620 NeededAlign = std::max(NeededAlign, I->getAlign());
621 }
622
623 Part.Alignment = std::max(Part.Alignment, I->getAlign());
624 return true;
625 };
626
627 // Look for loads and stores that are guaranteed to execute on entry.
628 for (Instruction &I : Arg->getParent()->getEntryBlock()) {
629 std::optional<bool> Res{};
630 if (LoadInst *LI = dyn_cast<LoadInst>(Val: &I))
631 Res = HandleEndUser(LI, LI->getType(), /* GuaranteedToExecute */ true);
632 else if (StoreInst *SI = dyn_cast<StoreInst>(Val: &I))
633 Res = HandleEndUser(SI, SI->getValueOperand()->getType(),
634 /* GuaranteedToExecute */ true);
635 if (Res && !*Res)
636 return false;
637
638 if (!isGuaranteedToTransferExecutionToSuccessor(I: &I))
639 break;
640 }
641
642 // Now look at all loads of the argument. Remember the load instructions
643 // for the aliasing check below.
644 SmallVector<const Use *, 16> Worklist;
645 SmallPtrSet<const Use *, 16> Visited;
646 SmallVector<LoadInst *, 16> Loads;
647 SmallPtrSet<CallBase *, 4> RecursiveCalls;
648 auto AppendUses = [&](const Value *V) {
649 for (const Use &U : V->uses())
650 if (Visited.insert(Ptr: &U).second)
651 Worklist.push_back(Elt: &U);
652 };
653 AppendUses(Arg);
654 while (!Worklist.empty()) {
655 const Use *U = Worklist.pop_back_val();
656 Value *V = U->getUser();
657
658 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: V)) {
659 if (!GEP->hasAllConstantIndices())
660 return false;
661 AppendUses(V);
662 continue;
663 }
664
665 if (auto *LI = dyn_cast<LoadInst>(Val: V)) {
666 if (!*HandleEndUser(LI, LI->getType(), /* GuaranteedToExecute */ false))
667 return false;
668 Loads.push_back(Elt: LI);
669 continue;
670 }
671
672 // Stores are allowed for byval arguments
673 auto *SI = dyn_cast<StoreInst>(Val: V);
674 if (AreStoresAllowed && SI &&
675 U->getOperandNo() == StoreInst::getPointerOperandIndex()) {
676 if (!*HandleEndUser(SI, SI->getValueOperand()->getType(),
677 /* GuaranteedToExecute */ false))
678 return false;
679 continue;
680 // Only stores TO the argument is allowed, all the other stores are
681 // unknown users
682 }
683
684 auto *CB = dyn_cast<CallBase>(Val: V);
685 Value *PtrArg = U->get();
686 if (CB && CB->getCalledFunction() == CB->getFunction()) {
687 if (PtrArg != Arg) {
688 LLVM_DEBUG(dbgs() << "ArgPromotion of " << *Arg << " failed: "
689 << "pointer offset is not equal to zero\n");
690 return false;
691 }
692
693 unsigned int ArgNo = Arg->getArgNo();
694 if (U->getOperandNo() != ArgNo) {
695 LLVM_DEBUG(dbgs() << "ArgPromotion of " << *Arg << " failed: "
696 << "arg position is different in callee\n");
697 return false;
698 }
699
700 // We limit promotion to only promoting up to a fixed number of elements
701 // of the aggregate.
702 if (MaxElements > 0 && ArgParts.size() > MaxElements) {
703 LLVM_DEBUG(dbgs() << "ArgPromotion of " << *Arg << " failed: "
704 << "more than " << MaxElements << " parts\n");
705 return false;
706 }
707
708 RecursiveCalls.insert(Ptr: CB);
709 continue;
710 }
711 // Unknown user.
712 LLVM_DEBUG(dbgs() << "ArgPromotion of " << *Arg << " failed: "
713 << "unknown user " << *V << "\n");
714 return false;
715 }
716
717 if (NeededDerefBytes || NeededAlign > 1) {
718 // Try to prove a required deref / aligned requirement.
719 if (!allCallersPassValidPointerForArgument(Arg, RecursiveCalls, NeededAlign,
720 NeededDerefBytes)) {
721 LLVM_DEBUG(dbgs() << "ArgPromotion of " << *Arg << " failed: "
722 << "not dereferenceable or aligned\n");
723 return false;
724 }
725 }
726
727 if (ArgParts.empty())
728 return true; // No users, this is a dead argument.
729
730 // Sort parts by offset.
731 append_range(C&: ArgPartsVec, R&: ArgParts);
732 sort(C&: ArgPartsVec, Comp: llvm::less_first());
733
734 // Make sure the parts are non-overlapping.
735 int64_t Offset = ArgPartsVec[0].first;
736 for (const auto &Pair : ArgPartsVec) {
737 if (Pair.first < Offset)
738 return false; // Overlap with previous part.
739
740 Offset = Pair.first + DL.getTypeStoreSize(Ty: Pair.second.Ty);
741 }
742
743 // If store instructions are allowed, the path from the entry of the function
744 // to each load may be not free of instructions that potentially invalidate
745 // the load, and this is an admissible situation.
746 if (AreStoresAllowed)
747 return true;
748
749 // Okay, now we know that the argument is only used by load instructions, and
750 // it is safe to unconditionally perform all of them.
751
752 // If we can determine that no call to the Function modifies the memory region
753 // accessed through Arg, through alias analysis using actual arguments in the
754 // callers, we know that it is guaranteed to be safe to promote the argument.
755 if (isArgUnmodifiedByAllCalls(Arg, FAM))
756 return true;
757
758 // Otherwise, use alias analysis to check if the pointer is guaranteed to not
759 // be modified from entry of the function to each of the load instructions.
760 for (LoadInst *Load : Loads) {
761 // Check to see if the load is invalidated from the start of the block to
762 // the load itself.
763 BasicBlock *BB = Load->getParent();
764
765 MemoryLocation Loc = MemoryLocation::get(LI: Load);
766 if (AAR.canInstructionRangeModRef(I1: BB->front(), I2: *Load, Loc, Mode: ModRefInfo::Mod))
767 return false; // Pointer is invalidated!
768
769 // Now check every path from the entry block to the load for transparency.
770 // To do this, we perform a depth first search on the inverse CFG from the
771 // loading block.
772 for (BasicBlock *P : predecessors(BB)) {
773 for (BasicBlock *TranspBB : inverse_depth_first(G: P))
774 if (AAR.canBasicBlockModify(BB: *TranspBB, Loc))
775 return false;
776 }
777 }
778
779 // If the path from the entry of the function to each load is free of
780 // instructions that potentially invalidate the load, we can make the
781 // transformation!
782 return true;
783}
784
785/// Check if callers and callee agree on how promoted arguments would be
786/// passed.
787static bool areTypesABICompatible(ArrayRef<Type *> Types, const Function &F,
788 const TargetTransformInfo &TTI) {
789 return all_of(Range: F.uses(), P: [&](const Use &U) {
790 CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
791 if (!CB)
792 return false;
793
794 const Function *Caller = CB->getCaller();
795 const Function *Callee = CB->getCalledFunction();
796 return TTI.areTypesABICompatible(Caller, Callee, Types);
797 });
798}
799
800/// PromoteArguments - This method checks the specified function to see if there
801/// are any promotable arguments and if it is safe to promote the function (for
802/// example, all callers are direct). If safe to promote some arguments, it
803/// calls the DoPromotion method.
804static Function *promoteArguments(Function *F, FunctionAnalysisManager &FAM,
805 unsigned MaxElements, bool IsRecursive) {
806 // Don't rewrite the signature of functions whose ABI must be preserved. For
807 // naked functions we can end up removing parameters that are seemingly 'not
808 // used' as they are referred to in the assembly.
809 if (!F->canChangeSignature())
810 return nullptr;
811
812 // Make sure that it is local to this module.
813 if (!F->hasLocalLinkage())
814 return nullptr;
815
816 // Ensure function definition is available for interprocedural analysis.
817 if (!F->isDefinitionExact())
818 return nullptr;
819
820 // Don't promote arguments for variadic functions. Adding, removing, or
821 // changing non-pack parameters can change the classification of pack
822 // parameters. Frontends encode that classification at the call site in the
823 // IR, while in the callee the classification is determined dynamically based
824 // on the number of registers consumed so far.
825 if (F->isVarArg())
826 return nullptr;
827
828 // Don't transform functions that receive inallocas, as the transformation may
829 // not be safe depending on calling convention.
830 if (F->getAttributes().hasAttrSomewhere(Kind: Attribute::InAlloca))
831 return nullptr;
832
833 // First check: see if there are any pointer arguments! If not, quick exit.
834 SmallVector<Argument *, 16> PointerArgs;
835 for (Argument &I : F->args())
836 if (I.getType()->isPointerTy())
837 PointerArgs.push_back(Elt: &I);
838 if (PointerArgs.empty())
839 return nullptr;
840
841 // Second check: make sure that all callers are direct callers. We can't
842 // transform functions that have indirect callers. Also see if the function
843 // is self-recursive.
844 for (Use &U : F->uses()) {
845 CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
846 // Must be a direct call.
847 if (CB == nullptr || !CB->isCallee(U: &U) ||
848 CB->getFunctionType() != F->getFunctionType())
849 return nullptr;
850
851 // Can't change signature of musttail callee
852 if (CB->isMustTailCall())
853 return nullptr;
854
855 if (CB->getFunction() == F)
856 IsRecursive = true;
857 }
858
859 // Can't change signature of musttail caller
860 // FIXME: Support promoting whole chain of musttail functions
861 for (BasicBlock &BB : *F)
862 if (BB.getTerminatingMustTailCall())
863 return nullptr;
864
865 const DataLayout &DL = F->getDataLayout();
866 auto &AAR = FAM.getResult<AAManager>(IR&: *F);
867 const auto &TTI = FAM.getResult<TargetIRAnalysis>(IR&: *F);
868
869 // Check to see which arguments are promotable. If an argument is promotable,
870 // add it to ArgsToPromote.
871 DenseMap<Argument *, SmallVector<OffsetAndArgPart, 4>> ArgsToPromote;
872 unsigned NumArgsAfterPromote = F->getFunctionType()->getNumParams();
873 for (Argument *PtrArg : PointerArgs) {
874 // Replace sret attribute with noalias. This reduces register pressure by
875 // avoiding a register copy.
876 if (PtrArg->hasStructRetAttr()) {
877 unsigned ArgNo = PtrArg->getArgNo();
878 F->removeParamAttr(ArgNo, Kind: Attribute::StructRet);
879 F->addParamAttr(ArgNo, Kind: Attribute::NoAlias);
880 for (Use &U : F->uses()) {
881 CallBase &CB = cast<CallBase>(Val&: *U.getUser());
882 CB.removeParamAttr(ArgNo, Kind: Attribute::StructRet);
883 CB.addParamAttr(ArgNo, Kind: Attribute::NoAlias);
884 }
885 }
886
887 // If we can promote the pointer to its value.
888 SmallVector<OffsetAndArgPart, 4> ArgParts;
889
890 if (findArgParts(Arg: PtrArg, DL, AAR, MaxElements, IsRecursive, ArgPartsVec&: ArgParts,
891 FAM)) {
892 SmallVector<Type *, 4> Types;
893 for (const auto &Pair : ArgParts)
894 Types.push_back(Elt: Pair.second.Ty);
895
896 if (areTypesABICompatible(Types, F: *F, TTI)) {
897 NumArgsAfterPromote += ArgParts.size() - 1;
898 ArgsToPromote.insert(KV: {PtrArg, std::move(ArgParts)});
899 }
900 }
901 }
902
903 // No promotable pointer arguments.
904 if (ArgsToPromote.empty())
905 return nullptr;
906
907 if (NumArgsAfterPromote > TTI.getMaxNumArgs())
908 return nullptr;
909
910 return doPromotion(F, FAM, ArgsToPromote);
911}
912
913PreservedAnalyses ArgumentPromotionPass::run(LazyCallGraph::SCC &C,
914 CGSCCAnalysisManager &AM,
915 LazyCallGraph &CG,
916 CGSCCUpdateResult &UR) {
917 bool Changed = false, LocalChange;
918
919 // Iterate until we stop promoting from this SCC.
920 do {
921 LocalChange = false;
922
923 FunctionAnalysisManager &FAM =
924 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
925
926 bool IsRecursive = C.size() > 1;
927 for (LazyCallGraph::Node &N : C) {
928 Function &OldF = N.getFunction();
929 Function *NewF = promoteArguments(F: &OldF, FAM, MaxElements, IsRecursive);
930 if (!NewF)
931 continue;
932 LocalChange = true;
933
934 // Directly substitute the functions in the call graph. Note that this
935 // requires the old function to be completely dead and completely
936 // replaced by the new function. It does no call graph updates, it merely
937 // swaps out the particular function mapped to a particular node in the
938 // graph.
939 C.getOuterRefSCC().replaceNodeFunction(N, NewF&: *NewF);
940 FAM.clear(IR&: OldF, Name: OldF.getName());
941 OldF.eraseFromParent();
942
943 PreservedAnalyses FuncPA;
944 FuncPA.preserveSet<CFGAnalyses>();
945 for (auto *U : NewF->users()) {
946 auto *UserF = cast<CallBase>(Val: U)->getFunction();
947 FAM.invalidate(IR&: *UserF, PA: FuncPA);
948 }
949 }
950
951 Changed |= LocalChange;
952 } while (LocalChange);
953
954 if (!Changed)
955 return PreservedAnalyses::all();
956
957 PreservedAnalyses PA;
958 // We've cleared out analyses for deleted functions.
959 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
960 // We've manually invalidated analyses for functions we've modified.
961 PA.preserveSet<AllAnalysesOn<Function>>();
962 return PA;
963}
964