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