55#include "llvm/IR/IntrinsicsAMDGPU.h"
56#include "llvm/IR/IntrinsicsNVPTX.h"
83#define DEBUG_TYPE "attributor"
87 cl::desc(
"Manifest Attributor internal string attributes."),
100 cl::desc(
"Maximum number of potential values to be "
101 "tracked for each position."),
106 "attributor-max-potential-values-iterations",
cl::Hidden,
108 "Maximum number of iterations we keep dismantling potential values."),
111STATISTIC(NumAAs,
"Number of abstract attributes created");
112STATISTIC(NumIndirectCallsPromoted,
"Number of indirect calls promoted");
127#define BUILD_STAT_MSG_IR_ATTR(TYPE, NAME) \
128 ("Number of " #TYPE " marked '" #NAME "'")
129#define BUILD_STAT_NAME(NAME, TYPE) NumIR##TYPE##_##NAME
130#define STATS_DECL_(NAME, MSG) STATISTIC(NAME, MSG);
131#define STATS_DECL(NAME, TYPE, MSG) \
132 STATS_DECL_(BUILD_STAT_NAME(NAME, TYPE), MSG);
133#define STATS_TRACK(NAME, TYPE) ++(BUILD_STAT_NAME(NAME, TYPE));
134#define STATS_DECLTRACK(NAME, TYPE, MSG) \
135 {STATS_DECL(NAME, TYPE, MSG) STATS_TRACK(NAME, TYPE)}
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 "'"))
158#define PIPE_OPERATOR(CLASS) \
159 raw_ostream &operator<<(raw_ostream &OS, const CLASS &AA) { \
160 return OS << static_cast<const AbstractAttribute &>(AA); \
217 bool HeaderOnly,
CycleRef *CPtr =
nullptr) {
220 auto *BB =
I->getParent();
237 if (
DL.getTypeSizeInBits(Ty) !=
DL.getTypeAllocSizeInBits(Ty))
262 StartPos +=
DL.getTypeAllocSizeInBits(ElTy);
272 bool AllowVolatile) {
273 if (!AllowVolatile &&
I->isVolatile())
277 return LI->getPointerOperand();
281 return SI->getPointerOperand();
285 return CXI->getPointerOperand();
289 return RMWI->getPointerOperand();
311 bool GetMinOffset,
bool AllowNonInbounds,
312 bool UseAssumed =
false) {
314 auto AttributorAnalysis = [&](
Value &V,
APInt &ROffset) ->
bool {
321 if (!ValueConstantRangeAA)
325 if (
Range.isFullSet())
331 ROffset =
Range.getSignedMin();
333 ROffset =
Range.getSignedMax();
344 const Value *Ptr, int64_t &BytesOffset,
349 true, AllowNonInbounds);
357template <
typename AAType,
typename StateType =
typename AAType::StateType,
359 bool RecurseForSelectAndPHI =
true>
361 Attributor &
A,
const AAType &QueryingAA, StateType &S,
363 LLVM_DEBUG(
dbgs() <<
"[Attributor] Clamp return value states for "
364 << QueryingAA <<
" into " << S <<
"\n");
366 assert((QueryingAA.getIRPosition().getPositionKind() ==
368 QueryingAA.getIRPosition().getPositionKind() ==
370 "Can only clamp returned value states for a function returned or call "
371 "site returned position!");
375 std::optional<StateType>
T;
378 auto CheckReturnValue = [&](
Value &RV) ->
bool {
392 <<
" AA: " <<
AA->getAsStr(&
A) <<
" @ " << RVPos <<
"\n");
393 const StateType &AAS =
AA->getState();
395 T = StateType::getBestState(AAS);
397 LLVM_DEBUG(
dbgs() <<
"[Attributor] AA State: " << AAS <<
" RV State: " <<
T
399 return T->isValidState();
402 if (!
A.checkForAllReturnedValues(CheckReturnValue, QueryingAA,
404 RecurseForSelectAndPHI))
405 S.indicatePessimisticFixpoint();
412template <
typename AAType,
typename BaseType,
413 typename StateType =
typename BaseType::StateType,
414 bool PropagateCallBaseContext =
false,
416 bool RecurseForSelectAndPHI =
true>
417struct AAReturnedFromReturnedValues :
public BaseType {
418 AAReturnedFromReturnedValues(
const IRPosition &IRP, Attributor &
A)
423 StateType S(StateType::getBestState(this->getState()));
425 RecurseForSelectAndPHI>(
427 PropagateCallBaseContext ? this->getCallBaseContext() : nullptr);
436template <
typename AAType,
typename StateType =
typename AAType::StateType,
438static void clampCallSiteArgumentStates(
Attributor &
A,
const AAType &QueryingAA,
440 LLVM_DEBUG(
dbgs() <<
"[Attributor] Clamp call site argument states for "
441 << QueryingAA <<
" into " << S <<
"\n");
443 assert(QueryingAA.getIRPosition().getPositionKind() ==
445 "Can only clamp call site argument states for an argument position!");
449 std::optional<StateType>
T;
452 unsigned ArgNo = QueryingAA.getIRPosition().getCallSiteArgNo();
472 LLVM_DEBUG(
dbgs() <<
"[Attributor] ACS: " << *ACS.getInstruction()
473 <<
" AA: " <<
AA->getAsStr(&
A) <<
" @" << ACSArgPos
475 const StateType &AAS =
AA->getState();
477 T = StateType::getBestState(AAS);
479 LLVM_DEBUG(
dbgs() <<
"[Attributor] AA State: " << AAS <<
" CSA State: " <<
T
481 return T->isValidState();
484 bool UsedAssumedInformation =
false;
485 if (!
A.checkForAllCallSites(CallSiteCheck, QueryingAA,
true,
486 UsedAssumedInformation))
487 S.indicatePessimisticFixpoint();
494template <
typename AAType,
typename BaseType,
495 typename StateType =
typename AAType::StateType,
497bool getArgumentStateFromCallBaseContext(
Attributor &
A,
501 "Expected an 'argument' position !");
507 assert(ArgNo >= 0 &&
"Invalid Arg No!");
521 const StateType &CBArgumentState =
522 static_cast<const StateType &
>(
AA->getState());
524 LLVM_DEBUG(
dbgs() <<
"[Attributor] Briding Call site context to argument"
525 <<
"Position:" << Pos <<
"CB Arg state:" << CBArgumentState
529 State ^= CBArgumentState;
534template <
typename AAType,
typename BaseType,
535 typename StateType =
typename AAType::StateType,
536 bool BridgeCallBaseContext =
false,
538struct AAArgumentFromCallSiteArguments :
public BaseType {
539 AAArgumentFromCallSiteArguments(
const IRPosition &IRP, Attributor &
A)
544 StateType S = StateType::getBestState(this->getState());
546 if (BridgeCallBaseContext) {
548 getArgumentStateFromCallBaseContext<AAType,
BaseType, StateType,
550 A, *
this, this->getIRPosition(), S);
554 clampCallSiteArgumentStates<AAType, StateType, IRAttributeKind>(
A, *
this,
564template <
typename AAType,
typename BaseType,
565 typename StateType =
typename BaseType::StateType,
566 bool IntroduceCallBaseContext =
false,
568struct AACalleeToCallSite :
public BaseType {
569 AACalleeToCallSite(
const IRPosition &IRP, Attributor &
A) :
BaseType(IRP,
A) {}
573 auto IRPKind = this->getIRPosition().getPositionKind();
576 "Can only wrap function returned positions for call site "
577 "returned positions!");
578 auto &S = this->getState();
581 if (IntroduceCallBaseContext)
582 LLVM_DEBUG(
dbgs() <<
"[Attributor] Introducing call base context:" << CB
587 for (
const Function *Callee : Callees) {
591 IntroduceCallBaseContext ? &CB :
nullptr)
593 *
Callee, IntroduceCallBaseContext ? &CB : nullptr);
595 if (Attribute::isEnumAttrKind(IRAttributeKind)) {
598 A,
this, FnPos, DepClassTy::REQUIRED, IsKnown))
604 A.getAAFor<AAType>(*
this, FnPos, DepClassTy::REQUIRED);
608 if (S.isAtFixpoint())
609 return S.isValidState();
613 if (!
A.checkForAllCallees(CalleePred, *
this, CB))
614 return S.indicatePessimisticFixpoint();
620template <
class AAType,
typename StateType =
typename AAType::StateType>
626 auto EIt = Explorer.
begin(CtxI), EEnd = Explorer.
end(CtxI);
627 for (
unsigned u = 0;
u <
Uses.size(); ++
u) {
631 if (Found &&
AA.followUseInMBEC(
A, U, UserI, State))
646template <
class AAType,
typename StateType =
typename AAType::StateType>
647static void followUsesInMBEC(AAType &
AA,
Attributor &
A, StateType &S,
649 const Value &Val =
AA.getIRPosition().getAssociatedValue();
654 A.getInfoCache().getMustBeExecutedContextExplorer();
660 for (
const Use &U : Val.
uses())
663 followUsesInContext<AAType>(
AA,
A, *Explorer, &CtxI,
Uses, S);
665 if (S.isAtFixpoint())
709 StateType ParentState;
713 ParentState.indicateOptimisticFixpoint();
715 for (
const BasicBlock *BB : Br->successors()) {
716 StateType ChildState;
718 size_t BeforeSize =
Uses.size();
719 followUsesInContext(
AA,
A, *Explorer, &BB->front(),
Uses, ChildState);
722 for (
auto It =
Uses.begin() + BeforeSize; It !=
Uses.end();)
725 ParentState &= ChildState;
776 R.indicatePessimisticFixpoint();
793 BS.indicateOptimisticFixpoint();
799 BS.indicatePessimisticFixpoint();
869 template <
typename F>
876 if (!
Range.mayOverlap(ItRange))
878 bool IsExact =
Range == ItRange && !
Range.offsetOrSizeAreUnknown();
879 for (
auto Index : It.getSecond()) {
889 template <
typename F>
900 for (
unsigned Index : LocalList->getSecond()) {
903 if (
Range.offsetAndSizeAreUnknown())
919 RemoteI = RemoteI ? RemoteI : &
I;
923 bool AccExists =
false;
925 for (
auto Index : LocalList) {
927 if (
A.getLocalInst() == &
I) {
936 <<
"[AAPointerInfo] Inserting access in new offset bins\n";);
938 for (
auto Key : ToAdd) {
945 AccessList.emplace_back(&
I, RemoteI, Ranges, Content, Kind, Ty);
947 "New Access should have been at AccIndex");
948 LocalList.push_back(AccIndex);
957 auto Before = Current;
959 if (Current == Before)
962 auto &ExistingRanges = Before.getRanges();
963 auto &NewRanges = Current.getRanges();
970 <<
"[AAPointerInfo] Removing access from old offset bins\n";);
977 "Expected bin to actually contain the Access.");
999struct AAPointerInfoImpl
1000 :
public StateWrapper<AA::PointerInfo::State, AAPointerInfo> {
1005 const std::string getAsStr(
Attributor *
A)
const override {
1006 return std::string(
"PointerInfo ") +
1007 (isValidState() ? (std::string(
"#") +
1008 std::to_string(OffsetBins.size()) +
" bins")
1013 [](int64_t O) {
return std::to_string(O); }),
1021 return AAPointerInfo::manifest(
A);
1024 const_bin_iterator
begin()
const override {
return State::begin(); }
1025 const_bin_iterator
end()
const override {
return State::end(); }
1026 int64_t numOffsetBins()
const override {
return State::numOffsetBins(); }
1027 bool reachesReturn()
const override {
1028 return !ReturnedOffsets.isUnassigned();
1030 void addReturnedOffsetsTo(OffsetInfo &OI)
const override {
1031 if (ReturnedOffsets.isUnknown()) {
1036 OffsetInfo MergedOI;
1037 for (
auto Offset : ReturnedOffsets) {
1038 OffsetInfo TmpOI = OI;
1040 MergedOI.merge(TmpOI);
1042 OI = std::move(MergedOI);
1045 ChangeStatus setReachesReturn(
const OffsetInfo &ReachedReturnedOffsets) {
1046 if (ReturnedOffsets.isUnknown())
1047 return ChangeStatus::UNCHANGED;
1048 if (ReachedReturnedOffsets.isUnknown()) {
1049 ReturnedOffsets.setUnknown();
1050 return ChangeStatus::CHANGED;
1052 if (ReturnedOffsets.merge(ReachedReturnedOffsets))
1053 return ChangeStatus::CHANGED;
1054 return ChangeStatus::UNCHANGED;
1057 bool forallInterferingAccesses(
1059 function_ref<
bool(
const AAPointerInfo::Access &,
bool)> CB)
1061 return State::forallInterferingAccesses(
Range, CB);
1064 bool forallInterferingAccesses(
1065 Attributor &
A,
const AbstractAttribute &QueryingAA, Instruction &
I,
1066 bool FindInterferingWrites,
bool FindInterferingReads,
1067 function_ref<
bool(
const Access &,
bool)> UserCB,
bool &HasBeenWrittenTo,
1069 function_ref<
bool(
const Access &)> SkipCB)
const override {
1070 HasBeenWrittenTo =
false;
1072 SmallPtrSet<const Access *, 8> DominatingWrites;
1080 const auto *ExecDomainAA =
A.lookupAAFor<AAExecutionDomain>(
1082 bool AllInSameNoSyncFn = IsAssumedNoSync;
1083 bool InstIsExecutedByInitialThreadOnly =
1084 ExecDomainAA && ExecDomainAA->isExecutedByInitialThreadOnly(
I);
1091 bool InstIsExecutedInAlignedRegion =
1092 FindInterferingReads && ExecDomainAA &&
1093 ExecDomainAA->isExecutedInAlignedRegion(
A,
I);
1095 if (InstIsExecutedInAlignedRegion || InstIsExecutedByInitialThreadOnly)
1096 A.recordDependence(*ExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
1098 InformationCache &InfoCache =
A.getInfoCache();
1099 bool IsThreadLocalObj =
1108 auto CanIgnoreThreadingForInst = [&](
const Instruction &
I) ->
bool {
1109 if (IsThreadLocalObj || AllInSameNoSyncFn)
1111 const auto *FnExecDomainAA =
1112 I.getFunction() == &
Scope
1114 :
A.lookupAAFor<AAExecutionDomain>(
1117 if (!FnExecDomainAA)
1119 if (InstIsExecutedInAlignedRegion ||
1120 (FindInterferingWrites &&
1121 FnExecDomainAA->isExecutedInAlignedRegion(
A,
I))) {
1122 A.recordDependence(*FnExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
1125 if (InstIsExecutedByInitialThreadOnly &&
1126 FnExecDomainAA->isExecutedByInitialThreadOnly(
I)) {
1127 A.recordDependence(*FnExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
1136 auto CanIgnoreThreading = [&](
const Access &Acc) ->
bool {
1137 return CanIgnoreThreadingForInst(*Acc.getRemoteInst()) ||
1138 (Acc.getRemoteInst() != Acc.getLocalInst() &&
1139 CanIgnoreThreadingForInst(*Acc.getLocalInst()));
1143 bool IsKnownNoRecurse;
1151 bool InstInKernel =
A.getInfoCache().isKernel(Scope);
1152 bool ObjHasKernelLifetime =
false;
1153 const bool UseDominanceReasoning =
1154 FindInterferingWrites && IsKnownNoRecurse;
1155 const DominatorTree *DT =
1164 unsigned VAS =
V->getType()->getPointerAddressSpace();
1175 std::function<bool(
const Function &)> IsLiveInCalleeCB;
1180 const Function *AIFn = AI->getFunction();
1181 ObjHasKernelLifetime =
A.getInfoCache().isKernel(*AIFn);
1182 bool IsKnownNoRecurse;
1185 IsKnownNoRecurse)) {
1186 IsLiveInCalleeCB = [AIFn](
const Function &Fn) {
return AIFn != &Fn; };
1191 ObjHasKernelLifetime = HasKernelLifetime(GV, *GV->getParent());
1192 if (ObjHasKernelLifetime)
1193 IsLiveInCalleeCB = [&
A](
const Function &Fn) {
1194 return !
A.getInfoCache().isKernel(Fn);
1202 auto AccessCB = [&](
const Access &Acc,
bool Exact) {
1203 Function *AccScope = Acc.getRemoteInst()->getFunction();
1204 bool AccInSameScope = AccScope == &
Scope;
1208 if (InstInKernel && ObjHasKernelLifetime && !AccInSameScope &&
1209 A.getInfoCache().isKernel(*AccScope))
1212 if (Exact && Acc.isMustAccess() && Acc.getRemoteInst() != &
I) {
1213 if (Acc.isWrite() || (
isa<LoadInst>(
I) && Acc.isWriteOrAssumption()))
1214 ExclusionSet.
insert(Acc.getRemoteInst());
1217 if ((!FindInterferingWrites || !Acc.isWriteOrAssumption()) &&
1218 (!FindInterferingReads || !Acc.isRead()))
1221 bool Dominates = FindInterferingWrites && DT && Exact &&
1222 Acc.isMustAccess() && AccInSameScope &&
1225 DominatingWrites.
insert(&Acc);
1229 AllInSameNoSyncFn &= Acc.getRemoteInst()->getFunction() == &
Scope;
1231 InterferingAccesses.
push_back({&Acc, Exact});
1234 if (!State::forallInterferingAccesses(
I, AccessCB,
Range))
1237 HasBeenWrittenTo = !DominatingWrites.
empty();
1241 for (
const Access *Acc : DominatingWrites) {
1242 if (!LeastDominatingWriteInst) {
1243 LeastDominatingWriteInst = Acc->getRemoteInst();
1244 }
else if (DT->
dominates(LeastDominatingWriteInst,
1245 Acc->getRemoteInst())) {
1246 LeastDominatingWriteInst = Acc->getRemoteInst();
1251 auto CanSkipAccess = [&](
const Access &Acc,
bool Exact) {
1252 if (SkipCB && SkipCB(Acc))
1254 if (!CanIgnoreThreading(Acc))
1260 bool ReadChecked = !FindInterferingReads;
1261 bool WriteChecked = !FindInterferingWrites;
1267 &ExclusionSet, IsLiveInCalleeCB))
1272 if (!WriteChecked) {
1274 &ExclusionSet, IsLiveInCalleeCB))
1275 WriteChecked =
true;
1289 if (!WriteChecked && HasBeenWrittenTo &&
1290 Acc.getRemoteInst()->getFunction() != &Scope) {
1292 const auto *FnReachabilityAA =
A.getAAFor<AAInterFnReachability>(
1294 if (FnReachabilityAA) {
1300 if (!FnReachabilityAA->instructionCanReach(
1301 A, *LeastDominatingWriteInst,
1302 *Acc.getRemoteInst()->getFunction(), &ExclusionSet))
1303 WriteChecked =
true;
1310 if (ReadChecked && WriteChecked)
1313 if (!DT || !UseDominanceReasoning)
1315 if (!DominatingWrites.count(&Acc))
1317 return LeastDominatingWriteInst != Acc.getRemoteInst();
1322 for (
auto &It : InterferingAccesses) {
1323 if ((!AllInSameNoSyncFn && !IsThreadLocalObj && !ExecDomainAA) ||
1324 !CanSkipAccess(*It.first, It.second)) {
1325 if (!UserCB(*It.first, It.second))
1333 const AAPointerInfo &OtherAA,
1335 using namespace AA::PointerInfo;
1337 return indicatePessimisticFixpoint();
1340 const auto &OtherAAImpl =
static_cast<const AAPointerInfoImpl &
>(OtherAA);
1341 bool IsByval = OtherAAImpl.getAssociatedArgument()->hasByValAttr();
1342 Changed |= setReachesReturn(OtherAAImpl.ReturnedOffsets);
1345 const auto &State = OtherAAImpl.getState();
1346 for (
const auto &It : State) {
1347 for (
auto Index : It.getSecond()) {
1348 const auto &RAcc = State.getAccess(Index);
1349 if (IsByval && !RAcc.isRead())
1351 bool UsedAssumedInformation =
false;
1353 auto Content =
A.translateArgumentToCallSiteContent(
1354 RAcc.getContent(), CB, *
this, UsedAssumedInformation);
1355 AK =
AccessKind(AK & (IsByval ? AccessKind::AK_R : AccessKind::AK_RW));
1356 AK =
AccessKind(AK | (RAcc.isMayAccess() ? AK_MAY : AK_MUST));
1358 Changed |= addAccess(
A, RAcc.getRanges(), CB, Content, AK,
1359 RAcc.getType(), RAcc.getRemoteInst());
1365 ChangeStatus translateAndAddState(Attributor &
A,
const AAPointerInfo &OtherAA,
1366 const OffsetInfo &Offsets, CallBase &CB,
1368 using namespace AA::PointerInfo;
1370 return indicatePessimisticFixpoint();
1372 const auto &OtherAAImpl =
static_cast<const AAPointerInfoImpl &
>(OtherAA);
1376 const auto &State = OtherAAImpl.getState();
1377 for (
const auto &It : State) {
1378 for (
auto Index : It.getSecond()) {
1379 const auto &RAcc = State.getAccess(Index);
1380 if (!IsMustAcc && RAcc.isAssumption())
1382 for (
auto Offset : Offsets) {
1386 if (!NewRanges.isUnknown()) {
1387 NewRanges.addToAllOffsets(Offset);
1392 Changed |= addAccess(
A, NewRanges, CB, RAcc.getContent(), AK,
1393 RAcc.getType(), RAcc.getRemoteInst());
1402 void trackPointerInfoStatistics(
const IRPosition &IRP)
const {}
1405 void dumpState(raw_ostream &O) {
1406 for (
auto &It : OffsetBins) {
1407 O <<
"[" << It.first.Offset <<
"-" << It.first.Offset + It.first.Size
1408 <<
"] : " << It.getSecond().size() <<
"\n";
1409 for (
auto AccIndex : It.getSecond()) {
1410 auto &Acc = AccessList[AccIndex];
1411 O <<
" - " << Acc.getKind() <<
" - " << *Acc.getLocalInst() <<
"\n";
1412 if (Acc.getLocalInst() != Acc.getRemoteInst())
1413 O <<
" --> " << *Acc.getRemoteInst()
1415 if (!Acc.isWrittenValueYetUndetermined()) {
1417 O <<
" - c: func " << Acc.getWrittenValue()->getName()
1419 else if (Acc.getWrittenValue())
1420 O <<
" - c: " << *Acc.getWrittenValue() <<
"\n";
1422 O <<
" - c: <unknown>\n";
1429struct AAPointerInfoFloating :
public AAPointerInfoImpl {
1431 AAPointerInfoFloating(
const IRPosition &IRP, Attributor &
A)
1432 : AAPointerInfoImpl(IRP,
A) {}
1435 bool handleAccess(Attributor &
A, Instruction &
I,
1436 std::optional<Value *> Content,
AccessKind Kind,
1439 using namespace AA::PointerInfo;
1441 const DataLayout &
DL =
A.getDataLayout();
1442 TypeSize AccessSize =
DL.getTypeStoreSize(&Ty);
1451 if (!VT || VT->getElementCount().isScalable() ||
1453 (*Content)->getType() != VT ||
1454 DL.getTypeStoreSize(VT->getElementType()).isScalable()) {
1465 int64_t ElementSize =
DL.getTypeStoreSize(ElementType).getFixedValue();
1470 for (
int i = 0, e = VT->getElementCount().getFixedValue(); i != e; ++i) {
1472 ConstContent, ConstantInt::get(Int32Ty, i));
1479 for (
auto &ElementOffset : ElementOffsets)
1480 ElementOffset += ElementSize;
1493 bool collectConstantsForGEP(Attributor &
A,
const DataLayout &
DL,
1494 OffsetInfo &UsrOI,
const OffsetInfo &PtrOI,
1495 const GEPOperator *
GEP);
1498 void trackStatistics()
const override {
1499 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1503bool AAPointerInfoFloating::collectConstantsForGEP(Attributor &
A,
1504 const DataLayout &
DL,
1506 const OffsetInfo &PtrOI,
1507 const GEPOperator *
GEP) {
1508 unsigned BitWidth =
DL.getIndexTypeSizeInBits(
GEP->getType());
1509 SmallMapVector<Value *, APInt, 4> VariableOffsets;
1512 assert(!UsrOI.isUnknown() && !PtrOI.isUnknown() &&
1513 "Don't look for constant values if the offset has already been "
1514 "determined to be unknown.");
1516 if (!
GEP->collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset)) {
1522 << (VariableOffsets.
empty() ?
"" :
"not") <<
" constant "
1526 Union.addToAll(ConstantOffset.getSExtValue());
1531 for (
const auto &VI : VariableOffsets) {
1532 auto *PotentialConstantsAA =
A.getAAFor<AAPotentialConstantValues>(
1534 if (!PotentialConstantsAA || !PotentialConstantsAA->isValidState()) {
1540 if (PotentialConstantsAA->undefIsContained())
1547 auto &AssumedSet = PotentialConstantsAA->getAssumedSet();
1548 if (AssumedSet.empty())
1552 for (
const auto &ConstOffset : AssumedSet) {
1553 auto CopyPerOffset =
Union;
1554 CopyPerOffset.addToAll(ConstOffset.getSExtValue() *
1555 VI.second.getZExtValue());
1556 Product.merge(CopyPerOffset);
1561 UsrOI = std::move(Union);
1565ChangeStatus AAPointerInfoFloating::updateImpl(Attributor &
A) {
1566 using namespace AA::PointerInfo;
1568 const DataLayout &
DL =
A.getDataLayout();
1569 Value &AssociatedValue = getAssociatedValue();
1571 DenseMap<Value *, OffsetInfo> OffsetInfoMap;
1572 OffsetInfoMap[&AssociatedValue].
insert(0);
1574 auto HandlePassthroughUser = [&](
Value *Usr,
Value *CurPtr,
bool &Follow) {
1585 "CurPtr does not exist in the map!");
1587 auto &UsrOI = OffsetInfoMap[Usr];
1588 auto &PtrOI = OffsetInfoMap[CurPtr];
1589 assert(!PtrOI.isUnassigned() &&
1590 "Cannot pass through if the input Ptr was not visited!");
1596 auto UsePred = [&](
const Use &
U,
bool &Follow) ->
bool {
1598 User *Usr =
U.getUser();
1599 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] Analyze " << *CurPtr <<
" in " << *Usr
1602 "The current pointer offset should have been seeded!");
1603 assert(!OffsetInfoMap[CurPtr].isUnassigned() &&
1604 "Current pointer should be assigned");
1608 return HandlePassthroughUser(Usr, CurPtr, Follow);
1610 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] Unhandled constant user " << *CE
1618 auto &UsrOI = OffsetInfoMap[Usr];
1619 auto &PtrOI = OffsetInfoMap[CurPtr];
1621 if (UsrOI.isUnknown())
1624 if (PtrOI.isUnknown()) {
1630 Follow = collectConstantsForGEP(
A,
DL, UsrOI, PtrOI,
GEP);
1636 return HandlePassthroughUser(Usr, CurPtr, Follow);
1641 if (RI->getFunction() == getAssociatedFunction()) {
1642 auto &PtrOI = OffsetInfoMap[CurPtr];
1643 Changed |= setReachesReturn(PtrOI);
1656 auto &UsrOI = PhiIt->second;
1657 auto &PtrOI = OffsetInfoMap[CurPtr];
1661 if (PtrOI.isUnknown()) {
1662 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] PHI operand offset unknown "
1663 << *CurPtr <<
" in " << *
PHI <<
"\n");
1664 Follow = !UsrOI.isUnknown();
1670 if (UsrOI == PtrOI) {
1671 assert(!PtrOI.isUnassigned() &&
1672 "Cannot assign if the current Ptr was not visited!");
1673 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] PHI is invariant (so far)");
1683 auto It = OffsetInfoMap.
find(CurPtrBase);
1684 if (It == OffsetInfoMap.
end()) {
1685 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] PHI operand is too complex "
1686 << *CurPtr <<
" in " << *
PHI
1687 <<
" (base: " << *CurPtrBase <<
")\n");
1701 A.getInfoCache().getAnalysisResultForFunction<CycleAnalysis>(
1702 *
PHI->getFunction());
1704 auto BaseOI = It->getSecond();
1705 BaseOI.addToAll(
Offset.getZExtValue());
1706 if (IsFirstPHIUser || BaseOI == UsrOI) {
1707 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] PHI is invariant " << *CurPtr
1708 <<
" in " << *Usr <<
"\n");
1709 return HandlePassthroughUser(Usr, CurPtr, Follow);
1713 dbgs() <<
"[AAPointerInfo] PHI operand pointer offset mismatch "
1714 << *CurPtr <<
" in " << *
PHI <<
"\n");
1733 if (!handleAccess(
A, *LoadI,
nullptr, AK,
1734 OffsetInfoMap[CurPtr].Offsets,
Changed,
1740 return II->isAssumeLikeIntrinsic();
1751 }
while (FromI && FromI != ToI);
1756 auto IsValidAssume = [&](IntrinsicInst &IntrI) {
1757 if (IntrI.getIntrinsicID() != Intrinsic::assume)
1760 if (IntrI.getParent() == BB) {
1761 if (IsImpactedInRange(LoadI->getNextNode(), &IntrI))
1767 if ((*PredIt) != BB)
1772 if (SuccBB == IntrBB)
1778 if (IsImpactedInRange(LoadI->getNextNode(), BB->
getTerminator()))
1780 if (IsImpactedInRange(&IntrBB->
front(), &IntrI))
1786 std::pair<Value *, IntrinsicInst *> Assumption;
1787 for (
const Use &LoadU : LoadI->uses()) {
1789 if (!CmpI->isEquality() || !CmpI->isTrueWhenEqual())
1791 for (
const Use &CmpU : CmpI->uses()) {
1793 if (!IsValidAssume(*IntrI))
1795 int Idx = CmpI->getOperandUse(0) == LoadU;
1796 Assumption = {CmpI->getOperand(Idx), IntrI};
1801 if (Assumption.first)
1806 if (!Assumption.first || !Assumption.second)
1810 << *Assumption.second <<
": " << *LoadI
1811 <<
" == " << *Assumption.first <<
"\n");
1812 bool UsedAssumedInformation =
false;
1813 std::optional<Value *> Content =
nullptr;
1814 if (Assumption.first)
1816 A.getAssumedSimplified(*Assumption.first, *
this,
1818 return handleAccess(
1819 A, *Assumption.second, Content, AccessKind::AK_ASSUMPTION,
1820 OffsetInfoMap[CurPtr].Offsets,
Changed, *LoadI->getType());
1825 for (
auto *OtherOp : OtherOps) {
1826 if (OtherOp == CurPtr) {
1829 <<
"[AAPointerInfo] Escaping use in store like instruction " <<
I
1841 bool UsedAssumedInformation =
false;
1842 std::optional<Value *> Content =
nullptr;
1844 Content =
A.getAssumedSimplified(
1846 return handleAccess(
A,
I, Content, AK, OffsetInfoMap[CurPtr].Offsets,
1851 return HandleStoreLike(*StoreI, StoreI->getValueOperand(),
1852 *StoreI->getValueOperand()->getType(),
1853 {StoreI->getValueOperand()}, AccessKind::AK_W);
1855 return HandleStoreLike(*RMWI,
nullptr, *RMWI->getValOperand()->getType(),
1856 {RMWI->getValOperand()}, AccessKind::AK_RW);
1858 return HandleStoreLike(
1859 *CXI,
nullptr, *CXI->getNewValOperand()->getType(),
1860 {CXI->getCompareOperand(), CXI->getNewValOperand()},
1867 A.getInfoCache().getTargetLibraryInfoForFunction(*CB->
getFunction());
1872 const auto *CSArgPI =
A.getAAFor<AAPointerInfo>(
1878 Changed = translateAndAddState(
A, *CSArgPI, OffsetInfoMap[CurPtr], *CB,
1881 if (!CSArgPI->reachesReturn())
1882 return isValidState();
1885 if (!Callee ||
Callee->arg_size() <= ArgNo)
1887 bool UsedAssumedInformation =
false;
1888 auto ReturnedValue =
A.getAssumedSimplified(
1893 auto *Arg =
Callee->getArg(ArgNo);
1894 if (ReturnedArg && Arg != ReturnedArg)
1896 bool IsRetMustAcc = IsArgMustAcc && (ReturnedArg == Arg);
1897 const auto *CSRetPI =
A.getAAFor<AAPointerInfo>(
1901 OffsetInfo OI = OffsetInfoMap[CurPtr];
1902 CSArgPI->addReturnedOffsetsTo(OI);
1904 translateAndAddState(
A, *CSRetPI, OI, *CB, IsRetMustAcc) |
Changed;
1905 return isValidState();
1907 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] Call user not handled " << *CB
1912 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] User not handled " << *Usr <<
"\n");
1915 auto EquivalentUseCB = [&](
const Use &OldU,
const Use &NewU) {
1916 assert(OffsetInfoMap.
count(OldU) &&
"Old use should be known already!");
1917 assert(!OffsetInfoMap[OldU].isUnassigned() &&
"Old use should be assinged");
1918 if (OffsetInfoMap.
count(NewU)) {
1920 if (!(OffsetInfoMap[NewU] == OffsetInfoMap[OldU])) {
1921 dbgs() <<
"[AAPointerInfo] Equivalent use callback failed: "
1922 << OffsetInfoMap[NewU] <<
" vs " << OffsetInfoMap[OldU]
1926 return OffsetInfoMap[NewU] == OffsetInfoMap[OldU];
1929 return HandlePassthroughUser(NewU.get(), OldU.
get(), Unused);
1931 if (!
A.checkForAllUses(UsePred, *
this, AssociatedValue,
1933 true, EquivalentUseCB)) {
1934 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] Check for all uses failed, abort!\n");
1935 return indicatePessimisticFixpoint();
1939 dbgs() <<
"Accesses by bin after update:\n";
1946struct AAPointerInfoReturned final : AAPointerInfoImpl {
1947 AAPointerInfoReturned(
const IRPosition &IRP, Attributor &
A)
1948 : AAPointerInfoImpl(IRP,
A) {}
1952 return indicatePessimisticFixpoint();
1956 void trackStatistics()
const override {
1957 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1961struct AAPointerInfoArgument final : AAPointerInfoFloating {
1962 AAPointerInfoArgument(
const IRPosition &IRP, Attributor &
A)
1963 : AAPointerInfoFloating(IRP,
A) {}
1966 void trackStatistics()
const override {
1967 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
1971struct AAPointerInfoCallSiteArgument final : AAPointerInfoFloating {
1972 AAPointerInfoCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
1973 : AAPointerInfoFloating(IRP,
A) {}
1977 using namespace AA::PointerInfo;
1983 if (
auto Length =
MI->getLengthInBytes())
1984 LengthVal =
Length->getSExtValue();
1985 unsigned ArgNo = getIRPosition().getCallSiteArgNo();
1988 LLVM_DEBUG(
dbgs() <<
"[AAPointerInfo] Unhandled memory intrinsic "
1990 return indicatePessimisticFixpoint();
1993 ArgNo == 0 ? AccessKind::AK_MUST_WRITE : AccessKind::AK_MUST_READ;
1995 Changed | addAccess(
A, {0, LengthVal}, *
MI,
nullptr,
Kind,
nullptr);
1998 dbgs() <<
"Accesses by bin after update:\n";
2009 Argument *Arg = getAssociatedArgument();
2013 A.getAAFor<AAPointerInfo>(*
this, ArgPos, DepClassTy::REQUIRED);
2014 if (ArgAA && ArgAA->getState().isValidState())
2015 return translateAndAddStateFromCallee(
A, *ArgAA,
2018 return indicatePessimisticFixpoint();
2021 bool IsKnownNoCapture;
2023 A,
this, getIRPosition(), DepClassTy::OPTIONAL, IsKnownNoCapture))
2024 return indicatePessimisticFixpoint();
2026 bool IsKnown =
false;
2028 return ChangeStatus::UNCHANGED;
2031 ReadOnly ? AccessKind::AK_MAY_READ : AccessKind::AK_MAY_READ_WRITE;
2037 void trackStatistics()
const override {
2038 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
2042struct AAPointerInfoCallSiteReturned final : AAPointerInfoFloating {
2043 AAPointerInfoCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
2044 : AAPointerInfoFloating(IRP,
A) {}
2047 void trackStatistics()
const override {
2048 AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
2056struct AANoUnwindImpl : AANoUnwind {
2057 AANoUnwindImpl(
const IRPosition &IRP, Attributor &
A) : AANoUnwind(IRP,
A) {}
2063 A,
nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
2067 const std::string getAsStr(Attributor *
A)
const override {
2068 return getAssumed() ?
"nounwind" :
"may-unwind";
2074 (unsigned)Instruction::Invoke, (
unsigned)Instruction::CallBr,
2075 (unsigned)Instruction::Call, (
unsigned)Instruction::CleanupRet,
2076 (unsigned)Instruction::CatchSwitch, (
unsigned)Instruction::Resume};
2079 if (!
I.mayThrow(
true))
2083 bool IsKnownNoUnwind;
2091 bool UsedAssumedInformation =
false;
2092 if (!
A.checkForAllInstructions(CheckForNoUnwind, *
this, Opcodes,
2093 UsedAssumedInformation))
2094 return indicatePessimisticFixpoint();
2096 return ChangeStatus::UNCHANGED;
2100struct AANoUnwindFunction final :
public AANoUnwindImpl {
2101 AANoUnwindFunction(
const IRPosition &IRP, Attributor &
A)
2102 : AANoUnwindImpl(IRP,
A) {}
2109struct AANoUnwindCallSite final
2110 : AACalleeToCallSite<AANoUnwind, AANoUnwindImpl> {
2111 AANoUnwindCallSite(
const IRPosition &IRP, Attributor &
A)
2112 : AACalleeToCallSite<AANoUnwind, AANoUnwindImpl>(IRP,
A) {}
2123 case Intrinsic::nvvm_barrier_cta_sync_aligned_all:
2124 case Intrinsic::nvvm_barrier_cta_sync_aligned_count:
2125 case Intrinsic::nvvm_barrier_cta_red_and_aligned_all:
2126 case Intrinsic::nvvm_barrier_cta_red_and_aligned_count:
2127 case Intrinsic::nvvm_barrier_cta_red_or_aligned_all:
2128 case Intrinsic::nvvm_barrier_cta_red_or_aligned_count:
2129 case Intrinsic::nvvm_barrier_cta_red_popc_aligned_all:
2130 case Intrinsic::nvvm_barrier_cta_red_popc_aligned_count:
2132 case Intrinsic::amdgcn_s_barrier:
2133 if (ExecutedAligned)
2156 switch (
I->getOpcode()) {
2157 case Instruction::AtomicRMW:
2160 case Instruction::Store:
2163 case Instruction::Load:
2168 "New atomic operations need to be known in the attributor.");
2187 const std::string getAsStr(Attributor *
A)
const override {
2188 return getAssumed() ?
"nosync" :
"may-sync";
2204 if (
I.mayReadOrWriteMemory())
2218 bool UsedAssumedInformation =
false;
2219 if (!
A.checkForAllReadWriteInstructions(CheckRWInstForNoSync, *
this,
2220 UsedAssumedInformation) ||
2221 !
A.checkForAllCallLikeInstructions(CheckForNoSync, *
this,
2222 UsedAssumedInformation))
2223 return indicatePessimisticFixpoint();
2228struct AANoSyncFunction final :
public AANoSyncImpl {
2229 AANoSyncFunction(
const IRPosition &IRP, Attributor &
A)
2230 : AANoSyncImpl(IRP,
A) {}
2237struct AANoSyncCallSite final : AACalleeToCallSite<AANoSync, AANoSyncImpl> {
2238 AANoSyncCallSite(
const IRPosition &IRP, Attributor &
A)
2239 : AACalleeToCallSite<AANoSync, AANoSyncImpl>(IRP,
A) {}
2249struct AANoFreeImpl :
public AANoFree {
2250 AANoFreeImpl(
const IRPosition &IRP, Attributor &
A) : AANoFree(IRP,
A) {}
2256 DepClassTy::NONE, IsKnown));
2274 bool UsedAssumedInformation =
false;
2275 if (!
A.checkForAllReadWriteInstructions(CheckForNoFree, *
this,
2276 UsedAssumedInformation) ||
2277 !
A.checkForAllCallLikeInstructions(CheckForNoFree, *
this,
2278 UsedAssumedInformation))
2279 return indicatePessimisticFixpoint();
2281 return ChangeStatus::UNCHANGED;
2285 const std::string getAsStr(Attributor *
A)
const override {
2286 return getAssumed() ?
"nofree" :
"may-free";
2290struct AANoFreeFunction final :
public AANoFreeImpl {
2291 AANoFreeFunction(
const IRPosition &IRP, Attributor &
A)
2292 : AANoFreeImpl(IRP,
A) {}
2299struct AANoFreeCallSite final : AACalleeToCallSite<AANoFree, AANoFreeImpl> {
2300 AANoFreeCallSite(
const IRPosition &IRP, Attributor &
A)
2301 : AACalleeToCallSite<AANoFree, AANoFreeImpl>(IRP,
A) {}
2308struct AANoFreeFloating : AANoFreeImpl {
2309 AANoFreeFloating(
const IRPosition &IRP, Attributor &
A)
2310 : AANoFreeImpl(IRP,
A) {}
2317 const IRPosition &IRP = getIRPosition();
2322 DepClassTy::OPTIONAL, IsKnown))
2323 return ChangeStatus::UNCHANGED;
2325 Value &AssociatedValue = getIRPosition().getAssociatedValue();
2326 auto Pred = [&](
const Use &
U,
bool &Follow) ->
bool {
2341 DepClassTy::REQUIRED, IsKnown))
2344 const AANoCapture *NoCaptureAA =
nullptr;
2347 DepClassTy::REQUIRED, IsKnown,
2348 false, &NoCaptureAA)) {
2373 if (!
A.checkForAllUses(Pred, *
this, AssociatedValue))
2374 return indicatePessimisticFixpoint();
2376 return ChangeStatus::UNCHANGED;
2381struct AANoFreeArgument final : AANoFreeFloating {
2382 AANoFreeArgument(
const IRPosition &IRP, Attributor &
A)
2383 : AANoFreeFloating(IRP,
A) {}
2390struct AANoFreeCallSiteArgument final : AANoFreeFloating {
2391 AANoFreeCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
2392 : AANoFreeFloating(IRP,
A) {}
2400 Argument *Arg = getAssociatedArgument();
2402 return indicatePessimisticFixpoint();
2406 DepClassTy::REQUIRED, IsKnown))
2407 return ChangeStatus::UNCHANGED;
2408 return indicatePessimisticFixpoint();
2416struct AANoFreeReturned final : AANoFreeFloating {
2417 AANoFreeReturned(
const IRPosition &IRP, Attributor &
A)
2418 : AANoFreeFloating(IRP,
A) {
2433 void trackStatistics()
const override {}
2437struct AANoFreeCallSiteReturned final : AANoFreeFloating {
2438 AANoFreeCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
2439 : AANoFreeFloating(IRP,
A) {}
2442 return ChangeStatus::UNCHANGED;
2453 bool IgnoreSubsumingPositions) {
2455 AttrKinds.
push_back(Attribute::NonNull);
2458 AttrKinds.
push_back(Attribute::Dereferenceable);
2459 if (
A.hasAttr(IRP, AttrKinds, IgnoreSubsumingPositions, Attribute::NonNull))
2466 if (!Fn->isDeclaration()) {
2476 bool UsedAssumedInformation =
false;
2477 if (!
A.checkForAllInstructions(
2479 Worklist.push_back({*cast<ReturnInst>(I).getReturnValue(), &I});
2483 UsedAssumedInformation,
false,
true))
2495 Attribute::NonNull)});
2500static int64_t getKnownNonNullAndDerefBytesForUse(
2501 Attributor &
A,
const AbstractAttribute &QueryingAA,
Value &AssociatedValue,
2502 const Use *U,
const Instruction *
I,
bool &IsNonNull,
bool &TrackUse) {
2505 const Value *UseV =
U->get();
2526 const DataLayout &
DL =
A.getInfoCache().getDL();
2530 U, {Attribute::NonNull, Attribute::Dereferenceable})) {
2547 bool IsKnownNonNull;
2550 IsNonNull |= IsKnownNonNull;
2553 return DerefAA ? DerefAA->getKnownDereferenceableBytes() : 0;
2557 if (!Loc || Loc->Ptr != UseV || !Loc->Size.isPrecise() ||
2558 Loc->Size.isScalable() ||
I->isVolatile())
2564 if (
Base &&
Base == &AssociatedValue) {
2565 int64_t DerefBytes = Loc->Size.getValue() +
Offset;
2567 return std::max(int64_t(0), DerefBytes);
2574 int64_t DerefBytes = Loc->Size.getValue();
2576 return std::max(int64_t(0), DerefBytes);
2582struct AANonNullImpl : AANonNull {
2583 AANonNullImpl(
const IRPosition &IRP, Attributor &
A) : AANonNull(IRP,
A) {}
2587 Value &
V = *getAssociatedValue().stripPointerCasts();
2589 indicatePessimisticFixpoint();
2593 if (Instruction *CtxI = getCtxI())
2594 followUsesInMBEC(*
this,
A, getState(), *CtxI);
2598 bool followUseInMBEC(Attributor &
A,
const Use *U,
const Instruction *
I,
2599 AANonNull::StateType &State) {
2600 bool IsNonNull =
false;
2601 bool TrackUse =
false;
2602 getKnownNonNullAndDerefBytesForUse(
A, *
this, getAssociatedValue(), U,
I,
2603 IsNonNull, TrackUse);
2604 State.setKnown(IsNonNull);
2609 const std::string getAsStr(Attributor *
A)
const override {
2610 return getAssumed() ?
"nonnull" :
"may-null";
2615struct AANonNullFloating :
public AANonNullImpl {
2616 AANonNullFloating(
const IRPosition &IRP, Attributor &
A)
2617 : AANonNullImpl(IRP,
A) {}
2621 auto CheckIRP = [&](
const IRPosition &IRP) {
2622 bool IsKnownNonNull;
2624 A, *
this, IRP, DepClassTy::OPTIONAL, IsKnownNonNull);
2628 bool UsedAssumedInformation =
false;
2629 Value *AssociatedValue = &getAssociatedValue();
2631 if (!
A.getAssumedSimplifiedValues(getIRPosition(), *
this,
Values,
2636 Values.size() != 1 ||
Values.front().getValue() != AssociatedValue;
2642 return AA::hasAssumedIRAttr<Attribute::NonNull>(
2643 A, this, IRPosition::value(*Op), DepClassTy::OPTIONAL,
2646 return ChangeStatus::UNCHANGED;
2650 DepClassTy::OPTIONAL, IsKnown) &&
2653 DepClassTy::OPTIONAL, IsKnown))
2654 return ChangeStatus::UNCHANGED;
2661 if (AVIRP == getIRPosition() || !CheckIRP(AVIRP))
2662 return indicatePessimisticFixpoint();
2663 return ChangeStatus::UNCHANGED;
2666 for (
const auto &VAC :
Values)
2668 return indicatePessimisticFixpoint();
2670 return ChangeStatus::UNCHANGED;
2678struct AANonNullReturned final
2679 : AAReturnedFromReturnedValues<AANonNull, AANonNull, AANonNull::StateType,
2680 false, AANonNull::IRAttributeKind, false> {
2681 AANonNullReturned(
const IRPosition &IRP, Attributor &
A)
2682 : AAReturnedFromReturnedValues<AANonNull, AANonNull, AANonNull::StateType,
2687 const std::string getAsStr(Attributor *
A)
const override {
2688 return getAssumed() ?
"nonnull" :
"may-null";
2696struct AANonNullArgument final
2697 : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl> {
2698 AANonNullArgument(
const IRPosition &IRP, Attributor &
A)
2699 : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl>(IRP,
A) {}
2705struct AANonNullCallSiteArgument final : AANonNullFloating {
2706 AANonNullCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
2707 : AANonNullFloating(IRP,
A) {}
2714struct AANonNullCallSiteReturned final
2715 : AACalleeToCallSite<AANonNull, AANonNullImpl> {
2716 AANonNullCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
2717 : AACalleeToCallSite<AANonNull, AANonNullImpl>(IRP,
A) {}
2726struct AAMustProgressImpl :
public AAMustProgress {
2727 AAMustProgressImpl(
const IRPosition &IRP, Attributor &
A)
2728 : AAMustProgress(IRP,
A) {}
2734 A,
nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
2739 const std::string getAsStr(Attributor *
A)
const override {
2740 return getAssumed() ?
"mustprogress" :
"may-not-progress";
2744struct AAMustProgressFunction final : AAMustProgressImpl {
2745 AAMustProgressFunction(
const IRPosition &IRP, Attributor &
A)
2746 : AAMustProgressImpl(IRP,
A) {}
2752 A,
this, getIRPosition(), DepClassTy::OPTIONAL, IsKnown)) {
2754 return indicateOptimisticFixpoint();
2755 return ChangeStatus::UNCHANGED;
2758 auto CheckForMustProgress = [&](AbstractCallSite ACS) {
2760 bool IsKnownMustProgress;
2762 A,
this, IPos, DepClassTy::REQUIRED, IsKnownMustProgress,
2766 bool AllCallSitesKnown =
true;
2767 if (!
A.checkForAllCallSites(CheckForMustProgress, *
this,
2770 return indicatePessimisticFixpoint();
2772 return ChangeStatus::UNCHANGED;
2776 void trackStatistics()
const override {
2782struct AAMustProgressCallSite final : AAMustProgressImpl {
2783 AAMustProgressCallSite(
const IRPosition &IRP, Attributor &
A)
2784 : AAMustProgressImpl(IRP,
A) {}
2793 bool IsKnownMustProgress;
2795 A,
this, FnPos, DepClassTy::REQUIRED, IsKnownMustProgress))
2796 return indicatePessimisticFixpoint();
2797 return ChangeStatus::UNCHANGED;
2801 void trackStatistics()
const override {
2810struct AANoRecurseImpl :
public AANoRecurse {
2811 AANoRecurseImpl(
const IRPosition &IRP, Attributor &
A) : AANoRecurse(IRP,
A) {}
2817 A,
nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
2822 const std::string getAsStr(Attributor *
A)
const override {
2823 return getAssumed() ?
"norecurse" :
"may-recurse";
2827struct AANoRecurseFunction final : AANoRecurseImpl {
2828 AANoRecurseFunction(
const IRPosition &IRP, Attributor &
A)
2829 : AANoRecurseImpl(IRP,
A) {}
2835 auto CallSitePred = [&](AbstractCallSite ACS) {
2836 bool IsKnownNoRecurse;
2840 DepClassTy::NONE, IsKnownNoRecurse))
2842 return IsKnownNoRecurse;
2844 bool UsedAssumedInformation =
false;
2845 if (
A.checkForAllCallSites(CallSitePred, *
this,
true,
2846 UsedAssumedInformation)) {
2852 if (!UsedAssumedInformation)
2853 indicateOptimisticFixpoint();
2854 return ChangeStatus::UNCHANGED;
2857 const AAInterFnReachability *EdgeReachability =
2858 A.getAAFor<AAInterFnReachability>(*
this, getIRPosition(),
2859 DepClassTy::REQUIRED);
2860 if (EdgeReachability && EdgeReachability->
canReach(
A, *getAnchorScope()))
2861 return indicatePessimisticFixpoint();
2862 return ChangeStatus::UNCHANGED;
2869struct AANoRecurseCallSite final
2870 : AACalleeToCallSite<AANoRecurse, AANoRecurseImpl> {
2871 AANoRecurseCallSite(
const IRPosition &IRP, Attributor &
A)
2872 : AACalleeToCallSite<AANoRecurse, AANoRecurseImpl>(IRP,
A) {}
2882struct AANonConvergentImpl :
public AANonConvergent {
2883 AANonConvergentImpl(
const IRPosition &IRP, Attributor &
A)
2884 : AANonConvergent(IRP,
A) {}
2887 const std::string getAsStr(Attributor *
A)
const override {
2888 return getAssumed() ?
"non-convergent" :
"may-be-convergent";
2892struct AANonConvergentFunction final : AANonConvergentImpl {
2893 AANonConvergentFunction(
const IRPosition &IRP, Attributor &
A)
2894 : AANonConvergentImpl(IRP,
A) {}
2900 auto CalleeIsNotConvergent = [&](
Instruction &Inst) {
2903 if (!Callee ||
Callee->isIntrinsic()) {
2906 if (
Callee->isDeclaration()) {
2907 return !
Callee->hasFnAttribute(Attribute::Convergent);
2909 const auto *ConvergentAA =
A.getAAFor<AANonConvergent>(
2911 return ConvergentAA && ConvergentAA->isAssumedNotConvergent();
2914 bool UsedAssumedInformation =
false;
2915 if (!
A.checkForAllCallLikeInstructions(CalleeIsNotConvergent, *
this,
2916 UsedAssumedInformation)) {
2917 return indicatePessimisticFixpoint();
2919 return ChangeStatus::UNCHANGED;
2923 if (isKnownNotConvergent() &&
2924 A.hasAttr(getIRPosition(), Attribute::Convergent)) {
2925 A.removeAttrs(getIRPosition(), {Attribute::Convergent});
2926 return ChangeStatus::CHANGED;
2928 return ChangeStatus::UNCHANGED;
2938struct AAUndefinedBehaviorImpl :
public AAUndefinedBehavior {
2939 AAUndefinedBehaviorImpl(
const IRPosition &IRP, Attributor &
A)
2940 : AAUndefinedBehavior(IRP,
A) {}
2946 UndefBranchCondition,
2948 NullReturnViolatesNonNull,
2950 NullArgViolatesNonNull,
2954 std::optional<unsigned> ArgNo;
2956 UBInfo(Kind K) :
K(
K), ArgNo(std::nullopt) {}
2958 UBInfo(Kind K, std::optional<unsigned> ArgNo) :
K(
K), ArgNo(ArgNo) {}
2964 const size_t UBPrevSize = KnownUBInsts.size();
2965 const size_t NoUBPrevSize = AssumedNoUBInsts.size();
2973 if (AssumedNoUBInsts.count(&
I) || KnownUBInsts.count(&
I))
2982 "Expected pointer operand of memory accessing instruction");
2986 std::optional<Value *> SimplifiedPtrOp =
2987 stopOnUndefOrAssumed(
A, PtrOp, &
I, UBInfo::UndefPtrAccess);
2988 if (!SimplifiedPtrOp || !*SimplifiedPtrOp)
2990 const Value *PtrOpVal = *SimplifiedPtrOp;
2996 AssumedNoUBInsts.insert(&
I);
3008 AssumedNoUBInsts.insert(&
I);
3010 KnownUBInsts.try_emplace(&
I, UBInfo::NullPtrAccess);
3019 if (AssumedNoUBInsts.count(&
I) || KnownUBInsts.count(&
I))
3027 std::optional<Value *> SimplifiedCond = stopOnUndefOrAssumed(
3028 A, BrInst->getCondition(), BrInst, UBInfo::UndefBranchCondition);
3029 if (!SimplifiedCond || !*SimplifiedCond)
3031 AssumedNoUBInsts.insert(&
I);
3039 if (AssumedNoUBInsts.count(&
I) || KnownUBInsts.count(&
I))
3048 for (
unsigned idx = 0; idx < CB.
arg_size(); idx++) {
3054 if (idx >=
Callee->arg_size())
3066 bool IsKnownNoUndef;
3068 A,
this, CalleeArgumentIRP, DepClassTy::NONE, IsKnownNoUndef);
3069 if (!IsKnownNoUndef)
3071 bool UsedAssumedInformation =
false;
3072 std::optional<Value *> SimplifiedVal =
3075 if (UsedAssumedInformation)
3077 if (SimplifiedVal && !*SimplifiedVal)
3080 KnownUBInsts.try_emplace(&
I, UBInfo(UBInfo::UndefCallArgument, idx));
3086 bool IsKnownNonNull;
3088 A,
this, CalleeArgumentIRP, DepClassTy::NONE, IsKnownNonNull);
3090 KnownUBInsts.try_emplace(&
I,
3091 UBInfo(UBInfo::NullArgViolatesNonNull, idx));
3100 std::optional<Value *> SimplifiedRetValue = stopOnUndefOrAssumed(
3101 A, RI.getReturnValue(), &
I, UBInfo::UndefReturnValue);
3102 if (!SimplifiedRetValue || !*SimplifiedRetValue)
3120 bool IsKnownNonNull;
3125 KnownUBInsts.try_emplace(&
I, UBInfo::NullReturnViolatesNonNull);
3131 bool UsedAssumedInformation =
false;
3132 A.checkForAllInstructions(InspectMemAccessInstForUB, *
this,
3133 {Instruction::Load, Instruction::Store,
3134 Instruction::AtomicCmpXchg,
3135 Instruction::AtomicRMW},
3136 UsedAssumedInformation,
3138 A.checkForAllInstructions(InspectBrInstForUB, *
this, {Instruction::CondBr},
3139 UsedAssumedInformation,
3141 A.checkForAllCallLikeInstructions(InspectCallSiteForUB, *
this,
3142 UsedAssumedInformation);
3146 if (!getAnchorScope()->getReturnType()->isVoidTy()) {
3148 if (!
A.isAssumedDead(ReturnIRP,
this,
nullptr, UsedAssumedInformation)) {
3149 bool IsKnownNoUndef;
3151 A,
this, ReturnIRP, DepClassTy::NONE, IsKnownNoUndef);
3153 A.checkForAllInstructions(InspectReturnInstForUB, *
this,
3154 {Instruction::Ret}, UsedAssumedInformation,
3159 if (NoUBPrevSize != AssumedNoUBInsts.size() ||
3160 UBPrevSize != KnownUBInsts.size())
3161 return ChangeStatus::CHANGED;
3162 return ChangeStatus::UNCHANGED;
3165 bool isKnownToCauseUB(Instruction *
I)
const override {
3166 return KnownUBInsts.count(
I);
3169 bool isAssumedToCauseUB(Instruction *
I)
const override {
3176 switch (
I->getOpcode()) {
3177 case Instruction::Load:
3178 case Instruction::Store:
3179 case Instruction::AtomicCmpXchg:
3180 case Instruction::AtomicRMW:
3181 case Instruction::CondBr:
3182 return !AssumedNoUBInsts.count(
I);
3191 static void emitUBRemark(Attributor &
A, Instruction *
I,
const UBInfo &Info) {
3192 auto Remark = [&](OptimizationRemark
OR) {
3194 case UBInfo::NullPtrAccess:
3195 case UBInfo::UndefPtrAccess: {
3196 return OR <<
"Memory access through a pointer known to be "
3199 <<
" is undefined behavior; replacing with 'unreachable'.";
3201 case UBInfo::UndefBranchCondition:
3202 return OR <<
"Branch condition known to be "
3204 <<
" is undefined behavior; replacing with 'unreachable'.";
3205 case UBInfo::UndefReturnValue:
3206 case UBInfo::NullReturnViolatesNonNull:
3207 return OR <<
"Value returned known to be "
3210 <<
" is undefined behavior; replacing with 'unreachable'.";
3211 case UBInfo::UndefCallArgument:
3212 case UBInfo::NullArgViolatesNonNull: {
3213 bool IsUndef =
Info.K == UBInfo::UndefCallArgument;
3216 <<
" passed to parameter of ";
3221 return OR <<
" known to be "
3222 <<
ore::NV(
"Argument", IsUndef ?
"undef" :
"null")
3223 <<
" is undefined behavior; replacing with 'unreachable'.";
3228 A.emitRemark<OptimizationRemark>(
I,
"UndefinedBehavior",
Remark);
3232 if (KnownUBInsts.empty())
3233 return ChangeStatus::UNCHANGED;
3234 for (
const auto &[
I, Info] : KnownUBInsts) {
3235 emitUBRemark(
A,
I, Info);
3236 A.changeToUnreachableAfterManifest(
I);
3238 return ChangeStatus::CHANGED;
3242 const std::string getAsStr(Attributor *
A)
const override {
3243 return getAssumed() ?
"undefined-behavior" :
"no-ub";
3272 MapVector<Instruction *, UBInfo> KnownUBInsts;
3276 SmallPtrSet<Instruction *, 8> AssumedNoUBInsts;
3287 std::optional<Value *> stopOnUndefOrAssumed(Attributor &
A,
Value *V,
3288 Instruction *
I, UBInfo::Kind K) {
3289 bool UsedAssumedInformation =
false;
3290 std::optional<Value *> SimplifiedV =
3293 if (!UsedAssumedInformation) {
3298 KnownUBInsts.try_emplace(
I, K);
3299 return std::nullopt;
3306 KnownUBInsts.try_emplace(
I, K);
3307 return std::nullopt;
3313struct AAUndefinedBehaviorFunction final : AAUndefinedBehaviorImpl {
3314 AAUndefinedBehaviorFunction(
const IRPosition &IRP, Attributor &
A)
3315 : AAUndefinedBehaviorImpl(IRP,
A) {}
3318 void trackStatistics()
const override {
3319 STATS_DECL(UndefinedBehaviorInstruction, Instruction,
3320 "Number of instructions known to have UB");
3322 KnownUBInsts.size();
3333static bool mayContainUnboundedCycle(
Function &
F, Attributor &
A) {
3334 ScalarEvolution *SE =
3335 A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(
F);
3336 LoopInfo *LI =
A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(
F);
3342 for (scc_iterator<Function *> SCCI =
scc_begin(&
F); !SCCI.isAtEnd(); ++SCCI)
3343 if (SCCI.hasCycle())
3353 for (
auto *L : LI->getLoopsInPreorder()) {
3360struct AAWillReturnImpl :
public AAWillReturn {
3361 AAWillReturnImpl(
const IRPosition &IRP, Attributor &
A)
3362 : AAWillReturn(IRP,
A) {}
3368 A,
nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
3373 bool isImpliedByMustprogressAndReadonly(Attributor &
A,
bool KnownOnly) {
3374 if (!
A.hasAttr(getIRPosition(), {Attribute::MustProgress}))
3379 return IsKnown || !KnownOnly;
3385 if (isImpliedByMustprogressAndReadonly(
A,
false))
3386 return ChangeStatus::UNCHANGED;
3392 A,
this, IPos, DepClassTy::REQUIRED, IsKnown)) {
3398 bool IsKnownNoRecurse;
3400 A,
this, IPos, DepClassTy::REQUIRED, IsKnownNoRecurse);
3403 bool UsedAssumedInformation =
false;
3404 if (!
A.checkForAllCallLikeInstructions(CheckForWillReturn, *
this,
3405 UsedAssumedInformation))
3406 return indicatePessimisticFixpoint();
3410 return !
I.isVolatile();
3412 if (!
A.checkForAllInstructions(CheckForVolatile, *
this,
3413 {Instruction::Load, Instruction::Store,
3414 Instruction::AtomicCmpXchg,
3415 Instruction::AtomicRMW},
3416 UsedAssumedInformation))
3417 return indicatePessimisticFixpoint();
3419 return ChangeStatus::UNCHANGED;
3423 const std::string getAsStr(Attributor *
A)
const override {
3424 return getAssumed() ?
"willreturn" :
"may-noreturn";
3428struct AAWillReturnFunction final : AAWillReturnImpl {
3429 AAWillReturnFunction(
const IRPosition &IRP, Attributor &
A)
3430 : AAWillReturnImpl(IRP,
A) {}
3434 AAWillReturnImpl::initialize(
A);
3437 assert(
F &&
"Did expect an anchor function");
3438 if (
F->isDeclaration() || mayContainUnboundedCycle(*
F,
A))
3439 indicatePessimisticFixpoint();
3447struct AAWillReturnCallSite final
3448 : AACalleeToCallSite<AAWillReturn, AAWillReturnImpl> {
3449 AAWillReturnCallSite(
const IRPosition &IRP, Attributor &
A)
3450 : AACalleeToCallSite<AAWillReturn, AAWillReturnImpl>(IRP,
A) {}
3454 if (isImpliedByMustprogressAndReadonly(
A,
false))
3455 return ChangeStatus::UNCHANGED;
3457 return AACalleeToCallSite::updateImpl(
A);
3479 const ToTy *
To =
nullptr;
3506 if (!ES || ES->
empty()) {
3507 ExclusionSet = nullptr;
3508 }
else if (MakeUnique) {
3509 ExclusionSet =
A.getInfoCache().getOrCreateUniqueBlockExecutionSet(ES);
3527 if (!PairDMI::isEqual({LHS->From, LHS->To}, {RHS->From, RHS->To}))
3529 return InstSetDMI::isEqual(LHS->ExclusionSet, RHS->ExclusionSet);
3537template <
typename BaseTy,
typename ToTy>
3538struct CachedReachabilityAA :
public BaseTy {
3539 using RQITy = ReachabilityQueryInfo<ToTy>;
3541 CachedReachabilityAA(
const IRPosition &IRP, Attributor &
A) : BaseTy(IRP,
A) {}
3544 bool isQueryAA()
const override {
return true; }
3549 for (
unsigned u = 0, e = QueryVector.size(); u < e; ++u) {
3550 RQITy *RQI = QueryVector[
u];
3551 if (RQI->Result == RQITy::Reachable::No &&
3553 Changed = ChangeStatus::CHANGED;
3559 bool IsTemporaryRQI) = 0;
3561 bool rememberResult(Attributor &
A,
typename RQITy::Reachable Result,
3562 RQITy &RQI,
bool UsedExclusionSet,
bool IsTemporaryRQI) {
3567 QueryCache.erase(&RQI);
3573 if (Result == RQITy::Reachable::Yes || !UsedExclusionSet) {
3574 RQITy PlainRQI(RQI.From, RQI.To);
3575 if (!QueryCache.count(&PlainRQI)) {
3576 RQITy *RQIPtr =
new (
A.Allocator) RQITy(RQI.From, RQI.To);
3578 QueryVector.push_back(RQIPtr);
3579 QueryCache.insert(RQIPtr);
3584 if (IsTemporaryRQI && Result != RQITy::Reachable::Yes && UsedExclusionSet) {
3585 assert((!RQI.ExclusionSet || !RQI.ExclusionSet->empty()) &&
3586 "Did not expect empty set!");
3587 RQITy *RQIPtr =
new (
A.Allocator)
3588 RQITy(
A, *RQI.From, *RQI.To, RQI.ExclusionSet,
true);
3589 assert(RQIPtr->Result == RQITy::Reachable::No &&
"Already reachable?");
3591 assert(!QueryCache.count(RQIPtr));
3592 QueryVector.push_back(RQIPtr);
3593 QueryCache.insert(RQIPtr);
3596 if (Result == RQITy::Reachable::No && IsTemporaryRQI)
3597 A.registerForUpdate(*
this);
3598 return Result == RQITy::Reachable::Yes;
3601 const std::string getAsStr(Attributor *
A)
const override {
3603 return "#queries(" + std::to_string(QueryVector.size()) +
")";
3606 bool checkQueryCache(Attributor &
A, RQITy &StackRQI,
3607 typename RQITy::Reachable &Result) {
3608 if (!this->getState().isValidState()) {
3609 Result = RQITy::Reachable::Yes;
3615 if (StackRQI.ExclusionSet) {
3616 RQITy PlainRQI(StackRQI.From, StackRQI.To);
3617 auto It = QueryCache.find(&PlainRQI);
3618 if (It != QueryCache.end() && (*It)->Result == RQITy::Reachable::No) {
3619 Result = RQITy::Reachable::No;
3624 auto It = QueryCache.find(&StackRQI);
3625 if (It != QueryCache.end()) {
3632 QueryCache.insert(&StackRQI);
3638 DenseSet<RQITy *> QueryCache;
3641struct AAIntraFnReachabilityFunction final
3642 :
public CachedReachabilityAA<AAIntraFnReachability, Instruction> {
3643 using Base = CachedReachabilityAA<AAIntraFnReachability, Instruction>;
3644 AAIntraFnReachabilityFunction(
const IRPosition &IRP, Attributor &
A)
3646 DT =
A.getInfoCache().getAnalysisResultForFunction<DominatorTreeAnalysis>(
3650 bool isAssumedReachable(
3651 Attributor &
A,
const Instruction &From,
const Instruction &To,
3653 auto *NonConstThis =
const_cast<AAIntraFnReachabilityFunction *
>(
this);
3657 RQITy StackRQI(
A, From, To, ExclusionSet,
false);
3659 if (!NonConstThis->checkQueryCache(
A, StackRQI, Result))
3660 return NonConstThis->isReachableImpl(
A, StackRQI,
3662 return Result == RQITy::Reachable::Yes;
3669 A.getAAFor<AAIsDead>(*
this, getIRPosition(), DepClassTy::OPTIONAL);
3672 [&](
const auto &DeadEdge) {
3673 return LivenessAA->isEdgeDead(DeadEdge.first,
3677 return LivenessAA->isAssumedDead(BB);
3679 return ChangeStatus::UNCHANGED;
3683 return Base::updateImpl(
A);
3687 bool IsTemporaryRQI)
override {
3689 bool UsedExclusionSet =
false;
3694 while (IP && IP != &To) {
3695 if (ExclusionSet && IP != Origin && ExclusionSet->
count(IP)) {
3696 UsedExclusionSet =
true;
3704 const BasicBlock *FromBB = RQI.From->getParent();
3705 const BasicBlock *ToBB = RQI.To->getParent();
3707 "Not an intra-procedural query!");
3711 if (FromBB == ToBB &&
3712 WillReachInBlock(*RQI.From, *RQI.To, RQI.ExclusionSet))
3713 return rememberResult(
A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
3718 if (!WillReachInBlock(ToBB->
front(), *RQI.To, RQI.ExclusionSet))
3719 return rememberResult(
A, RQITy::Reachable::No, RQI, UsedExclusionSet,
3723 SmallPtrSet<const BasicBlock *, 16> ExclusionBlocks;
3724 if (RQI.ExclusionSet)
3725 for (
auto *
I : *RQI.ExclusionSet)
3726 if (
I->getFunction() == Fn)
3727 ExclusionBlocks.
insert(
I->getParent());
3730 if (ExclusionBlocks.
count(FromBB) &&
3733 return rememberResult(
A, RQITy::Reachable::No, RQI,
true, IsTemporaryRQI);
3736 A.getAAFor<AAIsDead>(*
this, getIRPosition(), DepClassTy::OPTIONAL);
3737 if (LivenessAA && LivenessAA->isAssumedDead(ToBB)) {
3738 DeadBlocks.insert(ToBB);
3739 return rememberResult(
A, RQITy::Reachable::No, RQI, UsedExclusionSet,
3743 SmallPtrSet<const BasicBlock *, 16> Visited;
3747 DenseSet<std::pair<const BasicBlock *, const BasicBlock *>> LocalDeadEdges;
3748 while (!Worklist.
empty()) {
3750 if (!Visited.
insert(BB).second)
3752 for (
const BasicBlock *SuccBB :
successors(BB)) {
3753 if (LivenessAA && LivenessAA->isEdgeDead(BB, SuccBB)) {
3754 LocalDeadEdges.
insert({BB, SuccBB});
3759 return rememberResult(
A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
3762 return rememberResult(
A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
3765 if (ExclusionBlocks.
count(SuccBB)) {
3766 UsedExclusionSet =
true;
3773 DeadEdges.insert_range(LocalDeadEdges);
3774 return rememberResult(
A, RQITy::Reachable::No, RQI, UsedExclusionSet,
3779 void trackStatistics()
const override {}
3784 DenseSet<const BasicBlock *> DeadBlocks;
3788 DenseSet<std::pair<const BasicBlock *, const BasicBlock *>> DeadEdges;
3791 const DominatorTree *DT =
nullptr;
3799 bool IgnoreSubsumingPositions) {
3800 assert(ImpliedAttributeKind == Attribute::NoAlias &&
3801 "Unexpected attribute kind");
3807 IgnoreSubsumingPositions =
true;
3818 if (
A.hasAttr(IRP, {Attribute::ByVal, Attribute::NoAlias},
3819 IgnoreSubsumingPositions, Attribute::NoAlias))
3829 "Noalias is a pointer attribute");
3832 const std::string getAsStr(
Attributor *
A)
const override {
3833 return getAssumed() ?
"noalias" :
"may-alias";
3838struct AANoAliasFloating final : AANoAliasImpl {
3839 AANoAliasFloating(
const IRPosition &IRP, Attributor &
A)
3840 : AANoAliasImpl(IRP,
A) {}
3845 return indicatePessimisticFixpoint();
3849 void trackStatistics()
const override {
3855struct AANoAliasArgument final
3856 : AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl> {
3857 using Base = AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl>;
3858 AANoAliasArgument(
const IRPosition &IRP, Attributor &
A) :
Base(IRP,
A) {}
3871 DepClassTy::OPTIONAL, IsKnownNoSycn))
3872 return Base::updateImpl(
A);
3877 return Base::updateImpl(
A);
3881 bool UsedAssumedInformation =
false;
3882 if (
A.checkForAllCallSites(
3883 [](AbstractCallSite ACS) { return !ACS.isCallbackCall(); }, *
this,
3884 true, UsedAssumedInformation))
3885 return Base::updateImpl(
A);
3893 return indicatePessimisticFixpoint();
3900struct AANoAliasCallSiteArgument final : AANoAliasImpl {
3901 AANoAliasCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
3902 : AANoAliasImpl(IRP,
A) {}
3906 bool mayAliasWithArgument(Attributor &
A, AAResults *&AAR,
3907 const AAMemoryBehavior &MemBehaviorAA,
3908 const CallBase &CB,
unsigned OtherArgNo) {
3910 if (this->getCalleeArgNo() == (
int)OtherArgNo)
3918 auto *CBArgMemBehaviorAA =
A.getAAFor<AAMemoryBehavior>(
3922 if (CBArgMemBehaviorAA && CBArgMemBehaviorAA->isAssumedReadNone()) {
3923 A.recordDependence(*CBArgMemBehaviorAA, *
this, DepClassTy::OPTIONAL);
3930 if (CBArgMemBehaviorAA && CBArgMemBehaviorAA->isAssumedReadOnly() &&
3932 A.recordDependence(MemBehaviorAA, *
this, DepClassTy::OPTIONAL);
3933 A.recordDependence(*CBArgMemBehaviorAA, *
this, DepClassTy::OPTIONAL);
3939 AAR =
A.getInfoCache().getAnalysisResultForFunction<AAManager>(
3943 bool IsAliasing = !AAR || !AAR->
isNoAlias(&getAssociatedValue(), ArgOp);
3945 "callsite arguments: "
3946 << getAssociatedValue() <<
" " << *ArgOp <<
" => "
3947 << (IsAliasing ?
"" :
"no-") <<
"alias \n");
3952 bool isKnownNoAliasDueToNoAliasPreservation(
3953 Attributor &
A, AAResults *&AAR,
const AAMemoryBehavior &MemBehaviorAA) {
3966 auto UsePred = [&](
const Use &
U,
bool &Follow) ->
bool {
3982 bool IsKnownNoCapture;
3985 DepClassTy::OPTIONAL, IsKnownNoCapture))
3991 A, *UserI, *getCtxI(), *
this,
nullptr,
3992 [ScopeFn](
const Function &Fn) {
return &Fn != ScopeFn; }))
4007 LLVM_DEBUG(
dbgs() <<
"[AANoAliasCSArg] Unknown user: " << *UserI <<
"\n");
4011 bool IsKnownNoCapture;
4012 const AANoCapture *NoCaptureAA =
nullptr;
4014 A,
this, VIRP, DepClassTy::NONE, IsKnownNoCapture,
false, &NoCaptureAA);
4015 if (!IsAssumedNoCapture &&
4017 if (!
A.checkForAllUses(UsePred, *
this, getAssociatedValue())) {
4019 dbgs() <<
"[AANoAliasCSArg] " << getAssociatedValue()
4020 <<
" cannot be noalias as it is potentially captured\n");
4025 A.recordDependence(*NoCaptureAA, *
this, DepClassTy::OPTIONAL);
4031 for (
unsigned OtherArgNo = 0; OtherArgNo < CB.
arg_size(); OtherArgNo++)
4032 if (mayAliasWithArgument(
A, AAR, MemBehaviorAA, CB, OtherArgNo))
4042 auto *MemBehaviorAA =
4043 A.getAAFor<AAMemoryBehavior>(*
this, getIRPosition(), DepClassTy::NONE);
4045 A.recordDependence(*MemBehaviorAA, *
this, DepClassTy::OPTIONAL);
4046 return ChangeStatus::UNCHANGED;
4049 bool IsKnownNoAlias;
4052 A,
this, VIRP, DepClassTy::REQUIRED, IsKnownNoAlias)) {
4054 <<
" is not no-alias at the definition\n");
4055 return indicatePessimisticFixpoint();
4058 AAResults *AAR =
nullptr;
4059 if (MemBehaviorAA &&
4060 isKnownNoAliasDueToNoAliasPreservation(
A, AAR, *MemBehaviorAA)) {
4062 dbgs() <<
"[AANoAlias] No-Alias deduced via no-alias preservation\n");
4063 return ChangeStatus::UNCHANGED;
4066 return indicatePessimisticFixpoint();
4074struct AANoAliasReturned final : AANoAliasImpl {
4075 AANoAliasReturned(
const IRPosition &IRP, Attributor &
A)
4076 : AANoAliasImpl(IRP,
A) {}
4081 auto CheckReturnValue = [&](
Value &RV) ->
bool {
4092 bool IsKnownNoAlias;
4094 A,
this, RVPos, DepClassTy::REQUIRED, IsKnownNoAlias))
4097 bool IsKnownNoCapture;
4098 const AANoCapture *NoCaptureAA =
nullptr;
4100 A,
this, RVPos, DepClassTy::REQUIRED, IsKnownNoCapture,
false,
4102 return IsAssumedNoCapture ||
4106 if (!
A.checkForAllReturnedValues(CheckReturnValue, *
this))
4107 return indicatePessimisticFixpoint();
4109 return ChangeStatus::UNCHANGED;
4117struct AANoAliasCallSiteReturned final
4118 : AACalleeToCallSite<AANoAlias, AANoAliasImpl> {
4119 AANoAliasCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
4120 : AACalleeToCallSite<AANoAlias, AANoAliasImpl>(IRP,
A) {}
4130struct AAIsDeadValueImpl :
public AAIsDead {
4131 AAIsDeadValueImpl(
const IRPosition &IRP, Attributor &
A) : AAIsDead(IRP,
A) {}
4134 bool isAssumedDead()
const override {
return isAssumed(IS_DEAD); }
4137 bool isKnownDead()
const override {
return isKnown(IS_DEAD); }
4140 bool isAssumedDead(
const BasicBlock *BB)
const override {
return false; }
4143 bool isKnownDead(
const BasicBlock *BB)
const override {
return false; }
4146 bool isAssumedDead(
const Instruction *
I)
const override {
4147 return I == getCtxI() && isAssumedDead();
4151 bool isKnownDead(
const Instruction *
I)
const override {
4152 return isAssumedDead(
I) && isKnownDead();
4156 const std::string getAsStr(Attributor *
A)
const override {
4157 return isAssumedDead() ?
"assumed-dead" :
"assumed-live";
4161 bool areAllUsesAssumedDead(Attributor &
A,
Value &V) {
4163 if (
V.getType()->isVoidTy() ||
V.use_empty())
4169 if (!
A.isRunOn(*
I->getFunction()))
4171 bool UsedAssumedInformation =
false;
4172 std::optional<Constant *>
C =
4173 A.getAssumedConstant(V, *
this, UsedAssumedInformation);
4178 auto UsePred = [&](
const Use &
U,
bool &Follow) {
return false; };
4183 return A.checkForAllUses(UsePred, *
this, V,
false,
4184 DepClassTy::REQUIRED,
4189 bool isAssumedSideEffectFree(Attributor &
A, Instruction *
I) {
4193 if (!
I->isTerminator() && !
I->mayHaveSideEffects())
4202 bool IsKnownNoUnwind;
4204 A,
this, CallIRP, DepClassTy::OPTIONAL, IsKnownNoUnwind))
4212struct AAIsDeadFloating :
public AAIsDeadValueImpl {
4213 AAIsDeadFloating(
const IRPosition &IRP, Attributor &
A)
4214 : AAIsDeadValueImpl(IRP,
A) {}
4218 AAIsDeadValueImpl::initialize(
A);
4221 indicatePessimisticFixpoint();
4226 if (!isAssumedSideEffectFree(
A,
I)) {
4228 indicatePessimisticFixpoint();
4230 removeAssumedBits(HAS_NO_EFFECT);
4234 bool isDeadFence(Attributor &
A, FenceInst &FI) {
4235 const auto *ExecDomainAA =
A.lookupAAFor<AAExecutionDomain>(
4237 if (!ExecDomainAA || !ExecDomainAA->isNoOpFence(FI))
4239 A.recordDependence(*ExecDomainAA, *
this, DepClassTy::OPTIONAL);
4243 bool isDeadStore(Attributor &
A, StoreInst &SI,
4244 SmallSetVector<Instruction *, 8> *AssumeOnlyInst =
nullptr) {
4246 if (
SI.isVolatile())
4252 bool UsedAssumedInformation =
false;
4253 if (!AssumeOnlyInst) {
4254 PotentialCopies.clear();
4256 UsedAssumedInformation)) {
4259 <<
"[AAIsDead] Could not determine potential copies of store!\n");
4263 LLVM_DEBUG(
dbgs() <<
"[AAIsDead] Store has " << PotentialCopies.size()
4264 <<
" potential copies.\n");
4266 InformationCache &InfoCache =
A.getInfoCache();
4269 UsedAssumedInformation))
4273 auto &UserI = cast<Instruction>(*U.getUser());
4274 if (InfoCache.isOnlyUsedByAssume(UserI)) {
4276 AssumeOnlyInst->insert(&UserI);
4279 return A.isAssumedDead(U,
this,
nullptr, UsedAssumedInformation);
4285 <<
" is assumed live!\n");
4291 const std::string getAsStr(Attributor *
A)
const override {
4295 return "assumed-dead-store";
4298 return "assumed-dead-fence";
4299 return AAIsDeadValueImpl::getAsStr(
A);
4306 if (!isDeadStore(
A, *SI))
4307 return indicatePessimisticFixpoint();
4309 if (!isDeadFence(
A, *FI))
4310 return indicatePessimisticFixpoint();
4312 if (!isAssumedSideEffectFree(
A,
I))
4313 return indicatePessimisticFixpoint();
4314 if (!areAllUsesAssumedDead(
A, getAssociatedValue()))
4315 return indicatePessimisticFixpoint();
4320 bool isRemovableStore()
const override {
4321 return isAssumed(IS_REMOVABLE) &&
isa<StoreInst>(&getAssociatedValue());
4326 Value &
V = getAssociatedValue();
4333 SmallSetVector<Instruction *, 8> AssumeOnlyInst;
4334 bool IsDead = isDeadStore(
A, *SI, &AssumeOnlyInst);
4337 A.deleteAfterManifest(*
I);
4338 for (
size_t i = 0; i < AssumeOnlyInst.
size(); ++i) {
4340 for (
auto *Usr : AOI->
users())
4342 A.deleteAfterManifest(*AOI);
4348 A.deleteAfterManifest(*FI);
4351 if (isAssumedSideEffectFree(
A,
I) && !
I->isTerminator()) {
4352 A.deleteAfterManifest(*
I);
4360 void trackStatistics()
const override {
4366 SmallSetVector<Value *, 4> PotentialCopies;
4369struct AAIsDeadArgument :
public AAIsDeadFloating {
4370 AAIsDeadArgument(
const IRPosition &IRP, Attributor &
A)
4371 : AAIsDeadFloating(IRP,
A) {}
4375 Argument &Arg = *getAssociatedArgument();
4376 if (
A.isValidFunctionSignatureRewrite(Arg, {}))
4377 if (
A.registerFunctionSignatureRewrite(
4381 return ChangeStatus::CHANGED;
4383 return ChangeStatus::UNCHANGED;
4390struct AAIsDeadCallSiteArgument :
public AAIsDeadValueImpl {
4391 AAIsDeadCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
4392 : AAIsDeadValueImpl(IRP,
A) {}
4396 AAIsDeadValueImpl::initialize(
A);
4398 indicatePessimisticFixpoint();
4407 Argument *Arg = getAssociatedArgument();
4409 return indicatePessimisticFixpoint();
4411 auto *ArgAA =
A.getAAFor<AAIsDead>(*
this, ArgPos, DepClassTy::REQUIRED);
4413 return indicatePessimisticFixpoint();
4422 "Expected undef values to be filtered out!");
4424 if (
A.changeUseAfterManifest(U, UV))
4425 return ChangeStatus::CHANGED;
4426 return ChangeStatus::UNCHANGED;
4433struct AAIsDeadCallSiteReturned :
public AAIsDeadFloating {
4434 AAIsDeadCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
4435 : AAIsDeadFloating(IRP,
A) {}
4438 bool isAssumedDead()
const override {
4439 return AAIsDeadFloating::isAssumedDead() && IsAssumedSideEffectFree;
4444 AAIsDeadFloating::initialize(
A);
4446 indicatePessimisticFixpoint();
4451 IsAssumedSideEffectFree = isAssumedSideEffectFree(
A, getCtxI());
4457 if (IsAssumedSideEffectFree && !isAssumedSideEffectFree(
A, getCtxI())) {
4458 IsAssumedSideEffectFree =
false;
4459 Changed = ChangeStatus::CHANGED;
4461 if (!areAllUsesAssumedDead(
A, getAssociatedValue()))
4462 return indicatePessimisticFixpoint();
4467 void trackStatistics()
const override {
4468 if (IsAssumedSideEffectFree)
4475 const std::string getAsStr(Attributor *
A)
const override {
4476 return isAssumedDead()
4478 : (getAssumed() ?
"assumed-dead-users" :
"assumed-live");
4482 bool IsAssumedSideEffectFree =
true;
4485struct AAIsDeadReturned :
public AAIsDeadValueImpl {
4486 AAIsDeadReturned(
const IRPosition &IRP, Attributor &
A)
4487 : AAIsDeadValueImpl(IRP,
A) {}
4492 bool UsedAssumedInformation =
false;
4493 A.checkForAllInstructions([](Instruction &) {
return true; }, *
this,
4494 {Instruction::Ret}, UsedAssumedInformation);
4496 auto PredForCallSite = [&](AbstractCallSite ACS) {
4497 if (ACS.isCallbackCall() || !ACS.getInstruction())
4499 return areAllUsesAssumedDead(
A, *ACS.getInstruction());
4502 if (!
A.checkForAllCallSites(PredForCallSite, *
this,
true,
4503 UsedAssumedInformation))
4504 return indicatePessimisticFixpoint();
4506 return ChangeStatus::UNCHANGED;
4512 bool AnyChange =
false;
4513 UndefValue &UV = *
UndefValue::get(getAssociatedFunction()->getReturnType());
4520 bool UsedAssumedInformation =
false;
4521 A.checkForAllInstructions(RetInstPred, *
this, {Instruction::Ret},
4522 UsedAssumedInformation);
4523 return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
4530struct AAIsDeadFunction :
public AAIsDead {
4531 AAIsDeadFunction(
const IRPosition &IRP, Attributor &
A) : AAIsDead(IRP,
A) {}
4536 assert(
F &&
"Did expect an anchor function");
4537 if (!isAssumedDeadInternalFunction(
A)) {
4538 ToBeExploredFrom.insert(&
F->getEntryBlock().front());
4539 assumeLive(
A,
F->getEntryBlock());
4543 bool isAssumedDeadInternalFunction(Attributor &
A) {
4544 if (!getAnchorScope()->hasLocalLinkage())
4546 bool UsedAssumedInformation =
false;
4547 return A.checkForAllCallSites([](AbstractCallSite) {
return false; }, *
this,
4548 true, UsedAssumedInformation);
4552 const std::string getAsStr(Attributor *
A)
const override {
4553 return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) +
"/" +
4554 std::to_string(getAnchorScope()->
size()) +
"][#TBEP " +
4555 std::to_string(ToBeExploredFrom.size()) +
"][#KDE " +
4556 std::to_string(KnownDeadEnds.size()) +
"]";
4561 assert(getState().isValidState() &&
4562 "Attempted to manifest an invalid state!");
4567 if (AssumedLiveBlocks.empty()) {
4568 A.deleteAfterManifest(
F);
4569 return ChangeStatus::CHANGED;
4575 bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(
F);
4577 KnownDeadEnds.set_union(ToBeExploredFrom);
4578 for (
const Instruction *DeadEndI : KnownDeadEnds) {
4582 bool IsKnownNoReturn;
4590 A.registerInvokeWithDeadSuccessor(
const_cast<InvokeInst &
>(*
II));
4592 A.changeToUnreachableAfterManifest(
4593 const_cast<Instruction *
>(DeadEndI->getNextNode()));
4594 HasChanged = ChangeStatus::CHANGED;
4597 STATS_DECL(AAIsDead, BasicBlock,
"Number of dead basic blocks deleted.");
4598 for (BasicBlock &BB :
F)
4599 if (!AssumedLiveBlocks.count(&BB)) {
4600 A.deleteAfterManifest(BB);
4602 HasChanged = ChangeStatus::CHANGED;
4611 bool isEdgeDead(
const BasicBlock *From,
const BasicBlock *To)
const override {
4614 "Used AAIsDead of the wrong function");
4615 return isValidState() && !AssumedLiveEdges.count(std::make_pair(From, To));
4619 void trackStatistics()
const override {}
4622 bool isAssumedDead()
const override {
return false; }
4625 bool isKnownDead()
const override {
return false; }
4628 bool isAssumedDead(
const BasicBlock *BB)
const override {
4630 "BB must be in the same anchor scope function.");
4634 return !AssumedLiveBlocks.count(BB);
4638 bool isKnownDead(
const BasicBlock *BB)
const override {
4639 return getKnown() && isAssumedDead(BB);
4643 bool isAssumedDead(
const Instruction *
I)
const override {
4644 assert(
I->getParent()->getParent() == getAnchorScope() &&
4645 "Instruction must be in the same anchor scope function.");
4652 if (!AssumedLiveBlocks.count(
I->getParent()))
4658 if (KnownDeadEnds.count(PrevI) || ToBeExploredFrom.count(PrevI))
4666 bool isKnownDead(
const Instruction *
I)
const override {
4667 return getKnown() && isAssumedDead(
I);
4672 bool assumeLive(Attributor &
A,
const BasicBlock &BB) {
4673 if (!AssumedLiveBlocks.insert(&BB).second)
4680 for (
const Instruction &
I : BB)
4683 if (
F->hasLocalLinkage())
4684 A.markLiveInternalFunction(*
F);
4690 SmallSetVector<const Instruction *, 8> ToBeExploredFrom;
4693 SmallSetVector<const Instruction *, 8> KnownDeadEnds;
4696 DenseSet<std::pair<const BasicBlock *, const BasicBlock *>> AssumedLiveEdges;
4699 DenseSet<const BasicBlock *> AssumedLiveBlocks;
4703identifyAliveSuccessors(Attributor &
A,
const CallBase &CB,
4704 AbstractAttribute &AA,
4705 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4708 bool IsKnownNoReturn;
4711 return !IsKnownNoReturn;
4720identifyAliveSuccessors(Attributor &
A,
const InvokeInst &
II,
4721 AbstractAttribute &AA,
4722 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4723 bool UsedAssumedInformation =
4729 if (AAIsDeadFunction::mayCatchAsynchronousExceptions(*
II.getFunction())) {
4730 AliveSuccessors.
push_back(&
II.getUnwindDest()->front());
4734 bool IsKnownNoUnwind;
4737 UsedAssumedInformation |= !IsKnownNoUnwind;
4739 AliveSuccessors.
push_back(&
II.getUnwindDest()->front());
4742 return UsedAssumedInformation;
4746identifyAliveSuccessors(Attributor &,
const UncondBrInst &BI,
4747 AbstractAttribute &,
4748 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4754identifyAliveSuccessors(Attributor &
A,
const CondBrInst &BI,
4755 AbstractAttribute &AA,
4756 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4757 bool UsedAssumedInformation =
false;
4758 std::optional<Constant *>
C =
4759 A.getAssumedConstant(*BI.
getCondition(), AA, UsedAssumedInformation);
4769 UsedAssumedInformation =
false;
4771 return UsedAssumedInformation;
4775identifyAliveSuccessors(Attributor &
A,
const SwitchInst &SI,
4776 AbstractAttribute &AA,
4777 SmallVectorImpl<const Instruction *> &AliveSuccessors) {
4778 bool UsedAssumedInformation =
false;
4782 UsedAssumedInformation)) {
4784 for (
const BasicBlock *SuccBB :
successors(
SI.getParent()))
4793 return UsedAssumedInformation;
4796 Type &Ty = *
SI.getCondition()->getType();
4797 SmallPtrSet<ConstantInt *, 8>
Constants;
4798 auto CheckForConstantInt = [&](
Value *
V) {
4807 return CheckForConstantInt(VAC.
getValue());
4809 for (
const BasicBlock *SuccBB :
successors(
SI.getParent()))
4811 return UsedAssumedInformation;
4814 unsigned MatchedCases = 0;
4815 for (
const auto &CaseIt :
SI.cases()) {
4816 if (
Constants.count(CaseIt.getCaseValue())) {
4818 AliveSuccessors.
push_back(&CaseIt.getCaseSuccessor()->front());
4825 AliveSuccessors.
push_back(&
SI.getDefaultDest()->front());
4826 return UsedAssumedInformation;
4832 if (AssumedLiveBlocks.empty()) {
4833 if (isAssumedDeadInternalFunction(
A))
4837 ToBeExploredFrom.insert(&
F->getEntryBlock().front());
4838 assumeLive(
A,
F->getEntryBlock());
4842 LLVM_DEBUG(
dbgs() <<
"[AAIsDead] Live [" << AssumedLiveBlocks.size() <<
"/"
4843 << getAnchorScope()->
size() <<
"] BBs and "
4844 << ToBeExploredFrom.size() <<
" exploration points and "
4845 << KnownDeadEnds.size() <<
" known dead ends\n");
4850 ToBeExploredFrom.end());
4851 decltype(ToBeExploredFrom) NewToBeExploredFrom;
4854 while (!Worklist.
empty()) {
4861 I =
I->getNextNode();
4863 AliveSuccessors.
clear();
4865 bool UsedAssumedInformation =
false;
4866 switch (
I->getOpcode()) {
4870 "Expected non-terminators to be handled already!");
4871 for (
const BasicBlock *SuccBB :
successors(
I->getParent()))
4874 case Instruction::Call:
4876 *
this, AliveSuccessors);
4878 case Instruction::Invoke:
4880 *
this, AliveSuccessors);
4882 case Instruction::UncondBr:
4883 UsedAssumedInformation = identifyAliveSuccessors(
4886 case Instruction::CondBr:
4888 *
this, AliveSuccessors);
4890 case Instruction::Switch:
4892 *
this, AliveSuccessors);
4896 if (UsedAssumedInformation) {
4897 NewToBeExploredFrom.insert(
I);
4898 }
else if (AliveSuccessors.
empty() ||
4899 (
I->isTerminator() &&
4900 AliveSuccessors.
size() <
I->getNumSuccessors())) {
4901 if (KnownDeadEnds.insert(
I))
4906 << AliveSuccessors.
size() <<
" UsedAssumedInformation: "
4907 << UsedAssumedInformation <<
"\n");
4909 for (
const Instruction *AliveSuccessor : AliveSuccessors) {
4910 if (!
I->isTerminator()) {
4911 assert(AliveSuccessors.size() == 1 &&
4912 "Non-terminator expected to have a single successor!");
4916 auto Edge = std::make_pair(
I->getParent(), AliveSuccessor->getParent());
4917 if (AssumedLiveEdges.insert(
Edge).second)
4919 if (assumeLive(
A, *AliveSuccessor->getParent()))
4926 if (NewToBeExploredFrom.size() != ToBeExploredFrom.size() ||
4927 llvm::any_of(NewToBeExploredFrom, [&](
const Instruction *
I) {
4928 return !ToBeExploredFrom.count(I);
4931 ToBeExploredFrom = std::move(NewToBeExploredFrom);
4940 if (ToBeExploredFrom.empty() &&
4941 getAnchorScope()->
size() == AssumedLiveBlocks.size() &&
4942 llvm::all_of(KnownDeadEnds, [](
const Instruction *DeadEndI) {
4943 return DeadEndI->isTerminator() && DeadEndI->getNumSuccessors() == 0;
4945 return indicatePessimisticFixpoint();
4950struct AAIsDeadCallSite final : AAIsDeadFunction {
4951 AAIsDeadCallSite(
const IRPosition &IRP, Attributor &
A)
4952 : AAIsDeadFunction(IRP,
A) {}
4961 "supported for call sites yet!");
4966 return indicatePessimisticFixpoint();
4970 void trackStatistics()
const override {}
4977struct AADereferenceableImpl : AADereferenceable {
4978 AADereferenceableImpl(
const IRPosition &IRP, Attributor &
A)
4979 : AADereferenceable(IRP,
A) {}
4980 using StateType = DerefState;
4984 Value &
V = *getAssociatedValue().stripPointerCasts();
4986 A.getAttrs(getIRPosition(),
4987 {Attribute::Dereferenceable, Attribute::DereferenceableOrNull},
4990 takeKnownDerefBytesMaximum(Attr.getValueAsInt());
4993 bool IsKnownNonNull;
4995 A,
this, getIRPosition(), DepClassTy::OPTIONAL, IsKnownNonNull);
4998 takeKnownDerefBytesMaximum(
V.getPointerDereferenceableBytes(
4999 A.getDataLayout(), CanBeNull,
nullptr));
5001 if (Instruction *CtxI = getCtxI())
5002 followUsesInMBEC(*
this,
A, getState(), *CtxI);
5007 StateType &getState()
override {
return *
this; }
5008 const StateType &getState()
const override {
return *
this; }
5012 void addAccessedBytesForUse(Attributor &
A,
const Use *U,
const Instruction *
I,
5013 DerefState &State) {
5014 const Value *UseV =
U->get();
5019 if (!Loc || Loc->Ptr != UseV || !Loc->Size.isPrecise() ||
I->isVolatile())
5024 Loc->Ptr,
Offset,
A.getDataLayout(),
true);
5025 if (
Base &&
Base == &getAssociatedValue())
5026 State.addAccessedBytes(
Offset, Loc->Size.getValue());
5030 bool followUseInMBEC(Attributor &
A,
const Use *U,
const Instruction *
I,
5031 AADereferenceable::StateType &State) {
5032 bool IsNonNull =
false;
5033 bool TrackUse =
false;
5034 int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse(
5035 A, *
this, getAssociatedValue(), U,
I, IsNonNull, TrackUse);
5036 LLVM_DEBUG(
dbgs() <<
"[AADereferenceable] Deref bytes: " << DerefBytes
5037 <<
" for instruction " << *
I <<
"\n");
5039 addAccessedBytesForUse(
A, U,
I, State);
5040 State.takeKnownDerefBytesMaximum(DerefBytes);
5047 bool IsKnownNonNull;
5049 A,
this, getIRPosition(), DepClassTy::NONE, IsKnownNonNull);
5050 if (IsAssumedNonNull &&
5051 A.hasAttr(getIRPosition(), Attribute::DereferenceableOrNull)) {
5052 A.removeAttrs(getIRPosition(), {Attribute::DereferenceableOrNull});
5053 return ChangeStatus::CHANGED;
5058 void getDeducedAttributes(Attributor &
A, LLVMContext &Ctx,
5059 SmallVectorImpl<Attribute> &Attrs)
const override {
5061 bool IsKnownNonNull;
5063 A,
this, getIRPosition(), DepClassTy::NONE, IsKnownNonNull);
5064 if (IsAssumedNonNull)
5065 Attrs.emplace_back(Attribute::getWithDereferenceableBytes(
5066 Ctx, getAssumedDereferenceableBytes()));
5068 Attrs.emplace_back(Attribute::getWithDereferenceableOrNullBytes(
5069 Ctx, getAssumedDereferenceableBytes()));
5073 const std::string getAsStr(Attributor *
A)
const override {
5074 if (!getAssumedDereferenceableBytes())
5075 return "unknown-dereferenceable";
5076 bool IsKnownNonNull;
5077 bool IsAssumedNonNull =
false;
5080 *
A,
this, getIRPosition(), DepClassTy::NONE, IsKnownNonNull);
5081 return std::string(
"dereferenceable") +
5082 (IsAssumedNonNull ?
"" :
"_or_null") +
5083 (isAssumedGlobal() ?
"_globally" :
"") +
"<" +
5084 std::to_string(getKnownDereferenceableBytes()) +
"-" +
5085 std::to_string(getAssumedDereferenceableBytes()) +
">" +
5086 (!
A ?
" [non-null is unknown]" :
"");
5091struct AADereferenceableFloating : AADereferenceableImpl {
5092 AADereferenceableFloating(
const IRPosition &IRP, Attributor &
A)
5093 : AADereferenceableImpl(IRP,
A) {}
5098 bool UsedAssumedInformation =
false;
5100 if (!
A.getAssumedSimplifiedValues(getIRPosition(), *
this,
Values,
5102 Values.push_back({getAssociatedValue(), getCtxI()});
5105 Stripped =
Values.size() != 1 ||
5106 Values.front().getValue() != &getAssociatedValue();
5109 const DataLayout &
DL =
A.getDataLayout();
5112 auto VisitValueCB = [&](
const Value &
V) ->
bool {
5114 DL.getIndexSizeInBits(
V.getType()->getPointerAddressSpace());
5115 APInt
Offset(IdxWidth, 0);
5120 const auto *AA =
A.getAAFor<AADereferenceable>(
5122 int64_t DerefBytes = 0;
5123 if (!AA || (!Stripped &&
this == AA)) {
5127 DerefBytes =
Base->getPointerDereferenceableBytes(
5128 DL, CanBeNull,
nullptr);
5129 T.GlobalState.indicatePessimisticFixpoint();
5132 DerefBytes =
DS.DerefBytesState.getAssumed();
5133 T.GlobalState &=
DS.GlobalState;
5139 int64_t OffsetSExt =
Offset.getSExtValue();
5143 T.takeAssumedDerefBytesMinimum(
5144 std::max(int64_t(0), DerefBytes - OffsetSExt));
5149 T.takeKnownDerefBytesMaximum(
5150 std::max(int64_t(0), DerefBytes - OffsetSExt));
5151 T.indicatePessimisticFixpoint();
5152 }
else if (OffsetSExt > 0) {
5158 T.indicatePessimisticFixpoint();
5162 return T.isValidState();
5165 for (
const auto &VAC :
Values)
5166 if (!VisitValueCB(*VAC.
getValue()))
5167 return indicatePessimisticFixpoint();
5173 void trackStatistics()
const override {
5179struct AADereferenceableReturned final
5180 : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl> {
5182 AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl>;
5183 AADereferenceableReturned(
const IRPosition &IRP, Attributor &
A)
5187 void trackStatistics()
const override {
5193struct AADereferenceableArgument final
5194 : AAArgumentFromCallSiteArguments<AADereferenceable,
5195 AADereferenceableImpl> {
5197 AAArgumentFromCallSiteArguments<AADereferenceable, AADereferenceableImpl>;
5198 AADereferenceableArgument(
const IRPosition &IRP, Attributor &
A)
5202 void trackStatistics()
const override {
5208struct AADereferenceableCallSiteArgument final : AADereferenceableFloating {
5209 AADereferenceableCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
5210 : AADereferenceableFloating(IRP,
A) {}
5213 void trackStatistics()
const override {
5219struct AADereferenceableCallSiteReturned final
5220 : AACalleeToCallSite<AADereferenceable, AADereferenceableImpl> {
5221 using Base = AACalleeToCallSite<AADereferenceable, AADereferenceableImpl>;
5222 AADereferenceableCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
5226 void trackStatistics()
const override {
5236static unsigned getKnownAlignForUse(Attributor &
A, AAAlign &QueryingAA,
5237 Value &AssociatedValue,
const Use *U,
5238 const Instruction *
I,
bool &TrackUse) {
5247 if (
GEP->hasAllConstantIndices())
5252 switch (
II->getIntrinsicID()) {
5253 case Intrinsic::ptrmask: {
5255 const auto *ConstVals =
A.getAAFor<AAPotentialConstantValues>(
5257 const auto *AlignAA =
A.getAAFor<AAAlign>(
5259 if (ConstVals && ConstVals->isValidState() && ConstVals->isAtFixpoint()) {
5260 unsigned ShiftValue = std::min(ConstVals->getAssumedMinTrailingZeros(),
5262 Align ConstAlign(UINT64_C(1) << ShiftValue);
5263 if (ConstAlign >= AlignAA->getKnownAlign())
5264 return Align(1).value();
5267 return AlignAA->getKnownAlign().
value();
5270 case Intrinsic::amdgcn_make_buffer_rsrc: {
5271 const auto *AlignAA =
A.getAAFor<AAAlign>(
5274 return AlignAA->getKnownAlign().
value();
5292 MA = MaybeAlign(AlignAA->getKnownAlign());
5295 const DataLayout &
DL =
A.getDataLayout();
5296 const Value *UseV =
U->get();
5298 if (
SI->getPointerOperand() == UseV)
5299 MA =
SI->getAlign();
5301 if (LI->getPointerOperand() == UseV)
5302 MA = LI->getAlign();
5304 if (AI->getPointerOperand() == UseV)
5305 MA = AI->getAlign();
5307 if (AI->getPointerOperand() == UseV)
5308 MA = AI->getAlign();
5318 if (
Base == &AssociatedValue) {
5323 uint32_t
gcd = std::gcd(uint32_t(
abs((int32_t)
Offset)), Alignment);
5331struct AAAlignImpl : AAAlign {
5332 AAAlignImpl(
const IRPosition &IRP, Attributor &
A) : AAAlign(IRP,
A) {}
5337 A.getAttrs(getIRPosition(), {Attribute::Alignment},
Attrs);
5339 takeKnownMaximum(Attr.getValueAsInt());
5341 Value &
V = *getAssociatedValue().stripPointerCasts();
5342 takeKnownMaximum(
V.getPointerAlignment(
A.getDataLayout()).value());
5344 if (Instruction *CtxI = getCtxI())
5345 followUsesInMBEC(*
this,
A, getState(), *CtxI);
5353 Value &AssociatedValue = getAssociatedValue();
5355 return ChangeStatus::UNCHANGED;
5357 for (
const Use &U : AssociatedValue.
uses()) {
5359 if (
SI->getPointerOperand() == &AssociatedValue)
5360 if (
SI->getAlign() < getAssumedAlign()) {
5362 "Number of times alignment added to a store");
5363 SI->setAlignment(getAssumedAlign());
5364 InstrChanged = ChangeStatus::CHANGED;
5367 if (LI->getPointerOperand() == &AssociatedValue)
5368 if (LI->getAlign() < getAssumedAlign()) {
5369 LI->setAlignment(getAssumedAlign());
5371 "Number of times alignment added to a load");
5372 InstrChanged = ChangeStatus::CHANGED;
5375 if (RMW->getPointerOperand() == &AssociatedValue) {
5376 if (RMW->getAlign() < getAssumedAlign()) {
5378 "Number of times alignment added to atomicrmw");
5380 RMW->setAlignment(getAssumedAlign());
5381 InstrChanged = ChangeStatus::CHANGED;
5385 if (CAS->getPointerOperand() == &AssociatedValue) {
5386 if (CAS->getAlign() < getAssumedAlign()) {
5388 "Number of times alignment added to cmpxchg");
5389 CAS->setAlignment(getAssumedAlign());
5390 InstrChanged = ChangeStatus::CHANGED;
5398 Align InheritAlign =
5399 getAssociatedValue().getPointerAlignment(
A.getDataLayout());
5400 if (InheritAlign >= getAssumedAlign())
5401 return InstrChanged;
5402 return Changed | InstrChanged;
5410 void getDeducedAttributes(Attributor &
A, LLVMContext &Ctx,
5411 SmallVectorImpl<Attribute> &Attrs)
const override {
5412 if (getAssumedAlign() > 1)
5414 Attribute::getWithAlignment(Ctx,
Align(getAssumedAlign())));
5418 bool followUseInMBEC(Attributor &
A,
const Use *U,
const Instruction *
I,
5419 AAAlign::StateType &State) {
5420 bool TrackUse =
false;
5422 unsigned int KnownAlign =
5423 getKnownAlignForUse(
A, *
this, getAssociatedValue(), U,
I, TrackUse);
5424 State.takeKnownMaximum(KnownAlign);
5430 const std::string getAsStr(Attributor *
A)
const override {
5431 return "align<" + std::to_string(getKnownAlign().value()) +
"-" +
5432 std::to_string(getAssumedAlign().value()) +
">";
5437struct AAAlignFloating : AAAlignImpl {
5438 AAAlignFloating(
const IRPosition &IRP, Attributor &
A) : AAAlignImpl(IRP,
A) {}
5442 const DataLayout &
DL =
A.getDataLayout();
5445 bool UsedAssumedInformation =
false;
5447 if (!
A.getAssumedSimplifiedValues(getIRPosition(), *
this,
Values,
5449 Values.push_back({getAssociatedValue(), getCtxI()});
5452 Stripped =
Values.size() != 1 ||
5453 Values.front().getValue() != &getAssociatedValue();
5457 auto VisitValueCB = [&](
Value &
V) ->
bool {
5461 DepClassTy::REQUIRED);
5462 if (!AA || (!Stripped &&
this == AA)) {
5480 T.takeKnownMaximum(Alignment);
5481 T.indicatePessimisticFixpoint();
5484 const AAAlign::StateType &
DS = AA->
getState();
5487 return T.isValidState();
5490 for (
const auto &VAC :
Values) {
5491 if (!VisitValueCB(*VAC.
getValue()))
5492 return indicatePessimisticFixpoint();
5505struct AAAlignReturned final
5506 : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl> {
5507 using Base = AAReturnedFromReturnedValues<AAAlign, AAAlignImpl>;
5508 AAAlignReturned(
const IRPosition &IRP, Attributor &
A) :
Base(IRP,
A) {}
5515struct AAAlignArgument final
5516 : AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl> {
5517 using Base = AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl>;
5518 AAAlignArgument(
const IRPosition &IRP, Attributor &
A) :
Base(IRP,
A) {}
5525 if (
A.getInfoCache().isInvolvedInMustTailCall(*getAssociatedArgument()))
5526 return ChangeStatus::UNCHANGED;
5527 return Base::manifest(
A);
5534struct AAAlignCallSiteArgument final : AAAlignFloating {
5535 AAAlignCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
5536 : AAAlignFloating(IRP,
A) {}
5543 if (Argument *Arg = getAssociatedArgument())
5544 if (
A.getInfoCache().isInvolvedInMustTailCall(*Arg))
5545 return ChangeStatus::UNCHANGED;
5547 Align InheritAlign =
5548 getAssociatedValue().getPointerAlignment(
A.getDataLayout());
5549 if (InheritAlign >= getAssumedAlign())
5550 Changed = ChangeStatus::UNCHANGED;
5557 if (Argument *Arg = getAssociatedArgument()) {
5560 const auto *ArgAlignAA =
A.getAAFor<AAAlign>(
5563 takeKnownMaximum(ArgAlignAA->getKnownAlign().value());
5573struct AAAlignCallSiteReturned final
5574 : AACalleeToCallSite<AAAlign, AAAlignImpl> {
5575 using Base = AACalleeToCallSite<AAAlign, AAAlignImpl>;
5576 AAAlignCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
5582 switch (
II->getIntrinsicID()) {
5583 case Intrinsic::ptrmask: {
5587 const auto *ConstVals =
A.getAAFor<AAPotentialConstantValues>(
5589 if (ConstVals && ConstVals->isValidState()) {
5590 unsigned ShiftValue =
5591 std::min(ConstVals->getAssumedMinTrailingZeros(),
5592 Value::MaxAlignmentExponent);
5597 const auto *AlignAA =
5599 DepClassTy::REQUIRED);
5601 Alignment = std::max(AlignAA->getAssumedAlign(), Alignment);
5608 std::min(this->getAssumedAlign(), Alignment).value());
5614 case Intrinsic::amdgcn_make_buffer_rsrc: {
5615 const auto *AlignAA =
5617 DepClassTy::REQUIRED);
5620 this->getState(), AlignAA->getAssumedAlign().
value());
5627 return Base::updateImpl(
A);
5636struct AANoReturnImpl :
public AANoReturn {
5637 AANoReturnImpl(
const IRPosition &IRP, Attributor &
A) : AANoReturn(IRP,
A) {}
5643 A,
nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
5648 const std::string getAsStr(Attributor *
A)
const override {
5649 return getAssumed() ?
"noreturn" :
"may-return";
5654 auto CheckForNoReturn = [](
Instruction &) {
return false; };
5655 bool UsedAssumedInformation =
false;
5656 if (!
A.checkForAllInstructions(CheckForNoReturn, *
this,
5657 {(unsigned)Instruction::Ret},
5658 UsedAssumedInformation))
5659 return indicatePessimisticFixpoint();
5660 return ChangeStatus::UNCHANGED;
5664struct AANoReturnFunction final : AANoReturnImpl {
5665 AANoReturnFunction(
const IRPosition &IRP, Attributor &
A)
5666 : AANoReturnImpl(IRP,
A) {}
5673struct AANoReturnCallSite final
5674 : AACalleeToCallSite<AANoReturn, AANoReturnImpl> {
5675 AANoReturnCallSite(
const IRPosition &IRP, Attributor &
A)
5676 : AACalleeToCallSite<AANoReturn, AANoReturnImpl>(IRP,
A) {}
5687struct AAInstanceInfoImpl :
public AAInstanceInfo {
5688 AAInstanceInfoImpl(
const IRPosition &IRP, Attributor &
A)
5689 : AAInstanceInfo(IRP,
A) {}
5693 Value &
V = getAssociatedValue();
5695 if (
C->isThreadDependent())
5696 indicatePessimisticFixpoint();
5698 indicateOptimisticFixpoint();
5704 indicateOptimisticFixpoint();
5709 A.getInfoCache().getAnalysisResultForFunction<CycleAnalysis>(
5712 indicatePessimisticFixpoint();
5722 Value &
V = getAssociatedValue();
5725 Scope =
I->getFunction();
5728 if (!
Scope->hasLocalLinkage())
5732 return indicateOptimisticFixpoint();
5734 bool IsKnownNoRecurse;
5740 auto UsePred = [&](
const Use &
U,
bool &Follow) {
5755 if (!Callee || !
Callee->hasLocalLinkage())
5759 const auto *ArgInstanceInfoAA =
A.getAAFor<AAInstanceInfo>(
5761 DepClassTy::OPTIONAL);
5762 if (!ArgInstanceInfoAA ||
5763 !ArgInstanceInfoAA->isAssumedUniqueForAnalysis())
5768 A, *CB, *Scope, *
this,
nullptr,
5776 auto EquivalentUseCB = [&](
const Use &OldU,
const Use &NewU) {
5778 auto *Ptr =
SI->getPointerOperand()->stripPointerCasts();
5786 if (!
A.checkForAllUses(UsePred, *
this, V,
true,
5787 DepClassTy::OPTIONAL,
5788 true, EquivalentUseCB))
5789 return indicatePessimisticFixpoint();
5795 const std::string getAsStr(Attributor *
A)
const override {
5796 return isAssumedUniqueForAnalysis() ?
"<unique [fAa]>" :
"<unknown>";
5800 void trackStatistics()
const override {}
5804struct AAInstanceInfoFloating : AAInstanceInfoImpl {
5805 AAInstanceInfoFloating(
const IRPosition &IRP, Attributor &
A)
5806 : AAInstanceInfoImpl(IRP,
A) {}
5810struct AAInstanceInfoArgument final : AAInstanceInfoFloating {
5811 AAInstanceInfoArgument(
const IRPosition &IRP, Attributor &
A)
5812 : AAInstanceInfoFloating(IRP,
A) {}
5816struct AAInstanceInfoCallSiteArgument final : AAInstanceInfoImpl {
5817 AAInstanceInfoCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
5818 : AAInstanceInfoImpl(IRP,
A) {}
5826 Argument *Arg = getAssociatedArgument();
5828 return indicatePessimisticFixpoint();
5831 A.getAAFor<AAInstanceInfo>(*
this, ArgPos, DepClassTy::REQUIRED);
5833 return indicatePessimisticFixpoint();
5839struct AAInstanceInfoReturned final : AAInstanceInfoImpl {
5840 AAInstanceInfoReturned(
const IRPosition &IRP, Attributor &
A)
5841 : AAInstanceInfoImpl(IRP,
A) {
5857struct AAInstanceInfoCallSiteReturned final : AAInstanceInfoFloating {
5858 AAInstanceInfoCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
5859 : AAInstanceInfoFloating(IRP,
A) {}
5866 bool IgnoreSubsumingPositions) {
5867 assert(ImpliedAttributeKind == Attribute::Captures &&
5868 "Unexpected attribute kind");
5878 V.getType()->getPointerAddressSpace() == 0)) {
5883 A.getAttrs(IRP, {Attribute::Captures}, Attrs,
5893 {Attribute::Captures, Attribute::ByVal}, Attrs,
5931 bool NoThrow =
F.doesNotThrow();
5932 bool IsVoidReturn =
F.getReturnType()->isVoidTy();
5933 if (
ReadOnly && NoThrow && IsVoidReturn) {
5946 if (NoThrow && IsVoidReturn)
5951 if (!NoThrow || ArgNo < 0 ||
5952 !
F.getAttributes().hasAttrSomewhere(Attribute::Returned))
5955 for (
unsigned U = 0, E =
F.arg_size(); U < E; ++U)
5956 if (
F.hasParamAttribute(U, Attribute::Returned)) {
5957 if (U ==
unsigned(ArgNo))
5984 void getDeducedAttributes(Attributor &
A, LLVMContext &Ctx,
5985 SmallVectorImpl<Attribute> &Attrs)
const override {
5986 if (!isAssumedNoCaptureMaybeReturned())
5989 if (isArgumentPosition()) {
5990 if (isAssumedNoCapture())
5991 Attrs.emplace_back(Attribute::get(Ctx, Attribute::Captures));
5993 Attrs.emplace_back(Attribute::get(Ctx,
"no-capture-maybe-returned"));
5998 const std::string getAsStr(Attributor *
A)
const override {
5999 if (isKnownNoCapture())
6000 return "known not-captured";
6001 if (isAssumedNoCapture())
6002 return "assumed not-captured";
6003 if (isKnownNoCaptureMaybeReturned())
6004 return "known not-captured-maybe-returned";
6005 if (isAssumedNoCaptureMaybeReturned())
6006 return "assumed not-captured-maybe-returned";
6007 return "assumed-captured";
6012 bool checkUse(Attributor &
A, AANoCapture::StateType &State,
const Use &U,
6015 LLVM_DEBUG(
dbgs() <<
"[AANoCapture] Check use: " << *
U.get() <<
" in "
6021 return isCapturedIn(State,
true,
true,
6028 return isCapturedIn(State,
true,
true,
6034 return isCapturedIn(State,
false,
false,
6036 return isCapturedIn(State,
true,
true,
6044 return isCapturedIn(State,
true,
true,
6051 bool IsKnownNoCapture;
6052 const AANoCapture *ArgNoCaptureAA =
nullptr;
6054 A,
this, CSArgPos, DepClassTy::REQUIRED, IsKnownNoCapture,
false,
6056 if (IsAssumedNoCapture)
6057 return isCapturedIn(State,
false,
false,
6061 return isCapturedIn(State,
false,
false,
6066 return isCapturedIn(State,
true,
true,
6073 static bool isCapturedIn(AANoCapture::StateType &State,
bool CapturedInMem,
6074 bool CapturedInInt,
bool CapturedInRet) {
6075 LLVM_DEBUG(
dbgs() <<
" - captures [Mem " << CapturedInMem <<
"|Int "
6076 << CapturedInInt <<
"|Ret " << CapturedInRet <<
"]\n");
6088 const IRPosition &IRP = getIRPosition();
6092 return indicatePessimisticFixpoint();
6099 return indicatePessimisticFixpoint();
6107 T.addKnownBits(NOT_CAPTURED_IN_MEM);
6109 addKnownBits(NOT_CAPTURED_IN_MEM);
6116 auto CheckReturnedArgs = [&](
bool &UsedAssumedInformation) {
6120 UsedAssumedInformation))
6122 bool SeenConstant =
false;
6123 for (
const AA::ValueAndContext &VAC :
Values) {
6127 SeenConstant =
true;
6129 VAC.
getValue() == getAssociatedArgument())
6135 bool IsKnownNoUnwind;
6138 bool IsVoidTy =
F->getReturnType()->isVoidTy();
6139 bool UsedAssumedInformation =
false;
6140 if (IsVoidTy || CheckReturnedArgs(UsedAssumedInformation)) {
6141 T.addKnownBits(NOT_CAPTURED_IN_RET);
6142 if (
T.isKnown(NOT_CAPTURED_IN_MEM))
6144 if (IsKnownNoUnwind && (IsVoidTy || !UsedAssumedInformation)) {
6145 addKnownBits(NOT_CAPTURED_IN_RET);
6146 if (isKnown(NOT_CAPTURED_IN_MEM))
6147 return indicateOptimisticFixpoint();
6152 auto UseCheck = [&](
const Use &
U,
bool &Follow) ->
bool {
6161 return checkUse(
A,
T, U, Follow);
6164 if (!
A.checkForAllUses(UseCheck, *
this, *V))
6165 return indicatePessimisticFixpoint();
6168 auto Assumed = S.getAssumed();
6169 S.intersectAssumedBits(
T.getAssumed());
6170 if (!isAssumedNoCaptureMaybeReturned())
6171 return indicatePessimisticFixpoint();
6177struct AANoCaptureArgument final : AANoCaptureImpl {
6178 AANoCaptureArgument(
const IRPosition &IRP, Attributor &
A)
6179 : AANoCaptureImpl(IRP,
A) {}
6186struct AANoCaptureCallSiteArgument final : AANoCaptureImpl {
6187 AANoCaptureCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
6188 : AANoCaptureImpl(IRP,
A) {}
6196 Argument *Arg = getAssociatedArgument();
6198 return indicatePessimisticFixpoint();
6200 bool IsKnownNoCapture;
6201 const AANoCapture *ArgAA =
nullptr;
6203 A,
this, ArgPos, DepClassTy::REQUIRED, IsKnownNoCapture,
false,
6205 return ChangeStatus::UNCHANGED;
6207 return indicatePessimisticFixpoint();
6212 void trackStatistics()
const override {
6218struct AANoCaptureFloating final : AANoCaptureImpl {
6219 AANoCaptureFloating(
const IRPosition &IRP, Attributor &
A)
6220 : AANoCaptureImpl(IRP,
A) {}
6223 void trackStatistics()
const override {
6229struct AANoCaptureReturned final : AANoCaptureImpl {
6230 AANoCaptureReturned(
const IRPosition &IRP, Attributor &
A)
6231 : AANoCaptureImpl(IRP,
A) {
6246 void trackStatistics()
const override {}
6250struct AANoCaptureCallSiteReturned final : AANoCaptureImpl {
6251 AANoCaptureCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
6252 : AANoCaptureImpl(IRP,
A) {}
6258 determineFunctionCaptureCapabilities(getIRPosition(), *
F, *
this);
6262 void trackStatistics()
const override {
6279 dbgs() <<
"[ValueSimplify] is assumed to be "
6282 dbgs() <<
"[ValueSimplify] is assumed to be <none>\n";
6294 if (getAssociatedValue().
getType()->isVoidTy())
6295 indicatePessimisticFixpoint();
6296 if (
A.hasSimplificationCallback(getIRPosition()))
6297 indicatePessimisticFixpoint();
6301 const std::string getAsStr(Attributor *
A)
const override {
6303 dbgs() <<
"SAV: " << (bool)SimplifiedAssociatedValue <<
" ";
6304 if (SimplifiedAssociatedValue && *SimplifiedAssociatedValue)
6305 dbgs() <<
"SAV: " << **SimplifiedAssociatedValue <<
" ";
6307 return isValidState() ? (isAtFixpoint() ?
"simplified" :
"maybe-simple")
6312 void trackStatistics()
const override {}
6315 std::optional<Value *>
6316 getAssumedSimplifiedValue(Attributor &
A)
const override {
6317 return SimplifiedAssociatedValue;
6324 static Value *ensureType(Attributor &
A,
Value &V,
Type &Ty, Instruction *CtxI,
6328 if (CtxI &&
V.getType()->canLosslesslyBitCastTo(&Ty))
6330 : BitCastInst::CreatePointerBitCastOrAddrSpaceCast(
6339 static Value *reproduceInst(Attributor &
A,
6340 const AbstractAttribute &QueryingAA,
6341 Instruction &
I,
Type &Ty, Instruction *CtxI,
6343 assert(CtxI &&
"Cannot reproduce an instruction without context!");
6344 if (
Check && (
I.mayReadFromMemory() ||
6349 Value *NewOp = reproduceValue(
A, QueryingAA, *
Op, Ty, CtxI,
Check, VMap);
6351 assert(
Check &&
"Manifest of new value unexpectedly failed!");
6373 static Value *reproduceValue(Attributor &
A,
6374 const AbstractAttribute &QueryingAA,
Value &V,
6375 Type &Ty, Instruction *CtxI,
bool Check,
6377 if (
const auto &NewV = VMap.
lookup(&V))
6379 bool UsedAssumedInformation =
false;
6380 std::optional<Value *> SimpleV =
A.getAssumedSimplified(
6382 if (!SimpleV.has_value())
6386 EffectiveV = *SimpleV;
6391 return ensureType(
A, *EffectiveV, Ty, CtxI,
Check);
6393 if (
Value *NewV = reproduceInst(
A, QueryingAA, *
I, Ty, CtxI,
Check, VMap))
6394 return ensureType(
A, *NewV, Ty, CtxI,
Check);
6400 Value *manifestReplacementValue(Attributor &
A, Instruction *CtxI)
const {
6401 Value *NewV = SimplifiedAssociatedValue
6402 ? *SimplifiedAssociatedValue
6404 if (NewV && NewV != &getAssociatedValue()) {
6408 if (reproduceValue(
A, *
this, *NewV, *getAssociatedType(), CtxI,
6410 return reproduceValue(
A, *
this, *NewV, *getAssociatedType(), CtxI,
6418 bool checkAndUpdate(Attributor &
A,
const AbstractAttribute &QueryingAA,
6419 const IRPosition &IRP,
bool Simplify =
true) {
6420 bool UsedAssumedInformation =
false;
6423 QueryingValueSimplified =
A.getAssumedSimplified(
6425 return unionAssumed(QueryingValueSimplified);
6429 template <
typename AAType>
bool askSimplifiedValueFor(Attributor &
A) {
6430 if (!getAssociatedValue().
getType()->isIntegerTy())
6435 A.getAAFor<AAType>(*
this, getIRPosition(), DepClassTy::NONE);
6439 std::optional<Constant *> COpt = AA->getAssumedConstant(
A);
6442 SimplifiedAssociatedValue = std::nullopt;
6443 A.recordDependence(*AA, *
this, DepClassTy::OPTIONAL);
6446 if (
auto *
C = *COpt) {
6447 SimplifiedAssociatedValue =
C;
6448 A.recordDependence(*AA, *
this, DepClassTy::OPTIONAL);
6454 bool askSimplifiedValueForOtherAAs(Attributor &
A) {
6455 if (askSimplifiedValueFor<AAValueConstantRange>(
A))
6457 if (askSimplifiedValueFor<AAPotentialConstantValues>(
A))
6465 for (
auto &U : getAssociatedValue().uses()) {
6470 IP =
PHI->getIncomingBlock(U)->getTerminator();
6471 if (
auto *NewV = manifestReplacementValue(
A, IP)) {
6473 <<
" -> " << *NewV <<
" :: " << *
this <<
"\n");
6474 if (
A.changeUseAfterManifest(U, *NewV))
6475 Changed = ChangeStatus::CHANGED;
6479 return Changed | AAValueSimplify::manifest(
A);
6484 SimplifiedAssociatedValue = &getAssociatedValue();
6485 return AAValueSimplify::indicatePessimisticFixpoint();
6489struct AAValueSimplifyArgument final : AAValueSimplifyImpl {
6490 AAValueSimplifyArgument(
const IRPosition &IRP, Attributor &
A)
6491 : AAValueSimplifyImpl(IRP,
A) {}
6494 AAValueSimplifyImpl::initialize(
A);
6495 if (
A.hasAttr(getIRPosition(),
6496 {Attribute::InAlloca, Attribute::Preallocated,
6497 Attribute::StructRet, Attribute::Nest, Attribute::ByVal},
6499 indicatePessimisticFixpoint();
6506 Argument *Arg = getAssociatedArgument();
6512 return indicatePessimisticFixpoint();
6515 auto Before = SimplifiedAssociatedValue;
6517 auto PredForCallSite = [&](AbstractCallSite ACS) {
6518 const IRPosition &ACSArgPos =
6529 bool UsedAssumedInformation =
false;
6530 std::optional<Constant *> SimpleArgOp =
6531 A.getAssumedConstant(ACSArgPos, *
this, UsedAssumedInformation);
6538 return unionAssumed(*SimpleArgOp);
6543 bool UsedAssumedInformation =
false;
6544 if (hasCallBaseContext() &&
6545 getCallBaseContext()->getCalledOperand() == Arg->
getParent())
6547 AbstractCallSite(&getCallBaseContext()->getCalledOperandUse()));
6549 Success =
A.checkForAllCallSites(PredForCallSite, *
this,
true,
6550 UsedAssumedInformation);
6553 if (!askSimplifiedValueForOtherAAs(
A))
6554 return indicatePessimisticFixpoint();
6557 return Before == SimplifiedAssociatedValue ? ChangeStatus::UNCHANGED
6558 : ChangeStatus ::CHANGED;
6562 void trackStatistics()
const override {
6567struct AAValueSimplifyReturned : AAValueSimplifyImpl {
6568 AAValueSimplifyReturned(
const IRPosition &IRP, Attributor &
A)
6569 : AAValueSimplifyImpl(IRP,
A) {}
6572 std::optional<Value *>
6573 getAssumedSimplifiedValue(Attributor &
A)
const override {
6574 if (!isValidState())
6576 return SimplifiedAssociatedValue;
6581 auto Before = SimplifiedAssociatedValue;
6585 return checkAndUpdate(
6590 bool UsedAssumedInformation =
false;
6591 if (!
A.checkForAllInstructions(ReturnInstCB, *
this, {Instruction::Ret},
6592 UsedAssumedInformation))
6593 if (!askSimplifiedValueForOtherAAs(
A))
6594 return indicatePessimisticFixpoint();
6597 return Before == SimplifiedAssociatedValue ? ChangeStatus::UNCHANGED
6598 : ChangeStatus ::CHANGED;
6604 return ChangeStatus::UNCHANGED;
6608 void trackStatistics()
const override {
6613struct AAValueSimplifyFloating : AAValueSimplifyImpl {
6614 AAValueSimplifyFloating(
const IRPosition &IRP, Attributor &
A)
6615 : AAValueSimplifyImpl(IRP,
A) {}
6619 AAValueSimplifyImpl::initialize(
A);
6620 Value &
V = getAnchorValue();
6624 indicatePessimisticFixpoint();
6629 auto Before = SimplifiedAssociatedValue;
6630 if (!askSimplifiedValueForOtherAAs(
A))
6631 return indicatePessimisticFixpoint();
6634 return Before == SimplifiedAssociatedValue ? ChangeStatus::UNCHANGED
6635 : ChangeStatus ::CHANGED;
6639 void trackStatistics()
const override {
6644struct AAValueSimplifyFunction : AAValueSimplifyImpl {
6645 AAValueSimplifyFunction(
const IRPosition &IRP, Attributor &
A)
6646 : AAValueSimplifyImpl(IRP,
A) {}
6650 SimplifiedAssociatedValue =
nullptr;
6651 indicateOptimisticFixpoint();
6656 "AAValueSimplify(Function|CallSite)::updateImpl will not be called");
6659 void trackStatistics()
const override {
6664struct AAValueSimplifyCallSite : AAValueSimplifyFunction {
6665 AAValueSimplifyCallSite(
const IRPosition &IRP, Attributor &
A)
6666 : AAValueSimplifyFunction(IRP,
A) {}
6668 void trackStatistics()
const override {
6673struct AAValueSimplifyCallSiteReturned : AAValueSimplifyImpl {
6674 AAValueSimplifyCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
6675 : AAValueSimplifyImpl(IRP,
A) {}
6678 AAValueSimplifyImpl::initialize(
A);
6679 Function *Fn = getAssociatedFunction();
6680 assert(Fn &&
"Did expect an associted function");
6681 for (Argument &Arg : Fn->
args()) {
6686 checkAndUpdate(
A, *
this, IRP))
6687 indicateOptimisticFixpoint();
6689 indicatePessimisticFixpoint();
6697 return indicatePessimisticFixpoint();
6700 void trackStatistics()
const override {
6705struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating {
6706 AAValueSimplifyCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
6707 : AAValueSimplifyFloating(IRP,
A) {}
6713 auto *FloatAA =
A.lookupAAFor<AAValueSimplify>(
6715 if (FloatAA && FloatAA->getState().isValidState())
6718 if (
auto *NewV = manifestReplacementValue(
A, getCtxI())) {
6720 ->getArgOperandUse(getCallSiteArgNo());
6721 if (
A.changeUseAfterManifest(U, *NewV))
6722 Changed = ChangeStatus::CHANGED;
6725 return Changed | AAValueSimplify::manifest(
A);
6728 void trackStatistics()
const override {
6736struct AAHeapToStackFunction final :
public AAHeapToStack {
6738 static bool isGlobalizedLocal(
const CallBase &CB) {
6740 return A.
isValid() &&
A.getValueAsString() ==
"__kmpc_alloc_shared";
6743 struct AllocationInfo {
6748 bool IsGlobalizedLocal =
false;
6755 } Status = STACK_DUE_TO_USE;
6759 bool HasPotentiallyFreeingUnknownUses =
false;
6763 bool MoveAllocaIntoEntry =
true;
6766 SmallSetVector<CallBase *, 1> PotentialFreeCalls{};
6769 struct DeallocationInfo {
6777 bool MightFreeUnknownObjects =
false;
6780 SmallSetVector<CallBase *, 1> PotentialAllocationCalls{};
6783 AAHeapToStackFunction(
const IRPosition &IRP, Attributor &
A)
6784 : AAHeapToStack(IRP,
A) {}
6786 ~AAHeapToStackFunction()
override {
6789 for (
auto &It : AllocationInfos)
6790 It.second->~AllocationInfo();
6791 for (
auto &It : DeallocationInfos)
6792 It.second->~DeallocationInfo();
6796 AAHeapToStack::initialize(
A);
6799 const auto *TLI =
A.getInfoCache().getTargetLibraryInfoForFunction(*
F);
6806 DeallocationInfos[CB] =
new (
A.Allocator) DeallocationInfo{CB, FreedOp};
6813 auto *I8Ty = Type::getInt8Ty(CB->
getParent()->getContext());
6815 AllocationInfo *AI =
new (
A.Allocator) AllocationInfo{CB};
6816 AllocationInfos[CB] = AI;
6817 AI->IsGlobalizedLocal = isGlobalizedLocal(*CB);
6823 bool UsedAssumedInformation =
false;
6824 bool Success =
A.checkForAllCallLikeInstructions(
6825 AllocationIdentifierCB, *
this, UsedAssumedInformation,
6829 assert(
Success &&
"Did not expect the call base visit callback to fail!");
6832 [](
const IRPosition &,
const AbstractAttribute *,
6833 bool &) -> std::optional<Value *> {
return nullptr; };
6834 for (
const auto &It : AllocationInfos)
6837 for (
const auto &It : DeallocationInfos)
6842 const std::string getAsStr(Attributor *
A)
const override {
6843 unsigned NumH2SMallocs = 0, NumInvalidMallocs = 0;
6844 for (
const auto &It : AllocationInfos) {
6845 if (It.second->Status == AllocationInfo::INVALID)
6846 ++NumInvalidMallocs;
6850 return "[H2S] Mallocs Good/Bad: " + std::to_string(NumH2SMallocs) +
"/" +
6851 std::to_string(NumInvalidMallocs);
6855 void trackStatistics()
const override {
6858 "Number of malloc/calloc/aligned_alloc calls converted to allocas");
6859 for (
const auto &It : AllocationInfos)
6860 if (It.second->Status != AllocationInfo::INVALID)
6864 bool isAssumedHeapToStack(
const CallBase &CB)
const override {
6866 if (AllocationInfo *AI =
6867 AllocationInfos.lookup(
const_cast<CallBase *
>(&CB)))
6868 return AI->Status != AllocationInfo::INVALID;
6872 bool isAssumedHeapToStackRemovedFree(CallBase &CB)
const override {
6873 if (!isValidState())
6876 for (
const auto &It : AllocationInfos) {
6877 AllocationInfo &AI = *It.second;
6878 if (AI.Status == AllocationInfo::INVALID)
6881 if (AI.PotentialFreeCalls.count(&CB))
6889 assert(getState().isValidState() &&
6890 "Attempted to manifest an invalid state!");
6894 const auto *TLI =
A.getInfoCache().getTargetLibraryInfoForFunction(*
F);
6896 for (
auto &It : AllocationInfos) {
6897 AllocationInfo &AI = *It.second;
6898 if (AI.Status == AllocationInfo::INVALID)
6901 for (CallBase *FreeCall : AI.PotentialFreeCalls) {
6902 LLVM_DEBUG(
dbgs() <<
"H2S: Removing free call: " << *FreeCall <<
"\n");
6903 A.deleteAfterManifest(*FreeCall);
6904 HasChanged = ChangeStatus::CHANGED;
6907 LLVM_DEBUG(
dbgs() <<
"H2S: Removing malloc-like call: " << *AI.CB
6910 auto Remark = [&](OptimizationRemark
OR) {
6911 if (AI.IsGlobalizedLocal)
6912 return OR <<
"Moving globalized variable to the stack.";
6913 return OR <<
"Moving memory allocation from the heap to the stack.";
6915 if (AI.IsGlobalizedLocal)
6916 A.emitRemark<OptimizationRemark>(AI.CB,
"OMP110",
Remark);
6918 A.emitRemark<OptimizationRemark>(AI.CB,
"HeapToStack",
Remark);
6920 const DataLayout &
DL =
A.getInfoCache().getDL();
6922 std::optional<APInt> SizeAPI =
getSize(
A, *
this, AI);
6924 Size = ConstantInt::get(AI.CB->getContext(), *SizeAPI);
6926 LLVMContext &Ctx = AI.CB->getContext();
6927 ObjectSizeOpts Opts;
6928 ObjectSizeOffsetEvaluator Eval(
DL, TLI, Ctx, Opts);
6929 SizeOffsetValue SizeOffsetPair = Eval.compute(AI.CB);
6936 ?
F->getEntryBlock().begin()
6937 : AI.CB->getIterator();
6940 if (MaybeAlign RetAlign = AI.CB->getRetAlign())
6941 Alignment = std::max(Alignment, *RetAlign);
6943 std::optional<APInt> AlignmentAPI = getAPInt(
A, *
this, *Align);
6944 assert(AlignmentAPI && AlignmentAPI->getZExtValue() > 0 &&
6945 "Expected an alignment during manifest!");
6947 std::max(Alignment,
assumeAligned(AlignmentAPI->getZExtValue()));
6951 unsigned AS =
DL.getAllocaAddrSpace();
6953 new AllocaInst(Type::getInt8Ty(
F->getContext()), AS,
Size, Alignment,
6954 AI.CB->getName() +
".h2s", IP);
6956 if (Alloca->
getType() != AI.CB->getType())
6957 Alloca = BitCastInst::CreatePointerBitCastOrAddrSpaceCast(
6958 Alloca, AI.CB->getType(),
"malloc_cast", AI.CB->getIterator());
6960 auto *I8Ty = Type::getInt8Ty(
F->getContext());
6963 "Must be able to materialize initial memory state of allocation");
6968 auto *NBB =
II->getNormalDest();
6970 A.deleteAfterManifest(*AI.CB);
6972 A.deleteAfterManifest(*AI.CB);
6981 Builder.CreateMemSet(Alloca, InitVal,
Size, std::nullopt);
6983 HasChanged = ChangeStatus::CHANGED;
6989 std::optional<APInt> getAPInt(Attributor &
A,
const AbstractAttribute &AA,
6991 bool UsedAssumedInformation =
false;
6992 std::optional<Constant *> SimpleV =
6993 A.getAssumedConstant(V, AA, UsedAssumedInformation);
6995 return APInt(64, 0);
6997 return CI->getValue();
6998 return std::nullopt;
7001 std::optional<APInt>
getSize(Attributor &
A,
const AbstractAttribute &AA,
7002 AllocationInfo &AI) {
7004 bool UsedAssumedInformation =
false;
7005 if (std::optional<Constant *> SimpleV =
7006 A.getAssumedConstant(*V, AA, UsedAssumedInformation))
7013 const auto *TLI =
A.getInfoCache().getTargetLibraryInfoForFunction(*
F);
7019 MapVector<CallBase *, AllocationInfo *> AllocationInfos;
7023 MapVector<CallBase *, DeallocationInfo *> DeallocationInfos;
7028ChangeStatus AAHeapToStackFunction::updateImpl(Attributor &
A) {
7031 const auto *TLI =
A.getInfoCache().getTargetLibraryInfoForFunction(*
F);
7033 const auto *LivenessAA =
7036 MustBeExecutedContextExplorer *Explorer =
7037 A.getInfoCache().getMustBeExecutedContextExplorer();
7039 bool StackIsAccessibleByOtherThreads =
7040 A.getInfoCache().stackIsAccessibleByOtherThreads();
7043 A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(*F);
7044 std::optional<bool> MayContainIrreducibleControl;
7046 if (&
F->getEntryBlock() == &BB)
7048 if (!MayContainIrreducibleControl.has_value())
7050 if (*MayContainIrreducibleControl)
7059 bool HasUpdatedFrees =
false;
7061 auto UpdateFrees = [&]() {
7062 HasUpdatedFrees =
true;
7064 for (
auto &It : DeallocationInfos) {
7065 DeallocationInfo &DI = *It.second;
7068 if (DI.MightFreeUnknownObjects)
7072 bool UsedAssumedInformation =
false;
7073 if (
A.isAssumedDead(*DI.CB,
this, LivenessAA, UsedAssumedInformation,
7080 LLVM_DEBUG(
dbgs() <<
"[H2S] Unknown underlying object for free!\n");
7081 DI.MightFreeUnknownObjects =
true;
7094 DI.MightFreeUnknownObjects =
true;
7098 AllocationInfo *AI = AllocationInfos.lookup(ObjCB);
7100 LLVM_DEBUG(
dbgs() <<
"[H2S] Free of a non-allocation object: " << *Obj
7102 DI.MightFreeUnknownObjects =
true;
7106 DI.PotentialAllocationCalls.insert(ObjCB);
7110 auto FreeCheck = [&](AllocationInfo &AI) {
7114 if (!StackIsAccessibleByOtherThreads) {
7119 dbgs() <<
"[H2S] found an escaping use, stack is not accessible by "
7120 "other threads and function is not nosync:\n");
7124 if (!HasUpdatedFrees)
7128 if (AI.PotentialFreeCalls.size() != 1) {
7130 << AI.PotentialFreeCalls.size() <<
"\n");
7133 CallBase *UniqueFree = *AI.PotentialFreeCalls.begin();
7134 DeallocationInfo *DI = DeallocationInfos.lookup(UniqueFree);
7137 dbgs() <<
"[H2S] unique free call was not known as deallocation call "
7138 << *UniqueFree <<
"\n");
7141 if (DI->MightFreeUnknownObjects) {
7143 dbgs() <<
"[H2S] unique free call might free unknown allocations\n");
7146 if (DI->PotentialAllocationCalls.empty())
7148 if (DI->PotentialAllocationCalls.size() > 1) {
7150 << DI->PotentialAllocationCalls.size()
7151 <<
" different allocations\n");
7154 if (*DI->PotentialAllocationCalls.begin() != AI.CB) {
7157 <<
"[H2S] unique free call not known to free this allocation but "
7158 << **DI->PotentialAllocationCalls.begin() <<
"\n");
7163 if (!AI.IsGlobalizedLocal) {
7165 if (!Explorer || !Explorer->findInContextOf(UniqueFree, CtxI)) {
7166 LLVM_DEBUG(
dbgs() <<
"[H2S] unique free call might not be executed "
7167 "with the allocation "
7168 << *UniqueFree <<
"\n");
7175 auto UsesCheck = [&](AllocationInfo &AI) {
7176 bool ValidUsesOnly =
true;
7178 auto Pred = [&](
const Use &
U,
bool &Follow) ->
bool {
7183 if (
SI->getValueOperand() ==
U.get()) {
7185 <<
"[H2S] escaping store to memory: " << *UserI <<
"\n");
7186 ValidUsesOnly =
false;
7195 if (DeallocationInfos.count(CB)) {
7196 AI.PotentialFreeCalls.insert(CB);
7203 bool IsKnownNoCapture;
7212 if (!IsAssumedNoCapture ||
7213 (!AI.IsGlobalizedLocal && !IsAssumedNoFree)) {
7214 AI.HasPotentiallyFreeingUnknownUses |= !IsAssumedNoFree;
7217 auto Remark = [&](OptimizationRemarkMissed ORM) {
7219 <<
"Could not move globalized variable to the stack. "
7220 "Variable is potentially captured in call. Mark "
7221 "parameter as `__attribute__((noescape))` to override.";
7224 if (ValidUsesOnly && AI.IsGlobalizedLocal)
7225 A.emitRemark<OptimizationRemarkMissed>(CB,
"OMP113",
Remark);
7228 ValidUsesOnly =
false;
7241 ValidUsesOnly =
false;
7244 if (!
A.checkForAllUses(Pred, *
this, *AI.CB,
false,
7246 [&](
const Use &OldU,
const Use &NewU) {
7247 auto *SI = dyn_cast<StoreInst>(OldU.getUser());
7248 return !SI || StackIsAccessibleByOtherThreads ||
7249 AA::isAssumedThreadLocalObject(
7250 A, *SI->getPointerOperand(), *this);
7253 return ValidUsesOnly;
7258 for (
auto &It : AllocationInfos) {
7259 AllocationInfo &AI = *It.second;
7260 if (AI.Status == AllocationInfo::INVALID)
7264 std::optional<APInt> APAlign = getAPInt(
A, *
this, *Align);
7268 LLVM_DEBUG(
dbgs() <<
"[H2S] Unknown allocation alignment: " << *AI.CB
7270 AI.Status = AllocationInfo::INVALID;
7275 !APAlign->isPowerOf2()) {
7276 LLVM_DEBUG(
dbgs() <<
"[H2S] Invalid allocation alignment: " << APAlign
7278 AI.Status = AllocationInfo::INVALID;
7289 dbgs() <<
"[H2S] Unknown allocation size: " << *AI.CB <<
"\n";
7291 dbgs() <<
"[H2S] Allocation size too large: " << *AI.CB <<
" vs. "
7295 AI.Status = AllocationInfo::INVALID;
7301 switch (AI.Status) {
7302 case AllocationInfo::STACK_DUE_TO_USE:
7305 AI.Status = AllocationInfo::STACK_DUE_TO_FREE;
7307 case AllocationInfo::STACK_DUE_TO_FREE:
7310 AI.Status = AllocationInfo::INVALID;
7313 case AllocationInfo::INVALID:
7320 bool IsGlobalizedLocal = AI.IsGlobalizedLocal;
7321 if (AI.MoveAllocaIntoEntry &&
7322 (!
Size.has_value() ||
7323 (!IsGlobalizedLocal && IsInLoop(*AI.CB->getParent()))))
7324 AI.MoveAllocaIntoEntry =
false;
7333struct AAPrivatizablePtrImpl :
public AAPrivatizablePtr {
7334 AAPrivatizablePtrImpl(
const IRPosition &IRP, Attributor &
A)
7335 : AAPrivatizablePtr(IRP,
A), PrivatizableType(std::nullopt) {}
7338 AAPrivatizablePtr::indicatePessimisticFixpoint();
7339 PrivatizableType =
nullptr;
7340 return ChangeStatus::CHANGED;
7346 virtual std::optional<Type *> identifyPrivatizableType(Attributor &
A) = 0;
7350 std::optional<Type *> combineTypes(std::optional<Type *> T0,
7351 std::optional<Type *>
T1) {
7361 std::optional<Type *> getPrivatizableType()
const override {
7362 return PrivatizableType;
7365 const std::string getAsStr(Attributor *
A)
const override {
7366 return isAssumedPrivatizablePtr() ?
"[priv]" :
"[no-priv]";
7370 std::optional<Type *> PrivatizableType;
7375struct AAPrivatizablePtrArgument final :
public AAPrivatizablePtrImpl {
7376 AAPrivatizablePtrArgument(
const IRPosition &IRP, Attributor &
A)
7377 : AAPrivatizablePtrImpl(IRP,
A) {}
7380 std::optional<Type *> identifyPrivatizableType(Attributor &
A)
override {
7383 bool UsedAssumedInformation =
false;
7385 A.getAttrs(getIRPosition(), {Attribute::ByVal},
Attrs,
7387 if (!
Attrs.empty() &&
7388 A.checkForAllCallSites([](AbstractCallSite ACS) { return true; }, *
this,
7389 true, UsedAssumedInformation))
7390 return Attrs[0].getValueAsType();
7392 std::optional<Type *> Ty;
7393 unsigned ArgNo = getIRPosition().getCallSiteArgNo();
7401 auto CallSiteCheck = [&](AbstractCallSite ACS) {
7410 A.getAAFor<AAPrivatizablePtr>(*
this, ACSArgPos, DepClassTy::REQUIRED);
7413 std::optional<Type *> CSTy = PrivCSArgAA->getPrivatizableType();
7416 dbgs() <<
"[AAPrivatizablePtr] ACSPos: " << ACSArgPos <<
", CSTy: ";
7420 dbgs() <<
"<nullptr>";
7425 Ty = combineTypes(Ty, CSTy);
7428 dbgs() <<
" : New Type: ";
7430 (*Ty)->print(
dbgs());
7432 dbgs() <<
"<nullptr>";
7441 if (!
A.checkForAllCallSites(CallSiteCheck, *
this,
true,
7442 UsedAssumedInformation))
7449 PrivatizableType = identifyPrivatizableType(
A);
7450 if (!PrivatizableType)
7451 return ChangeStatus::UNCHANGED;
7452 if (!*PrivatizableType)
7453 return indicatePessimisticFixpoint();
7458 DepClassTy::OPTIONAL);
7461 if (!
A.hasAttr(getIRPosition(), Attribute::ByVal) &&
7464 return indicatePessimisticFixpoint();
7470 identifyReplacementTypes(*PrivatizableType, ReplacementTypes);
7474 Function &Fn = *getIRPosition().getAnchorScope();
7476 A.getInfoCache().getAnalysisResultForFunction<TargetIRAnalysis>(Fn);
7478 LLVM_DEBUG(
dbgs() <<
"[AAPrivatizablePtr] Missing TTI for function "
7480 return indicatePessimisticFixpoint();
7483 auto CallSiteCheck = [&](AbstractCallSite ACS) {
7490 bool UsedAssumedInformation =
false;
7491 if (!
A.checkForAllCallSites(CallSiteCheck, *
this,
true,
7492 UsedAssumedInformation)) {
7494 dbgs() <<
"[AAPrivatizablePtr] ABI incompatibility detected for "
7496 return indicatePessimisticFixpoint();
7500 Argument *Arg = getAssociatedArgument();
7501 if (!
A.isValidFunctionSignatureRewrite(*Arg, ReplacementTypes)) {
7503 return indicatePessimisticFixpoint();
7510 auto IsCompatiblePrivArgOfCallback = [&](CallBase &CB) {
7513 for (
const Use *U : CallbackUses) {
7514 AbstractCallSite CBACS(U);
7515 assert(CBACS && CBACS.isCallbackCall());
7516 for (Argument &CBArg : CBACS.getCalledFunction()->args()) {
7517 int CBArgNo = CBACS.getCallArgOperandNo(CBArg);
7521 <<
"[AAPrivatizablePtr] Argument " << *Arg
7522 <<
"check if can be privatized in the context of its parent ("
7524 <<
")\n[AAPrivatizablePtr] because it is an argument in a "
7526 << CBArgNo <<
"@" << CBACS.getCalledFunction()->getName()
7527 <<
")\n[AAPrivatizablePtr] " << CBArg <<
" : "
7528 << CBACS.getCallArgOperand(CBArg) <<
" vs "
7530 <<
"[AAPrivatizablePtr] " << CBArg <<
" : "
7531 << CBACS.getCallArgOperandNo(CBArg) <<
" vs " << ArgNo <<
"\n";
7534 if (CBArgNo !=
int(ArgNo))
7536 const auto *CBArgPrivAA =
A.getAAFor<AAPrivatizablePtr>(
7538 if (CBArgPrivAA && CBArgPrivAA->isValidState()) {
7539 auto CBArgPrivTy = CBArgPrivAA->getPrivatizableType();
7542 if (*CBArgPrivTy == PrivatizableType)
7547 dbgs() <<
"[AAPrivatizablePtr] Argument " << *Arg
7548 <<
" cannot be privatized in the context of its parent ("
7550 <<
")\n[AAPrivatizablePtr] because it is an argument in a "
7552 << CBArgNo <<
"@" << CBACS.getCalledFunction()->getName()
7553 <<
").\n[AAPrivatizablePtr] for which the argument "
7554 "privatization is not compatible.\n";
7564 auto IsCompatiblePrivArgOfDirectCS = [&](AbstractCallSite ACS) {
7568 "Expected a direct call operand for callback call operand");
7573 dbgs() <<
"[AAPrivatizablePtr] Argument " << *Arg
7574 <<
" check if be privatized in the context of its parent ("
7576 <<
")\n[AAPrivatizablePtr] because it is an argument in a "
7578 << DCArgNo <<
"@" << DCCallee->
getName() <<
").\n";
7581 if (
unsigned(DCArgNo) < DCCallee->
arg_size()) {
7582 const auto *DCArgPrivAA =
A.getAAFor<AAPrivatizablePtr>(
7584 DepClassTy::REQUIRED);
7585 if (DCArgPrivAA && DCArgPrivAA->isValidState()) {
7586 auto DCArgPrivTy = DCArgPrivAA->getPrivatizableType();
7589 if (*DCArgPrivTy == PrivatizableType)
7595 dbgs() <<
"[AAPrivatizablePtr] Argument " << *Arg
7596 <<
" cannot be privatized in the context of its parent ("
7598 <<
")\n[AAPrivatizablePtr] because it is an argument in a "
7601 <<
").\n[AAPrivatizablePtr] for which the argument "
7602 "privatization is not compatible.\n";
7610 auto IsCompatiblePrivArgOfOtherCallSite = [&](AbstractCallSite ACS) {
7614 return IsCompatiblePrivArgOfDirectCS(ACS);
7618 if (!
A.checkForAllCallSites(IsCompatiblePrivArgOfOtherCallSite, *
this,
true,
7619 UsedAssumedInformation))
7620 return indicatePessimisticFixpoint();
7622 return ChangeStatus::UNCHANGED;
7628 identifyReplacementTypes(
Type *PrivType,
7629 SmallVectorImpl<Type *> &ReplacementTypes) {
7632 assert(PrivType &&
"Expected privatizable type!");
7636 for (
unsigned u = 0, e = PrivStructType->getNumElements(); u < e; u++)
7637 ReplacementTypes.
push_back(PrivStructType->getElementType(u));
7639 ReplacementTypes.
append(PrivArrayType->getNumElements(),
7640 PrivArrayType->getElementType());
7651 assert(PrivType &&
"Expected privatizable type!");
7654 const DataLayout &
DL =
F.getDataLayout();
7658 const StructLayout *PrivStructLayout =
DL.getStructLayout(PrivStructType);
7659 for (
unsigned u = 0, e = PrivStructType->getNumElements(); u < e; u++) {
7662 new StoreInst(
F.getArg(ArgNo + u), Ptr, IP);
7665 Type *PointeeTy = PrivArrayType->getElementType();
7666 uint64_t PointeeTySize =
DL.getTypeStoreSize(PointeeTy);
7667 for (
unsigned u = 0, e = PrivArrayType->getNumElements(); u < e; u++) {
7669 new StoreInst(
F.getArg(ArgNo + u), Ptr, IP);
7672 new StoreInst(
F.getArg(ArgNo), &
Base, IP);
7678 void createReplacementValues(Align Alignment,
Type *PrivType,
7680 SmallVectorImpl<Value *> &ReplacementValues) {
7682 assert(PrivType &&
"Expected privatizable type!");
7690 const StructLayout *PrivStructLayout =
DL.getStructLayout(PrivStructType);
7691 for (
unsigned u = 0, e = PrivStructType->getNumElements(); u < e; u++) {
7692 Type *PointeeTy = PrivStructType->getElementType(u);
7695 LoadInst *
L =
new LoadInst(PointeeTy, Ptr,
"", IP->
getIterator());
7696 L->setAlignment(Alignment);
7700 Type *PointeeTy = PrivArrayType->getElementType();
7701 uint64_t PointeeTySize =
DL.getTypeStoreSize(PointeeTy);
7702 for (
unsigned u = 0, e = PrivArrayType->getNumElements(); u < e; u++) {
7704 LoadInst *
L =
new LoadInst(PointeeTy, Ptr,
"", IP->
getIterator());
7705 L->setAlignment(Alignment);
7710 L->setAlignment(Alignment);
7717 if (!PrivatizableType)
7718 return ChangeStatus::UNCHANGED;
7719 assert(*PrivatizableType &&
"Expected privatizable type!");
7725 bool UsedAssumedInformation =
false;
7726 if (!
A.checkForAllInstructions(
7727 [&](Instruction &
I) {
7728 CallInst &CI = cast<CallInst>(I);
7729 if (CI.isTailCall())
7730 TailCalls.push_back(&CI);
7733 *
this, {Instruction::Call}, UsedAssumedInformation))
7734 return ChangeStatus::UNCHANGED;
7736 Argument *Arg = getAssociatedArgument();
7739 const auto *AlignAA =
7746 [=](
const Attributor::ArgumentReplacementInfo &ARI,
7748 BasicBlock &EntryBB = ReplacementFn.getEntryBlock();
7750 const DataLayout &
DL = IP->getDataLayout();
7751 unsigned AS =
DL.getAllocaAddrSpace();
7752 Instruction *AI =
new AllocaInst(*PrivatizableType, AS,
7753 Arg->
getName() +
".priv", IP);
7754 createInitialization(*PrivatizableType, *AI, ReplacementFn,
7755 ArgIt->getArgNo(), IP);
7758 AI = BitCastInst::CreatePointerBitCastOrAddrSpaceCast(
7762 for (CallInst *CI : TailCalls)
7763 CI->setTailCall(
false);
7770 [=](
const Attributor::ArgumentReplacementInfo &ARI,
7771 AbstractCallSite ACS, SmallVectorImpl<Value *> &NewArgOperands) {
7774 createReplacementValues(
7775 AlignAA ? AlignAA->getAssumedAlign() :
Align(0),
7776 *PrivatizableType, ACS,
7784 identifyReplacementTypes(*PrivatizableType, ReplacementTypes);
7787 if (
A.registerFunctionSignatureRewrite(*Arg, ReplacementTypes,
7788 std::move(FnRepairCB),
7789 std::move(ACSRepairCB)))
7790 return ChangeStatus::CHANGED;
7791 return ChangeStatus::UNCHANGED;
7795 void trackStatistics()
const override {
7800struct AAPrivatizablePtrFloating :
public AAPrivatizablePtrImpl {
7801 AAPrivatizablePtrFloating(
const IRPosition &IRP, Attributor &
A)
7802 : AAPrivatizablePtrImpl(IRP,
A) {}
7807 indicatePessimisticFixpoint();
7812 "updateImpl will not be called");
7816 std::optional<Type *> identifyPrivatizableType(Attributor &
A)
override {
7819 LLVM_DEBUG(
dbgs() <<
"[AAPrivatizablePtr] No underlying object found!\n");
7826 return AI->getAllocatedType();
7828 auto *PrivArgAA =
A.getAAFor<AAPrivatizablePtr>(
7830 if (PrivArgAA && PrivArgAA->isAssumedPrivatizablePtr())
7831 return PrivArgAA->getPrivatizableType();
7834 LLVM_DEBUG(
dbgs() <<
"[AAPrivatizablePtr] Underlying object neither valid "
7835 "alloca nor privatizable argument: "
7841 void trackStatistics()
const override {
7846struct AAPrivatizablePtrCallSiteArgument final
7847 :
public AAPrivatizablePtrFloating {
7848 AAPrivatizablePtrCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
7849 : AAPrivatizablePtrFloating(IRP,
A) {}
7853 if (
A.hasAttr(getIRPosition(), Attribute::ByVal))
7854 indicateOptimisticFixpoint();
7859 PrivatizableType = identifyPrivatizableType(
A);
7860 if (!PrivatizableType)
7861 return ChangeStatus::UNCHANGED;
7862 if (!*PrivatizableType)
7863 return indicatePessimisticFixpoint();
7865 const IRPosition &IRP = getIRPosition();
7866 bool IsKnownNoCapture;
7868 A,
this, IRP, DepClassTy::REQUIRED, IsKnownNoCapture);
7869 if (!IsAssumedNoCapture) {
7870 LLVM_DEBUG(
dbgs() <<
"[AAPrivatizablePtr] pointer might be captured!\n");
7871 return indicatePessimisticFixpoint();
7874 bool IsKnownNoAlias;
7876 A,
this, IRP, DepClassTy::REQUIRED, IsKnownNoAlias)) {
7877 LLVM_DEBUG(
dbgs() <<
"[AAPrivatizablePtr] pointer might alias!\n");
7878 return indicatePessimisticFixpoint();
7883 LLVM_DEBUG(
dbgs() <<
"[AAPrivatizablePtr] pointer is written!\n");
7884 return indicatePessimisticFixpoint();
7887 return ChangeStatus::UNCHANGED;
7891 void trackStatistics()
const override {
7896struct AAPrivatizablePtrCallSiteReturned final
7897 :
public AAPrivatizablePtrFloating {
7898 AAPrivatizablePtrCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
7899 : AAPrivatizablePtrFloating(IRP,
A) {}
7904 indicatePessimisticFixpoint();
7908 void trackStatistics()
const override {
7913struct AAPrivatizablePtrReturned final :
public AAPrivatizablePtrFloating {
7914 AAPrivatizablePtrReturned(
const IRPosition &IRP, Attributor &
A)
7915 : AAPrivatizablePtrFloating(IRP,
A) {}
7920 indicatePessimisticFixpoint();
7924 void trackStatistics()
const override {
7934struct AAMemoryBehaviorImpl :
public AAMemoryBehavior {
7935 AAMemoryBehaviorImpl(
const IRPosition &IRP, Attributor &
A)
7936 : AAMemoryBehavior(IRP,
A) {}
7940 intersectAssumedBits(BEST_STATE);
7941 getKnownStateFromValue(
A, getIRPosition(), getState());
7942 AAMemoryBehavior::initialize(
A);
7946 static void getKnownStateFromValue(Attributor &
A,
const IRPosition &IRP,
7947 BitIntegerState &State,
7948 bool IgnoreSubsumingPositions =
false) {
7950 A.getAttrs(IRP, AttrKinds, Attrs, IgnoreSubsumingPositions);
7952 switch (Attr.getKindAsEnum()) {
7953 case Attribute::ReadNone:
7956 case Attribute::ReadOnly:
7959 case Attribute::WriteOnly:
7968 if (!
I->mayReadFromMemory())
7970 if (!
I->mayWriteToMemory())
7976 void getDeducedAttributes(Attributor &
A, LLVMContext &Ctx,
7977 SmallVectorImpl<Attribute> &Attrs)
const override {
7980 Attrs.push_back(Attribute::get(Ctx, Attribute::ReadNone));
7982 Attrs.push_back(Attribute::get(Ctx, Attribute::ReadOnly));
7983 else if (isAssumedWriteOnly())
7984 Attrs.push_back(Attribute::get(Ctx, Attribute::WriteOnly));
7990 const IRPosition &IRP = getIRPosition();
7992 if (
A.hasAttr(IRP, Attribute::ReadNone,
7994 return ChangeStatus::UNCHANGED;
8003 return ChangeStatus::UNCHANGED;
8006 A.removeAttrs(IRP, AttrKinds);
8009 A.removeAttrs(IRP, Attribute::Writable);
8016 const std::string getAsStr(Attributor *
A)
const override {
8021 if (isAssumedWriteOnly())
8023 return "may-read/write";
8027 static const Attribute::AttrKind AttrKinds[3];
8031 Attribute::ReadNone, Attribute::ReadOnly, Attribute::WriteOnly};
8034struct AAMemoryBehaviorFloating : AAMemoryBehaviorImpl {
8035 AAMemoryBehaviorFloating(
const IRPosition &IRP, Attributor &
A)
8036 : AAMemoryBehaviorImpl(IRP,
A) {}
8042 void trackStatistics()
const override {
8047 else if (isAssumedWriteOnly())
8054 bool followUsersOfUseIn(Attributor &
A,
const Use &U,
8055 const Instruction *UserI);
8058 void analyzeUseIn(Attributor &
A,
const Use &U,
const Instruction *UserI);
8062struct AAMemoryBehaviorArgument : AAMemoryBehaviorFloating {
8063 AAMemoryBehaviorArgument(
const IRPosition &IRP, Attributor &
A)
8064 : AAMemoryBehaviorFloating(IRP,
A) {}
8068 intersectAssumedBits(BEST_STATE);
8069 const IRPosition &IRP = getIRPosition();
8073 bool HasByVal =
A.hasAttr(IRP, {Attribute::ByVal},
8075 getKnownStateFromValue(
A, IRP, getState(),
8082 return ChangeStatus::UNCHANGED;
8086 if (
A.hasAttr(getIRPosition(),
8087 {Attribute::InAlloca, Attribute::Preallocated})) {
8088 removeKnownBits(NO_WRITES);
8089 removeAssumedBits(NO_WRITES);
8091 A.removeAttrs(getIRPosition(), AttrKinds);
8092 return AAMemoryBehaviorFloating::manifest(
A);
8096 void trackStatistics()
const override {
8101 else if (isAssumedWriteOnly())
8106struct AAMemoryBehaviorCallSiteArgument final : AAMemoryBehaviorArgument {
8107 AAMemoryBehaviorCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
8108 : AAMemoryBehaviorArgument(IRP,
A) {}
8114 Argument *Arg = getAssociatedArgument();
8116 indicatePessimisticFixpoint();
8120 addKnownBits(NO_WRITES);
8121 removeKnownBits(NO_READS);
8122 removeAssumedBits(NO_READS);
8124 AAMemoryBehaviorArgument::initialize(
A);
8125 if (getAssociatedFunction()->isDeclaration())
8126 indicatePessimisticFixpoint();
8135 Argument *Arg = getAssociatedArgument();
8138 A.getAAFor<AAMemoryBehavior>(*
this, ArgPos, DepClassTy::REQUIRED);
8140 return indicatePessimisticFixpoint();
8145 void trackStatistics()
const override {
8150 else if (isAssumedWriteOnly())
8156struct AAMemoryBehaviorCallSiteReturned final : AAMemoryBehaviorFloating {
8157 AAMemoryBehaviorCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
8158 : AAMemoryBehaviorFloating(IRP,
A) {}
8162 AAMemoryBehaviorImpl::initialize(
A);
8167 return ChangeStatus::UNCHANGED;
8171 void trackStatistics()
const override {}
8175struct AAMemoryBehaviorFunction final :
public AAMemoryBehaviorImpl {
8176 AAMemoryBehaviorFunction(
const IRPosition &IRP, Attributor &
A)
8177 : AAMemoryBehaviorImpl(IRP,
A) {}
8193 else if (isAssumedWriteOnly())
8196 A.removeAttrs(getIRPosition(), AttrKinds);
8199 for (Argument &Arg :
F.args())
8201 return A.manifestAttrs(getIRPosition(),
8202 Attribute::getWithMemoryEffects(
F.getContext(), ME));
8206 void trackStatistics()
const override {
8211 else if (isAssumedWriteOnly())
8217struct AAMemoryBehaviorCallSite final
8218 : AACalleeToCallSite<AAMemoryBehavior, AAMemoryBehaviorImpl> {
8219 AAMemoryBehaviorCallSite(
const IRPosition &IRP, Attributor &
A)
8220 : AACalleeToCallSite<AAMemoryBehavior, AAMemoryBehaviorImpl>(IRP,
A) {}
8231 else if (isAssumedWriteOnly())
8234 A.removeAttrs(getIRPosition(), AttrKinds);
8237 for (Use &U : CB.
args())
8239 Attribute::Writable);
8240 return A.manifestAttrs(
8241 getIRPosition(), Attribute::getWithMemoryEffects(CB.
getContext(), ME));
8245 void trackStatistics()
const override {
8250 else if (isAssumedWriteOnly())
8255ChangeStatus AAMemoryBehaviorFunction::updateImpl(Attributor &
A) {
8258 auto AssumedState = getAssumed();
8265 const auto *MemBehaviorAA =
A.getAAFor<AAMemoryBehavior>(
8267 if (MemBehaviorAA) {
8268 intersectAssumedBits(MemBehaviorAA->
getAssumed());
8269 return !isAtFixpoint();
8274 if (
I.mayReadFromMemory())
8275 removeAssumedBits(NO_READS);
8276 if (
I.mayWriteToMemory())
8277 removeAssumedBits(NO_WRITES);
8278 return !isAtFixpoint();
8281 bool UsedAssumedInformation =
false;
8282 if (!
A.checkForAllReadWriteInstructions(CheckRWInst, *
this,
8283 UsedAssumedInformation))
8284 return indicatePessimisticFixpoint();
8290ChangeStatus AAMemoryBehaviorFloating::updateImpl(Attributor &
A) {
8292 const IRPosition &IRP = getIRPosition();
8303 const auto *FnMemAA =
8306 FnMemAssumedState = FnMemAA->getAssumed();
8307 S.addKnownBits(FnMemAA->getKnown());
8308 if ((S.getAssumed() & FnMemAA->getAssumed()) == S.getAssumed())
8314 auto AssumedState = S.getAssumed();
8320 bool IsKnownNoCapture;
8321 const AANoCapture *ArgNoCaptureAA =
nullptr;
8326 if (!IsAssumedNoCapture &&
8328 S.intersectAssumedBits(FnMemAssumedState);
8334 auto UsePred = [&](
const Use &
U,
bool &Follow) ->
bool {
8336 LLVM_DEBUG(
dbgs() <<
"[AAMemoryBehavior] Use: " << *U <<
" in " << *UserI
8344 Follow = followUsersOfUseIn(
A, U, UserI);
8348 analyzeUseIn(
A, U, UserI);
8350 return !isAtFixpoint();
8353 if (!
A.checkForAllUses(UsePred, *
this, getAssociatedValue()))
8354 return indicatePessimisticFixpoint();
8360bool AAMemoryBehaviorFloating::followUsersOfUseIn(Attributor &
A,
const Use &U,
8361 const Instruction *UserI) {
8379 if (
U.get()->getType()->isPointerTy()) {
8381 bool IsKnownNoCapture;
8390void AAMemoryBehaviorFloating::analyzeUseIn(Attributor &
A,
const Use &U,
8391 const Instruction *UserI) {
8398 case Instruction::Load:
8400 removeAssumedBits(NO_READS);
8403 case Instruction::Store:
8408 removeAssumedBits(NO_WRITES);
8410 indicatePessimisticFixpoint();
8413 case Instruction::Call:
8414 case Instruction::CallBr:
8415 case Instruction::Invoke: {
8422 indicatePessimisticFixpoint();
8429 removeAssumedBits(NO_READS);
8436 if (
U.get()->getType()->isPointerTy())
8440 const auto *MemBehaviorAA =
8446 intersectAssumedBits(MemBehaviorAA->
getAssumed());
8454 removeAssumedBits(NO_READS);
8456 removeAssumedBits(NO_WRITES);
8468 return "all memory";
8471 std::string S =
"memory:";
8477 S +=
"internal global,";
8479 S +=
"external global,";
8483 S +=
"inaccessible,";
8497 AccessKind2Accesses.fill(
nullptr);
8500 ~AAMemoryLocationImpl()
override {
8503 for (AccessSet *AS : AccessKind2Accesses)
8510 intersectAssumedBits(BEST_STATE);
8511 getKnownStateFromValue(
A, getIRPosition(), getState());
8512 AAMemoryLocation::initialize(
A);
8516 static void getKnownStateFromValue(Attributor &
A,
const IRPosition &IRP,
8517 BitIntegerState &State,
8518 bool IgnoreSubsumingPositions =
false) {
8527 bool UseArgMemOnly =
true;
8529 if (AnchorFn &&
A.isRunOn(*AnchorFn))
8533 A.getAttrs(IRP, {Attribute::Memory},
Attrs, IgnoreSubsumingPositions);
8542 State.
addKnownBits(inverseLocation(NO_INACCESSIBLE_MEM,
true,
true));
8547 State.
addKnownBits(inverseLocation(NO_ARGUMENT_MEM,
true,
true));
8551 A.manifestAttrs(IRP,
8552 Attribute::getWithMemoryEffects(
8561 NO_INACCESSIBLE_MEM | NO_ARGUMENT_MEM,
true,
true));
8565 A.manifestAttrs(IRP,
8566 Attribute::getWithMemoryEffects(
8576 void getDeducedAttributes(Attributor &
A, LLVMContext &Ctx,
8577 SmallVectorImpl<Attribute> &Attrs)
const override {
8584 else if (isAssumedInaccessibleMemOnly())
8585 Attrs.push_back(Attribute::getWithMemoryEffects(
8587 else if (isAssumedArgMemOnly())
8590 else if (isAssumedInaccessibleOrArgMemOnly())
8591 Attrs.push_back(Attribute::getWithMemoryEffects(
8601 const IRPosition &IRP = getIRPosition();
8605 if (DeducedAttrs.
size() != 1)
8606 return ChangeStatus::UNCHANGED;
8609 return A.manifestAttrs(IRP, Attribute::getWithMemoryEffects(
8614 bool checkForAllAccessesToMemoryKind(
8616 MemoryLocationsKind)>
8618 MemoryLocationsKind RequestedMLK)
const override {
8619 if (!isValidState())
8622 MemoryLocationsKind AssumedMLK = getAssumedNotAccessedLocation();
8623 if (AssumedMLK == NO_LOCATIONS)
8627 for (MemoryLocationsKind CurMLK = 1; CurMLK < NO_LOCATIONS;
8628 CurMLK *= 2, ++Idx) {
8629 if (CurMLK & RequestedMLK)
8632 if (
const AccessSet *
Accesses = AccessKind2Accesses[Idx])
8633 for (
const AccessInfo &AI : *
Accesses)
8634 if (!Pred(AI.I, AI.Ptr, AI.Kind, CurMLK))
8647 MemoryLocationsKind KnownMLK = getKnown();
8649 for (MemoryLocationsKind CurMLK = 1; CurMLK < NO_LOCATIONS; CurMLK *= 2)
8650 if (!(CurMLK & KnownMLK))
8651 updateStateAndAccessesMap(getState(), CurMLK,
I,
nullptr,
Changed,
8652 getAccessKindFromInst(
I));
8653 return AAMemoryLocation::indicatePessimisticFixpoint();
8673 bool operator()(
const AccessInfo &
LHS,
const AccessInfo &
RHS)
const {
8677 return LHS.Ptr <
RHS.Ptr;
8678 if (
LHS.Kind !=
RHS.Kind)
8679 return LHS.Kind <
RHS.Kind;
8686 using AccessSet = SmallSet<AccessInfo, 2, AccessInfo>;
8687 std::array<AccessSet *, llvm::ConstantLog2<VALID_STATE>()>
8688 AccessKind2Accesses;
8693 categorizeArgumentPointerLocations(Attributor &
A, CallBase &CB,
8694 AAMemoryLocation::StateType &AccessedLocs,
8699 categorizeAccessedLocations(Attributor &
A, Instruction &
I,
bool &
Changed);
8702 AccessKind getAccessKindFromInst(
const Instruction *
I) {
8705 AK =
I->mayReadFromMemory() ? READ :
NONE;
8714 void updateStateAndAccessesMap(AAMemoryLocation::StateType &State,
8715 MemoryLocationsKind MLK,
const Instruction *
I,
8724 if (MLK == NO_UNKOWN_MEM)
8726 State.removeAssumedBits(MLK);
8731 void categorizePtrValue(Attributor &
A,
const Instruction &
I,
const Value &Ptr,
8732 AAMemoryLocation::StateType &State,
bool &
Changed,
8733 unsigned AccessAS = 0);
8739void AAMemoryLocationImpl::categorizePtrValue(
8740 Attributor &
A,
const Instruction &
I,
const Value &Ptr,
8742 LLVM_DEBUG(
dbgs() <<
"[AAMemoryLocation] Categorize pointer locations for "
8747 unsigned ObjectAS =
Obj.getType()->getPointerAddressSpace();
8749 MemoryLocationsKind MLK = NO_LOCATIONS;
8769 MLK = NO_ARGUMENT_MEM;
8775 if (GVar->isConstant())
8778 if (GV->hasLocalLinkage())
8779 MLK = NO_GLOBAL_INTERNAL_MEM;
8781 MLK = NO_GLOBAL_EXTERNAL_MEM;
8789 bool IsKnownNoAlias;
8793 MLK = NO_MALLOCED_MEM;
8795 MLK = NO_UNKOWN_MEM;
8797 MLK = NO_UNKOWN_MEM;
8800 assert(MLK != NO_LOCATIONS &&
"No location specified!");
8801 LLVM_DEBUG(
dbgs() <<
"[AAMemoryLocation] Ptr value can be categorized: "
8802 << Obj <<
" -> " << getMemoryLocationsAsStr(MLK) <<
"\n");
8804 getAccessKindFromInst(&
I));
8809 const auto *AA =
A.getAAFor<AAUnderlyingObjects>(
8813 dbgs() <<
"[AAMemoryLocation] Pointer locations not categorized\n");
8814 updateStateAndAccessesMap(
State, NO_UNKOWN_MEM, &
I,
nullptr,
Changed,
8815 getAccessKindFromInst(&
I));
8820 dbgs() <<
"[AAMemoryLocation] Accessed locations with pointer locations: "
8824void AAMemoryLocationImpl::categorizeArgumentPointerLocations(
8827 for (
unsigned ArgNo = 0,
E = CB.
arg_size(); ArgNo <
E; ++ArgNo) {
8836 const auto *ArgOpMemLocationAA =
8839 if (ArgOpMemLocationAA && ArgOpMemLocationAA->isAssumedReadNone())
8844 categorizePtrValue(
A, CB, *ArgOp, AccessedLocs,
Changed);
8849AAMemoryLocationImpl::categorizeAccessedLocations(Attributor &
A, Instruction &
I,
8851 LLVM_DEBUG(
dbgs() <<
"[AAMemoryLocation] Categorize accessed locations for "
8855 AccessedLocs.intersectAssumedBits(NO_LOCATIONS);
8860 const auto *CBMemLocationAA =
A.getAAFor<AAMemoryLocation>(
8863 <<
" [" << CBMemLocationAA <<
"]\n");
8864 if (!CBMemLocationAA) {
8865 updateStateAndAccessesMap(AccessedLocs, NO_UNKOWN_MEM, &
I,
nullptr,
8866 Changed, getAccessKindFromInst(&
I));
8867 return NO_UNKOWN_MEM;
8870 if (CBMemLocationAA->isAssumedReadNone())
8871 return NO_LOCATIONS;
8873 if (CBMemLocationAA->isAssumedInaccessibleMemOnly()) {
8874 updateStateAndAccessesMap(AccessedLocs, NO_INACCESSIBLE_MEM, &
I,
nullptr,
8875 Changed, getAccessKindFromInst(&
I));
8876 return AccessedLocs.getAssumed();
8879 uint32_t CBAssumedNotAccessedLocs =
8880 CBMemLocationAA->getAssumedNotAccessedLocation();
8883 uint32_t CBAssumedNotAccessedLocsNoArgMem =
8884 CBAssumedNotAccessedLocs | NO_ARGUMENT_MEM | NO_GLOBAL_MEM;
8886 for (MemoryLocationsKind CurMLK = 1; CurMLK < NO_LOCATIONS; CurMLK *= 2) {
8887 if (CBAssumedNotAccessedLocsNoArgMem & CurMLK)
8889 updateStateAndAccessesMap(AccessedLocs, CurMLK, &
I,
nullptr,
Changed,
8890 getAccessKindFromInst(&
I));
8895 bool HasGlobalAccesses = ((~CBAssumedNotAccessedLocs) & NO_GLOBAL_MEM);
8896 if (HasGlobalAccesses) {
8899 updateStateAndAccessesMap(AccessedLocs, MLK, &
I, Ptr,
Changed,
8900 getAccessKindFromInst(&
I));
8903 if (!CBMemLocationAA->checkForAllAccessesToMemoryKind(
8904 AccessPred, inverseLocation(NO_GLOBAL_MEM,
false,
false)))
8905 return AccessedLocs.getWorstState();
8909 dbgs() <<
"[AAMemoryLocation] Accessed state before argument handling: "
8910 << getMemoryLocationsAsStr(AccessedLocs.getAssumed()) <<
"\n");
8913 bool HasArgAccesses = ((~CBAssumedNotAccessedLocs) & NO_ARGUMENT_MEM);
8915 categorizeArgumentPointerLocations(
A, *CB, AccessedLocs,
Changed);
8918 dbgs() <<
"[AAMemoryLocation] Accessed state after argument handling: "
8919 << getMemoryLocationsAsStr(AccessedLocs.getAssumed()) <<
"\n");
8921 return AccessedLocs.getAssumed();
8926 dbgs() <<
"[AAMemoryLocation] Categorize memory access with pointer: "
8927 <<
I <<
" [" << *Ptr <<
"]\n");
8928 categorizePtrValue(
A,
I, *Ptr, AccessedLocs,
Changed,
8929 Ptr->getType()->getPointerAddressSpace());
8930 return AccessedLocs.getAssumed();
8933 LLVM_DEBUG(
dbgs() <<
"[AAMemoryLocation] Failed to categorize instruction: "
8935 updateStateAndAccessesMap(AccessedLocs, NO_UNKOWN_MEM, &
I,
nullptr,
Changed,
8936 getAccessKindFromInst(&
I));
8937 return AccessedLocs.getAssumed();
8941struct AAMemoryLocationFunction final :
public AAMemoryLocationImpl {
8942 AAMemoryLocationFunction(
const IRPosition &IRP, Attributor &
A)
8943 : AAMemoryLocationImpl(IRP,
A) {}
8948 const auto *MemBehaviorAA =
8949 A.getAAFor<AAMemoryBehavior>(*
this, getIRPosition(), DepClassTy::NONE);
8952 return indicateOptimisticFixpoint();
8954 "AAMemoryLocation was not read-none but AAMemoryBehavior was!");
8955 A.recordDependence(*MemBehaviorAA, *
this, DepClassTy::OPTIONAL);
8956 return ChangeStatus::UNCHANGED;
8960 auto AssumedState = getAssumed();
8964 MemoryLocationsKind MLK = categorizeAccessedLocations(
A,
I,
Changed);
8965 LLVM_DEBUG(
dbgs() <<
"[AAMemoryLocation] Accessed locations for " <<
I
8966 <<
": " << getMemoryLocationsAsStr(MLK) <<
"\n");
8967 removeAssumedBits(inverseLocation(MLK,
false,
false));
8970 return getAssumedNotAccessedLocation() != VALID_STATE;
8973 bool UsedAssumedInformation =
false;
8974 if (!
A.checkForAllReadWriteInstructions(CheckRWInst, *
this,
8975 UsedAssumedInformation))
8976 return indicatePessimisticFixpoint();
8978 Changed |= AssumedState != getAssumed();
8979 return Changed ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
8983 void trackStatistics()
const override {
8986 else if (isAssumedArgMemOnly())
8988 else if (isAssumedInaccessibleMemOnly())
8990 else if (isAssumedInaccessibleOrArgMemOnly())
8996struct AAMemoryLocationCallSite final : AAMemoryLocationImpl {
8997 AAMemoryLocationCallSite(
const IRPosition &IRP, Attributor &
A)
8998 : AAMemoryLocationImpl(IRP,
A) {}
9009 A.getAAFor<AAMemoryLocation>(*
this, FnPos, DepClassTy::REQUIRED);
9011 return indicatePessimisticFixpoint();
9015 updateStateAndAccessesMap(getState(), MLK,
I, Ptr,
Changed,
9016 getAccessKindFromInst(
I));
9019 if (!FnAA->checkForAllAccessesToMemoryKind(AccessPred, ALL_LOCATIONS))
9020 return indicatePessimisticFixpoint();
9021 return Changed ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
9025 void trackStatistics()
const override {
9035struct AADenormalFPMathImpl :
public AADenormalFPMath {
9036 AADenormalFPMathImpl(
const IRPosition &IRP, Attributor &
A)
9037 : AADenormalFPMath(IRP,
A) {}
9039 const std::string getAsStr(Attributor *
A)
const override {
9040 std::string Str(
"AADenormalFPMath[");
9041 raw_string_ostream OS(Str);
9043 DenormalState
Known = getKnown();
9044 if (
Known.Mode.isValid())
9045 OS <<
"denormal-fp-math=" <<
Known.Mode;
9049 if (
Known.ModeF32.isValid())
9050 OS <<
" denormal-fp-math-f32=" <<
Known.ModeF32;
9056struct AADenormalFPMathFunction final : AADenormalFPMathImpl {
9057 AADenormalFPMathFunction(
const IRPosition &IRP, Attributor &
A)
9058 : AADenormalFPMathImpl(IRP,
A) {}
9062 DenormalFPEnv DenormEnv =
F->getDenormalFPEnv();
9072 auto CheckCallSite = [=, &Change, &
A](AbstractCallSite CS) {
9075 <<
"->" << getAssociatedFunction()->
getName() <<
'\n');
9077 const auto *CallerInfo =
A.getAAFor<AADenormalFPMath>(
9083 CallerInfo->getState());
9087 bool AllCallSitesKnown =
true;
9088 if (!
A.checkForAllCallSites(CheckCallSite, *
this,
true, AllCallSitesKnown))
9089 return indicatePessimisticFixpoint();
9091 if (Change == ChangeStatus::CHANGED && isModeFixed())
9097 LLVMContext &Ctx = getAssociatedFunction()->getContext();
9103 DenormalFPEnv KnownEnv(
Known.Mode,
Known.ModeF32);
9106 AttrToRemove.
push_back(Attribute::DenormalFPEnv);
9109 Ctx, Attribute::DenormalFPEnv,
9110 DenormalFPEnv(
Known.Mode,
Known.ModeF32).toIntValue()));
9113 auto &IRP = getIRPosition();
9116 return A.removeAttrs(IRP, AttrToRemove) |
9117 A.manifestAttrs(IRP, AttrToAdd,
true);
9120 void trackStatistics()
const override {
9129struct AAValueConstantRangeImpl : AAValueConstantRange {
9130 using StateType = IntegerRangeState;
9131 AAValueConstantRangeImpl(
const IRPosition &IRP, Attributor &
A)
9132 : AAValueConstantRange(IRP,
A) {}
9136 if (
A.hasSimplificationCallback(getIRPosition())) {
9137 indicatePessimisticFixpoint();
9142 intersectKnown(getConstantRangeFromSCEV(
A, getCtxI()));
9145 intersectKnown(getConstantRangeFromLVI(
A, getCtxI()));
9149 const std::string getAsStr(Attributor *
A)
const override {
9151 llvm::raw_string_ostream OS(Str);
9153 getKnown().print(OS);
9155 getAssumed().print(OS);
9162 const SCEV *getSCEV(Attributor &
A,
const Instruction *
I =
nullptr)
const {
9163 if (!getAnchorScope())
9166 ScalarEvolution *SE =
9167 A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(
9170 LoopInfo *LI =
A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(
9176 const SCEV *S = SE->
getSCEV(&getAssociatedValue());
9185 ConstantRange getConstantRangeFromSCEV(Attributor &
A,
9186 const Instruction *
I =
nullptr)
const {
9187 if (!getAnchorScope())
9190 ScalarEvolution *SE =
9191 A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(
9194 const SCEV *S = getSCEV(
A,
I);
9204 getConstantRangeFromLVI(Attributor &
A,
9205 const Instruction *CtxI =
nullptr)
const {
9206 if (!getAnchorScope())
9209 LazyValueInfo *LVI =
9210 A.getInfoCache().getAnalysisResultForFunction<LazyValueAnalysis>(
9225 bool isValidCtxInstructionForOutsideAnalysis(Attributor &
A,
9226 const Instruction *CtxI,
9227 bool AllowAACtxI)
const {
9228 if (!CtxI || (!AllowAACtxI && CtxI == getCtxI()))
9240 InformationCache &InfoCache =
A.getInfoCache();
9241 const DominatorTree *DT =
9252 getKnownConstantRange(Attributor &
A,
9253 const Instruction *CtxI =
nullptr)
const override {
9254 if (!isValidCtxInstructionForOutsideAnalysis(
A, CtxI,
9258 ConstantRange LVIR = getConstantRangeFromLVI(
A, CtxI);
9259 ConstantRange SCEVR = getConstantRangeFromSCEV(
A, CtxI);
9260 return getKnown().intersectWith(SCEVR).intersectWith(LVIR);
9265 getAssumedConstantRange(Attributor &
A,
9266 const Instruction *CtxI =
nullptr)
const override {
9271 if (!isValidCtxInstructionForOutsideAnalysis(
A, CtxI,
9273 return getAssumed();
9275 ConstantRange LVIR = getConstantRangeFromLVI(
A, CtxI);
9276 ConstantRange SCEVR = getConstantRangeFromSCEV(
A, CtxI);
9277 return getAssumed().intersectWith(SCEVR).intersectWith(LVIR);
9282 getMDNodeForConstantRange(
Type *Ty, LLVMContext &Ctx,
9283 const ConstantRange &AssumedConstantRange) {
9285 Ty, AssumedConstantRange.
getLower())),
9287 Ty, AssumedConstantRange.
getUpper()))};
9292 static bool isBetterRange(
const ConstantRange &Assumed,
9293 const Instruction &
I) {
9297 std::optional<ConstantRange>
Known;
9301 }
else if (MDNode *KnownRanges =
I.getMetadata(LLVMContext::MD_range)) {
9307 if (KnownRanges->getNumOperands() > 2)
9310 ConstantInt *
Lower =
9312 ConstantInt *
Upper =
9322 setRangeMetadataIfisBetterRange(Instruction *
I,
9323 const ConstantRange &AssumedConstantRange) {
9324 if (isBetterRange(AssumedConstantRange, *
I)) {
9325 I->setMetadata(LLVMContext::MD_range,
9326 getMDNodeForConstantRange(
I->getType(),
I->getContext(),
9327 AssumedConstantRange));
9334 setRangeRetAttrIfisBetterRange(Attributor &
A,
const IRPosition &IRP,
9336 const ConstantRange &AssumedConstantRange) {
9337 if (isBetterRange(AssumedConstantRange, *
I)) {
9338 A.manifestAttrs(IRP,
9339 Attribute::get(
I->getContext(), Attribute::Range,
9340 AssumedConstantRange),
9350 ConstantRange AssumedConstantRange = getAssumedConstantRange(
A);
9353 auto &
V = getAssociatedValue();
9357 assert(
I == getCtxI() &&
"Should not annotate an instruction which is "
9358 "not the context instruction");
9360 if (setRangeMetadataIfisBetterRange(
I, AssumedConstantRange))
9361 Changed = ChangeStatus::CHANGED;
9363 if (setRangeRetAttrIfisBetterRange(
A, getIRPosition(),
I,
9364 AssumedConstantRange))
9365 Changed = ChangeStatus::CHANGED;
9373struct AAValueConstantRangeArgument final
9374 : AAArgumentFromCallSiteArguments<
9375 AAValueConstantRange, AAValueConstantRangeImpl, IntegerRangeState,
9377 using Base = AAArgumentFromCallSiteArguments<
9378 AAValueConstantRange, AAValueConstantRangeImpl, IntegerRangeState,
9380 AAValueConstantRangeArgument(
const IRPosition &IRP, Attributor &
A)
9384 void trackStatistics()
const override {
9389struct AAValueConstantRangeReturned
9390 : AAReturnedFromReturnedValues<AAValueConstantRange,
9391 AAValueConstantRangeImpl,
9392 AAValueConstantRangeImpl::StateType,
9395 AAReturnedFromReturnedValues<AAValueConstantRange,
9396 AAValueConstantRangeImpl,
9397 AAValueConstantRangeImpl::StateType,
9399 AAValueConstantRangeReturned(
const IRPosition &IRP, Attributor &
A)
9404 if (!
A.isFunctionIPOAmendable(*getAssociatedFunction()))
9405 indicatePessimisticFixpoint();
9409 void trackStatistics()
const override {
9414struct AAValueConstantRangeFloating : AAValueConstantRangeImpl {
9415 AAValueConstantRangeFloating(
const IRPosition &IRP, Attributor &
A)
9416 : AAValueConstantRangeImpl(IRP,
A) {}
9420 AAValueConstantRangeImpl::initialize(
A);
9424 Value &
V = getAssociatedValue();
9427 unionAssumed(ConstantRange(
C->getValue()));
9428 indicateOptimisticFixpoint();
9434 unionAssumed(ConstantRange(APInt(
getBitWidth(), 0)));
9435 indicateOptimisticFixpoint();
9447 if (
auto *RangeMD = LI->getMetadata(LLVMContext::MD_range)) {
9458 indicatePessimisticFixpoint();
9461 << getAssociatedValue() <<
"\n");
9464 bool calculateBinaryOperator(
9465 Attributor &
A, BinaryOperator *BinOp, IntegerRangeState &
T,
9466 const Instruction *CtxI,
9467 SmallVectorImpl<const AAValueConstantRange *> &QuerriedAAs) {
9472 bool UsedAssumedInformation =
false;
9473 const auto &SimplifiedLHS =
A.getAssumedSimplified(
9476 if (!SimplifiedLHS.has_value())
9478 if (!*SimplifiedLHS)
9480 LHS = *SimplifiedLHS;
9482 const auto &SimplifiedRHS =
A.getAssumedSimplified(
9485 if (!SimplifiedRHS.has_value())
9487 if (!*SimplifiedRHS)
9489 RHS = *SimplifiedRHS;
9495 auto *LHSAA =
A.getAAFor<AAValueConstantRange>(
9497 DepClassTy::REQUIRED);
9501 auto LHSAARange = LHSAA->getAssumedConstantRange(
A, CtxI);
9503 auto *RHSAA =
A.getAAFor<AAValueConstantRange>(
9505 DepClassTy::REQUIRED);
9509 auto RHSAARange = RHSAA->getAssumedConstantRange(
A, CtxI);
9511 auto AssumedRange = LHSAARange.binaryOp(BinOp->
getOpcode(), RHSAARange);
9513 T.unionAssumed(AssumedRange);
9517 return T.isValidState();
9520 bool calculateCastInst(
9521 Attributor &
A, CastInst *CastI, IntegerRangeState &
T,
9522 const Instruction *CtxI,
9523 SmallVectorImpl<const AAValueConstantRange *> &QuerriedAAs) {
9529 bool UsedAssumedInformation =
false;
9530 const auto &SimplifiedOpV =
A.getAssumedSimplified(
9533 if (!SimplifiedOpV.has_value())
9535 if (!*SimplifiedOpV)
9537 OpV = *SimplifiedOpV;
9542 auto *OpAA =
A.getAAFor<AAValueConstantRange>(
9544 DepClassTy::REQUIRED);
9548 T.unionAssumed(OpAA->getAssumed().castOp(CastI->
getOpcode(),
9550 return T.isValidState();
9554 calculateCmpInst(Attributor &
A, CmpInst *CmpI, IntegerRangeState &
T,
9555 const Instruction *CtxI,
9556 SmallVectorImpl<const AAValueConstantRange *> &QuerriedAAs) {
9561 bool UsedAssumedInformation =
false;
9562 const auto &SimplifiedLHS =
A.getAssumedSimplified(
9565 if (!SimplifiedLHS.has_value())
9567 if (!*SimplifiedLHS)
9569 LHS = *SimplifiedLHS;
9571 const auto &SimplifiedRHS =
A.getAssumedSimplified(
9574 if (!SimplifiedRHS.has_value())
9576 if (!*SimplifiedRHS)
9578 RHS = *SimplifiedRHS;
9584 auto *LHSAA =
A.getAAFor<AAValueConstantRange>(
9586 DepClassTy::REQUIRED);
9590 auto *RHSAA =
A.getAAFor<AAValueConstantRange>(
9592 DepClassTy::REQUIRED);
9596 auto LHSAARange = LHSAA->getAssumedConstantRange(
A, CtxI);
9597 auto RHSAARange = RHSAA->getAssumedConstantRange(
A, CtxI);
9600 if (LHSAARange.isEmptySet() || RHSAARange.isEmptySet())
9603 bool MustTrue =
false, MustFalse =
false;
9605 auto AllowedRegion =
9608 if (AllowedRegion.intersectWith(LHSAARange).isEmptySet())
9614 assert((!MustTrue || !MustFalse) &&
9615 "Either MustTrue or MustFalse should be false!");
9618 T.unionAssumed(ConstantRange(APInt( 1, 1)));
9620 T.unionAssumed(ConstantRange(APInt( 1, 0)));
9622 T.unionAssumed(ConstantRange( 1,
true));
9624 LLVM_DEBUG(
dbgs() <<
"[AAValueConstantRange] " << *CmpI <<
" after "
9625 << (MustTrue ?
"true" : (MustFalse ?
"false" :
"unknown"))
9626 <<
": " <<
T <<
"\n\t" << *LHSAA <<
"\t<op>\n\t"
9630 return T.isValidState();
9642 bool UsedAssumedInformation =
false;
9643 const auto &SimplifiedOpV =
A.getAssumedSimplified(
9646 if (!SimplifiedOpV.has_value())
9648 if (!*SimplifiedOpV)
9650 Value *VPtr = *SimplifiedOpV;
9653 const auto *AA =
A.getAAFor<AAValueConstantRange>(
9655 DepClassTy::REQUIRED);
9659 T.unionAssumed(AA->getAssumedConstantRange(
A, CtxI));
9663 return T.isValidState();
9668 if (!calculateBinaryOperator(
A, BinOp,
T, CtxI, QuerriedAAs))
9671 if (!calculateCmpInst(
A, CmpI,
T, CtxI, QuerriedAAs))
9674 if (!calculateCastInst(
A, CastI,
T, CtxI, QuerriedAAs))
9680 T.indicatePessimisticFixpoint();
9687 for (
const AAValueConstantRange *QueriedAA : QuerriedAAs) {
9688 if (QueriedAA !=
this)
9691 if (
T.getAssumed() == getState().getAssumed())
9693 T.indicatePessimisticFixpoint();
9696 return T.isValidState();
9699 if (!VisitValueCB(getAssociatedValue(), getCtxI()))
9700 return indicatePessimisticFixpoint();
9705 return ChangeStatus::UNCHANGED;
9706 if (++NumChanges > MaxNumChanges) {
9707 LLVM_DEBUG(
dbgs() <<
"[AAValueConstantRange] performed " << NumChanges
9708 <<
" but only " << MaxNumChanges
9709 <<
" are allowed to avoid cyclic reasoning.");
9710 return indicatePessimisticFixpoint();
9712 return ChangeStatus::CHANGED;
9716 void trackStatistics()
const override {
9725 static constexpr int MaxNumChanges = 5;
9728struct AAValueConstantRangeFunction : AAValueConstantRangeImpl {
9729 AAValueConstantRangeFunction(
const IRPosition &IRP, Attributor &
A)
9730 : AAValueConstantRangeImpl(IRP,
A) {}
9734 llvm_unreachable(
"AAValueConstantRange(Function|CallSite)::updateImpl will "
9742struct AAValueConstantRangeCallSite : AAValueConstantRangeFunction {
9743 AAValueConstantRangeCallSite(
const IRPosition &IRP, Attributor &
A)
9744 : AAValueConstantRangeFunction(IRP,
A) {}
9750struct AAValueConstantRangeCallSiteReturned
9751 : AACalleeToCallSite<AAValueConstantRange, AAValueConstantRangeImpl,
9752 AAValueConstantRangeImpl::StateType,
9754 AAValueConstantRangeCallSiteReturned(
const IRPosition &IRP, Attributor &
A)
9755 : AACalleeToCallSite<AAValueConstantRange, AAValueConstantRangeImpl,
9756 AAValueConstantRangeImpl::StateType,
9763 if (std::optional<ConstantRange>
Range = CI->getRange())
9764 intersectKnown(*
Range);
9767 AAValueConstantRangeImpl::initialize(
A);
9771 void trackStatistics()
const override {
9775struct AAValueConstantRangeCallSiteArgument : AAValueConstantRangeFloating {
9776 AAValueConstantRangeCallSiteArgument(
const IRPosition &IRP, Attributor &
A)
9777 : AAValueConstantRangeFloating(IRP,
A) {}
9781 return ChangeStatus::UNCHANGED;
9785 void trackStatistics()
const override {
9794struct AAPotentialConstantValuesImpl : AAPotentialConstantValues {
9797 AAPotentialConstantValuesImpl(
const IRPosition &IRP, Attributor &
A)
9798 : AAPotentialConstantValues(IRP,
A) {}
9802 if (
A.hasSimplificationCallback(getIRPosition()))
9803 indicatePessimisticFixpoint();
9805 AAPotentialConstantValues::initialize(
A);
9808 bool fillSetWithConstantValues(Attributor &
A,
const IRPosition &IRP, SetTy &S,
9809 bool &ContainsUndef,
bool ForSelf) {
9811 bool UsedAssumedInformation =
false;
9813 UsedAssumedInformation)) {
9820 auto *PotentialValuesAA =
A.getAAFor<AAPotentialConstantValues>(
9821 *
this, IRP, DepClassTy::REQUIRED);
9822 if (!PotentialValuesAA || !PotentialValuesAA->getState().isValidState())
9824 ContainsUndef = PotentialValuesAA->getState().undefIsContained();
9825 S = PotentialValuesAA->getState().getAssumedSet();
9832 ContainsUndef =
false;
9833 for (
auto &It :
Values) {
9835 ContainsUndef =
true;
9841 S.insert(CI->getValue());
9843 ContainsUndef &= S.empty();
9849 const std::string getAsStr(Attributor *
A)
const override {
9851 llvm::raw_string_ostream OS(Str);
9858 return indicatePessimisticFixpoint();
9862struct AAPotentialConstantValuesArgument final
9863 : AAArgumentFromCallSiteArguments<AAPotentialConstantValues,
9864 AAPotentialConstantValuesImpl,
9865 PotentialConstantIntValuesState> {
9866 using Base = AAArgumentFromCallSiteArguments<AAPotentialConstantValues,
9867 AAPotentialConstantValuesImpl,
9869 AAPotentialConstantValuesArgument(
const IRPosition &IRP, Attributor &
A)
9873 void trackStatistics()
const override {
9878struct AAPotentialConstantValuesReturned
9879 : AAReturnedFromReturnedValues<AAPotentialConstantValues,
9880 AAPotentialConstantValuesImpl> {
9881 using Base = AAReturnedFromReturnedValues<AAPotentialConstantValues,
9882 AAPotentialConstantValuesImpl>;
9883 AAPotentialConstantValuesReturned(
const IRPosition &IRP, Attributor &
A)
9887 if (!
A.isFunctionIPOAmendable(*getAssociatedFunction()))
9888 indicatePessimisticFixpoint();
9889 Base::initialize(
A);
9893 void trackStatistics()
const override {
9898struct AAPotentialConstantValuesFloating : AAPotentialConstantValuesImpl {
9899 AAPotentialConstantValuesFloating(
const IRPosition &IRP, Attributor &
A)
9900 : AAPotentialConstantValuesImpl(IRP,
A) {}
9904 AAPotentialConstantValuesImpl::initialize(
A);
9908 Value &
V = getAssociatedValue();
9911 unionAssumed(
C->getValue());
9912 indicateOptimisticFixpoint();
9917 unionAssumedWithUndef();
9918 indicateOptimisticFixpoint();
9928 indicatePessimisticFixpoint();
9931 << getAssociatedValue() <<
"\n");
9934 static bool calculateICmpInst(
const ICmpInst *ICI,
const APInt &
LHS,
9939 static APInt calculateCastInst(
const CastInst *CI,
const APInt &Src,
9940 uint32_t ResultBitWidth) {
9945 case Instruction::Trunc:
9946 return Src.trunc(ResultBitWidth);
9947 case Instruction::SExt:
9948 return Src.sext(ResultBitWidth);
9949 case Instruction::ZExt:
9950 return Src.zext(ResultBitWidth);
9951 case Instruction::BitCast:
9956 static APInt calculateBinaryOperator(
const BinaryOperator *BinOp,
9957 const APInt &
LHS,
const APInt &
RHS,
9958 bool &SkipOperation,
bool &Unsupported) {
9965 switch (BinOpcode) {
9969 case Instruction::Add:
9971 case Instruction::Sub:
9973 case Instruction::Mul:
9975 case Instruction::UDiv:
9977 SkipOperation =
true;
9981 case Instruction::SDiv:
9983 SkipOperation =
true;
9987 case Instruction::URem:
9989 SkipOperation =
true;
9993 case Instruction::SRem:
9995 SkipOperation =
true;
9999 case Instruction::Shl:
10001 case Instruction::LShr:
10003 case Instruction::AShr:
10005 case Instruction::And:
10007 case Instruction::Or:
10009 case Instruction::Xor:
10014 bool calculateBinaryOperatorAndTakeUnion(
const BinaryOperator *BinOp,
10015 const APInt &
LHS,
const APInt &
RHS) {
10016 bool SkipOperation =
false;
10019 calculateBinaryOperator(BinOp,
LHS,
RHS, SkipOperation, Unsupported);
10023 if (!SkipOperation)
10024 unionAssumed(Result);
10025 return isValidState();
10028 ChangeStatus updateWithICmpInst(Attributor &
A, ICmpInst *ICI) {
10029 auto AssumedBefore = getAssumed();
10033 bool LHSContainsUndef =
false, RHSContainsUndef =
false;
10034 SetTy LHSAAPVS, RHSAAPVS;
10036 LHSContainsUndef,
false) ||
10038 RHSContainsUndef,
false))
10039 return indicatePessimisticFixpoint();
10042 bool MaybeTrue =
false, MaybeFalse =
false;
10044 if (LHSContainsUndef && RHSContainsUndef) {
10047 unionAssumedWithUndef();
10048 }
else if (LHSContainsUndef) {
10049 for (
const APInt &R : RHSAAPVS) {
10050 bool CmpResult = calculateICmpInst(ICI, Zero, R);
10051 MaybeTrue |= CmpResult;
10052 MaybeFalse |= !CmpResult;
10053 if (MaybeTrue & MaybeFalse)
10054 return indicatePessimisticFixpoint();
10056 }
else if (RHSContainsUndef) {
10057 for (
const APInt &L : LHSAAPVS) {
10058 bool CmpResult = calculateICmpInst(ICI, L, Zero);
10059 MaybeTrue |= CmpResult;
10060 MaybeFalse |= !CmpResult;
10061 if (MaybeTrue & MaybeFalse)
10062 return indicatePessimisticFixpoint();
10065 for (
const APInt &L : LHSAAPVS) {
10066 for (
const APInt &R : RHSAAPVS) {
10067 bool CmpResult = calculateICmpInst(ICI, L, R);
10068 MaybeTrue |= CmpResult;
10069 MaybeFalse |= !CmpResult;
10070 if (MaybeTrue & MaybeFalse)
10071 return indicatePessimisticFixpoint();
10076 unionAssumed(APInt( 1, 1));
10078 unionAssumed(APInt( 1, 0));
10079 return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
10080 : ChangeStatus::CHANGED;
10083 ChangeStatus updateWithSelectInst(Attributor &
A, SelectInst *SI) {
10084 auto AssumedBefore = getAssumed();
10088 bool UsedAssumedInformation =
false;
10089 std::optional<Constant *>
C =
A.getAssumedConstant(
10090 *
SI->getCondition(), *
this, UsedAssumedInformation);
10093 bool OnlyLeft =
false, OnlyRight =
false;
10094 if (
C && *
C && (*C)->isOneValue())
10096 else if (
C && *
C && (*C)->isNullValue())
10099 bool LHSContainsUndef =
false, RHSContainsUndef =
false;
10100 SetTy LHSAAPVS, RHSAAPVS;
10103 LHSContainsUndef,
false))
10104 return indicatePessimisticFixpoint();
10108 RHSContainsUndef,
false))
10109 return indicatePessimisticFixpoint();
10111 if (OnlyLeft || OnlyRight) {
10113 auto *OpAA = OnlyLeft ? &LHSAAPVS : &RHSAAPVS;
10114 auto Undef = OnlyLeft ? LHSContainsUndef : RHSContainsUndef;
10117 unionAssumedWithUndef();
10119 for (
const auto &It : *OpAA)
10123 }
else if (LHSContainsUndef && RHSContainsUndef) {
10125 unionAssumedWithUndef();
10127 for (
const auto &It : LHSAAPVS)
10129 for (
const auto &It : RHSAAPVS)
10132 return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
10133 : ChangeStatus::CHANGED;
10136 ChangeStatus updateWithCastInst(Attributor &
A, CastInst *CI) {
10137 auto AssumedBefore = getAssumed();
10139 return indicatePessimisticFixpoint();
10144 bool SrcContainsUndef =
false;
10147 SrcContainsUndef,
false))
10148 return indicatePessimisticFixpoint();
10150 if (SrcContainsUndef)
10151 unionAssumedWithUndef();
10153 for (
const APInt &S : SrcPVS) {
10154 APInt
T = calculateCastInst(CI, S, ResultBitWidth);
10158 return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED
10159 : ChangeStatus::CHANGED;
10162 ChangeStatus updateWithBinaryOperator(Attributor &
A, BinaryOperator *BinOp) {
10163 auto AssumedBefore = getAssumed();
10167 bool LHSContainsUndef =
false, RHSContainsUndef =
false;
10168 SetTy LHSAAPVS, RHSAAPVS;
10170 LHSContainsUndef,
false) ||
10172 RHSContainsUndef,
false))
10173 return indicatePessimisticFixpoint();
10178 if (LHSContainsUndef && RHSContainsUndef) {
10179 if (!calculateBinaryOperatorAndTakeUnion(BinOp, Zero, Zero))
10180 return indicatePessimisticFixpoint();
10181 }
else if (LHSContainsUndef) {
10182 for (
const APInt &R : RHSAAPVS) {
10183 if (!calculateBinaryOperatorAndTakeUnion(BinOp, Zero, R))
10184 return indicatePessimisticFixpoint();
10186 }
else if (RHSContainsUndef) {
10187 for (
const APInt &L : LHSAAPVS) {
10188 if (!calculateBinaryOperatorAndTakeUnion(BinOp, L, Zero))
10189 return indicatePessimisticFixpoint();