1//===- Attributor.cpp - Module-wide attribute deduction -------------------===//
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 file implements an interprocedural pass that deduces and/or propagates
10// attributes. This is done in an abstract interpretation style fixpoint
11// iteration. See the Attributor.h file comment and the class descriptions in
12// that file for more information.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Transforms/IPO/Attributor.h"
17#include "IPOOptions.h"
18
19#include "llvm/ADT/ArrayRef.h"
20#include "llvm/ADT/PointerIntPair.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/AliasAnalysis.h"
25#include "llvm/Analysis/CallGraph.h"
26#include "llvm/Analysis/InlineCost.h"
27#include "llvm/Analysis/MemoryBuiltins.h"
28#include "llvm/Analysis/MustExecute.h"
29#include "llvm/IR/AttributeMask.h"
30#include "llvm/IR/Attributes.h"
31#include "llvm/IR/Constant.h"
32#include "llvm/IR/ConstantFold.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DataLayout.h"
35#include "llvm/IR/GlobalValue.h"
36#include "llvm/IR/GlobalVariable.h"
37#include "llvm/IR/Instruction.h"
38#include "llvm/IR/Instructions.h"
39#include "llvm/IR/IntrinsicInst.h"
40#include "llvm/IR/LLVMContext.h"
41#include "llvm/IR/ValueHandle.h"
42#include "llvm/Support/Casting.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/DebugCounter.h"
45#include "llvm/Support/FileSystem.h"
46#include "llvm/Support/GraphWriter.h"
47#include "llvm/Support/ModRef.h"
48#include "llvm/Support/raw_ostream.h"
49#include "llvm/Transforms/Utils/BasicBlockUtils.h"
50#include "llvm/Transforms/Utils/Cloning.h"
51#include "llvm/Transforms/Utils/Local.h"
52#include <cstdint>
53#include <memory>
54
55#ifdef EXPENSIVE_CHECKS
56#include "llvm/IR/Verifier.h"
57#endif
58
59#include <cassert>
60#include <optional>
61#include <string>
62
63using namespace llvm;
64
65#define DEBUG_TYPE "attributor"
66#define VERBOSE_DEBUG_TYPE DEBUG_TYPE "-verbose"
67
68DEBUG_COUNTER(ManifestDBGCounter, "attributor-manifest",
69 "Determine what attributes are manifested in the IR");
70
71/// A debug counter to limit the number of AAs created.
72DEBUG_COUNTER(NumAbstractAttributes, "num-abstract-attributes",
73 "How many AAs should be initialized");
74
75bool llvm::shouldCreateAbstractAttribute() {
76 return DebugCounter::shouldExecute(Counter&: NumAbstractAttributes);
77}
78
79STATISTIC(NumFnDeleted, "Number of function deleted");
80STATISTIC(NumFnWithExactDefinition,
81 "Number of functions with exact definitions");
82STATISTIC(NumFnWithoutExactDefinition,
83 "Number of functions without exact definitions");
84STATISTIC(NumFnShallowWrappersCreated, "Number of shallow wrappers created");
85STATISTIC(NumAttributesTimedOut,
86 "Number of abstract attributes timed out before fixpoint");
87STATISTIC(NumAttributesValidFixpoint,
88 "Number of abstract attributes in a valid fixpoint state");
89STATISTIC(NumAttributesManifested,
90 "Number of abstract attributes manifested in IR");
91
92/// Logic operators for the change status enum class.
93///
94///{
95ChangeStatus llvm::operator|(ChangeStatus L, ChangeStatus R) {
96 return L == ChangeStatus::CHANGED ? L : R;
97}
98ChangeStatus &llvm::operator|=(ChangeStatus &L, ChangeStatus R) {
99 L = L | R;
100 return L;
101}
102ChangeStatus llvm::operator&(ChangeStatus L, ChangeStatus R) {
103 return L == ChangeStatus::UNCHANGED ? L : R;
104}
105ChangeStatus &llvm::operator&=(ChangeStatus &L, ChangeStatus R) {
106 L = L & R;
107 return L;
108}
109///}
110
111namespace {
112/// NVPTX/AMDGPU address space values (shared between both targets)
113enum class NVPTXAMDGPUAddressSpace : unsigned {
114 Generic = 0,
115 Global = 1,
116 Shared = 3,
117 Constant = 4,
118 Local = 5,
119};
120
121/// SPIRV address space values (StorageClass)
122enum class SPIRVAddressSpace : unsigned {
123 Local = 0, // Function (private/local)
124 Global = 1, // CrossWorkgroup (global)
125 Constant = 2, // UniformConstant (constant)
126 Shared = 3, // Workgroup (shared)
127 Generic = 4, // Generic
128};
129} // namespace
130
131bool AA::isGPU(const Module &M) { return M.getTargetTriple().isGPU(); }
132
133bool AA::isGPUSharedAddressSpace(const Module &M, unsigned AS) {
134 assert(AA::isGPU(M) && "Only callable on GPU targets");
135 const Triple &T = M.getTargetTriple();
136
137 if (T.isSPIRV())
138 return AS == static_cast<unsigned>(SPIRVAddressSpace::Shared);
139
140 return AS == static_cast<unsigned>(NVPTXAMDGPUAddressSpace::Shared);
141}
142
143bool AA::isGPUConstantAddressSpace(const Module &M, unsigned AS) {
144 assert(AA::isGPU(M) && "Only callable on GPU targets");
145 const Triple &T = M.getTargetTriple();
146
147 if (T.isSPIRV())
148 return AS == static_cast<unsigned>(SPIRVAddressSpace::Constant);
149
150 return AS == static_cast<unsigned>(NVPTXAMDGPUAddressSpace::Constant);
151}
152
153bool AA::isGPULocalAddressSpace(const Module &M, unsigned AS) {
154 assert(AA::isGPU(M) && "Only callable on GPU targets");
155 const Triple &T = M.getTargetTriple();
156
157 if (T.isSPIRV())
158 return AS == static_cast<unsigned>(SPIRVAddressSpace::Local);
159
160 return AS == static_cast<unsigned>(NVPTXAMDGPUAddressSpace::Local);
161}
162
163bool AA::isNoSyncInst(Attributor &A, const Instruction &I,
164 const AbstractAttribute &QueryingAA) {
165 // We are looking for volatile instructions or non-relaxed atomics.
166 if (const auto *CB = dyn_cast<CallBase>(Val: &I)) {
167 if (CB->hasFnAttr(Kind: Attribute::NoSync))
168 return true;
169
170 // Non-convergent and readnone imply nosync.
171 if (!CB->isConvergent() && !CB->mayReadOrWriteMemory())
172 return true;
173
174 bool IsKnownNoSync;
175 return AA::hasAssumedIRAttr<Attribute::NoSync>(
176 A, QueryingAA: &QueryingAA, IRP: IRPosition::callsite_function(CB: *CB),
177 DepClass: DepClassTy::OPTIONAL, IsKnown&: IsKnownNoSync);
178 }
179
180 if (!I.mayReadOrWriteMemory())
181 return true;
182
183 return !AANoSync::isNonRelaxedAtomic(I: &I);
184}
185
186bool AA::isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA,
187 const Value &V, bool ForAnalysisOnly) {
188 // TODO: See the AAInstanceInfo class comment.
189 if (!ForAnalysisOnly)
190 return false;
191 auto *InstanceInfoAA = A.getAAFor<AAInstanceInfo>(
192 QueryingAA, IRP: IRPosition::value(V), DepClass: DepClassTy::OPTIONAL);
193 return InstanceInfoAA && InstanceInfoAA->isAssumedUniqueForAnalysis();
194}
195
196Constant *
197AA::getInitialValueForObj(Attributor &A, const AbstractAttribute &QueryingAA,
198 Value &Obj, Type &Ty, const TargetLibraryInfo *TLI,
199 const DataLayout &DL, AA::RangeTy *RangePtr) {
200 if (Constant *Init = getInitialValueOfAllocation(V: &Obj, TLI, Ty: &Ty))
201 return Init;
202 auto *GV = dyn_cast<GlobalVariable>(Val: &Obj);
203 if (!GV)
204 return nullptr;
205
206 bool UsedAssumedInformation = false;
207 Constant *Initializer = nullptr;
208 if (A.hasGlobalVariableSimplificationCallback(GV: *GV)) {
209 auto AssumedGV = A.getAssumedInitializerFromCallBack(
210 GV: *GV, AA: &QueryingAA, UsedAssumedInformation);
211 Initializer = *AssumedGV;
212 if (!Initializer)
213 return nullptr;
214 } else {
215 if (!GV->hasLocalLinkage()) {
216 // Externally visible global that's either non-constant,
217 // or a constant with an uncertain initializer.
218 if (!GV->hasDefinitiveInitializer() || !GV->isConstant())
219 return nullptr;
220 }
221
222 // Globals with local linkage are always initialized.
223 assert(!GV->hasLocalLinkage() || GV->hasInitializer());
224
225 if (!Initializer)
226 Initializer = GV->getInitializer();
227 }
228
229 if (RangePtr && !RangePtr->offsetOrSizeAreUnknown()) {
230 int64_t StorageSize = DL.getTypeStoreSize(Ty: &Ty);
231 if (StorageSize != RangePtr->Size)
232 return nullptr;
233 APInt Offset = APInt(64, RangePtr->Offset);
234 return ConstantFoldLoadFromConst(C: Initializer, Ty: &Ty, Offset, DL);
235 }
236
237 return ConstantFoldLoadFromUniformValue(C: Initializer, Ty: &Ty, DL);
238}
239
240bool AA::isValidInScope(const Value &V, const Function *Scope) {
241 if (isa<Constant>(Val: V))
242 return true;
243 if (auto *I = dyn_cast<Instruction>(Val: &V))
244 return I->getFunction() == Scope;
245 if (auto *A = dyn_cast<Argument>(Val: &V))
246 return A->getParent() == Scope;
247 return false;
248}
249
250bool AA::isValidAtPosition(const AA::ValueAndContext &VAC,
251 InformationCache &InfoCache) {
252 if (isa<Constant>(Val: VAC.getValue()) || VAC.getValue() == VAC.getCtxI())
253 return true;
254 const Function *Scope = nullptr;
255 const Instruction *CtxI = VAC.getCtxI();
256 if (CtxI)
257 Scope = CtxI->getFunction();
258 if (auto *A = dyn_cast<Argument>(Val: VAC.getValue()))
259 return A->getParent() == Scope;
260 if (auto *I = dyn_cast<Instruction>(Val: VAC.getValue())) {
261 if (I->getFunction() == Scope) {
262 if (const DominatorTree *DT =
263 InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(
264 F: *Scope))
265 return DT->dominates(Def: I, User: CtxI);
266 // Local dominance check mostly for the old PM passes.
267 if (CtxI && I->getParent() == CtxI->getParent())
268 return llvm::any_of(
269 Range: make_range(x: I->getIterator(), y: I->getParent()->end()),
270 P: [&](const Instruction &AfterI) { return &AfterI == CtxI; });
271 }
272 }
273 return false;
274}
275
276Value *AA::getWithType(Value &V, Type &Ty) {
277 if (V.getType() == &Ty)
278 return &V;
279 if (isa<PoisonValue>(Val: V))
280 return PoisonValue::get(T: &Ty);
281 if (isa<UndefValue>(Val: V))
282 return UndefValue::get(T: &Ty);
283 if (auto *C = dyn_cast<Constant>(Val: &V)) {
284 if (C->isNullValue() && !Ty.isPtrOrPtrVectorTy())
285 return Constant::getNullValue(Ty: &Ty);
286 if (C->getType()->isPointerTy() && Ty.isPointerTy())
287 return ConstantExpr::getPointerCast(C, Ty: &Ty);
288 if (C->getType()->getPrimitiveSizeInBits() >= Ty.getPrimitiveSizeInBits()) {
289 if (C->getType()->isIntegerTy() && Ty.isIntegerTy())
290 return ConstantExpr::getTrunc(C, Ty: &Ty, /* OnlyIfReduced */ true);
291 if (C->getType()->isFloatingPointTy() && Ty.isFloatingPointTy())
292 return ConstantFoldCastInstruction(opcode: Instruction::FPTrunc, V: C, DestTy: &Ty);
293 }
294 }
295 return nullptr;
296}
297
298std::optional<Value *>
299AA::combineOptionalValuesInAAValueLatice(const std::optional<Value *> &A,
300 const std::optional<Value *> &B,
301 Type *Ty) {
302 if (A == B)
303 return A;
304 if (!B)
305 return A;
306 if (*B == nullptr)
307 return nullptr;
308 if (!A)
309 return Ty ? getWithType(V&: **B, Ty&: *Ty) : nullptr;
310 if (*A == nullptr)
311 return nullptr;
312 if (!Ty)
313 Ty = (*A)->getType();
314 if (isa_and_nonnull<UndefValue>(Val: *A))
315 return getWithType(V&: **B, Ty&: *Ty);
316 if (isa<UndefValue>(Val: *B))
317 return A;
318 if (*A && *B && *A == getWithType(V&: **B, Ty&: *Ty))
319 return A;
320 return nullptr;
321}
322
323template <bool IsLoad, typename Ty>
324static bool getPotentialCopiesOfMemoryValue(
325 Attributor &A, Ty &I, SmallSetVector<Value *, 4> &PotentialCopies,
326 SmallSetVector<Instruction *, 4> *PotentialValueOrigins,
327 const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
328 bool OnlyExact) {
329 LLVM_DEBUG(dbgs() << "Trying to determine the potential copies of " << I
330 << " (only exact: " << OnlyExact << ")\n";);
331
332 Value &Ptr = *I.getPointerOperand();
333 // Containers to remember the pointer infos and new copies while we are not
334 // sure that we can find all of them. If we abort we want to avoid spurious
335 // dependences and potential copies in the provided container.
336 SmallVector<const AAPointerInfo *> PIs;
337 SmallSetVector<Value *, 8> NewCopies;
338 SmallSetVector<Instruction *, 8> NewCopyOrigins;
339
340 const auto *TLI =
341 A.getInfoCache().getTargetLibraryInfoForFunction(F: *I.getFunction());
342
343 auto Pred = [&](Value &Obj) {
344 LLVM_DEBUG(dbgs() << "Visit underlying object " << Obj << "\n");
345 if (isa<UndefValue>(Val: &Obj))
346 return true;
347 if (isa<ConstantPointerNull>(Val: &Obj)) {
348 // A null pointer access can be undefined but any offset from null may
349 // be OK. We do not try to optimize the latter.
350 if (!NullPointerIsDefined(I.getFunction(),
351 Ptr.getType()->getPointerAddressSpace()) &&
352 A.getAssumedSimplified(V: Ptr, AA: QueryingAA, UsedAssumedInformation,
353 S: AA::Interprocedural) == &Obj)
354 return true;
355 LLVM_DEBUG(
356 dbgs() << "Underlying object is a valid nullptr, giving up.\n";);
357 return false;
358 }
359 // TODO: Use assumed noalias return.
360 if (!isa<AllocaInst>(Val: &Obj) && !isa<GlobalVariable>(Val: &Obj) &&
361 !(IsLoad ? isAllocationFn(&Obj, TLI) : isNoAliasCall(V: &Obj))) {
362 LLVM_DEBUG(dbgs() << "Underlying object is not supported yet: " << Obj
363 << "\n";);
364 return false;
365 }
366 if (auto *GV = dyn_cast<GlobalVariable>(Val: &Obj))
367 if (!GV->hasLocalLinkage() &&
368 !(GV->isConstant() && GV->hasInitializer())) {
369 LLVM_DEBUG(dbgs() << "Underlying object is global with external "
370 "linkage, not supported yet: "
371 << Obj << "\n";);
372 return false;
373 }
374
375 bool NullOnly = true;
376 bool NullRequired = false;
377 auto CheckForNullOnlyAndUndef = [&](std::optional<Value *> V,
378 bool IsExact) {
379 if (!V || *V == nullptr)
380 NullOnly = false;
381 else if (isa<UndefValue>(Val: *V))
382 /* No op */;
383 else if (isa<Constant>(Val: *V) && cast<Constant>(Val: *V)->isNullValue())
384 NullRequired = !IsExact;
385 else
386 NullOnly = false;
387 };
388
389 auto AdjustWrittenValueType = [&](const AAPointerInfo::Access &Acc,
390 Value &V) {
391 Value *AdjV = AA::getWithType(V, Ty&: *I.getType());
392 if (!AdjV) {
393 LLVM_DEBUG(dbgs() << "Underlying object written but stored value "
394 "cannot be converted to read type: "
395 << *Acc.getRemoteInst() << " : " << *I.getType()
396 << "\n";);
397 }
398 return AdjV;
399 };
400
401 auto SkipCB = [&](const AAPointerInfo::Access &Acc) {
402 if ((IsLoad && !Acc.isWriteOrAssumption()) || (!IsLoad && !Acc.isRead()))
403 return true;
404 if (IsLoad) {
405 if (Acc.isWrittenValueYetUndetermined())
406 return true;
407 if (PotentialValueOrigins && !isa<AssumeInst>(Val: Acc.getRemoteInst()))
408 return false;
409 if (!Acc.isWrittenValueUnknown())
410 if (Value *V = AdjustWrittenValueType(Acc, *Acc.getWrittenValue()))
411 if (NewCopies.count(key: V)) {
412 NewCopyOrigins.insert(X: Acc.getRemoteInst());
413 return true;
414 }
415 if (auto *SI = dyn_cast<StoreInst>(Val: Acc.getRemoteInst()))
416 if (Value *V = AdjustWrittenValueType(Acc, *SI->getValueOperand()))
417 if (NewCopies.count(key: V)) {
418 NewCopyOrigins.insert(X: Acc.getRemoteInst());
419 return true;
420 }
421 }
422 return false;
423 };
424
425 auto CheckAccess = [&](const AAPointerInfo::Access &Acc, bool IsExact) {
426 if ((IsLoad && !Acc.isWriteOrAssumption()) || (!IsLoad && !Acc.isRead()))
427 return true;
428 if (IsLoad && Acc.isWrittenValueYetUndetermined())
429 return true;
430 CheckForNullOnlyAndUndef(Acc.getContent(), IsExact);
431 if (OnlyExact && !IsExact && !NullOnly &&
432 !isa_and_nonnull<UndefValue>(Val: Acc.getWrittenValue())) {
433 LLVM_DEBUG(dbgs() << "Non exact access " << *Acc.getRemoteInst()
434 << ", abort!\n");
435 return false;
436 }
437 if (NullRequired && !NullOnly) {
438 LLVM_DEBUG(dbgs() << "Required all `null` accesses due to non exact "
439 "one, however found non-null one: "
440 << *Acc.getRemoteInst() << ", abort!\n");
441 return false;
442 }
443 if (IsLoad) {
444 assert(isa<LoadInst>(I) && "Expected load or store instruction only!");
445 if (!Acc.isWrittenValueUnknown()) {
446 Value *V = AdjustWrittenValueType(Acc, *Acc.getWrittenValue());
447 if (!V)
448 return false;
449 NewCopies.insert(X: V);
450 if (PotentialValueOrigins)
451 NewCopyOrigins.insert(X: Acc.getRemoteInst());
452 return true;
453 }
454 auto *SI = dyn_cast<StoreInst>(Val: Acc.getRemoteInst());
455 if (!SI) {
456 LLVM_DEBUG(dbgs() << "Underlying object written through a non-store "
457 "instruction not supported yet: "
458 << *Acc.getRemoteInst() << "\n";);
459 return false;
460 }
461 Value *V = AdjustWrittenValueType(Acc, *SI->getValueOperand());
462 if (!V)
463 return false;
464 NewCopies.insert(X: V);
465 if (PotentialValueOrigins)
466 NewCopyOrigins.insert(X: SI);
467 } else {
468 assert(isa<StoreInst>(I) && "Expected load or store instruction only!");
469 auto *LI = dyn_cast<LoadInst>(Val: Acc.getRemoteInst());
470 if (!LI && OnlyExact) {
471 LLVM_DEBUG(dbgs() << "Underlying object read through a non-load "
472 "instruction not supported yet: "
473 << *Acc.getRemoteInst() << "\n";);
474 return false;
475 }
476 NewCopies.insert(X: Acc.getRemoteInst());
477 }
478 return true;
479 };
480
481 // If the value has been written to we don't need the initial value of the
482 // object.
483 bool HasBeenWrittenTo = false;
484
485 AA::RangeTy Range;
486 auto *PI = A.getAAFor<AAPointerInfo>(QueryingAA, IRP: IRPosition::value(V: Obj),
487 DepClass: DepClassTy::NONE);
488 if (!PI || !PI->forallInterferingAccesses(
489 A, QueryingAA, I,
490 /* FindInterferingWrites */ IsLoad,
491 /* FindInterferingReads */ !IsLoad, CheckAccess,
492 HasBeenWrittenTo, Range, SkipCB)) {
493 LLVM_DEBUG(
494 dbgs()
495 << "Failed to verify all interfering accesses for underlying object: "
496 << Obj << "\n");
497 return false;
498 }
499
500 if (IsLoad && !HasBeenWrittenTo && !Range.isUnassigned()) {
501 const DataLayout &DL = A.getDataLayout();
502 Value *InitialValue = AA::getInitialValueForObj(
503 A, QueryingAA, Obj, Ty&: *I.getType(), TLI, DL, RangePtr: &Range);
504 if (!InitialValue) {
505 LLVM_DEBUG(dbgs() << "Could not determine required initial value of "
506 "underlying object, abort!\n");
507 return false;
508 }
509 CheckForNullOnlyAndUndef(InitialValue, /* IsExact */ true);
510 if (NullRequired && !NullOnly) {
511 LLVM_DEBUG(dbgs() << "Non exact access but initial value that is not "
512 "null or undef, abort!\n");
513 return false;
514 }
515
516 NewCopies.insert(X: InitialValue);
517 if (PotentialValueOrigins)
518 NewCopyOrigins.insert(X: nullptr);
519 }
520
521 PIs.push_back(Elt: PI);
522
523 return true;
524 };
525
526 const auto *AAUO = A.getAAFor<AAUnderlyingObjects>(
527 QueryingAA, IRP: IRPosition::value(V: Ptr), DepClass: DepClassTy::OPTIONAL);
528 if (!AAUO || !AAUO->forallUnderlyingObjects(Pred)) {
529 LLVM_DEBUG(
530 dbgs() << "Underlying objects stored into could not be determined\n";);
531 return false;
532 }
533
534 // Only if we were successful collection all potential copies we record
535 // dependences (on non-fix AAPointerInfo AAs). We also only then modify the
536 // given PotentialCopies container.
537 for (const auto *PI : PIs) {
538 if (!PI->getState().isAtFixpoint())
539 UsedAssumedInformation = true;
540 A.recordDependence(FromAA: *PI, ToAA: QueryingAA, DepClass: DepClassTy::OPTIONAL);
541 }
542 PotentialCopies.insert_range(R&: NewCopies);
543 if (PotentialValueOrigins)
544 PotentialValueOrigins->insert_range(R&: NewCopyOrigins);
545
546 return true;
547}
548
549bool AA::getPotentiallyLoadedValues(
550 Attributor &A, LoadInst &LI, SmallSetVector<Value *, 4> &PotentialValues,
551 SmallSetVector<Instruction *, 4> &PotentialValueOrigins,
552 const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
553 bool OnlyExact) {
554 return getPotentialCopiesOfMemoryValue</* IsLoad */ true>(
555 A, I&: LI, PotentialCopies&: PotentialValues, PotentialValueOrigins: &PotentialValueOrigins, QueryingAA,
556 UsedAssumedInformation, OnlyExact);
557}
558
559bool AA::getPotentialCopiesOfStoredValue(
560 Attributor &A, StoreInst &SI, SmallSetVector<Value *, 4> &PotentialCopies,
561 const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation,
562 bool OnlyExact) {
563 return getPotentialCopiesOfMemoryValue</* IsLoad */ false>(
564 A, I&: SI, PotentialCopies, PotentialValueOrigins: nullptr, QueryingAA, UsedAssumedInformation,
565 OnlyExact);
566}
567
568static bool isAssumedReadOnlyOrReadNone(Attributor &A, const IRPosition &IRP,
569 const AbstractAttribute &QueryingAA,
570 bool RequireReadNone, bool &IsKnown) {
571 if (RequireReadNone) {
572 if (AA::hasAssumedIRAttr<Attribute::ReadNone>(
573 A, QueryingAA: &QueryingAA, IRP, DepClass: DepClassTy::OPTIONAL, IsKnown,
574 /* IgnoreSubsumingPositions */ true))
575 return true;
576 } else if (AA::hasAssumedIRAttr<Attribute::ReadOnly>(
577 A, QueryingAA: &QueryingAA, IRP, DepClass: DepClassTy::OPTIONAL, IsKnown,
578 /* IgnoreSubsumingPositions */ true))
579 return true;
580
581 IRPosition::Kind Kind = IRP.getPositionKind();
582 if (Kind == IRPosition::IRP_FUNCTION || Kind == IRPosition::IRP_CALL_SITE) {
583 const auto *MemLocAA =
584 A.getAAFor<AAMemoryLocation>(QueryingAA, IRP, DepClass: DepClassTy::NONE);
585 if (MemLocAA && MemLocAA->isAssumedReadNone()) {
586 IsKnown = MemLocAA->isKnownReadNone();
587 if (!IsKnown)
588 A.recordDependence(FromAA: *MemLocAA, ToAA: QueryingAA, DepClass: DepClassTy::OPTIONAL);
589 return true;
590 }
591 }
592
593 const auto *MemBehaviorAA =
594 A.getAAFor<AAMemoryBehavior>(QueryingAA, IRP, DepClass: DepClassTy::NONE);
595 if (MemBehaviorAA &&
596 (MemBehaviorAA->isAssumedReadNone() ||
597 (!RequireReadNone && MemBehaviorAA->isAssumedReadOnly()))) {
598 IsKnown = RequireReadNone ? MemBehaviorAA->isKnownReadNone()
599 : MemBehaviorAA->isKnownReadOnly();
600 if (!IsKnown)
601 A.recordDependence(FromAA: *MemBehaviorAA, ToAA: QueryingAA, DepClass: DepClassTy::OPTIONAL);
602 return true;
603 }
604
605 return false;
606}
607
608bool AA::isAssumedReadOnly(Attributor &A, const IRPosition &IRP,
609 const AbstractAttribute &QueryingAA, bool &IsKnown) {
610 return isAssumedReadOnlyOrReadNone(A, IRP, QueryingAA,
611 /* RequireReadNone */ false, IsKnown);
612}
613bool AA::isAssumedReadNone(Attributor &A, const IRPosition &IRP,
614 const AbstractAttribute &QueryingAA, bool &IsKnown) {
615 return isAssumedReadOnlyOrReadNone(A, IRP, QueryingAA,
616 /* RequireReadNone */ true, IsKnown);
617}
618
619static bool
620isPotentiallyReachable(Attributor &A, const Instruction &FromI,
621 const Instruction *ToI, const Function &ToFn,
622 const AbstractAttribute &QueryingAA,
623 const AA::InstExclusionSetTy *ExclusionSet,
624 std::function<bool(const Function &F)> GoBackwardsCB) {
625 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE, {
626 dbgs() << "[AA] isPotentiallyReachable @" << ToFn.getName() << " from "
627 << FromI << " [GBCB: " << bool(GoBackwardsCB) << "][#ExS: "
628 << (ExclusionSet ? std::to_string(ExclusionSet->size()) : "none")
629 << "]\n";
630 if (ExclusionSet)
631 for (auto *ES : *ExclusionSet)
632 dbgs() << *ES << "\n";
633 });
634
635 // We know kernels (generally) cannot be called from within the module. Thus,
636 // for reachability we would need to step back from a kernel which would allow
637 // us to reach anything anyway. Even if a kernel is invoked from another
638 // kernel, values like allocas and shared memory are not accessible. We
639 // implicitly check for this situation to avoid costly lookups.
640 if (GoBackwardsCB && &ToFn != FromI.getFunction() &&
641 !GoBackwardsCB(*FromI.getFunction()) && A.getInfoCache().isKernel(F: ToFn) &&
642 A.getInfoCache().isKernel(F: *FromI.getFunction())) {
643 LLVM_DEBUG(dbgs() << "[AA] assume kernel cannot be reached from within the "
644 "module; success\n";);
645 return false;
646 }
647
648 // If we can go arbitrarily backwards we will eventually reach an entry point
649 // that can reach ToI. Only if a set of blocks through which we cannot go is
650 // provided, or once we track internal functions not accessible from the
651 // outside, it makes sense to perform backwards analysis in the absence of a
652 // GoBackwardsCB.
653 if (!GoBackwardsCB && !ExclusionSet) {
654 LLVM_DEBUG(dbgs() << "[AA] check @" << ToFn.getName() << " from " << FromI
655 << " is not checked backwards and does not have an "
656 "exclusion set, abort\n");
657 return true;
658 }
659
660 SmallPtrSet<const Instruction *, 8> Visited;
661 SmallVector<const Instruction *> Worklist;
662 Worklist.push_back(Elt: &FromI);
663
664 while (!Worklist.empty()) {
665 const Instruction *CurFromI = Worklist.pop_back_val();
666 if (!Visited.insert(Ptr: CurFromI).second)
667 continue;
668
669 const Function *FromFn = CurFromI->getFunction();
670 if (FromFn == &ToFn) {
671 if (!ToI)
672 return true;
673 LLVM_DEBUG(dbgs() << "[AA] check " << *ToI << " from " << *CurFromI
674 << " intraprocedurally\n");
675 const auto *ReachabilityAA = A.getAAFor<AAIntraFnReachability>(
676 QueryingAA, IRP: IRPosition::function(F: ToFn), DepClass: DepClassTy::OPTIONAL);
677 bool Result = !ReachabilityAA || ReachabilityAA->isAssumedReachable(
678 A, From: *CurFromI, To: *ToI, ExclusionSet);
679 LLVM_DEBUG(dbgs() << "[AA] " << *CurFromI << " "
680 << (Result ? "can potentially " : "cannot ") << "reach "
681 << *ToI << " [Intra]\n");
682 if (Result)
683 return true;
684 }
685
686 bool Result = true;
687 if (!ToFn.isDeclaration() && ToI) {
688 const auto *ToReachabilityAA = A.getAAFor<AAIntraFnReachability>(
689 QueryingAA, IRP: IRPosition::function(F: ToFn), DepClass: DepClassTy::OPTIONAL);
690 const Instruction &EntryI = ToFn.getEntryBlock().front();
691 Result = !ToReachabilityAA || ToReachabilityAA->isAssumedReachable(
692 A, From: EntryI, To: *ToI, ExclusionSet);
693 LLVM_DEBUG(dbgs() << "[AA] Entry " << EntryI << " of @" << ToFn.getName()
694 << " " << (Result ? "can potentially " : "cannot ")
695 << "reach @" << *ToI << " [ToFn]\n");
696 }
697
698 if (Result) {
699 // The entry of the ToFn can reach the instruction ToI. If the current
700 // instruction is already known to reach the ToFn.
701 const auto *FnReachabilityAA = A.getAAFor<AAInterFnReachability>(
702 QueryingAA, IRP: IRPosition::function(F: *FromFn), DepClass: DepClassTy::OPTIONAL);
703 Result = !FnReachabilityAA || FnReachabilityAA->instructionCanReach(
704 A, Inst: *CurFromI, Fn: ToFn, ExclusionSet);
705 LLVM_DEBUG(dbgs() << "[AA] " << *CurFromI << " in @" << FromFn->getName()
706 << " " << (Result ? "can potentially " : "cannot ")
707 << "reach @" << ToFn.getName() << " [FromFn]\n");
708 if (Result)
709 return true;
710 }
711
712 // TODO: Check assumed nounwind.
713 const auto *ReachabilityAA = A.getAAFor<AAIntraFnReachability>(
714 QueryingAA, IRP: IRPosition::function(F: *FromFn), DepClass: DepClassTy::OPTIONAL);
715 auto ReturnInstCB = [&](Instruction &Ret) {
716 bool Result = !ReachabilityAA || ReachabilityAA->isAssumedReachable(
717 A, From: *CurFromI, To: Ret, ExclusionSet);
718 LLVM_DEBUG(dbgs() << "[AA][Ret] " << *CurFromI << " "
719 << (Result ? "can potentially " : "cannot ") << "reach "
720 << Ret << " [Intra]\n");
721 return !Result;
722 };
723
724 // Check if we can reach returns.
725 bool UsedAssumedInformation = false;
726 if (A.checkForAllInstructions(Pred: ReturnInstCB, Fn: FromFn, QueryingAA: &QueryingAA,
727 Opcodes: {Instruction::Ret}, UsedAssumedInformation)) {
728 LLVM_DEBUG(dbgs() << "[AA] No return is reachable, done\n");
729 continue;
730 }
731
732 if (!GoBackwardsCB) {
733 LLVM_DEBUG(dbgs() << "[AA] check @" << ToFn.getName() << " from " << FromI
734 << " is not checked backwards, abort\n");
735 return true;
736 }
737
738 // If we do not go backwards from the FromFn we are done here and so far we
739 // could not find a way to reach ToFn/ToI.
740 if (!GoBackwardsCB(*FromFn))
741 continue;
742
743 LLVM_DEBUG(dbgs() << "Stepping backwards to the call sites of @"
744 << FromFn->getName() << "\n");
745
746 auto CheckCallSite = [&](AbstractCallSite ACS) {
747 CallBase *CB = ACS.getInstruction();
748 if (!CB)
749 return false;
750
751 if (isa<InvokeInst>(Val: CB))
752 return false;
753
754 Instruction *Inst = CB->getNextNode();
755 Worklist.push_back(Elt: Inst);
756 return true;
757 };
758
759 Result = !A.checkForAllCallSites(Pred: CheckCallSite, Fn: *FromFn,
760 /* RequireAllCallSites */ true,
761 QueryingAA: &QueryingAA, UsedAssumedInformation);
762 if (Result) {
763 LLVM_DEBUG(dbgs() << "[AA] stepping back to call sites from " << *CurFromI
764 << " in @" << FromFn->getName()
765 << " failed, give up\n");
766 return true;
767 }
768
769 LLVM_DEBUG(dbgs() << "[AA] stepped back to call sites from " << *CurFromI
770 << " in @" << FromFn->getName()
771 << " worklist size is: " << Worklist.size() << "\n");
772 }
773 return false;
774}
775
776bool AA::isPotentiallyReachable(
777 Attributor &A, const Instruction &FromI, const Instruction &ToI,
778 const AbstractAttribute &QueryingAA,
779 const AA::InstExclusionSetTy *ExclusionSet,
780 std::function<bool(const Function &F)> GoBackwardsCB) {
781 const Function *ToFn = ToI.getFunction();
782 return ::isPotentiallyReachable(A, FromI, ToI: &ToI, ToFn: *ToFn, QueryingAA,
783 ExclusionSet, GoBackwardsCB);
784}
785
786bool AA::isPotentiallyReachable(
787 Attributor &A, const Instruction &FromI, const Function &ToFn,
788 const AbstractAttribute &QueryingAA,
789 const AA::InstExclusionSetTy *ExclusionSet,
790 std::function<bool(const Function &F)> GoBackwardsCB) {
791 return ::isPotentiallyReachable(A, FromI, /* ToI */ nullptr, ToFn, QueryingAA,
792 ExclusionSet, GoBackwardsCB);
793}
794
795bool AA::isAssumedThreadLocalObject(Attributor &A, Value &Obj,
796 const AbstractAttribute &QueryingAA) {
797 if (isa<UndefValue>(Val: Obj))
798 return true;
799 if (isa<AllocaInst>(Val: Obj)) {
800 InformationCache &InfoCache = A.getInfoCache();
801 if (!InfoCache.stackIsAccessibleByOtherThreads()) {
802 LLVM_DEBUG(
803 dbgs() << "[AA] Object '" << Obj
804 << "' is thread local; stack objects are thread local.\n");
805 return true;
806 }
807 bool IsKnownNoCapture;
808 bool IsAssumedNoCapture = AA::hasAssumedIRAttr<Attribute::Captures>(
809 A, QueryingAA: &QueryingAA, IRP: IRPosition::value(V: Obj), DepClass: DepClassTy::OPTIONAL,
810 IsKnown&: IsKnownNoCapture);
811 LLVM_DEBUG(dbgs() << "[AA] Object '" << Obj << "' is "
812 << (IsAssumedNoCapture ? "" : "not") << " thread local; "
813 << (IsAssumedNoCapture ? "non-" : "")
814 << "captured stack object.\n");
815 return IsAssumedNoCapture;
816 }
817 if (auto *GV = dyn_cast<GlobalVariable>(Val: &Obj)) {
818 if (GV->isConstant()) {
819 LLVM_DEBUG(dbgs() << "[AA] Object '" << Obj
820 << "' is thread local; constant global\n");
821 return true;
822 }
823 if (GV->isThreadLocal()) {
824 LLVM_DEBUG(dbgs() << "[AA] Object '" << Obj
825 << "' is thread local; thread local global\n");
826 return true;
827 }
828 }
829
830 if (A.getInfoCache().IsTargetGPU()) {
831 if (AA::isGPULocalAddressSpace(M: A.getInfoCache().getModule(),
832 AS: Obj.getType()->getPointerAddressSpace())) {
833 LLVM_DEBUG(dbgs() << "[AA] Object '" << Obj
834 << "' is thread local; GPU local memory\n");
835 return true;
836 }
837 if (AA::isGPUConstantAddressSpace(
838 M: A.getInfoCache().getModule(),
839 AS: Obj.getType()->getPointerAddressSpace())) {
840 LLVM_DEBUG(dbgs() << "[AA] Object '" << Obj
841 << "' is thread local; GPU constant memory\n");
842 return true;
843 }
844 }
845
846 LLVM_DEBUG(dbgs() << "[AA] Object '" << Obj << "' is not thread local\n");
847 return false;
848}
849
850bool AA::isPotentiallyAffectedByBarrier(Attributor &A, const Instruction &I,
851 const AbstractAttribute &QueryingAA) {
852 if (!I.mayHaveSideEffects() && !I.mayReadFromMemory())
853 return false;
854
855 SmallSetVector<const Value *, 8> Ptrs;
856
857 auto AddLocationPtr = [&](std::optional<MemoryLocation> Loc) {
858 if (!Loc || !Loc->Ptr) {
859 LLVM_DEBUG(
860 dbgs() << "[AA] Access to unknown location; -> requires barriers\n");
861 return false;
862 }
863 Ptrs.insert(X: Loc->Ptr);
864 return true;
865 };
866
867 if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Val: &I)) {
868 if (!AddLocationPtr(MemoryLocation::getForDest(MI)))
869 return true;
870 if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(Val: &I))
871 if (!AddLocationPtr(MemoryLocation::getForSource(MTI)))
872 return true;
873 } else if (!AddLocationPtr(MemoryLocation::getOrNone(Inst: &I)))
874 return true;
875
876 return isPotentiallyAffectedByBarrier(A, Ptrs: Ptrs.getArrayRef(), QueryingAA, CtxI: &I);
877}
878
879bool AA::isPotentiallyAffectedByBarrier(Attributor &A,
880 ArrayRef<const Value *> Ptrs,
881 const AbstractAttribute &QueryingAA,
882 const Instruction *CtxI) {
883 for (const Value *Ptr : Ptrs) {
884 if (!Ptr) {
885 LLVM_DEBUG(dbgs() << "[AA] nullptr; -> requires barriers\n");
886 return true;
887 }
888
889 auto Pred = [&](Value &Obj) {
890 if (AA::isAssumedThreadLocalObject(A, Obj, QueryingAA))
891 return true;
892 LLVM_DEBUG(dbgs() << "[AA] Access to '" << Obj << "' via '" << *Ptr
893 << "'; -> requires barrier\n");
894 return false;
895 };
896
897 const auto *UnderlyingObjsAA = A.getAAFor<AAUnderlyingObjects>(
898 QueryingAA, IRP: IRPosition::value(V: *Ptr), DepClass: DepClassTy::OPTIONAL);
899 if (!UnderlyingObjsAA || !UnderlyingObjsAA->forallUnderlyingObjects(Pred))
900 return true;
901 }
902 return false;
903}
904
905/// Return true if \p New is equal or worse than \p Old.
906static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
907 if (!Old.isIntAttribute())
908 return true;
909
910 return Old.getValueAsInt() >= New.getValueAsInt();
911}
912
913/// Return the attribute to add to a position to provide the information of
914/// \p Attr, given the attribute \p Existing of the same kind at the position
915/// (or none), or an invalid attribute if \p Existing already provides it.
916static Attribute getAttrToAdd(LLVMContext &Ctx, Attribute Attr,
917 Attribute Existing, bool ForceReplace) {
918 if (Attr.isEnumAttribute())
919 return Existing.isValid() ? Attribute() : Attr;
920 if (Attr.isStringAttribute()) {
921 if (Existing.isValid() && (!ForceReplace || Existing == Attr))
922 return Attribute();
923 return Attr;
924 }
925
926 if (Attr.isIntAttribute()) {
927 if (!ForceReplace && Attr.getKindAsEnum() == Attribute::Memory) {
928 MemoryEffects OldME = Existing.isValid() ? Existing.getMemoryEffects()
929 : MemoryEffects::unknown();
930 MemoryEffects ME = Attr.getMemoryEffects() & OldME;
931 if (ME == OldME)
932 return Attribute();
933 return Attribute::getWithMemoryEffects(Context&: Ctx, ME);
934 }
935 if (Existing.isValid() && !ForceReplace && isEqualOrWorse(New: Attr, Old: Existing))
936 return Attribute();
937 return Attr;
938 }
939
940 if (Attr.isConstantRangeAttribute())
941 return !ForceReplace && Existing.isValid() ? Attribute() : Attr;
942
943 llvm_unreachable("Expected enum or string attribute!");
944}
945
946Argument *IRPosition::getAssociatedArgument() const {
947 if (getPositionKind() == IRP_ARGUMENT)
948 return cast<Argument>(Val: &getAnchorValue());
949
950 // Not an Argument and no argument number means this is not a call site
951 // argument, thus we cannot find a callback argument to return.
952 int ArgNo = getCallSiteArgNo();
953 if (ArgNo < 0)
954 return nullptr;
955
956 // Use abstract call sites to make the connection between the call site
957 // values and the ones in callbacks. If a callback was found that makes use
958 // of the underlying call site operand, we want the corresponding callback
959 // callee argument and not the direct callee argument.
960 std::optional<Argument *> CBCandidateArg;
961 SmallVector<const Use *, 4> CallbackUses;
962 const auto &CB = cast<CallBase>(Val&: getAnchorValue());
963 AbstractCallSite::getCallbackUses(CB, CallbackUses);
964 for (const Use *U : CallbackUses) {
965 AbstractCallSite ACS(U);
966 assert(ACS && ACS.isCallbackCall());
967 if (!ACS.getCalledFunction())
968 continue;
969
970 for (unsigned u = 0, e = ACS.getNumArgOperands(); u < e; u++) {
971
972 // Test if the underlying call site operand is argument number u of the
973 // callback callee.
974 if (ACS.getCallArgOperandNo(ArgNo: u) != ArgNo)
975 continue;
976
977 assert(ACS.getCalledFunction()->arg_size() > u &&
978 "ACS mapped into var-args arguments!");
979 if (CBCandidateArg) {
980 CBCandidateArg = nullptr;
981 break;
982 }
983 CBCandidateArg = ACS.getCalledFunction()->getArg(i: u);
984 }
985 }
986
987 // If we found a unique callback candidate argument, return it.
988 if (CBCandidateArg && *CBCandidateArg)
989 return *CBCandidateArg;
990
991 // If no callbacks were found, or none used the underlying call site operand
992 // exclusively, use the direct callee argument if available.
993 auto *Callee = dyn_cast_if_present<Function>(Val: CB.getCalledOperand());
994 if (Callee && Callee->arg_size() > unsigned(ArgNo))
995 return Callee->getArg(i: ArgNo);
996
997 return nullptr;
998}
999
1000ChangeStatus AbstractAttribute::update(Attributor &A) {
1001 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
1002 if (isStateAtFixpoint())
1003 return HasChanged;
1004
1005 LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
1006
1007 HasChanged = updateImpl(A);
1008
1009 LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
1010 << "\n");
1011
1012 return HasChanged;
1013}
1014
1015Attributor::Attributor(SetVector<Function *> &Functions,
1016 InformationCache &InfoCache,
1017 AttributorConfig Configuration)
1018 : Opts(getIPOOptions(M: InfoCache.getModule())),
1019 Allocator(InfoCache.Allocator), Functions(Functions),
1020 InfoCache(InfoCache),
1021 MaxInitializationChainLength(
1022 Opts.attributor_max_initialization_chain_length),
1023 Configuration(Configuration) {
1024 if (!isClosedWorldModule())
1025 return;
1026 for (Function *Fn : Functions)
1027 if (Fn->hasAddressTaken(/*PutOffender=*/nullptr,
1028 /*IgnoreCallbackUses=*/false,
1029 /*IgnoreAssumeLikeCalls=*/true,
1030 /*IgnoreLLVMUsed=*/IngoreLLVMUsed: true,
1031 /*IgnoreARCAttachedCall=*/false,
1032 /*IgnoreCastedDirectCall=*/true))
1033 InfoCache.IndirectlyCallableFunctions.push_back(Elt: Fn);
1034}
1035
1036bool Attributor::getAttrsFromAssumes(const IRPosition &IRP,
1037 Attribute::AttrKind AK,
1038 SmallVectorImpl<Attribute> &Attrs) {
1039 assert(IRP.getPositionKind() != IRPosition::IRP_INVALID &&
1040 "Did expect a valid position!");
1041 MustBeExecutedContextExplorer *Explorer =
1042 getInfoCache().getMustBeExecutedContextExplorer();
1043 if (!Explorer)
1044 return false;
1045
1046 Value &AssociatedValue = IRP.getAssociatedValue();
1047
1048 const Assume2KnowledgeMap &A2K =
1049 getInfoCache().getKnowledgeMap().lookup(Val: {&AssociatedValue, AK});
1050
1051 // Check if we found any potential assume use, if not we don't need to look
1052 // at the context.
1053 if (A2K.empty())
1054 return false;
1055
1056 LLVMContext &Ctx = AssociatedValue.getContext();
1057 unsigned AttrsSize = Attrs.size();
1058 const Instruction *CtxI = IRP.getCtxI();
1059 if (!CtxI)
1060 return false;
1061 for (const auto &It : A2K) {
1062 if (Explorer->isInContextOf(I: It.first, PP: CtxI))
1063 Attrs.push_back(Elt: Attribute::get(Context&: Ctx, Kind: AK, Val: It.second.Max));
1064 }
1065 return AttrsSize != Attrs.size();
1066}
1067
1068template <typename DescTy>
1069ChangeStatus
1070Attributor::updateAttrMap(const IRPosition &IRP, ArrayRef<DescTy> AttrDescs,
1071 function_ref<bool(const DescTy &, AttributeSet,
1072 AttributeMask &, AttrBuilder &)>
1073 CB) {
1074 if (AttrDescs.empty())
1075 return ChangeStatus::UNCHANGED;
1076 switch (IRP.getPositionKind()) {
1077 case IRPosition::IRP_FLOAT:
1078 case IRPosition::IRP_INVALID:
1079 return ChangeStatus::UNCHANGED;
1080 default:
1081 break;
1082 };
1083
1084 AttributeList AL = IRP.getAttrList();
1085 Value *AttrListAnchor = IRP.getAttrListAnchor();
1086 auto [Iter, Inserted] = AttrsMap.insert(KV: {AttrListAnchor, AL});
1087 if (!Inserted)
1088 AL = Iter->second;
1089
1090 LLVMContext &Ctx = IRP.getAnchorValue().getContext();
1091 auto AttrIdx = IRP.getAttrIdx();
1092 AttributeSet AS = AL.getAttributes(Index: AttrIdx);
1093 AttributeMask AM;
1094 AttrBuilder AB(Ctx);
1095
1096 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
1097 for (const DescTy &AttrDesc : AttrDescs)
1098 if (CB(AttrDesc, AS, AM, AB))
1099 HasChanged = ChangeStatus::CHANGED;
1100
1101 if (HasChanged == ChangeStatus::UNCHANGED)
1102 return ChangeStatus::UNCHANGED;
1103
1104 if (!AM.empty())
1105 AL = AL.removeAttributesAtIndex(C&: Ctx, Index: AttrIdx, AttrsToRemove: AM);
1106 AL = AL.addAttributesAtIndex(C&: Ctx, Index: AttrIdx, B: AB);
1107
1108 Iter->second = AL;
1109 return HasChanged;
1110}
1111
1112bool Attributor::hasAttr(const IRPosition &IRP,
1113 ArrayRef<Attribute::AttrKind> AttrKinds,
1114 bool IgnoreSubsumingPositions,
1115 Attribute::AttrKind ImpliedAttributeKind) {
1116 bool Implied = false;
1117 bool HasAttr = false;
1118 auto HasAttrCB = [&](const Attribute::AttrKind &Kind, AttributeSet AttrSet,
1119 AttributeMask &, AttrBuilder &) {
1120 if (AttrSet.hasAttribute(Kind)) {
1121 Implied |= Kind != ImpliedAttributeKind;
1122 HasAttr = true;
1123 }
1124 return false;
1125 };
1126 for (const IRPosition &EquivIRP : SubsumingPositionIterator(IRP)) {
1127 updateAttrMap<Attribute::AttrKind>(IRP: EquivIRP, AttrDescs: AttrKinds, CB: HasAttrCB);
1128 if (HasAttr)
1129 break;
1130 // The first position returned by the SubsumingPositionIterator is
1131 // always the position itself. If we ignore subsuming positions we
1132 // are done after the first iteration.
1133 if (IgnoreSubsumingPositions)
1134 break;
1135 Implied = true;
1136 }
1137 if (!HasAttr) {
1138 Implied = true;
1139 // Most modules have no assume knowledge.
1140 if (!InfoCache.getKnowledgeMap().empty()) {
1141 SmallVector<Attribute> Attrs;
1142 for (Attribute::AttrKind AK : AttrKinds)
1143 if (getAttrsFromAssumes(IRP, AK, Attrs)) {
1144 HasAttr = true;
1145 break;
1146 }
1147 }
1148 }
1149
1150 // Check if we should manifest the implied attribute kind at the IRP.
1151 if (ImpliedAttributeKind != Attribute::None && HasAttr && Implied)
1152 manifestAttrs(IRP, DeducedAttrs: {Attribute::get(Context&: IRP.getAnchorValue().getContext(),
1153 Kind: ImpliedAttributeKind)});
1154 return HasAttr;
1155}
1156
1157void Attributor::getAttrs(const IRPosition &IRP,
1158 ArrayRef<Attribute::AttrKind> AttrKinds,
1159 SmallVectorImpl<Attribute> &Attrs,
1160 bool IgnoreSubsumingPositions) {
1161 auto CollectAttrCB = [&](const Attribute::AttrKind &Kind,
1162 AttributeSet AttrSet, AttributeMask &,
1163 AttrBuilder &) {
1164 if (AttrSet.hasAttribute(Kind))
1165 Attrs.push_back(Elt: AttrSet.getAttribute(Kind));
1166 return false;
1167 };
1168 for (const IRPosition &EquivIRP : SubsumingPositionIterator(IRP)) {
1169 updateAttrMap<Attribute::AttrKind>(IRP: EquivIRP, AttrDescs: AttrKinds, CB: CollectAttrCB);
1170 // The first position returned by the SubsumingPositionIterator is
1171 // always the position itself. If we ignore subsuming positions we
1172 // are done after the first iteration.
1173 if (IgnoreSubsumingPositions)
1174 break;
1175 }
1176 if (!InfoCache.getKnowledgeMap().empty()) {
1177 for (Attribute::AttrKind AK : AttrKinds)
1178 getAttrsFromAssumes(IRP, AK, Attrs);
1179 }
1180}
1181
1182ChangeStatus Attributor::removeAttrs(const IRPosition &IRP,
1183 ArrayRef<Attribute::AttrKind> AttrKinds) {
1184 auto RemoveAttrCB = [&](const Attribute::AttrKind &Kind, AttributeSet AttrSet,
1185 AttributeMask &AM, AttrBuilder &) {
1186 if (!AttrSet.hasAttribute(Kind))
1187 return false;
1188 AM.addAttribute(Val: Kind);
1189 return true;
1190 };
1191 return updateAttrMap<Attribute::AttrKind>(IRP, AttrDescs: AttrKinds, CB: RemoveAttrCB);
1192}
1193
1194ChangeStatus Attributor::removeAttrs(const IRPosition &IRP,
1195 ArrayRef<StringRef> Attrs) {
1196 auto RemoveAttrCB = [&](StringRef Attr, AttributeSet AttrSet,
1197 AttributeMask &AM, AttrBuilder &) -> bool {
1198 if (!AttrSet.hasAttribute(Kind: Attr))
1199 return false;
1200 AM.addAttribute(A: Attr);
1201 return true;
1202 };
1203
1204 return updateAttrMap<StringRef>(IRP, AttrDescs: Attrs, CB: RemoveAttrCB);
1205}
1206
1207ChangeStatus Attributor::manifestAttrs(const IRPosition &IRP,
1208 ArrayRef<Attribute> Attrs,
1209 bool ForceReplace) {
1210 if (Attrs.empty())
1211 return ChangeStatus::UNCHANGED;
1212
1213 switch (IRP.getPositionKind()) {
1214 case IRPosition::IRP_FLOAT:
1215 case IRPosition::IRP_INVALID:
1216 return ChangeStatus::UNCHANGED;
1217 default:
1218 break;
1219 }
1220
1221 AttributeList AL = IRP.getAttrList();
1222 auto [Iter, Inserted] = AttrsMap.insert(KV: {IRP.getAttrListAnchor(), AL});
1223 if (!Inserted)
1224 AL = Iter->second;
1225
1226 LLVMContext &Ctx = IRP.getAnchorValue().getContext();
1227 auto AttrIdx = IRP.getAttrIdx();
1228 AttributeSet AS = AL.getAttributes(Index: AttrIdx);
1229 SmallVector<Attribute, 8> Added;
1230 for (Attribute Attr : Attrs) {
1231 Attribute Existing = Attr.isStringAttribute()
1232 ? AS.getAttribute(Kind: Attr.getKindAsString())
1233 : AS.getAttribute(Kind: Attr.getKindAsEnum());
1234 if (Attribute New = getAttrToAdd(Ctx, Attr, Existing, ForceReplace);
1235 New.isValid())
1236 Added.push_back(Elt: New);
1237 }
1238
1239 if (Added.empty())
1240 return ChangeStatus::UNCHANGED;
1241
1242 // Added keeps the order of Attrs, so it is sorted with distinct kinds too.
1243 AL = AL.addSortedAttributesAtIndex(C&: Ctx, Index: AttrIdx, Attrs: Added);
1244 Iter->second = AL;
1245 return ChangeStatus::CHANGED;
1246}
1247
1248SubsumingPositionIterator::SubsumingPositionIterator(const IRPosition &IRP) {
1249 IRPositions.emplace_back(Args: IRP);
1250
1251 // Helper to determine if operand bundles on a call site are benign or
1252 // potentially problematic. We handle only llvm.assume for now.
1253 auto CanIgnoreOperandBundles = [](const CallBase &CB) {
1254 return (isa<IntrinsicInst>(Val: CB) &&
1255 cast<IntrinsicInst>(Val: CB).getIntrinsicID() == Intrinsic ::assume);
1256 };
1257
1258 const auto *CB = dyn_cast<CallBase>(Val: &IRP.getAnchorValue());
1259 switch (IRP.getPositionKind()) {
1260 case IRPosition::IRP_INVALID:
1261 case IRPosition::IRP_FLOAT:
1262 case IRPosition::IRP_FUNCTION:
1263 return;
1264 case IRPosition::IRP_ARGUMENT:
1265 case IRPosition::IRP_RETURNED:
1266 IRPositions.emplace_back(Args: IRPosition::function(F: *IRP.getAnchorScope()));
1267 return;
1268 case IRPosition::IRP_CALL_SITE:
1269 assert(CB && "Expected call site!");
1270 // TODO: We need to look at the operand bundles similar to the redirection
1271 // in CallBase.
1272 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB))
1273 if (auto *Callee = dyn_cast_if_present<Function>(Val: CB->getCalledOperand()))
1274 IRPositions.emplace_back(Args: IRPosition::function(F: *Callee));
1275 return;
1276 case IRPosition::IRP_CALL_SITE_RETURNED:
1277 assert(CB && "Expected call site!");
1278 // TODO: We need to look at the operand bundles similar to the redirection
1279 // in CallBase.
1280 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
1281 if (auto *Callee =
1282 dyn_cast_if_present<Function>(Val: CB->getCalledOperand())) {
1283 // The returned position of the callee does not describe the call if
1284 // the call uses a different return type.
1285 bool SameType = Callee->getReturnType() == CB->getType();
1286 if (SameType)
1287 IRPositions.emplace_back(Args: IRPosition::returned(F: *Callee));
1288 IRPositions.emplace_back(Args: IRPosition::function(F: *Callee));
1289 for (const Argument &Arg : Callee->args())
1290 if (SameType && Arg.hasReturnedAttr()) {
1291 IRPositions.emplace_back(
1292 Args: IRPosition::callsite_argument(CB: *CB, ArgNo: Arg.getArgNo()));
1293 IRPositions.emplace_back(
1294 Args: IRPosition::value(V: *CB->getArgOperand(i: Arg.getArgNo())));
1295 IRPositions.emplace_back(Args: IRPosition::argument(Arg));
1296 }
1297 }
1298 }
1299 IRPositions.emplace_back(Args: IRPosition::callsite_function(CB: *CB));
1300 return;
1301 case IRPosition::IRP_CALL_SITE_ARGUMENT: {
1302 assert(CB && "Expected call site!");
1303 // TODO: We need to look at the operand bundles similar to the redirection
1304 // in CallBase.
1305 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
1306 auto *Callee = dyn_cast_if_present<Function>(Val: CB->getCalledOperand());
1307 if (Callee) {
1308 if (Argument *Arg = IRP.getAssociatedArgument())
1309 IRPositions.emplace_back(Args: IRPosition::argument(Arg: *Arg));
1310 IRPositions.emplace_back(Args: IRPosition::function(F: *Callee));
1311 }
1312 }
1313 IRPositions.emplace_back(Args: IRPosition::value(V: IRP.getAssociatedValue()));
1314 return;
1315 }
1316 }
1317}
1318
1319#ifdef EXPENSIVE_CHECKS
1320void IRPosition::verify() {
1321 switch (getPositionKind()) {
1322 case IRP_INVALID:
1323 assert((CBContext == nullptr) &&
1324 "Invalid position must not have CallBaseContext!");
1325 assert(!Enc.getOpaqueValue() &&
1326 "Expected a nullptr for an invalid position!");
1327 return;
1328 case IRP_FLOAT:
1329 assert((!isa<Argument>(&getAssociatedValue())) &&
1330 "Expected specialized kind for argument values!");
1331 return;
1332 case IRP_RETURNED:
1333 assert(isa<Function>(getAsValuePtr()) &&
1334 "Expected function for a 'returned' position!");
1335 assert(getAsValuePtr() == &getAssociatedValue() &&
1336 "Associated value mismatch!");
1337 return;
1338 case IRP_CALL_SITE_RETURNED:
1339 assert((CBContext == nullptr) &&
1340 "'call site returned' position must not have CallBaseContext!");
1341 assert((isa<CallBase>(getAsValuePtr())) &&
1342 "Expected call base for 'call site returned' position!");
1343 assert(getAsValuePtr() == &getAssociatedValue() &&
1344 "Associated value mismatch!");
1345 return;
1346 case IRP_CALL_SITE:
1347 assert((CBContext == nullptr) &&
1348 "'call site function' position must not have CallBaseContext!");
1349 assert((isa<CallBase>(getAsValuePtr())) &&
1350 "Expected call base for 'call site function' position!");
1351 assert(getAsValuePtr() == &getAssociatedValue() &&
1352 "Associated value mismatch!");
1353 return;
1354 case IRP_FUNCTION:
1355 assert(isa<Function>(getAsValuePtr()) &&
1356 "Expected function for a 'function' position!");
1357 assert(getAsValuePtr() == &getAssociatedValue() &&
1358 "Associated value mismatch!");
1359 return;
1360 case IRP_ARGUMENT:
1361 assert(isa<Argument>(getAsValuePtr()) &&
1362 "Expected argument for a 'argument' position!");
1363 assert(getAsValuePtr() == &getAssociatedValue() &&
1364 "Associated value mismatch!");
1365 return;
1366 case IRP_CALL_SITE_ARGUMENT: {
1367 assert((CBContext == nullptr) &&
1368 "'call site argument' position must not have CallBaseContext!");
1369 Use *U = getAsUsePtr();
1370 (void)U; // Silence unused variable warning.
1371 assert(U && "Expected use for a 'call site argument' position!");
1372 assert(isa<CallBase>(U->getUser()) &&
1373 "Expected call base user for a 'call site argument' position!");
1374 assert(cast<CallBase>(U->getUser())->isArgOperand(U) &&
1375 "Expected call base argument operand for a 'call site argument' "
1376 "position");
1377 assert(cast<CallBase>(U->getUser())->getArgOperandNo(U) ==
1378 unsigned(getCallSiteArgNo()) &&
1379 "Argument number mismatch!");
1380 assert(U->get() == &getAssociatedValue() && "Associated value mismatch!");
1381 return;
1382 }
1383 }
1384}
1385#endif
1386
1387std::optional<Constant *>
1388Attributor::getAssumedConstant(const IRPosition &IRP,
1389 const AbstractAttribute &AA,
1390 bool &UsedAssumedInformation) {
1391 // First check all callbacks provided by outside AAs. If any of them returns
1392 // a non-null value that is different from the associated value, or
1393 // std::nullopt, we assume it's simplified.
1394 for (auto &CB : SimplificationCallbacks.lookup(Val: IRP)) {
1395 std::optional<Value *> SimplifiedV = CB(IRP, &AA, UsedAssumedInformation);
1396 if (!SimplifiedV)
1397 return std::nullopt;
1398 if (isa_and_nonnull<Constant>(Val: *SimplifiedV))
1399 return cast<Constant>(Val: *SimplifiedV);
1400 return nullptr;
1401 }
1402 if (auto *C = dyn_cast<Constant>(Val: &IRP.getAssociatedValue()))
1403 return C;
1404 SmallVector<AA::ValueAndContext> Values;
1405 if (getAssumedSimplifiedValues(IRP, AA: &AA, Values,
1406 S: AA::ValueScope::Interprocedural,
1407 UsedAssumedInformation)) {
1408 if (Values.empty())
1409 return std::nullopt;
1410 if (auto *C = dyn_cast_or_null<Constant>(
1411 Val: AAPotentialValues::getSingleValue(A&: *this, AA, IRP, Values)))
1412 return C;
1413 }
1414 return nullptr;
1415}
1416
1417std::optional<Value *> Attributor::getAssumedSimplified(
1418 const IRPosition &IRP, const AbstractAttribute *AA,
1419 bool &UsedAssumedInformation, AA::ValueScope S) {
1420 // First check all callbacks provided by outside AAs. If any of them returns
1421 // a non-null value that is different from the associated value, or
1422 // std::nullopt, we assume it's simplified.
1423 for (auto &CB : SimplificationCallbacks.lookup(Val: IRP))
1424 return CB(IRP, AA, UsedAssumedInformation);
1425
1426 SmallVector<AA::ValueAndContext> Values;
1427 if (!getAssumedSimplifiedValues(IRP, AA, Values, S, UsedAssumedInformation))
1428 return &IRP.getAssociatedValue();
1429 if (Values.empty())
1430 return std::nullopt;
1431 if (AA)
1432 if (Value *V = AAPotentialValues::getSingleValue(A&: *this, AA: *AA, IRP, Values))
1433 return V;
1434 if (IRP.getPositionKind() == IRPosition::IRP_RETURNED ||
1435 IRP.getPositionKind() == IRPosition::IRP_CALL_SITE_RETURNED)
1436 return nullptr;
1437 return &IRP.getAssociatedValue();
1438}
1439
1440bool Attributor::getAssumedSimplifiedValues(
1441 const IRPosition &InitialIRP, const AbstractAttribute *AA,
1442 SmallVectorImpl<AA::ValueAndContext> &Values, AA::ValueScope S,
1443 bool &UsedAssumedInformation, bool RecurseForSelectAndPHI) {
1444 SmallPtrSet<Value *, 8> Seen;
1445 SmallVector<IRPosition, 8> Worklist;
1446 Worklist.push_back(Elt: InitialIRP);
1447 while (!Worklist.empty()) {
1448 const IRPosition &IRP = Worklist.pop_back_val();
1449
1450 // First check all callbacks provided by outside AAs. If any of them returns
1451 // a non-null value that is different from the associated value, or
1452 // std::nullopt, we assume it's simplified.
1453 int NV = Values.size();
1454 const auto &SimplificationCBs = SimplificationCallbacks.lookup(Val: IRP);
1455 for (const auto &CB : SimplificationCBs) {
1456 std::optional<Value *> CBResult = CB(IRP, AA, UsedAssumedInformation);
1457 if (!CBResult.has_value())
1458 continue;
1459 Value *V = *CBResult;
1460 if (!V)
1461 return false;
1462 if ((S & AA::ValueScope::Interprocedural) ||
1463 AA::isValidInScope(V: *V, Scope: IRP.getAnchorScope()))
1464 Values.push_back(Elt: AA::ValueAndContext{*V, nullptr});
1465 else
1466 return false;
1467 }
1468 if (SimplificationCBs.empty()) {
1469 // If no high-level/outside simplification occurred, use
1470 // AAPotentialValues.
1471 const auto *PotentialValuesAA =
1472 getOrCreateAAFor<AAPotentialValues>(IRP, QueryingAA: AA, DepClass: DepClassTy::OPTIONAL);
1473 if (PotentialValuesAA &&
1474 PotentialValuesAA->getAssumedSimplifiedValues(A&: *this, Values, S)) {
1475 UsedAssumedInformation |= !PotentialValuesAA->isAtFixpoint();
1476 } else if (IRP.getPositionKind() != IRPosition::IRP_RETURNED) {
1477 Values.push_back(Elt: {IRP.getAssociatedValue(), IRP.getCtxI()});
1478 } else {
1479 // TODO: We could visit all returns and add the operands.
1480 return false;
1481 }
1482 }
1483
1484 if (!RecurseForSelectAndPHI)
1485 break;
1486
1487 for (int I = NV, E = Values.size(); I < E; ++I) {
1488 Value *V = Values[I].getValue();
1489 if (!isa<PHINode>(Val: V) && !isa<SelectInst>(Val: V))
1490 continue;
1491 if (!Seen.insert(Ptr: V).second)
1492 continue;
1493 // Move the last element to this slot.
1494 Values[I] = Values[E - 1];
1495 // Eliminate the last slot, adjust the indices.
1496 Values.pop_back();
1497 --E;
1498 --I;
1499 // Add a new value (select or phi) to the worklist.
1500 Worklist.push_back(Elt: IRPosition::value(V: *V));
1501 }
1502 }
1503 return true;
1504}
1505
1506std::optional<Value *> Attributor::translateArgumentToCallSiteContent(
1507 std::optional<Value *> V, CallBase &CB, const AbstractAttribute &AA,
1508 bool &UsedAssumedInformation) {
1509 if (!V)
1510 return V;
1511 if (*V == nullptr || isa<Constant>(Val: *V))
1512 return V;
1513 if (auto *Arg = dyn_cast<Argument>(Val: *V))
1514 if (CB.getCalledOperand() == Arg->getParent() &&
1515 CB.arg_size() > Arg->getArgNo())
1516 if (!Arg->hasPointeeInMemoryValueAttr())
1517 return getAssumedSimplified(
1518 IRP: IRPosition::callsite_argument(CB, ArgNo: Arg->getArgNo()), AA,
1519 UsedAssumedInformation, S: AA::Intraprocedural);
1520 return nullptr;
1521}
1522
1523Attributor::~Attributor() {
1524 // The abstract attributes are allocated via the BumpPtrAllocator Allocator,
1525 // thus we cannot delete them. We can, and want to, destruct them though.
1526 for (auto &It : AAMap) {
1527 AbstractAttribute *AA = It.getSecond();
1528 AA->~AbstractAttribute();
1529 }
1530}
1531
1532bool Attributor::isAssumedDead(const AbstractAttribute &AA,
1533 const AAIsDead *FnLivenessAA,
1534 bool &UsedAssumedInformation,
1535 bool CheckBBLivenessOnly, DepClassTy DepClass) {
1536 if (!Configuration.UseLiveness)
1537 return false;
1538 const IRPosition &IRP = AA.getIRPosition();
1539 if (!Functions.count(key: IRP.getAnchorScope()))
1540 return false;
1541 return isAssumedDead(IRP, QueryingAA: &AA, FnLivenessAA, UsedAssumedInformation,
1542 CheckBBLivenessOnly, DepClass);
1543}
1544
1545bool Attributor::isAssumedDead(const Use &U,
1546 const AbstractAttribute *QueryingAA,
1547 const AAIsDead *FnLivenessAA,
1548 bool &UsedAssumedInformation,
1549 bool CheckBBLivenessOnly, DepClassTy DepClass) {
1550 if (!Configuration.UseLiveness)
1551 return false;
1552 Instruction *UserI = dyn_cast<Instruction>(Val: U.getUser());
1553 if (!UserI)
1554 return isAssumedDead(IRP: IRPosition::value(V: *U.get()), QueryingAA, FnLivenessAA,
1555 UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
1556
1557 if (auto *CB = dyn_cast<CallBase>(Val: UserI)) {
1558 // For call site argument uses we can check if the argument is
1559 // unused/dead.
1560 if (CB->isArgOperand(U: &U)) {
1561 const IRPosition &CSArgPos =
1562 IRPosition::callsite_argument(CB: *CB, ArgNo: CB->getArgOperandNo(U: &U));
1563 return isAssumedDead(IRP: CSArgPos, QueryingAA, FnLivenessAA,
1564 UsedAssumedInformation, CheckBBLivenessOnly,
1565 DepClass);
1566 }
1567 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(Val: UserI)) {
1568 const IRPosition &RetPos = IRPosition::returned(F: *RI->getFunction());
1569 return isAssumedDead(IRP: RetPos, QueryingAA, FnLivenessAA,
1570 UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
1571 } else if (PHINode *PHI = dyn_cast<PHINode>(Val: UserI)) {
1572 BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
1573 return isAssumedDead(I: *IncomingBB->getTerminator(), QueryingAA, LivenessAA: FnLivenessAA,
1574 UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
1575 } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: UserI)) {
1576 if (!CheckBBLivenessOnly && SI->getPointerOperand() != U.get()) {
1577 const IRPosition IRP = IRPosition::inst(I: *SI);
1578 const AAIsDead *IsDeadAA =
1579 getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, DepClass: DepClassTy::NONE);
1580 if (IsDeadAA && IsDeadAA->isRemovableStore()) {
1581 if (QueryingAA)
1582 recordDependence(FromAA: *IsDeadAA, ToAA: *QueryingAA, DepClass);
1583 if (!IsDeadAA->isKnown(BitsEncoding: AAIsDead::IS_REMOVABLE))
1584 UsedAssumedInformation = true;
1585 return true;
1586 }
1587 }
1588 }
1589
1590 return isAssumedDead(IRP: IRPosition::inst(I: *UserI), QueryingAA, FnLivenessAA,
1591 UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
1592}
1593
1594bool Attributor::isAssumedDead(const Instruction &I,
1595 const AbstractAttribute *QueryingAA,
1596 const AAIsDead *FnLivenessAA,
1597 bool &UsedAssumedInformation,
1598 bool CheckBBLivenessOnly, DepClassTy DepClass,
1599 bool CheckForDeadStore) {
1600 if (!Configuration.UseLiveness)
1601 return false;
1602 const IRPosition::CallBaseContext *CBCtx =
1603 QueryingAA ? QueryingAA->getCallBaseContext() : nullptr;
1604
1605 if (ManifestAddedBlocks.contains(Ptr: I.getParent()))
1606 return false;
1607
1608 const Function &F = *I.getFunction();
1609 if (!FnLivenessAA || FnLivenessAA->getAnchorScope() != &F)
1610 FnLivenessAA = getOrCreateAAFor<AAIsDead>(IRP: IRPosition::function(F, CBContext: CBCtx),
1611 QueryingAA, DepClass: DepClassTy::NONE);
1612
1613 // Don't use recursive reasoning.
1614 if (!FnLivenessAA || QueryingAA == FnLivenessAA)
1615 return false;
1616
1617 // If we have a context instruction and a liveness AA we use it.
1618 if (CheckBBLivenessOnly ? FnLivenessAA->isAssumedDead(BB: I.getParent())
1619 : FnLivenessAA->isAssumedDead(I: &I)) {
1620 if (QueryingAA)
1621 recordDependence(FromAA: *FnLivenessAA, ToAA: *QueryingAA, DepClass);
1622 if (!FnLivenessAA->isKnownDead(I: &I))
1623 UsedAssumedInformation = true;
1624 return true;
1625 }
1626
1627 if (CheckBBLivenessOnly)
1628 return false;
1629
1630 const IRPosition IRP = IRPosition::inst(I, CBContext: CBCtx);
1631 const AAIsDead *IsDeadAA =
1632 getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, DepClass: DepClassTy::NONE);
1633
1634 // Don't use recursive reasoning.
1635 if (!IsDeadAA || QueryingAA == IsDeadAA)
1636 return false;
1637
1638 if (IsDeadAA->isAssumedDead()) {
1639 if (QueryingAA)
1640 recordDependence(FromAA: *IsDeadAA, ToAA: *QueryingAA, DepClass);
1641 if (!IsDeadAA->isKnownDead())
1642 UsedAssumedInformation = true;
1643 return true;
1644 }
1645
1646 if (CheckForDeadStore && isa<StoreInst>(Val: I) && IsDeadAA->isRemovableStore()) {
1647 if (QueryingAA)
1648 recordDependence(FromAA: *IsDeadAA, ToAA: *QueryingAA, DepClass);
1649 if (!IsDeadAA->isKnownDead())
1650 UsedAssumedInformation = true;
1651 return true;
1652 }
1653
1654 return false;
1655}
1656
1657bool Attributor::isAssumedDead(const IRPosition &IRP,
1658 const AbstractAttribute *QueryingAA,
1659 const AAIsDead *FnLivenessAA,
1660 bool &UsedAssumedInformation,
1661 bool CheckBBLivenessOnly, DepClassTy DepClass) {
1662 if (!Configuration.UseLiveness)
1663 return false;
1664 // Don't check liveness for constants, e.g. functions, used as (floating)
1665 // values since the context instruction and such is here meaningless.
1666 if (IRP.getPositionKind() == IRPosition::IRP_FLOAT &&
1667 isa<Constant>(Val: IRP.getAssociatedValue())) {
1668 return false;
1669 }
1670
1671 Instruction *CtxI = IRP.getCtxI();
1672 if (CtxI &&
1673 isAssumedDead(I: *CtxI, QueryingAA, FnLivenessAA, UsedAssumedInformation,
1674 /* CheckBBLivenessOnly */ true,
1675 DepClass: CheckBBLivenessOnly ? DepClass : DepClassTy::OPTIONAL))
1676 return true;
1677
1678 if (CheckBBLivenessOnly)
1679 return false;
1680
1681 // If we haven't succeeded we query the specific liveness info for the IRP.
1682 const AAIsDead *IsDeadAA;
1683 if (IRP.getPositionKind() == IRPosition::IRP_CALL_SITE)
1684 IsDeadAA = getOrCreateAAFor<AAIsDead>(
1685 IRP: IRPosition::callsite_returned(CB: cast<CallBase>(Val&: IRP.getAssociatedValue())),
1686 QueryingAA, DepClass: DepClassTy::NONE);
1687 else
1688 IsDeadAA = getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, DepClass: DepClassTy::NONE);
1689
1690 // Don't use recursive reasoning.
1691 if (!IsDeadAA || QueryingAA == IsDeadAA)
1692 return false;
1693
1694 if (IsDeadAA->isAssumedDead()) {
1695 if (QueryingAA)
1696 recordDependence(FromAA: *IsDeadAA, ToAA: *QueryingAA, DepClass);
1697 if (!IsDeadAA->isKnownDead())
1698 UsedAssumedInformation = true;
1699 return true;
1700 }
1701
1702 return false;
1703}
1704
1705bool Attributor::isAssumedDead(const BasicBlock &BB,
1706 const AbstractAttribute *QueryingAA,
1707 const AAIsDead *FnLivenessAA,
1708 DepClassTy DepClass) {
1709 if (!Configuration.UseLiveness)
1710 return false;
1711 const Function &F = *BB.getParent();
1712 if (!FnLivenessAA || FnLivenessAA->getAnchorScope() != &F)
1713 FnLivenessAA = getOrCreateAAFor<AAIsDead>(IRP: IRPosition::function(F),
1714 QueryingAA, DepClass: DepClassTy::NONE);
1715
1716 // Don't use recursive reasoning.
1717 if (!FnLivenessAA || QueryingAA == FnLivenessAA)
1718 return false;
1719
1720 if (FnLivenessAA->isAssumedDead(BB: &BB)) {
1721 if (QueryingAA)
1722 recordDependence(FromAA: *FnLivenessAA, ToAA: *QueryingAA, DepClass);
1723 return true;
1724 }
1725
1726 return false;
1727}
1728
1729bool Attributor::checkForAllCallees(
1730 function_ref<bool(ArrayRef<const Function *>)> Pred,
1731 const AbstractAttribute &QueryingAA, const CallBase &CB) {
1732 if (const Function *Callee = dyn_cast<Function>(Val: CB.getCalledOperand()))
1733 return Pred(Callee);
1734
1735 const auto *CallEdgesAA = getAAFor<AACallEdges>(
1736 QueryingAA, IRP: IRPosition::callsite_function(CB), DepClass: DepClassTy::OPTIONAL);
1737 if (!CallEdgesAA || CallEdgesAA->hasUnknownCallee())
1738 return false;
1739
1740 const auto &Callees = CallEdgesAA->getOptimisticEdges();
1741 return Pred(Callees.getArrayRef());
1742}
1743
1744bool canMarkAsVisited(const User *Usr) {
1745 return isa<PHINode>(Val: Usr) || !isa<Instruction>(Val: Usr);
1746}
1747
1748bool Attributor::checkForAllUses(
1749 function_ref<bool(const Use &, bool &)> Pred,
1750 const AbstractAttribute &QueryingAA, const Value &V,
1751 bool CheckBBLivenessOnly, DepClassTy LivenessDepClass,
1752 bool IgnoreDroppableUses,
1753 function_ref<bool(const Use &OldU, const Use &NewU)> EquivalentUseCB) {
1754
1755 // Check virtual uses first.
1756 for (VirtualUseCallbackTy &CB : VirtualUseCallbacks.lookup(Val: &V))
1757 if (!CB(*this, &QueryingAA))
1758 return false;
1759
1760 if (isa<ConstantData>(Val: V))
1761 return false;
1762
1763 // Check the trivial case first as it catches void values.
1764 if (V.use_empty())
1765 return true;
1766
1767 const IRPosition &IRP = QueryingAA.getIRPosition();
1768 SmallVector<const Use *, 16> Worklist;
1769 SmallPtrSet<const Use *, 16> Visited;
1770
1771 auto AddUsers = [&](const Value &V, const Use *OldUse) {
1772 for (const Use &UU : V.uses()) {
1773 if (OldUse && EquivalentUseCB && !EquivalentUseCB(*OldUse, UU)) {
1774 LLVM_DEBUG(dbgs() << "[Attributor] Potential copy was "
1775 "rejected by the equivalence call back: "
1776 << *UU << "!\n");
1777 return false;
1778 }
1779
1780 Worklist.push_back(Elt: &UU);
1781 }
1782 return true;
1783 };
1784
1785 AddUsers(V, /* OldUse */ nullptr);
1786
1787 LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size()
1788 << " initial uses to check\n");
1789
1790 const Function *ScopeFn = IRP.getAnchorScope();
1791 const auto *LivenessAA =
1792 ScopeFn ? getAAFor<AAIsDead>(QueryingAA, IRP: IRPosition::function(F: *ScopeFn),
1793 DepClass: DepClassTy::NONE)
1794 : nullptr;
1795
1796 while (!Worklist.empty()) {
1797 const Use *U = Worklist.pop_back_val();
1798 if (canMarkAsVisited(Usr: U->getUser()) && !Visited.insert(Ptr: U).second)
1799 continue;
1800 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE, {
1801 if (auto *Fn = dyn_cast<Function>(U->getUser()))
1802 dbgs() << "[Attributor] Check use: " << **U << " in " << Fn->getName()
1803 << "\n";
1804 else
1805 dbgs() << "[Attributor] Check use: " << **U << " in " << *U->getUser()
1806 << "\n";
1807 });
1808 bool UsedAssumedInformation = false;
1809 if (isAssumedDead(U: *U, QueryingAA: &QueryingAA, FnLivenessAA: LivenessAA, UsedAssumedInformation,
1810 CheckBBLivenessOnly, DepClass: LivenessDepClass)) {
1811 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE,
1812 dbgs() << "[Attributor] Dead use, skip!\n");
1813 continue;
1814 }
1815 if (IgnoreDroppableUses && U->getUser()->isDroppable()) {
1816 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE,
1817 dbgs() << "[Attributor] Droppable user, skip!\n");
1818 continue;
1819 }
1820
1821 if (auto *SI = dyn_cast<StoreInst>(Val: U->getUser())) {
1822 if (&SI->getOperandUse(i: 0) == U) {
1823 if (!Visited.insert(Ptr: U).second)
1824 continue;
1825 SmallSetVector<Value *, 4> PotentialCopies;
1826 if (AA::getPotentialCopiesOfStoredValue(
1827 A&: *this, SI&: *SI, PotentialCopies, QueryingAA, UsedAssumedInformation,
1828 /* OnlyExact */ true)) {
1829 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE,
1830 dbgs()
1831 << "[Attributor] Value is stored, continue with "
1832 << PotentialCopies.size()
1833 << " potential copies instead!\n");
1834 for (Value *PotentialCopy : PotentialCopies)
1835 if (!AddUsers(*PotentialCopy, U))
1836 return false;
1837 continue;
1838 }
1839 }
1840 }
1841
1842 bool Follow = false;
1843 if (!Pred(*U, Follow))
1844 return false;
1845 if (!Follow)
1846 continue;
1847
1848 User &Usr = *U->getUser();
1849 AddUsers(Usr, /* OldUse */ nullptr);
1850 }
1851
1852 return true;
1853}
1854
1855bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
1856 const AbstractAttribute &QueryingAA,
1857 bool RequireAllCallSites,
1858 bool &UsedAssumedInformation) {
1859 // We can try to determine information from
1860 // the call sites. However, this is only possible all call sites are known,
1861 // hence the function has internal linkage.
1862 const IRPosition &IRP = QueryingAA.getIRPosition();
1863 const Function *AssociatedFunction = IRP.getAssociatedFunction();
1864 if (!AssociatedFunction) {
1865 LLVM_DEBUG(dbgs() << "[Attributor] No function associated with " << IRP
1866 << "\n");
1867 return false;
1868 }
1869
1870 return checkForAllCallSites(Pred, Fn: *AssociatedFunction, RequireAllCallSites,
1871 QueryingAA: &QueryingAA, UsedAssumedInformation);
1872}
1873
1874bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
1875 const Function &Fn,
1876 bool RequireAllCallSites,
1877 const AbstractAttribute *QueryingAA,
1878 bool &UsedAssumedInformation,
1879 bool CheckPotentiallyDead) {
1880 if (RequireAllCallSites && !Fn.hasLocalLinkage()) {
1881 LLVM_DEBUG(
1882 dbgs()
1883 << "[Attributor] Function " << Fn.getName()
1884 << " has no internal linkage, hence not all call sites are known\n");
1885 return false;
1886 }
1887 // Check virtual uses first.
1888 for (VirtualUseCallbackTy &CB : VirtualUseCallbacks.lookup(Val: &Fn))
1889 if (!CB(*this, QueryingAA))
1890 return false;
1891
1892 SmallVector<const Use *, 8> Uses(make_pointer_range(Range: Fn.uses()));
1893 for (unsigned u = 0; u < Uses.size(); ++u) {
1894 const Use &U = *Uses[u];
1895 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE, {
1896 if (auto *Fn = dyn_cast<Function>(U))
1897 dbgs() << "[Attributor] Check use: " << Fn->getName() << " in "
1898 << *U.getUser() << "\n";
1899 else
1900 dbgs() << "[Attributor] Check use: " << *U << " in " << *U.getUser()
1901 << "\n";
1902 });
1903 if (!CheckPotentiallyDead &&
1904 isAssumedDead(U, QueryingAA, FnLivenessAA: nullptr, UsedAssumedInformation,
1905 /* CheckBBLivenessOnly */ true)) {
1906 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE,
1907 dbgs() << "[Attributor] Dead use, skip!\n");
1908 continue;
1909 }
1910 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: U.getUser())) {
1911 if (CE->isCast() && CE->getType()->isPointerTy()) {
1912 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE, {
1913 dbgs() << "[Attributor] Use, is constant cast expression, add "
1914 << CE->getNumUses() << " uses of that expression instead!\n";
1915 });
1916 for (const Use &CEU : CE->uses())
1917 Uses.push_back(Elt: &CEU);
1918 continue;
1919 }
1920 }
1921
1922 AbstractCallSite ACS(&U);
1923 if (!ACS) {
1924 LLVM_DEBUG(dbgs() << "[Attributor] Function " << Fn.getName()
1925 << " has non call site use " << *U.get() << " in "
1926 << *U.getUser() << "\n");
1927 return false;
1928 }
1929
1930 const Use *EffectiveUse =
1931 ACS.isCallbackCall() ? &ACS.getCalleeUseForCallback() : &U;
1932 if (!ACS.isCallee(U: EffectiveUse)) {
1933 if (!RequireAllCallSites) {
1934 LLVM_DEBUG(dbgs() << "[Attributor] User " << *EffectiveUse->getUser()
1935 << " is not a call of " << Fn.getName()
1936 << ", skip use\n");
1937 continue;
1938 }
1939 LLVM_DEBUG(dbgs() << "[Attributor] User " << *EffectiveUse->getUser()
1940 << " is an invalid use of " << Fn.getName() << "\n");
1941 return false;
1942 }
1943
1944 // Make sure the arguments that can be matched between the call site and the
1945 // callee argee on their type. It is unlikely they do not and it doesn't
1946 // make sense for all attributes to know/care about this.
1947 assert(&Fn == ACS.getCalledFunction() && "Expected known callee");
1948 unsigned MinArgsParams =
1949 std::min(a: size_t(ACS.getNumArgOperands()), b: Fn.arg_size());
1950 for (unsigned u = 0; u < MinArgsParams; ++u) {
1951 Value *CSArgOp = ACS.getCallArgOperand(ArgNo: u);
1952 if (CSArgOp && Fn.getArg(i: u)->getType() != CSArgOp->getType()) {
1953 LLVM_DEBUG(
1954 dbgs() << "[Attributor] Call site / callee argument type mismatch ["
1955 << u << "@" << Fn.getName() << ": "
1956 << *Fn.getArg(u)->getType() << " vs. "
1957 << *ACS.getCallArgOperand(u)->getType() << "\n");
1958 return false;
1959 }
1960 }
1961
1962 if (Pred(ACS))
1963 continue;
1964
1965 LLVM_DEBUG(dbgs() << "[Attributor] Call site callback failed for "
1966 << *ACS.getInstruction() << "\n");
1967 return false;
1968 }
1969
1970 return true;
1971}
1972
1973bool Attributor::shouldPropagateCallBaseContext(const IRPosition &IRP) {
1974 // TODO: Maintain a cache of Values that are
1975 // on the pathway from a Argument to a Instruction that would effect the
1976 // liveness/return state etc.
1977 return Opts.attributor_enable_call_site_specific_deduction;
1978}
1979
1980bool Attributor::checkForAllReturnedValues(function_ref<bool(Value &)> Pred,
1981 const AbstractAttribute &QueryingAA,
1982 AA::ValueScope S,
1983 bool RecurseForSelectAndPHI) {
1984
1985 const IRPosition &IRP = QueryingAA.getIRPosition();
1986 const Function *AssociatedFunction = IRP.getAssociatedFunction();
1987 if (!AssociatedFunction)
1988 return false;
1989
1990 bool UsedAssumedInformation = false;
1991 SmallVector<AA::ValueAndContext> Values;
1992 if (!getAssumedSimplifiedValues(
1993 InitialIRP: IRPosition::returned(F: *AssociatedFunction), AA: &QueryingAA, Values, S,
1994 UsedAssumedInformation, RecurseForSelectAndPHI))
1995 return false;
1996
1997 return llvm::all_of(Range&: Values, P: [&](const AA::ValueAndContext &VAC) {
1998 return Pred(*VAC.getValue());
1999 });
2000}
2001
2002static bool checkForAllInstructionsImpl(
2003 Attributor *A, InformationCache::OpcodeInstMapTy &OpcodeInstMap,
2004 function_ref<bool(Instruction &)> Pred, const AbstractAttribute *QueryingAA,
2005 const AAIsDead *LivenessAA, ArrayRef<unsigned> Opcodes,
2006 bool &UsedAssumedInformation, bool CheckBBLivenessOnly = false,
2007 bool CheckPotentiallyDead = false) {
2008 for (unsigned Opcode : Opcodes) {
2009 // Check if we have instructions with this opcode at all first.
2010 auto *Insts = OpcodeInstMap[Opcode];
2011 if (!Insts)
2012 continue;
2013
2014 for (Instruction *I : *Insts) {
2015 // Skip dead instructions.
2016 if (A && !CheckPotentiallyDead &&
2017 A->isAssumedDead(IRP: IRPosition::inst(I: *I), QueryingAA, FnLivenessAA: LivenessAA,
2018 UsedAssumedInformation, CheckBBLivenessOnly)) {
2019 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE,
2020 dbgs() << "[Attributor] Instruction " << *I
2021 << " is potentially dead, skip!\n";);
2022 continue;
2023 }
2024
2025 if (!Pred(*I))
2026 return false;
2027 }
2028 }
2029 return true;
2030}
2031
2032bool Attributor::checkForAllInstructions(function_ref<bool(Instruction &)> Pred,
2033 const Function *Fn,
2034 const AbstractAttribute *QueryingAA,
2035 ArrayRef<unsigned> Opcodes,
2036 bool &UsedAssumedInformation,
2037 bool CheckBBLivenessOnly,
2038 bool CheckPotentiallyDead) {
2039 // Since we need to provide instructions we have to have an exact definition.
2040 if (!Fn || Fn->isDeclaration())
2041 return false;
2042
2043 const IRPosition &QueryIRP = IRPosition::function(F: *Fn);
2044 const auto *LivenessAA =
2045 CheckPotentiallyDead && QueryingAA
2046 ? (getAAFor<AAIsDead>(QueryingAA: *QueryingAA, IRP: QueryIRP, DepClass: DepClassTy::NONE))
2047 : nullptr;
2048
2049 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F: *Fn);
2050 if (!checkForAllInstructionsImpl(A: this, OpcodeInstMap, Pred, QueryingAA,
2051 LivenessAA, Opcodes, UsedAssumedInformation,
2052 CheckBBLivenessOnly, CheckPotentiallyDead))
2053 return false;
2054
2055 return true;
2056}
2057
2058bool Attributor::checkForAllInstructions(function_ref<bool(Instruction &)> Pred,
2059 const AbstractAttribute &QueryingAA,
2060 ArrayRef<unsigned> Opcodes,
2061 bool &UsedAssumedInformation,
2062 bool CheckBBLivenessOnly,
2063 bool CheckPotentiallyDead) {
2064 const IRPosition &IRP = QueryingAA.getIRPosition();
2065 const Function *AssociatedFunction = IRP.getAssociatedFunction();
2066 return checkForAllInstructions(Pred, Fn: AssociatedFunction, QueryingAA: &QueryingAA, Opcodes,
2067 UsedAssumedInformation, CheckBBLivenessOnly,
2068 CheckPotentiallyDead);
2069}
2070
2071bool Attributor::checkForAllReadWriteInstructions(
2072 function_ref<bool(Instruction &)> Pred, AbstractAttribute &QueryingAA,
2073 bool &UsedAssumedInformation) {
2074 TimeTraceScope TS("checkForAllReadWriteInstructions");
2075
2076 const Function *AssociatedFunction =
2077 QueryingAA.getIRPosition().getAssociatedFunction();
2078 if (!AssociatedFunction)
2079 return false;
2080
2081 const IRPosition &QueryIRP = IRPosition::function(F: *AssociatedFunction);
2082 const auto *LivenessAA =
2083 getAAFor<AAIsDead>(QueryingAA, IRP: QueryIRP, DepClass: DepClassTy::NONE);
2084
2085 for (Instruction *I :
2086 InfoCache.getReadOrWriteInstsForFunction(F: *AssociatedFunction)) {
2087 // Skip dead instructions.
2088 if (isAssumedDead(IRP: IRPosition::inst(I: *I), QueryingAA: &QueryingAA, FnLivenessAA: LivenessAA,
2089 UsedAssumedInformation))
2090 continue;
2091
2092 if (!Pred(*I))
2093 return false;
2094 }
2095
2096 return true;
2097}
2098
2099void Attributor::runTillFixpoint() {
2100 TimeTraceScope TimeScope("Attributor::runTillFixpoint");
2101 LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
2102 << DG.SyntheticRoot.Deps.size()
2103 << " abstract attributes.\n");
2104
2105 // Now that all abstract attributes are collected and initialized we start
2106 // the abstract analysis.
2107
2108 unsigned IterationCounter = 1;
2109 unsigned MaxIterations = Configuration.MaxFixpointIterations.value_or(
2110 u: Opts.attributor_max_iterations);
2111
2112 SmallVector<AbstractAttribute *, 32> ChangedAAs;
2113 SetVector<AbstractAttribute *> Worklist, InvalidAAs;
2114 Worklist.reserve(Size: DG.SyntheticRoot.Deps.size());
2115 Worklist.insert_range(R&: DG.SyntheticRoot);
2116
2117 do {
2118 // Remember the size to determine new attributes.
2119 size_t NumAAs = DG.SyntheticRoot.Deps.size();
2120 LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
2121 << ", Worklist size: " << Worklist.size() << "\n");
2122
2123 // For invalid AAs we can fix dependent AAs that have a required dependence,
2124 // thereby folding long dependence chains in a single step without the need
2125 // to run updates.
2126 for (unsigned u = 0; u < InvalidAAs.size(); ++u) {
2127 AbstractAttribute *InvalidAA = InvalidAAs[u];
2128
2129 // Check the dependences to fast track invalidation.
2130 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE,
2131 dbgs() << "[Attributor] InvalidAA: " << *InvalidAA
2132 << " has " << InvalidAA->Deps.size()
2133 << " required & optional dependences\n");
2134 for (auto &DepIt : InvalidAA->Deps) {
2135 AbstractAttribute *DepAA = cast<AbstractAttribute>(Val: DepIt.getPointer());
2136 if (DepIt.getInt() == unsigned(DepClassTy::OPTIONAL)) {
2137 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE,
2138 dbgs() << " - recompute: " << *DepAA);
2139 Worklist.insert(X: DepAA);
2140 continue;
2141 }
2142 DEBUG_WITH_TYPE(VERBOSE_DEBUG_TYPE, dbgs()
2143 << " - invalidate: " << *DepAA);
2144 DepAA->getState().indicatePessimisticFixpoint();
2145 assert(DepAA->getState().isAtFixpoint() && "Expected fixpoint state!");
2146 if (!DepAA->getState().isValidState())
2147 InvalidAAs.insert(X: DepAA);
2148 else
2149 ChangedAAs.push_back(Elt: DepAA);
2150 }
2151 InvalidAA->Deps.clear();
2152 }
2153
2154 // Add all abstract attributes that are potentially dependent on one that
2155 // changed to the work list.
2156 for (AbstractAttribute *ChangedAA : ChangedAAs) {
2157 for (auto &DepIt : ChangedAA->Deps)
2158 Worklist.insert(X: cast<AbstractAttribute>(Val: DepIt.getPointer()));
2159 ChangedAA->Deps.clear();
2160 }
2161
2162 LLVM_DEBUG(dbgs() << "[Attributor] #Iteration: " << IterationCounter
2163 << ", Worklist+Dependent size: " << Worklist.size()
2164 << "\n");
2165
2166 // Reset the changed and invalid set.
2167 ChangedAAs.clear();
2168 InvalidAAs.clear();
2169
2170 // Update all abstract attribute in the work list and record the ones that
2171 // changed.
2172 for (AbstractAttribute *AA : Worklist) {
2173 if (!AA->isStateAtFixpoint())
2174 if (updateAA(AA&: *AA) == ChangeStatus::CHANGED)
2175 ChangedAAs.push_back(Elt: AA);
2176
2177 // Use the InvalidAAs vector to propagate invalid states fast transitively
2178 // without requiring updates.
2179 if (!AA->getState().isValidState())
2180 InvalidAAs.insert(X: AA);
2181 }
2182
2183 // Add attributes to the changed set if they have been created in the last
2184 // iteration.
2185 ChangedAAs.append(in_start: DG.SyntheticRoot.begin() + NumAAs,
2186 in_end: DG.SyntheticRoot.end());
2187
2188 // Reset the work list and repopulate with the changed abstract attributes.
2189 // Note that dependent ones are added above.
2190 Worklist.clear();
2191 Worklist.insert_range(R&: ChangedAAs);
2192 Worklist.insert_range(R&: QueryAAsAwaitingUpdate);
2193 QueryAAsAwaitingUpdate.clear();
2194
2195 } while (!Worklist.empty() && (IterationCounter++ < MaxIterations));
2196
2197 if (IterationCounter > MaxIterations && !Functions.empty()) {
2198 auto Remark = [&](OptimizationRemarkMissed ORM) {
2199 return ORM << "Attributor did not reach a fixpoint after "
2200 << ore::NV("Iterations", MaxIterations) << " iterations.";
2201 };
2202 Function *F = Functions.front();
2203 emitRemark<OptimizationRemarkMissed>(F, RemarkName: "FixedPoint", RemarkCB&: Remark);
2204 }
2205
2206 LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
2207 << IterationCounter << "/" << MaxIterations
2208 << " iterations\n");
2209
2210 // Reset abstract arguments not settled in a sound fixpoint by now. This
2211 // happens when we stopped the fixpoint iteration early. Note that only the
2212 // ones marked as "changed" *and* the ones transitively depending on them
2213 // need to be reverted to a pessimistic state. Others might not be in a
2214 // fixpoint state but we can use the optimistic results for them anyway.
2215 SmallPtrSet<AbstractAttribute *, 32> Visited;
2216 for (unsigned u = 0; u < ChangedAAs.size(); u++) {
2217 AbstractAttribute *ChangedAA = ChangedAAs[u];
2218 if (!Visited.insert(Ptr: ChangedAA).second)
2219 continue;
2220
2221 AbstractState &State = ChangedAA->getState();
2222 if (!State.isAtFixpoint()) {
2223 State.indicatePessimisticFixpoint();
2224
2225 NumAttributesTimedOut++;
2226 }
2227
2228 for (auto &DepIt : ChangedAA->Deps)
2229 ChangedAAs.push_back(Elt: cast<AbstractAttribute>(Val: DepIt.getPointer()));
2230 ChangedAA->Deps.clear();
2231 }
2232
2233 LLVM_DEBUG({
2234 if (!Visited.empty())
2235 dbgs() << "\n[Attributor] Finalized " << Visited.size()
2236 << " abstract attributes.\n";
2237 });
2238}
2239
2240void Attributor::registerForUpdate(AbstractAttribute &AA) {
2241 assert(AA.isQueryAA() &&
2242 "Non-query AAs should not be required to register for updates!");
2243 QueryAAsAwaitingUpdate.insert(X: &AA);
2244}
2245
2246ChangeStatus Attributor::manifestAttributes() {
2247 TimeTraceScope TimeScope("Attributor::manifestAttributes");
2248 size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();
2249
2250 unsigned NumManifested = 0;
2251 unsigned NumAtFixpoint = 0;
2252 ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
2253 for (auto &DepAA : DG.SyntheticRoot.Deps) {
2254 AbstractAttribute *AA = cast<AbstractAttribute>(Val: DepAA.getPointer());
2255 AbstractState &State = AA->getState();
2256
2257 // If there is not already a fixpoint reached, we can now take the
2258 // optimistic state. This is correct because we enforced a pessimistic one
2259 // on abstract attributes that were transitively dependent on a changed one
2260 // already above.
2261 if (!AA->isStateAtFixpoint())
2262 State.indicateOptimisticFixpoint();
2263
2264 // We must not manifest Attributes that use Callbase info.
2265 if (AA->hasCallBaseContext())
2266 continue;
2267 // If the state is invalid, we do not try to manifest it.
2268 if (!State.isValidState())
2269 continue;
2270
2271 if (AA->getCtxI() && !isRunOn(Fn&: *AA->getAnchorScope()))
2272 continue;
2273
2274 // Skip dead code.
2275 bool UsedAssumedInformation = false;
2276 if (isAssumedDead(AA: *AA, FnLivenessAA: nullptr, UsedAssumedInformation,
2277 /* CheckBBLivenessOnly */ true))
2278 continue;
2279 // Check if the manifest debug counter that allows skipping manifestation of
2280 // AAs
2281 if (!DebugCounter::shouldExecute(Counter&: ManifestDBGCounter))
2282 continue;
2283 // Manifest the state and record if we changed the IR.
2284 ChangeStatus LocalChange = AA->manifest(A&: *this);
2285 if (LocalChange == ChangeStatus::CHANGED && AreStatisticsEnabled())
2286 AA->trackStatistics();
2287 LLVM_DEBUG(dbgs() << "[Attributor] Manifest " << LocalChange << " : " << *AA
2288 << "\n");
2289
2290 ManifestChange = ManifestChange | LocalChange;
2291
2292 NumAtFixpoint++;
2293 NumManifested += (LocalChange == ChangeStatus::CHANGED);
2294 }
2295
2296 (void)NumManifested;
2297 (void)NumAtFixpoint;
2298 LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
2299 << " arguments while " << NumAtFixpoint
2300 << " were in a valid fixpoint state\n");
2301
2302 NumAttributesManifested += NumManifested;
2303 NumAttributesValidFixpoint += NumAtFixpoint;
2304
2305 (void)NumFinalAAs;
2306 if (NumFinalAAs != DG.SyntheticRoot.Deps.size()) {
2307 auto DepIt = DG.SyntheticRoot.Deps.begin();
2308 for (unsigned u = 0; u < NumFinalAAs; ++u)
2309 ++DepIt;
2310 for (unsigned u = NumFinalAAs; u < DG.SyntheticRoot.Deps.size();
2311 ++u, ++DepIt) {
2312 errs() << "Unexpected abstract attribute: "
2313 << cast<AbstractAttribute>(Val: DepIt->getPointer()) << " :: "
2314 << cast<AbstractAttribute>(Val: DepIt->getPointer())
2315 ->getIRPosition()
2316 .getAssociatedValue()
2317 << "\n";
2318 }
2319 llvm_unreachable("Expected the final number of abstract attributes to "
2320 "remain unchanged!");
2321 }
2322
2323 for (auto &It : AttrsMap) {
2324 AttributeList &AL = It.getSecond();
2325 const IRPosition &IRP =
2326 isa<Function>(Val: It.getFirst())
2327 ? IRPosition::function(F: *cast<Function>(Val: It.getFirst()))
2328 : IRPosition::callsite_function(CB: *cast<CallBase>(Val: It.getFirst()));
2329 if (IRP.getAttrList() == AL)
2330 continue;
2331 IRP.setAttrList(AL);
2332 AttrModifiedFunctions.insert(X: IRP.getAnchorScope());
2333 }
2334
2335 return ManifestChange;
2336}
2337
2338void Attributor::identifyDeadInternalFunctions() {
2339 // Early exit if we don't intend to delete functions.
2340 if (!Configuration.DeleteFns)
2341 return;
2342
2343 // To avoid triggering an assertion in the lazy call graph we will not delete
2344 // any internal library functions. We should modify the assertion though and
2345 // allow internals to be deleted.
2346 const auto *TLI =
2347 isModulePass()
2348 ? nullptr
2349 : getInfoCache().getTargetLibraryInfoForFunction(F: *Functions.back());
2350
2351 // Identify dead internal functions and delete them. This happens outside
2352 // the other fixpoint analysis as we might treat potentially dead functions
2353 // as live to lower the number of iterations. If they happen to be dead, the
2354 // below fixpoint loop will identify and eliminate them.
2355
2356 SmallVector<Function *, 8> InternalFns;
2357 for (Function *F : Functions)
2358 if (F->hasLocalLinkage() &&
2359 (isModulePass() || TLI->getLibFunc(FDecl: *F) == NotLibFunc))
2360 InternalFns.push_back(Elt: F);
2361
2362 SmallPtrSet<Function *, 8> LiveInternalFns;
2363 bool FoundLiveInternal = true;
2364 while (FoundLiveInternal) {
2365 FoundLiveInternal = false;
2366 for (Function *&F : InternalFns) {
2367 if (!F)
2368 continue;
2369
2370 bool UsedAssumedInformation = false;
2371 if (checkForAllCallSites(
2372 Pred: [&](AbstractCallSite ACS) {
2373 Function *Callee = ACS.getInstruction()->getFunction();
2374 return ToBeDeletedFunctions.count(key: Callee) ||
2375 (Functions.count(key: Callee) && Callee->hasLocalLinkage() &&
2376 !LiveInternalFns.count(Ptr: Callee));
2377 },
2378 Fn: *F, RequireAllCallSites: true, QueryingAA: nullptr, UsedAssumedInformation)) {
2379 continue;
2380 }
2381
2382 LiveInternalFns.insert(Ptr: F);
2383 F = nullptr;
2384 FoundLiveInternal = true;
2385 }
2386 }
2387
2388 for (Function *F : InternalFns)
2389 if (F)
2390 ToBeDeletedFunctions.insert(X: F);
2391}
2392
2393ChangeStatus Attributor::cleanupIR() {
2394 TimeTraceScope TimeScope("Attributor::cleanupIR");
2395 // Delete stuff at the end to avoid invalid references and a nice order.
2396 LLVM_DEBUG(dbgs() << "\n[Attributor] Delete/replace at least "
2397 << ToBeDeletedFunctions.size() << " functions and "
2398 << ToBeDeletedBlocks.size() << " blocks and "
2399 << ToBeDeletedInsts.size() << " instructions and "
2400 << ToBeChangedValues.size() << " values and "
2401 << ToBeChangedUses.size() << " uses. To insert "
2402 << ToBeChangedToUnreachableInsts.size()
2403 << " unreachables.\n"
2404 << "Preserve manifest added " << ManifestAddedBlocks.size()
2405 << " blocks\n");
2406
2407 SmallVector<WeakTrackingVH, 32> DeadInsts;
2408 SmallVector<Instruction *, 32> TerminatorsToFold;
2409
2410 auto ReplaceUse = [&](Use *U, Value *NewV) {
2411 Value *OldV = U->get();
2412
2413 // If we plan to replace NewV we need to update it at this point.
2414 do {
2415 const auto &Entry = ToBeChangedValues.lookup(Key: NewV);
2416 if (!get<0>(Pair: Entry))
2417 break;
2418 NewV = get<0>(Pair: Entry);
2419 } while (true);
2420
2421 Instruction *I = dyn_cast<Instruction>(Val: U->getUser());
2422 assert((!I || isRunOn(*I->getFunction())) &&
2423 "Cannot replace an instruction outside the current SCC!");
2424
2425 // Do not replace uses in returns if the value is a must-tail call we will
2426 // not delete.
2427 if (auto *RI = dyn_cast_or_null<ReturnInst>(Val: I)) {
2428 if (auto *CI = dyn_cast<CallInst>(Val: OldV->stripPointerCasts()))
2429 if (CI->isMustTailCall() && !ToBeDeletedInsts.count(key: CI))
2430 return;
2431 // If we rewrite a return and the new value is not an argument, strip the
2432 // `returned` attribute as it is wrong now.
2433 if (!isa<Argument>(Val: NewV))
2434 for (auto &Arg : RI->getFunction()->args())
2435 Arg.removeAttr(Kind: Attribute::Returned);
2436 }
2437
2438 LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser()
2439 << " instead of " << *OldV << "\n");
2440 U->set(NewV);
2441
2442 // The new value may reference a function, e.g., if an argument is replaced
2443 // by a function pointer, so the call graph of the user's function changes.
2444 if (I) {
2445 CGModifiedFunctions.insert(X: I->getFunction());
2446 if (auto *C = dyn_cast<Constant>(Val: NewV))
2447 Configuration.CGUpdater.addReferences(Fn&: *I->getFunction(), C&: *C);
2448 }
2449 if (Instruction *OldI = dyn_cast<Instruction>(Val: OldV)) {
2450 if (!isa<PHINode>(Val: OldI) && !ToBeDeletedInsts.count(key: OldI) &&
2451 isInstructionTriviallyDead(I: OldI))
2452 DeadInsts.push_back(Elt: OldI);
2453 }
2454 if (isa<UndefValue>(Val: NewV) && isa<CallBase>(Val: U->getUser())) {
2455 auto *CB = cast<CallBase>(Val: U->getUser());
2456 if (CB->isArgOperand(U)) {
2457 unsigned Idx = CB->getArgOperandNo(U);
2458 // Drop all attributes that make passing undef UB, e.g., dereferenceable
2459 // implies noundef.
2460 AttributeMask UBImplying = AttributeFuncs::getUBImplyingAttributes();
2461 CB->removeParamAttrs(ArgNo: Idx, AttrsToRemove: UBImplying);
2462 auto *Callee = dyn_cast_if_present<Function>(Val: CB->getCalledOperand());
2463 if (Callee && Callee->arg_size() > Idx)
2464 Callee->removeParamAttrs(ArgNo: Idx, Attrs: UBImplying);
2465 }
2466 }
2467 if (isa<Constant>(Val: NewV) && isa<CondBrInst>(Val: U->getUser())) {
2468 Instruction *UserI = cast<Instruction>(Val: U->getUser());
2469 if (isa<UndefValue>(Val: NewV)) {
2470 ToBeChangedToUnreachableInsts.insert(X: UserI);
2471 } else {
2472 TerminatorsToFold.push_back(Elt: UserI);
2473 }
2474 }
2475 };
2476
2477 for (auto &It : ToBeChangedUses) {
2478 Use *U = It.first;
2479 Value *NewV = It.second;
2480 ReplaceUse(U, NewV);
2481 }
2482
2483 SmallVector<Use *, 4> Uses;
2484 for (auto &It : ToBeChangedValues) {
2485 Value *OldV = It.first;
2486 auto [NewV, Done] = It.second;
2487 Uses.clear();
2488 for (auto &U : OldV->uses())
2489 if (Done || !U.getUser()->isDroppable())
2490 Uses.push_back(Elt: &U);
2491 for (Use *U : Uses) {
2492 if (auto *I = dyn_cast<Instruction>(Val: U->getUser()))
2493 if (!isRunOn(Fn&: *I->getFunction()))
2494 continue;
2495 ReplaceUse(U, NewV);
2496 }
2497 }
2498
2499 for (const auto &V : InvokeWithDeadSuccessor)
2500 if (InvokeInst *II = dyn_cast_or_null<InvokeInst>(Val: V)) {
2501 assert(isRunOn(*II->getFunction()) &&
2502 "Cannot replace an invoke outside the current SCC!");
2503 bool UnwindBBIsDead = II->hasFnAttr(Kind: Attribute::NoUnwind);
2504 bool NormalBBIsDead = II->hasFnAttr(Kind: Attribute::NoReturn);
2505 bool Invoke2CallAllowed =
2506 !AAIsDead::mayCatchAsynchronousExceptions(F: *II->getFunction());
2507 assert((UnwindBBIsDead || NormalBBIsDead) &&
2508 "Invoke does not have dead successors!");
2509 BasicBlock *BB = II->getParent();
2510 BasicBlock *NormalDestBB = II->getNormalDest();
2511 if (UnwindBBIsDead) {
2512 Instruction *NormalNextIP = &NormalDestBB->front();
2513 if (Invoke2CallAllowed) {
2514 changeToCall(II);
2515 NormalNextIP = BB->getTerminator();
2516 }
2517 if (NormalBBIsDead)
2518 ToBeChangedToUnreachableInsts.insert(X: NormalNextIP);
2519 } else {
2520 assert(NormalBBIsDead && "Broken invariant!");
2521 if (!NormalDestBB->getUniquePredecessor())
2522 NormalDestBB = SplitBlockPredecessors(BB: NormalDestBB, Preds: {BB}, Suffix: ".dead");
2523 ToBeChangedToUnreachableInsts.insert(X: &NormalDestBB->front());
2524 }
2525 }
2526 for (Instruction *I : TerminatorsToFold) {
2527 assert(isRunOn(*I->getFunction()) &&
2528 "Cannot replace a terminator outside the current SCC!");
2529 CGModifiedFunctions.insert(X: I->getFunction());
2530 ConstantFoldTerminator(BB: I->getParent());
2531 }
2532 for (const auto &V : ToBeChangedToUnreachableInsts)
2533 if (Instruction *I = dyn_cast_or_null<Instruction>(Val: V)) {
2534 LLVM_DEBUG(dbgs() << "[Attributor] Change to unreachable: " << *I
2535 << "\n");
2536 assert(isRunOn(*I->getFunction()) &&
2537 "Cannot replace an instruction outside the current SCC!");
2538 CGModifiedFunctions.insert(X: I->getFunction());
2539 changeToUnreachable(I);
2540 }
2541
2542 for (const auto &V : ToBeDeletedInsts) {
2543 if (Instruction *I = dyn_cast_or_null<Instruction>(Val: V)) {
2544 assert((!isa<CallBase>(I) || isa<IntrinsicInst>(I) ||
2545 isRunOn(*I->getFunction())) &&
2546 "Cannot delete an instruction outside the current SCC!");
2547 I->dropDroppableUses();
2548 CGModifiedFunctions.insert(X: I->getFunction());
2549 if (!I->getType()->isVoidTy())
2550 I->replaceAllUsesWith(V: UndefValue::get(T: I->getType()));
2551 if (!isa<PHINode>(Val: I) && isInstructionTriviallyDead(I))
2552 DeadInsts.push_back(Elt: I);
2553 else
2554 I->eraseFromParent();
2555 }
2556 }
2557
2558 llvm::erase_if(C&: DeadInsts, P: [&](WeakTrackingVH I) { return !I; });
2559
2560 LLVM_DEBUG({
2561 dbgs() << "[Attributor] DeadInsts size: " << DeadInsts.size() << "\n";
2562 for (auto &I : DeadInsts)
2563 if (I)
2564 dbgs() << " - " << *I << "\n";
2565 });
2566
2567 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
2568
2569 if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) {
2570 SmallVector<BasicBlock *, 8> ToBeDeletedBBs;
2571 ToBeDeletedBBs.reserve(N: NumDeadBlocks);
2572 for (BasicBlock *BB : ToBeDeletedBlocks) {
2573 assert(isRunOn(*BB->getParent()) &&
2574 "Cannot delete a block outside the current SCC!");
2575 CGModifiedFunctions.insert(X: BB->getParent());
2576 // Do not delete BBs added during manifests of AAs.
2577 if (ManifestAddedBlocks.contains(Ptr: BB))
2578 continue;
2579 ToBeDeletedBBs.push_back(Elt: BB);
2580 }
2581 // Actually we do not delete the blocks but squash them into a single
2582 // unreachable but untangling branches that jump here is something we need
2583 // to do in a more generic way.
2584 detachDeadBlocks(BBs: ToBeDeletedBBs, Updates: nullptr);
2585 }
2586
2587 identifyDeadInternalFunctions();
2588
2589 // Rewrite the functions as requested during manifest.
2590 ChangeStatus ManifestChange = rewriteFunctionSignatures(ModifiedFns&: CGModifiedFunctions);
2591
2592 for (Function *Fn : CGModifiedFunctions)
2593 if (!ToBeDeletedFunctions.count(key: Fn) && Functions.count(key: Fn))
2594 Configuration.CGUpdater.reanalyzeFunction(Fn&: *Fn);
2595
2596 for (Function *Fn : ToBeDeletedFunctions) {
2597 if (!Functions.count(key: Fn))
2598 continue;
2599 Configuration.CGUpdater.removeFunction(Fn&: *Fn);
2600 }
2601
2602 if (!ToBeChangedUses.empty())
2603 ManifestChange = ChangeStatus::CHANGED;
2604
2605 if (!ToBeChangedToUnreachableInsts.empty())
2606 ManifestChange = ChangeStatus::CHANGED;
2607
2608 if (!ToBeDeletedFunctions.empty())
2609 ManifestChange = ChangeStatus::CHANGED;
2610
2611 if (!ToBeDeletedBlocks.empty())
2612 ManifestChange = ChangeStatus::CHANGED;
2613
2614 if (!ToBeDeletedInsts.empty())
2615 ManifestChange = ChangeStatus::CHANGED;
2616
2617 if (!InvokeWithDeadSuccessor.empty())
2618 ManifestChange = ChangeStatus::CHANGED;
2619
2620 if (!DeadInsts.empty())
2621 ManifestChange = ChangeStatus::CHANGED;
2622
2623 NumFnDeleted += ToBeDeletedFunctions.size();
2624
2625 LLVM_DEBUG(dbgs() << "[Attributor] Deleted " << ToBeDeletedFunctions.size()
2626 << " functions after manifest.\n");
2627
2628#ifdef EXPENSIVE_CHECKS
2629 for (Function *F : Functions) {
2630 if (ToBeDeletedFunctions.count(F))
2631 continue;
2632 assert(!verifyFunction(*F, &errs()) && "Module verification failed!");
2633 }
2634#endif
2635
2636 return ManifestChange;
2637}
2638
2639ChangeStatus Attributor::run() {
2640 TimeTraceScope TimeScope("Attributor::run");
2641 AttributorCallGraph ACallGraph(*this);
2642
2643 if (Opts.attributor_print_call_graph)
2644 ACallGraph.populateAll();
2645
2646 Phase = AttributorPhase::UPDATE;
2647 runTillFixpoint();
2648
2649 // dump graphs on demand
2650 if (Opts.attributor_dump_dep_graph)
2651 DG.dumpGraph(DotFileNamePrefix: Opts.attributor_depgraph_dot_filename_prefix);
2652
2653 if (Opts.attributor_view_dep_graph)
2654 DG.viewGraph();
2655
2656 if (Opts.attributor_print_dep)
2657 DG.print();
2658
2659 Phase = AttributorPhase::MANIFEST;
2660 ChangeStatus ManifestChange = manifestAttributes();
2661
2662 Phase = AttributorPhase::CLEANUP;
2663 ChangeStatus CleanupChange = cleanupIR();
2664
2665 if (Opts.attributor_print_call_graph)
2666 ACallGraph.print();
2667
2668 return ManifestChange | CleanupChange;
2669}
2670
2671ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
2672 std::optional<TimeTraceScope> TimeScope;
2673 if (TimeTraceEnabled) {
2674 TimeScope.emplace(args: "updateAA", args: [&]() {
2675 return AA.getName().str() +
2676 std::to_string(val: AA.getIRPosition().getPositionKind());
2677 });
2678 }
2679
2680 assert(Phase == AttributorPhase::UPDATE &&
2681 "We can update AA only in the update stage!");
2682
2683 // Use a new dependence vector for this update.
2684 DependenceVector DV;
2685 DependenceStack.push_back(Elt: &DV);
2686
2687 auto &AAState = AA.getState();
2688 ChangeStatus CS = ChangeStatus::UNCHANGED;
2689 bool UsedAssumedInformation = false;
2690 if (!isAssumedDead(AA, FnLivenessAA: nullptr, UsedAssumedInformation,
2691 /* CheckBBLivenessOnly */ true))
2692 CS = AA.update(A&: *this);
2693
2694 if (!AA.isQueryAA() && DV.empty() && !AA.isStateAtFixpoint()) {
2695 // If the AA did not rely on outside information but changed, we run it
2696 // again to see if it found a fixpoint. Most AAs do but we don't require
2697 // them to. Hence, it might take the AA multiple iterations to get to a
2698 // fixpoint even if it does not rely on outside information, which is fine.
2699 ChangeStatus RerunCS = ChangeStatus::UNCHANGED;
2700 if (CS == ChangeStatus::CHANGED)
2701 RerunCS = AA.update(A&: *this);
2702
2703 // If the attribute did not change during the run or rerun, and it still did
2704 // not query any non-fix information, the state will not change and we can
2705 // indicate that right at this point.
2706 if (RerunCS == ChangeStatus::UNCHANGED && !AA.isQueryAA() && DV.empty())
2707 AAState.indicateOptimisticFixpoint();
2708 }
2709
2710 if (!AA.isStateAtFixpoint())
2711 rememberDependences();
2712
2713 // Verify the stack was used properly, that is we pop the dependence vector we
2714 // put there earlier.
2715 DependenceVector *PoppedDV = DependenceStack.pop_back_val();
2716 (void)PoppedDV;
2717 assert(PoppedDV == &DV && "Inconsistent usage of the dependence stack!");
2718
2719 return CS;
2720}
2721
2722void Attributor::createShallowWrapper(Function &F) {
2723 assert(!F.isDeclaration() && "Cannot create a wrapper around a declaration!");
2724
2725 Module &M = *F.getParent();
2726 LLVMContext &Ctx = M.getContext();
2727 FunctionType *FnTy = F.getFunctionType();
2728
2729 Function *Wrapper =
2730 Function::Create(Ty: FnTy, Linkage: F.getLinkage(), AddrSpace: F.getAddressSpace(), N: F.getName());
2731 F.setName(""); // set the inside function anonymous
2732 M.getFunctionList().insert(where: F.getIterator(), New: Wrapper);
2733
2734 F.setLinkage(GlobalValue::InternalLinkage);
2735
2736 F.replaceAllUsesWith(V: Wrapper);
2737 assert(F.use_empty() && "Uses remained after wrapper was created!");
2738
2739 // Move the COMDAT section to the wrapper.
2740 // TODO: Check if we need to keep it for F as well.
2741 Wrapper->setComdat(F.getComdat());
2742 F.setComdat(nullptr);
2743
2744 // Copy all metadata and attributes but keep them on F as well.
2745 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
2746 F.getAllMetadata(MDs);
2747 for (auto MDIt : MDs)
2748 Wrapper->addMetadata(KindID: MDIt.first, MD&: *MDIt.second);
2749 Wrapper->setAttributes(F.getAttributes());
2750
2751 // Create the call in the wrapper.
2752 BasicBlock *EntryBB = BasicBlock::Create(Context&: Ctx, Name: "entry", Parent: Wrapper);
2753
2754 SmallVector<Value *, 8> Args;
2755 Argument *FArgIt = F.arg_begin();
2756 for (Argument &Arg : Wrapper->args()) {
2757 Args.push_back(Elt: &Arg);
2758 Arg.setName((FArgIt++)->getName());
2759 }
2760
2761 CallInst *CI = CallInst::Create(Func: &F, Args, NameStr: "", InsertBefore: EntryBB);
2762 CI->setTailCall(true);
2763 CI->addFnAttr(Kind: Attribute::NoInline);
2764 ReturnInst::Create(C&: Ctx, retVal: CI->getType()->isVoidTy() ? nullptr : CI, InsertBefore: EntryBB);
2765
2766 NumFnShallowWrappersCreated++;
2767}
2768
2769bool Attributor::isInternalizable(Function &F) {
2770 if (F.isDeclaration() || F.hasLocalLinkage() ||
2771 GlobalValue::isInterposableLinkage(Linkage: F.getLinkage()))
2772 return false;
2773 return true;
2774}
2775
2776Function *Attributor::internalizeFunction(Function &F, bool Force) {
2777 if (!getIPOOptions(F).attributor_allow_deep_wrappers && !Force)
2778 return nullptr;
2779 if (!isInternalizable(F))
2780 return nullptr;
2781
2782 SmallPtrSet<Function *, 2> FnSet = {&F};
2783 DenseMap<Function *, Function *> InternalizedFns;
2784 internalizeFunctions(FnSet, FnMap&: InternalizedFns);
2785
2786 return InternalizedFns[&F];
2787}
2788
2789bool Attributor::internalizeFunctions(SmallPtrSetImpl<Function *> &FnSet,
2790 DenseMap<Function *, Function *> &FnMap) {
2791 for (Function *F : FnSet)
2792 if (!Attributor::isInternalizable(F&: *F))
2793 return false;
2794
2795 FnMap.clear();
2796 // Generate the internalized version of each function.
2797 for (Function *F : FnSet) {
2798 Module &M = *F->getParent();
2799 FunctionType *FnTy = F->getFunctionType();
2800
2801 // Create a copy of the current function
2802 Function *Copied =
2803 Function::Create(Ty: FnTy, Linkage: F->getLinkage(), AddrSpace: F->getAddressSpace(),
2804 N: F->getName() + ".internalized");
2805 ValueToValueMapTy VMap;
2806 auto *NewFArgIt = Copied->arg_begin();
2807 for (auto &Arg : F->args()) {
2808 auto ArgName = Arg.getName();
2809 NewFArgIt->setName(ArgName);
2810 VMap[&Arg] = &(*NewFArgIt++);
2811 }
2812 SmallVector<ReturnInst *, 8> Returns;
2813
2814 // Copy the body of the original function to the new one
2815 CloneFunctionInto(NewFunc: Copied, OldFunc: F, VMap,
2816 Changes: CloneFunctionChangeType::LocalChangesOnly, Returns);
2817
2818 // Set the linakage and visibility late as CloneFunctionInto has some
2819 // implicit requirements.
2820 Copied->setVisibility(GlobalValue::DefaultVisibility);
2821 Copied->setLinkage(GlobalValue::PrivateLinkage);
2822
2823 // Copy metadata
2824 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
2825 F->getAllMetadata(MDs);
2826 for (auto MDIt : MDs)
2827 if (!Copied->hasMetadata())
2828 Copied->addMetadata(KindID: MDIt.first, MD&: *MDIt.second);
2829
2830 M.getFunctionList().insert(where: F->getIterator(), New: Copied);
2831 Copied->setDSOLocal(true);
2832 FnMap[F] = Copied;
2833 }
2834
2835 // Replace all uses of the old function with the new internalized function
2836 // unless the caller is a function that was just internalized.
2837 for (Function *F : FnSet) {
2838 auto &InternalizedFn = FnMap[F];
2839 auto IsNotInternalized = [&](Use &U) -> bool {
2840 if (auto *CB = dyn_cast<CallBase>(Val: U.getUser()))
2841 return !FnMap.lookup(Val: CB->getCaller());
2842 return false;
2843 };
2844 F->replaceUsesWithIf(New: InternalizedFn, ShouldReplace: IsNotInternalized);
2845 }
2846
2847 return true;
2848}
2849
2850bool Attributor::isValidFunctionSignatureRewrite(
2851 Argument &Arg, ArrayRef<Type *> ReplacementTypes) {
2852
2853 if (!Configuration.RewriteSignatures)
2854 return false;
2855
2856 Function *Fn = Arg.getParent();
2857 auto CallSiteCanBeChanged = [Fn](AbstractCallSite ACS) {
2858 // Forbid the call site to cast the function return type. If we need to
2859 // rewrite these functions we need to re-create a cast for the new call site
2860 // (if the old had uses).
2861 if (!ACS.getCalledFunction() ||
2862 ACS.getInstruction()->getType() !=
2863 ACS.getCalledFunction()->getReturnType())
2864 return false;
2865 if (cast<CallBase>(Val: ACS.getInstruction())->getCalledOperand()->getType() !=
2866 Fn->getType())
2867 return false;
2868 if (ACS.getNumArgOperands() != Fn->arg_size())
2869 return false;
2870 // Forbid must-tail calls for now.
2871 return !ACS.isCallbackCall() && !ACS.getInstruction()->isMustTailCall();
2872 };
2873
2874 // Avoid var-arg functions for now.
2875 if (Fn->isVarArg()) {
2876 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite var-args functions\n");
2877 return false;
2878 }
2879
2880 // Avoid functions with complicated argument passing semantics.
2881 AttributeList FnAttributeList = Fn->getAttributes();
2882 if (FnAttributeList.hasAttrSomewhere(Kind: Attribute::Nest) ||
2883 FnAttributeList.hasAttrSomewhere(Kind: Attribute::StructRet) ||
2884 FnAttributeList.hasAttrSomewhere(Kind: Attribute::InAlloca) ||
2885 FnAttributeList.hasAttrSomewhere(Kind: Attribute::Preallocated)) {
2886 LLVM_DEBUG(
2887 dbgs() << "[Attributor] Cannot rewrite due to complex attribute\n");
2888 return false;
2889 }
2890
2891 // Avoid callbacks for now.
2892 bool UsedAssumedInformation = false;
2893 if (!checkForAllCallSites(Pred: CallSiteCanBeChanged, Fn: *Fn, RequireAllCallSites: true, QueryingAA: nullptr,
2894 UsedAssumedInformation,
2895 /* CheckPotentiallyDead */ true)) {
2896 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite all call sites\n");
2897 return false;
2898 }
2899
2900 auto InstPred = [](Instruction &I) {
2901 if (auto *CI = dyn_cast<CallInst>(Val: &I))
2902 return !CI->isMustTailCall();
2903 return true;
2904 };
2905
2906 // Forbid must-tail calls for now.
2907 // TODO:
2908 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F: *Fn);
2909 if (!checkForAllInstructionsImpl(A: nullptr, OpcodeInstMap, Pred: InstPred, QueryingAA: nullptr,
2910 LivenessAA: nullptr, Opcodes: {Instruction::Call},
2911 UsedAssumedInformation)) {
2912 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite due to instructions\n");
2913 return false;
2914 }
2915
2916 return true;
2917}
2918
2919bool Attributor::registerFunctionSignatureRewrite(
2920 Argument &Arg, ArrayRef<Type *> ReplacementTypes,
2921 ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB,
2922 ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB) {
2923 LLVM_DEBUG(dbgs() << "[Attributor] Register new rewrite of " << Arg << " in "
2924 << Arg.getParent()->getName() << " with "
2925 << ReplacementTypes.size() << " replacements\n");
2926 assert(isValidFunctionSignatureRewrite(Arg, ReplacementTypes) &&
2927 "Cannot register an invalid rewrite");
2928
2929 Function *Fn = Arg.getParent();
2930 SmallVectorImpl<std::unique_ptr<ArgumentReplacementInfo>> &ARIs =
2931 ArgumentReplacementMap[Fn];
2932 if (ARIs.empty())
2933 ARIs.resize(N: Fn->arg_size());
2934
2935 // If we have a replacement already with less than or equal new arguments,
2936 // ignore this request.
2937 std::unique_ptr<ArgumentReplacementInfo> &ARI = ARIs[Arg.getArgNo()];
2938 if (ARI && ARI->getNumReplacementArgs() <= ReplacementTypes.size()) {
2939 LLVM_DEBUG(dbgs() << "[Attributor] Existing rewrite is preferred\n");
2940 return false;
2941 }
2942
2943 // If we have a replacement already but we like the new one better, delete
2944 // the old.
2945 ARI.reset();
2946
2947 LLVM_DEBUG(dbgs() << "[Attributor] Register new rewrite of " << Arg << " in "
2948 << Arg.getParent()->getName() << " with "
2949 << ReplacementTypes.size() << " replacements\n");
2950
2951 // Remember the replacement.
2952 ARI.reset(p: new ArgumentReplacementInfo(*this, Arg, ReplacementTypes,
2953 std::move(CalleeRepairCB),
2954 std::move(ACSRepairCB)));
2955
2956 return true;
2957}
2958
2959bool Attributor::shouldSeedAttribute(AbstractAttribute &AA) {
2960 bool Result = true;
2961#ifndef NDEBUG
2962 if (Opts.attributor_seed_allow_list.size() != 0)
2963 Result = llvm::is_contained(Opts.attributor_seed_allow_list, AA.getName());
2964 Function *Fn = AA.getAnchorScope();
2965 if (Opts.attributor_function_seed_allow_list.size() != 0 && Fn)
2966 Result &= llvm::is_contained(Opts.attributor_function_seed_allow_list,
2967 Fn->getName());
2968#endif
2969 return Result;
2970}
2971
2972ChangeStatus Attributor::rewriteFunctionSignatures(
2973 SmallSetVector<Function *, 8> &ModifiedFns) {
2974 ChangeStatus Changed = ChangeStatus::UNCHANGED;
2975
2976 for (auto &It : ArgumentReplacementMap) {
2977 Function *OldFn = It.first;
2978
2979 // Deleted functions do not require rewrites.
2980 if (!Functions.count(key: OldFn) || ToBeDeletedFunctions.count(key: OldFn))
2981 continue;
2982
2983 const SmallVectorImpl<std::unique_ptr<ArgumentReplacementInfo>> &ARIs =
2984 It.second;
2985 assert(ARIs.size() == OldFn->arg_size() && "Inconsistent state!");
2986
2987 SmallVector<Type *, 16> NewArgumentTypes;
2988 SmallVector<AttributeSet, 16> NewArgumentAttributes;
2989
2990 // Collect replacement argument types and copy over existing attributes.
2991 AttributeList OldFnAttributeList = OldFn->getAttributes();
2992 for (Argument &Arg : OldFn->args()) {
2993 if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
2994 ARIs[Arg.getArgNo()]) {
2995 NewArgumentTypes.append(in_start: ARI->ReplacementTypes.begin(),
2996 in_end: ARI->ReplacementTypes.end());
2997 NewArgumentAttributes.append(NumInputs: ARI->getNumReplacementArgs(),
2998 Elt: AttributeSet());
2999 } else {
3000 NewArgumentTypes.push_back(Elt: Arg.getType());
3001 NewArgumentAttributes.push_back(
3002 Elt: OldFnAttributeList.getParamAttrs(ArgNo: Arg.getArgNo()));
3003 }
3004 }
3005
3006 uint64_t LargestVectorWidth = 0;
3007 for (auto *I : NewArgumentTypes)
3008 if (auto *VT = dyn_cast<llvm::VectorType>(Val: I))
3009 LargestVectorWidth =
3010 std::max(a: LargestVectorWidth,
3011 b: VT->getPrimitiveSizeInBits().getKnownMinValue());
3012
3013 FunctionType *OldFnTy = OldFn->getFunctionType();
3014 Type *RetTy = OldFnTy->getReturnType();
3015
3016 // Construct the new function type using the new arguments types.
3017 FunctionType *NewFnTy =
3018 FunctionType::get(Result: RetTy, Params: NewArgumentTypes, isVarArg: OldFnTy->isVarArg());
3019
3020 LLVM_DEBUG(dbgs() << "[Attributor] Function rewrite '" << OldFn->getName()
3021 << "' from " << *OldFn->getFunctionType() << " to "
3022 << *NewFnTy << "\n");
3023
3024 // Create the new function body and insert it into the module.
3025 Function *NewFn = Function::Create(Ty: NewFnTy, Linkage: OldFn->getLinkage(),
3026 AddrSpace: OldFn->getAddressSpace(), N: "");
3027 Functions.insert(X: NewFn);
3028 OldFn->getParent()->getFunctionList().insert(where: OldFn->getIterator(), New: NewFn);
3029 NewFn->takeName(V: OldFn);
3030 NewFn->copyAttributesFrom(Src: OldFn);
3031
3032 // Patch the pointer to LLVM function in debug info descriptor.
3033 NewFn->setSubprogram(OldFn->getSubprogram());
3034 OldFn->setSubprogram(nullptr);
3035
3036 // Recompute the parameter attributes list based on the new arguments for
3037 // the function.
3038 LLVMContext &Ctx = OldFn->getContext();
3039 NewFn->setAttributes(AttributeList::get(
3040 C&: Ctx, FnAttrs: OldFnAttributeList.getFnAttrs(), RetAttrs: OldFnAttributeList.getRetAttrs(),
3041 ArgAttrs: NewArgumentAttributes));
3042 AttributeFuncs::updateMinLegalVectorWidthAttr(Fn&: *NewFn, Width: LargestVectorWidth);
3043
3044 // Remove argmem from the memory effects if we have no more pointer
3045 // arguments, or they are readnone.
3046 MemoryEffects ME = NewFn->getMemoryEffects();
3047 int ArgNo = -1;
3048 if (ME.doesAccessArgPointees() && all_of(Range&: NewArgumentTypes, P: [&](Type *T) {
3049 ++ArgNo;
3050 return !T->isPtrOrPtrVectorTy() ||
3051 NewFn->hasParamAttribute(ArgNo, Kind: Attribute::ReadNone);
3052 })) {
3053 NewFn->setMemoryEffects(ME - MemoryEffects::argMemOnly());
3054 }
3055
3056 // Since we have now created the new function, splice the body of the old
3057 // function right into the new function, leaving the old rotting hulk of the
3058 // function empty.
3059 NewFn->splice(ToIt: NewFn->begin(), FromF: OldFn);
3060
3061 // Set of all "call-like" instructions that invoke the old function mapped
3062 // to their new replacements.
3063 SmallVector<std::pair<CallBase *, CallBase *>, 8> CallSitePairs;
3064
3065 // Callback to create a new "call-like" instruction for a given one.
3066 auto CallSiteReplacementCreator = [&](AbstractCallSite ACS) {
3067 CallBase *OldCB = cast<CallBase>(Val: ACS.getInstruction());
3068 const AttributeList &OldCallAttributeList = OldCB->getAttributes();
3069
3070 // Collect the new argument operands for the replacement call site.
3071 SmallVector<Value *, 16> NewArgOperands;
3072 SmallVector<AttributeSet, 16> NewArgOperandAttributes;
3073 for (unsigned OldArgNum = 0; OldArgNum < ARIs.size(); ++OldArgNum) {
3074 unsigned NewFirstArgNum = NewArgOperands.size();
3075 (void)NewFirstArgNum; // only used inside assert.
3076 if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
3077 ARIs[OldArgNum]) {
3078 if (ARI->ACSRepairCB)
3079 ARI->ACSRepairCB(*ARI, ACS, NewArgOperands);
3080 assert(ARI->getNumReplacementArgs() + NewFirstArgNum ==
3081 NewArgOperands.size() &&
3082 "ACS repair callback did not provide as many operand as new "
3083 "types were registered!");
3084 // TODO: Exose the attribute set to the ACS repair callback
3085 NewArgOperandAttributes.append(NumInputs: ARI->ReplacementTypes.size(),
3086 Elt: AttributeSet());
3087 } else {
3088 NewArgOperands.push_back(Elt: ACS.getCallArgOperand(ArgNo: OldArgNum));
3089 NewArgOperandAttributes.push_back(
3090 Elt: OldCallAttributeList.getParamAttrs(ArgNo: OldArgNum));
3091 }
3092 }
3093
3094 assert(NewArgOperands.size() == NewArgOperandAttributes.size() &&
3095 "Mismatch # argument operands vs. # argument operand attributes!");
3096 assert(NewArgOperands.size() == NewFn->arg_size() &&
3097 "Mismatch # argument operands vs. # function arguments!");
3098
3099 SmallVector<OperandBundleDef, 4> OperandBundleDefs;
3100 OldCB->getOperandBundlesAsDefs(Defs&: OperandBundleDefs);
3101
3102 // Create a new call or invoke instruction to replace the old one.
3103 CallBase *NewCB;
3104 if (InvokeInst *II = dyn_cast<InvokeInst>(Val: OldCB)) {
3105 NewCB = InvokeInst::Create(Func: NewFn, IfNormal: II->getNormalDest(),
3106 IfException: II->getUnwindDest(), Args: NewArgOperands,
3107 Bundles: OperandBundleDefs, NameStr: "", InsertBefore: OldCB->getIterator());
3108 } else {
3109 auto *NewCI = CallInst::Create(Func: NewFn, Args: NewArgOperands, Bundles: OperandBundleDefs,
3110 NameStr: "", InsertBefore: OldCB->getIterator());
3111 NewCI->setTailCallKind(cast<CallInst>(Val: OldCB)->getTailCallKind());
3112 NewCB = NewCI;
3113 }
3114
3115 // Copy over various properties and the new attributes.
3116 NewCB->copyProfileAndDebugMetadata(SrcInst: *OldCB);
3117 NewCB->setCallingConv(OldCB->getCallingConv());
3118 NewCB->takeName(V: OldCB);
3119 NewCB->setAttributes(AttributeList::get(
3120 C&: Ctx, FnAttrs: OldCallAttributeList.getFnAttrs(),
3121 RetAttrs: OldCallAttributeList.getRetAttrs(), ArgAttrs: NewArgOperandAttributes));
3122
3123 AttributeFuncs::updateMinLegalVectorWidthAttr(Fn&: *NewCB->getCaller(),
3124 Width: LargestVectorWidth);
3125
3126 CallSitePairs.push_back(Elt: {OldCB, NewCB});
3127 return true;
3128 };
3129
3130 // Use the CallSiteReplacementCreator to create replacement call sites.
3131 bool UsedAssumedInformation = false;
3132 bool Success = checkForAllCallSites(Pred: CallSiteReplacementCreator, Fn: *OldFn,
3133 RequireAllCallSites: true, QueryingAA: nullptr, UsedAssumedInformation,
3134 /* CheckPotentiallyDead */ true);
3135 (void)Success;
3136 assert(Success && "Assumed call site replacement to succeed!");
3137
3138 // Rewire the arguments.
3139 Argument *OldFnArgIt = OldFn->arg_begin();
3140 Argument *NewFnArgIt = NewFn->arg_begin();
3141 for (unsigned OldArgNum = 0; OldArgNum < ARIs.size();
3142 ++OldArgNum, ++OldFnArgIt) {
3143 if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
3144 ARIs[OldArgNum]) {
3145 if (ARI->CalleeRepairCB)
3146 ARI->CalleeRepairCB(*ARI, *NewFn, NewFnArgIt);
3147 if (ARI->ReplacementTypes.empty())
3148 OldFnArgIt->replaceAllUsesWith(
3149 V: PoisonValue::get(T: OldFnArgIt->getType()));
3150 NewFnArgIt += ARI->ReplacementTypes.size();
3151 } else {
3152 NewFnArgIt->takeName(V: &*OldFnArgIt);
3153 OldFnArgIt->replaceAllUsesWith(V: &*NewFnArgIt);
3154 ++NewFnArgIt;
3155 }
3156 }
3157
3158 // Eliminate the instructions *after* we visited all of them.
3159 for (auto &CallSitePair : CallSitePairs) {
3160 CallBase &OldCB = *CallSitePair.first;
3161 CallBase &NewCB = *CallSitePair.second;
3162 assert(OldCB.getType() == NewCB.getType() &&
3163 "Cannot handle call sites with different types!");
3164 ModifiedFns.insert(X: OldCB.getFunction());
3165 OldCB.replaceAllUsesWith(V: &NewCB);
3166 OldCB.eraseFromParent();
3167 }
3168
3169 // Replace the function in the call graph (if any).
3170 Configuration.CGUpdater.replaceFunctionWith(OldFn&: *OldFn, NewFn&: *NewFn);
3171
3172 // If the old function was modified and needed to be reanalyzed, the new one
3173 // does now.
3174 if (ModifiedFns.remove(X: OldFn))
3175 ModifiedFns.insert(X: NewFn);
3176
3177 Changed = ChangeStatus::CHANGED;
3178 }
3179
3180 return Changed;
3181}
3182
3183/// The opcodes of the instructions recorded in FunctionInfo::OpcodeInstMap.
3184static constexpr unsigned InterestingOpcodes[] = {
3185 Instruction::Call, Instruction::CallBr,
3186 Instruction::Invoke, Instruction::CleanupRet,
3187 Instruction::CatchSwitch, Instruction::AtomicRMW,
3188 Instruction::AtomicCmpXchg, Instruction::UncondBr,
3189 Instruction::CondBr, Instruction::Resume,
3190 Instruction::Ret, Instruction::Load,
3191 Instruction::Store, Instruction::Alloca,
3192 Instruction::AddrSpaceCast,
3193};
3194
3195void InformationCache::initializeInformationCache(const Function &CF,
3196 FunctionInfo &FI) {
3197 // As we do not modify the function here we can remove the const
3198 // withouth breaking implicit assumptions. At the end of the day, we could
3199 // initialize the cache eagerly which would look the same to the users.
3200 Function &F = const_cast<Function &>(CF);
3201
3202 FI.IsKernel = F.hasFnAttribute(Kind: "kernel");
3203
3204 // Walk all instructions to find interesting instructions that might be
3205 // queried by abstract attributes during their initialization or update.
3206 // This has to happen before we create attributes.
3207
3208 for (Instruction &I : instructions(F: &F)) {
3209 bool IsInterestingOpcode = false;
3210
3211 // To allow easy access to all instructions in a function with a given
3212 // opcode we store them in the InfoCache. As not all opcodes are interesting
3213 // to concrete attributes we only cache the ones that are as identified in
3214 // the following switch.
3215 // Note: There are no concrete attributes now so this is initially empty.
3216 switch (I.getOpcode()) {
3217 default:
3218 assert(!isa<CallBase>(&I) &&
3219 "New call base instruction type needs to be known in the "
3220 "Attributor.");
3221 break;
3222 case Instruction::Call:
3223 // Calls are interesting on their own, additionally:
3224 // For `llvm.assume` calls we also fill the KnowledgeMap as we find them.
3225 // For `must-tail` calls we remember the caller and callee.
3226 if (auto *Assume = dyn_cast<AssumeInst>(Val: &I)) {
3227 fillMapFromAssume(Assume&: *Assume, Result&: KnowledgeMap);
3228 } else if (cast<CallInst>(Val&: I).isMustTailCall()) {
3229 FI.ContainsMustTailCall = true;
3230 if (auto *Callee = dyn_cast_if_present<Function>(
3231 Val: cast<CallInst>(Val&: I).getCalledOperand()))
3232 getFunctionInfo(F: *Callee).CalledViaMustTail = true;
3233 }
3234 [[fallthrough]];
3235 case Instruction::CallBr:
3236 case Instruction::Invoke:
3237 case Instruction::CleanupRet:
3238 case Instruction::CatchSwitch:
3239 case Instruction::AtomicRMW:
3240 case Instruction::AtomicCmpXchg:
3241 case Instruction::UncondBr:
3242 case Instruction::CondBr:
3243 case Instruction::Resume:
3244 case Instruction::Ret:
3245 case Instruction::Load:
3246 // The alignment of a pointer is interesting for loads.
3247 case Instruction::Store:
3248 // The alignment of a pointer is interesting for stores.
3249 case Instruction::Alloca:
3250 case Instruction::AddrSpaceCast:
3251 IsInterestingOpcode = true;
3252 }
3253 if (IsInterestingOpcode) {
3254 assert(is_contained(InterestingOpcodes, I.getOpcode()) &&
3255 "Interesting opcode missing from InterestingOpcodes");
3256 auto *&Insts = FI.OpcodeInstMap[I.getOpcode()];
3257 if (!Insts)
3258 Insts = new (Allocator) InstructionVectorTy();
3259 Insts->push_back(Elt: &I);
3260 }
3261 if (I.mayReadOrWriteMemory())
3262 FI.RWInsts.push_back(Elt: &I);
3263 }
3264
3265 bool IsInlineable = F.hasFnAttribute(Kind: Attribute::AlwaysInline) &&
3266 isInlineViable(Callee&: F).isSuccess();
3267 if (IsInlineable)
3268 InlineableFunctions.insert(Ptr: &F);
3269 FI.IsExactOrInlineable = IsInlineable || F.hasExactDefinition();
3270}
3271
3272void InformationCache::collectAssumeOnlyValues(FunctionInfo &FI) {
3273 FI.AssumeOnlyValuesCollected = true;
3274 InstructionVectorTy *Calls = FI.OpcodeInstMap[Instruction::Call];
3275 if (!Calls)
3276 return;
3277
3278 DenseMap<const Value *, std::optional<short>> AssumeUsesMap;
3279
3280 // Add \p V to the assume uses map which track the number of uses outside of
3281 // "visited" assumes. If no outside uses are left the value is added to the
3282 // assume only use vector.
3283 auto AddToAssumeUsesMap = [&](const Value &V) -> void {
3284 SmallVector<const Instruction *> Worklist;
3285 if (auto *I = dyn_cast<Instruction>(Val: &V))
3286 Worklist.push_back(Elt: I);
3287 while (!Worklist.empty()) {
3288 const Instruction *I = Worklist.pop_back_val();
3289 std::optional<short> &NumUses = AssumeUsesMap[I];
3290 if (!NumUses)
3291 NumUses = I->getNumUses();
3292 NumUses = *NumUses - /* this assume */ 1;
3293 if (*NumUses != 0)
3294 continue;
3295 AssumeOnlyValues.insert(X: I);
3296 for (const Instruction *OpI : make_isa_range<Instruction>(Range: I->operands()))
3297 Worklist.push_back(Elt: OpI);
3298 }
3299 };
3300
3301 for (AssumeInst *Assume : make_isa_range<AssumeInst>(Range&: *Calls)) {
3302 AssumeOnlyValues.insert(X: Assume);
3303 AddToAssumeUsesMap(*Assume->getArgOperand(i: 0));
3304 }
3305}
3306
3307InformationCache::FunctionInfo::~FunctionInfo() {
3308 // The instruction vectors are allocated using a BumpPtrAllocator, we need to
3309 // manually destroy them.
3310 for (unsigned Opcode : InterestingOpcodes) {
3311 if (InstructionVectorTy *Insts = OpcodeInstMap[Opcode])
3312 Insts->~InstructionVectorTy();
3313 }
3314}
3315
3316ArrayRef<Function *>
3317InformationCache::getIndirectlyCallableFunctions(Attributor &A) const {
3318 assert(A.isClosedWorldModule() && "Cannot see all indirect callees!");
3319 return IndirectlyCallableFunctions;
3320}
3321
3322std::optional<unsigned> InformationCache::getFlatAddressSpace() const {
3323 if (IsTargetGPU())
3324 return 0;
3325 return std::nullopt;
3326}
3327
3328void Attributor::recordDependence(const AbstractAttribute &FromAA,
3329 const AbstractAttribute &ToAA,
3330 DepClassTy DepClass) {
3331 if (DepClass == DepClassTy::NONE)
3332 return;
3333 // If we are outside of an update, thus before the actual fixpoint iteration
3334 // started (= when we create AAs), we do not track dependences because we will
3335 // put all AAs into the initial worklist anyway.
3336 if (DependenceStack.empty())
3337 return;
3338 if (FromAA.isStateAtFixpoint())
3339 return;
3340 DependenceStack.back()->push_back(Elt: {.FromAA: &FromAA, .ToAA: &ToAA, .DepClass: DepClass});
3341}
3342
3343void Attributor::rememberDependences() {
3344 assert(!DependenceStack.empty() && "No dependences to remember!");
3345
3346 for (DepInfo &DI : *DependenceStack.back()) {
3347 assert((DI.DepClass == DepClassTy::REQUIRED ||
3348 DI.DepClass == DepClassTy::OPTIONAL) &&
3349 "Expected required or optional dependence (1 bit)!");
3350 auto &DepAAs = const_cast<AbstractAttribute &>(*DI.FromAA).Deps;
3351 DepAAs.insert(X: AbstractAttribute::DepTy(
3352 const_cast<AbstractAttribute *>(DI.ToAA), unsigned(DI.DepClass)));
3353 }
3354}
3355
3356template <Attribute::AttrKind AK, typename AAType>
3357void Attributor::checkAndQueryIRAttr(const IRPosition &IRP, AttributeSet Attrs,
3358 bool SkipHasAttrCheck) {
3359 bool IsKnown;
3360 if (SkipHasAttrCheck || !Attrs.hasAttribute(Kind: AK))
3361 if (!Configuration.Allowed || Configuration.Allowed->contains<AAType>())
3362 if (!AA::hasAssumedIRAttr<AK>(*this, nullptr, IRP, DepClassTy::NONE,
3363 IsKnown))
3364 getOrCreateAAFor<AAType>(IRP);
3365}
3366
3367void Attributor::identifyDefaultAbstractAttributes(Function &F) {
3368 assert(!F.isDeclaration());
3369
3370 if (!VisitedFunctions.insert(V: &F).second)
3371 return;
3372
3373 // In non-module runs we need to look at the call sites of a function to
3374 // determine if it is part of a must-tail call edge. This will influence what
3375 // attributes we can derive.
3376 InformationCache::FunctionInfo &FI = InfoCache.getFunctionInfo(F);
3377 if (!isModulePass() && !FI.CalledViaMustTail) {
3378 for (const Use &U : F.uses())
3379 if (const auto *CB = dyn_cast<CallBase>(Val: U.getUser()))
3380 if (CB->isCallee(U: &U) && CB->isMustTailCall())
3381 FI.CalledViaMustTail = true;
3382 }
3383
3384 IRPosition FPos = IRPosition::function(F);
3385 bool IsIPOAmendable = isFunctionIPOAmendable(F);
3386 auto Attrs = F.getAttributes();
3387 auto FnAttrs = Attrs.getFnAttrs();
3388
3389 // Check for dead BasicBlocks in every function.
3390 // We need dead instruction detection because we do not want to deal with
3391 // broken IR in which SSA rules do not apply.
3392 getOrCreateAAFor<AAIsDead>(IRP: FPos);
3393
3394 // Every function might contain instructions that cause "undefined
3395 // behavior".
3396 getOrCreateAAFor<AAUndefinedBehavior>(IRP: FPos);
3397
3398 // Every function might be applicable for Heap-To-Stack conversion.
3399 if (Opts.enable_heap_to_stack_conversion)
3400 getOrCreateAAFor<AAHeapToStack>(IRP: FPos);
3401
3402 // Every function might be "must-progress".
3403 checkAndQueryIRAttr<Attribute::MustProgress, AAMustProgress>(IRP: FPos, Attrs: FnAttrs);
3404
3405 // Every function might be "no-free".
3406 checkAndQueryIRAttr<Attribute::NoFree, AANoFree>(IRP: FPos, Attrs: FnAttrs);
3407
3408 // Every function might be "will-return".
3409 checkAndQueryIRAttr<Attribute::WillReturn, AAWillReturn>(IRP: FPos, Attrs: FnAttrs);
3410
3411 // Every function might be marked "nosync"
3412 checkAndQueryIRAttr<Attribute::NoSync, AANoSync>(IRP: FPos, Attrs: FnAttrs);
3413
3414 // Everything that is visible from the outside (=function, argument, return
3415 // positions), cannot be changed if the function is not IPO amendable. We can
3416 // however analyse the code inside.
3417 if (IsIPOAmendable) {
3418
3419 // Every function can be nounwind.
3420 checkAndQueryIRAttr<Attribute::NoUnwind, AANoUnwind>(IRP: FPos, Attrs: FnAttrs);
3421
3422 // Every function might be "no-return".
3423 checkAndQueryIRAttr<Attribute::NoReturn, AANoReturn>(IRP: FPos, Attrs: FnAttrs);
3424
3425 // Every function might be "no-recurse".
3426 checkAndQueryIRAttr<Attribute::NoRecurse, AANoRecurse>(IRP: FPos, Attrs: FnAttrs);
3427
3428 // Every function can be "non-convergent".
3429 if (Attrs.hasFnAttr(Kind: Attribute::Convergent))
3430 getOrCreateAAFor<AANonConvergent>(IRP: FPos);
3431
3432 // Every function might be "readnone/readonly/writeonly/...".
3433 getOrCreateAAFor<AAMemoryBehavior>(IRP: FPos);
3434
3435 // Every function can be "readnone/argmemonly/inaccessiblememonly/...".
3436 getOrCreateAAFor<AAMemoryLocation>(IRP: FPos);
3437
3438 // Every function can track active assumptions.
3439 getOrCreateAAFor<AAAssumptionInfo>(IRP: FPos);
3440
3441 // If we're not using a dynamic mode for float, there's nothing worthwhile
3442 // to infer. This misses the edge case denormal-fp-math="dynamic" and
3443 // denormal-fp-math-f32=something, but that likely has no real world use.
3444 DenormalMode Mode = F.getDenormalMode(FPType: APFloat::IEEEsingle());
3445 if (Mode.Input == DenormalMode::Dynamic ||
3446 Mode.Output == DenormalMode::Dynamic)
3447 getOrCreateAAFor<AADenormalFPMath>(IRP: FPos);
3448
3449 // Return attributes are only appropriate if the return type is non void.
3450 Type *ReturnType = F.getReturnType();
3451 if (!ReturnType->isVoidTy()) {
3452 IRPosition RetPos = IRPosition::returned(F);
3453 AttributeSet RetAttrs = Attrs.getRetAttrs();
3454
3455 // Every returned value might be dead.
3456 getOrCreateAAFor<AAIsDead>(IRP: RetPos);
3457
3458 // Every function might be simplified.
3459 bool UsedAssumedInformation = false;
3460 getAssumedSimplified(IRP: RetPos, AA: nullptr, UsedAssumedInformation,
3461 S: AA::Intraprocedural);
3462
3463 // Every returned value might be marked noundef.
3464 checkAndQueryIRAttr<Attribute::NoUndef, AANoUndef>(IRP: RetPos, Attrs: RetAttrs);
3465
3466 if (ReturnType->isPointerTy()) {
3467
3468 // Every function with pointer return type might be marked align.
3469 getOrCreateAAFor<AAAlign>(IRP: RetPos);
3470
3471 // Every function with pointer return type might be marked nonnull.
3472 checkAndQueryIRAttr<Attribute::NonNull, AANonNull>(IRP: RetPos, Attrs: RetAttrs);
3473
3474 // Every function with pointer return type might be marked noalias.
3475 checkAndQueryIRAttr<Attribute::NoAlias, AANoAlias>(IRP: RetPos, Attrs: RetAttrs);
3476
3477 // Every function with pointer return type might be marked
3478 // dereferenceable.
3479 getOrCreateAAFor<AADereferenceable>(IRP: RetPos);
3480 } else if (AttributeFuncs::isNoFPClassCompatibleType(Ty: ReturnType)) {
3481 getOrCreateAAFor<AANoFPClass>(IRP: RetPos);
3482 }
3483 }
3484 }
3485
3486 for (Argument &Arg : F.args()) {
3487 IRPosition ArgPos = IRPosition::argument(Arg);
3488 auto ArgNo = Arg.getArgNo();
3489 AttributeSet ArgAttrs = Attrs.getParamAttrs(ArgNo);
3490
3491 if (!IsIPOAmendable) {
3492 if (Arg.getType()->isPointerTy())
3493 // Every argument with pointer type might be marked nofree.
3494 checkAndQueryIRAttr<Attribute::NoFree, AANoFree>(IRP: ArgPos, Attrs: ArgAttrs);
3495 continue;
3496 }
3497
3498 // Every argument might be simplified. We have to go through the
3499 // Attributor interface though as outside AAs can register custom
3500 // simplification callbacks.
3501 bool UsedAssumedInformation = false;
3502 getAssumedSimplified(IRP: ArgPos, /* AA */ nullptr, UsedAssumedInformation,
3503 S: AA::Intraprocedural);
3504
3505 // Every argument might be dead.
3506 getOrCreateAAFor<AAIsDead>(IRP: ArgPos);
3507
3508 // Every argument might be marked noundef.
3509 checkAndQueryIRAttr<Attribute::NoUndef, AANoUndef>(IRP: ArgPos, Attrs: ArgAttrs);
3510
3511 if (Arg.getType()->isPointerTy()) {
3512 // Every argument with pointer type might be marked nonnull.
3513 checkAndQueryIRAttr<Attribute::NonNull, AANonNull>(IRP: ArgPos, Attrs: ArgAttrs);
3514
3515 // Every argument with pointer type might be marked noalias.
3516 checkAndQueryIRAttr<Attribute::NoAlias, AANoAlias>(IRP: ArgPos, Attrs: ArgAttrs);
3517
3518 // Every argument with pointer type might be marked dereferenceable.
3519 getOrCreateAAFor<AADereferenceable>(IRP: ArgPos);
3520
3521 // Every argument with pointer type might be marked align.
3522 getOrCreateAAFor<AAAlign>(IRP: ArgPos);
3523
3524 // Every argument with pointer type might be marked nocapture.
3525 checkAndQueryIRAttr<Attribute::Captures, AANoCapture>(
3526 IRP: ArgPos, Attrs: ArgAttrs, /*SkipHasAttrCheck=*/true);
3527
3528 // Every argument with pointer type might be marked
3529 // "readnone/readonly/writeonly/..."
3530 getOrCreateAAFor<AAMemoryBehavior>(IRP: ArgPos);
3531
3532 // Every argument with pointer type might be marked nofree.
3533 checkAndQueryIRAttr<Attribute::NoFree, AANoFree>(IRP: ArgPos, Attrs: ArgAttrs);
3534
3535 // Every argument with pointer type might be privatizable (or
3536 // promotable)
3537 getOrCreateAAFor<AAPrivatizablePtr>(IRP: ArgPos);
3538 } else if (AttributeFuncs::isNoFPClassCompatibleType(Ty: Arg.getType())) {
3539 getOrCreateAAFor<AANoFPClass>(IRP: ArgPos);
3540 }
3541 }
3542
3543 auto CallSitePred = [&](Instruction &I) -> bool {
3544 auto &CB = cast<CallBase>(Val&: I);
3545 IRPosition CBInstPos = IRPosition::inst(I: CB);
3546 IRPosition CBFnPos = IRPosition::callsite_function(CB);
3547
3548 // Call sites might be dead if they do not have side effects and no live
3549 // users. The return value might be dead if there are no live users.
3550 getOrCreateAAFor<AAIsDead>(IRP: CBInstPos);
3551
3552 Function *Callee = dyn_cast_if_present<Function>(Val: CB.getCalledOperand());
3553 // TODO: Even if the callee is not known now we might be able to simplify
3554 // the call/callee.
3555 if (!Callee) {
3556 getOrCreateAAFor<AAIndirectCallInfo>(IRP: CBFnPos);
3557 return true;
3558 }
3559
3560 // Every call site can track active assumptions.
3561 getOrCreateAAFor<AAAssumptionInfo>(IRP: CBFnPos);
3562
3563 // Skip declarations except if annotations on their call sites were
3564 // explicitly requested.
3565 if (!Opts.attributor_annotate_decl_cs && Callee->isDeclaration() &&
3566 !Callee->hasMetadata(KindID: LLVMContext::MD_callback))
3567 return true;
3568
3569 if (!Callee->getReturnType()->isVoidTy() && !CB.use_empty()) {
3570 IRPosition CBRetPos = IRPosition::callsite_returned(CB);
3571 bool UsedAssumedInformation = false;
3572 getAssumedSimplified(IRP: CBRetPos, AA: nullptr, UsedAssumedInformation,
3573 S: AA::Intraprocedural);
3574
3575 if (AttributeFuncs::isNoFPClassCompatibleType(Ty: Callee->getReturnType()))
3576 getOrCreateAAFor<AANoFPClass>(IRP: CBInstPos);
3577 }
3578
3579 const AttributeList &CBAttrs = CBFnPos.getAttrList();
3580 for (int I = 0, E = CB.arg_size(); I < E; ++I) {
3581
3582 IRPosition CBArgPos = IRPosition::callsite_argument(CB, ArgNo: I);
3583 AttributeSet CBArgAttrs = CBAttrs.getParamAttrs(ArgNo: I);
3584
3585 // Every call site argument might be dead.
3586 getOrCreateAAFor<AAIsDead>(IRP: CBArgPos);
3587
3588 // Call site argument might be simplified. We have to go through the
3589 // Attributor interface though as outside AAs can register custom
3590 // simplification callbacks.
3591 bool UsedAssumedInformation = false;
3592 getAssumedSimplified(IRP: CBArgPos, /* AA */ nullptr, UsedAssumedInformation,
3593 S: AA::Intraprocedural);
3594
3595 // Every call site argument might be marked "noundef".
3596 checkAndQueryIRAttr<Attribute::NoUndef, AANoUndef>(IRP: CBArgPos, Attrs: CBArgAttrs);
3597
3598 Type *ArgTy = CB.getArgOperand(i: I)->getType();
3599
3600 if (!ArgTy->isPointerTy()) {
3601 if (AttributeFuncs::isNoFPClassCompatibleType(Ty: ArgTy))
3602 getOrCreateAAFor<AANoFPClass>(IRP: CBArgPos);
3603
3604 continue;
3605 }
3606
3607 // Call site argument attribute "non-null".
3608 checkAndQueryIRAttr<Attribute::NonNull, AANonNull>(IRP: CBArgPos, Attrs: CBArgAttrs);
3609
3610 // Call site argument attribute "captures(none)".
3611 checkAndQueryIRAttr<Attribute::Captures, AANoCapture>(
3612 IRP: CBArgPos, Attrs: CBArgAttrs, /*SkipHasAttrCheck=*/true);
3613
3614 // Call site argument attribute "no-alias".
3615 checkAndQueryIRAttr<Attribute::NoAlias, AANoAlias>(IRP: CBArgPos, Attrs: CBArgAttrs);
3616
3617 // Call site argument attribute "dereferenceable".
3618 getOrCreateAAFor<AADereferenceable>(IRP: CBArgPos);
3619
3620 // Call site argument attribute "align".
3621 getOrCreateAAFor<AAAlign>(IRP: CBArgPos);
3622
3623 // Call site argument attribute
3624 // "readnone/readonly/writeonly/..."
3625 if (!CBAttrs.hasParamAttr(ArgNo: I, Kind: Attribute::ReadNone))
3626 getOrCreateAAFor<AAMemoryBehavior>(IRP: CBArgPos);
3627
3628 // Call site argument attribute "nofree".
3629 checkAndQueryIRAttr<Attribute::NoFree, AANoFree>(IRP: CBArgPos, Attrs: CBArgAttrs);
3630 }
3631 return true;
3632 };
3633
3634 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
3635 [[maybe_unused]] bool Success;
3636 bool UsedAssumedInformation = false;
3637 Success = checkForAllInstructionsImpl(
3638 A: nullptr, OpcodeInstMap, Pred: CallSitePred, QueryingAA: nullptr, LivenessAA: nullptr,
3639 Opcodes: {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
3640 (unsigned)Instruction::Call},
3641 UsedAssumedInformation);
3642 assert(Success && "Expected the check call to be successful!");
3643
3644 auto LoadStorePred = [&](Instruction &I) -> bool {
3645 if (auto *LI = dyn_cast<LoadInst>(Val: &I)) {
3646 getOrCreateAAFor<AAAlign>(IRP: IRPosition::value(V: *LI->getPointerOperand()));
3647 if (Opts.attributor_simplify_all_loads)
3648 getAssumedSimplified(IRP: IRPosition::value(V: I), AA: nullptr,
3649 UsedAssumedInformation, S: AA::Intraprocedural);
3650 getOrCreateAAFor<AAInvariantLoadPointer>(
3651 IRP: IRPosition::value(V: *LI->getPointerOperand()));
3652 if (InfoCache.getFlatAddressSpace().has_value()) {
3653 getOrCreateAAFor<AAAddressSpace>(
3654 IRP: IRPosition::value(V: *LI->getPointerOperand()));
3655 }
3656 } else {
3657 auto &SI = cast<StoreInst>(Val&: I);
3658 getOrCreateAAFor<AAIsDead>(IRP: IRPosition::inst(I));
3659 getAssumedSimplified(IRP: IRPosition::value(V: *SI.getValueOperand()), AA: nullptr,
3660 UsedAssumedInformation, S: AA::Intraprocedural);
3661 getOrCreateAAFor<AAAlign>(IRP: IRPosition::value(V: *SI.getPointerOperand()));
3662 if (InfoCache.getFlatAddressSpace().has_value()) {
3663 getOrCreateAAFor<AAAddressSpace>(
3664 IRP: IRPosition::value(V: *SI.getPointerOperand()));
3665 }
3666 }
3667 return true;
3668 };
3669 Success = checkForAllInstructionsImpl(
3670 A: nullptr, OpcodeInstMap, Pred: LoadStorePred, QueryingAA: nullptr, LivenessAA: nullptr,
3671 Opcodes: {(unsigned)Instruction::Load, (unsigned)Instruction::Store},
3672 UsedAssumedInformation);
3673 assert(Success && "Expected the check call to be successful!");
3674
3675 // AllocaInstPredicate
3676 auto AAAllocationInfoPred = [&](Instruction &I) -> bool {
3677 getOrCreateAAFor<AAAllocationInfo>(IRP: IRPosition::value(V: I));
3678 return true;
3679 };
3680
3681 Success = checkForAllInstructionsImpl(
3682 A: nullptr, OpcodeInstMap, Pred: AAAllocationInfoPred, QueryingAA: nullptr, LivenessAA: nullptr,
3683 Opcodes: {(unsigned)Instruction::Alloca}, UsedAssumedInformation);
3684 assert(Success && "Expected the check call to be successful!");
3685}
3686
3687bool Attributor::isClosedWorldModule() const {
3688 return valueOr(X: Opts.attributor_assume_closed_world,
3689 Default: isModulePass() && Configuration.IsClosedWorldModule);
3690}
3691
3692/// Helpers to ease debugging through output streams and print calls.
3693///
3694///{
3695raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
3696 return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
3697}
3698
3699raw_ostream &llvm::operator<<(raw_ostream &OS, IRPosition::Kind AP) {
3700 switch (AP) {
3701 case IRPosition::IRP_INVALID:
3702 return OS << "inv";
3703 case IRPosition::IRP_FLOAT:
3704 return OS << "flt";
3705 case IRPosition::IRP_RETURNED:
3706 return OS << "fn_ret";
3707 case IRPosition::IRP_CALL_SITE_RETURNED:
3708 return OS << "cs_ret";
3709 case IRPosition::IRP_FUNCTION:
3710 return OS << "fn";
3711 case IRPosition::IRP_CALL_SITE:
3712 return OS << "cs";
3713 case IRPosition::IRP_ARGUMENT:
3714 return OS << "arg";
3715 case IRPosition::IRP_CALL_SITE_ARGUMENT:
3716 return OS << "cs_arg";
3717 }
3718 llvm_unreachable("Unknown attribute position!");
3719}
3720
3721raw_ostream &llvm::operator<<(raw_ostream &OS, const IRPosition &Pos) {
3722 const Value &AV = Pos.getAssociatedValue();
3723 OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " ["
3724 << Pos.getAnchorValue().getName() << "@" << Pos.getCallSiteArgNo() << "]";
3725
3726 if (Pos.hasCallBaseContext())
3727 OS << "[cb_context:" << *Pos.getCallBaseContext() << "]";
3728 return OS << "}";
3729}
3730
3731raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerRangeState &S) {
3732 OS << "range-state(" << S.getBitWidth() << ")<";
3733 S.getKnown().print(OS);
3734 OS << " / ";
3735 S.getAssumed().print(OS);
3736 OS << ">";
3737
3738 return OS << static_cast<const AbstractState &>(S);
3739}
3740
3741raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
3742 return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
3743}
3744
3745raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
3746 AA.print(OS);
3747 return OS;
3748}
3749
3750raw_ostream &llvm::operator<<(raw_ostream &OS,
3751 const PotentialConstantIntValuesState &S) {
3752 OS << "set-state(< {";
3753 if (!S.isValidState())
3754 OS << "full-set";
3755 else {
3756 for (const auto &It : S.getAssumedSet())
3757 OS << It << ", ";
3758 if (S.undefIsContained())
3759 OS << "undef ";
3760 }
3761 OS << "} >)";
3762
3763 return OS;
3764}
3765
3766raw_ostream &llvm::operator<<(raw_ostream &OS,
3767 const PotentialLLVMValuesState &S) {
3768 OS << "set-state(< {";
3769 if (!S.isValidState())
3770 OS << "full-set";
3771 else {
3772 for (const auto &It : S.getAssumedSet()) {
3773 if (auto *F = dyn_cast<Function>(Val: It.first.getValue()))
3774 OS << "@" << F->getName() << "[" << int(It.second) << "], ";
3775 else
3776 OS << *It.first.getValue() << "[" << int(It.second) << "], ";
3777 }
3778 if (S.undefIsContained())
3779 OS << "undef ";
3780 }
3781 OS << "} >)";
3782
3783 return OS;
3784}
3785
3786void AbstractAttribute::print(Attributor *A, raw_ostream &OS) const {
3787 OS << "[";
3788 OS << getName();
3789 OS << "] for CtxI ";
3790
3791 if (auto *I = getCtxI()) {
3792 OS << "'";
3793 I->print(O&: OS);
3794 OS << "'";
3795 } else
3796 OS << "<<null inst>>";
3797
3798 OS << " at position " << getIRPosition() << " with state " << getAsStr(A)
3799 << '\n';
3800}
3801
3802void AbstractAttribute::printWithDeps(raw_ostream &OS) const {
3803 print(OS);
3804
3805 for (const auto &DepAA : Deps) {
3806 auto *AA = DepAA.getPointer();
3807 OS << " updates ";
3808 AA->print(OS);
3809 }
3810
3811 OS << '\n';
3812}
3813
3814raw_ostream &llvm::operator<<(raw_ostream &OS,
3815 const AAPointerInfo::Access &Acc) {
3816 OS << " [" << Acc.getKind() << "] " << *Acc.getRemoteInst();
3817 if (Acc.getLocalInst() != Acc.getRemoteInst())
3818 OS << " via " << *Acc.getLocalInst();
3819 if (Acc.getContent()) {
3820 if (*Acc.getContent())
3821 OS << " [" << **Acc.getContent() << "]";
3822 else
3823 OS << " [ <unknown> ]";
3824 }
3825 return OS;
3826}
3827///}
3828
3829/// ----------------------------------------------------------------------------
3830/// Pass (Manager) Boilerplate
3831/// ----------------------------------------------------------------------------
3832
3833static bool runAttributorOnFunctions(InformationCache &InfoCache,
3834 SetVector<Function *> &Functions,
3835 CallGraphUpdater &CGUpdater,
3836 FunctionAnalysisManager &FAM,
3837 bool DeleteFns, bool IsModulePass) {
3838 if (Functions.empty())
3839 return false;
3840
3841 const IPOOptions &Opts = getIPOOptions(M: InfoCache.getModule());
3842 LLVM_DEBUG({
3843 dbgs() << "[Attributor] Run on module with " << Functions.size()
3844 << " functions:\n";
3845 for (Function *Fn : Functions)
3846 dbgs() << " - " << Fn->getName() << "\n";
3847 });
3848
3849 // Create an Attributor and initially empty information cache that is filled
3850 // while we identify default attribute opportunities.
3851 AttributorConfig AC(CGUpdater);
3852 AC.IsModulePass = IsModulePass;
3853 AC.DeleteFns = DeleteFns;
3854 auto OREGetter = [&FAM](Function *F) -> OptimizationRemarkEmitter & {
3855 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: *F);
3856 };
3857 AC.OREGetter = OREGetter;
3858 AC.PassName = DEBUG_TYPE;
3859
3860 /// Tracking callback for specialization of indirect calls.
3861 DenseMap<CallBase *, std::unique_ptr<SmallPtrSet<Function *, 8>>>
3862 IndirectCalleeTrackingMap;
3863 if (Opts.attributor_max_specializations_per_call_base) {
3864 AC.IndirectCalleeSpecializationCallback =
3865 [&](Attributor &, const AbstractAttribute &AA, CallBase &CB,
3866 Function &Callee, unsigned) {
3867 if (*Opts.attributor_max_specializations_per_call_base == 0)
3868 return false;
3869 auto &Set = IndirectCalleeTrackingMap[&CB];
3870 if (!Set)
3871 Set = std::make_unique<SmallPtrSet<Function *, 8>>();
3872 if (Set->size() >= *Opts.attributor_max_specializations_per_call_base)
3873 return Set->contains(Ptr: &Callee);
3874 Set->insert(Ptr: &Callee);
3875 return true;
3876 };
3877 }
3878
3879 Attributor A(Functions, InfoCache, AC);
3880
3881 // Create shallow wrappers for all functions that are not IPO amendable
3882 if (Opts.attributor_allow_shallow_wrappers)
3883 for (Function *F : Functions)
3884 if (!A.isFunctionIPOAmendable(F: *F))
3885 Attributor::createShallowWrapper(F&: *F);
3886
3887 // Internalize non-exact functions
3888 // TODO: for now we eagerly internalize functions without calculating the
3889 // cost, we need a cost interface to determine whether internalizing
3890 // a function is "beneficial"
3891 if (Opts.attributor_allow_deep_wrappers) {
3892 unsigned FunSize = Functions.size();
3893 for (unsigned u = 0; u < FunSize; u++) {
3894 Function *F = Functions[u];
3895 if (!F->isDeclaration() && !F->isDefinitionExact() && !F->use_empty() &&
3896 !GlobalValue::isInterposableLinkage(Linkage: F->getLinkage())) {
3897 Function *NewF = Attributor::internalizeFunction(F&: *F);
3898 assert(NewF && "Could not internalize function.");
3899 Functions.insert(X: NewF);
3900
3901 // Update call graph
3902 CGUpdater.replaceFunctionWith(OldFn&: *F, NewFn&: *NewF);
3903 for (const Use &U : NewF->uses())
3904 if (CallBase *CB = dyn_cast<CallBase>(Val: U.getUser())) {
3905 auto *CallerF = CB->getCaller();
3906 CGUpdater.reanalyzeFunction(Fn&: *CallerF);
3907 }
3908 }
3909 }
3910 }
3911
3912 for (Function *F : Functions) {
3913 if (F->isDeclaration())
3914 continue;
3915
3916 if (F->hasExactDefinition())
3917 NumFnWithExactDefinition++;
3918 else
3919 NumFnWithoutExactDefinition++;
3920
3921 // We look at internal functions only on-demand but if any use is not a
3922 // direct call or outside the current set of analyzed functions, we have
3923 // to do it eagerly.
3924 if (F->hasLocalLinkage()) {
3925 if (llvm::all_of(Range: F->uses(), P: [&Functions](const Use &U) {
3926 const auto *CB = dyn_cast<CallBase>(Val: U.getUser());
3927 return CB && CB->isCallee(U: &U) &&
3928 Functions.count(key: const_cast<Function *>(CB->getCaller()));
3929 }))
3930 continue;
3931 }
3932
3933 // Populate the Attributor with abstract attribute opportunities in the
3934 // function and the information cache with IR information.
3935 A.identifyDefaultAbstractAttributes(F&: *F);
3936 }
3937
3938 ChangeStatus Changed = A.run();
3939
3940 LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
3941 << " functions, result: " << Changed << ".\n");
3942 return Changed == ChangeStatus::CHANGED;
3943}
3944
3945static bool runAttributorLightOnFunctions(InformationCache &InfoCache,
3946 SetVector<Function *> &Functions,
3947 CallGraphUpdater &CGUpdater,
3948 FunctionAnalysisManager &FAM,
3949 bool IsModulePass) {
3950 if (Functions.empty())
3951 return false;
3952
3953 LLVM_DEBUG({
3954 dbgs() << "[AttributorLight] Run on module with " << Functions.size()
3955 << " functions:\n";
3956 for (Function *Fn : Functions)
3957 dbgs() << " - " << Fn->getName() << "\n";
3958 });
3959
3960 // Create an Attributor and initially empty information cache that is filled
3961 // while we identify default attribute opportunities.
3962 AttributorConfig AC(CGUpdater);
3963 AC.IsModulePass = IsModulePass;
3964 AC.DeleteFns = false;
3965 static constexpr AAKindSet Allowed =
3966 AAKindSet::get<AAWillReturn, AANoUnwind, AANoRecurse, AANoSync, AANoFree,
3967 AANoReturn, AAMemoryLocation, AAMemoryBehavior,
3968 AAUnderlyingObjects, AANoCapture, AAInterFnReachability,
3969 AAIntraFnReachability, AACallEdges, AANoFPClass,
3970 AAMustProgress, AANonNull, AADenormalFPMath>();
3971 AC.Allowed = Allowed;
3972 AC.UseLiveness = false;
3973
3974 Attributor A(Functions, InfoCache, AC);
3975
3976 for (Function *F : Functions) {
3977 if (F->isDeclaration())
3978 continue;
3979
3980 if (F->hasExactDefinition())
3981 NumFnWithExactDefinition++;
3982 else
3983 NumFnWithoutExactDefinition++;
3984
3985 // We look at internal functions only on-demand but if any use is not a
3986 // direct call or outside the current set of analyzed functions, we have
3987 // to do it eagerly.
3988 if (AC.UseLiveness && F->hasLocalLinkage()) {
3989 if (llvm::all_of(Range: F->uses(), P: [&Functions](const Use &U) {
3990 const auto *CB = dyn_cast<CallBase>(Val: U.getUser());
3991 return CB && CB->isCallee(U: &U) &&
3992 Functions.count(key: const_cast<Function *>(CB->getCaller()));
3993 }))
3994 continue;
3995 }
3996
3997 // Populate the Attributor with abstract attribute opportunities in the
3998 // function and the information cache with IR information.
3999 A.identifyDefaultAbstractAttributes(F&: *F);
4000 }
4001
4002 ChangeStatus Changed = A.run();
4003
4004 if (Changed == ChangeStatus::CHANGED) {
4005 // Invalidate analyses for modified functions so that we don't have to
4006 // invalidate all analyses for all functions in this SCC.
4007 PreservedAnalyses FuncPA;
4008 // We haven't changed the CFG for modified functions.
4009 FuncPA.preserveSet<CFGAnalyses>();
4010 // Functions whose instructions did not change do not need to be simplified
4011 // again if their SCC is revisited.
4012 PreservedAnalyses AttrOnlyPA = FuncPA;
4013 AttrOnlyPA.preserve<ShouldNotRunFunctionPassesAnalysis>();
4014
4015 const SmallSetVector<Function *, 8> &IRModified = A.getModifiedFunctions();
4016
4017 // Also invalidate any direct callers of changed functions since analyses
4018 // may care about attributes of direct callees. For example, MemorySSA
4019 // cares about whether or not a call's callee modifies memory and queries
4020 // that through function attributes.
4021 auto InvalidateCallers = [&](Function &Changed) {
4022 for (auto *U : Changed.users()) {
4023 auto *Call = dyn_cast<CallBase>(Val: U);
4024 if (Call && Call->getCalledFunction() == &Changed)
4025 FAM.invalidate(IR&: *Call->getFunction(), PA: AttrOnlyPA);
4026 }
4027 };
4028
4029 for (Function *Changed : IRModified) {
4030 FAM.invalidate(IR&: *Changed, PA: FuncPA);
4031 InvalidateCallers(*Changed);
4032 }
4033
4034 for (Function *Changed : A.getAttrModifiedFunctions()) {
4035 if (IRModified.contains(key: Changed))
4036 continue;
4037 FAM.invalidate(IR&: *Changed, PA: AttrOnlyPA);
4038 InvalidateCallers(*Changed);
4039 }
4040 }
4041 LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
4042 << " functions, result: " << Changed << ".\n");
4043 return Changed == ChangeStatus::CHANGED;
4044}
4045
4046void AADepGraph::viewGraph() { llvm::ViewGraph(G: this, Name: "Dependency Graph"); }
4047
4048void AADepGraph::dumpGraph(StringRef DotFileNamePrefix) {
4049 static std::atomic<int> CallTimes;
4050 std::string Prefix;
4051
4052 if (!DotFileNamePrefix.empty())
4053 Prefix = DotFileNamePrefix;
4054 else
4055 Prefix = "dep_graph";
4056 std::string Filename =
4057 Prefix + "_" + std::to_string(val: CallTimes.load()) + ".dot";
4058
4059 outs() << "Dependency graph dump to " << Filename << ".\n";
4060
4061 std::error_code EC;
4062
4063 raw_fd_ostream File(Filename, EC, sys::fs::OF_TextWithCRLF);
4064 if (!EC)
4065 llvm::WriteGraph(O&: File, G: this);
4066
4067 CallTimes++;
4068}
4069
4070void AADepGraph::print() {
4071 for (auto DepAA : SyntheticRoot.Deps)
4072 cast<AbstractAttribute>(Val: DepAA.getPointer())->printWithDeps(OS&: outs());
4073}
4074
4075PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
4076 FunctionAnalysisManager &FAM =
4077 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
4078 AnalysisGetter AG(FAM);
4079
4080 SetVector<Function *> Functions;
4081 Functions.reserve(Size: M.size());
4082 for (Function &F : M)
4083 Functions.insert(X: &F);
4084
4085 CallGraphUpdater CGUpdater;
4086 BumpPtrAllocator Allocator;
4087 InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
4088 if (runAttributorOnFunctions(InfoCache, Functions, CGUpdater, FAM,
4089 /* DeleteFns */ true, /* IsModulePass */ true)) {
4090 // FIXME: Think about passes we will preserve and add them here.
4091 return PreservedAnalyses::none();
4092 }
4093 return PreservedAnalyses::all();
4094}
4095
4096PreservedAnalyses AttributorCGSCCPass::run(LazyCallGraph::SCC &C,
4097 CGSCCAnalysisManager &AM,
4098 LazyCallGraph &CG,
4099 CGSCCUpdateResult &UR) {
4100 FunctionAnalysisManager &FAM =
4101 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
4102 AnalysisGetter AG(FAM);
4103
4104 SetVector<Function *> Functions;
4105 Functions.reserve(Size: C.size());
4106 for (LazyCallGraph::Node &N : C)
4107 Functions.insert(X: &N.getFunction());
4108
4109 if (Functions.empty())
4110 return PreservedAnalyses::all();
4111
4112 Module &M = *Functions.back()->getParent();
4113 CallGraphUpdater CGUpdater;
4114 CGUpdater.initialize(LCG&: CG, SCC&: C, AM, UR);
4115 BumpPtrAllocator Allocator;
4116 InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
4117 if (runAttributorOnFunctions(InfoCache, Functions, CGUpdater, FAM,
4118 /* DeleteFns */ false,
4119 /* IsModulePass */ false)) {
4120 // FIXME: Think about passes we will preserve and add them here.
4121 PreservedAnalyses PA;
4122 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
4123 return PA;
4124 }
4125 return PreservedAnalyses::all();
4126}
4127
4128PreservedAnalyses AttributorLightPass::run(Module &M,
4129 ModuleAnalysisManager &AM) {
4130 FunctionAnalysisManager &FAM =
4131 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
4132 AnalysisGetter AG(FAM, /* CachedOnly */ true);
4133
4134 SetVector<Function *> Functions;
4135 Functions.reserve(Size: M.size());
4136 for (Function &F : M)
4137 Functions.insert(X: &F);
4138
4139 CallGraphUpdater CGUpdater;
4140 BumpPtrAllocator Allocator;
4141 InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
4142 if (runAttributorLightOnFunctions(InfoCache, Functions, CGUpdater, FAM,
4143 /* IsModulePass */ true)) {
4144 PreservedAnalyses PA;
4145 // We have not added or removed functions.
4146 PA.preserve<FunctionAnalysisManagerModuleProxy>();
4147 // We already invalidated all relevant function analyses above.
4148 PA.preserveSet<AllAnalysesOn<Function>>();
4149 return PA;
4150 }
4151 return PreservedAnalyses::all();
4152}
4153
4154PreservedAnalyses AttributorLightCGSCCPass::run(LazyCallGraph::SCC &C,
4155 CGSCCAnalysisManager &AM,
4156 LazyCallGraph &CG,
4157 CGSCCUpdateResult &UR) {
4158 FunctionAnalysisManager &FAM =
4159 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
4160 AnalysisGetter AG(FAM);
4161
4162 SetVector<Function *> Functions;
4163 for (LazyCallGraph::Node &N : C)
4164 Functions.insert(X: &N.getFunction());
4165
4166 if (Functions.empty())
4167 return PreservedAnalyses::all();
4168
4169 Module &M = *Functions.back()->getParent();
4170 CallGraphUpdater CGUpdater;
4171 CGUpdater.initialize(LCG&: CG, SCC&: C, AM, UR);
4172 BumpPtrAllocator Allocator;
4173 InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
4174 if (runAttributorLightOnFunctions(InfoCache, Functions, CGUpdater, FAM,
4175 /* IsModulePass */ false)) {
4176 PreservedAnalyses PA;
4177 // We have not added or removed functions.
4178 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
4179 // We already invalidated all relevant function analyses above.
4180 PA.preserveSet<AllAnalysesOn<Function>>();
4181 return PA;
4182 }
4183 return PreservedAnalyses::all();
4184}
4185namespace llvm {
4186
4187template <> struct GraphTraits<AADepGraphNode *> {
4188 using NodeRef = AADepGraphNode *;
4189 using DepTy = PointerIntPair<AADepGraphNode *, 1>;
4190 using EdgeRef = PointerIntPair<AADepGraphNode *, 1>;
4191
4192 static NodeRef getEntryNode(AADepGraphNode *DGN) { return DGN; }
4193 static NodeRef DepGetVal(const DepTy &DT) { return DT.getPointer(); }
4194
4195 using ChildIteratorType =
4196 mapped_iterator<AADepGraphNode::DepSetTy::iterator, decltype(&DepGetVal)>;
4197 using ChildEdgeIteratorType = AADepGraphNode::DepSetTy::iterator;
4198
4199 static ChildIteratorType child_begin(NodeRef N) { return N->child_begin(); }
4200
4201 static ChildIteratorType child_end(NodeRef N) { return N->child_end(); }
4202};
4203
4204template <>
4205struct GraphTraits<AADepGraph *> : public GraphTraits<AADepGraphNode *> {
4206 static NodeRef getEntryNode(AADepGraph *DG) { return DG->GetEntryNode(); }
4207
4208 using nodes_iterator =
4209 mapped_iterator<AADepGraphNode::DepSetTy::iterator, decltype(&DepGetVal)>;
4210
4211 static nodes_iterator nodes_begin(AADepGraph *DG) { return DG->begin(); }
4212
4213 static nodes_iterator nodes_end(AADepGraph *DG) { return DG->end(); }
4214};
4215
4216template <> struct DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits {
4217 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
4218
4219 static std::string getNodeLabel(const AADepGraphNode *Node,
4220 const AADepGraph *DG) {
4221 std::string AAString;
4222 raw_string_ostream O(AAString);
4223 Node->print(OS&: O);
4224 return AAString;
4225 }
4226};
4227
4228} // end namespace llvm
4229