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