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