97#ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
98#define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
141template <
typename Fn>
class function_ref;
142struct AADepGraphNode;
145struct AbstractAttribute;
146struct InformationCache;
148struct AttributorCallGraph;
176 using Base = std::pair<Value *, const Instruction *>;
196 const Value &V,
bool ForAnalysisOnly =
true);
220std::optional<Value *>
222 const std::optional<Value *> &
B,
Type *Ty);
248 "Inconsistent state!");
284 return L.
Offset < R.Offset;
293 static constexpr int64_t
Unassigned = std::numeric_limits<int32_t>::min();
294 static constexpr int64_t
Unknown = std::numeric_limits<int32_t>::max();
298 OS <<
"[" << R.Offset <<
", " << R.Size <<
"]";
303 return A.Offset ==
B.Offset &&
A.Size ==
B.Size;
312 RangeTy *RangePtr =
nullptr);
329 bool OnlyExact =
false);
343 bool OnlyExact =
false);
367 std::function<
bool(
const Function &
F)> GoBackwardsCB =
nullptr);
374 std::function<
bool(
const Function &
F)> GoBackwardsCB =
nullptr);
393 return Base::getEmptyKey();
396 return Base::getTombstoneKey();
399 return Base::getHashValue(VAC);
404 return Base::isEqual(
LHS,
RHS);
418 return Base::getHashValue(S);
422 return Base::isEqual(
LHS,
RHS);
435 super::getTombstoneKey());
440 for (
const auto *II : *BES)
448 if (
LHS == getEmptyKey() ||
RHS == getEmptyKey() ||
449 LHS == getTombstoneKey() ||
RHS == getTombstoneKey())
452 return ((
LHS &&
LHS->empty()) || (
RHS &&
RHS->empty()));
453 if (
LHS->size() !=
RHS->size())
494 return cast<AbstractAttribute>(DT.
getPointer());
584 if (
auto *
Arg = dyn_cast<Argument>(&V))
586 if (
auto *CB = dyn_cast<CallBase>(&V))
665 return Enc ==
RHS.Enc &&
RHS.CBContext == CBContext;
676 switch (getEncodingBits()) {
678 case ENC_RETURNED_VALUE:
679 case ENC_FLOATING_FUNCTION:
680 return *getAsValuePtr();
681 case ENC_CALL_SITE_ARGUMENT_USE:
682 return *(getAsUsePtr()->getUser());
695 return Arg->getParent();
696 return CB->getCalledFunction();
720 if (isa<Function>(V))
721 return &cast<Function>(V);
722 if (isa<Argument>(V))
723 return cast<Argument>(V).getParent();
724 if (isa<Instruction>(V))
725 return cast<Instruction>(V).getFunction();
732 if (
auto *
I = dyn_cast<Instruction>(&V))
734 if (
auto *
Arg = dyn_cast<Argument>(&V))
735 if (!
Arg->getParent()->isDeclaration())
736 return &
Arg->getParent()->getEntryBlock().front();
737 if (
auto *
F = dyn_cast<Function>(&V))
738 if (!
F->isDeclaration())
739 return &(
F->getEntryBlock().front());
765 return getArgNo(
true);
774 return getArgNo(
false);
794 "There is no attribute index for a floating or invalid position!");
799 char EncodingBits = getEncodingBits();
800 if (EncodingBits == ENC_CALL_SITE_ARGUMENT_USE)
802 if (EncodingBits == ENC_FLOATING_FUNCTION)
805 Value *V = getAsValuePtr();
808 if (isa<Argument>(V))
810 if (isa<Function>(V))
812 if (isa<CallBase>(V))
827 bool IgnoreSubsumingPositions =
false,
840 bool IgnoreSubsumingPositions =
false,
860 CB->setAttributes(AttrList);
890 Result.CBContext =
nullptr;
913 : CBContext(CBContext) {
920 : CBContext(CBContext) {
927 if (isa<Function>(AnchorVal) || isa<CallBase>(AnchorVal))
928 Enc = {&AnchorVal, ENC_FLOATING_FUNCTION};
930 Enc = {&AnchorVal, ENC_VALUE};
934 Enc = {&AnchorVal, ENC_VALUE};
938 Enc = {&AnchorVal, ENC_RETURNED_VALUE};
941 Enc = {&AnchorVal, ENC_VALUE};
945 "Cannot create call site argument IRP with an anchor value!");
954 int getArgNo(
bool CallbackCalleeArgIfApplicable)
const {
955 if (CallbackCalleeArgIfApplicable)
957 return Arg->getArgNo();
960 return cast<Argument>(getAsValuePtr())->getArgNo();
962 Use &U = *getAsUsePtr();
963 return cast<CallBase>(U.getUser())->getArgOperandNo(&U);
975 "Use constructor is for call site arguments only!");
976 Enc = {&U, ENC_CALL_SITE_ARGUMENT_USE};
985 SmallVectorImpl<Attribute> &Attrs)
const;
990 SmallVectorImpl<Attribute> &Attrs,
991 Attributor &
A)
const;
995 Value *getAsValuePtr()
const {
996 assert(getEncodingBits() != ENC_CALL_SITE_ARGUMENT_USE &&
997 "Not a value pointer!");
1003 Use *getAsUsePtr()
const {
1004 assert(getEncodingBits() == ENC_CALL_SITE_ARGUMENT_USE &&
1005 "Not a value pointer!");
1006 return reinterpret_cast<Use *
>(Enc.
getPointer());
1011 static bool isReturnPosition(
char EncodingBits) {
1012 return EncodingBits == ENC_RETURNED_VALUE;
1017 bool isReturnPosition()
const {
return isReturnPosition(getEncodingBits()); }
1027 ENC_RETURNED_VALUE = 0b01,
1028 ENC_FLOATING_FUNCTION = 0b10,
1029 ENC_CALL_SITE_ARGUMENT_USE = 0b11,
1034 static constexpr int NumEncodingBits =
1035 PointerLikeTypeTraits<void *>::NumLowBitsAvailable;
1036 static_assert(NumEncodingBits >= 2,
"At least two bits are required!");
1039 PointerIntPair<void *, NumEncodingBits, char> Enc;
1046 char getEncodingBits()
const {
return Enc.getInt(); }
1091 using iterator =
decltype(IRPositions)::iterator;
1114 template <
typename Analysis>
1118 if constexpr (HasLegacyWrapper<Analysis>)
1133 Pass *LegacyPass =
nullptr;
1136template <
typename Analysis>
1138 Analysis, std::void_t<typename Analysis::LegacyWrapper>> =
true;
1166 [&](
const Function &
F) {
1169 AG(AG), TargetTriple(
M.getTargetTriple()) {
1177 for (
auto &It : FuncInfoMap)
1178 It.getSecond()->~FunctionInfo();
1181 for (
auto *BES : BESets)
1182 BES->~InstExclusionSetTy();
1188 template <
typename CBTy>
1190 bool LookThroughConstantExprUses =
true) {
1197 if (LookThroughConstantExprUses && isa<ConstantExpr>(U.
getUser())) {
1218 while (!Worklist.
empty()) {
1223 if (
auto *CB = dyn_cast<CallBase>(&
I))
1230 Worklist.
append(SCC.begin(), SCC.end());
1231 while (!Worklist.
empty()) {
1237 if (
auto *UsrI = dyn_cast<Instruction>(U.
getUser()))
1238 if (Seen.
insert(UsrI->getFunction()).second)
1239 Worklist.
push_back(UsrI->getFunction());
1256 return getFunctionInfo(
F).OpcodeInstMap;
1261 return getFunctionInfo(
F).RWInsts;
1280 FunctionInfo &FI = getFunctionInfo(*
Arg.getParent());
1281 return FI.CalledViaMustTail || FI.ContainsMustTailCall;
1285 return AssumeOnlyValues.contains(&
I);
1289 template <
typename AP>
1304 auto It = BESets.find(BES);
1305 if (It != BESets.end())
1308 BESets.insert(UniqueBES);
1326 struct FunctionInfo {
1338 bool CalledViaMustTail;
1341 bool ContainsMustTailCall;
1345 DenseMap<const Function *, FunctionInfo *> FuncInfoMap;
1348 FunctionInfo &getFunctionInfo(
const Function &
F) {
1349 FunctionInfo *&FI = FuncInfoMap[&
F];
1351 FI =
new (Allocator) FunctionInfo();
1352 initializeInformationCache(
F, *FI);
1361 void initializeInformationCache(
const Function &
F, FunctionInfo &FI);
1364 const DataLayout &DL;
1370 MustBeExecutedContextExplorer Explorer;
1376 SetVector<const Instruction *> AssumeOnlyValues;
1379 DenseSet<AA::InstExclusionSetTy *> BESets;
1385 SmallPtrSet<const Function *, 8> InlineableFunctions;
1388 Triple TargetTriple;
1482 InfoCache(InfoCache), Configuration(Configuration) {}
1514 template <
typename AAType>
1517 return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1526 template <
typename AAType>
1529 return getOrCreateAAFor<AAType>(IRP, &QueryingAA, DepClass,
1538 template <
typename AAType>
1541 DepClassTy DepClass,
bool ForceUpdate =
false,
1542 bool UpdateAfterInit =
true) {
1543 if (!shouldPropagateCallBaseContext(IRP))
1546 if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, DepClass,
1548 if (ForceUpdate && Phase == AttributorPhase::UPDATE)
1555 auto &AA = AAType::createForPosition(IRP, *
this);
1562 if (Phase == AttributorPhase::SEEDING && !shouldSeedAttribute(AA)) {
1563 AA.getState().indicatePessimisticFixpoint();
1585 AA.getState().indicatePessimisticFixpoint();
1591 ++InitializationChainLength;
1592 AA.initialize(*
this);
1593 --InitializationChainLength;
1600 AA.getState().indicatePessimisticFixpoint();
1606 if (Phase == AttributorPhase::MANIFEST ||
1607 Phase == AttributorPhase::CLEANUP) {
1608 AA.getState().indicatePessimisticFixpoint();
1614 if (UpdateAfterInit) {
1615 AttributorPhase OldPhase = Phase;
1616 Phase = AttributorPhase::UPDATE;
1628 template <
typename AAType>
1630 return getOrCreateAAFor<AAType>(IRP,
nullptr,
1636 template <
typename AAType>
1640 bool AllowInvalidState =
false) {
1641 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1642 "Cannot query an attribute with a type not derived from "
1643 "'AbstractAttribute'!");
1650 AAType *AA =
static_cast<AAType *
>(AAPtr);
1659 if (!AllowInvalidState && !AA->getState().isValidState())
1689 static_assert(std::is_base_of<AbstractAttribute, AAType>::value,
1690 "Cannot register an attribute with a type not derived from "
1691 "'AbstractAttribute'!");
1697 assert(!AAPtr &&
"Attribute already in map!");
1701 if (Phase == AttributorPhase::SEEDING || Phase == AttributorPhase::UPDATE)
1717 return Functions.
empty() || Functions.
count(Fn);
1737 return F.hasExactDefinition() || InfoCache.InlineableFunctions.count(&
F);
1746 "Only local linkage is assumed dead initially.");
1765 Value *&V = ToBeChangedUses[&U];
1767 isa_and_nonnull<UndefValue>(V)))
1769 assert((!V || V == &NV || isa<UndefValue>(NV)) &&
1770 "Use was registered twice for replacement with different values!");
1779 bool ChangeDroppable =
true) {
1781 auto *CB = cast<CallBase>(IRP.
getCtxI());
1786 auto &Entry = ToBeChangedValues[&V];
1787 Value *CurNV = get<0>(Entry);
1789 isa<UndefValue>(CurNV)))
1791 assert((!CurNV || CurNV == &NV || isa<UndefValue>(NV)) &&
1792 "Value replacement was registered twice with different values!");
1793 Entry = {&NV, ChangeDroppable};
1800 ToBeChangedToUnreachableInsts.insert(
I);
1807 InvokeWithDeadSuccessor.insert(&II);
1821 ManifestAddedBlocks.insert(&BB);
1827 ToBeDeletedFunctions.insert(&
F);
1834 bool &UsedAssumedInformation);
1837 bool &UsedAssumedInformation) {
1845 bool &UsedAssumedInformation,
1851 bool &UsedAssumedInformation,
1854 UsedAssumedInformation, S);
1863 bool &UsedAssumedInformation,
1876 bool &UsedAssumedInformation);
1887 SimplificationCallbacks[IRP].emplace_back(CB);
1892 return SimplificationCallbacks.count(IRP);
1899 VirtualUseCallbacks[&V].emplace_back(CB);
1905 SimplificationCallbacks;
1908 VirtualUseCallbacks;
1912 std::optional<Value *>
1915 bool &UsedAssumedInformation);
1921 bool &UsedAssumedInformation,
1922 bool CheckBBLivenessOnly =
false,
1929 const AAIsDead *LivenessAA,
bool &UsedAssumedInformation,
1930 bool CheckBBLivenessOnly =
false,
1932 bool CheckForDeadStore =
false);
1938 const AAIsDead *FnLivenessAA,
bool &UsedAssumedInformation,
1939 bool CheckBBLivenessOnly =
false,
1946 const AAIsDead *FnLivenessAA,
bool &UsedAssumedInformation,
1947 bool CheckBBLivenessOnly =
false,
1968 bool CheckBBLivenessOnly =
false,
1970 bool IgnoreDroppableUses =
true,
1972 EquivalentUseCB =
nullptr);
1985 template <
typename RemarkKind,
typename RemarkCallBack>
1987 RemarkCallBack &&RemarkCB)
const {
1996 return RemarkCB(RemarkKind(Configuration.
PassName, RemarkName,
I))
1997 <<
" [" << RemarkName <<
"]";
2001 return RemarkCB(RemarkKind(Configuration.
PassName, RemarkName,
I));
2006 template <
typename RemarkKind,
typename RemarkCallBack>
2008 RemarkCallBack &&RemarkCB)
const {
2016 return RemarkCB(RemarkKind(Configuration.
PassName, RemarkName,
F))
2017 <<
" [" << RemarkName <<
"]";
2021 return RemarkCB(RemarkKind(Configuration.
PassName, RemarkName,
F));
2063 return ReplacementTypes;
2077 ReplacementTypes(ReplacementTypes.begin(), ReplacementTypes.end()),
2078 CalleeRepairCB(
std::
move(CalleeRepairCB)),
2079 ACSRepairCB(
std::
move(ACSRepairCB)) {}
2135 bool RequireAllCallSites,
2136 bool &UsedAssumedInformation);
2146 const Function &Fn,
bool RequireAllCallSites,
2148 bool &UsedAssumedInformation,
2149 bool CheckPotentiallyDead =
false);
2177 bool &UsedAssumedInformation,
2178 bool CheckBBLivenessOnly =
false,
2179 bool CheckPotentiallyDead =
false);
2188 bool &UsedAssumedInformation,
2189 bool CheckBBLivenessOnly =
false,
2190 bool CheckPotentiallyDead =
false);
2197 bool &UsedAssumedInformation,
2198 bool CheckBBLivenessOnly =
false,
2199 bool CheckPotentiallyDead =
false) {
2202 {(
unsigned)Instruction::Invoke, (
unsigned)Instruction::CallBr,
2204 UsedAssumedInformation, CheckBBLivenessOnly, CheckPotentiallyDead);
2214 bool &UsedAssumedInformation);
2280 void runTillFixpoint();
2292 void identifyDeadInternalFunctions();
2300 void rememberDependences();
2303 bool shouldPropagateCallBaseContext(
const IRPosition &IRP);
2319 using AAMapKeyTy = std::pair<const char *, IRPosition>;
2325 ArgumentReplacementMap;
2378 enum class AttributorPhase {
2383 } Phase = AttributorPhase::SEEDING;
2386 unsigned InitializationChainLength = 0;
2391 SmallPtrSet<BasicBlock *, 8> ManifestAddedBlocks;
2392 SmallSetVector<Function *, 8> ToBeDeletedFunctions;
2393 SmallSetVector<BasicBlock *, 8> ToBeDeletedBlocks;
2394 SmallSetVector<WeakVH, 8> ToBeDeletedInsts;
2399 SmallSetVector<AbstractAttribute *, 16> QueryAAsAwaitingUpdate;
2402 const AttributorConfig Configuration;
2405 friend AttributorCallGraph;
2463template <
typename base_ty, base_ty BestState, base_ty WorstState>
2517 return !(*
this == R);
2535 joinOR(R.getAssumed(), R.getKnown());
2539 joinAND(R.getAssumed(), R.getKnown());
2563template <
typename base_ty =
uint32_t, base_ty BestState = ~base_ty(0),
2564 base_ty WorstState = 0>
2571 return (this->
Known & BitsEncoding) == BitsEncoding;
2576 return (this->
Assumed & BitsEncoding) == BitsEncoding;
2583 this->
Known |= Bits;
2606 void handleNewAssumedValue(
base_t Value)
override {
2610 void joinOR(
base_t AssumedValue,
base_t KnownValue)
override {
2611 this->
Known |= KnownValue;
2612 this->
Assumed |= AssumedValue;
2614 void joinAND(
base_t AssumedValue,
base_t KnownValue)
override {
2615 this->
Known &= KnownValue;
2616 this->
Assumed &= AssumedValue;
2622template <
typename base_ty =
uint32_t, base_ty BestState = ~base_ty(0),
2623 base_ty WorstState = 0>
2655 void handleNewAssumedValue(
base_t Value)
override {
2659 void joinOR(
base_t AssumedValue,
base_t KnownValue)
override {
2660 this->
Known = std::max(this->
Known, KnownValue);
2663 void joinAND(
base_t AssumedValue,
base_t KnownValue)
override {
2664 this->
Known = std::min(this->
Known, KnownValue);
2671template <
typename base_ty = u
int32_t>
2691 void handleNewAssumedValue(
base_t Value)
override {
2695 void joinOR(
base_t AssumedValue,
base_t KnownValue)
override {
2699 void joinAND(
base_t AssumedValue,
base_t KnownValue)
override {
2729 void handleNewAssumedValue(
base_t Value)
override {
2733 void handleNewKnownValue(
base_t Value)
override {
2737 void joinOR(
base_t AssumedValue,
base_t KnownValue)
override {
2738 Known |= KnownValue;
2741 void joinAND(
base_t AssumedValue,
base_t KnownValue)
override {
2742 Known &= KnownValue;
2769 return ConstantRange::getFull(
BitWidth);
2774 return ConstantRange::getEmpty(
BitWidth);
2869 : Universal(
false), Set(Assumptions) {}
2872 : Universal(Universal), Set(Assumptions) {}
2883 bool IsUniversal = Universal;
2887 if (
RHS.isUniversal())
2896 Universal &=
RHS.isUniversal();
2897 return IsUniversal != Universal ||
Size != Set.
size();
2903 bool IsUniversal = Universal;
2907 if (!
RHS.isUniversal() && !Universal)
2910 Universal |=
RHS.isUniversal();
2911 return IsUniversal != Universal ||
Size != Set.
size();
2927 : Known(Known), Assumed(
true), IsAtFixedpoint(
false) {}
2937 IsAtFixedpoint =
true;
2944 IsAtFixedpoint =
true;
2963 unsigned SizeBefore = Assumed.
getSet().
size();
2970 return SizeBefore != Assumed.
getSet().
size();
2982 SetContents Assumed;
2984 bool IsAtFixedpoint;
2992 bool ForceReplace =
false);
3012template <Attribute::AttrKind AK,
typename BaseType>
3018 const IRPosition &IRP = this->getIRPosition();
3022 this->getState().indicateOptimisticFixpoint();
3035 if (IsFnInterface && (!FnScope || !
A.isFunctionIPOAmendable(*FnScope)))
3036 this->getState().indicatePessimisticFixpoint();
3041 if (isa<UndefValue>(this->getIRPosition().getAssociatedValue()))
3205template <
typename base_ty, base_ty BestState, base_ty WorstState>
3212raw_ostream &
operator<<(raw_ostream &OS,
const IntegerRangeState &State);
3229template <
typename StateType>
3231 auto Assumed = S.getAssumed();
3243 :
public IRAttribute<Attribute::Returned, AbstractAttribute> {
3272 const std::string
getName()
const override {
return "AAReturnedValues"; }
3289 StateWrapper<BooleanState, AbstractAttribute>> {
3302 const std::string
getName()
const override {
return "AANoUnwind"; }
3318 StateWrapper<BooleanState, AbstractAttribute>> {
3346 const std::string
getName()
const override {
return "AANoSync"; }
3363 StateWrapper<BooleanState, AbstractAttribute>> {
3376 const std::string
getName()
const override {
return "AANonNull"; }
3393 StateWrapper<BooleanState, AbstractAttribute>> {
3406 const std::string
getName()
const override {
return "AANoRecurse"; }
3423 StateWrapper<BooleanState, AbstractAttribute>> {
3436 const std::string
getName()
const override {
return "AAWillReturn"; }
3452 :
public StateWrapper<BooleanState, AbstractAttribute> {
3473 const std::string
getName()
const override {
return "AAUndefinedBehavior"; }
3490 :
public StateWrapper<BooleanState, AbstractAttribute> {
3506 const std::string
getName()
const override {
return "AAIntraFnReachability"; }
3524 StateWrapper<BooleanState, AbstractAttribute>> {
3537 const std::string
getName()
const override {
return "AANoAlias"; }
3554 StateWrapper<BooleanState, AbstractAttribute>> {
3567 const std::string
getName()
const override {
return "AANoFree"; }
3584 StateWrapper<BooleanState, AbstractAttribute>> {
3597 const std::string
getName()
const override {
return "AANoReturn"; }
3613 :
public StateWrapper<BitIntegerState<uint8_t, 3, 0>, AbstractAttribute> {
3656 "Instruction must be in the same anchor scope function.");
3684 const std::string
getName()
const override {
return "AAIsDead"; }
3709 DS.indicatePessimisticFixpoint();
3746 void computeKnownDerefBytesFromAccessedMap() {
3749 if (KnownBytes < Access.first)
3751 KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second);
3784 void takeKnownDerefBytesMaximum(
uint64_t Bytes) {
3788 computeKnownDerefBytesFromAccessedMap();
3792 void takeAssumedDerefBytesMinimum(
uint64_t Bytes) {
3799 AccessedBytes = std::max(AccessedBytes,
Size);
3802 computeKnownDerefBytesFromAccessedMap();
3807 return this->DerefBytesState ==
R.DerefBytesState &&
3808 this->GlobalState ==
R.GlobalState;
3812 bool operator!=(
const DerefState &R)
const {
return !(*
this ==
R); }
3817 GlobalState ^=
R.GlobalState;
3824 GlobalState +=
R.GlobalState;
3831 GlobalState &=
R.GlobalState;
3838 GlobalState |=
R.GlobalState;
3843 const AANonNull *NonNullAA =
nullptr;
3849 StateWrapper<DerefState, AbstractAttribute>> {
3854 return NonNullAA && NonNullAA->isAssumedNonNull();
3859 return NonNullAA && NonNullAA->isKnownNonNull();
3885 const std::string
getName()
const override {
return "AADereferenceable"; }
3904 Attribute::Alignment,
3905 StateWrapper<AAAlignmentStateType, AbstractAttribute>> {
3915 const std::string
getName()
const override {
return "AAAlign"; }
3957 const std::string
getName()
const override {
return "AAInstanceInfo"; }
3975 Attribute::NoCapture,
3976 StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>> {
4020 const std::string
getName()
const override {
return "AANoCapture"; }
4048 DS.indicatePessimisticFixpoint();
4110 :
public StateWrapper<ValueSimplifyStateType, AbstractAttribute, Type *> {
4120 const std::string
getName()
const override {
return "AAValueSimplify"; }
4140 virtual std::optional<Value *>
4141 getAssumedSimplifiedValue(
Attributor &
A)
const = 0;
4161 const std::string
getName()
const override {
return "AAHeapToStack"; }
4186 :
public StateWrapper<BooleanState, AbstractAttribute> {
4206 const std::string
getName()
const override {
return "AAPrivatizablePtr"; }
4225 Attribute::ReadNone,
4226 StateWrapper<BitIntegerState<uint8_t, 3>, AbstractAttribute>> {
4269 const std::string
getName()
const override {
return "AAMemoryBehavior"; }
4288 Attribute::ReadNone,
4289 StateWrapper<BitIntegerState<uint32_t, 511>, AbstractAttribute>> {