LLVM 20.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 auto UsePred = [&](const Use &U, bool &Follow) -> bool {
1625 Value *CurPtr = U.get();
1626 User *Usr = U.getUser();
1627 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Analyze " << *CurPtr << " in " << *Usr
1628 << "\n");
1629 assert(OffsetInfoMap.count(CurPtr) &&
1630 "The current pointer offset should have been seeded!");
1631
1632 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Usr)) {
1633 if (CE->isCast())
1634 return HandlePassthroughUser(Usr, CurPtr, Follow);
1635 if (!isa<GEPOperator>(CE)) {
1636 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Unhandled constant user " << *CE
1637 << "\n");
1638 return false;
1639 }
1640 }
1641 if (auto *GEP = dyn_cast<GEPOperator>(Usr)) {
1642 // Note the order here, the Usr access might change the map, CurPtr is
1643 // already in it though.
1644 auto &UsrOI = OffsetInfoMap[Usr];
1645 auto &PtrOI = OffsetInfoMap[CurPtr];
1646
1647 if (UsrOI.isUnknown())
1648 return true;
1649
1650 if (PtrOI.isUnknown()) {
1651 Follow = true;
1652 UsrOI.setUnknown();
1653 return true;
1654 }
1655
1656 Follow = collectConstantsForGEP(A, DL, UsrOI, PtrOI, GEP);
1657 return true;
1658 }
1659 if (isa<PtrToIntInst>(Usr))
1660 return false;
1661 if (isa<CastInst>(Usr) || isa<SelectInst>(Usr) || isa<ReturnInst>(Usr))
1662 return HandlePassthroughUser(Usr, CurPtr, Follow);
1663
1664 // For PHIs we need to take care of the recurrence explicitly as the value
1665 // might change while we iterate through a loop. For now, we give up if
1666 // the PHI is not invariant.
1667 if (auto *PHI = dyn_cast<PHINode>(Usr)) {
1668 // Note the order here, the Usr access might change the map, CurPtr is
1669 // already in it though.
1670 bool IsFirstPHIUser = !OffsetInfoMap.count(PHI);
1671 auto &UsrOI = OffsetInfoMap[PHI];
1672 auto &PtrOI = OffsetInfoMap[CurPtr];
1673
1674 // Check if the PHI operand has already an unknown offset as we can't
1675 // improve on that anymore.
1676 if (PtrOI.isUnknown()) {
1677 LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI operand offset unknown "
1678 << *CurPtr << " in " << *PHI << "\n");
1679 Follow = !UsrOI.isUnknown();
1680 UsrOI.setUnknown();
1681 return true;
1682 }
1683
1684 // Check if the PHI is invariant (so far).
1685 if (UsrOI == PtrOI) {
1686 assert(!PtrOI.isUnassigned() &&
1687 "Cannot assign if the current Ptr was not visited!");
1688 LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI is invariant (so far)");
1689 return true;
1690 }
1691
1692 // Check if the PHI operand can be traced back to AssociatedValue.
1693 APInt Offset(
1694 DL.getIndexSizeInBits(CurPtr->getType()->getPointerAddressSpace()),
1695 0);
1696 Value *CurPtrBase = CurPtr->stripAndAccumulateConstantOffsets(
1697 DL, Offset, /* AllowNonInbounds */ true);
1698 auto It = OffsetInfoMap.find(CurPtrBase);
1699 if (It == OffsetInfoMap.end()) {
1700 LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI operand is too complex "
1701 << *CurPtr << " in " << *PHI
1702 << " (base: " << *CurPtrBase << ")\n");
1703 UsrOI.setUnknown();
1704 Follow = true;
1705 return true;
1706 }
1707
1708 // Check if the PHI operand is not dependent on the PHI itself. Every
1709 // recurrence is a cyclic net of PHIs in the data flow, and has an
1710 // equivalent Cycle in the control flow. One of those PHIs must be in the
1711 // header of that control flow Cycle. This is independent of the choice of
1712 // Cycles reported by CycleInfo. It is sufficient to check the PHIs in
1713 // every Cycle header; if such a node is marked unknown, this will
1714 // eventually propagate through the whole net of PHIs in the recurrence.
1715 const auto *CI =
1716 A.getInfoCache().getAnalysisResultForFunction<CycleAnalysis>(
1717 *PHI->getFunction());
1718 if (mayBeInCycle(CI, cast<Instruction>(Usr), /* HeaderOnly */ true)) {
1719 auto BaseOI = It->getSecond();
1720 BaseOI.addToAll(Offset.getZExtValue());
1721 if (IsFirstPHIUser || BaseOI == UsrOI) {
1722 LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI is invariant " << *CurPtr
1723 << " in " << *Usr << "\n");
1724 return HandlePassthroughUser(Usr, CurPtr, Follow);
1725 }
1726
1727 LLVM_DEBUG(
1728 dbgs() << "[AAPointerInfo] PHI operand pointer offset mismatch "
1729 << *CurPtr << " in " << *PHI << "\n");
1730 UsrOI.setUnknown();
1731 Follow = true;
1732 return true;
1733 }
1734
1735 UsrOI.merge(PtrOI);
1736 Follow = true;
1737 return true;
1738 }
1739
1740 if (auto *LoadI = dyn_cast<LoadInst>(Usr)) {
1741 // If the access is to a pointer that may or may not be the associated
1742 // value, e.g. due to a PHI, we cannot assume it will be read.
1743 AccessKind AK = AccessKind::AK_R;
1744 if (getUnderlyingObject(CurPtr) == &AssociatedValue)
1745 AK = AccessKind(AK | AccessKind::AK_MUST);
1746 else
1747 AK = AccessKind(AK | AccessKind::AK_MAY);
1748 if (!handleAccess(A, *LoadI, /* Content */ nullptr, AK,
1749 OffsetInfoMap[CurPtr].Offsets, Changed,
1750 *LoadI->getType()))
1751 return false;
1752
1753 auto IsAssumption = [](Instruction &I) {
1754 if (auto *II = dyn_cast<IntrinsicInst>(&I))
1755 return II->isAssumeLikeIntrinsic();
1756 return false;
1757 };
1758
1759 auto IsImpactedInRange = [&](Instruction *FromI, Instruction *ToI) {
1760 // Check if the assumption and the load are executed together without
1761 // memory modification.
1762 do {
1763 if (FromI->mayWriteToMemory() && !IsAssumption(*FromI))
1764 return true;
1765 FromI = FromI->getNextNonDebugInstruction();
1766 } while (FromI && FromI != ToI);
1767 return false;
1768 };
1769
1770 BasicBlock *BB = LoadI->getParent();
1771 auto IsValidAssume = [&](IntrinsicInst &IntrI) {
1772 if (IntrI.getIntrinsicID() != Intrinsic::assume)
1773 return false;
1774 BasicBlock *IntrBB = IntrI.getParent();
1775 if (IntrI.getParent() == BB) {
1776 if (IsImpactedInRange(LoadI->getNextNonDebugInstruction(), &IntrI))
1777 return false;
1778 } else {
1779 auto PredIt = pred_begin(IntrBB);
1780 if (PredIt == pred_end(IntrBB))
1781 return false;
1782 if ((*PredIt) != BB)
1783 return false;
1784 if (++PredIt != pred_end(IntrBB))
1785 return false;
1786 for (auto *SuccBB : successors(BB)) {
1787 if (SuccBB == IntrBB)
1788 continue;
1789 if (isa<UnreachableInst>(SuccBB->getTerminator()))
1790 continue;
1791 return false;
1792 }
1793 if (IsImpactedInRange(LoadI->getNextNonDebugInstruction(),
1794 BB->getTerminator()))
1795 return false;
1796 if (IsImpactedInRange(&IntrBB->front(), &IntrI))
1797 return false;
1798 }
1799 return true;
1800 };
1801
1802 std::pair<Value *, IntrinsicInst *> Assumption;
1803 for (const Use &LoadU : LoadI->uses()) {
1804 if (auto *CmpI = dyn_cast<CmpInst>(LoadU.getUser())) {
1805 if (!CmpI->isEquality() || !CmpI->isTrueWhenEqual())
1806 continue;
1807 for (const Use &CmpU : CmpI->uses()) {
1808 if (auto *IntrI = dyn_cast<IntrinsicInst>(CmpU.getUser())) {
1809 if (!IsValidAssume(*IntrI))
1810 continue;
1811 int Idx = CmpI->getOperandUse(0) == LoadU;
1812 Assumption = {CmpI->getOperand(Idx), IntrI};
1813 break;
1814 }
1815 }
1816 }
1817 if (Assumption.first)
1818 break;
1819 }
1820
1821 // Check if we found an assumption associated with this load.
1822 if (!Assumption.first || !Assumption.second)
1823 return true;
1824
1825 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Assumption found "
1826 << *Assumption.second << ": " << *LoadI
1827 << " == " << *Assumption.first << "\n");
1828 bool UsedAssumedInformation = false;
1829 std::optional<Value *> Content = nullptr;
1830 if (Assumption.first)
1831 Content =
1832 A.getAssumedSimplified(*Assumption.first, *this,
1833 UsedAssumedInformation, AA::Interprocedural);
1834 return handleAccess(
1835 A, *Assumption.second, Content, AccessKind::AK_ASSUMPTION,
1836 OffsetInfoMap[CurPtr].Offsets, Changed, *LoadI->getType());
1837 }
1838
1839 auto HandleStoreLike = [&](Instruction &I, Value *ValueOp, Type &ValueTy,
1840 ArrayRef<Value *> OtherOps, AccessKind AK) {
1841 for (auto *OtherOp : OtherOps) {
1842 if (OtherOp == CurPtr) {
1843 LLVM_DEBUG(
1844 dbgs()
1845 << "[AAPointerInfo] Escaping use in store like instruction " << I
1846 << "\n");
1847 return false;
1848 }
1849 }
1850
1851 // If the access is to a pointer that may or may not be the associated
1852 // value, e.g. due to a PHI, we cannot assume it will be written.
1853 if (getUnderlyingObject(CurPtr) == &AssociatedValue)
1854 AK = AccessKind(AK | AccessKind::AK_MUST);
1855 else
1856 AK = AccessKind(AK | AccessKind::AK_MAY);
1857 bool UsedAssumedInformation = false;
1858 std::optional<Value *> Content = nullptr;
1859 if (ValueOp)
1860 Content = A.getAssumedSimplified(
1861 *ValueOp, *this, UsedAssumedInformation, AA::Interprocedural);
1862 return handleAccess(A, I, Content, AK, OffsetInfoMap[CurPtr].Offsets,
1863 Changed, ValueTy);
1864 };
1865
1866 if (auto *StoreI = dyn_cast<StoreInst>(Usr))
1867 return HandleStoreLike(*StoreI, StoreI->getValueOperand(),
1868 *StoreI->getValueOperand()->getType(),
1869 {StoreI->getValueOperand()}, AccessKind::AK_W);
1870 if (auto *RMWI = dyn_cast<AtomicRMWInst>(Usr))
1871 return HandleStoreLike(*RMWI, nullptr, *RMWI->getValOperand()->getType(),
1872 {RMWI->getValOperand()}, AccessKind::AK_RW);
1873 if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(Usr))
1874 return HandleStoreLike(
1875 *CXI, nullptr, *CXI->getNewValOperand()->getType(),
1876 {CXI->getCompareOperand(), CXI->getNewValOperand()},
1877 AccessKind::AK_RW);
1878
1879 if (auto *CB = dyn_cast<CallBase>(Usr)) {
1880 if (CB->isLifetimeStartOrEnd())
1881 return true;
1882 const auto *TLI =
1883 A.getInfoCache().getTargetLibraryInfoForFunction(*CB->getFunction());
1884 if (getFreedOperand(CB, TLI) == U)
1885 return true;
1886 if (CB->isArgOperand(&U)) {
1887 unsigned ArgNo = CB->getArgOperandNo(&U);
1888 const auto *CSArgPI = A.getAAFor<AAPointerInfo>(
1889 *this, IRPosition::callsite_argument(*CB, ArgNo),
1891 if (!CSArgPI)
1892 return false;
1893 Changed =
1894 translateAndAddState(A, *CSArgPI, OffsetInfoMap[CurPtr], *CB) |
1895 Changed;
1896 return isValidState();
1897 }
1898 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Call user not handled " << *CB
1899 << "\n");
1900 // TODO: Allow some call uses
1901 return false;
1902 }
1903
1904 LLVM_DEBUG(dbgs() << "[AAPointerInfo] User not handled " << *Usr << "\n");
1905 return false;
1906 };
1907 auto EquivalentUseCB = [&](const Use &OldU, const Use &NewU) {
1908 assert(OffsetInfoMap.count(OldU) && "Old use should be known already!");
1909 if (OffsetInfoMap.count(NewU)) {
1910 LLVM_DEBUG({
1911 if (!(OffsetInfoMap[NewU] == OffsetInfoMap[OldU])) {
1912 dbgs() << "[AAPointerInfo] Equivalent use callback failed: "
1913 << OffsetInfoMap[NewU] << " vs " << OffsetInfoMap[OldU]
1914 << "\n";
1915 }
1916 });
1917 return OffsetInfoMap[NewU] == OffsetInfoMap[OldU];
1918 }
1919 OffsetInfoMap[NewU] = OffsetInfoMap[OldU];
1920 return true;
1921 };
1922 if (!A.checkForAllUses(UsePred, *this, AssociatedValue,
1923 /* CheckBBLivenessOnly */ true, DepClassTy::OPTIONAL,
1924 /* IgnoreDroppableUses */ true, EquivalentUseCB)) {
1925 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Check for all uses failed, abort!\n");
1926 return indicatePessimisticFixpoint();
1927 }
1928
1929 LLVM_DEBUG({
1930 dbgs() << "Accesses by bin after update:\n";
1931 dumpState(dbgs());
1932 });
1933
1934 return Changed;
1935}
1936
1937struct AAPointerInfoReturned final : AAPointerInfoImpl {
1938 AAPointerInfoReturned(const IRPosition &IRP, Attributor &A)
1939 : AAPointerInfoImpl(IRP, A) {}
1940
1941 /// See AbstractAttribute::updateImpl(...).
1942 ChangeStatus updateImpl(Attributor &A) override {
1943 return indicatePessimisticFixpoint();
1944 }
1945
1946 /// See AbstractAttribute::trackStatistics()
1947 void trackStatistics() const override {
1948 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1949 }
1950};
1951
1952struct AAPointerInfoArgument final : AAPointerInfoFloating {
1953 AAPointerInfoArgument(const IRPosition &IRP, Attributor &A)
1954 : AAPointerInfoFloating(IRP, A) {}
1955
1956 /// See AbstractAttribute::trackStatistics()
1957 void trackStatistics() const override {
1958 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1959 }
1960};
1961
1962struct AAPointerInfoCallSiteArgument final : AAPointerInfoFloating {
1963 AAPointerInfoCallSiteArgument(const IRPosition &IRP, Attributor &A)
1964 : AAPointerInfoFloating(IRP, A) {}
1965
1966 /// See AbstractAttribute::updateImpl(...).
1967 ChangeStatus updateImpl(Attributor &A) override {
1968 using namespace AA::PointerInfo;
1969 // We handle memory intrinsics explicitly, at least the first (=
1970 // destination) and second (=source) arguments as we know how they are
1971 // accessed.
1972 if (auto *MI = dyn_cast_or_null<MemIntrinsic>(getCtxI())) {
1973 ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
1974 int64_t LengthVal = AA::RangeTy::Unknown;
1975 if (Length)
1976 LengthVal = Length->getSExtValue();
1977 unsigned ArgNo = getIRPosition().getCallSiteArgNo();
1978 ChangeStatus Changed = ChangeStatus::UNCHANGED;
1979 if (ArgNo > 1) {
1980 LLVM_DEBUG(dbgs() << "[AAPointerInfo] Unhandled memory intrinsic "
1981 << *MI << "\n");
1982 return indicatePessimisticFixpoint();
1983 } else {
1984 auto Kind =
1985 ArgNo == 0 ? AccessKind::AK_MUST_WRITE : AccessKind::AK_MUST_READ;
1986 Changed =
1987 Changed | addAccess(A, {0, LengthVal}, *MI, nullptr, Kind, nullptr);
1988 }
1989 LLVM_DEBUG({
1990 dbgs() << "Accesses by bin after update:\n";
1991 dumpState(dbgs());
1992 });
1993
1994 return Changed;
1995 }
1996
1997 // TODO: Once we have call site specific value information we can provide
1998 // call site specific liveness information and then it makes
1999 // sense to specialize attributes for call sites arguments instead of
2000 // redirecting requests to the callee argument.
2001 Argument *Arg = getAssociatedArgument();
2002 if (Arg) {
2003 const IRPosition &ArgPos = IRPosition::argument(*Arg);
2004 auto *ArgAA =
2005 A.getAAFor<AAPointerInfo>(*this, ArgPos, DepClassTy::REQUIRED);
2006 if (ArgAA && ArgAA->getState().isValidState())
2007 return translateAndAddStateFromCallee(A, *ArgAA,
2008 *cast<CallBase>(getCtxI()));
2009 if (!Arg->getParent()->isDeclaration())
2010 return indicatePessimisticFixpoint();
2011 }
2012
2013 bool IsKnownNoCapture;
2014 if (!AA::hasAssumedIRAttr<Attribute::NoCapture>(
2015 A, this, getIRPosition(), DepClassTy::OPTIONAL, IsKnownNoCapture))
2016 return indicatePessimisticFixpoint();
2017
2018 bool IsKnown = false;
2019 if (AA::isAssumedReadNone(A, getIRPosition(), *this, IsKnown))
2020 return ChangeStatus::UNCHANGED;
2021 bool ReadOnly = AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown);
2022 auto Kind =
2023 ReadOnly ? AccessKind::AK_MAY_READ : AccessKind::AK_MAY_READ_WRITE;
2024 return addAccess(A, AA::RangeTy::getUnknown(), *getCtxI(), nullptr, Kind,
2025 nullptr);
2026 }
2027
2028 /// See AbstractAttribute::trackStatistics()
2029 void trackStatistics() const override {
2030 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
2031 }
2032};
2033
2034struct AAPointerInfoCallSiteReturned final : AAPointerInfoFloating {
2035 AAPointerInfoCallSiteReturned(const IRPosition &IRP, Attributor &A)
2036 : AAPointerInfoFloating(IRP, A) {}
2037
2038 /// See AbstractAttribute::trackStatistics()
2039 void trackStatistics() const override {
2040 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
2041 }
2042};
2043} // namespace
2044
2045/// -----------------------NoUnwind Function Attribute--------------------------
2046
2047namespace {
2048struct AANoUnwindImpl : AANoUnwind {
2049 AANoUnwindImpl(const IRPosition &IRP, Attributor &A) : AANoUnwind(IRP, A) {}
2050
2051 /// See AbstractAttribute::initialize(...).
2052 void initialize(Attributor &A) override {
2053 bool IsKnown;
2054 assert(!AA::hasAssumedIRAttr<Attribute::NoUnwind>(
2055 A, nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
2056 (void)IsKnown;
2057 }
2058
2059 const std::string getAsStr(Attributor *A) const override {
2060 return getAssumed() ? "nounwind" : "may-unwind";
2061 }
2062
2063 /// See AbstractAttribute::updateImpl(...).
2064 ChangeStatus updateImpl(Attributor &A) override {
2065 auto Opcodes = {
2066 (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
2067 (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet,
2068 (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
2069
2070 auto CheckForNoUnwind = [&](Instruction &I) {
2071 if (!I.mayThrow(/* IncludePhaseOneUnwind */ true))
2072 return true;
2073
2074 if (const auto *CB = dyn_cast<CallBase>(&I)) {
2075 bool IsKnownNoUnwind;
2076 return AA::hasAssumedIRAttr<Attribute::NoUnwind>(
2077 A, this, IRPosition::callsite_function(*CB), DepClassTy::REQUIRED,
2078 IsKnownNoUnwind);
2079 }
2080 return false;
2081 };
2082
2083 bool UsedAssumedInformation = false;
2084 if (!A.checkForAllInstructions(CheckForNoUnwind, *this, Opcodes,
2085 UsedAssumedInformation))
2086 return indicatePessimisticFixpoint();
2087
2088 return ChangeStatus::UNCHANGED;
2089 }
2090};
2091
2092struct AANoUnwindFunction final : public AANoUnwindImpl {
2093 AANoUnwindFunction(const IRPosition &IRP, Attributor &A)
2094 : AANoUnwindImpl(IRP, A) {}
2095
2096 /// See AbstractAttribute::trackStatistics()
2097 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nounwind) }
2098};
2099
2100/// NoUnwind attribute deduction for a call sites.
2101struct AANoUnwindCallSite final
2102 : AACalleeToCallSite<AANoUnwind, AANoUnwindImpl> {
2103 AANoUnwindCallSite(const IRPosition &IRP, Attributor &A)
2104 : AACalleeToCallSite<AANoUnwind, AANoUnwindImpl>(IRP, A) {}
2105
2106 /// See AbstractAttribute::trackStatistics()
2107 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nounwind); }
2108};
2109} // namespace
2110
2111/// ------------------------ NoSync Function Attribute -------------------------
2112
2113bool AANoSync::isAlignedBarrier(const CallBase &CB, bool ExecutedAligned) {
2114 switch (CB.getIntrinsicID()) {
2115 case Intrinsic::nvvm_barrier0:
2116 case Intrinsic::nvvm_barrier0_and:
2117 case Intrinsic::nvvm_barrier0_or:
2118 case Intrinsic::nvvm_barrier0_popc:
2119 return true;
2120 case Intrinsic::amdgcn_s_barrier:
2121 if (ExecutedAligned)
2122 return true;
2123 break;
2124 default:
2125 break;
2126 }
2127 return hasAssumption(CB, KnownAssumptionString("ompx_aligned_barrier"));
2128}
2129
2131 if (!I->isAtomic())
2132 return false;
2133
2134 if (auto *FI = dyn_cast<FenceInst>(I))
2135 // All legal orderings for fence are stronger than monotonic.
2136 return FI->getSyncScopeID() != SyncScope::SingleThread;
2137 if (auto *AI = dyn_cast<AtomicCmpXchgInst>(I)) {
2138 // Unordered is not a legal ordering for cmpxchg.
2139 return (AI->getSuccessOrdering() != AtomicOrdering::Monotonic ||
2140 AI->getFailureOrdering() != AtomicOrdering::Monotonic);
2141 }
2142
2143 AtomicOrdering Ordering;
2144 switch (I->getOpcode()) {
2145 case Instruction::AtomicRMW:
2146 Ordering = cast<AtomicRMWInst>(I)->getOrdering();
2147 break;
2148 case Instruction::Store:
2149 Ordering = cast<StoreInst>(I)->getOrdering();
2150 break;
2151 case Instruction::Load:
2152 Ordering = cast<LoadInst>(I)->getOrdering();
2153 break;
2154 default:
2156 "New atomic operations need to be known in the attributor.");
2157 }
2158
2159 return (Ordering != AtomicOrdering::Unordered &&
2160 Ordering != AtomicOrdering::Monotonic);
2161}
2162
2163/// Return true if this intrinsic is nosync. This is only used for intrinsics
2164/// which would be nosync except that they have a volatile flag. All other
2165/// intrinsics are simply annotated with the nosync attribute in Intrinsics.td.
2167 if (auto *MI = dyn_cast<MemIntrinsic>(I))
2168 return !MI->isVolatile();
2169 return false;
2170}
2171
2172namespace {
2173struct AANoSyncImpl : AANoSync {
2174 AANoSyncImpl(const IRPosition &IRP, Attributor &A) : AANoSync(IRP, A) {}
2175
2176 /// See AbstractAttribute::initialize(...).
2177 void initialize(Attributor &A) override {
2178 bool IsKnown;
2179 assert(!AA::hasAssumedIRAttr<Attribute::NoSync>(A, nullptr, getIRPosition(),
2180 DepClassTy::NONE, IsKnown));
2181 (void)IsKnown;
2182 }
2183
2184 const std::string getAsStr(Attributor *A) const override {
2185 return getAssumed() ? "nosync" : "may-sync";
2186 }
2187
2188 /// See AbstractAttribute::updateImpl(...).
2189 ChangeStatus updateImpl(Attributor &A) override;
2190};
2191
2192ChangeStatus AANoSyncImpl::updateImpl(Attributor &A) {
2193
2194 auto CheckRWInstForNoSync = [&](Instruction &I) {
2195 return AA::isNoSyncInst(A, I, *this);
2196 };
2197
2198 auto CheckForNoSync = [&](Instruction &I) {
2199 // At this point we handled all read/write effects and they are all
2200 // nosync, so they can be skipped.
2201 if (I.mayReadOrWriteMemory())
2202 return true;
2203
2204 bool IsKnown;
2205 CallBase &CB = cast<CallBase>(I);
2206 if (AA::hasAssumedIRAttr<Attribute::NoSync>(
2208 IsKnown))
2209 return true;
2210
2211 // non-convergent and readnone imply nosync.
2212 return !CB.isConvergent();
2213 };
2214
2215 bool UsedAssumedInformation = false;
2216 if (!A.checkForAllReadWriteInstructions(CheckRWInstForNoSync, *this,
2217 UsedAssumedInformation) ||
2218 !A.checkForAllCallLikeInstructions(CheckForNoSync, *this,
2219 UsedAssumedInformation))
2220 return indicatePessimisticFixpoint();
2221
2223}
2224
2225struct AANoSyncFunction final : public AANoSyncImpl {
2226 AANoSyncFunction(const IRPosition &IRP, Attributor &A)
2227 : AANoSyncImpl(IRP, A) {}
2228
2229 /// See AbstractAttribute::trackStatistics()
2230 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nosync) }
2231};
2232
2233/// NoSync attribute deduction for a call sites.
2234struct AANoSyncCallSite final : AACalleeToCallSite<AANoSync, AANoSyncImpl> {
2235 AANoSyncCallSite(const IRPosition &IRP, Attributor &A)
2236 : AACalleeToCallSite<AANoSync, AANoSyncImpl>(IRP, A) {}
2237
2238 /// See AbstractAttribute::trackStatistics()
2239 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nosync); }
2240};
2241} // namespace
2242
2243/// ------------------------ No-Free Attributes ----------------------------
2244
2245namespace {
2246struct AANoFreeImpl : public AANoFree {
2247 AANoFreeImpl(const IRPosition &IRP, Attributor &A) : AANoFree(IRP, A) {}
2248
2249 /// See AbstractAttribute::initialize(...).
2250 void initialize(Attributor &A) override {
2251 bool IsKnown;
2252 assert(!AA::hasAssumedIRAttr<Attribute::NoFree>(A, nullptr, getIRPosition(),
2253 DepClassTy::NONE, IsKnown));
2254 (void)IsKnown;
2255 }
2256
2257 /// See AbstractAttribute::updateImpl(...).
2258 ChangeStatus updateImpl(Attributor &A) override {
2259 auto CheckForNoFree = [&](Instruction &I) {
2260 bool IsKnown;
2261 return AA::hasAssumedIRAttr<Attribute::NoFree>(
2262 A, this, IRPosition::callsite_function(cast<CallBase>(I)),
2263 DepClassTy::REQUIRED, IsKnown);
2264 };
2265
2266 bool UsedAssumedInformation = false;
2267 if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this,
2268 UsedAssumedInformation))
2269 return indicatePessimisticFixpoint();
2270 return ChangeStatus::UNCHANGED;
2271 }
2272
2273 /// See AbstractAttribute::getAsStr().
2274 const std::string getAsStr(Attributor *A) const override {
2275 return getAssumed() ? "nofree" : "may-free";
2276 }
2277};
2278
2279struct AANoFreeFunction final : public AANoFreeImpl {
2280 AANoFreeFunction(const IRPosition &IRP, Attributor &A)
2281 : AANoFreeImpl(IRP, A) {}
2282
2283 /// See AbstractAttribute::trackStatistics()
2284 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nofree) }
2285};
2286
2287/// NoFree attribute deduction for a call sites.
2288struct AANoFreeCallSite final : AACalleeToCallSite<AANoFree, AANoFreeImpl> {
2289 AANoFreeCallSite(const IRPosition &IRP, Attributor &A)
2290 : AACalleeToCallSite<AANoFree, AANoFreeImpl>(IRP, A) {}
2291
2292 /// See AbstractAttribute::trackStatistics()
2293 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nofree); }
2294};
2295
2296/// NoFree attribute for floating values.
2297struct AANoFreeFloating : AANoFreeImpl {
2298 AANoFreeFloating(const IRPosition &IRP, Attributor &A)
2299 : AANoFreeImpl(IRP, A) {}
2300
2301 /// See AbstractAttribute::trackStatistics()
2302 void trackStatistics() const override{STATS_DECLTRACK_FLOATING_ATTR(nofree)}
2303
2304 /// See Abstract Attribute::updateImpl(...).
2305 ChangeStatus updateImpl(Attributor &A) override {
2306 const IRPosition &IRP = getIRPosition();
2307
2308 bool IsKnown;
2309 if (AA::hasAssumedIRAttr<Attribute::NoFree>(A, this,
2311 DepClassTy::OPTIONAL, IsKnown))
2312 return ChangeStatus::UNCHANGED;
2313
2314 Value &AssociatedValue = getIRPosition().getAssociatedValue();
2315 auto Pred = [&](const Use &U, bool &Follow) -> bool {
2316 Instruction *UserI = cast<Instruction>(U.getUser());
2317 if (auto *CB = dyn_cast<CallBase>(UserI)) {
2318 if (CB->isBundleOperand(&U))
2319 return false;
2320 if (!CB->isArgOperand(&U))
2321 return true;
2322 unsigned ArgNo = CB->getArgOperandNo(&U);
2323
2324 bool IsKnown;
2325 return AA::hasAssumedIRAttr<Attribute::NoFree>(
2326 A, this, IRPosition::callsite_argument(*CB, ArgNo),
2327 DepClassTy::REQUIRED, IsKnown);
2328 }
2329
2330 if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) ||
2331 isa<PHINode>(UserI) || isa<SelectInst>(UserI)) {
2332 Follow = true;
2333 return true;
2334 }
2335 if (isa<StoreInst>(UserI) || isa<LoadInst>(UserI) ||
2336 isa<ReturnInst>(UserI))
2337 return true;
2338
2339 // Unknown user.
2340 return false;
2341 };
2342 if (!A.checkForAllUses(Pred, *this, AssociatedValue))
2343 return indicatePessimisticFixpoint();
2344
2345 return ChangeStatus::UNCHANGED;
2346 }
2347};
2348
2349/// NoFree attribute for a call site argument.
2350struct AANoFreeArgument final : AANoFreeFloating {
2351 AANoFreeArgument(const IRPosition &IRP, Attributor &A)
2352 : AANoFreeFloating(IRP, A) {}
2353
2354 /// See AbstractAttribute::trackStatistics()
2355 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nofree) }
2356};
2357
2358/// NoFree attribute for call site arguments.
2359struct AANoFreeCallSiteArgument final : AANoFreeFloating {
2360 AANoFreeCallSiteArgument(const IRPosition &IRP, Attributor &A)
2361 : AANoFreeFloating(IRP, A) {}
2362
2363 /// See AbstractAttribute::updateImpl(...).
2364 ChangeStatus updateImpl(Attributor &A) override {
2365 // TODO: Once we have call site specific value information we can provide
2366 // call site specific liveness information and then it makes
2367 // sense to specialize attributes for call sites arguments instead of
2368 // redirecting requests to the callee argument.
2369 Argument *Arg = getAssociatedArgument();
2370 if (!Arg)
2371 return indicatePessimisticFixpoint();
2372 const IRPosition &ArgPos = IRPosition::argument(*Arg);
2373 bool IsKnown;
2374 if (AA::hasAssumedIRAttr<Attribute::NoFree>(A, this, ArgPos,
2375 DepClassTy::REQUIRED, IsKnown))
2376 return ChangeStatus::UNCHANGED;
2377 return indicatePessimisticFixpoint();
2378 }
2379
2380 /// See AbstractAttribute::trackStatistics()
2381 void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nofree)};
2382};
2383
2384/// NoFree attribute for function return value.
2385struct AANoFreeReturned final : AANoFreeFloating {
2386 AANoFreeReturned(const IRPosition &IRP, Attributor &A)
2387 : AANoFreeFloating(IRP, A) {
2388 llvm_unreachable("NoFree is not applicable to function returns!");
2389 }
2390
2391 /// See AbstractAttribute::initialize(...).
2392 void initialize(Attributor &A) override {
2393 llvm_unreachable("NoFree is not applicable to function returns!");
2394 }
2395
2396 /// See AbstractAttribute::updateImpl(...).
2397 ChangeStatus updateImpl(Attributor &A) override {
2398 llvm_unreachable("NoFree is not applicable to function returns!");
2399 }
2400
2401 /// See AbstractAttribute::trackStatistics()
2402 void trackStatistics() const override {}
2403};
2404
2405/// NoFree attribute deduction for a call site return value.
2406struct AANoFreeCallSiteReturned final : AANoFreeFloating {
2407 AANoFreeCallSiteReturned(const IRPosition &IRP, Attributor &A)
2408 : AANoFreeFloating(IRP, A) {}
2409
2410 ChangeStatus manifest(Attributor &A) override {
2411 return ChangeStatus::UNCHANGED;
2412 }
2413 /// See AbstractAttribute::trackStatistics()
2414 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nofree) }
2415};
2416} // namespace
2417
2418/// ------------------------ NonNull Argument Attribute ------------------------
2419
2421 Attribute::AttrKind ImpliedAttributeKind,
2422 bool IgnoreSubsumingPositions) {
2424 AttrKinds.push_back(Attribute::NonNull);
2427 AttrKinds.push_back(Attribute::Dereferenceable);
2428 if (A.hasAttr(IRP, AttrKinds, IgnoreSubsumingPositions, Attribute::NonNull))
2429 return true;
2430
2431 DominatorTree *DT = nullptr;
2432 AssumptionCache *AC = nullptr;
2433 InformationCache &InfoCache = A.getInfoCache();
2434 if (const Function *Fn = IRP.getAnchorScope()) {
2435 if (!Fn->isDeclaration()) {
2438 }
2439 }
2440
2442 if (IRP.getPositionKind() != IRP_RETURNED) {
2443 Worklist.push_back({IRP.getAssociatedValue(), IRP.getCtxI()});
2444 } else {
2445 bool UsedAssumedInformation = false;
2446 if (!A.checkForAllInstructions(
2447 [&](Instruction &I) {
2448 Worklist.push_back({*cast<ReturnInst>(I).getReturnValue(), &I});
2449 return true;
2450 },
2451 IRP.getAssociatedFunction(), nullptr, {Instruction::Ret},
2452 UsedAssumedInformation, false, /*CheckPotentiallyDead=*/true))
2453 return false;
2454 }
2455
2456 if (llvm::any_of(Worklist, [&](AA::ValueAndContext VAC) {
2457 return !isKnownNonZero(
2458 VAC.getValue(),
2459 SimplifyQuery(A.getDataLayout(), DT, AC, VAC.getCtxI()));
2460 }))
2461 return false;
2462
2463 A.manifestAttrs(IRP, {Attribute::get(IRP.getAnchorValue().getContext(),
2464 Attribute::NonNull)});
2465 return true;
2466}
2467
2468namespace {
2469static int64_t getKnownNonNullAndDerefBytesForUse(
2470 Attributor &A, const AbstractAttribute &QueryingAA, Value &AssociatedValue,
2471 const Use *U, const Instruction *I, bool &IsNonNull, bool &TrackUse) {
2472 TrackUse = false;
2473
2474 const Value *UseV = U->get();
2475 if (!UseV->getType()->isPointerTy())
2476 return 0;
2477
2478 // We need to follow common pointer manipulation uses to the accesses they
2479 // feed into. We can try to be smart to avoid looking through things we do not
2480 // like for now, e.g., non-inbounds GEPs.
2481 if (isa<CastInst>(I)) {
2482 TrackUse = true;
2483 return 0;
2484 }
2485
2486 if (isa<GetElementPtrInst>(I)) {
2487 TrackUse = true;
2488 return 0;
2489 }
2490
2491 Type *PtrTy = UseV->getType();
2492 const Function *F = I->getFunction();
2495 const DataLayout &DL = A.getInfoCache().getDL();
2496 if (const auto *CB = dyn_cast<CallBase>(I)) {
2497 if (CB->isBundleOperand(U)) {
2499 U, {Attribute::NonNull, Attribute::Dereferenceable})) {
2500 IsNonNull |=
2501 (RK.AttrKind == Attribute::NonNull || !NullPointerIsDefined);
2502 return RK.ArgValue;
2503 }
2504 return 0;
2505 }
2506
2507 if (CB->isCallee(U)) {
2508 IsNonNull |= !NullPointerIsDefined;
2509 return 0;
2510 }
2511
2512 unsigned ArgNo = CB->getArgOperandNo(U);
2513 IRPosition IRP = IRPosition::callsite_argument(*CB, ArgNo);
2514 // As long as we only use known information there is no need to track
2515 // dependences here.
2516 bool IsKnownNonNull;
2517 AA::hasAssumedIRAttr<Attribute::NonNull>(A, &QueryingAA, IRP,
2518 DepClassTy::NONE, IsKnownNonNull);
2519 IsNonNull |= IsKnownNonNull;
2520 auto *DerefAA =
2521 A.getAAFor<AADereferenceable>(QueryingAA, IRP, DepClassTy::NONE);
2522 return DerefAA ? DerefAA->getKnownDereferenceableBytes() : 0;
2523 }
2524
2525 std::optional<MemoryLocation> Loc = MemoryLocation::getOrNone(I);
2526 if (!Loc || Loc->Ptr != UseV || !Loc->Size.isPrecise() ||
2527 Loc->Size.isScalable() || I->isVolatile())
2528 return 0;
2529
2530 int64_t Offset;
2531 const Value *Base =
2532 getMinimalBaseOfPointer(A, QueryingAA, Loc->Ptr, Offset, DL);
2533 if (Base && Base == &AssociatedValue) {
2534 int64_t DerefBytes = Loc->Size.getValue() + Offset;
2535 IsNonNull |= !NullPointerIsDefined;
2536 return std::max(int64_t(0), DerefBytes);
2537 }
2538
2539 /// Corner case when an offset is 0.
2541 /*AllowNonInbounds*/ true);
2542 if (Base && Base == &AssociatedValue && Offset == 0) {
2543 int64_t DerefBytes = Loc->Size.getValue();
2544 IsNonNull |= !NullPointerIsDefined;
2545 return std::max(int64_t(0), DerefBytes);
2546 }
2547
2548 return 0;
2549}
2550
2551struct AANonNullImpl : AANonNull {
2552 AANonNullImpl(const IRPosition &IRP, Attributor &A) : AANonNull(IRP, A) {}
2553
2554 /// See AbstractAttribute::initialize(...).
2555 void initialize(Attributor &A) override {
2556 Value &V = *getAssociatedValue().stripPointerCasts();
2557 if (isa<ConstantPointerNull>(V)) {
2558 indicatePessimisticFixpoint();
2559 return;
2560 }
2561
2562 if (Instruction *CtxI = getCtxI())
2563 followUsesInMBEC(*this, A, getState(), *CtxI);
2564 }
2565
2566 /// See followUsesInMBEC
2567 bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
2568 AANonNull::StateType &State) {
2569 bool IsNonNull = false;
2570 bool TrackUse = false;
2571 getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I,
2572 IsNonNull, TrackUse);
2573 State.setKnown(IsNonNull);
2574 return TrackUse;
2575 }
2576
2577 /// See AbstractAttribute::getAsStr().
2578 const std::string getAsStr(Attributor *A) const override {
2579 return getAssumed() ? "nonnull" : "may-null";
2580 }
2581};
2582
2583/// NonNull attribute for a floating value.
2584struct AANonNullFloating : public AANonNullImpl {
2585 AANonNullFloating(const IRPosition &IRP, Attributor &A)
2586 : AANonNullImpl(IRP, A) {}
2587
2588 /// See AbstractAttribute::updateImpl(...).
2589 ChangeStatus updateImpl(Attributor &A) override {
2590 auto CheckIRP = [&](const IRPosition &IRP) {
2591 bool IsKnownNonNull;
2592 return AA::hasAssumedIRAttr<Attribute::NonNull>(
2593 A, *this, IRP, DepClassTy::OPTIONAL, IsKnownNonNull);
2594 };
2595
2596 bool Stripped;
2597 bool UsedAssumedInformation = false;
2598 Value *AssociatedValue = &getAssociatedValue();
2600 if (!A.getAssumedSimplifiedValues(getIRPosition(), *this, Values,
2601 AA::AnyScope, UsedAssumedInformation))
2602 Stripped = false;
2603 else
2604 Stripped =
2605 Values.size() != 1 || Values.front().getValue() != AssociatedValue;
2606
2607 if (!Stripped) {
2608 bool IsKnown;
2609 if (auto *PHI = dyn_cast<PHINode>(AssociatedValue))
2610 if (llvm::all_of(PHI->incoming_values(), [&](Value *Op) {
2611 return AA::hasAssumedIRAttr<Attribute::NonNull>(
2612 A, this, IRPosition::value(*Op), DepClassTy::OPTIONAL,
2613 IsKnown);
2614 }))
2615 return ChangeStatus::UNCHANGED;
2616 if (auto *Select = dyn_cast<SelectInst>(AssociatedValue))
2617 if (AA::hasAssumedIRAttr<Attribute::NonNull>(
2618 A, this, IRPosition::value(*Select->getFalseValue()),
2619 DepClassTy::OPTIONAL, IsKnown) &&
2620 AA::hasAssumedIRAttr<Attribute::NonNull>(
2621 A, this, IRPosition::value(*Select->getTrueValue()),
2622 DepClassTy::OPTIONAL, IsKnown))
2623 return ChangeStatus::UNCHANGED;
2624
2625 // If we haven't stripped anything we might still be able to use a
2626 // different AA, but only if the IRP changes. Effectively when we
2627 // interpret this not as a call site value but as a floating/argument
2628 // value.
2629 const IRPosition AVIRP = IRPosition::value(*AssociatedValue);
2630 if (AVIRP == getIRPosition() || !CheckIRP(AVIRP))
2631 return indicatePessimisticFixpoint();
2632 return ChangeStatus::UNCHANGED;
2633 }
2634
2635 for (const auto &VAC : Values)
2636 if (!CheckIRP(IRPosition::value(*VAC.getValue())))
2637 return indicatePessimisticFixpoint();
2638
2639 return ChangeStatus::UNCHANGED;
2640 }
2641
2642 /// See AbstractAttribute::trackStatistics()
2643 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
2644};
2645
2646/// NonNull attribute for function return value.
2647struct AANonNullReturned final
2648 : AAReturnedFromReturnedValues<AANonNull, AANonNull, AANonNull::StateType,
2649 false, AANonNull::IRAttributeKind, false> {
2650 AANonNullReturned(const IRPosition &IRP, Attributor &A)
2651 : AAReturnedFromReturnedValues<AANonNull, AANonNull, AANonNull::StateType,
2652 false, Attribute::NonNull, false>(IRP, A) {
2653 }
2654
2655 /// See AbstractAttribute::getAsStr().
2656 const std::string getAsStr(Attributor *A) const override {
2657 return getAssumed() ? "nonnull" : "may-null";
2658 }
2659
2660 /// See AbstractAttribute::trackStatistics()
2661 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
2662};
2663
2664/// NonNull attribute for function argument.
2665struct AANonNullArgument final
2666 : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl> {
2667 AANonNullArgument(const IRPosition &IRP, Attributor &A)
2668 : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl>(IRP, A) {}
2669
2670 /// See AbstractAttribute::trackStatistics()
2671 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nonnull) }
2672};
2673
2674struct AANonNullCallSiteArgument final : AANonNullFloating {
2675 AANonNullCallSiteArgument(const IRPosition &IRP, Attributor &A)
2676 : AANonNullFloating(IRP, A) {}
2677
2678 /// See AbstractAttribute::trackStatistics()
2679 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(nonnull) }
2680};
2681
2682/// NonNull attribute for a call site return position.
2683struct AANonNullCallSiteReturned final
2684 : AACalleeToCallSite<AANonNull, AANonNullImpl> {
2685 AANonNullCallSiteReturned(const IRPosition &IRP, Attributor &A)
2686 : AACalleeToCallSite<AANonNull, AANonNullImpl>(IRP, A) {}
2687
2688 /// See AbstractAttribute::trackStatistics()
2689 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) }
2690};
2691} // namespace
2692
2693/// ------------------------ Must-Progress Attributes --------------------------
2694namespace {
2695struct AAMustProgressImpl : public AAMustProgress {
2696 AAMustProgressImpl(const IRPosition &IRP, Attributor &A)
2697 : AAMustProgress(IRP, A) {}
2698
2699 /// See AbstractAttribute::initialize(...).
2700 void initialize(Attributor &A) override {
2701 bool IsKnown;
2702 assert(!AA::hasAssumedIRAttr<Attribute::MustProgress>(
2703 A, nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
2704 (void)IsKnown;
2705 }
2706
2707 /// See AbstractAttribute::getAsStr()
2708 const std::string getAsStr(Attributor *A) const override {
2709 return getAssumed() ? "mustprogress" : "may-not-progress";
2710 }
2711};
2712
2713struct AAMustProgressFunction final : AAMustProgressImpl {
2714 AAMustProgressFunction(const IRPosition &IRP, Attributor &A)
2715 : AAMustProgressImpl(IRP, A) {}
2716
2717 /// See AbstractAttribute::updateImpl(...).
2718 ChangeStatus updateImpl(Attributor &A) override {
2719 bool IsKnown;
2720 if (AA::hasAssumedIRAttr<Attribute::WillReturn>(
2721 A, this, getIRPosition(), DepClassTy::OPTIONAL, IsKnown)) {
2722 if (IsKnown)
2723 return indicateOptimisticFixpoint();
2724 return ChangeStatus::UNCHANGED;
2725 }
2726
2727 auto CheckForMustProgress = [&](AbstractCallSite ACS) {
2728 IRPosition IPos = IRPosition::callsite_function(*ACS.getInstruction());
2729 bool IsKnownMustProgress;
2730 return AA::hasAssumedIRAttr<Attribute::MustProgress>(
2731 A, this, IPos, DepClassTy::REQUIRED, IsKnownMustProgress,
2732 /* IgnoreSubsumingPositions */ true);
2733 };
2734
2735 bool AllCallSitesKnown = true;
2736 if (!A.checkForAllCallSites(CheckForMustProgress, *this,
2737 /* RequireAllCallSites */ true,
2738 AllCallSitesKnown))
2739 return indicatePessimisticFixpoint();
2740
2741 return ChangeStatus::UNCHANGED;
2742 }
2743
2744 /// See AbstractAttribute::trackStatistics()
2745 void trackStatistics() const override {
2746 STATS_DECLTRACK_FN_ATTR(mustprogress)
2747 }
2748};
2749
2750/// MustProgress attribute deduction for a call sites.
2751struct AAMustProgressCallSite final : AAMustProgressImpl {
2752 AAMustProgressCallSite(const IRPosition &IRP, Attributor &A)
2753 : AAMustProgressImpl(IRP, A) {}
2754
2755 /// See AbstractAttribute::updateImpl(...).
2756 ChangeStatus updateImpl(Attributor &A) override {
2757 // TODO: Once we have call site specific value information we can provide
2758 // call site specific liveness information and then it makes
2759 // sense to specialize attributes for call sites arguments instead of
2760 // redirecting requests to the callee argument.
2761 const IRPosition &FnPos = IRPosition::function(*getAnchorScope());
2762 bool IsKnownMustProgress;
2763 if (!AA::hasAssumedIRAttr<Attribute::MustProgress>(
2764 A, this, FnPos, DepClassTy::REQUIRED, IsKnownMustProgress))
2765 return indicatePessimisticFixpoint();
2766 return ChangeStatus::UNCHANGED;
2767 }
2768
2769 /// See AbstractAttribute::trackStatistics()
2770 void trackStatistics() const override {
2771 STATS_DECLTRACK_CS_ATTR(mustprogress);
2772 }
2773};
2774} // namespace
2775
2776/// ------------------------ No-Recurse Attributes ----------------------------
2777
2778namespace {
2779struct AANoRecurseImpl : public AANoRecurse {
2780 AANoRecurseImpl(const IRPosition &IRP, Attributor &A) : AANoRecurse(IRP, A) {}
2781
2782 /// See AbstractAttribute::initialize(...).
2783 void initialize(Attributor &A) override {
2784 bool IsKnown;
2785 assert(!AA::hasAssumedIRAttr<Attribute::NoRecurse>(
2786 A, nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
2787 (void)IsKnown;
2788 }
2789
2790 /// See AbstractAttribute::getAsStr()
2791 const std::string getAsStr(Attributor *A) const override {
2792 return getAssumed() ? "norecurse" : "may-recurse";
2793 }
2794};
2795
2796struct AANoRecurseFunction final : AANoRecurseImpl {
2797 AANoRecurseFunction(const IRPosition &IRP, Attributor &A)
2798 : AANoRecurseImpl(IRP, A) {}
2799
2800 /// See AbstractAttribute::updateImpl(...).
2801 ChangeStatus updateImpl(Attributor &A) override {
2802
2803 // If all live call sites are known to be no-recurse, we are as well.
2804 auto CallSitePred = [&](AbstractCallSite ACS) {
2805 bool IsKnownNoRecurse;
2806 if (!AA::hasAssumedIRAttr<Attribute::NoRecurse>(
2807 A, this,
2808 IRPosition::function(*ACS.getInstruction()->getFunction()),
2809 DepClassTy::NONE, IsKnownNoRecurse))
2810 return false;
2811 return IsKnownNoRecurse;
2812 };
2813 bool UsedAssumedInformation = false;
2814 if (A.checkForAllCallSites(CallSitePred, *this, true,
2815 UsedAssumedInformation)) {
2816 // If we know all call sites and all are known no-recurse, we are done.
2817 // If all known call sites, which might not be all that exist, are known
2818 // to be no-recurse, we are not done but we can continue to assume
2819 // no-recurse. If one of the call sites we have not visited will become
2820 // live, another update is triggered.
2821 if (!UsedAssumedInformation)
2822 indicateOptimisticFixpoint();
2823 return ChangeStatus::UNCHANGED;
2824 }
2825
2826 const AAInterFnReachability *EdgeReachability =
2827 A.getAAFor<AAInterFnReachability>(*this, getIRPosition(),
2828 DepClassTy::REQUIRED);
2829 if (EdgeReachability && EdgeReachability->canReach(A, *getAnchorScope()))
2830 return indicatePessimisticFixpoint();
2831 return ChangeStatus::UNCHANGED;
2832 }
2833
2834 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) }
2835};
2836
2837/// NoRecurse attribute deduction for a call sites.
2838struct AANoRecurseCallSite final
2839 : AACalleeToCallSite<AANoRecurse, AANoRecurseImpl> {
2840 AANoRecurseCallSite(const IRPosition &IRP, Attributor &A)
2841 : AACalleeToCallSite<AANoRecurse, AANoRecurseImpl>(IRP, A) {}
2842
2843 /// See AbstractAttribute::trackStatistics()
2844 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(norecurse); }
2845};
2846} // namespace
2847
2848/// ------------------------ No-Convergent Attribute --------------------------
2849
2850namespace {
2851struct AANonConvergentImpl : public AANonConvergent {
2852 AANonConvergentImpl(const IRPosition &IRP, Attributor &A)
2853 : AANonConvergent(IRP, A) {}
2854
2855 /// See AbstractAttribute::getAsStr()
2856 const std::string getAsStr(Attributor *A) const override {
2857 return getAssumed() ? "non-convergent" : "may-be-convergent";
2858 }
2859};
2860
2861struct AANonConvergentFunction final : AANonConvergentImpl {
2862 AANonConvergentFunction(const IRPosition &IRP, Attributor &A)
2863 : AANonConvergentImpl(IRP, A) {}
2864
2865 /// See AbstractAttribute::updateImpl(...).
2866 ChangeStatus updateImpl(Attributor &A) override {
2867 // If all function calls are known to not be convergent, we are not
2868 // convergent.
2869 auto CalleeIsNotConvergent = [&](Instruction &Inst) {
2870 CallBase &CB = cast<CallBase>(Inst);
2871 auto *Callee = dyn_cast_if_present<Function>(CB.getCalledOperand());
2872 if (!Callee || Callee->isIntrinsic()) {
2873 return false;
2874 }
2875 if (Callee->isDeclaration()) {
2876 return !Callee->hasFnAttribute(Attribute::Convergent);
2877 }
2878 const auto *ConvergentAA = A.getAAFor<AANonConvergent>(
2879 *this, IRPosition::function(*Callee), DepClassTy::REQUIRED);
2880 return ConvergentAA && ConvergentAA->isAssumedNotConvergent();
2881 };
2882
2883 bool UsedAssumedInformation = false;
2884 if (!A.checkForAllCallLikeInstructions(CalleeIsNotConvergent, *this,
2885 UsedAssumedInformation)) {
2886 return indicatePessimisticFixpoint();
2887 }
2888 return ChangeStatus::UNCHANGED;
2889 }
2890
2891 ChangeStatus manifest(Attributor &A) override {
2892 if (isKnownNotConvergent() &&
2893 A.hasAttr(getIRPosition(), Attribute::Convergent)) {
2894 A.removeAttrs(getIRPosition(), {Attribute::Convergent});
2895 return ChangeStatus::CHANGED;
2896 }
2897 return ChangeStatus::UNCHANGED;
2898 }
2899
2900 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(convergent) }
2901};
2902} // namespace
2903
2904/// -------------------- Undefined-Behavior Attributes ------------------------
2905
2906namespace {
2907struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior {
2908 AAUndefinedBehaviorImpl(const IRPosition &IRP, Attributor &A)
2909 : AAUndefinedBehavior(IRP, A) {}
2910
2911 /// See AbstractAttribute::updateImpl(...).
2912 // through a pointer (i.e. also branches etc.)
2913 ChangeStatus updateImpl(Attributor &A) override {
2914 const size_t UBPrevSize = KnownUBInsts.size();
2915 const size_t NoUBPrevSize = AssumedNoUBInsts.size();
2916
2917 auto InspectMemAccessInstForUB = [&](Instruction &I) {
2918 // Lang ref now states volatile store is not UB, let's skip them.
2919 if (I.isVolatile() && I.mayWriteToMemory())
2920 return true;
2921
2922 // Skip instructions that are already saved.
2923 if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
2924 return true;
2925
2926 // If we reach here, we know we have an instruction
2927 // that accesses memory through a pointer operand,
2928 // for which getPointerOperand() should give it to us.
2929 Value *PtrOp =
2930 const_cast<Value *>(getPointerOperand(&I, /* AllowVolatile */ true));
2931 assert(PtrOp &&
2932 "Expected pointer operand of memory accessing instruction");
2933
2934 // Either we stopped and the appropriate action was taken,
2935 // or we got back a simplified value to continue.
2936 std::optional<Value *> SimplifiedPtrOp =
2937 stopOnUndefOrAssumed(A, PtrOp, &I);
2938 if (!SimplifiedPtrOp || !*SimplifiedPtrOp)
2939 return true;
2940 const Value *PtrOpVal = *SimplifiedPtrOp;
2941
2942 // A memory access through a pointer is considered UB
2943 // only if the pointer has constant null value.
2944 // TODO: Expand it to not only check constant values.
2945 if (!isa<ConstantPointerNull>(PtrOpVal)) {
2946 AssumedNoUBInsts.insert(&I);
2947 return true;
2948 }
2949 const Type *PtrTy = PtrOpVal->getType();
2950
2951 // Because we only consider instructions inside functions,
2952 // assume that a parent function exists.
2953 const Function *F = I.getFunction();
2954
2955 // A memory access using constant null pointer is only considered UB
2956 // if null pointer is _not_ defined for the target platform.
2958 AssumedNoUBInsts.insert(&I);
2959 else
2960 KnownUBInsts.insert(&I);
2961 return true;
2962 };
2963
2964 auto InspectBrInstForUB = [&](Instruction &I) {
2965 // A conditional branch instruction is considered UB if it has `undef`
2966 // condition.
2967
2968 // Skip instructions that are already saved.
2969 if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
2970 return true;
2971
2972 // We know we have a branch instruction.
2973 auto *BrInst = cast<BranchInst>(&I);
2974
2975 // Unconditional branches are never considered UB.
2976 if (BrInst->isUnconditional())
2977 return true;
2978
2979 // Either we stopped and the appropriate action was taken,
2980 // or we got back a simplified value to continue.
2981 std::optional<Value *> SimplifiedCond =
2982 stopOnUndefOrAssumed(A, BrInst->getCondition(), BrInst);
2983 if (!SimplifiedCond || !*SimplifiedCond)
2984 return true;
2985 AssumedNoUBInsts.insert(&I);
2986 return true;
2987 };
2988
2989 auto InspectCallSiteForUB = [&](Instruction &I) {
2990 // Check whether a callsite always cause UB or not
2991
2992 // Skip instructions that are already saved.
2993 if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
2994 return true;
2995
2996 // Check nonnull and noundef argument attribute violation for each
2997 // callsite.
2998 CallBase &CB = cast<CallBase>(I);
2999 auto *Callee = dyn_cast_if_present<Function>(CB.getCalledOperand());
3000 if (!Callee)
3001 return true;
3002 for (unsigned idx = 0; idx < CB.arg_size(); idx++) {
3003 // If current argument is known to be simplified to null pointer and the
3004 // corresponding argument position is known to have nonnull attribute,
3005 // the argument is poison. Furthermore, if the argument is poison and
3006 // the position is known to have noundef attriubte, this callsite is
3007 // considered UB.
3008 if (idx >= Callee->arg_size())
3009 break;
3010 Value *ArgVal = CB.getArgOperand(idx);
3011 if (!ArgVal)
3012 continue;
3013 // Here, we handle three cases.
3014 // (1) Not having a value means it is dead. (we can replace the value
3015 // with undef)
3016 // (2) Simplified to undef. The argument violate noundef attriubte.
3017 // (3) Simplified to null pointer where known to be nonnull.
3018 // The argument is a poison value and violate noundef attribute.
3019 IRPosition CalleeArgumentIRP = IRPosition::callsite_argument(CB, idx);
3020 bool IsKnownNoUndef;
3021 AA::hasAssumedIRAttr<Attribute::NoUndef>(
3022 A, this, CalleeArgumentIRP, DepClassTy::NONE, IsKnownNoUndef);
3023 if (!IsKnownNoUndef)
3024 continue;
3025 bool UsedAssumedInformation = false;
3026 std::optional<Value *> SimplifiedVal =
3027 A.getAssumedSimplified(IRPosition::value(*ArgVal), *this,
3028 UsedAssumedInformation, AA::Interprocedural);
3029 if (UsedAssumedInformation)
3030 continue;
3031 if (SimplifiedVal && !*SimplifiedVal)
3032 return true;
3033 if (!SimplifiedVal || isa<UndefValue>(**SimplifiedVal)) {
3034 KnownUBInsts.insert(&I);
3035 continue;
3036 }
3037 if (!ArgVal->getType()->isPointerTy() ||
3038 !isa<ConstantPointerNull>(**SimplifiedVal))
3039 continue;
3040 bool IsKnownNonNull;
3041 AA::hasAssumedIRAttr<Attribute::NonNull>(
3042 A, this, CalleeArgumentIRP, DepClassTy::NONE, IsKnownNonNull);
3043 if (IsKnownNonNull)
3044 KnownUBInsts.insert(&I);
3045 }
3046 return true;
3047 };
3048
3049 auto InspectReturnInstForUB = [&](Instruction &I) {
3050 auto &RI = cast<ReturnInst>(I);
3051 // Either we stopped and the appropriate action was taken,
3052 // or we got back a simplified return value to continue.
3053 std::optional<Value *> SimplifiedRetValue =
3054 stopOnUndefOrAssumed(A, RI.getReturnValue(), &I);
3055 if (!SimplifiedRetValue || !*SimplifiedRetValue)
3056 return true;
3057
3058 // Check if a return instruction always cause UB or not
3059 // Note: It is guaranteed that the returned position of the anchor
3060 // scope has noundef attribute when this is called.
3061 // We also ensure the return position is not "assumed dead"
3062 // because the returned value was then potentially simplified to
3063 // `undef` in AAReturnedValues without removing the `noundef`
3064 // attribute yet.
3065
3066 // When the returned position has noundef attriubte, UB occurs in the
3067 // following cases.
3068 // (1) Returned value is known to be undef.
3069 // (2) The value is known to be a null pointer and the returned
3070 // position has nonnull attribute (because the returned value is
3071 // poison).
3072 if (isa<ConstantPointerNull>(*SimplifiedRetValue)) {
3073 bool IsKnownNonNull;
3074 AA::hasAssumedIRAttr<Attribute::NonNull>(
3075 A, this, IRPosition::returned(*getAnchorScope()), DepClassTy::NONE,
3076 IsKnownNonNull);
3077 if (IsKnownNonNull)
3078 KnownUBInsts.insert(&I);
3079 }
3080
3081 return true;
3082 };
3083
3084 bool UsedAssumedInformation = false;
3085 A.checkForAllInstructions(InspectMemAccessInstForUB, *this,
3086 {Instruction::Load, Instruction::Store,
3087 Instruction::AtomicCmpXchg,
3088 Instruction::AtomicRMW},
3089 UsedAssumedInformation,
3090 /* CheckBBLivenessOnly */ true);
3091 A.checkForAllInstructions(InspectBrInstForUB, *this, {Instruction::Br},
3092 UsedAssumedInformation,
3093 /* CheckBBLivenessOnly */ true);
3094 A.checkForAllCallLikeInstructions(InspectCallSiteForUB, *this,
3095 UsedAssumedInformation);
3096
3097 // If the returned position of the anchor scope has noundef attriubte, check
3098 // all returned instructions.
3099 if (!getAnchorScope()->getReturnType()->isVoidTy()) {
3100 const IRPosition &ReturnIRP = IRPosition::returned(*getAnchorScope());
3101 if (!A.isAssumedDead(ReturnIRP, this, nullptr, UsedAssumedInformation)) {
3102 bool IsKnownNoUndef;
3103 AA::hasAssumedIRAttr<Attribute::NoUndef>(
3104 A, this, ReturnIRP, DepClassTy::NONE, IsKnownNoUndef);
3105 if (IsKnownNoUndef)
3106 A.checkForAllInstructions(InspectReturnInstForUB, *this,
3107 {Instruction::Ret}, UsedAssumedInformation,
3108 /* CheckBBLivenessOnly */ true);
3109 }
3110 }
3111
3112 if (NoUBPrevSize != AssumedNoUBInsts.size() ||
3113 UBPrevSize != KnownUBInsts.size())
3114 return ChangeStatus::CHANGED;
3115 return ChangeStatus::UNCHANGED;
3116 }
3117
3118 bool isKnownToCauseUB(Instruction *I) const override {
3119 return KnownUBInsts.count(I);
3120 }
3121
3122 bool isAssumedToCauseUB(Instruction *I) const override {
3123 // In simple words, if an instruction is not in the assumed to _not_
3124 // cause UB, then it is assumed UB (that includes those
3125 // in the KnownUBInsts set). The rest is boilerplate
3126 // is to ensure that it is one of the instructions we test
3127 // for UB.
3128
3129 switch (I->getOpcode()) {
3130 case Instruction::Load:
3131 case Instruction::Store:
3132 case Instruction::AtomicCmpXchg:
3133 case Instruction::AtomicRMW:
3134 return !AssumedNoUBInsts.count(I);
3135 case Instruction::Br: {
3136 auto *BrInst = cast<BranchInst>(I);
3137 if (BrInst->isUnconditional())
3138 return false;
3139 return !AssumedNoUBInsts.count(I);
3140 } break;
3141 default:
3142 return false;
3143 }
3144 return false;
3145 }
3146
3147 ChangeStatus manifest(Attributor &A) override {
3148 if (KnownUBInsts.empty())
3149 return ChangeStatus::UNCHANGED;
3150 for (Instruction *I : KnownUBInsts)
3151 A.changeToUnreachableAfterManifest(I);
3152 return ChangeStatus::CHANGED;
3153 }
3154
3155 /// See AbstractAttribute::getAsStr()
3156 const std::string getAsStr(Attributor *A) const override {
3157 return getAssumed() ? "undefined-behavior" : "no-ub";
3158 }
3159
3160 /// Note: The correctness of this analysis depends on the fact that the
3161 /// following 2 sets will stop changing after some point.
3162 /// "Change" here means that their size changes.
3163 /// The size of each set is monotonically increasing
3164 /// (we only add items to them) and it is upper bounded by the number of
3165 /// instructions in the processed function (we can never save more
3166 /// elements in either set than this number). Hence, at some point,
3167 /// they will stop increasing.
3168 /// Consequently, at some point, both sets will have stopped
3169 /// changing, effectively making the analysis reach a fixpoint.
3170
3171 /// Note: These 2 sets are disjoint and an instruction can be considered
3172 /// one of 3 things:
3173 /// 1) Known to cause UB (AAUndefinedBehavior could prove it) and put it in
3174 /// the KnownUBInsts set.
3175 /// 2) Assumed to cause UB (in every updateImpl, AAUndefinedBehavior
3176 /// has a reason to assume it).
3177 /// 3) Assumed to not cause UB. very other instruction - AAUndefinedBehavior
3178 /// could not find a reason to assume or prove that it can cause UB,
3179 /// hence it assumes it doesn't. We have a set for these instructions
3180 /// so that we don't reprocess them in every update.
3181 /// Note however that instructions in this set may cause UB.
3182
3183protected:
3184 /// A set of all live instructions _known_ to cause UB.
3185 SmallPtrSet<Instruction *, 8> KnownUBInsts;
3186
3187private:
3188 /// A set of all the (live) instructions that are assumed to _not_ cause UB.
3189 SmallPtrSet<Instruction *, 8> AssumedNoUBInsts;
3190
3191 // Should be called on updates in which if we're processing an instruction
3192 // \p I that depends on a value \p V, one of the following has to happen:
3193 // - If the value is assumed, then stop.
3194 // - If the value is known but undef, then consider it UB.
3195 // - Otherwise, do specific processing with the simplified value.
3196 // We return std::nullopt in the first 2 cases to signify that an appropriate
3197 // action was taken and the caller should stop.
3198 // Otherwise, we return the simplified value that the caller should
3199 // use for specific processing.
3200 std::optional<Value *> stopOnUndefOrAssumed(Attributor &A, Value *V,
3201 Instruction *I) {
3202 bool UsedAssumedInformation = false;
3203 std::optional<Value *> SimplifiedV =
3204 A.getAssumedSimplified(IRPosition::value(*V), *this,
3205 UsedAssumedInformation, AA::Interprocedural);
3206 if (!UsedAssumedInformation) {
3207 // Don't depend on assumed values.
3208 if (!SimplifiedV) {
3209 // If it is known (which we tested above) but it doesn't have a value,
3210 // then we can assume `undef` and hence the instruction is UB.
3211 KnownUBInsts.insert(I);
3212 return std::nullopt;
3213 }
3214 if (!*SimplifiedV)
3215 return nullptr;
3216 V = *SimplifiedV;
3217 }
3218 if (isa<UndefValue>(V)) {
3219 KnownUBInsts.insert(I);
3220 return std::nullopt;
3221 }
3222 return V;
3223 }
3224};
3225
3226struct AAUndefinedBehaviorFunction final : AAUndefinedBehaviorImpl {
3227 AAUndefinedBehaviorFunction(const IRPosition &IRP, Attributor &A)
3228 : AAUndefinedBehaviorImpl(IRP, A) {}
3229
3230 /// See AbstractAttribute::trackStatistics()
3231 void trackStatistics() const override {
3232 STATS_DECL(UndefinedBehaviorInstruction, Instruction,
3233 "Number of instructions known to have UB");
3234 BUILD_STAT_NAME(UndefinedBehaviorInstruction, Instruction) +=
3235 KnownUBInsts.size();
3236 }
3237};
3238} // namespace
3239
3240/// ------------------------ Will-Return Attributes ----------------------------
3241
3242namespace {
3243// Helper function that checks whether a function has any cycle which we don't
3244// know if it is bounded or not.
3245// Loops with maximum trip count are considered bounded, any other cycle not.
3246static bool mayContainUnboundedCycle(Function &F, Attributor &A) {
3247 ScalarEvolution *SE =
3248 A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(F);
3249 LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(F);
3250 // If either SCEV or LoopInfo is not available for the function then we assume
3251 // any cycle to be unbounded cycle.
3252 // We use scc_iterator which uses Tarjan algorithm to find all the maximal
3253 // SCCs.To detect if there's a cycle, we only need to find the maximal ones.
3254 if (!SE || !LI) {
3255 for (scc_iterator<Function *> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI)
3256 if (SCCI.hasCycle())
3257 return true;
3258 return false;
3259 }
3260
3261 // If there's irreducible control, the function may contain non-loop cycles.
3263 return true;
3264
3265 // Any loop that does not have a max trip count is considered unbounded cycle.
3266 for (auto *L : LI->getLoopsInPreorder()) {
3267 if (!SE->getSmallConstantMaxTripCount(L))
3268 return true;
3269 }
3270 return false;
3271}
3272
3273struct AAWillReturnImpl : public AAWillReturn {
3274 AAWillReturnImpl(const IRPosition &IRP, Attributor &A)
3275 : AAWillReturn(IRP, A) {}
3276
3277 /// See AbstractAttribute::initialize(...).
3278 void initialize(Attributor &A) override {
3279 bool IsKnown;
3280 assert(!AA::hasAssumedIRAttr<Attribute::WillReturn>(
3281 A, nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
3282 (void)IsKnown;
3283 }
3284
3285 /// Check for `mustprogress` and `readonly` as they imply `willreturn`.
3286 bool isImpliedByMustprogressAndReadonly(Attributor &A, bool KnownOnly) {
3287 if (!A.hasAttr(getIRPosition(), {Attribute::MustProgress}))
3288 return false;
3289
3290 bool IsKnown;
3291 if (AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown))
3292 return IsKnown || !KnownOnly;
3293 return false;
3294 }
3295
3296 /// See AbstractAttribute::updateImpl(...).
3297 ChangeStatus updateImpl(Attributor &A) override {
3298 if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ false))
3299 return ChangeStatus::UNCHANGED;
3300
3301 auto CheckForWillReturn = [&](Instruction &I) {
3302 IRPosition IPos = IRPosition::callsite_function(cast<CallBase>(I));
3303 bool IsKnown;
3304 if (AA::hasAssumedIRAttr<Attribute::WillReturn>(
3305 A, this, IPos, DepClassTy::REQUIRED, IsKnown)) {
3306 if (IsKnown)
3307 return true;
3308 } else {
3309 return false;
3310 }
3311 bool IsKnownNoRecurse;
3312 return AA::hasAssumedIRAttr<Attribute::NoRecurse>(
3313 A, this, IPos, DepClassTy::REQUIRED, IsKnownNoRecurse);
3314 };
3315
3316 bool UsedAssumedInformation = false;
3317 if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this,
3318 UsedAssumedInformation))
3319 return indicatePessimisticFixpoint();
3320
3321 return ChangeStatus::UNCHANGED;
3322 }
3323
3324 /// See AbstractAttribute::getAsStr()
3325 const std::string getAsStr(Attributor *A) const override {
3326 return getAssumed() ? "willreturn" : "may-noreturn";
3327 }
3328};
3329
3330struct AAWillReturnFunction final : AAWillReturnImpl {
3331 AAWillReturnFunction(const IRPosition &IRP, Attributor &A)
3332 : AAWillReturnImpl(IRP, A) {}
3333
3334 /// See AbstractAttribute::initialize(...).
3335 void initialize(Attributor &A) override {
3336 AAWillReturnImpl::initialize(A);
3337
3338 Function *F = getAnchorScope();
3339 assert(F && "Did expect an anchor function");
3340 if (F->isDeclaration() || mayContainUnboundedCycle(*F, A))
3341 indicatePessimisticFixpoint();
3342 }
3343
3344 /// See AbstractAttribute::trackStatistics()
3345 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(willreturn) }
3346};
3347
3348/// WillReturn attribute deduction for a call sites.
3349struct AAWillReturnCallSite final
3350 : AACalleeToCallSite<AAWillReturn, AAWillReturnImpl> {
3351 AAWillReturnCallSite(const IRPosition &IRP, Attributor &A)
3352 : AACalleeToCallSite<AAWillReturn, AAWillReturnImpl>(IRP, A) {}
3353
3354 /// See AbstractAttribute::updateImpl(...).
3355 ChangeStatus updateImpl(Attributor &A) override {
3356 if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ false))
3357 return ChangeStatus::UNCHANGED;
3358
3359 return AACalleeToCallSite::updateImpl(A);
3360 }
3361
3362 /// See AbstractAttribute::trackStatistics()
3363 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); }
3364};
3365} // namespace
3366
3367/// -------------------AAIntraFnReachability Attribute--------------------------
3368
3369/// All information associated with a reachability query. This boilerplate code
3370/// is used by both AAIntraFnReachability and AAInterFnReachability, with
3371/// different \p ToTy values.
3372template <typename ToTy> struct ReachabilityQueryInfo {
3373 enum class Reachable {
3374 No,
3375 Yes,
3376 };
3377
3378 /// Start here,
3379 const Instruction *From = nullptr;
3380 /// reach this place,
3381 const ToTy *To = nullptr;
3382 /// without going through any of these instructions,
3383 const AA::InstExclusionSetTy *ExclusionSet = nullptr;
3384 /// and remember if it worked:
3385 Reachable Result = Reachable::No;
3386
3387 /// Precomputed hash for this RQI.
3388 unsigned Hash = 0;
3389
3390 unsigned computeHashValue() const {
3391 assert(Hash == 0 && "Computed hash twice!");
3394 return const_cast<ReachabilityQueryInfo<ToTy> *>(this)->Hash =
3395 detail::combineHashValue(PairDMI ::getHashValue({From, To}),
3396 InstSetDMI::getHashValue(ExclusionSet));
3397 }
3398
3400 : From(From), To(To) {}
3401
3402 /// Constructor replacement to ensure unique and stable sets are used for the
3403 /// cache.
3405 const AA::InstExclusionSetTy *ES, bool MakeUnique)
3406 : From(&From), To(&To), ExclusionSet(ES) {
3407
3408 if (!ES || ES->empty()) {
3409 ExclusionSet = nullptr;
3410 } else if (MakeUnique) {
3411 ExclusionSet = A.getInfoCache().getOrCreateUniqueBlockExecutionSet(ES);
3412 }
3413 }
3414
3416 : From(RQI.From), To(RQI.To), ExclusionSet(RQI.ExclusionSet) {}
3417};
3418
3419namespace llvm {
3420template <typename ToTy> struct DenseMapInfo<ReachabilityQueryInfo<ToTy> *> {
3423
3426
3427 static inline ReachabilityQueryInfo<ToTy> *getEmptyKey() { return &EmptyKey; }
3429 return &TombstoneKey;
3430 }
3431 static unsigned getHashValue(const ReachabilityQueryInfo<ToTy> *RQI) {
3432 return RQI->Hash ? RQI->Hash : RQI->computeHashValue();
3433 }
3436 if (!PairDMI::isEqual({LHS->From, LHS->To}, {RHS->From, RHS->To}))
3437 return false;
3438 return InstSetDMI::isEqual(LHS->ExclusionSet, RHS->ExclusionSet);
3439 }
3440};
3441
3442#define DefineKeys(ToTy) \
3443 template <> \
3444 ReachabilityQueryInfo<ToTy> \
3445 DenseMapInfo<ReachabilityQueryInfo<ToTy> *>::EmptyKey = \
3446 ReachabilityQueryInfo<ToTy>( \
3447 DenseMapInfo<const Instruction *>::getEmptyKey(), \
3448 DenseMapInfo<const ToTy *>::getEmptyKey()); \
3449 template <> \
3450 ReachabilityQueryInfo<ToTy> \
3451 DenseMapInfo<ReachabilityQueryInfo<ToTy> *>::TombstoneKey = \
3452 ReachabilityQueryInfo<ToTy>( \
3453 DenseMapInfo<const Instruction *>::getTombstoneKey(), \
3454 DenseMapInfo<const ToTy *>::getTombstoneKey());
3455
3457#undef DefineKeys
3458
3459} // namespace llvm
3460
3461namespace {
3462
3463template <typename BaseTy, typename ToTy>
3464struct CachedReachabilityAA : public BaseTy {
3465 using RQITy = ReachabilityQueryInfo<ToTy>;
3466
3467 CachedReachabilityAA(const IRPosition &IRP, Attributor &A) : BaseTy(IRP, A) {}
3468
3469 /// See AbstractAttribute::isQueryAA.
3470 bool isQueryAA() const override { return true; }
3471
3472 /// See AbstractAttribute::updateImpl(...).
3473 ChangeStatus updateImpl(Attributor &A) override {
3474 ChangeStatus Changed = ChangeStatus::UNCHANGED;
3475 for (unsigned u = 0, e = QueryVector.size(); u < e; ++u) {
3476 RQITy *RQI = QueryVector[u];
3477 if (RQI->Result == RQITy::Reachable::No &&
3478 isReachableImpl(A, *RQI, /*IsTemporaryRQI=*/false))
3479 Changed = ChangeStatus::CHANGED;
3480 }
3481 return Changed;
3482 }
3483
3484 virtual bool isReachableImpl(Attributor &A, RQITy &RQI,
3485 bool IsTemporaryRQI) = 0;
3486
3487 bool rememberResult(Attributor &A, typename RQITy::Reachable Result,
3488 RQITy &RQI, bool UsedExclusionSet, bool IsTemporaryRQI) {
3489 RQI.Result = Result;
3490
3491 // Remove the temporary RQI from the cache.
3492 if (IsTemporaryRQI)
3493 QueryCache.erase(&RQI);
3494
3495 // Insert a plain RQI (w/o exclusion set) if that makes sense. Two options:
3496 // 1) If it is reachable, it doesn't matter if we have an exclusion set for
3497 // this query. 2) We did not use the exclusion set, potentially because
3498 // there is none.
3499 if (Result == RQITy::Reachable::Yes || !UsedExclusionSet) {
3500 RQITy PlainRQI(RQI.From, RQI.To);
3501 if (!QueryCache.count(&PlainRQI)) {
3502 RQITy *RQIPtr = new (A.Allocator) RQITy(RQI.From, RQI.To);
3503 RQIPtr->Result = Result;
3504 QueryVector.push_back(RQIPtr);
3505 QueryCache.insert(RQIPtr);
3506 }
3507 }
3508
3509 // Check if we need to insert a new permanent RQI with the exclusion set.
3510 if (IsTemporaryRQI && Result != RQITy::Reachable::Yes && UsedExclusionSet) {
3511 assert((!RQI.ExclusionSet || !RQI.ExclusionSet->empty()) &&
3512 "Did not expect empty set!");
3513 RQITy *RQIPtr = new (A.Allocator)
3514 RQITy(A, *RQI.From, *RQI.To, RQI.ExclusionSet, true);
3515 assert(RQIPtr->Result == RQITy::Reachable::No && "Already reachable?");
3516 RQIPtr->Result = Result;
3517 assert(!QueryCache.count(RQIPtr));
3518 QueryVector.push_back(RQIPtr);
3519 QueryCache.insert(RQIPtr);
3520 }
3521
3522 if (Result == RQITy::Reachable::No && IsTemporaryRQI)
3523 A.registerForUpdate(*this);
3524 return Result == RQITy::Reachable::Yes;
3525 }
3526
3527 const std::string getAsStr(Attributor *A) const override {
3528 // TODO: Return the number of reachable queries.
3529 return "#queries(" + std::to_string(QueryVector.size()) + ")";
3530 }
3531
3532 bool checkQueryCache(Attributor &A, RQITy &StackRQI,
3533 typename RQITy::Reachable &Result) {
3534 if (!this->getState().isValidState()) {
3535 Result = RQITy::Reachable::Yes;
3536 return true;
3537 }
3538
3539 // If we have an exclusion set we might be able to find our answer by
3540 // ignoring it first.
3541 if (StackRQI.ExclusionSet) {
3542 RQITy PlainRQI(StackRQI.From, StackRQI.To);
3543 auto It = QueryCache.find(&PlainRQI);
3544 if (It != QueryCache.end() && (*It)->Result == RQITy::Reachable::No) {
3545 Result = RQITy::Reachable::No;
3546 return true;
3547 }
3548 }
3549
3550 auto It = QueryCache.find(&StackRQI);
3551 if (It != QueryCache.end()) {
3552 Result = (*It)->Result;
3553 return true;
3554 }
3555
3556 // Insert a temporary for recursive queries. We will replace it with a
3557 // permanent entry later.
3558 QueryCache.insert(&StackRQI);
3559 return false;
3560 }
3561
3562private:
3563 SmallVector<RQITy *> QueryVector;
3564 DenseSet<RQITy *> QueryCache;
3565};
3566
3567struct AAIntraFnReachabilityFunction final
3568 : public CachedReachabilityAA<AAIntraFnReachability, Instruction> {
3569 using Base = CachedReachabilityAA<AAIntraFnReachability, Instruction>;
3570 AAIntraFnReachabilityFunction(const IRPosition &IRP, Attributor &A)
3571 : Base(IRP, A) {
3572 DT = A.getInfoCache().getAnalysisResultForFunction<DominatorTreeAnalysis>(
3573 *IRP.getAssociatedFunction());
3574 }
3575
3576 bool isAssumedReachable(
3577 Attributor &A, const Instruction &From, const Instruction &To,
3578 const AA::InstExclusionSetTy *ExclusionSet) const override {
3579 auto *NonConstThis = const_cast<AAIntraFnReachabilityFunction *>(this);
3580 if (&From == &To)
3581 return true;
3582
3583 RQITy StackRQI(A, From, To, ExclusionSet, false);
3584 typename RQITy::Reachable Result;
3585 if (!NonConstThis->checkQueryCache(A, StackRQI, Result))
3586 return NonConstThis->isReachableImpl(A, StackRQI,
3587 /*IsTemporaryRQI=*/true);
3588 return Result == RQITy::Reachable::Yes;
3589 }
3590
3591 ChangeStatus updateImpl(Attributor &A) override {
3592 // We only depend on liveness. DeadEdges is all we care about, check if any
3593 // of them changed.
3594 auto *LivenessAA =
3595 A.getAAFor<AAIsDead>(*this, getIRPosition(), DepClassTy::OPTIONAL);
3596 if (LivenessAA &&
3597 llvm::all_of(DeadEdges,
3598 [&](const auto &DeadEdge) {
3599 return LivenessAA->isEdgeDead(DeadEdge.first,
3600 DeadEdge.second);
3601 }) &&
3602 llvm::all_of(DeadBlocks, [&](const BasicBlock *BB) {
3603 return LivenessAA->isAssumedDead(BB);
3604 })) {
3605 return ChangeStatus::UNCHANGED;
3606 }
3607 DeadEdges.clear();
3608 DeadBlocks.clear();
3609 return Base::updateImpl(A);
3610 }
3611
3612 bool isReachableImpl(Attributor &A, RQITy &RQI,
3613 bool IsTemporaryRQI) override {
3614 const Instruction *Origin = RQI.From;
3615 bool UsedExclusionSet = false;
3616
3617 auto WillReachInBlock = [&](const Instruction &From, const Instruction &To,
3618 const AA::InstExclusionSetTy *ExclusionSet) {
3619 const Instruction *IP = &From;
3620 while (IP && IP != &To) {
3621 if (ExclusionSet && IP != Origin && ExclusionSet->count(IP)) {
3622 UsedExclusionSet = true;
3623 break;
3624 }
3625 IP = IP->getNextNode();
3626 }
3627 return IP == &To;
3628 };
3629
3630 const BasicBlock *FromBB = RQI.From->getParent();
3631 const BasicBlock *ToBB = RQI.To->getParent();
3632 assert(FromBB->getParent() == ToBB->getParent() &&
3633 "Not an intra-procedural query!");
3634
3635 // Check intra-block reachability, however, other reaching paths are still
3636 // possible.
3637 if (FromBB == ToBB &&
3638 WillReachInBlock(*RQI.From, *RQI.To, RQI.ExclusionSet))
3639 return rememberResult(A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
3640 IsTemporaryRQI);
3641
3642 // Check if reaching the ToBB block is sufficient or if even that would not
3643 // ensure reaching the target. In the latter case we are done.
3644 if (!WillReachInBlock(ToBB->front(), *RQI.To, RQI.ExclusionSet))
3645 return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet,
3646 IsTemporaryRQI);
3647
3648 const Function *Fn = FromBB->getParent();
3650 if (RQI.ExclusionSet)
3651 for (auto *I : *RQI.ExclusionSet)
3652 if (I->getFunction() == Fn)
3653 ExclusionBlocks.insert(I->getParent());
3654
3655 // Check if we make it out of the FromBB block at all.
3656 if (ExclusionBlocks.count(FromBB) &&
3657 !WillReachInBlock(*RQI.From, *FromBB->getTerminator(),
3658 RQI.ExclusionSet))
3659 return rememberResult(A, RQITy::Reachable::No, RQI, true, IsTemporaryRQI);
3660
3661 auto *LivenessAA =
3662 A.getAAFor<AAIsDead>(*this, getIRPosition(), DepClassTy::OPTIONAL);
3663 if (LivenessAA && LivenessAA->isAssumedDead(ToBB)) {
3664 DeadBlocks.insert(ToBB);
3665 return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet,
3666 IsTemporaryRQI);
3667 }
3668
3671 Worklist.push_back(FromBB);
3672
3674 while (!Worklist.empty()) {
3675 const BasicBlock *BB = Worklist.pop_back_val();
3676 if (!Visited.insert(BB).second)
3677 continue;
3678 for (const BasicBlock *SuccBB : successors(BB)) {
3679 if (LivenessAA && LivenessAA->isEdgeDead(BB, SuccBB)) {
3680 LocalDeadEdges.insert({BB, SuccBB});
3681 continue;
3682 }
3683 // We checked before if we just need to reach the ToBB block.
3684 if (SuccBB == ToBB)
3685 return rememberResult(A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
3686 IsTemporaryRQI);
3687 if (DT && ExclusionBlocks.empty() && DT->dominates(BB, ToBB))
3688 return rememberResult(A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
3689 IsTemporaryRQI);
3690
3691 if (ExclusionBlocks.count(SuccBB)) {
3692 UsedExclusionSet = true;
3693 continue;
3694 }
3695 Worklist.push_back(SuccBB);
3696 }
3697 }
3698
3699 DeadEdges.insert(LocalDeadEdges.begin(), LocalDeadEdges.end());
3700 return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet,
3701 IsTemporaryRQI);
3702 }
3703
3704 /// See AbstractAttribute::trackStatistics()
3705 void trackStatistics() const override {}
3706
3707private:
3708 // Set of assumed dead blocks we used in the last query. If any changes we
3709 // update the state.
3711
3712 // Set of assumed dead edges we used in the last query. If any changes we
3713 // update the state.
3715
3716 /// The dominator tree of the function to short-circuit reasoning.
3717 const DominatorTree *DT = nullptr;
3718};
3719} // namespace
3720
3721/// ------------------------ NoAlias Argument Attribute ------------------------
3722
3724 Attribute::AttrKind ImpliedAttributeKind,
3725 bool IgnoreSubsumingPositions) {
3726 assert(ImpliedAttributeKind == Attribute::NoAlias &&
3727 "Unexpected attribute kind");
3728 Value *Val = &IRP.getAssociatedValue();
3729 if (IRP.getPositionKind() != IRP_CALL_SITE_ARGUMENT) {
3730 if (isa<AllocaInst>(Val))
3731 return true;
3732 } else {
3733 IgnoreSubsumingPositions = true;
3734 }
3735
3736 if (isa<UndefValue>(Val))
3737 return true;
3738
3739 if (isa<ConstantPointerNull>(Val) &&
3742 return true;
3743
3744 if (A.hasAttr(IRP, {Attribute::ByVal, Attribute::NoAlias},
3745 IgnoreSubsumingPositions, Attribute::NoAlias))
3746 return true;
3747
3748 return false;
3749}
3750
3751namespace {
3752struct AANoAliasImpl : AANoAlias {
3753 AANoAliasImpl(const IRPosition &IRP, Attributor &A) : AANoAlias(IRP, A) {
3754 assert(getAssociatedType()->isPointerTy() &&
3755 "Noalias is a pointer attribute");
3756 }
3757
3758 const std::string getAsStr(Attributor *A) const override {
3759 return getAssumed() ? "noalias" : "may-alias";
3760 }
3761};
3762
3763/// NoAlias attribute for a floating value.
3764struct AANoAliasFloating final : AANoAliasImpl {
3765 AANoAliasFloating(const IRPosition &IRP, Attributor &A)
3766 : AANoAliasImpl(IRP, A) {}
3767
3768 /// See AbstractAttribute::updateImpl(...).
3769 ChangeStatus updateImpl(Attributor &A) override {
3770 // TODO: Implement this.
3771 return indicatePessimisticFixpoint();
3772 }
3773
3774 /// See AbstractAttribute::trackStatistics()
3775 void trackStatistics() const override {
3777 }
3778};
3779
3780/// NoAlias attribute for an argument.
3781struct AANoAliasArgument final
3782 : AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl> {
3783 using Base = AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl>;
3784 AANoAliasArgument(const IRPosition &IRP, Attributor &A) : Base(IRP, A) {}
3785
3786 /// See AbstractAttribute::update(...).
3787 ChangeStatus updateImpl(Attributor &A) override {
3788 // We have to make sure no-alias on the argument does not break
3789 // synchronization when this is a callback argument, see also [1] below.
3790 // If synchronization cannot be affected, we delegate to the base updateImpl
3791 // function, otherwise we give up for now.
3792
3793 // If the function is no-sync, no-alias cannot break synchronization.
3794 bool IsKnownNoSycn;
3795 if (AA::hasAssumedIRAttr<Attribute::NoSync>(
3796 A, this, IRPosition::function_scope(getIRPosition()),
3797 DepClassTy::OPTIONAL, IsKnownNoSycn))
3798 return Base::updateImpl(A);
3799
3800 // If the argument is read-only, no-alias cannot break synchronization.
3801 bool IsKnown;
3802 if (AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown))
3803 return Base::updateImpl(A);
3804
3805 // If the argument is never passed through callbacks, no-alias cannot break
3806 // synchronization.
3807 bool UsedAssumedInformation = false;
3808 if (A.checkForAllCallSites(
3809 [](AbstractCallSite ACS) { return !ACS.isCallbackCall(); }, *this,
3810 true, UsedAssumedInformation))
3811 return Base::updateImpl(A);
3812
3813 // TODO: add no-alias but make sure it doesn't break synchronization by
3814 // introducing fake uses. See:
3815 // [1] Compiler Optimizations for OpenMP, J. Doerfert and H. Finkel,
3816 // International Workshop on OpenMP 2018,
3817 // http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf
3818
3819 return indicatePessimisticFixpoint();
3820 }
3821
3822 /// See AbstractAttribute::trackStatistics()
3823 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noalias) }
3824};
3825
3826struct AANoAliasCallSiteArgument final : AANoAliasImpl {
3827 AANoAliasCallSiteArgument(const IRPosition &IRP, Attributor &A)
3828 : AANoAliasImpl(IRP, A) {}
3829
3830 /// Determine if the underlying value may alias with the call site argument
3831 /// \p OtherArgNo of \p ICS (= the underlying call site).
3832 bool mayAliasWithArgument(Attributor &A, AAResults *&AAR,
3833 const AAMemoryBehavior &MemBehaviorAA,
3834 const CallBase &CB, unsigned OtherArgNo) {
3835 // We do not need to worry about aliasing with the underlying IRP.
3836 if (this->getCalleeArgNo() == (int)OtherArgNo)
3837 return false;
3838
3839 // If it is not a pointer or pointer vector we do not alias.
3840 const Value *ArgOp = CB.getArgOperand(OtherArgNo);
3841 if (!ArgOp->getType()->isPtrOrPtrVectorTy())
3842 return false;
3843
3844 auto *CBArgMemBehaviorAA = A.getAAFor<AAMemoryBehavior>(
3845 *this, IRPosition::callsite_argument(CB, OtherArgNo), DepClassTy::NONE);
3846
3847 // If the argument is readnone, there is no read-write aliasing.
3848 if (CBArgMemBehaviorAA && CBArgMemBehaviorAA->isAssumedReadNone()) {
3849 A.recordDependence(*CBArgMemBehaviorAA, *this, DepClassTy::OPTIONAL);
3850 return false;
3851 }
3852
3853 // If the argument is readonly and the underlying value is readonly, there
3854 // is no read-write aliasing.
3855 bool IsReadOnly = MemBehaviorAA.isAssumedReadOnly();
3856 if (CBArgMemBehaviorAA && CBArgMemBehaviorAA->isAssumedReadOnly() &&
3857 IsReadOnly) {
3858 A.recordDependence(MemBehaviorAA, *this, DepClassTy::OPTIONAL);
3859 A.recordDependence(*CBArgMemBehaviorAA, *this, DepClassTy::OPTIONAL);
3860 return false;
3861 }
3862
3863 // We have to utilize actual alias analysis queries so we need the object.
3864 if (!AAR)
3865 AAR = A.getInfoCache().getAnalysisResultForFunction<AAManager>(
3866 *getAnchorScope());
3867
3868 // Try to rule it out at the call site.
3869 bool IsAliasing = !AAR || !AAR->isNoAlias(&getAssociatedValue(), ArgOp);
3870 LLVM_DEBUG(dbgs() << "[NoAliasCSArg] Check alias between "
3871 "callsite arguments: "
3872 << getAssociatedValue() << " " << *ArgOp << " => "
3873 << (IsAliasing ? "" : "no-") << "alias \n");
3874
3875 return IsAliasing;
3876 }
3877
3878 bool isKnownNoAliasDueToNoAliasPreservation(
3879 Attributor &A, AAResults *&AAR, const AAMemoryBehavior &MemBehaviorAA) {
3880 // We can deduce "noalias" if the following conditions hold.
3881 // (i) Associated value is assumed to be noalias in the definition.
3882 // (ii) Associated value is assumed to be no-capture in all the uses
3883 // possibly executed before this callsite.
3884 // (iii) There is no other pointer argument which could alias with the
3885 // value.
3886
3887 auto IsDereferenceableOrNull = [&](Value *O, const DataLayout &DL) {
3888 const auto *DerefAA = A.getAAFor<AADereferenceable>(
3889 *this, IRPosition::value(*O), DepClassTy::OPTIONAL);
3890 return DerefAA ? DerefAA->getAssumedDereferenceableBytes() : 0;
3891 };
3892
3893 const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
3894 const Function *ScopeFn = VIRP.getAnchorScope();
3895 // Check whether the value is captured in the scope using AANoCapture.
3896 // Look at CFG and check only uses possibly executed before this
3897 // callsite.
3898 auto UsePred = [&](const Use &U, bool &Follow) -> bool {
3899 Instruction *UserI = cast<Instruction>(U.getUser());
3900
3901 // If UserI is the curr instruction and there is a single potential use of
3902 // the value in UserI we allow the use.
3903 // TODO: We should inspect the operands and allow those that cannot alias
3904 // with the value.
3905 if (UserI == getCtxI() && UserI->getNumOperands() == 1)
3906 return true;
3907
3908 if (ScopeFn) {
3909 if (auto *CB = dyn_cast<CallBase>(UserI)) {
3910 if (CB->isArgOperand(&U)) {
3911
3912 unsigned ArgNo = CB->getArgOperandNo(&U);
3913
3914 bool IsKnownNoCapture;
3915 if (AA::hasAssumedIRAttr<Attribute::NoCapture>(
3916 A, this, IRPosition::callsite_argument(*CB, ArgNo),
3917 DepClassTy::OPTIONAL, IsKnownNoCapture))
3918 return true;
3919 }
3920 }
3921
3923 A, *UserI, *getCtxI(), *this, /* ExclusionSet */ nullptr,
3924 [ScopeFn](const Function &Fn) { return &Fn != ScopeFn; }))
3925 return true;
3926 }
3927
3928 // TODO: We should track the capturing uses in AANoCapture but the problem
3929 // is CGSCC runs. For those we would need to "allow" AANoCapture for
3930 // a value in the module slice.
3931 switch (DetermineUseCaptureKind(U, IsDereferenceableOrNull)) {
3932 case UseCaptureKind::NO_CAPTURE:
3933 return true;
3934 case UseCaptureKind::MAY_CAPTURE:
3935 LLVM_DEBUG(dbgs() << "[AANoAliasCSArg] Unknown user: " << *UserI
3936 << "\n");
3937 return false;
3938 case UseCaptureKind::PASSTHROUGH:
3939 Follow = true;
3940 return true;
3941 }
3942 llvm_unreachable("unknown UseCaptureKind");
3943 };
3944
3945 bool IsKnownNoCapture;
3946 const AANoCapture *NoCaptureAA = nullptr;
3947 bool IsAssumedNoCapture = AA::hasAssumedIRAttr<Attribute::NoCapture>(
3948 A, this, VIRP, DepClassTy::NONE, IsKnownNoCapture, false, &NoCaptureAA);
3949 if (!IsAssumedNoCapture &&
3950 (!NoCaptureAA || !NoCaptureAA->isAssumedNoCaptureMaybeReturned())) {
3951 if (!A.checkForAllUses(UsePred, *this, getAssociatedValue())) {
3952 LLVM_DEBUG(
3953 dbgs() << "[AANoAliasCSArg] " << getAssociatedValue()
3954 << " cannot be noalias as it is potentially captured\n");
3955 return false;
3956 }
3957 }
3958 if (NoCaptureAA)
3959 A.recordDependence(*NoCaptureAA, *this, DepClassTy::OPTIONAL);
3960
3961 // Check there is no other pointer argument which could alias with the
3962 // value passed at this call site.
3963 // TODO: AbstractCallSite
3964 const auto &CB = cast<CallBase>(getAnchorValue());
3965 for (unsigned OtherArgNo = 0; OtherArgNo < CB.arg_size(); OtherArgNo++)
3966 if (mayAliasWithArgument(A, AAR, MemBehaviorAA, CB, OtherArgNo))
3967 return false;
3968
3969 return true;
3970 }
3971
3972 /// See AbstractAttribute::updateImpl(...).
3973 ChangeStatus updateImpl(Attributor &A) override {
3974 // If the argument is readnone we are done as there are no accesses via the
3975 // argument.
3976 auto *MemBehaviorAA =
3977 A.getAAFor<AAMemoryBehavior>(*this, getIRPosition(), DepClassTy::NONE);
3978 if (MemBehaviorAA && MemBehaviorAA->isAssumedReadNone()) {
3979 A.recordDependence(*MemBehaviorAA, *this, DepClassTy::OPTIONAL);
3980 return ChangeStatus::UNCHANGED;
3981 }
3982
3983 bool IsKnownNoAlias;
3984 const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
3985 if (!AA::hasAssumedIRAttr<Attribute::NoAlias>(
3986 A, this, VIRP, DepClassTy::REQUIRED, IsKnownNoAlias)) {
3987 LLVM_DEBUG(dbgs() << "[AANoAlias] " << getAssociatedValue()
3988 << " is not no-alias at the definition\n");
3989 return indicatePessimisticFixpoint();
3990 }
3991
3992 AAResults *AAR = nullptr;
3993 if (MemBehaviorAA &&
3994 isKnownNoAliasDueToNoAliasPreservation(A, AAR, *MemBehaviorAA)) {
3995 LLVM_DEBUG(
3996 dbgs() << "[AANoAlias] No-Alias deduced via no-alias preservation\n");
3997 return ChangeStatus::UNCHANGED;
3998 }
3999
4000 return indicatePessimisticFixpoint();
4001 }
4002
4003 /// See AbstractAttribute::trackStatistics()
4004 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(noalias) }
4005};
4006
4007/// NoAlias attribute for function return value.
4008struct AANoAliasReturned final : AANoAliasImpl {
4009 AANoAliasReturned(const IRPosition &IRP, Attributor &A)
4010 : AANoAliasImpl(IRP, A) {}
4011
4012 /// See AbstractAttribute::updateImpl(...).
4013 ChangeStatus updateImpl(Attributor &A) override {
4014
4015 auto CheckReturnValue = [&](Value &RV) -> bool {
4016 if (Constant *C = dyn_cast<Constant>(&RV))
4017 if (C->isNullValue() || isa<UndefValue>(C))
4018 return true;
4019
4020 /// For now, we can only deduce noalias if we have call sites.
4021 /// FIXME: add more support.
4022 if (!isa<CallBase>(&RV))
4023 return false;
4024
4025 const IRPosition &RVPos = IRPosition::value(RV);
4026 bool IsKnownNoAlias;
4027 if (!AA::hasAssumedIRAttr<Attribute::NoAlias>(
4028 A, this, RVPos, DepClassTy::REQUIRED, IsKnownNoAlias))
4029 return false;
4030
4031 bool IsKnownNoCapture;
4032 const AANoCapture *NoCaptureAA = nullptr;
4033 bool IsAssumedNoCapture = AA::hasAssumedIRAttr<Attribute::NoCapture>(
4034 A, this, RVPos, DepClassTy::REQUIRED, IsKnownNoCapture, false,
4035 &NoCaptureAA);
4036 return IsAssumedNoCapture ||
4037 (NoCaptureAA && NoCaptureAA->isAssumedNoCaptureMaybeReturned());
4038 };
4039
4040 if (!A.checkForAllReturnedValues(CheckReturnValue, *this))
4041 return indicatePessimisticFixpoint();
4042
4043 return ChangeStatus::UNCHANGED;
4044 }
4045
4046 /// See AbstractAttribute::trackStatistics()
4047 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(noalias) }
4048};
4049
4050/// NoAlias attribute deduction for a call site return value.
4051struct AANoAliasCallSiteReturned final
4052 : AACalleeToCallSite<AANoAlias, AANoAliasImpl> {
4053 AANoAliasCallSiteReturned(const IRPosition &IRP, Attributor &A)
4054 : AACalleeToCallSite<AANoAlias, AANoAliasImpl>(IRP, A) {}
4055
4056 /// See AbstractAttribute::trackStatistics()
4057 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noalias); }
4058};
4059} // namespace
4060
4061/// -------------------AAIsDead Function Attribute-----------------------
4062
4063namespace {
4064struct AAIsDeadValueImpl : public AAIsDead {
4065 AAIsDeadValueImpl(const IRPosition &IRP, Attributor &A) : AAIsDead(IRP, A) {}
4066
4067 /// See AAIsDead::isAssumedDead().
4068 bool isAssumedDead() const override { return isAssumed(IS_DEAD); }
4069
4070 /// See AAIsDead::isKnownDead().
4071 bool isKnownDead() const override { return isKnown(IS_DEAD); }
4072
4073 /// See AAIsDead::isAssumedDead(BasicBlock *).
4074 bool isAssumedDead(const BasicBlock *BB) const override { return false; }
4075
4076 /// See AAIsDead::isKnownDead(BasicBlock *).
4077 bool isKnownDead(const BasicBlock *BB) const override { return false; }
4078
4079 /// See AAIsDead::isAssumedDead(Instruction *I).
4080 bool isAssumedDead(const Instruction *I) const override {
4081 return I == getCtxI() && isAssumedDead();
4082 }
4083
4084 /// See AAIsDead::isKnownDead(Instruction *I).
4085 bool isKnownDead(const Instruction *I) const override {
4086 return isAssumedDead(I) && isKnownDead();
4087 }
4088
4089 /// See AbstractAttribute::getAsStr().
4090 const std::string getAsStr(Attributor *A) const override {
4091 return isAssumedDead() ? "assumed-dead" : "assumed-live";
4092 }
4093
4094 /// Check if all uses are assumed dead.
4095 bool areAllUsesAssumedDead(Attributor &A, Value &V) {
4096 // Callers might not check the type, void has no uses.
4097 if (V.getType()->isVoidTy() || V.use_empty())
4098 return true;
4099
4100 // If we replace a value with a constant there are no uses left afterwards.
4101 if (!isa<Constant>(V)) {
4102 if (auto *I = dyn_cast<Instruction>(&V))
4103 if (!A.isRunOn(*I->getFunction()))
4104 return false;
4105 bool UsedAssumedInformation = false;
4106 std::optional<Constant *> C =
4107 A.getAssumedConstant(V, *this, UsedAssumedInformation);
4108 if (!C || *C)
4109 return true;
4110 }
4111
4112 auto UsePred = [&](const Use &U, bool &Follow) { return false; };
4113 // Explicitly set the dependence class to required because we want a long
4114 // chain of N dependent instructions to be considered live as soon as one is
4115 // without going through N update cycles. This is not required for
4116 // correctness.
4117 return A.checkForAllUses(UsePred, *this, V, /* CheckBBLivenessOnly */ false,
4118 DepClassTy::REQUIRED,
4119 /* IgnoreDroppableUses */ false);
4120 }
4121
4122 /// Determine if \p I is assumed to be side-effect free.
4123 bool isAssumedSideEffectFree(Attributor &A, Instruction *I) {
4125 return true;
4126
4127 auto *CB = dyn_cast<CallBase>(I);
4128 if (!CB || isa<IntrinsicInst>(CB))
4129 return false;
4130
4131 const IRPosition &CallIRP = IRPosition::callsite_function(*CB);
4132
4133 bool IsKnownNoUnwind;
4134 if (!AA::hasAssumedIRAttr<Attribute::NoUnwind>(
4135 A, this, CallIRP, DepClassTy::OPTIONAL, IsKnownNoUnwind))
4136 return false;
4137
4138 bool IsKnown;
4139 return AA::isAssumedReadOnly(A, CallIRP, *this, IsKnown);
4140 }
4141};
4142
4143struct AAIsDeadFloating : public AAIsDeadValueImpl {
4144 AAIsDeadFloating(const IRPosition &IRP, Attributor &A)
4145 : AAIsDeadValueImpl(IRP, A) {}
4146
4147 /// See AbstractAttribute::initialize(...).
4148 void initialize(Attributor &A) override {
4149 AAIsDeadValueImpl::initialize(A);
4150
4151 if (isa<UndefValue>(getAssociatedValue())) {
4152 indicatePessimisticFixpoint();
4153 return;
4154 }
4155
4156 Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
4157 if (!isAssumedSideEffectFree(A, I)) {
4158 if (!isa_and_nonnull<StoreInst>(I) && !isa_and_nonnull<FenceInst>(I))
4159 indicatePessimisticFixpoint();
4160 else
4161 removeAssumedBits(HAS_NO_EFFECT);
4162 }
4163 }
4164
4165 bool isDeadFence(Attributor &A, FenceInst &FI) {
4166 const auto *ExecDomainAA = A.lookupAAFor<AAExecutionDomain>(
4167 IRPosition::function(*FI.getFunction()), *this, DepClassTy::NONE);
4168 if (!ExecDomainAA || !ExecDomainAA->isNoOpFence(FI))
4169 return false;
4170 A.recordDependence(*ExecDomainAA, *this, DepClassTy::OPTIONAL);
4171 return true;
4172 }
4173
4174 bool isDeadStore(Attributor &A, StoreInst &SI,
4175 SmallSetVector<Instruction *, 8> *AssumeOnlyInst = nullptr) {
4176 // Lang ref now states volatile store is not UB/dead, let's skip them.
4177 if (SI.isVolatile())
4178 return false;
4179
4180 // If we are collecting assumes to be deleted we are in the manifest stage.
4181 // It's problematic to collect the potential copies again now so we use the
4182 // cached ones.
4183 bool UsedAssumedInformation = false;
4184 if (!AssumeOnlyInst) {
4185 PotentialCopies.clear();
4186 if (!AA::getPotentialCopiesOfStoredValue(A, SI, PotentialCopies, *this,
4187 UsedAssumedInformation)) {
4188 LLVM_DEBUG(
4189 dbgs()
4190 << "[AAIsDead] Could not determine potential copies of store!\n");
4191 return false;
4192 }
4193 }
4194 LLVM_DEBUG(dbgs() << "[AAIsDead] Store has " << PotentialCopies.size()
4195 << " potential copies.\n");
4196
4197 InformationCache &InfoCache = A.getInfoCache();
4198 return llvm::all_of(PotentialCopies, [&](Value *V) {
4199 if (A.isAssumedDead(IRPosition::value(*V), this, nullptr,
4200 UsedAssumedInformation))
4201 return true;
4202 if (auto *LI = dyn_cast<LoadInst>(V)) {
4203 if (llvm::all_of(LI->uses(), [&](const Use &U) {
4204 auto &UserI = cast<Instruction>(*U.getUser());
4205 if (InfoCache.isOnlyUsedByAssume(UserI)) {
4206 if (AssumeOnlyInst)
4207 AssumeOnlyInst->insert(&UserI);
4208 return true;
4209 }
4210 return A.isAssumedDead(U, this, nullptr, UsedAssumedInformation);
4211 })) {
4212 return true;
4213 }
4214 }
4215 LLVM_DEBUG(dbgs() << "[AAIsDead] Potential copy " << *V
4216 << " is assumed live!\n");
4217 return false;
4218 });
4219 }
4220
4221 /// See AbstractAttribute::getAsStr().
4222 const std::string getAsStr(Attributor *A) const override {
4223 Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
4224 if (isa_and_nonnull<StoreInst>(I))
4225 if (isValidState())
4226 return "assumed-dead-store";
4227 if (isa_and_nonnull<FenceInst>(I))
4228 if (isValidState())
4229 return "assumed-dead-fence";
4230 return AAIsDeadValueImpl::getAsStr(A);
4231 }
4232
4233 /// See AbstractAttribute::updateImpl(...).
4234 ChangeStatus updateImpl(Attributor &A) override {
4235 Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
4236 if (auto *SI = dyn_cast_or_null<StoreInst>(I)) {
4237 if (!isDeadStore(A, *SI))
4238 return indicatePessimisticFixpoint();
4239 } else if (auto *FI = dyn_cast_or_null<FenceInst>(I)) {
4240 if (!isDeadFence(A, *FI))
4241 return indicatePessimisticFixpoint();
4242 } else {
4243 if (!isAssumedSideEffectFree(A, I))
4244 return indicatePessimisticFixpoint();
4245 if (!areAllUsesAssumedDead(A, getAssociatedValue()))
4246 return indicatePessimisticFixpoint();
4247 }
4249 }
4250
4251 bool isRemovableStore() const override {
4252 return isAssumed(IS_REMOVABLE) && isa<StoreInst>(&getAssociatedValue());
4253 }
4254
4255 /// See AbstractAttribute::manifest(...).
4256 ChangeStatus manifest(Attributor &A) override {
4257 Value &V = getAssociatedValue();
4258 if (auto *I = dyn_cast<Instruction>(&V)) {
4259 // If we get here we basically know the users are all dead. We check if
4260 // isAssumedSideEffectFree returns true here again because it might not be
4261 // the case and only the users are dead but the instruction (=call) is
4262 // still needed.
4263 if (auto *SI = dyn_cast<StoreInst>(I)) {
4264 SmallSetVector<Instruction *, 8> AssumeOnlyInst;
4265 bool IsDead = isDeadStore(A, *SI, &AssumeOnlyInst);
4266 (void)IsDead;
4267 assert(IsDead && "Store was assumed to be dead!");
4268 A.deleteAfterManifest(*I);
4269 for (size_t i = 0; i < AssumeOnlyInst.size(); ++i) {
4270 Instruction *AOI = AssumeOnlyInst[i];
4271 for (auto *Usr : AOI->users())
4272 AssumeOnlyInst.insert(cast<Instruction>(Usr));
4273 A.deleteAfterManifest(*AOI);
4274 }
4275 return ChangeStatus::CHANGED;
4276 }
4277 if (auto *FI = dyn_cast<FenceInst>(I)) {
4278 assert(isDeadFence(A, *FI));
4279 A.deleteAfterManifest(*FI);
4280 return ChangeStatus::CHANGED;
4281 }
4282 if (isAssumedSideEffectFree(A, I) && !isa<InvokeInst>(I)) {
4283 A.deleteAfterManifest(*I);
4284 return ChangeStatus::CHANGED;
4285 }
4286 }
4288 }
4289
4290 /// See AbstractAttribute::trackStatistics()
4291 void trackStatistics() const override {
4293 }
4294
4295private:
4296 // The potential copies of a dead store, used for deletion during manifest.
4297 SmallSetVector<Value *, 4> PotentialCopies;
4298};
4299
4300struct AAIsDeadArgument : public AAIsDeadFloating {
4301 AAIsDeadArgument(const IRPosition &IRP, Attributor &A)
4302 : AAIsDeadFloating(IRP, A) {}
4303
4304 /// See AbstractAttribute::manifest(...).
4305 ChangeStatus manifest(Attributor &A) override {
4306 Argument &Arg = *getAssociatedArgument();
4307 if (A.isValidFunctionSignatureRewrite(Arg, /* ReplacementTypes */ {}))
4308 if (A.registerFunctionSignatureRewrite(
4309 Arg, /* ReplacementTypes */ {},
4312 return ChangeStatus::CHANGED;
4313 }
4314 return ChangeStatus::UNCHANGED;
4315 }
4316
4317 /// See AbstractAttribute::trackStatistics()
4318 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(IsDead) }
4319};
4320
4321struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl {
4322 AAIsDeadCallSiteArgument(const IRPosition &IRP, Attributor &A)
4323 : AAIsDeadValueImpl(IRP, A) {}
4324
4325 /// See AbstractAttribute::initialize(...).
4326 void initialize(Attributor &A) override {
4327 AAIsDeadValueImpl::initialize(A);
4328 if (isa<UndefValue>(getAssociatedValue()))
4329 indicatePessimisticFixpoint();
4330 }
4331
4332 /// See AbstractAttribute::updateImpl(...).
4333 ChangeStatus updateImpl(Attributor &A) override {
4334 // TODO: Once we have call site specific value information we can provide
4335 // call site specific liveness information and then it makes
4336 // sense to specialize attributes for call sites arguments instead of
4337 // redirecting requests to the callee argument.
4338 Argument *Arg = getAssociatedArgument();
4339 if (!Arg)
4340 return indicatePessimisticFixpoint();
4341 const IRPosition &ArgPos = IRPosition::argument(*Arg);
4342 auto *ArgAA = A.getAAFor<AAIsDead>(*this, ArgPos, DepClassTy::REQUIRED);
4343 if (!ArgAA)
4344 return indicatePessimisticFixpoint();
4345 return clampStateAndIndicateChange(getState(), ArgAA->getState());
4346 }
4347
4348 /// See AbstractAttribute::manifest(...).
4349 ChangeStatus manifest(Attributor &A) override {
4350 CallBase &CB = cast<CallBase>(getAnchorValue());
4351 Use &U = CB.getArgOperandUse(getCallSiteArgNo());
4352 assert(!isa<UndefValue>(U.get()) &&
4353 "Expected undef values to be filtered out!");
4354 UndefValue &UV = *UndefValue::get(U->getType());
4355 if (A.changeUseAfterManifest(U, UV))
4356 return ChangeStatus::CHANGED;
4357 return ChangeStatus::UNCHANGED;
4358 }
4359
4360 /// See AbstractAttribute::trackStatistics()
4361 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(IsDead) }
4362};
4363
4364struct AAIsDeadCallSiteReturned : public AAIsDeadFloating {
4365 AAIsDeadCallSiteReturned(const IRPosition &IRP, Attributor &A)
4366 : AAIsDeadFloating(IRP, A) {}
4367
4368 /// See AAIsDead::isAssumedDead().
4369 bool isAssumedDead() const override {
4370 return AAIsDeadFloating::isAssumedDead() && IsAssumedSideEffectFree;
4371 }
4372
4373 /// See AbstractAttribute::initialize(...).
4374 void initialize(Attributor &A) override {
4375 AAIsDeadFloating::initialize(A);
4376 if (isa<UndefValue>(getAssociatedValue())) {
4377 indicatePessimisticFixpoint();
4378 return;
4379 }
4380
4381 // We track this separately as a secondary state.
4382 IsAssumedSideEffectFree = isAssumedSideEffectFree(A, getCtxI());
4383 }
4384
4385 /// See AbstractAttribute::updateImpl(...).
4386 ChangeStatus updateImpl(Attributor &A) override {
4387 ChangeStatus Changed = ChangeStatus::UNCHANGED;
4388 if (IsAssumedSideEffectFree && !isAssumedSideEffectFree(A, getCtxI())) {
4389 IsAssumedSideEffectFree = false;
4390 Changed = ChangeStatus::CHANGED;
4391 }
4392 if (!areAllUsesAssumedDead(A, getAssociatedValue()))
4393 return indicatePessimisticFixpoint();
4394 return Changed;
4395 }
4396
4397 /// See AbstractAttribute::trackStatistics()
4398 void trackStatistics() const override {
4399 if (IsAssumedSideEffectFree)
4401 else
4402 STATS_DECLTRACK_CSRET_ATTR(UnusedResult)
4403 }
4404
4405 /// See AbstractAttribute::getAsStr().
4406 const std::string getAsStr(Attributor *A) const override {
4407 return isAssumedDead()
4408 ? "assumed-dead"
4409 : (getAssumed() ? "assumed-dead-users" : "assumed-live");
4410 }
4411
4412private:
4413 bool IsAssumedSideEffectFree = true;
4414};
4415
4416struct AAIsDeadReturned : public AAIsDeadValueImpl {
4417 AAIsDeadReturned(const IRPosition &IRP, Attributor &A)
4418 : AAIsDeadValueImpl(IRP, A) {}
4419
4420 /// See AbstractAttribute::updateImpl(...).
4421 ChangeStatus updateImpl(Attributor &A) override {
4422
4423 bool UsedAssumedInformation = false;
4424 A.checkForAllInstructions([](Instruction &) { return true; }, *this,
4425 {Instruction::Ret}, UsedAssumedInformation);
4426
4427 auto PredForCallSite = [&](AbstractCallSite ACS) {
4428 if (ACS.isCallbackCall() || !ACS.getInstruction())
4429 return false;
4430 return areAllUsesAssumedDead(A, *ACS.getInstruction());
4431 };
4432
4433 if (!A.checkForAllCallSites(PredForCallSite, *this, true,
4434 UsedAssumedInformation))
4435 return indicatePessimisticFixpoint();
4436
4437 return ChangeStatus::UNCHANGED;
4438 }
4439
4440 /// See AbstractAttribute::manifest(...).
4441 ChangeStatus manifest(Attributor &A) override {
4442 // TODO: Rewrite the signature to return void?
4443 bool AnyChange = false;
4444 UndefValue &UV = *UndefValue::get(getAssociatedFunction()->getReturnType());
4445 auto RetInstPred = [&](Instruction &I) {
4446 ReturnInst &RI = cast<ReturnInst>(I);
4447 if (!isa<UndefValue>(RI.getReturnValue()))
4448 AnyChange |= A.changeUseAfterManifest(RI.getOperandUse(0), UV);
4449 return true;
4450 };
4451 bool UsedAssumedInformation = false;
4452 A.checkForAllInstructions(RetInstPred, *this, {Instruction::Ret},
4453 UsedAssumedInformation);
4454 return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
4455 }
4456
4457 /// See AbstractAttribute::trackStatistics()
4458 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(IsDead) }
4459};
4460
4461struct AAIsDeadFunction : public AAIsDead {
4462 AAIsDeadFunction(const IRPosition &IRP, Attributor &A) : AAIsDead(IRP, A) {}
4463
4464 /// See AbstractAttribute::initialize(...).
4465 void initialize(Attributor &A) override {
4466 Function *F = getAnchorScope();
4467 assert(F && "Did expect an anchor function");
4468 if (!isAssumedDeadInternalFunction(A)) {
4469 ToBeExploredFrom.insert(&F->getEntryBlock().front());
4470 assumeLive(A, F->getEntryBlock());
4471 }
4472 }
4473
4474 bool isAssumedDeadInternalFunction(Attributor &A) {
4475 if (!getAnchorScope()->hasLocalLinkage())
4476 return false;
4477 bool UsedAssumedInformation = false;
4478 return A.checkForAllCallSites([](AbstractCallSite) { return false; }, *this,
4479 true, UsedAssumedInformation);
4480 }
4481
4482 /// See AbstractAttribute::getAsStr().
4483 const std::string getAsStr(Attributor *A) const override {
4484 return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" +
4485 std::to_string(getAnchorScope()->size()) + "][#TBEP " +
4486 std::to_string(ToBeExploredFrom.size()) + "][#KDE " +
4487 std::to_string(KnownDeadEnds.size()) + "]";
4488 }
4489
4490 /// See AbstractAttribute::manifest(...).
4491 ChangeStatus manifest(Attributor &A) override {
4492 assert(getState().isValidState() &&
4493 "Attempted to manifest an invalid state!");
4494
4495 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
4496 Function &F = *getAnchorScope();
4497
4498 if (AssumedLiveBlocks.empty()) {
4499 A.deleteAfterManifest(F);
4500 return ChangeStatus::CHANGED;
4501 }
4502
4503 // Flag to determine if we can change an invoke to a call assuming the
4504 // callee is nounwind. This is not possible if the personality of the
4505 // function allows to catch asynchronous exceptions.
4506 bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
4507
4508 KnownDeadEnds.set_union(ToBeExploredFrom);
4509 for (const Instruction *DeadEndI : KnownDeadEnds) {
4510 auto *CB = dyn_cast<CallBase>(DeadEndI);
4511 if (!CB)
4512 continue;
4513 bool IsKnownNoReturn;
4514 bool MayReturn = !AA::hasAssumedIRAttr<Attribute::NoReturn>(
4515 A, this, IRPosition::callsite_function(*CB), DepClassTy::OPTIONAL,
4516 IsKnownNoReturn);
4517 if (MayReturn && (!Invoke2CallAllowed || !isa<InvokeInst>(CB)))
4518 continue;
4519
4520 if (auto *II = dyn_cast<InvokeInst>(DeadEndI))
4521 A.registerInvokeWithDeadSuccessor(const_cast<InvokeInst &>(*II));
4522 else
4523 A.changeToUnreachableAfterManifest(
4524 const_cast<Instruction *>(DeadEndI->getNextNode()));
4525 HasChanged = ChangeStatus::CHANGED;
4526 }
4527
4528 STATS_DECL(AAIsDead, BasicBlock, "Number of dead basic blocks deleted.");
4529 for (BasicBlock &BB : F)
4530 if (!AssumedLiveBlocks.count(&BB)) {
4531 A.deleteAfterManifest(BB);
4533 HasChanged = ChangeStatus::CHANGED;
4534 }
4535
4536 return HasChanged;
4537 }
4538
4539 /// See AbstractAttribute::updateImpl(...).
4540 ChangeStatus updateImpl(Attributor &A) override;
4541
4542 bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const override {
4543 assert(From->getParent() == getAnchorScope() &&
4544 To->getParent() == getAnchorScope() &&
4545 "Used AAIsDead of the wrong function");
4546 return isValidState() && !AssumedLiveEdges.count(std::make_pair(From, To));
4547 }
4548
4549 /// See AbstractAttribute::trackStatistics()
4550 void trackStatistics() const override {}
4551
4552 /// Returns true if the function is assumed dead.
4553 bool isAssumedDead() const override { return false; }
4554
4555 /// See AAIsDead::isKnownDead().
4556 bool isKnownDead() const override { return false; }
4557
4558 /// See AAIsDead::isAssumedDead(BasicBlock *).
4559 bool isAssumedDead(const BasicBlock *BB) const override {
4560 assert(BB->getParent() == getAnchorScope() &&
4561 "BB must be in the same anchor scope function.");
4562
4563 if (!getAssumed())
4564 return false;
4565 return !AssumedLiveBlocks.count(BB);
4566 }
4567
4568 /// See AAIsDead::isKnownDead(BasicBlock *).
4569 bool isKnownDead(const BasicBlock *BB) const override {
4570 return getKnown() && isAssumedDead(BB);
4571 }
4572
4573 /// See AAIsDead::isAssumed(Instruction *I).
4574 bool isAssumedDead(const Instruction *I) const override {
4575 assert(I->getParent()->getParent() == getAnchorScope() &&
4576 "Instruction must be in the same anchor scope function.");
4577
4578 if (!getAssumed())
4579 return false;
4580
4581 // If it is not in AssumedLiveBlocks then it for sure dead.
4582 // Otherwise, it can still be after noreturn call in a live block.
4583 if (!AssumedLiveBlocks.count(I->getParent()))
4584 return true;
4585
4586 // If it is not after a liveness barrier it is live.
4587 const Instruction *PrevI = I->getPrevNode();
4588 while (PrevI) {
4589 if (KnownDeadEnds.count(PrevI) || ToBeExploredFrom.count(PrevI))
4590 return true;
4591 PrevI = PrevI->getPrevNode();
4592 }
4593 return false;
4594 }
4595
4596 /// See AAIsDead::isKnownDead(Instruction *I).
4597 bool isKnownDead(const Instruction *I) const override {
4598 return getKnown() && isAssumedDead(I);
4599 }
4600
4601 /// Assume \p BB is (partially) live now and indicate to the Attributor \p A
4602 /// that internal function called from \p BB should now be looked at.
4603 bool assumeLive(Attributor &A, const BasicBlock &BB) {
4604 if (!AssumedLiveBlocks.insert(&BB).second)
4605 return false;
4606
4607 // We assume that all of BB is (probably) live now and if there are calls to
4608 // internal functions we will assume that those are now live as well. This
4609 // is a performance optimization for blocks with calls to a lot of internal
4610 // functions. It can however cause dead functions to be treated as live.
4611 for (const Instruction &I : BB)
4612 if (const auto *CB = dyn_cast<CallBase>(&I))
4613 if (auto *F = dyn_cast_if_present<Function>(CB->getCalledOperand()))
4614 if (F->hasLocalLinkage())
4615 A.markLiveInternalFunction(*F);
4616 return true;
4617 }
4618
4619 /// Collection of instructions that need to be explored again, e.g., we
4620 /// did assume they do not transfer control to (one of their) successors.
4622
4623 /// Collection of instructions that are known to not transfer control.
4625
4626 /// Collection of all assumed live edges
4628
4629 /// Collection of all assumed live BasicBlocks.
4630 DenseSet<const BasicBlock *> AssumedLiveBlocks;
4631};
4632
4633static bool
4634identifyAliveSuccessors(Attributor &A, const CallBase &CB,
4636 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4637 const IRPosition &IPos = IRPosition::callsite_function(CB);
4638
4639 bool IsKnownNoReturn;
4640 if (AA::hasAssumedIRAttr<Attribute::NoReturn>(
4641 A, &AA, IPos, DepClassTy::OPTIONAL, IsKnownNoReturn))
4642 return !IsKnownNoReturn;
4643 if (CB.isTerminator())
4644 AliveSuccessors.push_back(&CB.getSuccessor(0)->front());
4645 else
4646 AliveSuccessors.push_back(CB.getNextNode());
4647 return false;
4648}
4649
4650static bool
4651identifyAliveSuccessors(Attributor &A, const InvokeInst &II,
4653 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4654 bool UsedAssumedInformation =
4655 identifyAliveSuccessors(A, cast<CallBase>(II), AA, AliveSuccessors);
4656
4657 // First, determine if we can change an invoke to a call assuming the
4658 // callee is nounwind. This is not possible if the personality of the
4659 // function allows to catch asynchronous exceptions.
4660 if (AAIsDeadFunction::mayCatchAsynchronousExceptions(*II.getFunction())) {
4661 AliveSuccessors.push_back(&II.getUnwindDest()->front());
4662 } else {
4664
4665 bool IsKnownNoUnwind;
4666 if (AA::hasAssumedIRAttr<Attribute::NoUnwind>(
4667 A, &AA, IPos, DepClassTy::OPTIONAL, IsKnownNoUnwind)) {
4668 UsedAssumedInformation |= !IsKnownNoUnwind;
4669 } else {
4670 AliveSuccessors.push_back(&II.getUnwindDest()->front());
4671 }
4672 }
4673 return UsedAssumedInformation;
4674}
4675
4676static bool
4677identifyAliveSuccessors(Attributor &A, const BranchInst &BI,
4679 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4680 bool UsedAssumedInformation = false;
4681 if (BI.getNumSuccessors() == 1) {
4682 AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
4683 } else {
4684 std::optional<Constant *> C =
4685 A.getAssumedConstant(*BI.getCondition(), AA, UsedAssumedInformation);
4686 if (!C || isa_and_nonnull<UndefValue>(*C)) {
4687 // No value yet, assume both edges are dead.
4688 } else if (isa_and_nonnull<ConstantInt>(*C)) {
4689 const BasicBlock *SuccBB =
4690 BI.getSuccessor(1 - cast<ConstantInt>(*C)->getValue().getZExtValue());
4691 AliveSuccessors.push_back(&SuccBB->front());
4692 } else {
4693 AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
4694 AliveSuccessors.push_back(&BI.getSuccessor(1)->front());
4695 UsedAssumedInformation = false;
4696 }
4697 }
4698 return UsedAssumedInformation;
4699}
4700
4701static bool
4702identifyAliveSuccessors(Attributor &A, const SwitchInst &SI,
4704 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4705 bool UsedAssumedInformation = false;
4707 if (!A.getAssumedSimplifiedValues(IRPosition::value(*SI.getCondition()), &AA,
4708 Values, AA::AnyScope,
4709 UsedAssumedInformation)) {
4710 // Something went wrong, assume all successors are live.
4711 for (const BasicBlock *SuccBB : successors(SI.getParent()))
4712 AliveSuccessors.push_back(&SuccBB->front());
4713 return false;
4714 }
4715
4716 if (Values.empty() ||
4717 (Values.size() == 1 &&
4718 isa_and_nonnull<UndefValue>(Values.front().getValue()))) {
4719 // No valid value yet, assume all edges are dead.
4720 return UsedAssumedInformation;
4721 }
4722
4723 Type &Ty = *SI.getCondition()->getType();
4725 auto CheckForConstantInt = [&](Value *V) {
4726 if (auto *CI = dyn_cast_if_present<ConstantInt>(AA::getWithType(*V, Ty))) {
4727 Constants.insert(CI);
4728 return true;
4729 }
4730 return false;
4731 };
4732
4733 if (!all_of(Values, [&](AA::ValueAndContext &VAC) {
4734 return CheckForConstantInt(VAC.getValue());
4735 })) {
4736 for (const BasicBlock *SuccBB : successors(SI.getParent()))
4737 AliveSuccessors.push_back(&SuccBB->front());
4738 return UsedAssumedInformation;
4739 }
4740
4741 unsigned MatchedCases = 0;
4742 for (const auto &CaseIt : SI.cases()) {
4743 if (Constants.count(CaseIt.getCaseValue())) {
4744 ++MatchedCases;
4745 AliveSuccessors.push_back(&CaseIt.getCaseSuccessor()->front());
4746 }
4747 }
4748
4749 // If all potential values have been matched, we will not visit the default
4750 // case.
4751 if (MatchedCases < Constants.size())
4752 AliveSuccessors.push_back(&SI.getDefaultDest()->front());
4753 return UsedAssumedInformation;
4754}
4755
4756ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
4758
4759 if (AssumedLiveBlocks.empty()) {
4760 if (isAssumedDeadInternalFunction(A))
4762
4763 Function *F = getAnchorScope();
4764 ToBeExploredFrom.insert(&F->getEntryBlock().front());
4765 assumeLive(A, F->getEntryBlock());
4766 Change = ChangeStatus::CHANGED;
4767 }
4768
4769 LLVM_DEBUG(dbgs() << "[AAIsDead] Live [" << AssumedLiveBlocks.size() << "/"
4770 << getAnchorScope()->size() << "] BBs and "
4771 << ToBeExploredFrom.size() << " exploration points and "
4772 << KnownDeadEnds.size() << " known dead ends\n");
4773
4774 // Copy and clear the list of instructions we need to explore from. It is
4775 // refilled with instructions the next update has to look at.
4776 SmallVector<const Instruction *, 8> Worklist(ToBeExploredFrom.begin(),
4777 ToBeExploredFrom.end());
4778 decltype(ToBeExploredFrom) NewToBeExploredFrom;
4779
4781 while (!Worklist.empty()) {
4782 const Instruction *I = Worklist.pop_back_val();
4783 LLVM_DEBUG(dbgs() << "[AAIsDead] Exploration inst: " << *I << "\n");
4784
4785 // Fast forward for uninteresting instructions. We could look for UB here
4786 // though.
4787 while (!I->isTerminator() && !isa<CallBase>(I))
4788 I = I->getNextNode();
4789
4790 AliveSuccessors.clear();
4791
4792 bool UsedAssumedInformation = false;
4793 switch (I->getOpcode()) {
4794 // TODO: look for (assumed) UB to backwards propagate "deadness".
4795 default:
4796 assert(I->isTerminator() &&
4797 "Expected non-terminators to be handled already!");
4798 for (const BasicBlock *SuccBB : successors(I->getParent()))
4799 AliveSuccessors.push_back(&SuccBB->front());
4800 break;
4801 case Instruction::Call:
4802 UsedAssumedInformation = identifyAliveSuccessors(A, cast<CallInst>(*I),
4803 *this, AliveSuccessors);
4804 break;
4805 case Instruction::Invoke:
4806 UsedAssumedInformation = identifyAliveSuccessors(A, cast<InvokeInst>(*I),
4807 *this, AliveSuccessors);
4808 break;
4809 case Instruction::Br:
4810 UsedAssumedInformation = identifyAliveSuccessors(A, cast<BranchInst>(*I),
4811 *this, AliveSuccessors);
4812 break;
4813 case Instruction::Switch:
4814 UsedAssumedInformation = identifyAliveSuccessors(A, cast<SwitchInst>(*I),
4815 *this, AliveSuccessors);
4816 break;
4817 }
4818
4819 if (UsedAssumedInformation) {
4820 NewToBeExploredFrom.insert(I);
4821 } else if (AliveSuccessors.empty() ||
4822 (I->isTerminator() &&
4823 AliveSuccessors.size() < I->getNumSuccessors())) {
4824 if (KnownDeadEnds.insert(I))
4825 Change = ChangeStatus::CHANGED;
4826 }
4827
4828 LLVM_DEBUG(dbgs() << "[AAIsDead] #AliveSuccessors: "
4829 << AliveSuccessors.size() << " UsedAssumedInformation: "
4830 << UsedAssumedInformation << "\n");
4831
4832 for (const Instruction *AliveSuccessor : AliveSuccessors) {
4833 if (!I->isTerminator()) {
4834 assert(AliveSuccessors.size() == 1 &&
4835 "Non-terminator expected to have a single successor!");
4836 Worklist.push_back(AliveSuccessor);
4837 } else {
4838 // record the assumed live edge
4839 auto Edge = std::make_pair(I->getParent(), AliveSuccessor->getParent());
4840 if (AssumedLiveEdges.insert(Edge).second)
4841 Change = ChangeStatus::CHANGED;
4842 if (assumeLive(A, *AliveSuccessor->getParent()))
4843 Worklist.push_back(AliveSuccessor);
4844 }
4845 }
4846 }
4847
4848 // Check if the content of ToBeExploredFrom changed, ignore the order.
4849 if (NewToBeExploredFrom.size() != ToBeExploredFrom.size() ||
4850 llvm::any_of(NewToBeExploredFrom, [&](const Instruction *I) {
4851 return !ToBeExploredFrom.count(I);
4852 })) {
4853 Change = ChangeStatus::CHANGED;
4854 ToBeExploredFrom = std::move(NewToBeExploredFrom);
4855 }
4856
4857 // If we know everything is live there is no need to query for liveness.
4858 // Instead, indicating a pessimistic fixpoint will cause the state to be
4859 // "invalid" and all queries to be answered conservatively without lookups.
4860 // To be in this state we have to (1) finished the exploration and (3) not
4861 // discovered any non-trivial dead end and (2) not ruled unreachable code
4862 // dead.
4863 if (ToBeExploredFrom.empty() &&
4864 getAnchorScope()->size() == AssumedLiveBlocks.size() &&
4865 llvm::all_of(KnownDeadEnds, [](const Instruction *DeadEndI) {
4866 return DeadEndI->isTerminator() && DeadEndI->getNumSuccessors() == 0;
4867 }))
4868 return indicatePessimisticFixpoint();
4869 return Change;
4870}
4871
4872/// Liveness information for a call sites.
4873struct AAIsDeadCallSite final : AAIsDeadFunction {
4874 AAIsDeadCallSite(const IRPosition &IRP, Attributor &A)
4875 : AAIsDeadFunction(IRP, A) {}
4876
4877 /// See AbstractAttribute::initialize(...).
4878 void initialize(Attributor &A) override {
4879 // TODO: Once we have call site specific value information we can provide
4880 // call site specific liveness information and then it makes
4881 // sense to specialize attributes for call sites instead of
4882 // redirecting requests to the callee.
4883 llvm_unreachable("Abstract attributes for liveness are not "
4884 "supported for call sites yet!");
4885 }
4886
4887 /// See AbstractAttribute::updateImpl(...).
4888 ChangeStatus updateImpl(Attributor &A) override {
4889 return indicatePessimisticFixpoint();
4890 }
4891
4892 /// See AbstractAttribute::trackStatistics()
4893 void trackStatistics() const override {}
4894};
4895} // namespace
4896
4897/// -------------------- Dereferenceable Argument Attribute --------------------
4898
4899namespace {
4900struct AADereferenceableImpl : AADereferenceable {
4901 AADereferenceableImpl(const IRPosition &IRP, Attributor &A)
4902 : AADereferenceable(IRP, A) {}
4903 using StateType = DerefState;
4904
4905 /// See AbstractAttribute::initialize(...).
4906 void initialize(Attributor &A) override {
4907 Value &V = *getAssociatedValue().stripPointerCasts();
4909 A.getAttrs(getIRPosition(),
4910 {Attribute::Dereferenceable, Attribute::DereferenceableOrNull},
4911 Attrs, /* IgnoreSubsumingPositions */ false);
4912 for (const Attribute &Attr : Attrs)
4913 takeKnownDerefBytesMaximum(Attr.getValueAsInt());
4914
4915 // Ensure we initialize the non-null AA (if necessary).
4916 bool IsKnownNonNull;
4917 AA::hasAssumedIRAttr<Attribute::NonNull>(
4918 A, this, getIRPosition(), DepClassTy::OPTIONAL, IsKnownNonNull);
4919
4920 bool CanBeNull, CanBeFreed;
4921 takeKnownDerefBytesMaximum(V.getPointerDereferenceableBytes(
4922 A.getDataLayout(), CanBeNull, CanBeFreed));
4923
4924 if (Instruction *CtxI = getCtxI())
4925 followUsesInMBEC(*this, A, getState(), *CtxI);
4926 }
4927
4928 /// See AbstractAttribute::getState()
4929 /// {
4930 StateType &getState() override { return *this; }
4931 const StateType &getState() const override { return *this; }
4932 /// }
4933
4934 /// Helper function for collecting accessed bytes in must-be-executed-context
4935 void addAccessedBytesForUse(Attributor &A, const Use *U, const Instruction *I,
4936 DerefState &State) {
4937 const Value *UseV = U->get();
4938 if (!UseV->getType()->isPointerTy())
4939 return;
4940
4941 std::optional<MemoryLocation> Loc = MemoryLocation::getOrNone(I);
4942 if (!Loc || Loc->Ptr != UseV || !Loc->Size.isPrecise() || I->isVolatile())
4943 return;
4944
4945 int64_t Offset;
4947 Loc->Ptr, Offset, A.getDataLayout(), /*AllowNonInbounds*/ true);
4948 if (Base && Base == &getAssociatedValue())
4949 State.addAccessedBytes(Offset, Loc->Size.getValue());
4950 }
4951
4952 /// See followUsesInMBEC
4953 bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
4955 bool IsNonNull = false;
4956 bool TrackUse = false;
4957 int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse(
4958 A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse);
4959 LLVM_DEBUG(dbgs() << "[AADereferenceable] Deref bytes: " << DerefBytes
4960 << " for instruction " << *I << "\n");
4961
4962 addAccessedBytesForUse(A, U, I, State);
4963 State.takeKnownDerefBytesMaximum(DerefBytes);
4964 return TrackUse;
4965 }
4966
4967 /// See AbstractAttribute::manifest(...).
4968 ChangeStatus manifest(Attributor &A) override {
4969 ChangeStatus Change = AADereferenceable::manifest(A);
4970 bool IsKnownNonNull;
4971 bool IsAssumedNonNull = AA::hasAssumedIRAttr<Attribute::NonNull>(
4972 A, this, getIRPosition(), DepClassTy::NONE, IsKnownNonNull);
4973 if (IsAssumedNonNull &&
4974