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