LLVM 17.0.0git
AttributorAttributes.cpp
Go to the documentation of this file.
1//===- AttributorAttributes.cpp - Attributes for Attributor 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// See the Attributor.h file comment and the class descriptions in that file for
10// more information.
11//
12//===----------------------------------------------------------------------===//
13
15
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/MapVector.h"
21#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SetVector.h"
26#include "llvm/ADT/Statistic.h"
39#include "llvm/IR/Argument.h"
40#include "llvm/IR/Assumptions.h"
41#include "llvm/IR/BasicBlock.h"
42#include "llvm/IR/Constant.h"
43#include "llvm/IR/Constants.h"
44#include "llvm/IR/DataLayout.h"
46#include "llvm/IR/GlobalValue.h"
47#include "llvm/IR/IRBuilder.h"
48#include "llvm/IR/InlineAsm.h"
49#include "llvm/IR/InstrTypes.h"
50#include "llvm/IR/Instruction.h"
53#include "llvm/IR/IntrinsicsAMDGPU.h"
54#include "llvm/IR/IntrinsicsNVPTX.h"
55#include "llvm/IR/NoFolder.h"
56#include "llvm/IR/Value.h"
57#include "llvm/IR/ValueHandle.h"
67#include <cassert>
68#include <numeric>
69#include <optional>
70
71using namespace llvm;
72
73#define DEBUG_TYPE "attributor"
74
76 "attributor-manifest-internal", cl::Hidden,
77 cl::desc("Manifest Attributor internal string attributes."),
78 cl::init(false));
79
80static cl::opt<int> MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128),
82
83template <>
85
87
89 "attributor-max-potential-values", cl::Hidden,
90 cl::desc("Maximum number of potential values to be "
91 "tracked for each position."),
93 cl::init(7));
94
96 "attributor-max-potential-values-iterations", cl::Hidden,
98 "Maximum number of iterations we keep dismantling potential values."),
99 cl::init(64));
100
101STATISTIC(NumAAs, "Number of abstract attributes created");
102
103// Some helper macros to deal with statistics tracking.
104//
105// Usage:
106// For simple IR attribute tracking overload trackStatistics in the abstract
107// attribute and choose the right STATS_DECLTRACK_********* macro,
108// e.g.,:
109// void trackStatistics() const override {
110// STATS_DECLTRACK_ARG_ATTR(returned)
111// }
112// If there is a single "increment" side one can use the macro
113// STATS_DECLTRACK with a custom message. If there are multiple increment
114// sides, STATS_DECL and STATS_TRACK can also be used separately.
115//
116#define BUILD_STAT_MSG_IR_ATTR(TYPE, NAME) \
117 ("Number of " #TYPE " marked '" #NAME "'")
118#define BUILD_STAT_NAME(NAME, TYPE) NumIR##TYPE##_##NAME
119#define STATS_DECL_(NAME, MSG) STATISTIC(NAME, MSG);
120#define STATS_DECL(NAME, TYPE, MSG) \
121 STATS_DECL_(BUILD_STAT_NAME(NAME, TYPE), MSG);
122#define STATS_TRACK(NAME, TYPE) ++(BUILD_STAT_NAME(NAME, TYPE));
123#define STATS_DECLTRACK(NAME, TYPE, MSG) \
124 { \
125 STATS_DECL(NAME, TYPE, MSG) \
126 STATS_TRACK(NAME, TYPE) \
127 }
128#define STATS_DECLTRACK_ARG_ATTR(NAME) \
129 STATS_DECLTRACK(NAME, Arguments, BUILD_STAT_MSG_IR_ATTR(arguments, NAME))
130#define STATS_DECLTRACK_CSARG_ATTR(NAME) \
131 STATS_DECLTRACK(NAME, CSArguments, \
132 BUILD_STAT_MSG_IR_ATTR(call site arguments, NAME))
133#define STATS_DECLTRACK_FN_ATTR(NAME) \
134 STATS_DECLTRACK(NAME, Function, BUILD_STAT_MSG_IR_ATTR(functions, NAME))
135#define STATS_DECLTRACK_CS_ATTR(NAME) \
136 STATS_DECLTRACK(NAME, CS, BUILD_STAT_MSG_IR_ATTR(call site, NAME))
137#define STATS_DECLTRACK_FNRET_ATTR(NAME) \
138 STATS_DECLTRACK(NAME, FunctionReturn, \
139 BUILD_STAT_MSG_IR_ATTR(function returns, NAME))
140#define STATS_DECLTRACK_CSRET_ATTR(NAME) \
141 STATS_DECLTRACK(NAME, CSReturn, \
142 BUILD_STAT_MSG_IR_ATTR(call site returns, NAME))
143#define STATS_DECLTRACK_FLOATING_ATTR(NAME) \
144 STATS_DECLTRACK(NAME, Floating, \
145 ("Number of floating values known to be '" #NAME "'"))
146
147// Specialization of the operator<< for abstract attributes subclasses. This
148// disambiguates situations where multiple operators are applicable.
149namespace llvm {
150#define PIPE_OPERATOR(CLASS) \
151 raw_ostream &operator<<(raw_ostream &OS, const CLASS &AA) { \
152 return OS << static_cast<const AbstractAttribute &>(AA); \
153 }
154
188
189#undef PIPE_OPERATOR
190
191template <>
193 const DerefState &R) {
194 ChangeStatus CS0 =
195 clampStateAndIndicateChange(S.DerefBytesState, R.DerefBytesState);
196 ChangeStatus CS1 = clampStateAndIndicateChange(S.GlobalState, R.GlobalState);
197 return CS0 | CS1;
198}
199
200} // namespace llvm
201
202static bool mayBeInCycle(const CycleInfo *CI, const Instruction *I,
203 bool HeaderOnly, Cycle **CPtr = nullptr) {
204 if (!CI)
205 return true;
206 auto *BB = I->getParent();
207 auto *C = CI->getCycle(BB);
208 if (!C)
209 return false;
210 if (CPtr)
211 *CPtr = C;
212 return !HeaderOnly || BB == C->getHeader();
213}
214
215/// Checks if a type could have padding bytes.
216static bool isDenselyPacked(Type *Ty, const DataLayout &DL) {
217 // There is no size information, so be conservative.
218 if (!Ty->isSized())
219 return false;
220
221 // If the alloc size is not equal to the storage size, then there are padding
222 // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128.
223 if (DL.getTypeSizeInBits(Ty) != DL.getTypeAllocSizeInBits(Ty))
224 return false;
225
226 // FIXME: This isn't the right way to check for padding in vectors with
227 // non-byte-size elements.
228 if (VectorType *SeqTy = dyn_cast<VectorType>(Ty))
229 return isDenselyPacked(SeqTy->getElementType(), DL);
230
231 // For array types, check for padding within members.
232 if (ArrayType *SeqTy = dyn_cast<ArrayType>(Ty))
233 return isDenselyPacked(SeqTy->getElementType(), DL);
234
235 if (!isa<StructType>(Ty))
236 return true;
237
238 // Check for padding within and between elements of a struct.
239 StructType *StructTy = cast<StructType>(Ty);
240 const StructLayout *Layout = DL.getStructLayout(StructTy);
241 uint64_t StartPos = 0;
242 for (unsigned I = 0, E = StructTy->getNumElements(); I < E; ++I) {
243 Type *ElTy = StructTy->getElementType(I);
244 if (!isDenselyPacked(ElTy, DL))
245 return false;
246 if (StartPos != Layout->getElementOffsetInBits(I))
247 return false;
248 StartPos += DL.getTypeAllocSizeInBits(ElTy);
249 }
250
251 return true;
252}
253
254/// Get pointer operand of memory accessing instruction. If \p I is
255/// not a memory accessing instruction, return nullptr. If \p AllowVolatile,
256/// is set to false and the instruction is volatile, return nullptr.
258 bool AllowVolatile) {
259 if (!AllowVolatile && I->isVolatile())
260 return nullptr;
261
262 if (auto *LI = dyn_cast<LoadInst>(I)) {
263 return LI->getPointerOperand();
264 }
265
266 if (auto *SI = dyn_cast<StoreInst>(I)) {
267 return SI->getPointerOperand();
268 }
269
270 if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(I)) {
271 return CXI->getPointerOperand();
272 }
273
274 if (auto *RMWI = dyn_cast<AtomicRMWInst>(I)) {
275 return RMWI->getPointerOperand();
276 }
277
278 return nullptr;
279}
280
281/// Helper function to create a pointer of type \p ResTy, based on \p Ptr, and
282/// advanced by \p Offset bytes. To aid later analysis the method tries to build
283/// getelement pointer instructions that traverse the natural type of \p Ptr if
284/// possible. If that fails, the remaining offset is adjusted byte-wise, hence
285/// through a cast to i8*.
286///
287/// TODO: This could probably live somewhere more prominantly if it doesn't
288/// already exist.
289static Value *constructPointer(Type *ResTy, Type *PtrElemTy, Value *Ptr,
290 int64_t Offset, IRBuilder<NoFolder> &IRB,
291 const DataLayout &DL) {
292 assert(Offset >= 0 && "Negative offset not supported yet!");
293 LLVM_DEBUG(dbgs() << "Construct pointer: " << *Ptr << " + " << Offset
294 << "-bytes as " << *ResTy << "\n");
295
296 if (Offset) {
297 Type *Ty = PtrElemTy;
298 APInt IntOffset(DL.getIndexTypeSizeInBits(Ptr->getType()), Offset);
299 SmallVector<APInt> IntIndices = DL.getGEPIndicesForOffset(Ty, IntOffset);
300
301 SmallVector<Value *, 4> ValIndices;
302 std::string GEPName = Ptr->getName().str();
303 for (const APInt &Index : IntIndices) {
304 ValIndices.push_back(IRB.getInt(Index));
305 GEPName += "." + std::to_string(Index.getZExtValue());
306 }
307
308 // Create a GEP for the indices collected above.
309 Ptr = IRB.CreateGEP(PtrElemTy, Ptr, ValIndices, GEPName);
310
311 // If an offset is left we use byte-wise adjustment.
312 if (IntOffset != 0) {
313 Ptr = IRB.CreateBitCast(Ptr, IRB.getInt8PtrTy());
314 Ptr = IRB.CreateGEP(IRB.getInt8Ty(), Ptr, IRB.getInt(IntOffset),
315 GEPName + ".b" + Twine(IntOffset.getZExtValue()));
316 }
317 }
318
319 // Ensure the result has the requested type.
321 Ptr->getName() + ".cast");
322
323 LLVM_DEBUG(dbgs() << "Constructed pointer: " << *Ptr << "\n");
324 return Ptr;
325}
326
327static const Value *
329 const Value *Val, const DataLayout &DL, APInt &Offset,
330 bool GetMinOffset, bool AllowNonInbounds,
331 bool UseAssumed = false) {
332
333 auto AttributorAnalysis = [&](Value &V, APInt &ROffset) -> bool {
334 const IRPosition &Pos = IRPosition::value(V);
335 // Only track dependence if we are going to use the assumed info.
336 const AAValueConstantRange &ValueConstantRangeAA =
337 A.getAAFor<AAValueConstantRange>(QueryingAA, Pos,
338 UseAssumed ? DepClassTy::OPTIONAL
339 : DepClassTy::NONE);
340 ConstantRange Range = UseAssumed ? ValueConstantRangeAA.getAssumed()
341 : ValueConstantRangeAA.getKnown();
342 if (Range.isFullSet())
343 return false;
344
345 // We can only use the lower part of the range because the upper part can
346 // be higher than what the value can really be.
347 if (GetMinOffset)
348 ROffset = Range.getSignedMin();
349 else
350 ROffset = Range.getSignedMax();
351 return true;
352 };
353
354 return Val->stripAndAccumulateConstantOffsets(DL, Offset, AllowNonInbounds,
355 /* AllowInvariant */ true,
356 AttributorAnalysis);
357}
358
359static const Value *
361 const Value *Ptr, int64_t &BytesOffset,
362 const DataLayout &DL, bool AllowNonInbounds = false) {
363 APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
364 const Value *Base =
365 stripAndAccumulateOffsets(A, QueryingAA, Ptr, DL, OffsetAPInt,
366 /* GetMinOffset */ true, AllowNonInbounds);
367
368 BytesOffset = OffsetAPInt.getSExtValue();
369 return Base;
370}
371
372/// Clamp the information known for all returned values of a function
373/// (identified by \p QueryingAA) into \p S.
374template <typename AAType, typename StateType = typename AAType::StateType>
376 Attributor &A, const AAType &QueryingAA, StateType &S,
377 const IRPosition::CallBaseContext *CBContext = nullptr) {
378 LLVM_DEBUG(dbgs() << "[Attributor] Clamp return value states for "
379 << QueryingAA << " into " << S << "\n");
380
381 assert((QueryingAA.getIRPosition().getPositionKind() ==
383 QueryingAA.getIRPosition().getPositionKind() ==
385 "Can only clamp returned value states for a function returned or call "
386 "site returned position!");
387
388 // Use an optional state as there might not be any return values and we want
389 // to join (IntegerState::operator&) the state of all there are.
390 std::optional<StateType> T;
391
392 // Callback for each possibly returned value.
393 auto CheckReturnValue = [&](Value &RV) -> bool {
394 const IRPosition &RVPos = IRPosition::value(RV, CBContext);
395 const AAType &AA =
396 A.getAAFor<AAType>(QueryingAA, RVPos, DepClassTy::REQUIRED);
397 LLVM_DEBUG(dbgs() << "[Attributor] RV: " << RV << " AA: " << AA.getAsStr()
398 << " @ " << RVPos << "\n");
399 const StateType &AAS = AA.getState();
400 if (!T)
401 T = StateType::getBestState(AAS);
402 *T &= AAS;
403 LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " RV State: " << T
404 << "\n");
405 return T->isValidState();
406 };
407
408 if (!A.checkForAllReturnedValues(CheckReturnValue, QueryingAA))
409 S.indicatePessimisticFixpoint();
410 else if (T)
411 S ^= *T;
412}
413
414namespace {
415/// Helper class for generic deduction: return value -> returned position.
416template <typename AAType, typename BaseType,
417 typename StateType = typename BaseType::StateType,
418 bool PropagateCallBaseContext = false>
419struct AAReturnedFromReturnedValues : public BaseType {
420 AAReturnedFromReturnedValues(const IRPosition &IRP, Attributor &A)
421 : BaseType(IRP, A) {}
422
423 /// See AbstractAttribute::updateImpl(...).
424 ChangeStatus updateImpl(Attributor &A) override {
425 StateType S(StateType::getBestState(this->getState()));
426 clampReturnedValueStates<AAType, StateType>(
427 A, *this, S,
428 PropagateCallBaseContext ? this->getCallBaseContext() : nullptr);
429 // TODO: If we know we visited all returned values, thus no are assumed
430 // dead, we can take the known information from the state T.
431 return clampStateAndIndicateChange<StateType>(this->getState(), S);
432 }
433};
434
435/// Clamp the information known at all call sites for a given argument
436/// (identified by \p QueryingAA) into \p S.
437template <typename AAType, typename StateType = typename AAType::StateType>
438static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA,
439 StateType &S) {
440 LLVM_DEBUG(dbgs() << "[Attributor] Clamp call site argument states for "
441 << QueryingAA << " into " << S << "\n");
442
443 assert(QueryingAA.getIRPosition().getPositionKind() ==
445 "Can only clamp call site argument states for an argument position!");
446
447 // Use an optional state as there might not be any return values and we want
448 // to join (IntegerState::operator&) the state of all there are.
449 std::optional<StateType> T;
450
451 // The argument number which is also the call site argument number.
452 unsigned ArgNo = QueryingAA.getIRPosition().getCallSiteArgNo();
453
454 auto CallSiteCheck = [&](AbstractCallSite ACS) {
455 const IRPosition &ACSArgPos = IRPosition::callsite_argument(ACS, ArgNo);
456 // Check if a coresponding argument was found or if it is on not associated
457 // (which can happen for callback calls).
458 if (ACSArgPos.getPositionKind() == IRPosition::IRP_INVALID)
459 return false;
460
461 const AAType &AA =
462 A.getAAFor<AAType>(QueryingAA, ACSArgPos, DepClassTy::REQUIRED);
463 LLVM_DEBUG(dbgs() << "[Attributor] ACS: " << *ACS.getInstruction()
464 << " AA: " << AA.getAsStr() << " @" << ACSArgPos << "\n");
465 const StateType &AAS = AA.getState();
466 if (!T)
467 T = StateType::getBestState(AAS);
468 *T &= AAS;
469 LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " CSA State: " << T
470 << "\n");
471 return T->isValidState();
472 };
473
474 bool UsedAssumedInformation = false;
475 if (!A.checkForAllCallSites(CallSiteCheck, QueryingAA, true,
476 UsedAssumedInformation))
477 S.indicatePessimisticFixpoint();
478 else if (T)
479 S ^= *T;
480}
481
482/// This function is the bridge between argument position and the call base
483/// context.
484template <typename AAType, typename BaseType,
485 typename StateType = typename AAType::StateType>
486bool getArgumentStateFromCallBaseContext(Attributor &A,
487 BaseType &QueryingAttribute,
488 IRPosition &Pos, StateType &State) {
490 "Expected an 'argument' position !");
491 const CallBase *CBContext = Pos.getCallBaseContext();
492 if (!CBContext)
493 return false;
494
495 int ArgNo = Pos.getCallSiteArgNo();
496 assert(ArgNo >= 0 && "Invalid Arg No!");
497
498 const auto &AA = A.getAAFor<AAType>(
499 QueryingAttribute, IRPosition::callsite_argument(*CBContext, ArgNo),
500 DepClassTy::REQUIRED);
501 const StateType &CBArgumentState =
502 static_cast<const StateType &>(AA.getState());
503
504 LLVM_DEBUG(dbgs() << "[Attributor] Briding Call site context to argument"
505 << "Position:" << Pos << "CB Arg state:" << CBArgumentState
506 << "\n");
507
508 // NOTE: If we want to do call site grouping it should happen here.
509 State ^= CBArgumentState;
510 return true;
511}
512
513/// Helper class for generic deduction: call site argument -> argument position.
514template <typename AAType, typename BaseType,
515 typename StateType = typename AAType::StateType,
516 bool BridgeCallBaseContext = false>
517struct AAArgumentFromCallSiteArguments : public BaseType {
518 AAArgumentFromCallSiteArguments(const IRPosition &IRP, Attributor &A)
519 : BaseType(IRP, A) {}
520
521 /// See AbstractAttribute::updateImpl(...).
522 ChangeStatus updateImpl(Attributor &A) override {
523 StateType S = StateType::getBestState(this->getState());
524
525 if (BridgeCallBaseContext) {
526 bool Success =
527 getArgumentStateFromCallBaseContext<AAType, BaseType, StateType>(
528 A, *this, this->getIRPosition(), S);
529 if (Success)
530 return clampStateAndIndicateChange<StateType>(this->getState(), S);
531 }
532 clampCallSiteArgumentStates<AAType, StateType>(A, *this, S);
533
534 // TODO: If we know we visited all incoming values, thus no are assumed
535 // dead, we can take the known information from the state T.
536 return clampStateAndIndicateChange<StateType>(this->getState(), S);
537 }
538};
539
540/// Helper class for generic replication: function returned -> cs returned.
541template <typename AAType, typename BaseType,
542 typename StateType = typename BaseType::StateType,
543 bool IntroduceCallBaseContext = false>
544struct AACallSiteReturnedFromReturned : public BaseType {
545 AACallSiteReturnedFromReturned(const IRPosition &IRP, Attributor &A)
546 : BaseType(IRP, A) {}
547
548 /// See AbstractAttribute::updateImpl(...).
549 ChangeStatus updateImpl(Attributor &A) override {
550 assert(this->getIRPosition().getPositionKind() ==
552 "Can only wrap function returned positions for call site returned "
553 "positions!");
554 auto &S = this->getState();
555
556 const Function *AssociatedFunction =
557 this->getIRPosition().getAssociatedFunction();
558 if (!AssociatedFunction)
559 return S.indicatePessimisticFixpoint();
560
561 CallBase &CBContext = cast<CallBase>(this->getAnchorValue());
562 if (IntroduceCallBaseContext)
563 LLVM_DEBUG(dbgs() << "[Attributor] Introducing call base context:"
564 << CBContext << "\n");
565
567 *AssociatedFunction, IntroduceCallBaseContext ? &CBContext : nullptr);
568 const AAType &AA = A.getAAFor<AAType>(*this, FnPos, DepClassTy::REQUIRED);
569 return clampStateAndIndicateChange(S, AA.getState());
570 }
571};
572
573/// Helper function to accumulate uses.
574template <class AAType, typename StateType = typename AAType::StateType>
575static void followUsesInContext(AAType &AA, Attributor &A,
577 const Instruction *CtxI,
579 StateType &State) {
580 auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
581 for (unsigned u = 0; u < Uses.size(); ++u) {
582 const Use *U = Uses[u];
583 if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
584 bool Found = Explorer.findInContextOf(UserI, EIt, EEnd);
585 if (Found && AA.followUseInMBEC(A, U, UserI, State))
586 for (const Use &Us : UserI->uses())
587 Uses.insert(&Us);
588 }
589 }
590}
591
592/// Use the must-be-executed-context around \p I to add information into \p S.
593/// The AAType class is required to have `followUseInMBEC` method with the
594/// following signature and behaviour:
595///
596/// bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I)
597/// U - Underlying use.
598/// I - The user of the \p U.
599/// Returns true if the value should be tracked transitively.
600///
601template <class AAType, typename StateType = typename AAType::StateType>
602static void followUsesInMBEC(AAType &AA, Attributor &A, StateType &S,
603 Instruction &CtxI) {
604
605 // Container for (transitive) uses of the associated value.
607 for (const Use &U : AA.getIRPosition().getAssociatedValue().uses())
608 Uses.insert(&U);
609
611 A.getInfoCache().getMustBeExecutedContextExplorer();
612
613 followUsesInContext<AAType>(AA, A, Explorer, &CtxI, Uses, S);
614
615 if (S.isAtFixpoint())
616 return;
617
619 auto Pred = [&](const Instruction *I) {
620 if (const BranchInst *Br = dyn_cast<BranchInst>(I))
621 if (Br->isConditional())
622 BrInsts.push_back(Br);
623 return true;
624 };
625
626 // Here, accumulate conditional branch instructions in the context. We
627 // explore the child paths and collect the known states. The disjunction of
628 // those states can be merged to its own state. Let ParentState_i be a state
629 // to indicate the known information for an i-th branch instruction in the
630 // context. ChildStates are created for its successors respectively.
631 //
632 // ParentS_1 = ChildS_{1, 1} /\ ChildS_{1, 2} /\ ... /\ ChildS_{1, n_1}
633 // ParentS_2 = ChildS_{2, 1} /\ ChildS_{2, 2} /\ ... /\ ChildS_{2, n_2}
634 // ...
635 // ParentS_m = ChildS_{m, 1} /\ ChildS_{m, 2} /\ ... /\ ChildS_{m, n_m}
636 //
637 // Known State |= ParentS_1 \/ ParentS_2 \/... \/ ParentS_m
638 //
639 // FIXME: Currently, recursive branches are not handled. For example, we
640 // can't deduce that ptr must be dereferenced in below function.
641 //
642 // void f(int a, int c, int *ptr) {
643 // if(a)
644 // if (b) {
645 // *ptr = 0;
646 // } else {
647 // *ptr = 1;
648 // }
649 // else {
650 // if (b) {
651 // *ptr = 0;
652 // } else {
653 // *ptr = 1;
654 // }
655 // }
656 // }
657
658 Explorer.checkForAllContext(&CtxI, Pred);
659 for (const BranchInst *Br : BrInsts) {
660 StateType ParentState;
661
662 // The known state of the parent state is a conjunction of children's
663 // known states so it is initialized with a best state.
664 ParentState.indicateOptimisticFixpoint();
665
666 for (const BasicBlock *BB : Br->successors()) {
667 StateType ChildState;
668
669 size_t BeforeSize = Uses.size();
670 followUsesInContext(AA, A, Explorer, &BB->front(), Uses, ChildState);
671
672 // Erase uses which only appear in the child.
673 for (auto It = Uses.begin() + BeforeSize; It != Uses.end();)
674 It = Uses.erase(It);
675
676 ParentState &= ChildState;
677 }
678
679 // Use only known state.
680 S += ParentState;
681 }
682}
683} // namespace
684
685/// ------------------------ PointerInfo ---------------------------------------
686
687namespace llvm {
688namespace AA {
689namespace PointerInfo {
690
691struct State;
692
693} // namespace PointerInfo
694} // namespace AA
695
696/// Helper for AA::PointerInfo::Access DenseMap/Set usage.
697template <>
700 static inline Access getEmptyKey();
701 static inline Access getTombstoneKey();
702 static unsigned getHashValue(const Access &A);
703 static bool isEqual(const Access &LHS, const Access &RHS);
704};
705
706/// Helper that allows RangeTy as a key in a DenseMap.
707template <> struct DenseMapInfo<AA::RangeTy> {
708 static inline AA::RangeTy getEmptyKey() {
709 auto EmptyKey = DenseMapInfo<int64_t>::getEmptyKey();
710 return AA::RangeTy{EmptyKey, EmptyKey};
711 }
712
713 static inline AA::RangeTy getTombstoneKey() {
714 auto TombstoneKey = DenseMapInfo<int64_t>::getTombstoneKey();
715 return AA::RangeTy{TombstoneKey, TombstoneKey};
716 }
717
718 static unsigned getHashValue(const AA::RangeTy &Range) {
722 }
723
724 static bool isEqual(const AA::RangeTy &A, const AA::RangeTy B) {
725 return A == B;
726 }
727};
728
729/// Helper for AA::PointerInfo::Access DenseMap/Set usage ignoring everythign
730/// but the instruction
731struct AccessAsInstructionInfo : DenseMapInfo<Instruction *> {
734 static inline Access getEmptyKey();
735 static inline Access getTombstoneKey();
736 static unsigned getHashValue(const Access &A);
737 static bool isEqual(const Access &LHS, const Access &RHS);
738};
739
740} // namespace llvm
741
742/// A type to track pointer/struct usage and accesses for AAPointerInfo.
744 /// Return the best possible representable state.
745 static State getBestState(const State &SIS) { return State(); }
746
747 /// Return the worst possible representable state.
748 static State getWorstState(const State &SIS) {
749 State R;
750 R.indicatePessimisticFixpoint();
751 return R;
752 }
753
754 State() = default;
755 State(State &&SIS) = default;
756
757 const State &getAssumed() const { return *this; }
758
759 /// See AbstractState::isValidState().
760 bool isValidState() const override { return BS.isValidState(); }
761
762 /// See AbstractState::isAtFixpoint().
763 bool isAtFixpoint() const override { return BS.isAtFixpoint(); }
764
765 /// See AbstractState::indicateOptimisticFixpoint().
769 }
770
771 /// See AbstractState::indicatePessimisticFixpoint().
775 }
776
777 State &operator=(const State &R) {
778 if (this == &R)
779 return *this;
780 BS = R.BS;
781 AccessList = R.AccessList;
782 OffsetBins = R.OffsetBins;
783 RemoteIMap = R.RemoteIMap;
784 return *this;
785 }
786
788 if (this == &R)
789 return *this;
790 std::swap(BS, R.BS);
791 std::swap(AccessList, R.AccessList);
792 std::swap(OffsetBins, R.OffsetBins);
793 std::swap(RemoteIMap, R.RemoteIMap);
794 return *this;
795 }
796
797 /// Add a new Access to the state at offset \p Offset and with size \p Size.
798 /// The access is associated with \p I, writes \p Content (if anything), and
799 /// is of kind \p Kind. If an Access already exists for the same \p I and same
800 /// \p RemoteI, the two are combined, potentially losing information about
801 /// offset and size. The resulting access must now be moved from its original
802 /// OffsetBin to the bin for its new offset.
803 ///
804 /// \Returns CHANGED, if the state changed, UNCHANGED otherwise.
806 Instruction &I, std::optional<Value *> Content,
808 Instruction *RemoteI = nullptr);
809
811
814 const_bin_iterator end() const { return OffsetBins.end(); }
815
816 const AAPointerInfo::Access &getAccess(unsigned Index) const {
817 return AccessList[Index];
818 }
819
820protected:
821 // Every memory instruction results in an Access object. We maintain a list of
822 // all Access objects that we own, along with the following maps:
823 //
824 // - OffsetBins: RangeTy -> { Access }
825 // - RemoteIMap: RemoteI x LocalI -> Access
826 //
827 // A RemoteI is any instruction that accesses memory. RemoteI is different
828 // from LocalI if and only if LocalI is a call; then RemoteI is some
829 // instruction in the callgraph starting from LocalI. Multiple paths in the
830 // callgraph from LocalI to RemoteI may produce multiple accesses, but these
831 // are all combined into a single Access object. This may result in loss of
832 // information in RangeTy in the Access object.
836
837 /// See AAPointerInfo::forallInterferingAccesses.
839 AA::RangeTy Range,
840 function_ref<bool(const AAPointerInfo::Access &, bool)> CB) const {
841 if (!isValidState())
842 return false;
843
844 for (const auto &It : OffsetBins) {
845 AA::RangeTy ItRange = It.getFirst();
846 if (!Range.mayOverlap(ItRange))
847 continue;
848 bool IsExact = Range == ItRange && !Range.offsetOrSizeAreUnknown();
849 for (auto Index : It.getSecond()) {
850 auto &Access = AccessList[Index];
851 if (!CB(Access, IsExact))
852 return false;
853 }
854 }
855 return true;
856 }
857
858 /// See AAPointerInfo::forallInterferingAccesses.
860 Instruction &I,
861 function_ref<bool(const AAPointerInfo::Access &, bool)> CB,
862 AA::RangeTy &Range) const {
863 if (!isValidState())
864 return false;
865
866 auto LocalList = RemoteIMap.find(&I);
867 if (LocalList == RemoteIMap.end()) {
868 return true;
869 }
870
871 for (unsigned Index : LocalList->getSecond()) {
872 for (auto &R : AccessList[Index]) {
873 Range &= R;
874 if (Range.offsetAndSizeAreUnknown())
875 break;
876 }
877 }
878 return forallInterferingAccesses(Range, CB);
879 }
880
881private:
882 /// State to track fixpoint and validity.
883 BooleanState BS;
884};
885
888 std::optional<Value *> Content, AAPointerInfo::AccessKind Kind, Type *Ty,
889 Instruction *RemoteI) {
890 RemoteI = RemoteI ? RemoteI : &I;
891
892 // Check if we have an access for this instruction, if not, simply add it.
893 auto &LocalList = RemoteIMap[RemoteI];
894 bool AccExists = false;
895 unsigned AccIndex = AccessList.size();
896 for (auto Index : LocalList) {
897 auto &A = AccessList[Index];
898 if (A.getLocalInst() == &I) {
899 AccExists = true;
900 AccIndex = Index;
901 break;
902 }
903 }
904
905 auto AddToBins = [&](const AAPointerInfo::RangeList &ToAdd) {
907 if (ToAdd.size())
908 dbgs() << "[AAPointerInfo] Inserting access in new offset bins\n";
909 );
910
911 for (auto Key : ToAdd) {
912 LLVM_DEBUG(dbgs() << " key " << Key << "\n");
913 OffsetBins[Key].insert(AccIndex);
914 }
915 };
916
917 if (!AccExists) {
918 AccessList.emplace_back(&I, RemoteI, Ranges, Content, Kind, Ty);
919 assert((AccessList.size() == AccIndex + 1) &&
920 "New Access should have been at AccIndex");
921 LocalList.push_back(AccIndex);
922 AddToBins(AccessList[AccIndex].getRanges());
924 }
925
926 // Combine the new Access with the existing Access, and then update the
927 // mapping in the offset bins.
928 AAPointerInfo::Access Acc(&I, RemoteI, Ranges, Content, Kind, Ty);
929 auto &Current = AccessList[AccIndex];
930 auto Before = Current;
931 Current &= Acc;
932 if (Current == Before)
934
935 auto &ExistingRanges = Before.getRanges();
936 auto &NewRanges = Current.getRanges();
937
938 // Ranges that are in the old access but not the new access need to be removed
939 // from the offset bins.
941 AAPointerInfo::RangeList::set_difference(ExistingRanges, NewRanges, ToRemove);
943 if (ToRemove.size())
944 dbgs() << "[AAPointerInfo] Removing access from old offset bins\n";
945 );
946
947 for (auto Key : ToRemove) {
948 LLVM_DEBUG(dbgs() << " key " << Key << "\n");
949 assert(OffsetBins.count(Key) && "Existing Access must be in some bin.");
950 auto &Bin = OffsetBins[Key];
951 assert(Bin.count(AccIndex) &&
952 "Expected bin to actually contain the Access.");
953 Bin.erase(AccIndex);
954 }
955
956 // Ranges that are in the new access but not the old access need to be added
957 // to the offset bins.
959 AAPointerInfo::RangeList::set_difference(NewRanges, ExistingRanges, ToAdd);
960 AddToBins(ToAdd);
962}
963
964namespace {
965
966/// A helper containing a list of offsets computed for a Use. Ideally this
967/// list should be strictly ascending, but we ensure that only when we
968/// actually translate the list of offsets to a RangeList.
969struct OffsetInfo {
970 using VecTy = SmallVector<int64_t>;
971 using const_iterator = VecTy::const_iterator;
972 VecTy Offsets;
973
974 const_iterator begin() const { return Offsets.begin(); }
975 const_iterator end() const { return Offsets.end(); }
976
977 bool operator==(const OffsetInfo &RHS) const {
978 return Offsets == RHS.Offsets;
979 }
980
981 bool operator!=(const OffsetInfo &RHS) const { return !(*this == RHS); }
982
983 void insert(int64_t Offset) { Offsets.push_back(Offset); }
984 bool isUnassigned() const { return Offsets.size() == 0; }
985
986 bool isUnknown() const {
987 if (isUnassigned())
988 return false;
989 if (Offsets.size() == 1)
990 return Offsets.front() == AA::RangeTy::Unknown;
991 return false;
992 }
993
994 void setUnknown() {
995 Offsets.clear();
996 Offsets.push_back(AA::RangeTy::Unknown);
997 }
998
999 void addToAll(int64_t Inc) {
1000 for (auto &Offset : Offsets) {
1001 Offset += Inc;
1002 }
1003 }
1004
1005 /// Copy offsets from \p R into the current list.
1006 ///
1007 /// Ideally all lists should be strictly ascending, but we defer that to the
1008 /// actual use of the list. So we just blindly append here.
1009 void merge(const OffsetInfo &R) { Offsets.append(R.Offsets); }
1010};
1011
1012#ifndef NDEBUG
1013static raw_ostream &operator<<(raw_ostream &OS, const OffsetInfo &OI) {
1014 ListSeparator LS;
1015 OS << "[";
1016 for (auto Offset : OI) {
1017 OS << LS << Offset;
1018 }
1019 OS << "]";
1020 return OS;
1021}
1022#endif // NDEBUG
1023
1024struct AAPointerInfoImpl
1025 : public StateWrapper<AA::PointerInfo::State, AAPointerInfo> {
1027 AAPointerInfoImpl(const IRPosition &IRP, Attributor &A) : BaseTy(IRP) {}
1028
1029 /// See AbstractAttribute::getAsStr().
1030 const std::string getAsStr() const override {
1031 return std::string("PointerInfo ") +
1032 (isValidState() ? (std::string("#") +
1033 std::to_string(OffsetBins.size()) + " bins")
1034 : "<invalid>");
1035 }
1036
1037 /// See AbstractAttribute::manifest(...).
1038 ChangeStatus manifest(Attributor &A) override {
1039 return AAPointerInfo::manifest(A);
1040 }
1041
1042 bool forallInterferingAccesses(
1043 AA::RangeTy Range,
1044 function_ref<bool(const AAPointerInfo::Access &, bool)> CB)
1045 const override {
1046 return State::forallInterferingAccesses(Range, CB);
1047 }
1048
1049 bool forallInterferingAccesses(
1050 Attributor &A, const AbstractAttribute &QueryingAA, Instruction &I,
1051 bool FindInterferingWrites, bool FindInterferingReads,
1052 function_ref<bool(const Access &, bool)> UserCB, bool &HasBeenWrittenTo,
1053 AA::RangeTy &Range) const override {
1054 HasBeenWrittenTo = false;
1055
1056 SmallPtrSet<const Access *, 8> DominatingWrites;
1057 SmallVector<std::pair<const Access *, bool>, 8> InterferingAccesses;
1058
1059 Function &Scope = *I.getFunction();
1060 const auto &NoSyncAA = A.getAAFor<AANoSync>(
1061 QueryingAA, IRPosition::function(Scope), DepClassTy::OPTIONAL);
1062 const auto *ExecDomainAA = A.lookupAAFor<AAExecutionDomain>(
1063 IRPosition::function(Scope), &QueryingAA, DepClassTy::NONE);
1064 bool AllInSameNoSyncFn = NoSyncAA.isAssumedNoSync();
1065 bool InstIsExecutedByInitialThreadOnly =
1066 ExecDomainAA && ExecDomainAA->isExecutedByInitialThreadOnly(I);
1067 bool InstIsExecutedInAlignedRegion =
1068 ExecDomainAA && ExecDomainAA->isExecutedInAlignedRegion(A, I);
1069 if (InstIsExecutedInAlignedRegion || InstIsExecutedByInitialThreadOnly)
1070 A.recordDependence(*ExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
1071
1072 InformationCache &InfoCache = A.getInfoCache();
1073 bool IsThreadLocalObj =
1074 AA::isAssumedThreadLocalObject(A, getAssociatedValue(), *this);
1075
1076 // Helper to determine if we need to consider threading, which we cannot
1077 // right now. However, if the function is (assumed) nosync or the thread
1078 // executing all instructions is the main thread only we can ignore
1079 // threading. Also, thread-local objects do not require threading reasoning.
1080 // Finally, we can ignore threading if either access is executed in an
1081 // aligned region.
1082 auto CanIgnoreThreadingForInst = [&](const Instruction &I) -> bool {
1083 if (IsThreadLocalObj || AllInSameNoSyncFn)
1084 return true;
1085 const auto *FnExecDomainAA =
1086 I.getFunction() == &Scope
1087 ? ExecDomainAA
1088 : A.lookupAAFor<AAExecutionDomain>(
1089 IRPosition::function(*I.getFunction()), &QueryingAA,
1090 DepClassTy::NONE);
1091 if (!FnExecDomainAA)
1092 return false;
1093 if (InstIsExecutedInAlignedRegion ||
1094 FnExecDomainAA->isExecutedInAlignedRegion(A, I)) {
1095 A.recordDependence(*FnExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
1096 return true;
1097 }
1098 if (InstIsExecutedByInitialThreadOnly &&
1099 FnExecDomainAA->isExecutedByInitialThreadOnly(I)) {
1100 A.recordDependence(*FnExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
1101 return true;
1102 }
1103 return false;
1104 };
1105
1106 // Helper to determine if the access is executed by the same thread as the
1107 // given instruction, for now it is sufficient to avoid any potential
1108 // threading effects as we cannot deal with them anyway.
1109 auto CanIgnoreThreading = [&](const Access &Acc) -> bool {
1110 return CanIgnoreThreadingForInst(*Acc.getRemoteInst()) ||
1111 (Acc.getRemoteInst() != Acc.getLocalInst() &&
1112 CanIgnoreThreadingForInst(*Acc.getLocalInst()));
1113 };
1114
1115 // TODO: Use inter-procedural reachability and dominance.
1116 const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
1117 QueryingAA, IRPosition::function(Scope), DepClassTy::OPTIONAL);
1118
1119 const bool UseDominanceReasoning =
1120 FindInterferingWrites && NoRecurseAA.isKnownNoRecurse();
1121 const DominatorTree *DT =
1123
1124 // Helper to check if a value has "kernel lifetime", that is it will not
1125 // outlive a GPU kernel. This is true for shared, constant, and local
1126 // globals on AMD and NVIDIA GPUs.
1127 auto HasKernelLifetime = [&](Value *V, Module &M) {
1128 if (!AA::isGPU(M))
1129 return false;
1130 switch (AA::GPUAddressSpace(V->getType()->getPointerAddressSpace())) {
1131 case AA::GPUAddressSpace::Shared:
1132 case AA::GPUAddressSpace::Constant:
1133 case AA::GPUAddressSpace::Local:
1134 return true;
1135 default:
1136 return false;
1137 };
1138 };
1139
1140 // The IsLiveInCalleeCB will be used by the AA::isPotentiallyReachable query
1141 // to determine if we should look at reachability from the callee. For
1142 // certain pointers we know the lifetime and we do not have to step into the
1143 // callee to determine reachability as the pointer would be dead in the
1144 // callee. See the conditional initialization below.
1145 std::function<bool(const Function &)> IsLiveInCalleeCB;
1146
1147 if (auto *AI = dyn_cast<AllocaInst>(&getAssociatedValue())) {
1148 // If the alloca containing function is not recursive the alloca
1149 // must be dead in the callee.
1150 const Function *AIFn = AI->getFunction();
1151 const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
1152 *this, IRPosition::function(*AIFn), DepClassTy::OPTIONAL);
1153 if (NoRecurseAA.isAssumedNoRecurse()) {
1154 IsLiveInCalleeCB = [AIFn](const Function &Fn) { return AIFn != &Fn; };
1155 }
1156 } else if (auto *GV = dyn_cast<GlobalValue>(&getAssociatedValue())) {
1157 // If the global has kernel lifetime we can stop if we reach a kernel
1158 // as it is "dead" in the (unknown) callees.
1159 if (HasKernelLifetime(GV, *GV->getParent()))
1160 IsLiveInCalleeCB = [](const Function &Fn) {
1161 return !Fn.hasFnAttribute("kernel");
1162 };
1163 }
1164
1165 // Set of accesses/instructions that will overwrite the result and are
1166 // therefore blockers in the reachability traversal.
1167 AA::InstExclusionSetTy ExclusionSet;
1168
1169 auto AccessCB = [&](const Access &Acc, bool Exact) {
1170 if (Exact && Acc.isMustAccess() && Acc.getRemoteInst() != &I) {
1171 if (Acc.isWrite() || (isa<LoadInst>(I) && Acc.isWriteOrAssumption()))
1172 ExclusionSet.insert(Acc.getRemoteInst());
1173 }
1174
1175 if ((!FindInterferingWrites || !Acc.isWriteOrAssumption()) &&
1176 (!FindInterferingReads || !Acc.isRead()))
1177 return true;
1178
1179 bool Dominates = FindInterferingWrites && DT && Exact &&
1180 Acc.isMustAccess() &&
1181 (Acc.getRemoteInst()->getFunction() == &Scope) &&
1182 DT->dominates(Acc.getRemoteInst(), &I);
1183 if (Dominates)
1184 DominatingWrites.insert(&Acc);
1185
1186 // Track if all interesting accesses are in the same `nosync` function as
1187 // the given instruction.
1188 AllInSameNoSyncFn &= Acc.getRemoteInst()->getFunction() == &Scope;
1189
1190 InterferingAccesses.push_back({&Acc, Exact});
1191 return true;
1192 };
1193 if (!State::forallInterferingAccesses(I, AccessCB, Range))
1194 return false;
1195
1196 HasBeenWrittenTo = !DominatingWrites.empty();
1197
1198 // Dominating writes form a chain, find the least/lowest member.
1199 Instruction *LeastDominatingWriteInst = nullptr;
1200 for (const Access *Acc : DominatingWrites) {
1201 if (!LeastDominatingWriteInst) {
1202 LeastDominatingWriteInst = Acc->getRemoteInst();
1203 } else if (DT->dominates(LeastDominatingWriteInst,
1204 Acc->getRemoteInst())) {
1205 LeastDominatingWriteInst = Acc->getRemoteInst();
1206 }
1207 }
1208
1209 // Helper to determine if we can skip a specific write access.
1210 auto CanSkipAccess = [&](const Access &Acc, bool Exact) {
1211 if (!CanIgnoreThreading(Acc))
1212 return false;
1213
1214 // Check read (RAW) dependences and write (WAR) dependences as necessary.
1215 // If we successfully excluded all effects we are interested in, the
1216 // access can be skipped.
1217 bool ReadChecked = !FindInterferingReads;
1218 bool WriteChecked = !FindInterferingWrites;
1219
1220 // If the instruction cannot reach the access, the former does not
1221 // interfere with what the access reads.
1222 if (!ReadChecked) {
1223 if (!AA::isPotentiallyReachable(A, I, *Acc.getRemoteInst(), QueryingAA,
1224 &ExclusionSet, IsLiveInCalleeCB))
1225 ReadChecked = true;
1226 }
1227 // If the instruction cannot be reach from the access, the latter does not
1228 // interfere with what the instruction reads.
1229 if (!WriteChecked) {
1230 if (!AA::isPotentiallyReachable(A, *Acc.getRemoteInst(), I, QueryingAA,
1231 &ExclusionSet, IsLiveInCalleeCB))
1232 WriteChecked = true;
1233 }
1234
1235 // If we still might be affected by the write of the access but there are
1236 // dominating writes in the function of the instruction
1237 // (HasBeenWrittenTo), we can try to reason that the access is overwritten
1238 // by them. This would have happend above if they are all in the same
1239 // function, so we only check the inter-procedural case. Effectively, we
1240 // want to show that there is no call after the dominting write that might
1241 // reach the access, and when it returns reach the instruction with the
1242 // updated value. To this end, we iterate all call sites, check if they
1243 // might reach the instruction without going through another access
1244 // (ExclusionSet) and at the same time might reach the access. However,
1245 // that is all part of AAInterFnReachability.
1246 if (!WriteChecked && HasBeenWrittenTo &&
1247 Acc.getRemoteInst()->getFunction() != &Scope) {
1248
1249 const auto &FnReachabilityAA = A.getAAFor<AAInterFnReachability>(
1250 QueryingAA, IRPosition::function(Scope), DepClassTy::OPTIONAL);
1251
1252 // Without going backwards in the call tree, can we reach the access
1253 // from the least dominating write. Do not allow to pass the instruction
1254 // itself either.
1255 bool Inserted = ExclusionSet.insert(&I).second;
1256
1257 if (!FnReachabilityAA.instructionCanReach(
1258 A, *LeastDominatingWriteInst,
1259 *Acc.getRemoteInst()->getFunction(), &ExclusionSet))
1260 WriteChecked = true;
1261
1262 if (Inserted)
1263 ExclusionSet.erase(&I);
1264 }
1265
1266 if (ReadChecked && WriteChecked)
1267 return true;
1268
1269 if (!DT || !UseDominanceReasoning)
1270 return false;
1271 if (!DominatingWrites.count(&Acc))
1272 return false;
1273 return LeastDominatingWriteInst != Acc.getRemoteInst();
1274 };
1275
1276 // Run the user callback on all accesses we cannot skip and return if
1277 // that succeeded for all or not.
1278 for (auto &It : InterferingAccesses) {
1279 if ((!AllInSameNoSyncFn && !IsThreadLocalObj && !ExecDomainAA) ||
1280 !CanSkipAccess(*It.first, It.second)) {
1281 if (!UserCB(*It.first, It.second))
1282 return false;
1283 }
1284 }
1285 return true;
1286 }
1287
1288 ChangeStatus translateAndAddStateFromCallee(Attributor &A,
1289 const AAPointerInfo &OtherAA,
1290 CallBase &CB) {
1291 using namespace AA::PointerInfo;
1292 if (!OtherAA.getState().isValidState() || !isValidState())
1293 return indicatePessimisticFixpoint();
1294
1295 const auto &OtherAAImpl = static_cast<const AAPointerInfoImpl &>(OtherAA);
1296 bool IsByval = OtherAAImpl.getAssociatedArgument()->hasByValAttr();
1297
1298 // Combine the accesses bin by bin.
1299 ChangeStatus Changed = ChangeStatus::UNCHANGED;
1300 const auto &State = OtherAAImpl.getState();
1301 for (const auto &It : State) {
1302 for (auto Index : It.getSecond()) {
1303 const auto &RAcc = State.getAccess(Index);
1304 if (IsByval && !RAcc.isRead())
1305 continue;
1306 bool UsedAssumedInformation = false;
1307 AccessKind AK = RAcc.getKind();
1308 auto Content = A.translateArgumentToCallSiteContent(
1309 RAcc.getContent(), CB, *this, UsedAssumedInformation);
1310 AK = AccessKind(AK & (IsByval ? AccessKind::AK_R : AccessKind::AK_RW));
1311 AK = AccessKind(AK | (RAcc.isMayAccess() ? AK_MAY : AK_MUST));
1312
1313 Changed |= addAccess(A, RAcc.getRanges(), CB, Content, AK,
1314 RAcc.getType(), RAcc.getRemoteInst());
1315 }
1316 }
1317 return Changed;
1318 }
1319
1320 ChangeStatus translateAndAddState(Attributor &A, const AAPointerInfo &OtherAA,
1321 const OffsetInfo &Offsets, CallBase &CB) {
1322 using namespace AA::PointerInfo;
1323 if (!OtherAA.getState().isValidState() || !isValidState())
1324 return indicatePessimisticFixpoint();
1325
1326 const auto &OtherAAImpl = static_cast<const AAPointerInfoImpl &>(OtherAA);
1327
1328 // Combine the accesses bin by bin.
1329 ChangeStatus Changed = ChangeStatus::UNCHANGED;
1330 const auto &State = OtherAAImpl.getState();
1331 for (const auto &It : State) {
1332 for (auto Index : It.getSecond()) {
1333 const auto &RAcc = State.getAccess(Index);
1334 for (auto Offset : Offsets) {
1335 auto NewRanges = Offset == AA::RangeTy::Unknown
1337 : RAcc.getRanges();
1338 if (!NewRanges.isUnknown()) {
1339 NewRanges.addToAllOffsets(Offset);
1340 }
1341 Changed |=
1342 addAccess(A, NewRanges, CB, RAcc.getContent(), RAcc.getKind(),
1343 RAcc.getType(), RAcc.getRemoteInst());
1344 }
1345 }
1346 }
1347 return Changed;
1348 }
1349
1350 /// Statistic tracking for all AAPointerInfo implementations.
1351 /// See AbstractAttribute::trackStatistics().
1352 void trackPointerInfoStatistics(const IRPosition &IRP) const {}
1353
1354 /// Dump the state into \p O.
1355 void dumpState(raw_ostream &O) {
1356 for (auto &It : OffsetBins) {
1357 O << "[" << It.first.Offset << "-" << It.first.Offset + It.first.Size
1358 << "] : " << It.getSecond().size() << "\n";
1359 for (auto AccIndex : It.getSecond()) {
1360 auto &Acc = AccessList[AccIndex];
1361 O << " - " << Acc.getKind() << " - " << *Acc.getLocalInst() << "\n";
1362 if (Acc.getLocalInst() != Acc.getRemoteInst())
1363 O << " --> " << *Acc.getRemoteInst()
1364 << "\n";
1365 if (!Acc.isWrittenValueYetUndetermined()) {
1366 if (isa_and_nonnull<Function>(Acc.getWrittenValue()))
1367 O << " - c: func " << Acc.getWrittenValue()->getName()
1368 << "\n";
1369 else if (Acc.getWrittenValue())
1370 O << " - c: " << *Acc.getWrittenValue() << "\n";
1371 else
1372 O << " - c: <unknown>\n";
1373 }
1374 }
1375 }
1376 }
1377};
1378
1379struct AAPointerInfoFloating : public AAPointerInfoImpl {
1381 AAPointerInfoFloating(const IRPosition &IRP, Attributor &A)
1382 : AAPointerInfoImpl(IRP, A) {}
1383
1384 /// Deal with an access and signal if it was handled successfully.
1385 bool handleAccess(Attributor &A, Instruction &I,
1386 std::optional<Value *> Content, AccessKind Kind,
1387 SmallVectorImpl<int64_t> &Offsets, ChangeStatus &Changed,
1388 Type &Ty) {
1389 using namespace AA::PointerInfo;
1391 const DataLayout &DL = A.getDataLayout();
1392 TypeSize AccessSize = DL.getTypeStoreSize(&Ty);
1393 if (!AccessSize.isScalable())
1394 Size = AccessSize.getFixedValue();
1395
1396 // Make a strictly ascending list of offsets as required by addAccess()
1397 llvm::sort(Offsets);
1398 auto *Last = std::unique(Offsets.begin(), Offsets.end());
1399 Offsets.erase(Last, Offsets.end());
1400
1401 VectorType *VT = dyn_cast<VectorType>(&Ty);
1402 if (!VT || VT->getElementCount().isScalable() ||
1403 !Content.value_or(nullptr) || !isa<Constant>(*Content) ||
1404 (*Content)->getType() != VT ||
1405 DL.getTypeStoreSize(VT->getElementType()).isScalable()) {
1406 Changed = Changed | addAccess(A, {Offsets, Size}, I, Content, Kind, &Ty);
1407 } else {
1408 // Handle vector stores with constant content element-wise.
1409 // TODO: We could look for the elements or create instructions
1410 // representing them.
1411 // TODO: We need to push the Content into the range abstraction
1412 // (AA::RangeTy) to allow different content values for different
1413 // ranges. ranges. Hence, support vectors storing different values.
1414 Type *ElementType = VT->getElementType();
1415 int64_t ElementSize = DL.getTypeStoreSize(ElementType).getFixedValue();
1416 auto *ConstContent = cast<Constant>(*Content);
1417 Type *Int32Ty = Type::getInt32Ty(ElementType->getContext());
1418 SmallVector<int64_t> ElementOffsets(Offsets.begin(), Offsets.end());
1419
1420 for (int i = 0, e = VT->getElementCount().getFixedValue(); i != e; ++i) {
1421 Value *ElementContent = ConstantExpr::getExtractElement(
1422 ConstContent, ConstantInt::get(Int32Ty, i));
1423
1424 // Add the element access.
1425 Changed = Changed | addAccess(A, {ElementOffsets, ElementSize}, I,
1426 ElementContent, Kind, ElementType);
1427
1428 // Advance the offsets for the next element.
1429 for (auto &ElementOffset : ElementOffsets)
1430 ElementOffset += ElementSize;
1431 }
1432 }
1433 return true;
1434 };
1435
1436 /// See AbstractAttribute::updateImpl(...).
1437 ChangeStatus updateImpl(Attributor &A) override;
1438
1439 /// If the indices to \p GEP can be traced to constants, incorporate all
1440 /// of these into \p UsrOI.
1441 ///
1442 /// \return true iff \p UsrOI is updated.
1443 bool collectConstantsForGEP(Attributor &A, const DataLayout &DL,
1444 OffsetInfo &UsrOI, const OffsetInfo &PtrOI,
1445 const GEPOperator *GEP);
1446
1447 /// See AbstractAttribute::trackStatistics()
1448 void trackStatistics() const override {
1449 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1450 }
1451};
1452
1453bool AAPointerInfoFloating::collectConstantsForGEP(Attributor &A,
1454 const DataLayout &DL,
1455 OffsetInfo &UsrOI,
1456 const OffsetInfo &PtrOI,
1457 const GEPOperator *GEP) {
1458 unsigned BitWidth = DL.getIndexTypeSizeInBits(GEP->getType());
1459 MapVector<Value *, APInt> VariableOffsets;
1460 APInt ConstantOffset(BitWidth, 0);
1461
1462 assert(!UsrOI.isUnknown() && !PtrOI.isUnknown() &&
1463 "Don't look for constant values if the offset has already been "
1464 "determined to be unknown.");
1465
1466 if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) {
1467 UsrOI.setUnknown();
1468 return true;
1469 }
1470
1471 LLVM_DEBUG(dbgs() << "[AAPointerInfo] GEP offset is "
1472 << (VariableOffsets.empty() ? "" : "not") << " constant "
1473 << *GEP << "\n");
1474
1475 auto Union = PtrOI;
1476 Union.addToAll(ConstantOffset.getSExtValue());
1477
1478 // Each VI in VariableOffsets has a set of potential constant values. Every
1479 // combination of elements, picked one each from these sets, is separately
1480 // added to the original set of offsets, thus resulting in more offsets.
1481 for (const auto &VI : VariableOffsets) {
1482 auto &PotentialConstantsAA = A.getAAFor<AAPotentialConstantValues>(
1483 *this, IRPosition::value(*VI.first), DepClassTy::OPTIONAL);
1484 if (!PotentialConstantsAA.isValidState()) {
1485 UsrOI.setUnknown();
1486 return true;
1487 }
1488
1489 // UndefValue is treated as a zero, which leaves Union as is.
1490 if (PotentialConstantsAA.undefIsContained())
1491 continue;
1492
1493 // We need at least one constant in every set to compute an actual offset.
1494 // Otherwise, we end up pessimizing AAPointerInfo by respecting offsets that
1495 // don't actually exist. In other words, the absence of constant values
1496 // implies that the operation can be assumed dead for now.
1497 auto &AssumedSet = PotentialConstantsAA.getAssumedSet();
1498 if (AssumedSet.empty())
1499 return false;
1500
1501 OffsetInfo Product;
1502 for (const auto &ConstOffset : AssumedSet) {
1503 auto CopyPerOffset = Union;
1504 CopyPerOffset.addToAll(ConstOffset.getSExtValue() *
1505 VI.second.getZExtValue());
1506 Product.merge(CopyPerOffset);
1507 }
1508 Union = Product;
1509 }
1510
1511 UsrOI = std::move(Union);
1512 return true;
1513}
1514
1515ChangeStatus AAPointerInfoFloating::updateImpl(Attributor &A) {
1516 using namespace AA::PointerInfo;
1518 const DataLayout &DL = A.getDataLayout();
1519 Value &AssociatedValue = getAssociatedValue();
1520
1521 DenseMap<Value *, OffsetInfo> OffsetInfoMap;
1522 OffsetInfoMap[&AssociatedValue].insert(0);
1523
1524 auto HandlePassthroughUser = [&](Value *Usr, Value *CurPtr, bool &Follow) {
1525 // One does not simply walk into a map and assign a reference to a possibly
1526 // new location. That can cause an invalidation before the assignment
1527 // happens, like so:
1528 //
1529 // OffsetInfoMap[Usr] = OffsetInfoMap[CurPtr]; /* bad idea! */
1530 //
1531 // The RHS is a reference that may be invalidated by an insertion caused by
1532 // the LHS. So we ensure that the side-effect of the LHS happens first.
1533 auto &UsrOI = OffsetInfoMap[Usr];
1534 auto &PtrOI = OffsetInfoMap[CurPtr];
1535 assert(!PtrOI.isUnassigned() &&
1536 "Cannot pass through if the input Ptr was not visited!");
1537 UsrOI = PtrOI;
1538 Follow = true;
1539 return true;
1540 };
1541
1542 const auto *F = getAnchorScope();
1543 const auto *CI =
1544 F ? A.getInfoCache().getAnalysisResultForFunction<CycleAnalysis>(*F)
1545 : nullptr;
1546 const auto *TLI =
1547 F ? A.getInfoCache().getTargetLibraryInfoForFunction(*F) : nullptr;
1548
1549 auto UsePred = [&](const Use &U, bool &Follow) -> bool {
1550 Value *CurPtr = U.get();
1551 User *Usr = U.getUser();
1552 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Analyze " << *CurPtr << " in " << *Usr
1553 << "\n");
1554 assert(OffsetInfoMap.count(CurPtr) &&
1555 "The current pointer offset should have been seeded!");
1556
1557 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Usr)) {
1558 if (CE->isCast())
1559 return HandlePassthroughUser(Usr, CurPtr, Follow);
1560 if (CE->isCompare())
1561 return true;
1562 if (!isa<GEPOperator>(CE)) {
1563 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Unhandled constant user " << *CE
1564 << "\n");
1565 return false;
1566 }
1567 }
1568 if (auto *GEP = dyn_cast<GEPOperator>(Usr)) {
1569 // Note the order here, the Usr access might change the map, CurPtr is
1570 // already in it though.
1571 auto &UsrOI = OffsetInfoMap[Usr];
1572 auto &PtrOI = OffsetInfoMap[CurPtr];
1573
1574 if (UsrOI.isUnknown())
1575 return true;
1576
1577 if (PtrOI.isUnknown()) {
1578 Follow = true;
1579 UsrOI.setUnknown();
1580 return true;
1581 }
1582
1583 Follow = collectConstantsForGEP(A, DL, UsrOI, PtrOI, GEP);
1584 return true;
1585 }
1586 if (isa<PtrToIntInst>(Usr))
1587 return false;
1588 if (isa<CastInst>(Usr) || isa<SelectInst>(Usr) || isa<ReturnInst>(Usr))
1589 return HandlePassthroughUser(Usr, CurPtr, Follow);
1590
1591 // For PHIs we need to take care of the recurrence explicitly as the value
1592 // might change while we iterate through a loop. For now, we give up if
1593 // the PHI is not invariant.
1594 if (isa<PHINode>(Usr)) {
1595 // Note the order here, the Usr access might change the map, CurPtr is
1596 // already in it though.
1597 bool IsFirstPHIUser = !OffsetInfoMap.count(Usr);
1598 auto &UsrOI = OffsetInfoMap[Usr];
1599 auto &PtrOI = OffsetInfoMap[CurPtr];
1600
1601 // Check if the PHI operand has already an unknown offset as we can't
1602 // improve on that anymore.
1603 if (PtrOI.isUnknown()) {
1604 LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI operand offset unknown "
1605 << *CurPtr << " in " << *Usr << "\n");
1606 Follow = !UsrOI.isUnknown();
1607 UsrOI.setUnknown();
1608 return true;
1609 }
1610
1611 // Check if the PHI is invariant (so far).
1612 if (UsrOI == PtrOI) {
1613 assert(!PtrOI.isUnassigned() &&
1614 "Cannot assign if the current Ptr was not visited!");
1615 LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI is invariant (so far)");
1616 return true;
1617 }
1618
1619 // Check if the PHI operand can be traced back to AssociatedValue.
1620 APInt Offset(
1621 DL.getIndexSizeInBits(CurPtr->getType()->getPointerAddressSpace()),
1622 0);
1623 Value *CurPtrBase = CurPtr->stripAndAccumulateConstantOffsets(
1624 DL, Offset, /* AllowNonInbounds */ true);
1625 auto It = OffsetInfoMap.find(CurPtrBase);
1626 if (It == OffsetInfoMap.end()) {
1627 LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI operand is too complex "
1628 << *CurPtr << " in " << *Usr << "\n");
1629 UsrOI.setUnknown();
1630 Follow = true;
1631 return true;
1632 }
1633
1634 // Check if the PHI operand is not dependent on the PHI itself. Every
1635 // recurrence is a cyclic net of PHIs in the data flow, and has an
1636 // equivalent Cycle in the control flow. One of those PHIs must be in the
1637 // header of that control flow Cycle. This is independent of the choice of
1638 // Cycles reported by CycleInfo. It is sufficient to check the PHIs in
1639 // every Cycle header; if such a node is marked unknown, this will
1640 // eventually propagate through the whole net of PHIs in the recurrence.
1641 if (mayBeInCycle(CI, cast<Instruction>(Usr), /* HeaderOnly */ true)) {
1642 auto BaseOI = It->getSecond();
1643 BaseOI.addToAll(Offset.getZExtValue());
1644 if (IsFirstPHIUser || BaseOI == UsrOI) {
1645 LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI is invariant " << *CurPtr
1646 << " in " << *Usr << "\n");
1647 return HandlePassthroughUser(Usr, CurPtr, Follow);
1648 }
1649
1650 LLVM_DEBUG(
1651 dbgs() << "[AAPointerInfo] PHI operand pointer offset mismatch "
1652 << *CurPtr << " in " << *Usr << "\n");
1653 UsrOI.setUnknown();
1654 Follow = true;
1655 return true;
1656 }
1657
1658 UsrOI.merge(PtrOI);
1659 Follow = true;
1660 return true;
1661 }
1662
1663 if (auto *LoadI = dyn_cast<LoadInst>(Usr)) {
1664 // If the access is to a pointer that may or may not be the associated
1665 // value, e.g. due to a PHI, we cannot assume it will be read.
1666 AccessKind AK = AccessKind::AK_R;
1667 if (getUnderlyingObject(CurPtr) == &AssociatedValue)
1668 AK = AccessKind(AK | AccessKind::AK_MUST);
1669 else
1670 AK = AccessKind(AK | AccessKind::AK_MAY);
1671 if (!handleAccess(A, *LoadI, /* Content */ nullptr, AK,
1672 OffsetInfoMap[CurPtr].Offsets, Changed,
1673 *LoadI->getType()))
1674 return false;
1675
1676 auto IsAssumption = [](Instruction &I) {
1677 if (auto *II = dyn_cast<IntrinsicInst>(&I))
1678 return II->isAssumeLikeIntrinsic();
1679 return false;
1680 };
1681
1682 auto IsImpactedInRange = [&](Instruction *FromI, Instruction *ToI) {
1683 // Check if the assumption and the load are executed together without
1684 // memory modification.
1685 do {
1686 if (FromI->mayWriteToMemory() && !IsAssumption(*FromI))
1687 return true;
1688 FromI = FromI->getNextNonDebugInstruction();
1689 } while (FromI && FromI != ToI);
1690 return false;
1691 };
1692
1693 BasicBlock *BB = LoadI->getParent();
1694 auto IsValidAssume = [&](IntrinsicInst &IntrI) {
1695 if (IntrI.getIntrinsicID() != Intrinsic::assume)
1696 return false;
1697 BasicBlock *IntrBB = IntrI.getParent();
1698 if (IntrI.getParent() == BB) {
1699 if (IsImpactedInRange(LoadI->getNextNonDebugInstruction(), &IntrI))
1700 return false;
1701 } else {
1702 auto PredIt = pred_begin(IntrBB);
1703 if (PredIt == pred_end(IntrBB))
1704 return false;
1705 if ((*PredIt) != BB)
1706 return false;
1707 if (++PredIt != pred_end(IntrBB))
1708 return false;
1709 for (auto *SuccBB : successors(BB)) {
1710 if (SuccBB == IntrBB)
1711 continue;
1712 if (isa<UnreachableInst>(SuccBB->getTerminator()))
1713 continue;
1714 return false;
1715 }
1716 if (IsImpactedInRange(LoadI->getNextNonDebugInstruction(),
1717 BB->getTerminator()))
1718 return false;
1719 if (IsImpactedInRange(&IntrBB->front(), &IntrI))
1720 return false;
1721 }
1722 return true;
1723 };
1724
1725 std::pair<Value *, IntrinsicInst *> Assumption;
1726 for (const Use &LoadU : LoadI->uses()) {
1727 if (auto *CmpI = dyn_cast<CmpInst>(LoadU.getUser())) {
1728 if (!CmpI->isEquality() || !CmpI->isTrueWhenEqual())
1729 continue;
1730 for (const Use &CmpU : CmpI->uses()) {
1731 if (auto *IntrI = dyn_cast<IntrinsicInst>(CmpU.getUser())) {
1732 if (!IsValidAssume(*IntrI))
1733 continue;
1734 int Idx = CmpI->getOperandUse(0) == LoadU;
1735 Assumption = {CmpI->getOperand(Idx), IntrI};
1736 break;
1737 }
1738 }
1739 }
1740 if (Assumption.first)
1741 break;
1742 }
1743
1744 // Check if we found an assumption associated with this load.
1745 if (!Assumption.first || !Assumption.second)
1746 return true;
1747
1748 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Assumption found "
1749 << *Assumption.second << ": " << *LoadI
1750 << " == " << *Assumption.first << "\n");
1751
1752 return handleAccess(
1753 A, *Assumption.second, Assumption.first, AccessKind::AK_ASSUMPTION,
1754 OffsetInfoMap[CurPtr].Offsets, Changed, *LoadI->getType());
1755 }
1756
1757 auto HandleStoreLike = [&](Instruction &I, Value *ValueOp, Type &ValueTy,
1758 ArrayRef<Value *> OtherOps, AccessKind AK) {
1759 for (auto *OtherOp : OtherOps) {
1760 if (OtherOp == CurPtr) {
1761 LLVM_DEBUG(
1762 dbgs()
1763 << "[AAPointerInfo] Escaping use in store like instruction " << I
1764 << "\n");
1765 return false;
1766 }
1767 }
1768
1769 // If the access is to a pointer that may or may not be the associated
1770 // value, e.g. due to a PHI, we cannot assume it will be written.
1771 if (getUnderlyingObject(CurPtr) == &AssociatedValue)
1772 AK = AccessKind(AK | AccessKind::AK_MUST);
1773 else
1774 AK = AccessKind(AK | AccessKind::AK_MAY);
1775 bool UsedAssumedInformation = false;
1776 std::optional<Value *> Content = nullptr;
1777 if (ValueOp)
1778 Content = A.getAssumedSimplified(
1779 *ValueOp, *this, UsedAssumedInformation, AA::Interprocedural);
1780 return handleAccess(A, I, Content, AK, OffsetInfoMap[CurPtr].Offsets,
1781 Changed, ValueTy);
1782 };
1783
1784 if (auto *StoreI = dyn_cast<StoreInst>(Usr))
1785 return HandleStoreLike(*StoreI, StoreI->getValueOperand(),
1786 *StoreI->getValueOperand()->getType(),
1787 {StoreI->getValueOperand()}, AccessKind::AK_W);
1788 if (auto *RMWI = dyn_cast<AtomicRMWInst>(Usr))
1789 return HandleStoreLike(*RMWI, nullptr, *RMWI->getValOperand()->getType(),
1790 {RMWI->getValOperand()}, AccessKind::AK_RW);
1791 if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(Usr))
1792 return HandleStoreLike(
1793 *CXI, nullptr, *CXI->getNewValOperand()->getType(),
1794 {CXI->getCompareOperand(), CXI->getNewValOperand()},
1795 AccessKind::AK_RW);
1796
1797 if (auto *CB = dyn_cast<CallBase>(Usr)) {
1798 if (CB->isLifetimeStartOrEnd())
1799 return true;
1800 if (getFreedOperand(CB, TLI) == U)
1801 return true;
1802 if (CB->isArgOperand(&U)) {
1803 unsigned ArgNo = CB->getArgOperandNo(&U);
1804 const auto &CSArgPI = A.getAAFor<AAPointerInfo>(
1805 *this, IRPosition::callsite_argument(*CB, ArgNo),
1807 Changed = translateAndAddState(A, CSArgPI, OffsetInfoMap[CurPtr], *CB) |
1808 Changed;
1809 return isValidState();
1810 }
1811 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Call user not handled " << *CB
1812 << "\n");
1813 // TODO: Allow some call uses
1814 return false;
1815 }
1816
1817 LLVM_DEBUG(dbgs() << "[AAPointerInfo] User not handled " << *Usr << "\n");
1818 return false;
1819 };
1820 auto EquivalentUseCB = [&](const Use &OldU, const Use &NewU) {
1821 assert(OffsetInfoMap.count(OldU) && "Old use should be known already!");
1822 if (OffsetInfoMap.count(NewU)) {
1823 LLVM_DEBUG({
1824 if (!(OffsetInfoMap[NewU] == OffsetInfoMap[OldU])) {
1825 dbgs() << "[AAPointerInfo] Equivalent use callback failed: "
1826 << OffsetInfoMap[NewU] << " vs " << OffsetInfoMap[OldU]
1827 << "\n";
1828 }
1829 });
1830 return OffsetInfoMap[NewU] == OffsetInfoMap[OldU];
1831 }
1832 OffsetInfoMap[NewU] = OffsetInfoMap[OldU];
1833 return true;
1834 };
1835 if (!A.checkForAllUses(UsePred, *this, AssociatedValue,
1836 /* CheckBBLivenessOnly */ true, DepClassTy::OPTIONAL,
1837 /* IgnoreDroppableUses */ true, EquivalentUseCB)) {
1838 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Check for all uses failed, abort!\n");
1839 return indicatePessimisticFixpoint();
1840 }
1841
1842 LLVM_DEBUG({
1843 dbgs() << "Accesses by bin after update:\n";
1844 dumpState(dbgs());
1845 });
1846
1847 return Changed;
1848}
1849
1850struct AAPointerInfoReturned final : AAPointerInfoImpl {
1851 AAPointerInfoReturned(const IRPosition &IRP, Attributor &A)
1852 : AAPointerInfoImpl(IRP, A) {}
1853
1854 /// See AbstractAttribute::updateImpl(...).
1855 ChangeStatus updateImpl(Attributor &A) override {
1856 return indicatePessimisticFixpoint();
1857 }
1858
1859 /// See AbstractAttribute::trackStatistics()
1860 void trackStatistics() const override {
1861 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1862 }
1863};
1864
1865struct AAPointerInfoArgument final : AAPointerInfoFloating {
1866 AAPointerInfoArgument(const IRPosition &IRP, Attributor &A)
1867 : AAPointerInfoFloating(IRP, A) {}
1868
1869 /// See AbstractAttribute::initialize(...).
1870 void initialize(Attributor &A) override {
1871 AAPointerInfoFloating::initialize(A);
1872 if (getAnchorScope()->isDeclaration())
1873 indicatePessimisticFixpoint();
1874 }
1875
1876 /// See AbstractAttribute::trackStatistics()
1877 void trackStatistics() const override {
1878 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1879 }
1880};
1881
1882struct AAPointerInfoCallSiteArgument final : AAPointerInfoFloating {
1883 AAPointerInfoCallSiteArgument(const IRPosition &IRP, Attributor &A)
1884 : AAPointerInfoFloating(IRP, A) {}
1885
1886 /// See AbstractAttribute::updateImpl(...).
1887 ChangeStatus updateImpl(Attributor &A) override {
1888 using namespace AA::PointerInfo;
1889 // We handle memory intrinsics explicitly, at least the first (=
1890 // destination) and second (=source) arguments as we know how they are
1891 // accessed.
1892 if (auto *MI = dyn_cast_or_null<MemIntrinsic>(getCtxI())) {
1893 ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
1894 int64_t LengthVal = AA::RangeTy::Unknown;
1895 if (Length)
1896 LengthVal = Length->getSExtValue();
1897 unsigned ArgNo = getIRPosition().getCallSiteArgNo();
1898 ChangeStatus Changed = ChangeStatus::UNCHANGED;
1899 if (ArgNo > 1) {
1900 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Unhandled memory intrinsic "
1901 << *MI << "\n");
1902 return indicatePessimisticFixpoint();
1903 } else {
1904 auto Kind =
1905 ArgNo == 0 ? AccessKind::AK_MUST_WRITE : AccessKind::AK_MUST_READ;
1906 Changed =
1907 Changed | addAccess(A, {0, LengthVal}, *MI, nullptr, Kind, nullptr);
1908 }
1909 LLVM_DEBUG({
1910 dbgs() << "Accesses by bin after update:\n";
1911 dumpState(dbgs());
1912 });
1913
1914 return Changed;
1915 }
1916
1917 // TODO: Once we have call site specific value information we can provide
1918 // call site specific liveness information and then it makes
1919 // sense to specialize attributes for call sites arguments instead of
1920 // redirecting requests to the callee argument.
1921 Argument *Arg = getAssociatedArgument();
1922 if (Arg) {
1923 const IRPosition &ArgPos = IRPosition::argument(*Arg);
1924 auto &ArgAA =
1925 A.getAAFor<AAPointerInfo>(*this, ArgPos, DepClassTy::REQUIRED);
1926 if (ArgAA.getState().isValidState())
1927 return translateAndAddStateFromCallee(A, ArgAA,
1928 *cast<CallBase>(getCtxI()));
1929 if (!Arg->getParent()->isDeclaration())
1930 return indicatePessimisticFixpoint();
1931 }
1932
1933 const auto &NoCaptureAA =
1934 A.getAAFor<AANoCapture>(*this, getIRPosition(), DepClassTy::OPTIONAL);
1935
1936 if (!NoCaptureAA.isAssumedNoCapture())
1937 return indicatePessimisticFixpoint();
1938
1939 bool IsKnown = false;
1940 if (AA::isAssumedReadNone(A, getIRPosition(), *this, IsKnown))
1941 return ChangeStatus::UNCHANGED;
1942 bool ReadOnly = AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown);
1943 auto Kind =
1944 ReadOnly ? AccessKind::AK_MAY_READ : AccessKind::AK_MAY_READ_WRITE;
1945 return addAccess(A, AA::RangeTy::getUnknown(), *getCtxI(), nullptr, Kind,
1946 nullptr);
1947 }
1948
1949 /// See AbstractAttribute::trackStatistics()
1950 void trackStatistics() const override {
1951 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1952 }
1953};
1954
1955struct AAPointerInfoCallSiteReturned final : AAPointerInfoFloating {
1956 AAPointerInfoCallSiteReturned(const IRPosition &IRP, Attributor &A)
1957 : AAPointerInfoFloating(IRP, A) {}
1958
1959 /// See AbstractAttribute::trackStatistics()
1960 void trackStatistics() const override {
1961 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1962 }
1963};
1964} // namespace
1965
1966/// -----------------------NoUnwind Function Attribute--------------------------
1967
1968namespace {
1969struct AANoUnwindImpl : AANoUnwind {
1970 AANoUnwindImpl(const IRPosition &IRP, Attributor &A) : AANoUnwind(IRP, A) {}
1971
1972 const std::string getAsStr() const override {
1973 return getAssumed() ? "nounwind" : "may-unwind";
1974 }
1975
1976 /// See AbstractAttribute::updateImpl(...).
1977 ChangeStatus updateImpl(Attributor &A) override {
1978 auto Opcodes = {
1979 (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
1980 (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet,
1981 (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
1982
1983 auto CheckForNoUnwind = [&](Instruction &I) {
1984 if (!I.mayThrow(/* IncludePhaseOneUnwind */ true))
1985 return true;
1986
1987 if (const auto *CB = dyn_cast<CallBase>(&I)) {
1988 const auto &NoUnwindAA = A.getAAFor<AANoUnwind>(
1989 *this, IRPosition::callsite_function(*CB), DepClassTy::REQUIRED);
1990 return NoUnwindAA.isAssumedNoUnwind();
1991 }
1992 return false;
1993 };
1994
1995 bool UsedAssumedInformation = false;
1996 if (!A.checkForAllInstructions(CheckForNoUnwind, *this, Opcodes,
1997 UsedAssumedInformation))
1998 return indicatePessimisticFixpoint();
1999
2000 return ChangeStatus::UNCHANGED;
2001 }
2002};
2003
2004struct AANoUnwindFunction final : public AANoUnwindImpl {
2005 AANoUnwindFunction(const IRPosition &IRP, Attributor &A)
2006 : AANoUnwindImpl(IRP, A) {}
2007
2008 /// See AbstractAttribute::trackStatistics()
2009 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nounwind) }
2010};
2011
2012/// NoUnwind attribute deduction for a call sites.
2013struct AANoUnwindCallSite final : AANoUnwindImpl {
2014 AANoUnwindCallSite(const IRPosition &IRP, Attributor &A)
2015 : AANoUnwindImpl(IRP, A) {}
2016
2017 /// See AbstractAttribute::initialize(...).
2018 void initialize(Attributor &A) override {
2019 AANoUnwindImpl::initialize(A);
2020 Function *F = getAssociatedFunction();
2021 if (!F || F->isDeclaration())
2022 indicatePessimisticFixpoint();
2023 }
2024
2025 /// See AbstractAttribute::updateImpl(...).
2026 ChangeStatus updateImpl(Attributor &A) override {
2027 // TODO: Once we have call site specific value information we can provide
2028 // call site specific liveness information and then it makes
2029 // sense to specialize attributes for call sites arguments instead of
2030 // redirecting requests to the callee argument.
2031 Function *F = getAssociatedFunction();
2032 const IRPosition &FnPos = IRPosition::function(*F);
2033 auto &FnAA = A.getAAFor<AANoUnwind>(*this, FnPos, DepClassTy::REQUIRED);
2034 return clampStateAndIndicateChange(getState(), FnAA.getState());
2035 }
2036
2037 /// See AbstractAttribute::trackStatistics()
2038 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nounwind); }
2039};
2040} // namespace
2041
2042/// --------------------- Function Return Values -------------------------------
2043
2044namespace {
2045/// "Attribute" that collects all potential returned values and the return
2046/// instructions that they arise from.
2047///
2048/// If there is a unique returned value R, the manifest method will:
2049/// - mark R with the "returned" attribute, if R is an argument.
2050class AAReturnedValuesImpl : public AAReturnedValues, public AbstractState {
2051
2052 /// Mapping of values potentially returned by the associated function to the
2053 /// return instructions that might return them.
2055
2056 /// State flags
2057 ///
2058 ///{
2059 bool IsFixed = false;
2060 bool IsValidState = true;
2061 ///}
2062
2063public:
2064 AAReturnedValuesImpl(const IRPosition &IRP, Attributor &A)
2065 : AAReturnedValues(IRP, A) {}
2066
2067 /// See AbstractAttribute::initialize(...).
2068 void initialize(Attributor &A) override {
2069 // Reset the state.
2070 IsFixed = false;
2071 IsValidState = true;
2072 ReturnedValues.clear();
2073
2074 Function *F = getAssociatedFunction();
2075 if (!F || F->isDeclaration()) {
2076 indicatePessimisticFixpoint();
2077 return;
2078 }
2079 assert(!F->getReturnType()->isVoidTy() &&
2080 "Did not expect a void return type!");
2081
2082 // The map from instruction opcodes to those instructions in the function.
2083 auto &OpcodeInstMap = A.getInfoCache().getOpcodeInstMapForFunction(*F);
2084
2085 // Look through all arguments, if one is marked as returned we are done.
2086 for (Argument &Arg : F->args()) {
2087 if (Arg.hasReturnedAttr()) {
2088 auto &ReturnInstSet = ReturnedValues[&Arg];
2089 if (auto *Insts = OpcodeInstMap.lookup(Instruction::Ret))
2090 for (Instruction *RI : *Insts)
2091 ReturnInstSet.insert(cast<ReturnInst>(RI));
2092
2093 indicateOptimisticFixpoint();
2094 return;
2095 }
2096 }
2097
2098 if (!A.isFunctionIPOAmendable(*F))
2099 indicatePessimisticFixpoint();
2100 }
2101
2102 /// See AbstractAttribute::manifest(...).
2103 ChangeStatus manifest(Attributor &A) override;
2104
2105 /// See AbstractAttribute::getState(...).
2106 AbstractState &getState() override { return *this; }
2107
2108 /// See AbstractAttribute::getState(...).
2109 const AbstractState &getState() const override { return *this; }
2110
2111 /// See AbstractAttribute::updateImpl(Attributor &A).
2112 ChangeStatus updateImpl(Attributor &A) override;
2113
2114 llvm::iterator_range<iterator> returned_values() override {
2115 return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
2116 }
2117
2118 llvm::iterator_range<const_iterator> returned_values() const override {
2119 return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
2120 }
2121
2122 /// Return the number of potential return values, -1 if unknown.
2123 size_t getNumReturnValues() const override {
2124 return isValidState() ? ReturnedValues.size() : -1;
2125 }
2126
2127 /// Return an assumed unique return value if a single candidate is found. If
2128 /// there cannot be one, return a nullptr. If it is not clear yet, return
2129 /// std::nullopt.
2130 std::optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const;
2131
2132 /// See AbstractState::checkForAllReturnedValues(...).
2133 bool checkForAllReturnedValuesAndReturnInsts(
2134 function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
2135 const override;
2136
2137 /// Pretty print the attribute similar to the IR representation.
2138 const std::string getAsStr() const override;
2139
2140 /// See AbstractState::isAtFixpoint().
2141 bool isAtFixpoint() const override { return IsFixed; }
2142
2143 /// See AbstractState::isValidState().
2144 bool isValidState() const override { return IsValidState; }
2145
2146 /// See AbstractState::indicateOptimisticFixpoint(...).
2147 ChangeStatus indicateOptimisticFixpoint() override {
2148 IsFixed = true;
2149 return ChangeStatus::UNCHANGED;
2150 }
2151
2152 ChangeStatus indicatePessimisticFixpoint() override {
2153 IsFixed = true;
2154 IsValidState = false;
2155 return ChangeStatus::CHANGED;
2156 }
2157};
2158
2159ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
2161
2162 // Bookkeeping.
2163 assert(isValidState());
2164 STATS_DECLTRACK(KnownReturnValues, FunctionReturn,
2165 "Number of function with known return values");
2166
2167 // Check if we have an assumed unique return value that we could manifest.
2168 std::optional<Value *> UniqueRV = getAssumedUniqueReturnValue(A);
2169
2170 if (!UniqueRV || !*UniqueRV)
2171 return Changed;
2172
2173 // Bookkeeping.
2174 STATS_DECLTRACK(UniqueReturnValue, FunctionReturn,
2175 "Number of function with unique return");
2176 // If the assumed unique return value is an argument, annotate it.
2177 if (auto *UniqueRVArg = dyn_cast<Argument>(*UniqueRV)) {
2178 if (UniqueRVArg->getType()->canLosslesslyBitCastTo(
2179 getAssociatedFunction()->getReturnType())) {
2180 getIRPosition() = IRPosition::argument(*UniqueRVArg);
2181 Changed = IRAttribute::manifest(A);
2182 }
2183 }
2184 return Changed;
2185}
2186
2187const std::string AAReturnedValuesImpl::getAsStr() const {
2188 return (isAtFixpoint() ? "returns(#" : "may-return(#") +
2189 (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
2190}
2191
2192std::optional<Value *>
2193AAReturnedValuesImpl::getAssumedUniqueReturnValue(Attributor &A) const {
2194 // If checkForAllReturnedValues provides a unique value, ignoring potential
2195 // undef values that can also be present, it is assumed to be the actual
2196 // return value and forwarded to the caller of this method. If there are
2197 // multiple, a nullptr is returned indicating there cannot be a unique
2198 // returned value.
2199 std::optional<Value *> UniqueRV;
2200 Type *Ty = getAssociatedFunction()->getReturnType();
2201
2202 auto Pred = [&](Value &RV) -> bool {
2203 UniqueRV = AA::combineOptionalValuesInAAValueLatice(UniqueRV, &RV, Ty);
2204 return UniqueRV != std::optional<Value *>(nullptr);
2205 };
2206
2207 if (!A.checkForAllReturnedValues(Pred, *this))
2208 UniqueRV = nullptr;
2209
2210 return UniqueRV;
2211}
2212
2213bool AAReturnedValuesImpl::checkForAllReturnedValuesAndReturnInsts(
2214 function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
2215 const {
2216 if (!isValidState())
2217 return false;
2218
2219 // Check all returned values but ignore call sites as long as we have not
2220 // encountered an overdefined one during an update.
2221 for (const auto &It : ReturnedValues) {
2222 Value *RV = It.first;
2223 if (!Pred(*RV, It.second))
2224 return false;
2225 }
2226
2227 return true;
2228}
2229
2230ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
2232
2234 bool UsedAssumedInformation = false;
2235 auto ReturnInstCB = [&](Instruction &I) {
2236 ReturnInst &Ret = cast<ReturnInst>(I);
2237 Values.clear();
2238 if (!A.getAssumedSimplifiedValues(IRPosition::value(*Ret.getReturnValue()),
2239 *this, Values, AA::Intraprocedural,
2240 UsedAssumedInformation))
2241 Values.push_back({*Ret.getReturnValue(), Ret});
2242
2243 for (auto &VAC : Values) {
2244 assert(AA::isValidInScope(*VAC.getValue(), Ret.getFunction()) &&
2245 "Assumed returned value should be valid in function scope!");
2246 if (ReturnedValues[VAC.getValue()].insert(&Ret))
2247 Changed = ChangeStatus::CHANGED;
2248 }
2249 return true;
2250 };
2251
2252 // Discover returned values from all live returned instructions in the
2253 // associated function.
2254 if (!A.checkForAllInstructions(ReturnInstCB, *this, {Instruction::Ret},
2255 UsedAssumedInformation))
2256 return indicatePessimisticFixpoint();
2257 return Changed;
2258}
2259
2260struct AAReturnedValuesFunction final : public AAReturnedValuesImpl {
2261 AAReturnedValuesFunction(const IRPosition &IRP, Attributor &A)
2262 : AAReturnedValuesImpl(IRP, A) {}
2263
2264 /// See AbstractAttribute::trackStatistics()
2265 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(returned) }
2266};
2267
2268/// Returned values information for a call sites.
2269struct AAReturnedValuesCallSite final : AAReturnedValuesImpl {
2270 AAReturnedValuesCallSite(const IRPosition &IRP, Attributor &A)
2271 : AAReturnedValuesImpl(IRP, A) {}
2272
2273 /// See AbstractAttribute::initialize(...).
2274 void initialize(Attributor &A) override {
2275 // TODO: Once we have call site specific value information we can provide
2276 // call site specific liveness information and then it makes
2277 // sense to specialize attributes for call sites instead of
2278 // redirecting requests to the callee.
2279 llvm_unreachable("Abstract attributes for returned values are not "
2280 "supported for call sites yet!");
2281 }
2282
2283 /// See AbstractAttribute::updateImpl(...).
2284 ChangeStatus updateImpl(Attributor &A) override {
2285 return indicatePessimisticFixpoint();
2286 }
2287
2288 /// See AbstractAttribute::trackStatistics()
2289 void trackStatistics() const override {}
2290};
2291} // namespace
2292
2293/// ------------------------ NoSync Function Attribute -------------------------
2294
2295bool AANoSync::isAlignedBarrier(const CallBase &CB, bool ExecutedAligned) {
2296 switch (CB.getIntrinsicID()) {
2297 case Intrinsic::nvvm_barrier0:
2298 case Intrinsic::nvvm_barrier0_and:
2299 case Intrinsic::nvvm_barrier0_or:
2300 case Intrinsic::nvvm_barrier0_popc:
2301 return true;
2302 case Intrinsic::amdgcn_s_barrier:
2303 if (ExecutedAligned)
2304 return true;
2305 break;
2306 default:
2307 break;
2308 }
2309 return hasAssumption(CB, KnownAssumptionString("ompx_aligned_barrier"));
2310}
2311
2313 if (!I->isAtomic())
2314 return false;
2315
2316 if (auto *FI = dyn_cast<FenceInst>(I))
2317 // All legal orderings for fence are stronger than monotonic.
2318 return FI->getSyncScopeID() != SyncScope::SingleThread;
2319 if (auto *AI = dyn_cast<AtomicCmpXchgInst>(I)) {
2320 // Unordered is not a legal ordering for cmpxchg.
2321 return (AI->getSuccessOrdering() != AtomicOrdering::Monotonic ||
2322 AI->getFailureOrdering() != AtomicOrdering::Monotonic);
2323 }
2324
2325 AtomicOrdering Ordering;
2326 switch (I->getOpcode()) {
2327 case Instruction::AtomicRMW:
2328 Ordering = cast<AtomicRMWInst>(I)->getOrdering();
2329 break;
2330 case Instruction::Store:
2331 Ordering = cast<StoreInst>(I)->getOrdering();
2332 break;
2333 case Instruction::Load:
2334 Ordering = cast<LoadInst>(I)->getOrdering();
2335 break;
2336 default:
2338 "New atomic operations need to be known in the attributor.");
2339 }
2340
2341 return (Ordering != AtomicOrdering::Unordered &&
2342 Ordering != AtomicOrdering::Monotonic);
2343}
2344
2345/// Return true if this intrinsic is nosync. This is only used for intrinsics
2346/// which would be nosync except that they have a volatile flag. All other
2347/// intrinsics are simply annotated with the nosync attribute in Intrinsics.td.
2349 if (auto *MI = dyn_cast<MemIntrinsic>(I))
2350 return !MI->isVolatile();
2351 return false;
2352}
2353
2354namespace {
2355struct AANoSyncImpl : AANoSync {
2356 AANoSyncImpl(const IRPosition &IRP, Attributor &A) : AANoSync(IRP, A) {}
2357
2358 const std::string getAsStr() const override {
2359 return getAssumed() ? "nosync" : "may-sync";
2360 }
2361
2362 /// See AbstractAttribute::updateImpl(...).
2363 ChangeStatus updateImpl(Attributor &A) override;
2364};
2365
2366ChangeStatus AANoSyncImpl::updateImpl(Attributor &A) {
2367
2368 auto CheckRWInstForNoSync = [&](Instruction &I) {
2369 return AA::isNoSyncInst(A, I, *this);
2370 };
2371
2372 auto CheckForNoSync = [&](Instruction &I) {
2373 // At this point we handled all read/write effects and they are all
2374 // nosync, so they can be skipped.
2375 if (I.mayReadOrWriteMemory())
2376 return true;
2377
2378 // non-convergent and readnone imply nosync.
2379 return !cast<CallBase>(I).isConvergent();
2380 };
2381
2382 bool UsedAssumedInformation = false;
2383 if (!A.checkForAllReadWriteInstructions(CheckRWInstForNoSync, *this,
2384 UsedAssumedInformation) ||
2385 !A.checkForAllCallLikeInstructions(CheckForNoSync, *this,
2386 UsedAssumedInformation))
2387 return indicatePessimisticFixpoint();
2388
2390}
2391
2392struct AANoSyncFunction final : public AANoSyncImpl {
2393 AANoSyncFunction(const IRPosition &IRP, Attributor &A)
2394 : AANoSyncImpl(IRP, A) {}
2395
2396 /// See AbstractAttribute::trackStatistics()
2397 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nosync) }
2398};
2399
2400/// NoSync attribute deduction for a call sites.
2401struct AANoSyncCallSite final : AANoSyncImpl {
2402 AANoSyncCallSite(const IRPosition &IRP, Attributor &A)
2403 : AANoSyncImpl(IRP, A) {}
2404
2405 /// See AbstractAttribute::initialize(...).
2406 void initialize(Attributor &A) override {
2407 AANoSyncImpl::initialize(A);
2408 Function *F = getAssociatedFunction();
2409 if (!F || F->isDeclaration())
2410 indicatePessimisticFixpoint();
2411 }
2412
2413 /// See AbstractAttribute::updateImpl(...).
2414 ChangeStatus updateImpl(Attributor &A) override {
2415 // TODO: Once we have call site specific value information we can provide
2416 // call site specific liveness information and then it makes
2417 // sense to specialize attributes for call sites arguments instead of
2418 // redirecting requests to the callee argument.
2419 Function *F = getAssociatedFunction();
2420 const IRPosition &FnPos = IRPosition::function(*F);
2421 auto &FnAA = A.getAAFor<AANoSync>(*this, FnPos, DepClassTy::REQUIRED);
2422 return clampStateAndIndicateChange(getState(), FnAA.getState());
2423 }
2424
2425 /// See AbstractAttribute::trackStatistics()
2426 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nosync); }
2427};
2428} // namespace
2429
2430/// ------------------------ No-Free Attributes ----------------------------
2431
2432namespace {
2433struct AANoFreeImpl : public AANoFree {
2434 AANoFreeImpl(const IRPosition &IRP, Attributor &A) : AANoFree(IRP, A) {}
2435
2436 /// See AbstractAttribute::updateImpl(...).
2437 ChangeStatus updateImpl(Attributor &A) override {
2438 auto CheckForNoFree = [&](Instruction &I) {
2439 const auto &CB = cast<CallBase>(I);
2440 if (CB.hasFnAttr(Attribute::NoFree))
2441 return true;
2442
2443 const auto &NoFreeAA = A.getAAFor<AANoFree>(
2444 *this, IRPosition::callsite_function(CB), DepClassTy::REQUIRED);
2445 return NoFreeAA.isAssumedNoFree();
2446 };
2447
2448 bool UsedAssumedInformation = false;
2449 if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this,
2450 UsedAssumedInformation))
2451 return indicatePessimisticFixpoint();
2452 return ChangeStatus::UNCHANGED;
2453 }
2454
2455 /// See AbstractAttribute::getAsStr().
2456 const std::string getAsStr() const override {
2457 return getAssumed() ? "nofree" : "may-free";
2458 }
2459};
2460
2461struct AANoFreeFunction final : public AANoFreeImpl {
2462 AANoFreeFunction(const IRPosition &IRP, Attributor &A)
2463 : AANoFreeImpl(IRP, A) {}
2464
2465 /// See AbstractAttribute::trackStatistics()
2466 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nofree) }
2467};
2468
2469/// NoFree attribute deduction for a call sites.
2470struct AANoFreeCallSite final : AANoFreeImpl {
2471 AANoFreeCallSite(const IRPosition &IRP, Attributor &A)
2472 : AANoFreeImpl(IRP, A) {}
2473
2474 /// See AbstractAttribute::initialize(...).
2475 void initialize(Attributor &A) override {
2476 AANoFreeImpl::initialize(A);
2477 Function *F = getAssociatedFunction();
2478 if (!F || F->isDeclaration())
2479 indicatePessimisticFixpoint();
2480 }
2481
2482 /// See AbstractAttribute::updateImpl(...).
2483 ChangeStatus updateImpl(Attributor &A) override {
2484 // TODO: Once we have call site specific value information we can provide
2485 // call site specific liveness information and then it makes
2486 // sense to specialize attributes for call sites arguments instead of
2487 // redirecting requests to the callee argument.
2488 Function *F = getAssociatedFunction();
2489 const IRPosition &FnPos = IRPosition::function(*F);
2490 auto &FnAA = A.getAAFor<AANoFree>(*this, FnPos, DepClassTy::REQUIRED);
2491 return clampStateAndIndicateChange(getState(), FnAA.getState());
2492 }
2493
2494 /// See AbstractAttribute::trackStatistics()
2495 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nofree); }
2496};
2497
2498/// NoFree attribute for floating values.
2499struct AANoFreeFloating : AANoFreeImpl {
2500 AANoFreeFloating(const IRPosition &IRP, Attributor &A)
2501 : AANoFreeImpl(IRP, A) {}
2502
2503 /// See AbstractAttribute::trackStatistics()
2504 void trackStatistics() const override{STATS_DECLTRACK_FLOATING_ATTR(nofree)}
2505
2506 /// See Abstract Attribute::updateImpl(...).
2507 ChangeStatus updateImpl(Attributor &A) override {
2508 const IRPosition &IRP = getIRPosition();
2509
2510 const auto &NoFreeAA = A.getAAFor<AANoFree>(
2511 *this, IRPosition::function_scope(IRP), DepClassTy::OPTIONAL);
2512 if (NoFreeAA.isAssumedNoFree())
2513 return ChangeStatus::UNCHANGED;
2514
2515 Value &AssociatedValue = getIRPosition().getAssociatedValue();
2516 auto Pred = [&](const Use &U, bool &Follow) -> bool {
2517 Instruction *UserI = cast<Instruction>(U.getUser());
2518 if (auto *CB = dyn_cast<CallBase>(UserI)) {
2519 if (CB->isBundleOperand(&U))
2520 return false;
2521 if (!CB->isArgOperand(&U))
2522 return true;
2523 unsigned ArgNo = CB->getArgOperandNo(&U);
2524
2525 const auto &NoFreeArg = A.getAAFor<AANoFree>(
2526 *this, IRPosition::callsite_argument(*CB, ArgNo),
2527 DepClassTy::REQUIRED);
2528 return NoFreeArg.isAssumedNoFree();
2529 }
2530
2531 if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) ||
2532 isa<PHINode>(UserI) || isa<SelectInst>(UserI)) {
2533 Follow = true;
2534 return true;
2535 }
2536 if (isa<StoreInst>(UserI) || isa<LoadInst>(UserI) ||
2537 isa<ReturnInst>(UserI))
2538 return true;
2539
2540 // Unknown user.
2541 return false;
2542 };
2543 if (!A.checkForAllUses(Pred, *this, AssociatedValue))
2544 return indicatePessimisticFixpoint();
2545
2546 return ChangeStatus::UNCHANGED;
2547 }
2548};
2549
2550/// NoFree attribute for a call site argument.
2551struct AANoFreeArgument final : AANoFreeFloating {
2552 AANoFreeArgument(const IRPosition &IRP, Attributor &A)
2553 : AANoFreeFloating(IRP, A) {}
2554
2555 /// See AbstractAttribute::trackStatistics()
2556 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nofree) }
2557};
2558
2559/// NoFree attribute for call site arguments.
2560struct AANoFreeCallSiteArgument final : AANoFreeFloating {
2561 AANoFreeCallSiteArgument(const IRPosition &IRP, Attributor &A)
2562 : AANoFreeFloating(IRP, A) {}
2563
2564 /// See AbstractAttribute::updateImpl(...).
2565 ChangeStatus updateImpl(Attributor &A) override {
2566 // TODO: Once we have call site specific value information we can provide
2567 // call site specific liveness information and then it makes
2568 // sense to specialize attributes for call sites arguments instead of
2569 // redirecting requests to the callee argument.
2570 Argument *Arg = getAssociatedArgument();
2571 if (!Arg)
2572 return indicatePessimisticFixpoint();
2573 const IRPosition &ArgPos = IRPosition::argument(*Arg);
2574 auto &ArgAA = A.getAAFor<AANoFree>(*this, ArgPos, DepClassTy::REQUIRED);
2575 return clampStateAndIndicateChange(getState(), ArgAA.getState());
2576 }
2577
2578 /// See AbstractAttribute::trackStatistics()
2579 void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nofree)};
2580};
2581
2582/// NoFree attribute for function return value.
2583struct AANoFreeReturned final : AANoFreeFloating {
2584 AANoFreeReturned(const IRPosition &IRP, Attributor &A)
2585 : AANoFreeFloating(IRP, A) {
2586 llvm_unreachable("NoFree is not applicable to function returns!");
2587 }
2588
2589 /// See AbstractAttribute::initialize(...).
2590 void initialize(Attributor &A) override {
2591 llvm_unreachable("NoFree is not applicable to function returns!");
2592 }
2593
2594 /// See AbstractAttribute::updateImpl(...).
2595 ChangeStatus updateImpl(Attributor &A) override {
2596 llvm_unreachable("NoFree is not applicable to function returns!");
2597 }
2598
2599 /// See AbstractAttribute::trackStatistics()
2600 void trackStatistics() const override {}
2601};
2602
2603/// NoFree attribute deduction for a call site return value.
2604struct AANoFreeCallSiteReturned final : AANoFreeFloating {
2605 AANoFreeCallSiteReturned(const IRPosition &IRP, Attributor &A)
2606 : AANoFreeFloating(IRP, A) {}
2607
2608 ChangeStatus manifest(Attributor &A) override {
2609 return ChangeStatus::UNCHANGED;
2610 }
2611 /// See AbstractAttribute::trackStatistics()
2612 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nofree) }
2613};
2614} // namespace
2615
2616/// ------------------------ NonNull Argument Attribute ------------------------
2617namespace {
2618static int64_t getKnownNonNullAndDerefBytesForUse(
2619 Attributor &A, const AbstractAttribute &QueryingAA, Value &AssociatedValue,
2620 const Use *U, const Instruction *I, bool &IsNonNull, bool &TrackUse) {
2621 TrackUse = false;
2622
2623 const Value *UseV = U->get();
2624 if (!UseV->getType()->isPointerTy())
2625 return 0;
2626
2627 // We need to follow common pointer manipulation uses to the accesses they
2628 // feed into. We can try to be smart to avoid looking through things we do not
2629 // like for now, e.g., non-inbounds GEPs.
2630 if (isa<CastInst>(I)) {
2631 TrackUse = true;
2632 return 0;
2633 }
2634
2635 if (isa<GetElementPtrInst>(I)) {
2636 TrackUse = true;
2637 return 0;
2638 }
2639
2640 Type *PtrTy = UseV->getType();
2641 const Function *F = I->getFunction();
2644 const DataLayout &DL = A.getInfoCache().getDL();
2645 if (const auto *CB = dyn_cast<CallBase>(I)) {
2646 if (CB->isBundleOperand(U)) {
2648 U, {Attribute::NonNull, Attribute::Dereferenceable})) {
2649 IsNonNull |=
2650 (RK.AttrKind == Attribute::NonNull || !NullPointerIsDefined);
2651 return RK.ArgValue;
2652 }
2653 return 0;
2654 }
2655
2656 if (CB->isCallee(U)) {
2657 IsNonNull |= !NullPointerIsDefined;
2658 return 0;
2659 }
2660
2661 unsigned ArgNo = CB->getArgOperandNo(U);
2662 IRPosition IRP = IRPosition::callsite_argument(*CB, ArgNo);
2663 // As long as we only use known information there is no need to track
2664 // dependences here.
2665 auto &DerefAA =
2666 A.getAAFor<AADereferenceable>(QueryingAA, IRP, DepClassTy::NONE);
2667 IsNonNull |= DerefAA.isKnownNonNull();
2668 return DerefAA.getKnownDereferenceableBytes();
2669 }
2670
2671 std::optional<MemoryLocation> Loc = MemoryLocation::getOrNone(I);
2672 if (!Loc || Loc->Ptr != UseV || !Loc->Size.isPrecise() || I->isVolatile())
2673 return 0;
2674
2675 int64_t Offset;
2676 const Value *Base =
2677 getMinimalBaseOfPointer(A, QueryingAA, Loc->Ptr, Offset, DL);
2678 if (Base && Base == &AssociatedValue) {
2679 int64_t DerefBytes = Loc->Size.getValue() + Offset;
2680 IsNonNull |= !NullPointerIsDefined;
2681 return std::max(int64_t(0), DerefBytes);
2682 }
2683
2684 /// Corner case when an offset is 0.
2686 /*AllowNonInbounds*/ true);
2687 if (Base && Base == &AssociatedValue && Offset == 0) {
2688 int64_t DerefBytes = Loc->Size.getValue();
2689 IsNonNull |= !NullPointerIsDefined;
2690 return std::max(int64_t(0), DerefBytes);
2691 }
2692
2693 return 0;
2694}
2695
2696struct AANonNullImpl : AANonNull {
2697 AANonNullImpl(const IRPosition &IRP, Attributor &A)
2698 : AANonNull(IRP, A),
2699 NullIsDefined(NullPointerIsDefined(
2700 getAnchorScope(),
2701 getAssociatedValue().getType()->getPointerAddressSpace())) {}
2702
2703 /// See AbstractAttribute::initialize(...).
2704 void initialize(Attributor &A) override {
2705 Value &V = *getAssociatedValue().stripPointerCasts();
2706 if (!NullIsDefined &&
2707 hasAttr({Attribute::NonNull, Attribute::Dereferenceable},
2708 /* IgnoreSubsumingPositions */ false, &A)) {
2709 indicateOptimisticFixpoint();
2710 return;
2711 }
2712
2713 if (isa<ConstantPointerNull>(V)) {
2714 indicatePessimisticFixpoint();
2715 return;
2716 }
2717
2718 AANonNull::initialize(A);
2719
2720 bool CanBeNull, CanBeFreed;
2721 if (V.getPointerDereferenceableBytes(A.getDataLayout(), CanBeNull,
2722 CanBeFreed)) {
2723 if (!CanBeNull) {
2724 indicateOptimisticFixpoint();
2725 return;
2726 }
2727 }
2728
2729 if (isa<GlobalValue>(V)) {
2730 indicatePessimisticFixpoint();
2731 return;
2732 }
2733
2734 if (Instruction *CtxI = getCtxI())
2735 followUsesInMBEC(*this, A, getState(), *CtxI);
2736 }
2737
2738 /// See followUsesInMBEC
2739 bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
2740 AANonNull::StateType &State) {
2741 bool IsNonNull = false;
2742 bool TrackUse = false;
2743 getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I,
2744 IsNonNull, TrackUse);
2745 State.setKnown(IsNonNull);
2746 return TrackUse;
2747 }
2748
2749 /// See AbstractAttribute::getAsStr().
2750 const std::string getAsStr() const override {
2751 return getAssumed() ? "nonnull" : "may-null";
2752 }
2753
2754 /// Flag to determine if the underlying value can be null and still allow
2755 /// valid accesses.
2756 const bool NullIsDefined;
2757};
2758
2759/// NonNull attribute for a floating value.
2760struct AANonNullFloating : public AANonNullImpl {
2761 AANonNullFloating(const IRPosition &IRP, Attributor &A)
2762 : AANonNullImpl(IRP, A) {}
2763
2764 /// See AbstractAttribute::updateImpl(...).
2765 ChangeStatus updateImpl(Attributor &A) override {
2766 const DataLayout &DL = A.getDataLayout();
2767
2768 bool Stripped;
2769 bool UsedAssumedInformation = false;
2771 if (!A.getAssumedSimplifiedValues(getIRPosition(), *this, Values,
2772 AA::AnyScope, UsedAssumedInformation)) {
2773 Values.push_back({getAssociatedValue(), getCtxI()});
2774 Stripped = false;
2775 } else {
2776 Stripped = Values.size() != 1 ||
2777 Values.front().getValue() != &getAssociatedValue();
2778 }
2779
2780 DominatorTree *DT = nullptr;
2781 AssumptionCache *AC = nullptr;
2782 InformationCache &InfoCache = A.getInfoCache();
2783 if (const Function *Fn = getAnchorScope()) {
2786 }
2787
2789 auto VisitValueCB = [&](Value &V, const Instruction *CtxI) -> bool {
2790 const auto &AA = A.getAAFor<AANonNull>(*this, IRPosition::value(V),
2791 DepClassTy::REQUIRED);
2792 if (!Stripped && this == &AA) {
2793 if (!isKnownNonZero(&V, DL, 0, AC, CtxI, DT))
2794 T.indicatePessimisticFixpoint();
2795 } else {
2796 // Use abstract attribute information.
2797 const AANonNull::StateType &NS = AA.getState();
2798 T ^= NS;
2799 }
2800 return T.isValidState();
2801 };
2802
2803 for (const auto &VAC : Values)
2804 if (!VisitValueCB(*VAC.getValue(), VAC.getCtxI()))
2805 return indicatePessimisticFixpoint();
2806
2807 return clampStateAndIndicateChange(getState(), T);
2808 }
2809
2810 /// See AbstractAttribute::trackStatistics()
2811 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
2812};
2813
2814/// NonNull attribute for function return value.
2815struct AANonNullReturned final
2816 : AAReturnedFromReturnedValues<AANonNull, AANonNull> {
2817 AANonNullReturned(const IRPosition &IRP, Attributor &A)
2818 : AAReturnedFromReturnedValues<AANonNull, AANonNull>(IRP, A) {}
2819
2820 /// See AbstractAttribute::getAsStr().
2821 const std::string getAsStr() const override {
2822 return getAssumed() ? "nonnull" : "may-null";
2823 }
2824
2825 /// See AbstractAttribute::trackStatistics()
2826 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
2827};
2828
2829/// NonNull attribute for function argument.
2830struct AANonNullArgument final
2831 : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl> {
2832 AANonNullArgument(const IRPosition &IRP, Attributor &A)
2833 : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl>(IRP, A) {}
2834
2835 /// See AbstractAttribute::trackStatistics()
2836 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nonnull) }
2837};
2838
2839struct AANonNullCallSiteArgument final : AANonNullFloating {
2840 AANonNullCallSiteArgument(const IRPosition &IRP, Attributor &A)
2841 : AANonNullFloating(IRP, A) {}
2842
2843 /// See AbstractAttribute::trackStatistics()
2844 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(nonnull) }
2845};
2846
2847/// NonNull attribute for a call site return position.
2848struct AANonNullCallSiteReturned final
2849 : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl> {
2850 AANonNullCallSiteReturned(const IRPosition &IRP, Attributor &A)
2851 : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl>(IRP, A) {}
2852
2853 /// See AbstractAttribute::trackStatistics()
2854 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) }
2855};
2856} // namespace
2857
2858/// ------------------------ Must-Progress Attributes --------------------------
2859namespace {
2860struct AAMustProgressImpl : public AAMustProgress {
2861 AAMustProgressImpl(const IRPosition &IRP, Attributor &A)
2862 : AAMustProgress(IRP, A) {}
2863
2864 /// See AbstractAttribute::getAsStr()
2865 const std::string getAsStr() const override {
2866 return getAssumed() ? "mustprogress" : "may-not-progress";
2867 }
2868};
2869
2870struct AAMustProgressFunction final : AAMustProgressImpl {
2871 AAMustProgressFunction(const IRPosition &IRP, Attributor &A)
2872 : AAMustProgressImpl(IRP, A) {}
2873
2874 /// See AbstractAttribute::updateImpl(...).
2875 ChangeStatus updateImpl(Attributor &A) override {
2876 const auto &WillReturnAA =
2877 A.getAAFor<AAWillReturn>(*this, getIRPosition(), DepClassTy::OPTIONAL);
2878 if (WillReturnAA.isKnownWillReturn())
2879 return indicateOptimisticFixpoint();
2880 if (WillReturnAA.isAssumedWillReturn())
2881 return ChangeStatus::UNCHANGED;
2882
2883 auto CheckForMustProgress = [&](AbstractCallSite ACS) {
2884 IRPosition IPos = IRPosition::callsite_function(*ACS.getInstruction());
2885 const auto &MustProgressAA =
2886 A.getAAFor<AAMustProgress>(*this, IPos, DepClassTy::OPTIONAL);
2887 return MustProgressAA.isAssumedMustProgress();
2888 };
2889
2890 bool AllCallSitesKnown = true;
2891 if (!A.checkForAllCallSites(CheckForMustProgress, *this,
2892 /* RequireAllCallSites */ true,
2893 AllCallSitesKnown))
2894 return indicatePessimisticFixpoint();
2895
2896 return ChangeStatus::UNCHANGED;
2897 }
2898
2899 /// See AbstractAttribute::trackStatistics()
2900 void trackStatistics() const override {
2901 STATS_DECLTRACK_FN_ATTR(mustprogress)
2902 }
2903};
2904
2905/// MustProgress attribute deduction for a call sites.
2906struct AAMustProgressCallSite final : AAMustProgressImpl {
2907 AAMustProgressCallSite(const IRPosition &IRP, Attributor &A)
2908 : AAMustProgressImpl(IRP, A) {}
2909
2910 /// See AbstractAttribute::updateImpl(...).
2911 ChangeStatus updateImpl(Attributor &A) override {
2912 // TODO: Once we have call site specific value information we can provide
2913 // call site specific liveness information and then it makes
2914 // sense to specialize attributes for call sites arguments instead of
2915 // redirecting requests to the callee argument.
2916 const IRPosition &FnPos = IRPosition::function(*getAnchorScope());
2917 const auto &FnAA =
2918 A.getAAFor<AAMustProgress>(*this, FnPos, DepClassTy::OPTIONAL);
2919 return clampStateAndIndicateChange(getState(), FnAA.getState());
2920 }
2921
2922 /// See AbstractAttribute::trackStatistics()
2923 void trackStatistics() const override {
2924 STATS_DECLTRACK_CS_ATTR(mustprogress);
2925 }
2926};
2927} // namespace
2928
2929/// ------------------------ No-Recurse Attributes ----------------------------
2930
2931namespace {
2932struct AANoRecurseImpl : public AANoRecurse {
2933 AANoRecurseImpl(const IRPosition &IRP, Attributor &A) : AANoRecurse(IRP, A) {}
2934
2935 /// See AbstractAttribute::getAsStr()
2936 const std::string getAsStr() const override {
2937 return getAssumed() ? "norecurse" : "may-recurse";
2938 }
2939};
2940
2941struct AANoRecurseFunction final : AANoRecurseImpl {
2942 AANoRecurseFunction(const IRPosition &IRP, Attributor &A)
2943 : AANoRecurseImpl(IRP, A) {}
2944
2945 /// See AbstractAttribute::updateImpl(...).
2946 ChangeStatus updateImpl(Attributor &A) override {
2947
2948 // If all live call sites are known to be no-recurse, we are as well.
2949 auto CallSitePred = [&](AbstractCallSite ACS) {
2950 const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
2951 *this, IRPosition::function(*ACS.getInstruction()->getFunction()),
2952 DepClassTy::NONE);
2953 return NoRecurseAA.isKnownNoRecurse();
2954 };
2955 bool UsedAssumedInformation = false;
2956 if (A.checkForAllCallSites(CallSitePred, *this, true,
2957 UsedAssumedInformation)) {
2958 // If we know all call sites and all are known no-recurse, we are done.
2959 // If all known call sites, which might not be all that exist, are known
2960 // to be no-recurse, we are not done but we can continue to assume
2961 // no-recurse. If one of the call sites we have not visited will become
2962 // live, another update is triggered.
2963 if (!UsedAssumedInformation)
2964 indicateOptimisticFixpoint();
2965 return ChangeStatus::UNCHANGED;
2966 }
2967
2968 const AAInterFnReachability &EdgeReachability =
2969 A.getAAFor<AAInterFnReachability>(*this, getIRPosition(),
2970 DepClassTy::REQUIRED);
2971 if (EdgeReachability.canReach(A, *getAnchorScope()))
2972 return indicatePessimisticFixpoint();
2973 return ChangeStatus::UNCHANGED;
2974 }
2975
2976 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) }
2977};
2978
2979/// NoRecurse attribute deduction for a call sites.
2980struct AANoRecurseCallSite final : AANoRecurseImpl {
2981 AANoRecurseCallSite(const IRPosition &IRP, Attributor &A)
2982 : AANoRecurseImpl(IRP, A) {}
2983
2984 /// See AbstractAttribute::initialize(...).
2985 void initialize(Attributor &A) override {
2986 AANoRecurseImpl::initialize(A);
2987 Function *F = getAssociatedFunction();
2988 if (!F || F->isDeclaration())
2989 indicatePessimisticFixpoint();
2990 }
2991
2992 /// See AbstractAttribute::updateImpl(...).
2993 ChangeStatus updateImpl(Attributor &A) override {
2994 // TODO: Once we have call site specific value information we can provide
2995 // call site specific liveness information and then it makes
2996 // sense to specialize attributes for call sites arguments instead of
2997 // redirecting requests to the callee argument.
2998 Function *F = getAssociatedFunction();
2999 const IRPosition &FnPos = IRPosition::function(*F);
3000 auto &FnAA = A.getAAFor<AANoRecurse>(*this, FnPos, DepClassTy::REQUIRED);
3001 return clampStateAndIndicateChange(getState(), FnAA.getState());
3002 }
3003
3004 /// See AbstractAttribute::trackStatistics()
3005 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(norecurse); }
3006};
3007} // namespace
3008
3009/// ------------------------ No-Convergent Attribute --------------------------
3010
3011namespace {
3012struct AANonConvergentImpl : public AANonConvergent {
3013 AANonConvergentImpl(const IRPosition &IRP, Attributor &A)
3014 : AANonConvergent(IRP, A) {}
3015
3016 /// See AbstractAttribute::getAsStr()
3017 const std::string getAsStr() const override {
3018 return getAssumed() ? "non-convergent" : "may-be-convergent";
3019 }
3020};
3021
3022struct AANonConvergentFunction final : AANonConvergentImpl {
3023 AANonConvergentFunction(const IRPosition &IRP, Attributor &A)
3024 : AANonConvergentImpl(IRP, A) {}
3025
3026 /// See AbstractAttribute::updateImpl(...).
3027 ChangeStatus updateImpl(Attributor &A) override {
3028 // If all function calls are known to not be convergent, we are not convergent.
3029 auto CalleeIsNotConvergent = [&](Instruction &Inst) {
3030 CallBase &CB = cast<CallBase>(Inst);
3032 if (!Callee || Callee->isIntrinsic()) {
3033 return false;
3034 }
3035 if (Callee->isDeclaration()) {
3036 return !Callee->hasFnAttribute(Attribute::Convergent);
3037 }
3038 const auto &ConvergentAA = A.getAAFor<AANonConvergent>(
3039 *this, IRPosition::function(*Callee), DepClassTy::REQUIRED);
3040 return ConvergentAA.isAssumedNotConvergent();
3041 };
3042
3043 bool UsedAssumedInformation = false;
3044 if (!A.checkForAllCallLikeInstructions(CalleeIsNotConvergent, *this,
3045 UsedAssumedInformation)) {
3046 return indicatePessimisticFixpoint();
3047 }
3048 return ChangeStatus::UNCHANGED;
3049 }
3050
3051 ChangeStatus manifest(Attributor &A) override {
3052 if (isKnownNotConvergent() && hasAttr(Attribute::Convergent)) {
3053 removeAttrs({Attribute::Convergent});
3054 return ChangeStatus::CHANGED;
3055 }
3056 return ChangeStatus::UNCHANGED;
3057 }
3058
3059 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(convergent) }
3060};
3061} // namespace
3062
3063/// -------------------- Undefined-Behavior Attributes ------------------------
3064
3065namespace {
3066struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior {
3067 AAUndefinedBehaviorImpl(const IRPosition &IRP, Attributor &A)
3068 : AAUndefinedBehavior(IRP, A) {}
3069
3070 /// See AbstractAttribute::updateImpl(...).
3071 // through a pointer (i.e. also branches etc.)
3072 ChangeStatus updateImpl(Attributor &A) override {
3073 const size_t UBPrevSize = KnownUBInsts.size();
3074 const size_t NoUBPrevSize = AssumedNoUBInsts.size();
3075
3076 auto InspectMemAccessInstForUB = [&](Instruction &I) {
3077 // Lang ref now states volatile store is not UB, let's skip them.
3078 if (I.isVolatile() && I.mayWriteToMemory())
3079 return true;
3080
3081 // Skip instructions that are already saved.
3082 if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
3083 return true;
3084
3085 // If we reach here, we know we have an instruction
3086 // that accesses memory through a pointer operand,
3087 // for which getPointerOperand() should give it to us.
3088 Value *PtrOp =
3089 const_cast<Value *>(getPointerOperand(&I, /* AllowVolatile */ true));
3090 assert(PtrOp &&
3091 "Expected pointer operand of memory accessing instruction");
3092
3093 // Either we stopped and the appropriate action was taken,
3094 // or we got back a simplified value to continue.
3095 std::optional<Value *> SimplifiedPtrOp =
3096 stopOnUndefOrAssumed(A, PtrOp, &I);
3097 if (!SimplifiedPtrOp || !*SimplifiedPtrOp)
3098 return true;
3099 const Value *PtrOpVal = *SimplifiedPtrOp;
3100
3101 // A memory access through a pointer is considered UB
3102 // only if the pointer has constant null value.
3103 // TODO: Expand it to not only check constant values.
3104 if (!isa<ConstantPointerNull>(PtrOpVal)) {
3105 AssumedNoUBInsts.insert(&I);
3106 return true;
3107 }
3108 const Type *PtrTy = PtrOpVal->getType();
3109
3110 // Because we only consider instructions inside functions,
3111 // assume that a parent function exists.
3112 const Function *F = I.getFunction();
3113
3114 // A memory access using constant null pointer is only considered UB
3115 // if null pointer is _not_ defined for the target platform.
3117 AssumedNoUBInsts.insert(&I);
3118 else
3119 KnownUBInsts.insert(&I);
3120 return true;
3121 };
3122
3123 auto InspectBrInstForUB = [&](Instruction &I) {
3124 // A conditional branch instruction is considered UB if it has `undef`
3125 // condition.
3126
3127 // Skip instructions that are already saved.
3128 if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
3129 return true;
3130
3131 // We know we have a branch instruction.
3132 auto *BrInst = cast<BranchInst>(&I);
3133
3134 // Unconditional branches are never considered UB.
3135 if (BrInst->isUnconditional())
3136 return true;
3137
3138 // Either we stopped and the appropriate action was taken,
3139 // or we got back a simplified value to continue.
3140 std::optional<Value *> SimplifiedCond =
3141 stopOnUndefOrAssumed(A, BrInst->getCondition(), BrInst);
3142 if (!SimplifiedCond || !*SimplifiedCond)
3143 return true;
3144 AssumedNoUBInsts.insert(&I);
3145 return true;
3146 };
3147
3148 auto InspectCallSiteForUB = [&](Instruction &I) {
3149 // Check whether a callsite always cause UB or not
3150
3151 // Skip instructions that are already saved.
3152 if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
3153 return true;
3154
3155 // Check nonnull and noundef argument attribute violation for each
3156 // callsite.
3157 CallBase &CB = cast<CallBase>(I);
3159 if (!Callee)
3160 return true;
3161 for (unsigned idx = 0; idx < CB.arg_size(); idx++) {
3162 // If current argument is known to be simplified to null pointer and the
3163 // corresponding argument position is known to have nonnull attribute,
3164 // the argument is poison. Furthermore, if the argument is poison and
3165 // the position is known to have noundef attriubte, this callsite is
3166 // considered UB.
3167 if (idx >= Callee->arg_size())
3168 break;
3169 Value *ArgVal = CB.getArgOperand(idx);
3170 if (!ArgVal)
3171 continue;
3172 // Here, we handle three cases.
3173 // (1) Not having a value means it is dead. (we can replace the value
3174 // with undef)
3175 // (2) Simplified to undef. The argument violate noundef attriubte.
3176 // (3) Simplified to null pointer where known to be nonnull.
3177 // The argument is a poison value and violate noundef attribute.
3178 IRPosition CalleeArgumentIRP = IRPosition::callsite_argument(CB, idx);
3179 auto &NoUndefAA =
3180 A.getAAFor<AANoUndef>(*this, CalleeArgumentIRP, DepClassTy::NONE);
3181 if (!NoUndefAA.isKnownNoUndef())
3182 continue;
3183 bool UsedAssumedInformation = false;
3184 std::optional<Value *> SimplifiedVal =
3185 A.getAssumedSimplified(IRPosition::value(*ArgVal), *this,
3186 UsedAssumedInformation, AA::Interprocedural);
3187 if (UsedAssumedInformation)
3188 continue;
3189 if (SimplifiedVal && !*SimplifiedVal)
3190 return true;
3191 if (!SimplifiedVal || isa<UndefValue>(**SimplifiedVal)) {
3192 KnownUBInsts.insert(&I);
3193 continue;
3194 }
3195 if (!ArgVal->getType()->isPointerTy() ||
3196 !isa<ConstantPointerNull>(**SimplifiedVal))
3197 continue;
3198 auto &NonNullAA =
3199 A.getAAFor<AANonNull>(*this, CalleeArgumentIRP, DepClassTy::NONE);
3200 if (NonNullAA.isKnownNonNull())
3201 KnownUBInsts.insert(&I);
3202 }
3203 return true;
3204 };
3205
3206 auto InspectReturnInstForUB = [&](Instruction &I) {
3207 auto &RI = cast<ReturnInst>(I);
3208 // Either we stopped and the appropriate action was taken,
3209 // or we got back a simplified return value to continue.
3210 std::optional<Value *> SimplifiedRetValue =
3211 stopOnUndefOrAssumed(A, RI.getReturnValue(), &I);
3212 if (!SimplifiedRetValue || !*SimplifiedRetValue)
3213 return true;
3214
3215 // Check if a return instruction always cause UB or not
3216 // Note: It is guaranteed that the returned position of the anchor
3217 // scope has noundef attribute when this is called.
3218 // We also ensure the return position is not "assumed dead"
3219 // because the returned value was then potentially simplified to
3220 // `undef` in AAReturnedValues without removing the `noundef`
3221 // attribute yet.
3222
3223 // When the returned position has noundef attriubte, UB occurs in the
3224 // following cases.
3225 // (1) Returned value is known to be undef.
3226 // (2) The value is known to be a null pointer and the returned
3227 // position has nonnull attribute (because the returned value is
3228 // poison).
3229 if (isa<ConstantPointerNull>(*SimplifiedRetValue)) {
3230 auto &NonNullAA = A.getAAFor<AANonNull>(
3231 *this, IRPosition::returned(*getAnchorScope()), DepClassTy::NONE);
3232 if (NonNullAA.isKnownNonNull())
3233 KnownUBInsts.insert(&I);
3234 }
3235
3236 return true;
3237 };
3238
3239 bool UsedAssumedInformation = false;
3240 A.checkForAllInstructions(InspectMemAccessInstForUB, *this,
3241 {Instruction::Load, Instruction::Store,
3242 Instruction::AtomicCmpXchg,
3243 Instruction::AtomicRMW},
3244 UsedAssumedInformation,
3245 /* CheckBBLivenessOnly */ true);
3246 A.checkForAllInstructions(InspectBrInstForUB, *this, {Instruction::Br},
3247 UsedAssumedInformation,
3248 /* CheckBBLivenessOnly */ true);
3249 A.checkForAllCallLikeInstructions(InspectCallSiteForUB, *this,
3250 UsedAssumedInformation);
3251
3252 // If the returned position of the anchor scope has noundef attriubte, check
3253 // all returned instructions.
3254 if (!getAnchorScope()->getReturnType()->isVoidTy()) {
3255 const IRPosition &ReturnIRP = IRPosition::returned(*getAnchorScope());
3256 if (!A.isAssumedDead(ReturnIRP, this, nullptr, UsedAssumedInformation)) {
3257 auto &RetPosNoUndefAA =
3258 A.getAAFor<AANoUndef>(*this, ReturnIRP, DepClassTy::NONE);
3259 if (RetPosNoUndefAA.isKnownNoUndef())
3260 A.checkForAllInstructions(InspectReturnInstForUB, *this,
3261 {Instruction::Ret}, UsedAssumedInformation,
3262 /* CheckBBLivenessOnly */ true);
3263 }
3264 }
3265
3266 if (NoUBPrevSize != AssumedNoUBInsts.size() ||
3267 UBPrevSize != KnownUBInsts.size())
3268 return ChangeStatus::CHANGED;
3269 return ChangeStatus::UNCHANGED;
3270 }
3271
3272 bool isKnownToCauseUB(Instruction *I) const override {
3273 return KnownUBInsts.count(I);
3274 }
3275
3276 bool isAssumedToCauseUB(Instruction *I) const override {
3277 // In simple words, if an instruction is not in the assumed to _not_
3278 // cause UB, then it is assumed UB (that includes those
3279 // in the KnownUBInsts set). The rest is boilerplate
3280 // is to ensure that it is one of the instructions we test
3281 // for UB.
3282
3283 switch (I->getOpcode()) {
3284 case Instruction::Load:
3285 case Instruction::Store:
3286 case Instruction::AtomicCmpXchg:
3287 case Instruction::AtomicRMW:
3288 return !AssumedNoUBInsts.count(I);
3289 case Instruction::Br: {
3290 auto *BrInst = cast<BranchInst>(I);
3291 if (BrInst->isUnconditional())
3292 return false;
3293 return !AssumedNoUBInsts.count(I);
3294 } break;
3295 default:
3296 return false;
3297 }
3298 return false;
3299 }
3300
3301 ChangeStatus manifest(Attributor &A) override {
3302 if (KnownUBInsts.empty())
3304 for (Instruction *I : KnownUBInsts)
3305 A.changeToUnreachableAfterManifest(I);
3306 return ChangeStatus::CHANGED;
3307 }
3308
3309 /// See AbstractAttribute::getAsStr()
3310 const std::string getAsStr() const override {
3311 return getAssumed() ? "undefined-behavior" : "no-ub";
3312 }
3313
3314 /// Note: The correctness of this analysis depends on the fact that the
3315 /// following 2 sets will stop changing after some point.
3316 /// "Change" here means that their size changes.
3317 /// The size of each set is monotonically increasing
3318 /// (we only add items to them) and it is upper bounded by the number of
3319 /// instructions in the processed function (we can never save more
3320 /// elements in either set than this number). Hence, at some point,
3321 /// they will stop increasing.
3322 /// Consequently, at some point, both sets will have stopped
3323 /// changing, effectively making the analysis reach a fixpoint.
3324
3325 /// Note: These 2 sets are disjoint and an instruction can be considered
3326 /// one of 3 things:
3327 /// 1) Known to cause UB (AAUndefinedBehavior could prove it) and put it in
3328 /// the KnownUBInsts set.
3329 /// 2) Assumed to cause UB (in every updateImpl, AAUndefinedBehavior
3330 /// has a reason to assume it).
3331 /// 3) Assumed to not cause UB. very other instruction - AAUndefinedBehavior
3332 /// could not find a reason to assume or prove that it can cause UB,
3333 /// hence it assumes it doesn't. We have a set for these instructions
3334 /// so that we don't reprocess them in every update.
3335 /// Note however that instructions in this set may cause UB.
3336
3337protected:
3338 /// A set of all live instructions _known_ to cause UB.
3339 SmallPtrSet<Instruction *, 8> KnownUBInsts;
3340
3341private:
3342 /// A set of all the (live) instructions that are assumed to _not_ cause UB.
3343 SmallPtrSet<Instruction *, 8> AssumedNoUBInsts;
3344
3345 // Should be called on updates in which if we're processing an instruction
3346 // \p I that depends on a value \p V, one of the following has to happen:
3347 // - If the value is assumed, then stop.
3348 // - If the value is known but undef, then consider it UB.
3349 // - Otherwise, do specific processing with the simplified value.
3350 // We return std::nullopt in the first 2 cases to signify that an appropriate
3351 // action was taken and the caller should stop.
3352 // Otherwise, we return the simplified value that the caller should
3353 // use for specific processing.
3354 std::optional<Value *> stopOnUndefOrAssumed(Attributor &A, Value *V,
3355 Instruction *I) {
3356 bool UsedAssumedInformation = false;
3357 std::optional<Value *> SimplifiedV =
3358 A.getAssumedSimplified(IRPosition::value(*V), *this,
3359 UsedAssumedInformation, AA::Interprocedural);
3360 if (!UsedAssumedInformation) {
3361 // Don't depend on assumed values.
3362 if (!SimplifiedV) {
3363 // If it is known (which we tested above) but it doesn't have a value,
3364 // then we can assume `undef` and hence the instruction is UB.
3365 KnownUBInsts.insert(I);
3366 return std::nullopt;
3367 }
3368 if (!*SimplifiedV)
3369 return nullptr;
3370 V = *SimplifiedV;
3371 }
3372 if (isa<UndefValue>(V)) {
3373 KnownUBInsts.insert(I);
3374 return std::nullopt;
3375 }
3376 return V;
3377 }
3378};
3379
3380struct AAUndefinedBehaviorFunction final : AAUndefinedBehaviorImpl {
3381 AAUndefinedBehaviorFunction(const IRPosition &IRP, Attributor &A)
3382 : AAUndefinedBehaviorImpl(IRP, A) {}
3383
3384 /// See AbstractAttribute::trackStatistics()
3385 void trackStatistics() const override {
3386 STATS_DECL(UndefinedBehaviorInstruction, Instruction,
3387 "Number of instructions known to have UB");
3388 BUILD_STAT_NAME(UndefinedBehaviorInstruction, Instruction) +=
3389 KnownUBInsts.size();
3390 }
3391};
3392} // namespace
3393
3394/// ------------------------ Will-Return Attributes ----------------------------
3395
3396namespace {
3397// Helper function that checks whether a function has any cycle which we don't
3398// know if it is bounded or not.
3399// Loops with maximum trip count are considered bounded, any other cycle not.
3400static bool mayContainUnboundedCycle(Function &F, Attributor &A) {
3401 ScalarEvolution *SE =
3402 A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(F);
3403 LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(F);
3404 // If either SCEV or LoopInfo is not available for the function then we assume
3405 // any cycle to be unbounded cycle.
3406 // We use scc_iterator which uses Tarjan algorithm to find all the maximal
3407 // SCCs.To detect if there's a cycle, we only need to find the maximal ones.
3408 if (!SE || !LI) {
3409 for (scc_iterator<Function *> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI)
3410 if (SCCI.hasCycle())
3411 return true;
3412 return false;
3413 }
3414
3415 // If there's irreducible control, the function may contain non-loop cycles.
3417 return true;
3418
3419 // Any loop that does not have a max trip count is considered unbounded cycle.
3420 for (auto *L : LI->getLoopsInPreorder()) {
3421 if (!SE->getSmallConstantMaxTripCount(L))
3422 return true;
3423 }
3424 return false;
3425}
3426
3427struct AAWillReturnImpl : public AAWillReturn {
3428 AAWillReturnImpl(const IRPosition &IRP, Attributor &A)
3429 : AAWillReturn(IRP, A) {}
3430
3431 /// See AbstractAttribute::initialize(...).
3432 void initialize(Attributor &A) override {
3433 AAWillReturn::initialize(A);
3434
3435 if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ true)) {
3436 indicateOptimisticFixpoint();
3437 return;
3438 }
3439 }
3440
3441 /// Check for `mustprogress` and `readonly` as they imply `willreturn`.
3442 bool isImpliedByMustprogressAndReadonly(Attributor &A, bool KnownOnly) {
3443 // Check for `mustprogress` in the scope and the associated function which
3444 // might be different if this is a call site.
3445 if ((!getAnchorScope() || !getAnchorScope()->mustProgress()) &&
3446 (!getAssociatedFunction() || !getAssociatedFunction()->mustProgress()))
3447 return false;
3448
3449 bool IsKnown;
3450 if (AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown))
3451 return IsKnown || !KnownOnly;
3452 return false;
3453 }
3454
3455 /// See AbstractAttribute::updateImpl(...).
3456 ChangeStatus updateImpl(Attributor &A) override {
3457 if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ false))
3458 return ChangeStatus::UNCHANGED;
3459
3460 auto CheckForWillReturn = [&](Instruction &I) {
3461 IRPosition IPos = IRPosition::callsite_function(cast<CallBase>(I));
3462 const auto &WillReturnAA =
3463 A.getAAFor<AAWillReturn>(*this, IPos, DepClassTy::REQUIRED);
3464 if (WillReturnAA.isKnownWillReturn())
3465 return true;
3466 if (!WillReturnAA.isAssumedWillReturn())
3467 return false;
3468 const auto &NoRecurseAA =
3469 A.getAAFor<AANoRecurse>(*this, IPos, DepClassTy::REQUIRED);
3470 return NoRecurseAA.isAssumedNoRecurse();
3471 };
3472
3473 bool UsedAssumedInformation = false;
3474 if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this,
3475 UsedAssumedInformation))
3476 return indicatePessimisticFixpoint();
3477
3478 return ChangeStatus::UNCHANGED;
3479 }
3480
3481 /// See AbstractAttribute::getAsStr()
3482 const std::string getAsStr() const override {
3483 return getAssumed() ? "willreturn" : "may-noreturn";
3484 }
3485};
3486
3487struct AAWillReturnFunction final : AAWillReturnImpl {
3488 AAWillReturnFunction(const IRPosition &IRP, Attributor &A)
3489 : AAWillReturnImpl(IRP, A) {}
3490
3491 /// See AbstractAttribute::initialize(...).
3492 void initialize(Attributor &A) override {
3493 AAWillReturnImpl::initialize(A);
3494
3495 Function *F = getAnchorScope();
3496 if (!F || F->isDeclaration() || mayContainUnboundedCycle(*F, A))
3497 indicatePessimisticFixpoint();
3498 }
3499
3500 /// See AbstractAttribute::trackStatistics()
3501 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(willreturn) }
3502};
3503
3504/// WillReturn attribute deduction for a call sites.
3505struct AAWillReturnCallSite final : AAWillReturnImpl {
3506 AAWillReturnCallSite(const IRPosition &IRP, Attributor &A)
3507 : AAWillReturnImpl(IRP, A) {}
3508
3509 /// See AbstractAttribute::initialize(...).
3510 void initialize(Attributor &A) override {
3511 AAWillReturnImpl::initialize(A);
3512 Function *F = getAssociatedFunction();
3513 if (!F || !A.isFunctionIPOAmendable(*F))
3514 indicatePessimisticFixpoint();
3515 }
3516
3517 /// See AbstractAttribute::updateImpl(...).
3518 ChangeStatus updateImpl(Attributor &A) override {
3519 if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ false))
3520 return ChangeStatus::UNCHANGED;
3521
3522 // TODO: Once we have call site specific value information we can provide
3523 // call site specific liveness information and then it makes
3524 // sense to specialize attributes for call sites arguments instead of
3525 // redirecting requests to the callee argument.
3526 Function *F = getAssociatedFunction();
3527 const IRPosition &FnPos = IRPosition::function(*F);
3528 auto &FnAA = A.getAAFor<AAWillReturn>(*this, FnPos, DepClassTy::REQUIRED);
3529 return clampStateAndIndicateChange(getState(), FnAA.getState());
3530 }
3531
3532 /// See AbstractAttribute::trackStatistics()
3533 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); }
3534};
3535} // namespace
3536
3537/// -------------------AAIntraFnReachability Attribute--------------------------
3538
3539/// All information associated with a reachability query. This boilerplate code
3540/// is used by both AAIntraFnReachability and AAInterFnReachability, with
3541/// different \p ToTy values.
3542template <typename ToTy> struct ReachabilityQueryInfo {
3543 enum class Reachable {
3544 No,
3545 Yes,
3546 };
3547
3548 /// Start here,
3549 const Instruction *From = nullptr;
3550 /// reach this place,
3551 const ToTy *To = nullptr;
3552 /// without going through any of these instructions,
3553 const AA::InstExclusionSetTy *ExclusionSet = nullptr;
3554 /// and remember if it worked:
3555 Reachable Result = Reachable::No;
3556
3558 : From(From), To(To) {}
3559
3560 /// Constructor replacement to ensure unique and stable sets are used for the
3561 /// cache.
3563 const AA::InstExclusionSetTy *ES, bool MakeUnique)
3564 : From(&From), To(&To), ExclusionSet(ES) {
3565
3566 if (!ES || ES->empty()) {
3567 ExclusionSet = nullptr;
3568 } else if (MakeUnique) {
3569 ExclusionSet = A.getInfoCache().getOrCreateUniqueBlockExecutionSet(ES);
3570 }
3571 }
3572
3574 : From(RQI.From), To(RQI.To), ExclusionSet(RQI.ExclusionSet) {}
3575};
3576
3577namespace llvm {
3578template <typename ToTy> struct DenseMapInfo<ReachabilityQueryInfo<ToTy> *> {
3581
3584
3585 static inline ReachabilityQueryInfo<ToTy> *getEmptyKey() { return &EmptyKey; }
3587 return &TombstoneKey;
3588 }
3589 static unsigned getHashValue(const ReachabilityQueryInfo<ToTy> *RQI) {
3590 unsigned H = PairDMI ::getHashValue({RQI->From, RQI->To});
3591 H += InstSetDMI::getHashValue(RQI->ExclusionSet);
3592 return H;
3593 }
3596 if (!PairDMI::isEqual({LHS->From, LHS->To}, {RHS->From, RHS->To}))
3597 return false;
3598 return InstSetDMI::isEqual(LHS->ExclusionSet, RHS->ExclusionSet);
3599 }
3600};
3601
3602#define DefineKeys(ToTy) \
3603 template <> \
3604 ReachabilityQueryInfo<ToTy> \
3605 DenseMapInfo<ReachabilityQueryInfo<ToTy> *>::EmptyKey = \
3606 ReachabilityQueryInfo<ToTy>( \
3607 DenseMapInfo<const Instruction *>::getEmptyKey(), \
3608 DenseMapInfo<const ToTy *>::getEmptyKey()); \
3609 template <> \
3610 ReachabilityQueryInfo<ToTy> \
3611 DenseMapInfo<ReachabilityQueryInfo<ToTy> *>::TombstoneKey = \
3612 ReachabilityQueryInfo<ToTy>( \
3613 DenseMapInfo<const Instruction *>::getTombstoneKey(), \
3614 DenseMapInfo<const ToTy *>::getTombstoneKey());
3615
3617#undef DefineKeys
3618
3619} // namespace llvm
3620
3621namespace {
3622
3623template <typename BaseTy, typename ToTy>
3624struct CachedReachabilityAA : public BaseTy {
3625 using RQITy = ReachabilityQueryInfo<ToTy>;
3626
3627 CachedReachabilityAA<BaseTy, ToTy>(const IRPosition &IRP, Attributor &A)
3628 : BaseTy(IRP, A) {}
3629
3630 /// See AbstractAttribute::isQueryAA.
3631 bool isQueryAA() const override { return true; }
3632
3633 /// See AbstractAttribute::updateImpl(...).
3634 ChangeStatus updateImpl(Attributor &A) override {
3635 ChangeStatus Changed = ChangeStatus::UNCHANGED;
3636 InUpdate = true;
3637 for (unsigned u = 0, e = QueryVector.size(); u < e; ++u) {
3638 RQITy *RQI = QueryVector[u];
3639 if (RQI->Result == RQITy::Reachable::No && isReachableImpl(A, *RQI))
3640 Changed = ChangeStatus::CHANGED;
3641 }
3642 InUpdate = false;
3643 return Changed;
3644 }
3645
3646 virtual bool isReachableImpl(Attributor &A, RQITy &RQI) = 0;
3647
3648 bool rememberResult(Attributor &A, typename RQITy::Reachable Result,
3649 RQITy &RQI, bool UsedExclusionSet) {
3650 RQI.Result = Result;
3651
3652 // Remove the temporary RQI from the cache.
3653 if (!InUpdate)
3654 QueryCache.erase(&RQI);
3655
3656 // Insert a plain RQI (w/o exclusion set) if that makes sense. Two options:
3657 // 1) If it is reachable, it doesn't matter if we have an exclusion set for this query.
3658 // 2) We did not use the exclusion set, potentially because there is none.
3659 if (Result == RQITy::Reachable::Yes || !UsedExclusionSet) {
3660 RQITy PlainRQI(RQI.From, RQI.To);
3661 if (!QueryCache.count(&PlainRQI)) {
3662 RQITy *RQIPtr = new (A.Allocator) RQITy(RQI.From, RQI.To);
3663 RQIPtr->Result = Result;
3664 QueryVector.push_back(RQIPtr);
3665 QueryCache.insert(RQIPtr);
3666 }
3667 }
3668
3669 // Check if we need to insert a new permanent RQI with the exclusion set.
3670 if (!InUpdate && Result != RQITy::Reachable::Yes && UsedExclusionSet) {
3671 assert((!RQI.ExclusionSet || !RQI.ExclusionSet->empty()) &&
3672 "Did not expect empty set!");
3673 RQITy *RQIPtr = new (A.Allocator)
3674 RQITy(A, *RQI.From, *RQI.To, RQI.ExclusionSet, true);
3675 assert(RQIPtr->Result == RQITy::Reachable::No && "Already reachable?");
3676 RQIPtr->Result = Result;
3677 assert(!QueryCache.count(RQIPtr));
3678 QueryVector.push_back(RQIPtr);
3679 QueryCache.insert(RQIPtr);
3680 }
3681
3682 if (Result == RQITy::Reachable::No && !InUpdate)
3683 A.registerForUpdate(*this);
3684 return Result == RQITy::Reachable::Yes;
3685 }
3686
3687 const std::string getAsStr() const override {
3688 // TODO: Return the number of reachable queries.
3689 return "#queries(" + std::to_string(QueryVector.size()) + ")";
3690 }
3691
3692 bool checkQueryCache(Attributor &A, RQITy &StackRQI,
3693 typename RQITy::Reachable &Result) {
3694 if (!this->getState().isValidState()) {
3695 Result = RQITy::Reachable::Yes;
3696 return true;
3697 }
3698
3699 // If we have an exclusion set we might be able to find our answer by
3700 // ignoring it first.
3701 if (StackRQI.ExclusionSet) {
3702 RQITy PlainRQI(StackRQI.From, StackRQI.To);
3703 auto It = QueryCache.find(&PlainRQI);
3704 if (It != QueryCache.end() && (*It)->Result == RQITy::Reachable::No) {
3705 Result = RQITy::Reachable::No;
3706 return true;
3707 }
3708 }
3709
3710 auto It = QueryCache.find(&StackRQI);
3711 if (It != QueryCache.end()) {
3712 Result = (*It)->Result;
3713 return true;
3714 }
3715
3716 // Insert a temporary for recursive queries. We will replace it with a
3717 // permanent entry later.
3718 QueryCache.insert(&StackRQI);
3719 return false;
3720 }
3721
3722private:
3723 bool InUpdate = false;
3724 SmallVector<RQITy *> QueryVector;
3725 DenseSet<RQITy *> QueryCache;
3726};
3727
3728struct AAIntraFnReachabilityFunction final
3729 : public CachedReachabilityAA<AAIntraFnReachability, Instruction> {
3730 using Base = CachedReachabilityAA<AAIntraFnReachability, Instruction>;
3731 AAIntraFnReachabilityFunction(const IRPosition &IRP, Attributor &A)
3732 : Base(IRP, A) {}
3733
3734 bool isAssumedReachable(
3735 Attributor &A, const Instruction &From, const Instruction &To,
3736 const AA::InstExclusionSetTy *ExclusionSet) const override {
3737 auto *NonConstThis = const_cast<AAIntraFnReachabilityFunction *>(this);
3738 if (&From == &To)
3739 return true;
3740
3741 RQITy StackRQI(A, From, To, ExclusionSet, false);
3742 typename RQITy::Reachable Result;
3743 if (!NonConstThis->checkQueryCache(A, StackRQI, Result))
3744 return NonConstThis->isReachableImpl(A, StackRQI);
3745 return Result == RQITy::Reachable::Yes;
3746 }
3747
3748 ChangeStatus updateImpl(Attributor &A) override {
3749 // We only depend on liveness. DeadEdges is all we care about, check if any
3750 // of them changed.
3751 auto &LivenessAA =
3752 A.getAAFor<AAIsDead>(*this, getIRPosition(), DepClassTy::OPTIONAL);
3753 if (llvm::all_of(DeadEdges, [&](const auto &DeadEdge) {
3754 return LivenessAA.isEdgeDead(DeadEdge.first, DeadEdge.second);
3755 })) {
3756 return ChangeStatus::UNCHANGED;
3757 }
3758 DeadEdges.clear();
3759 return Base::updateImpl(A);
3760 }
3761
3762 bool isReachableImpl(Attributor &A, RQITy &RQI) override {
3763 const Instruction *Origin = RQI.From;
3764 bool UsedExclusionSet = false;
3765
3766 auto WillReachInBlock = [&](const Instruction &From, const Instruction &To,
3767 const AA::InstExclusionSetTy *ExclusionSet) {
3768 const Instruction *IP = &From;
3769 while (IP && IP != &To) {
3770 if (ExclusionSet && IP != Origin && ExclusionSet->count(IP)) {
3771 UsedExclusionSet = true;
3772 break;
3773 }
3774 IP = IP->getNextNode();
3775 }
3776 return IP == &To;
3777 };
3778
3779 const BasicBlock *FromBB = RQI.From->getParent();
3780 const BasicBlock *ToBB = RQI.To->getParent();
3781 assert(FromBB->getParent() == ToBB->getParent() &&
3782 "Not an intra-procedural query!");
3783
3784 // Check intra-block reachability, however, other reaching paths are still
3785 // possible.
3786 if (FromBB == ToBB &&
3787 WillReachInBlock(*RQI.From, *RQI.To, RQI.ExclusionSet))
3788 return rememberResult(A, RQITy::Reachable::Yes, RQI, UsedExclusionSet);
3789
3790 // Check if reaching the ToBB block is sufficient or if even that would not
3791 // ensure reaching the target. In the latter case we are done.
3792 if (!WillReachInBlock(ToBB->front(), *RQI.To, RQI.ExclusionSet))
3793 return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet);
3794
3796 if (RQI.ExclusionSet)
3797 for (auto *I : *RQI.ExclusionSet)
3798 ExclusionBlocks.insert(I->getParent());
3799
3800 // Check if we make it out of the FromBB block at all.
3801 if (ExclusionBlocks.count(FromBB) &&
3802 !WillReachInBlock(*RQI.From, *FromBB->getTerminator(),
3803 RQI.ExclusionSet))
3804 return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet);
3805
3808 Worklist.push_back(FromBB);
3809
3811 auto &LivenessAA =
3812 A.getAAFor<AAIsDead>(*this, getIRPosition(), DepClassTy::OPTIONAL);
3813 while (!Worklist.empty()) {
3814 const BasicBlock *BB = Worklist.pop_back_val();
3815 if (!Visited.insert(BB).second)
3816 continue;
3817 for (const BasicBlock *SuccBB : successors(BB)) {
3818 if (LivenessAA.isEdgeDead(BB, SuccBB)) {
3819 LocalDeadEdges.insert({BB, SuccBB});
3820 continue;
3821 }
3822 // We checked before if we just need to reach the ToBB block.
3823 if (SuccBB == ToBB)
3824 return rememberResult(A, RQITy::Reachable::Yes, RQI,
3825 UsedExclusionSet);
3826 if (ExclusionBlocks.count(SuccBB)) {
3827 UsedExclusionSet = true;
3828 continue;
3829 }
3830 Worklist.push_back(SuccBB);
3831 }
3832 }
3833
3834 DeadEdges.insert(LocalDeadEdges.begin(), LocalDeadEdges.end());
3835 return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet);
3836 }
3837
3838 /// See AbstractAttribute::trackStatistics()
3839 void trackStatistics() const override {}
3840
3841private:
3842 // Set of assumed dead edges we used in the last query. If any changes we
3843 // update the state.
3845};
3846} // namespace
3847
3848/// ------------------------ NoAlias Argument Attribute ------------------------
3849
3850namespace {
3851struct AANoAliasImpl : AANoAlias {
3852 AANoAliasImpl(const IRPosition &IRP, Attributor &A) : AANoAlias(IRP, A) {
3853 assert(getAssociatedType()->isPointerTy() &&
3854 "Noalias is a pointer attribute");
3855 }
3856
3857 const std::string getAsStr() const override {
3858 return getAssumed() ? "noalias" : "may-alias";
3859 }
3860};
3861
3862/// NoAlias attribute for a floating value.
3863struct AANoAliasFloating final : AANoAliasImpl {
3864 AANoAliasFloating(const IRPosition &IRP, Attributor &A)
3865 : AANoAliasImpl(IRP, A) {}
3866
3867 /// See AbstractAttribute::initialize(...).
3868 void initialize(Attributor &A) override {
3869 AANoAliasImpl::initialize(A);
3870 Value *Val = &getAssociatedValue();
3871 do {
3872 CastInst *CI = dyn_cast<CastInst>(Val);
3873 if (!CI)
3874 break;
3875 Value *Base = CI->getOperand(0);
3876 if (!Base->hasOneUse())
3877 break;
3878 Val = Base;
3879 } while (true);
3880
3881 if (!Val->getType()->isPointerTy()) {
3882 indicatePessimisticFixpoint();
3883 return;
3884 }
3885
3886 if (isa<AllocaInst>(Val))
3887 indicateOptimisticFixpoint();
3888 else if (isa<ConstantPointerNull>(Val) &&
3889 !NullPointerIsDefined(getAnchorScope(),
3891 indicateOptimisticFixpoint();
3892 else if (Val != &getAssociatedValue()) {
3893 const auto &ValNoAliasAA = A.getAAFor<AANoAlias>(
3894 *this, IRPosition::value(*Val), DepClassTy::OPTIONAL);
3895 if (ValNoAliasAA.isKnownNoAlias())
3896 indicateOptimisticFixpoint();
3897 }
3898 }
3899
3900 /// See AbstractAttribute::updateImpl(...).
3901 ChangeStatus updateImpl(Attributor &A) override {
3902 // TODO: Implement this.
3903 return indicatePessimisticFixpoint();
3904 }
3905
3906 /// See AbstractAttribute::trackStatistics()
3907 void trackStatistics() const override {
3909 }
3910};
3911
3912/// NoAlias attribute for an argument.
3913struct AANoAliasArgument final
3914 : AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl> {
3915 using Base = AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl>;
3916 AANoAliasArgument(const IRPosition &IRP, Attributor &A) : Base(IRP, A) {}
3917
3918 /// See AbstractAttribute::initialize(...).
3919 void initialize(Attributor &A) override {
3920 Base::initialize(A);
3921 // See callsite argument attribute and callee argument attribute.
3922 if (hasAttr({Attribute::ByVal}))
3923 indicateOptimisticFixpoint();
3924 }
3925
3926 /// See AbstractAttribute::update(...).
3927 ChangeStatus updateImpl(Attributor &A) override {
3928 // We have to make sure no-alias on the argument does not break
3929 // synchronization when this is a callback argument, see also [1] below.
3930 // If synchronization cannot be affected, we delegate to the base updateImpl
3931 // function, otherwise we give up for now.
3932
3933 // If the function is no-sync, no-alias cannot break synchronization.
3934 const auto &NoSyncAA =
3935 A.getAAFor<AANoSync>(*this, IRPosition::function_scope(getIRPosition()),
3936 DepClassTy::OPTIONAL);
3937 if (NoSyncAA.isAssumedNoSync())
3938 return Base::updateImpl(A);
3939
3940 // If the argument is read-only, no-alias cannot break synchronization.
3941 bool IsKnown;
3942 if (AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown))
3943 return Base::updateImpl(A);
3944
3945 // If the argument is never passed through callbacks, no-alias cannot break
3946 // synchronization.
3947 bool UsedAssumedInformation = false;
3948 if (A.checkForAllCallSites(
3949 [](AbstractCallSite ACS) { return !ACS.isCallbackCall(); }, *this,
3950 true, UsedAssumedInformation))
3951 return Base::updateImpl(A);
3952
3953 // TODO: add no-alias but make sure it doesn't break synchronization by
3954 // introducing fake uses. See:
3955 // [1] Compiler Optimizations for OpenMP, J. Doerfert and H. Finkel,
3956 // International Workshop on OpenMP 2018,
3957 // http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf
3958
3959 return indicatePessimisticFixpoint();
3960 }
3961
3962 /// See AbstractAttribute::trackStatistics()
3963 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noalias) }
3964};
3965
3966struct AANoAliasCallSiteArgument final : AANoAliasImpl {
3967 AANoAliasCallSiteArgument(const IRPosition &IRP, Attributor &A)
3968 : AANoAliasImpl(IRP, A) {}
3969
3970 /// See AbstractAttribute::initialize(...).
3971 void initialize(Attributor &A) override {
3972 // See callsite argument attribute and callee argument attribute.
3973 const auto &CB = cast<CallBase>(getAnchorValue());
3974 if (CB.paramHasAttr(getCallSiteArgNo(), Attribute::NoAlias))
3975 indicateOptimisticFixpoint();
3976 Value &Val = getAssociatedValue();
3977 if (isa<ConstantPointerNull>(Val) &&
3978 !NullPointerIsDefined(getAnchorScope(),
3980 indicateOptimisticFixpoint();
3981 }
3982
3983 /// Determine if the underlying value may alias with the call site argument
3984 /// \p OtherArgNo of \p ICS (= the underlying call site).
3985 bool mayAliasWithArgument(Attributor &A, AAResults *&AAR,
3986 const AAMemoryBehavior &MemBehaviorAA,
3987 const CallBase &CB, unsigned OtherArgNo) {
3988 // We do not need to worry about aliasing with the underlying IRP.
3989 if (this->getCalleeArgNo() == (int)OtherArgNo)
3990 return false;
3991
3992 // If it is not a pointer or pointer vector we do not alias.
3993 const Value *ArgOp = CB.getArgOperand(OtherArgNo);
3994 if (!ArgOp->getType()->isPtrOrPtrVectorTy())
3995 return false;
3996
3997 auto &CBArgMemBehaviorAA = A.getAAFor<AAMemoryBehavior>(
3998 *this, IRPosition::callsite_argument(CB, OtherArgNo), DepClassTy::NONE);
3999
4000 // If the argument is readnone, there is no read-write aliasing.
4001 if (CBArgMemBehaviorAA.isAssumedReadNone()) {
4002 A.recordDependence(CBArgMemBehaviorAA, *this, DepClassTy::OPTIONAL);
4003 return false;
4004 }
4005
4006 // If the argument is readonly and the underlying value is readonly, there
4007 // is no read-write aliasing.
4008 bool IsReadOnly = MemBehaviorAA.isAssumedReadOnly();
4009 if (CBArgMemBehaviorAA.isAssumedReadOnly() && IsReadOnly) {
4010 A.recordDependence(MemBehaviorAA, *this, DepClassTy::OPTIONAL);
4011 A.recordDependence(CBArgMemBehaviorAA, *this, DepClassTy::OPTIONAL);
4012 return false;
4013 }
4014
4015 // We have to utilize actual alias analysis queries so we need the object.
4016 if (!AAR)
4017 AAR = A.getInfoCache().getAAResultsForFunction(*getAnchorScope());
4018
4019 // Try to rule it out at the call site.
4020 bool IsAliasing = !AAR || !AAR->isNoAlias(&getAssociatedValue(), ArgOp);
4021 LLVM_DEBUG(dbgs() << "[NoAliasCSArg] Check alias between "
4022 "callsite arguments: "
4023 << getAssociatedValue() << " " << *ArgOp << " => "
4024 << (IsAliasing ? "" : "no-") << "alias \n");
4025
4026 return IsAliasing;
4027 }
4028
4029 bool
4030 isKnownNoAliasDueToNoAliasPreservation(Attributor &A, AAResults *&AAR,
4031 const AAMemoryBehavior &MemBehaviorAA,
4032 const AANoAlias &NoAliasAA) {
4033 // We can deduce "noalias" if the following conditions hold.
4034 // (i) Associated value is assumed to be noalias in the definition.
4035 // (ii) Associated value is assumed to be no-capture in all the uses
4036 // possibly executed before this callsite.
4037 // (iii) There is no other pointer argument which could alias with the
4038 // value.
4039
4040 bool AssociatedValueIsNoAliasAtDef = NoAliasAA.isAssumedNoAlias();
4041 if (!AssociatedValueIsNoAliasAtDef) {
4042 LLVM_DEBUG(dbgs() << "[AANoAlias] " << getAssociatedValue()
4043 << " is not no-alias at the definition\n");
4044 return false;
4045 }
4046
4047 auto IsDereferenceableOrNull = [&](Value *O, const DataLayout &DL) {
4048 const auto &DerefAA = A.getAAFor<AADereferenceable>(
4049 *this, IRPosition::value(*O), DepClassTy::OPTIONAL);
4050 return DerefAA.getAssumedDereferenceableBytes();
4051 };
4052
4053 A.recordDependence(NoAliasAA, *this, DepClassTy::OPTIONAL);
4054
4055 const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
4056 const Function *ScopeFn = VIRP.getAnchorScope();
4057 auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, VIRP, DepClassTy::NONE);
4058 // Check whether the value is captured in the scope using AANoCapture.
4059 // Look at CFG and check only uses possibly executed before this
4060 // callsite.
4061 auto UsePred = [&](const Use &U, bool &Follow) -> bool {
4062 Instruction *UserI = cast<Instruction>(U.getUser());
4063
4064 // If UserI is the curr instruction and there is a single potential use of
4065 // the value in UserI we allow the use.
4066 // TODO: We should inspect the operands and allow those that cannot alias
4067 // with the value.
4068 if (UserI == getCtxI() && UserI->getNumOperands() == 1)
4069 return true;
4070
4071 if (ScopeFn) {
4072 if (auto *CB = dyn_cast<CallBase>(UserI)) {
4073 if (CB->isArgOperand(&U)) {
4074
4075 unsigned ArgNo = CB->getArgOperandNo(&U);
4076
4077 const auto &NoCaptureAA = A.getAAFor<AANoCapture>(
4078 *this, IRPosition::callsite_argument(*CB, ArgNo),
4079 DepClassTy::OPTIONAL);
4080
4081 if (NoCaptureAA.isAssumedNoCapture())
4082 return true;
4083 }
4084 }
4085
4087 A, *UserI, *getCtxI(), *this, /* ExclusionSet */ nullptr,
4088 [ScopeFn](const Function &Fn) { return &Fn != ScopeFn; }))
4089 return true;
4090 }
4091
4092 // TODO: We should track the capturing uses in AANoCapture but the problem
4093 // is CGSCC runs. For those we would need to "allow" AANoCapture for
4094 // a value in the module slice.
4095 switch (DetermineUseCaptureKind(U, IsDereferenceableOrNull)) {
4096 case UseCaptureKind::NO_CAPTURE:
4097 return true;
4098 case UseCaptureKind::MAY_CAPTURE:
4099 LLVM_DEBUG(dbgs() << "[AANoAliasCSArg] Unknown user: " << *UserI
4100 << "\n");
4101 return false;
4102 case UseCaptureKind::PASSTHROUGH:
4103 Follow = true;
4104 return true;
4105 }
4106 llvm_unreachable("unknown UseCaptureKind");
4107 };
4108
4109 if (!NoCaptureAA.isAssumedNoCaptureMaybeReturned()) {
4110 if (!A.checkForAllUses(UsePred, *this, getAssociatedValue())) {
4111 LLVM_DEBUG(
4112 dbgs() << "[AANoAliasCSArg] " << getAssociatedValue()
4113 << " cannot be noalias as it is potentially captured\n");
4114 return false;
4115 }
4116 }
4117 A.recordDependence(NoCaptureAA, *this, DepClassTy::OPTIONAL);
4118
4119 // Check there is no other pointer argument which could alias with the
4120 // value passed at this call site.
4121 // TODO: AbstractCallSite
4122 const auto &CB = cast<CallBase>(getAnchorValue());
4123 for (unsigned OtherArgNo = 0; OtherArgNo < CB.arg_size(); OtherArgNo++)
4124 if (mayAliasWithArgument(A, AAR, MemBehaviorAA, CB, OtherArgNo))
4125 return false;
4126
4127 return true;
4128 }
4129
4130 /// See AbstractAttribute::updateImpl(...).
4131 ChangeStatus updateImpl(Attributor &A) override {
4132 // If the argument is readnone we are done as there are no accesses via the
4133 // argument.
4134 auto &MemBehaviorAA =
4135 A.getAAFor<AAMemoryBehavior>(*this, getIRPosition(), DepClassTy::NONE);
4136 if (MemBehaviorAA.isAssumedReadNone()) {
4137 A.recordDependence(MemBehaviorAA, *this, DepClassTy::OPTIONAL);
4138 return ChangeStatus::UNCHANGED;
4139 }
4140
4141 const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
4142 const auto &NoAliasAA =
4143 A.getAAFor<AANoAlias>(*this, VIRP, DepClassTy::NONE);
4144
4145 AAResults *AAR = nullptr;
4146 if (isKnownNoAliasDueToNoAliasPreservation(A, AAR, MemBehaviorAA,
4147 NoAliasAA)) {
4148 LLVM_DEBUG(
4149 dbgs() << "[AANoAlias] No-Alias deduced via no-alias preservation\n");
4150 return ChangeStatus::UNCHANGED;
4151 }
4152
4153 return indicatePessimisticFixpoint();
4154 }
4155
4156 /// See AbstractAttribute::trackStatistics()
4157 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(noalias) }
4158};
4159
4160/// NoAlias attribute for function return value.
4161struct AANoAliasReturned final : AANoAliasImpl {
4162 AANoAliasReturned(const IRPosition &IRP, Attributor &A)
4163 : AANoAliasImpl(IRP, A) {}
4164
4165 /// See AbstractAttribute::initialize(...).
4166 void initialize(Attributor &A) override {
4167 AANoAliasImpl::initialize(A);
4168 Function *F = getAssociatedFunction();
4169 if (!F || F->isDeclaration())
4170 indicatePessimisticFixpoint();
4171 }
4172
4173 /// See AbstractAttribute::updateImpl(...).
4174 ChangeStatus updateImpl(Attributor &A) override {
4175
4176 auto CheckReturnValue = [&](Value &RV) -> bool {
4177 if (Constant *C = dyn_cast<Constant>(&RV))
4178 if (C->isNullValue() || isa<UndefValue>(C))
4179 return true;
4180
4181 /// For now, we can only deduce noalias if we have call sites.
4182 /// FIXME: add more support.
4183 if (!isa<CallBase>(&RV))
4184 return false;
4185
4186 const IRPosition &RVPos = IRPosition::value(RV);
4187 const auto &NoAliasAA =
4188 A.getAAFor<AANoAlias>(*this, RVPos, DepClassTy::REQUIRED);
4189 if (!NoAliasAA.isAssumedNoAlias())
4190 return false;
4191
4192 const auto &NoCaptureAA =
4193 A.getAAFor<AANoCapture>(*this, RVPos, DepClassTy::REQUIRED);
4194 return NoCaptureAA.isAssumedNoCaptureMaybeReturned();
4195 };
4196
4197 if (!A.checkForAllReturnedValues(CheckReturnValue, *this))
4198 return indicatePessimisticFixpoint();
4199
4200 return ChangeStatus::UNCHANGED;
4201 }
4202
4203 /// See AbstractAttribute::trackStatistics()
4204 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(noalias) }
4205};
4206
4207/// NoAlias attribute deduction for a call site return value.
4208struct AANoAliasCallSiteReturned final : AANoAliasImpl {
4209 AANoAliasCallSiteReturned(const IRPosition &IRP, Attributor &A)
4210 : AANoAliasImpl(IRP, A) {}
4211
4212 /// See AbstractAttribute::initialize(...).
4213 void initialize(Attributor &A) override {
4214 AANoAliasImpl::initialize(A);
4215 Function *F = getAssociatedFunction();
4216 if (!F || F->isDeclaration())
4217 indicatePessimisticFixpoint();
4218 }
4219
4220 /// See AbstractAttribute::updateImpl(...).
4221 ChangeStatus updateImpl(Attributor &A) override {
4222 // TODO: Once we have call site specific value information we can provide
4223 // call site specific liveness information and then it makes
4224 // sense to specialize attributes for call sites arguments instead of
4225 // redirecting requests to the callee argument.
4226 Function *F = getAssociatedFunction();
4227 const IRPosition &FnPos = IRPosition::returned(*F);
4228 auto &FnAA = A.getAAFor<AANoAlias>(*this, FnPos, DepClassTy::REQUIRED);
4229 return clampStateAndIndicateChange(getState(), FnAA.getState());
4230 }
4231
4232 /// See AbstractAttribute::trackStatistics()
4233 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noalias); }
4234};
4235} // namespace
4236
4237/// -------------------AAIsDead Function Attribute-----------------------
4238
4239namespace {
4240struct AAIsDeadValueImpl : public AAIsDead {
4241 AAIsDeadValueImpl(const IRPosition &IRP, Attributor &A) : AAIsDead(IRP, A) {}
4242
4243 /// See AbstractAttribute::initialize(...).
4244 void initialize(Attributor &A) override {
4245 if (auto *Scope = getAnchorScope())
4246 if (!A.isRunOn(*Scope))
4247 indicatePessimisticFixpoint();
4248 }
4249
4250 /// See AAIsDead::isAssumedDead().
4251 bool isAssumedDead() const override { return isAssumed(IS_DEAD); }
4252
4253 /// See AAIsDead::isKnownDead().
4254 bool isKnownDead() const override { return isKnown(IS_DEAD); }
4255
4256 /// See AAIsDead::isAssumedDead(BasicBlock *).
4257 bool isAssumedDead(const BasicBlock *BB) const override { return false; }
4258
4259 /// See AAIsDead::isKnownDead(BasicBlock *).
4260 bool isKnownDead(const BasicBlock *BB) const override { return false; }
4261
4262 /// See AAIsDead::isAssumedDead(Instruction *I).
4263 bool isAssumedDead(const Instruction *I) const override {
4264 return I == getCtxI() && isAssumedDead();
4265 }
4266
4267 /// See AAIsDead::isKnownDead(Instruction *I).
4268 bool isKnownDead(const Instruction *I) const override {
4269 return isAssumedDead(I) && isKnownDead();
4270 }
4271
4272 /// See AbstractAttribute::getAsStr().
4273 const std::string getAsStr() const override {
4274 return isAssumedDead() ? "assumed-dead" : "assumed-live";
4275 }
4276
4277 /// Check if all uses are assumed dead.
4278 bool areAllUsesAssumedDead(Attributor &A, Value &V) {
4279 // Callers might not check the type, void has no uses.
4280 if (V.getType()->isVoidTy() || V.use_empty())
4281 return true;
4282
4283 // If we replace a value with a constant there are no uses left afterwards.
4284 if (!isa<Constant>(V)) {
4285 if (auto *I = dyn_cast<Instruction>(&V))
4286 if (!A.isRunOn(*I->getFunction()))
4287 return false;
4288 bool UsedAssumedInformation = false;
4289 std::optional<Constant *> C =
4290 A.getAssumedConstant(V, *this, UsedAssumedInformation);
4291 if (!C || *C)
4292 return true;
4293 }
4294
4295 auto UsePred = [&](const Use &U, bool &Follow) { return false; };
4296 // Explicitly set the dependence class to required because we want a long
4297 // chain of N dependent instructions to be considered live as soon as one is
4298 // without going through N update cycles. This is not required for
4299 // correctness.
4300 return A.checkForAllUses(UsePred, *this, V, /* CheckBBLivenessOnly */ false,
4301 DepClassTy::REQUIRED,
4302 /* IgnoreDroppableUses */ false);
4303 }
4304
4305 /// Determine if \p I is assumed to be side-effect free.
4306 bool isAssumedSideEffectFree(Attributor &A, Instruction *I) {
4308 return true;
4309
4310 auto *CB = dyn_cast<CallBase>(I);
4311 if (!CB || isa<IntrinsicInst>(CB))
4312 return false;
4313
4314 const IRPosition &CallIRP = IRPosition::callsite_function(*CB);
4315 const auto &NoUnwindAA =
4316 A.getAndUpdateAAFor<AANoUnwind>(*this, CallIRP, DepClassTy::NONE);
4317 if (!NoUnwindAA.isAssumedNoUnwind())
4318 return false;
4319 if (!NoUnwindAA.isKnownNoUnwind())
4320 A.recordDependence(NoUnwindAA, *this, DepClassTy::OPTIONAL);
4321
4322 bool IsKnown;
4323 return AA::isAssumedReadOnly(A, CallIRP, *this, IsKnown);
4324 }
4325};
4326
4327struct AAIsDeadFloating : public AAIsDeadValueImpl {
4328 AAIsDeadFloating(const IRPosition &IRP, Attributor &A)
4329 : AAIsDeadValueImpl(IRP, A) {}
4330
4331 /// See AbstractAttribute::initialize(...).
4332 void initialize(Attributor &A) override {
4333 AAIsDeadValueImpl::initialize(A);
4334
4335 if (isa<UndefValue>(getAssociatedValue())) {
4336 indicatePessimisticFixpoint();
4337 return;
4338 }
4339
4340 Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
4341 if (!isAssumedSideEffectFree(A, I)) {
4342 if (!isa_and_nonnull<StoreInst>(I) && !isa_and_nonnull<FenceInst>(I))
4343 indicatePessimisticFixpoint();
4344 else
4345 removeAssumedBits(HAS_NO_EFFECT);
4346 }
4347 }
4348
4349 bool isDeadFence(Attributor &A, FenceInst &FI) {
4350 const auto *ExecDomainAA = A.lookupAAFor<AAExecutionDomain>(
4351 IRPosition::function(*FI.getFunction()), *this, DepClassTy::NONE);
4352 if (!ExecDomainAA || !ExecDomainAA->isNoOpFence(FI))
4353 return false;
4354 A.recordDependence(*ExecDomainAA, *this, DepClassTy::OPTIONAL);
4355 return true;
4356 }
4357
4358 bool isDeadStore(Attributor &A, StoreInst &SI,
4359 SmallSetVector<Instruction *, 8> *AssumeOnlyInst = nullptr) {
4360 // Lang ref now states volatile store is not UB/dead, let's skip them.
4361 if (SI.isVolatile())
4362 return false;
4363
4364 // If we are collecting assumes to be deleted we are in the manifest stage.
4365 // It's problematic to collect the potential copies again now so we use the
4366 // cached ones.
4367 bool UsedAssumedInformation = false;
4368 if (!AssumeOnlyInst) {
4369 PotentialCopies.clear();
4370 if (!AA::getPotentialCopiesOfStoredValue(A, SI, PotentialCopies, *this,
4371 UsedAssumedInformation)) {
4372 LLVM_DEBUG(
4373 dbgs()
4374 << "[AAIsDead] Could not determine potential copies of store!\n");
4375 return false;
4376 }
4377 }
4378 LLVM_DEBUG(dbgs() << "[AAIsDead] Store has " << PotentialCopies.size()
4379 << " potential copies.\n");
4380
4381 InformationCache &InfoCache = A.getInfoCache();
4382 return llvm::all_of(PotentialCopies, [&](Value *V) {
4383 if (A.isAssumedDead(IRPosition::value(*V), this, nullptr,
4384 UsedAssumedInformation))
4385 return true;
4386 if (auto *LI = dyn_cast<LoadInst>(V)) {
4387 if (llvm::all_of(LI->uses(), [&](const Use &U) {
4388 auto &UserI = cast<Instruction>(*U.getUser());
4389 if (InfoCache.isOnlyUsedByAssume(UserI)) {
4390 if (AssumeOnlyInst)
4391 AssumeOnlyInst->insert(&UserI);
4392 return true;
4393 }
4394 return A.isAssumedDead(U, this, nullptr, UsedAssumedInformation);
4395 })) {
4396 return true;
4397 }
4398 }
4399 LLVM_DEBUG(dbgs() << "[AAIsDead] Potential copy " << *V
4400 << " is assumed live!\n");
4401 return false;
4402 });
4403 }
4404
4405 /// See AbstractAttribute::getAsStr().
4406 const std::string getAsStr() const override {
4407 Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
4408 if (isa_and_nonnull<StoreInst>(I))
4409 if (isValidState())
4410 return "assumed-dead-store";
4411 if (isa_and_nonnull<FenceInst>(I))
4412 if (isValidState())
4413 return "assumed-dead-fence";
4414 return AAIsDeadValueImpl::getAsStr();
4415 }
4416
4417 /// See AbstractAttribute::updateImpl(...).
4418 ChangeStatus updateImpl(Attributor &A) override {
4419 Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
4420 if (auto *SI = dyn_cast_or_null<StoreInst>(I)) {
4421 if (!isDeadStore(A, *SI))
4422 return indicatePessimisticFixpoint();
4423 } else if (auto *FI = dyn_cast_or_null<FenceInst>(I)) {
4424 if (!isDeadFence(A, *FI))
4425 return indicatePessimisticFixpoint();
4426 } else {
4427 if (!isAssumedSideEffectFree(A, I))
4428 return indicatePessimisticFixpoint();
4429 if (!areAllUsesAssumedDead(A, getAssociatedValue()))
4430 return indicatePessimisticFixpoint();
4431 }
4433 }
4434
4435 bool isRemovableStore() const override {
4436 return isAssumed(IS_REMOVABLE) && isa<StoreInst>(&getAssociatedValue());
4437 }
4438
4439 /// See AbstractAttribute::manifest(...).
4440 ChangeStatus manifest(Attributor &A) override {
4441 Value &V = getAssociatedValue();
4442 if (auto *I = dyn_cast<Instruction>(&V)) {
4443 // If we get here we basically know the users are all dead. We check if
4444 // isAssumedSideEffectFree returns true here again because it might not be
4445 // the case and only the users are dead but the instruction (=call) is
4446 // still needed.
4447 if (auto *SI = dyn_cast<StoreInst>(I)) {
4448 SmallSetVector<Instruction *, 8> AssumeOnlyInst;
4449 bool IsDead = isDeadStore(A, *SI, &AssumeOnlyInst);
4450 (void)IsDead;
4451 assert(IsDead && "Store was assumed to be dead!");
4452 A.deleteAfterManifest(*I);
4453 for (size_t i = 0; i < AssumeOnlyInst.size(); ++i) {
4454 Instruction *AOI = AssumeOnlyInst[i];
4455 for (auto *Usr : AOI->users())
4456 AssumeOnlyInst.insert(cast<Instruction>(Usr));
4457 A.deleteAfterManifest(*AOI);
4458 }
4459 return ChangeStatus::CHANGED;
4460 }
4461 if (auto *FI = dyn_cast<FenceInst>(I)) {
4462 assert(isDeadFence(A, *FI));
4463 A.deleteAfterManifest(*FI);
4464 return ChangeStatus::CHANGED;
4465 }
4466 if (isAssumedSideEffectFree(A, I) && !isa<InvokeInst>(I)) {
4467 A.deleteAfterManifest(*I);
4468 return ChangeStatus::CHANGED;
4469 }
4470 }
4472 }
4473
4474 /// See AbstractAttribute::trackStatistics()
4475 void trackStatistics() const override {
4477 }
4478
4479private:
4480 // The potential copies of a dead store, used for deletion during manifest.
4481 SmallSetVector<Value *, 4> PotentialCopies;
4482};
4483
4484struct AAIsDeadArgument : public AAIsDeadFloating {
4485 AAIsDeadArgument(const IRPosition &IRP, Attributor &A)
4486 : AAIsDeadFloating(IRP, A) {}
4487
4488 /// See AbstractAttribute::initialize(...).
4489 void initialize(Attributor &A) override {
4490 AAIsDeadFloating::initialize(A);
4491 if (!A.isFunctionIPOAmendable(*getAnchorScope()))
4492 indicatePessimisticFixpoint();
4493 }
4494
4495 /// See AbstractAttribute::manifest(...).
4496 ChangeStatus manifest(Attributor &A) override {
4497 Argument &Arg = *getAssociatedArgument();
4498 if (A.isValidFunctionSignatureRewrite(Arg, /* ReplacementTypes */ {}))
4499 if (A.registerFunctionSignatureRewrite(
4500 Arg, /* ReplacementTypes */ {},
4503 return ChangeStatus::CHANGED;
4504 }
4505 return ChangeStatus::UNCHANGED;
4506 }
4507
4508 /// See AbstractAttribute::trackStatistics()
4509 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(IsDead) }
4510};
4511
4512struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl {
4513 AAIsDeadCallSiteArgument(const IRPosition &IRP, Attributor &A)
4514 : AAIsDeadValueImpl(IRP, A) {}
4515
4516 /// See AbstractAttribute::initialize(...).
4517 void initialize(Attributor &A) override {
4518 AAIsDeadValueImpl::initialize(A);
4519 if (isa<UndefValue>(getAssociatedValue()))
4520 indicatePessimisticFixpoint();
4521 }
4522
4523 /// See AbstractAttribute::updateImpl(...).
4524 ChangeStatus updateImpl(Attributor &A) override {
4525 // TODO: Once we have call site specific value information we can provide
4526 // call site specific liveness information and then it makes
4527 // sense to specialize attributes for call sites arguments instead of
4528 // redirecting requests to the callee argument.
4529 Argument *Arg = getAssociatedArgument();
4530 if (!Arg)
4531 return indicatePessimisticFixpoint();
4532 const IRPosition &ArgPos = IRPosition::argument(*Arg);
4533 auto &ArgAA = A.getAAFor<AAIsDead>(*this, ArgPos, DepClassTy::REQUIRED);
4534 return clampStateAndIndicateChange(getState(), ArgAA.getState());
4535 }
4536
4537 /// See AbstractAttribute::manifest(...).
4538 ChangeStatus manifest(Attributor &A) override {
4539 CallBase &CB = cast<CallBase>(getAnchorValue());
4540 Use &U = CB.getArgOperandUse(getCallSiteArgNo());
4541 assert(!isa<UndefValue>(U.get()) &&
4542 "Expected undef values to be filtered out!");
4543 UndefValue &UV = *UndefValue::get(U->getType());
4544 if (A.changeUseAfterManifest(U, UV))
4545 return ChangeStatus::CHANGED;
4546 return ChangeStatus::UNCHANGED;
4547 }
4548
4549 /// See AbstractAttribute::trackStatistics()
4550 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(IsDead) }
4551};
4552
4553struct AAIsDeadCallSiteReturned : public AAIsDeadFloating {
4554 AAIsDeadCallSiteReturned(const IRPosition &IRP, Attributor &A)
4555 : AAIsDeadFloating(IRP, A) {}
4556
4557 /// See AAIsDead::isAssumedDead().
4558 bool isAssumedDead() const override {
4559 return AAIsDeadFloating::isAssumedDead() && IsAssumedSideEffectFree;
4560 }
4561
4562 /// See AbstractAttribute::initialize(...).
4563 void initialize(Attributor &A) override {
4564 AAIsDeadFloating::initialize(A);
4565 if (isa<UndefValue>(getAssociatedValue())) {
4566 indicatePessimisticFixpoint();
4567 return;
4568 }
4569
4570 // We track this separately as a secondary state.
4571 IsAssumedSideEffectFree = isAssumedSideEffectFree(A, getCtxI());
4572 }
4573
4574 /// See AbstractAttribute::updateImpl(...).
4575 ChangeStatus updateImpl(Attributor &A) override {
4576 ChangeStatus Changed = ChangeStatus::UNCHANGED;
4577 if (IsAssumedSideEffectFree && !isAssumedSideEffectFree(A, getCtxI())) {
4578 IsAssumedSideEffectFree = false;
4579 Changed = ChangeStatus::CHANGED;
4580 }
4581 if (!areAllUsesAssumedDead(A, getAssociatedValue()))
4582 return indicatePessimisticFixpoint();
4583 return Changed;
4584 }
4585
4586 /// See AbstractAttribute::trackStatistics()
4587 void trackStatistics() const override {
4588 if (IsAssumedSideEffectFree)
4590 else
4591 STATS_DECLTRACK_CSRET_ATTR(UnusedResult)
4592 }
4593
4594 /// See AbstractAttribute::getAsStr().
4595 const std::string getAsStr() const override {
4596 return isAssumedDead()
4597 ? "assumed-dead"
4598 : (getAssumed() ? "assumed-dead-users" : "assumed-live");
4599 }
4600
4601private:
4602 bool IsAssumedSideEffectFree = true;
4603};
4604
4605struct AAIsDeadReturned : public AAIsDeadValueImpl {
4606 AAIsDeadReturned(const IRPosition &IRP, Attributor &A)
4607 : AAIsDeadValueImpl(IRP, A) {}
4608
4609 /// See AbstractAttribute::updateImpl(...).
4610 ChangeStatus updateImpl(Attributor &A) override {
4611
4612 bool UsedAssumedInformation = false;
4613 A.checkForAllInstructions([](Instruction &) { return true; }, *this,
4614 {Instruction::Ret}, UsedAssumedInformation);
4615
4616 auto PredForCallSite = [&](AbstractCallSite ACS) {
4617 if (ACS.isCallbackCall() || !ACS.getInstruction())
4618 return false;
4619 return areAllUsesAssumedDead(A, *ACS.getInstruction());
4620 };
4621
4622 if (!A.checkForAllCallSites(PredForCallSite, *this, true,
4623 UsedAssumedInformation))
4624 return indicatePessimisticFixpoint();
4625
4626 return ChangeStatus::UNCHANGED;
4627 }
4628
4629 /// See AbstractAttribute::manifest(...).
4630 ChangeStatus manifest(Attributor &A) override {
4631 // TODO: Rewrite the signature to return void?
4632 bool AnyChange = false;
4633 UndefValue &UV = *UndefValue::get(getAssociatedFunction()->getReturnType());
4634 auto RetInstPred = [&](Instruction &I) {
4635 ReturnInst &RI = cast<ReturnInst>(I);
4636 if (!isa<UndefValue>(RI.getReturnValue()))
4637 AnyChange |= A.changeUseAfterManifest(RI.getOperandUse(0), UV);
4638 return true;
4639 };
4640 bool UsedAssumedInformation = false;
4641 A.checkForAllInstructions(RetInstPred, *this, {Instruction::Ret},
4642 UsedAssumedInformation);
4643 return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
4644 }
4645
4646 /// See AbstractAttribute::trackStatistics()
4647 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(IsDead) }
4648};
4649
4650struct AAIsDeadFunction : public AAIsDead {
4651 AAIsDeadFunction(const IRPosition &IRP, Attributor &A) : AAIsDead(IRP, A) {}
4652
4653 /// See AbstractAttribute::initialize(...).
4654 void initialize(Attributor &A) override {
4655 Function *F = getAnchorScope();
4656 if (!F || F->isDeclaration() || !A.isRunOn(*F)) {
4657 indicatePessimisticFixpoint();
4658 return;
4659 }
4660 if (!isAssumedDeadInternalFunction(A)) {
4661 ToBeExploredFrom.insert(&F->getEntryBlock().front());
4662 assumeLive(A, F->getEntryBlock());
4663 }
4664 }
4665
4666 bool isAssumedDeadInternalFunction(Attributor &A) {
4667 if (!getAnchorScope()->hasLocalLinkage())
4668 return false;
4669 bool UsedAssumedInformation = false;
4670 return A.checkForAllCallSites([](AbstractCallSite) { return false; }, *this,
4671 true, UsedAssumedInformation);
4672 }
4673
4674 /// See AbstractAttribute::getAsStr().
4675 const std::string getAsStr() const override {
4676 return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" +
4677 std::to_string(getAnchorScope()->size()) + "][#TBEP " +
4678 std::to_string(ToBeExploredFrom.size()) + "][#KDE " +
4679 std::to_string(KnownDeadEnds.size()) + "]";
4680 }
4681
4682 /// See AbstractAttribute::manifest(...).
4683 ChangeStatus manifest(Attributor &A) override {
4684 assert(getState().isValidState() &&
4685 "Attempted to manifest an invalid state!");
4686
4687 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
4688 Function &F = *getAnchorScope();
4689
4690 if (AssumedLiveBlocks.empty()) {
4691 A.deleteAfterManifest(F);
4692 return ChangeStatus::CHANGED;
4693 }
4694
4695 // Flag to determine if we can change an invoke to a call assuming the
4696 // callee is nounwind. This is not possible if the personality of the
4697 // function allows to catch asynchronous exceptions.
4698 bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
4699
4700 KnownDeadEnds.set_union(ToBeExploredFrom);
4701 for (const Instruction *DeadEndI : KnownDeadEnds) {
4702 auto *CB = dyn_cast<CallBase>(DeadEndI);
4703 if (!CB)
4704 continue;
4705 const auto &NoReturnAA = A.getAndUpdateAAFor<AANoReturn>(
4706 *this, IRPosition::callsite_function(*CB), DepClassTy::OPTIONAL);
4707 bool MayReturn = !NoReturnAA.isAssumedNoReturn();
4708 if (MayReturn && (!Invoke2CallAllowed || !isa<InvokeInst>(CB)))
4709 continue;
4710
4711 if (auto *II = dyn_cast<InvokeInst>(DeadEndI))
4712 A.registerInvokeWithDeadSuccessor(const_cast<InvokeInst &>(*II));
4713 else
4714 A.changeToUnreachableAfterManifest(
4715 const_cast<Instruction *>(DeadEndI->getNextNode()));
4716 HasChanged = ChangeStatus::CHANGED;
4717 }
4718
4719 STATS_DECL(AAIsDead, BasicBlock, "Number of dead basic blocks deleted.");
4720 for (BasicBlock &BB : F)
4721 if (!AssumedLiveBlocks.count(&BB)) {
4722 A.deleteAfterManifest(BB);
4724 HasChanged = ChangeStatus::CHANGED;
4725 }
4726
4727 return HasChanged;
4728 }
4729
4730 /// See AbstractAttribute::updateImpl(...).
4731 ChangeStatus updateImpl(Attributor &A) override;
4732
4733 bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const override {
4734 assert(From->getParent() == getAnchorScope() &&
4735 To->getParent() == getAnchorScope() &&
4736 "Used AAIsDead of the wrong function");
4737 return isValidState() && !AssumedLiveEdges.count(std::make_pair(From, To));
4738 }
4739
4740 /// See AbstractAttribute::trackStatistics()
4741 void trackStatistics() const override {}
4742
4743 /// Returns true if the function is assumed dead.
4744 bool isAssumedDead() const override { return false; }
4745
4746 /// See AAIsDead::isKnownDead().
4747 bool isKnownDead() const override { return false; }
4748
4749 /// See AAIsDead::isAssumedDead(BasicBlock *).
4750 bool isAssumedDead(const BasicBlock *BB) const override {
4751 assert(BB->getParent() == getAnchorScope() &&
4752 "BB must be in the same anchor scope function.");
4753
4754 if (!getAssumed())
4755 return false;
4756 return !AssumedLiveBlocks.count(BB);
4757 }
4758
4759 /// See AAIsDead::isKnownDead(BasicBlock *).
4760 bool isKnownDead(const BasicBlock *BB) const override {
4761 return getKnown() && isAssumedDead(BB);
4762 }
4763
4764 /// See AAIsDead::isAssumed(Instruction *I).
4765 bool isAssumedDead(const Instruction *I) const override {
4766 assert(I->getParent()->getParent() == getAnchorScope() &&
4767 "Instruction must be in the same anchor scope function.");
4768
4769 if (!getAssumed())
4770 return false;
4771
4772 // If it is not in AssumedLiveBlocks then it for sure dead.
4773 // Otherwise, it can still be after noreturn call in a live block.
4774 if (!AssumedLiveBlocks.count(I->getParent()))
4775 return true;
4776
4777 // If it is not after a liveness barrier it is live.
4778 const Instruction *PrevI = I->getPrevNode();
4779 while (PrevI) {
4780 if (KnownDeadEnds.count(PrevI) || ToBeExploredFrom.count(PrevI))
4781 return true;
4782 PrevI = PrevI->getPrevNode();
4783 }
4784 return false;
4785 }
4786
4787 /// See AAIsDead::isKnownDead(Instruction *I).
4788 bool isKnownDead(const Instruction *I) const override {
4789 return getKnown() && isAssumedDead(I);
4790 }
4791
4792 /// Assume \p BB is (partially) live now and indicate to the Attributor \p A
4793 /// that internal function called from \p BB should now be looked at.
4794 bool assumeLive(Attributor &A, const BasicBlock &BB) {
4795 if (!AssumedLiveBlocks.insert(&BB).second)
4796 return false;
4797
4798 // We assume that all of BB is (probably) live now and if there are calls to
4799 // internal functions we will assume that those are now live as well. This
4800 // is a performance optimization for blocks with calls to a lot of internal
4801 // functions. It can however cause dead functions to be treated as live.
4802 for (const Instruction &I : BB)
4803 if (const auto *CB = dyn_cast<CallBase>(&I))
4804 if (const Function *F = CB->getCalledFunction())
4805 if (F->hasLocalLinkage())
4806 A.markLiveInternalFunction(*F);
4807 return true;
4808 }
4809
4810 /// Collection of instructions that need to be explored again, e.g., we
4811 /// did assume they do not transfer control to (one of their) successors.
4813
4814 /// Collection of instructions that are known to not transfer control.
4816
4817 /// Collection of all assumed live edges
4819
4820 /// Collection of all assumed live BasicBlocks.
4821 DenseSet<const BasicBlock *> AssumedLiveBlocks;
4822};
4823
4824static bool
4825identifyAliveSuccessors(Attributor &A, const CallBase &CB,
4827 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4828 const IRPosition &IPos = IRPosition::callsite_function(CB);
4829
4830 const auto &NoReturnAA =
4831 A.getAndUpdateAAFor<AANoReturn>(AA, IPos, DepClassTy::OPTIONAL);
4832 if (NoReturnAA.isAssumedNoReturn())
4833 return !NoReturnAA.isKnownNoReturn();
4834 if (CB.isTerminator())
4835 AliveSuccessors.push_back(&CB.getSuccessor(0)->front());
4836 else
4837 AliveSuccessors.push_back(CB.getNextNode());
4838 return false;
4839}
4840
4841static bool
4842identifyAliveSuccessors(Attributor &A, const InvokeInst &II,
4844 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4845 bool UsedAssumedInformation =
4846 identifyAliveSuccessors(A, cast<CallBase>(II), AA, AliveSuccessors);
4847
4848 // First, determine if we can change an invoke to a call assuming the
4849 // callee is nounwind. This is not possible if the personality of the
4850 // function allows to catch asynchronous exceptions.
4851 if (AAIsDeadFunction::mayCatchAsynchronousExceptions(*II.getFunction())) {
4852 AliveSuccessors.push_back(&II.getUnwindDest()->front());
4853 } else {
4854 const IRPosition &IPos = IRPosition::callsite_function(II);
4855 const auto &AANoUnw =
4856 A.getAndUpdateAAFor<AANoUnwind>(AA, IPos, DepClassTy::OPTIONAL);
4857 if (AANoUnw.isAssumedNoUnwind()) {
4858 UsedAssumedInformation |= !AANoUnw.isKnownNoUnwind();
4859 } else {
4860 AliveSuccessors.push_back(&II.getUnwindDest()->front());
4861 }
4862 }
4863 return UsedAssumedInformation;
4864}
4865
4866static bool
4867identifyAliveSuccessors(Attributor &A, const BranchInst &BI,
4869 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4870 bool UsedAssumedInformation = false;
4871 if (BI.getNumSuccessors() == 1) {
4872 AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
4873 } else {
4874 std::optional<Constant *> C =
4875 A.getAssumedConstant(*BI.getCondition(), AA, UsedAssumedInformation);
4876 if (!C || isa_and_nonnull<UndefValue>(*C)) {
4877 // No value yet, assume both edges are dead.
4878 } else if (isa_and_nonnull<ConstantInt>(*C)) {
4879 const BasicBlock *SuccBB =
4880 BI.getSuccessor(1 - cast<ConstantInt>(*C)->getValue().getZExtValue());
4881 AliveSuccessors.push_back(&SuccBB->front());
4882 } else {
4883 AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
4884 AliveSuccessors.push_back(&BI.getSuccessor(1)->front());
4885 UsedAssumedInformation = false;
4886 }
4887 }
4888 return UsedAssumedInformation;
4889}
4890
4891static bool
4892identifyAliveSuccessors(Attributor &A, const SwitchInst &SI,
4894 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4895 bool UsedAssumedInformation = false;
4896 std::optional<Constant *> C =
4897 A.getAssumedConstant(*SI.getCondition(), AA, UsedAssumedInformation);
4898 if (!C || isa_and_nonnull<UndefValue>(*C)) {
4899 // No value yet, assume all edges are dead.
4900 } else if (isa_and_nonnull<ConstantInt>(*C)) {
4901 for (const auto &CaseIt : SI.cases()) {
4902 if (CaseIt.getCaseValue() == *C) {
4903 AliveSuccessors.push_back(&CaseIt.getCaseSuccessor()->front());
4904 return UsedAssumedInformation;
4905 }
4906 }
4907 AliveSuccessors.push_back(&SI.getDefaultDest()->front());
4908 return UsedAssumedInformation;
4909 } else {
4910 for (const BasicBlock *SuccBB : successors(SI.getParent()))
4911 AliveSuccessors.push_back(&SuccBB->front());
4912 }
4913 return UsedAssumedInformation;
4914}
4915
4916ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
4918
4919 if (AssumedLiveBlocks.empty()) {
4920 if (isAssumedDeadInternalFunction(A))
4922
4923 Function *F = getAnchorScope();
4924 ToBeExploredFrom.insert(&F->getEntryBlock().front());
4925 assumeLive(A, F->getEntryBlock());
4926 Change = ChangeStatus::CHANGED;
4927 }
4928
4929 LLVM_DEBUG(dbgs() << "[AAIsDead] Live [" << AssumedLiveBlocks.size() << "/"
4930 << getAnchorScope()->size() << "] BBs and "
4931 << ToBeExploredFrom.size() << " exploration points and "
4932 << KnownDeadEnds.size() << " known dead ends\n");
4933
4934 // Copy and clear the list of instructions we need to explore from. It is
4935 // refilled with instructions the next update has to look at.
4936 SmallVector<const Instruction *, 8> Worklist(ToBeExploredFrom.begin(),
4937 ToBeExploredFrom.end());
4938 decltype(ToBeExploredFrom) NewToBeExploredFrom;
4939
4941 while (!Worklist.empty()) {
4942 const Instruction *I = Worklist.pop_back_val();
4943 LLVM_DEBUG(dbgs() << "[AAIsDead] Exploration inst: " << *I << "\n");
4944
4945 // Fast forward for uninteresting instructions. We could look for UB here
4946 // though.
4947 while (!I->isTerminator() && !isa<CallBase>(I))
4948 I = I->getNextNode();
4949
4950 AliveSuccessors.clear();
4951
4952 bool UsedAssumedInformation = false;
4953 switch (I->getOpcode()) {
4954 // TODO: look for (assumed) UB to backwards propagate "deadness".
4955 default:
4956 assert(I->isTerminator() &&
4957 "Expected non-terminators to be handled already!");
4958 for (const BasicBlock *SuccBB : successors(I->getParent()))
4959 AliveSuccessors.push_back(&SuccBB->front());
4960 break;
4961 case Instruction::Call:
4962 UsedAssumedInformation = identifyAliveSuccessors(A, cast<CallInst>(*I),
4963 *this, AliveSuccessors);
4964 break;
4965 case Instruction::Invoke:
4966 UsedAssumedInformation = identifyAliveSuccessors(A, cast<InvokeInst>(*I),
4967 *this, AliveSuccessors);
4968 break;
4969 case Instruction::Br:
4970 UsedAssumedInformation = identifyAliveSuccessors(A, cast<BranchInst>(*I),
4971 *this, AliveSuccessors);