Go to the documentation of this file.
49 #ifdef EXPENSIVE_CHECKS
58 #define DEBUG_TYPE "attributor"
61 "Determine what attributes are manifested in the IR");
63 STATISTIC(NumFnDeleted,
"Number of function deleted");
65 "Number of functions with exact definitions");
67 "Number of functions without exact definitions");
68 STATISTIC(NumFnShallowWrappersCreated,
"Number of shallow wrappers created");
70 "Number of abstract attributes timed out before fixpoint");
72 "Number of abstract attributes in a valid fixpoint state");
74 "Number of abstract attributes manifested in IR");
86 cl::desc(
"Maximal number of fixpoint iterations."),
90 "attributor-max-initialization-chain-length",
cl::Hidden,
92 "Maximal number of chained initializations (to avoid stack overflows)"),
97 "attributor-max-iterations-verify",
cl::Hidden,
98 cl::desc(
"Verify that max-iterations is a tight bound for a fixpoint"),
103 cl::desc(
"Annotate call sites of function declarations."),
cl::init(
false));
110 cl::desc(
"Allow the Attributor to create shallow "
111 "wrappers for non-exact definitions."),
116 cl::desc(
"Allow the Attributor to use IP information "
117 "derived from non-exact functions via cloning"),
124 cl::desc(
"Comma seperated list of attribute names that are "
125 "allowed to be seeded."),
129 "attributor-function-seed-allow-list",
cl::Hidden,
130 cl::desc(
"Comma seperated list of function names that are "
131 "allowed to be seeded."),
137 cl::desc(
"Dump the dependency graph to dot files."),
141 "attributor-depgraph-dot-filename-prefix",
cl::Hidden,
142 cl::desc(
"The prefix used for the CallGraph dot file names."));
145 cl::desc(
"View the dependency graph."),
149 cl::desc(
"Print attribute dependencies"),
153 "attributor-enable-call-site-specific-deduction",
cl::Hidden,
154 cl::desc(
"Allow the Attributor to do call site specific analysis"),
159 cl::desc(
"Print Attributor's internal call graph"),
164 cl::desc(
"Try to simplify all loads."),
189 if (
const auto *CB = dyn_cast<CallBase>(&
I)) {
190 if (CB->hasFnAttr(Attribute::NoSync))
194 if (!CB->isConvergent() && !CB->mayReadOrWriteMemory())
200 const auto &NoSyncAA = A.getAAFor<
AANoSync>(
205 if (!
I.mayReadOrWriteMemory())
212 const Value &V,
bool ForAnalysisOnly) {
214 if (!ForAnalysisOnly)
223 if (isa<AllocaInst>(Obj))
227 auto *GV = dyn_cast<GlobalVariable>(&Obj);
230 if (!GV->hasLocalLinkage() && !(GV->isConstant() && GV->hasInitializer()))
232 if (!GV->hasInitializer())
234 return dyn_cast_or_null<Constant>(
getWithType(*GV->getInitializer(), Ty));
238 if (isa<Constant>(V))
240 if (
auto *
I = dyn_cast<Instruction>(&V))
241 return I->getFunction() ==
Scope;
242 if (
auto *A = dyn_cast<Argument>(&V))
243 return A->getParent() ==
Scope;
255 if (
auto *A = dyn_cast<Argument>(VAC.
getValue()))
256 return A->getParent() ==
Scope;
257 if (
auto *
I = dyn_cast<Instruction>(VAC.
getValue())) {
258 if (
I->getFunction() ==
Scope) {
262 return DT->dominates(
I, CtxI);
264 if (CtxI &&
I->getParent() == CtxI->
getParent())
267 [&](
const Instruction &AfterI) { return &AfterI == CtxI; });
276 if (isa<PoisonValue>(V))
278 if (isa<UndefValue>(V))
280 if (
auto *
C = dyn_cast<Constant>(&V)) {
281 if (
C->isNullValue())
309 Ty = (*A)->getType();
310 if (isa_and_nonnull<UndefValue>(*A))
312 if (isa<UndefValue>(*
B))
319 template <
bool IsLoad,
typename Ty>
325 LLVM_DEBUG(
dbgs() <<
"Trying to determine the potential copies of " <<
I
326 <<
" (only exact: " << OnlyExact <<
")\n";);
328 Value &Ptr = *
I.getPointerOperand();
331 UsedAssumedInformation)) {
333 dbgs() <<
"Underlying objects stored into could not be determined\n";);
345 A.getInfoCache().getTargetLibraryInfoForFunction(*
I.getFunction());
346 for (
Value *Obj : Objects) {
348 if (isa<UndefValue>(Obj))
350 if (isa<ConstantPointerNull>(Obj)) {
354 Ptr.getType()->getPointerAddressSpace()) &&
355 A.getAssumedSimplified(Ptr, QueryingAA, UsedAssumedInformation) ==
359 dbgs() <<
"Underlying object is a valid nullptr, giving up.\n";);
363 if (!isa<AllocaInst>(Obj) && !isa<GlobalVariable>(Obj) &&
365 LLVM_DEBUG(
dbgs() <<
"Underlying object is not supported yet: " << *Obj
369 if (
auto *GV = dyn_cast<GlobalVariable>(Obj))
370 if (!GV->hasLocalLinkage() &&
371 !(GV->isConstant() && GV->hasInitializer())) {
373 "linkage, not supported yet: "
382 NewCopies.push_back(InitialValue);
383 NewCopyOrigins.push_back(
nullptr);
387 if ((IsLoad && !Acc.
isWrite()) || (!IsLoad && !Acc.
isRead()))
391 if (OnlyExact && !IsExact &&
398 assert(isa<LoadInst>(
I) &&
"Expected load or store instruction only!");
406 LLVM_DEBUG(
dbgs() <<
"Underlying object written through a non-store "
407 "instruction not supported yet: "
411 NewCopies.push_back(
SI->getValueOperand());
412 NewCopyOrigins.push_back(
SI);
414 assert(isa<StoreInst>(
I) &&
"Expected load or store instruction only!");
416 if (!LI && OnlyExact) {
418 "instruction not supported yet: "
429 if (!PI.forallInterferingAccesses(A, QueryingAA,
I, CheckAccess)) {
432 <<
"Failed to verify all interfering accesses for underlying object: "
442 for (
auto *PI : PIs) {
443 if (!PI->getState().isAtFixpoint())
444 UsedAssumedInformation =
true;
447 PotentialCopies.
insert(NewCopies.begin(), NewCopies.end());
448 PotentialValueOrigins.
insert(NewCopyOrigins.begin(), NewCopyOrigins.end());
459 A, LI, PotentialValues, PotentialValueOrigins, QueryingAA,
460 UsedAssumedInformation, OnlyExact);
469 A,
SI, PotentialCopies, PotentialValueOrigins, QueryingAA,
470 UsedAssumedInformation, OnlyExact);
475 bool RequireReadNone,
bool &IsKnown) {
479 const auto &MemLocAA =
481 if (MemLocAA.isAssumedReadNone()) {
489 const auto &MemBehaviorAA =
491 if (MemBehaviorAA.isAssumedReadNone() ||
492 (!RequireReadNone && MemBehaviorAA.isAssumedReadOnly())) {
494 : MemBehaviorAA.isKnownReadOnly();
520 <<
" from " << FromI <<
" [GBCB: " <<
bool(GoBackwardsCB)
525 Worklist.push_back(&FromI);
529 while (!Worklist.empty()) {
531 if (!Visited.
insert(CurFromI).second)
535 if (FromFn == &ToFn) {
538 LLVM_DEBUG(
dbgs() <<
"[AA] check " << *ToI <<
" from " << *CurFromI
539 <<
" intraprocedurally\n");
542 bool Result = ReachabilityAA.isAssumedReachable(A, *CurFromI, *ToI);
544 << (Result ?
"can potentially " :
"cannot ") <<
"reach "
545 << *ToI <<
" [Intra]\n");
548 if (NoRecurseAA.isAssumedNoRecurse())
557 if (!GoBackwardsCB) {
559 << *CurFromI <<
" is not checked backwards, abort\n");
566 bool Result = FnReachabilityAA.instructionCanReach(
567 A, *CurFromI, ToFn,
false);
569 <<
" " << (Result ?
"can potentially " :
"cannot ")
570 <<
"reach @" << ToFn.
getName() <<
" [FromFn]\n");
576 if (!GoBackwardsCB(*FromFn))
583 CallBase *CB = ACS.getInstruction();
587 if (isa<InvokeInst>(CB))
591 Worklist.push_back(Inst);
595 bool UsedAssumedInformation =
false;
596 Result = !A.checkForAllCallSites(CheckCallSite, *FromFn,
598 &QueryingAA, UsedAssumedInformation);
600 LLVM_DEBUG(
dbgs() <<
"[AA] stepping back to call sites from " << *CurFromI
601 <<
" in @" << FromFn->
getName()
602 <<
" failed, give up\n");
606 LLVM_DEBUG(
dbgs() <<
"[AA] stepped back to call sites from " << *CurFromI
607 <<
" in @" << FromFn->
getName()
608 <<
" worklist size is: " << Worklist.size() <<
"\n");
617 LLVM_DEBUG(
dbgs() <<
"[AA] isPotentiallyReachable " << ToI <<
" from "
618 << FromI <<
" [GBCB: " <<
bool(GoBackwardsCB) <<
"]\n");
645 bool ForceReplace =
false) {
649 if (
Attrs.hasAttributeAtIndex(AttrIdx,
Kind))
658 if (
Attrs.hasAttributeAtIndex(AttrIdx,
Kind))
667 if (
Attrs.hasAttributeAtIndex(AttrIdx,
Kind))
697 for (
const Use *U : CallbackUses) {
711 "ACS mapped into var-args arguments!");
712 if (CBCandidateArg) {
713 CBCandidateArg =
nullptr;
728 return Callee->getArg(ArgNo);
742 LLVM_DEBUG(
dbgs() <<
"[Attributor] Update " << HasChanged <<
" " << *
this
778 for (
const Attribute &Attr : DeducedAttrs) {
812 IRPositions.emplace_back(IRP);
816 auto CanIgnoreOperandBundles = [](
const CallBase &CB) {
817 return (isa<IntrinsicInst>(CB) &&
818 cast<IntrinsicInst>(CB).getIntrinsicID() == Intrinsic ::assume);
832 assert(CB &&
"Expected call site!");
835 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB))
840 assert(CB &&
"Expected call site!");
843 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
848 if (
Arg.hasReturnedAttr()) {
849 IRPositions.emplace_back(
851 IRPositions.emplace_back(
860 assert(CB &&
"Expected call site!");
863 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
878 bool IgnoreSubsumingPositions,
Attributor *A)
const {
882 if (EquivIRP.getAttrsFromIRAttr(AK,
Attrs))
887 if (IgnoreSubsumingPositions)
892 if (getAttrsFromAssumes(AK,
Attrs, *A))
899 bool IgnoreSubsumingPositions,
Attributor *A)
const {
902 EquivIRP.getAttrsFromIRAttr(AK,
Attrs);
906 if (IgnoreSubsumingPositions)
911 getAttrsFromAssumes(AK,
Attrs, *A);
938 A.getInfoCache().getKnowledgeMap().lookup({&AssociatedValue, AK});
948 A.getInfoCache().getMustBeExecutedContextExplorer();
956 void IRPosition::verify() {
957 #ifdef EXPENSIVE_CHECKS
960 assert((CBContext ==
nullptr) &&
961 "Invalid position must not have CallBaseContext!");
963 "Expected a nullptr for an invalid position!");
967 "Expected specialized kind for argument values!");
970 assert(isa<Function>(getAsValuePtr()) &&
971 "Expected function for a 'returned' position!");
973 "Associated value mismatch!");
976 assert((CBContext ==
nullptr) &&
977 "'call site returned' position must not have CallBaseContext!");
978 assert((isa<CallBase>(getAsValuePtr())) &&
979 "Expected call base for 'call site returned' position!");
981 "Associated value mismatch!");
984 assert((CBContext ==
nullptr) &&
985 "'call site function' position must not have CallBaseContext!");
986 assert((isa<CallBase>(getAsValuePtr())) &&
987 "Expected call base for 'call site function' position!");
989 "Associated value mismatch!");
992 assert(isa<Function>(getAsValuePtr()) &&
993 "Expected function for a 'function' position!");
995 "Associated value mismatch!");
998 assert(isa<Argument>(getAsValuePtr()) &&
999 "Expected argument for a 'argument' position!");
1001 "Associated value mismatch!");
1004 assert((CBContext ==
nullptr) &&
1005 "'call site argument' position must not have CallBaseContext!");
1006 Use *U = getAsUsePtr();
1008 assert(U &&
"Expected use for a 'call site argument' position!");
1009 assert(isa<CallBase>(U->getUser()) &&
1010 "Expected call base user for a 'call site argument' position!");
1011 assert(cast<CallBase>(U->getUser())->isArgOperand(U) &&
1012 "Expected call base argument operand for a 'call site argument' "
1014 assert(cast<CallBase>(U->getUser())->getArgOperandNo(U) ==
1016 "Argument number mismatch!");
1027 bool &UsedAssumedInformation) {
1031 for (
auto &CB : SimplificationCallbacks.lookup(IRP)) {
1035 if (isa_and_nonnull<Constant>(*SimplifiedV))
1036 return cast<Constant>(*SimplifiedV);
1041 const auto &ValueSimplifyAA =
1044 ValueSimplifyAA.getAssumedSimplifiedValue(*
this);
1045 bool IsKnown = ValueSimplifyAA.isAtFixpoint();
1046 UsedAssumedInformation |= !IsKnown;
1051 if (isa_and_nonnull<UndefValue>(SimplifiedV.
getValue())) {
1057 CI = dyn_cast_or_null<Constant>(
1067 bool &UsedAssumedInformation) {
1071 for (
auto &CB : SimplificationCallbacks.lookup(IRP))
1072 return CB(IRP,
AA, UsedAssumedInformation);
1075 const auto &ValueSimplifyAA =
1078 ValueSimplifyAA.getAssumedSimplifiedValue(*
this);
1079 bool IsKnown = ValueSimplifyAA.isAtFixpoint();
1080 UsedAssumedInformation |= !IsKnown;
1086 if (*SimplifiedV ==
nullptr)
1088 if (
Value *SimpleV =
1099 bool &UsedAssumedInformation) {
1102 if (*V ==
nullptr || isa<Constant>(*V))
1104 if (
auto *
Arg = dyn_cast<Argument>(*V))
1106 if (!
Arg->hasPointeeInMemoryValueAttr())
1109 UsedAssumedInformation);
1118 AA->~AbstractAttribute();
1124 bool &UsedAssumedInformation,
1125 bool CheckBBLivenessOnly,
DepClassTy DepClass) {
1130 CheckBBLivenessOnly, DepClass);
1136 bool &UsedAssumedInformation,
1137 bool CheckBBLivenessOnly,
DepClassTy DepClass) {
1141 UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
1143 if (
auto *CB = dyn_cast<CallBase>(UserI)) {
1146 if (CB->isArgOperand(&U)) {
1150 UsedAssumedInformation, CheckBBLivenessOnly,
1153 }
else if (
ReturnInst *RI = dyn_cast<ReturnInst>(UserI)) {
1156 UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
1157 }
else if (
PHINode *PHI = dyn_cast<PHINode>(UserI)) {
1158 BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
1160 UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
1161 }
else if (
StoreInst *
SI = dyn_cast<StoreInst>(UserI)) {
1162 if (!CheckBBLivenessOnly &&
SI->getPointerOperand() != U.
get()) {
1170 UsedAssumedInformation =
true;
1177 UsedAssumedInformation, CheckBBLivenessOnly, DepClass);
1183 bool &UsedAssumedInformation,
1184 bool CheckBBLivenessOnly,
DepClassTy DepClass) {
1188 if (ManifestAddedBlocks.contains(
I.getParent()))
1199 (CheckBBLivenessOnly ? FnLivenessAA->
isAssumedDead(
I.getParent())
1204 UsedAssumedInformation =
true;
1208 if (CheckBBLivenessOnly)
1215 if (QueryingAA == &IsDeadAA)
1222 UsedAssumedInformation =
true;
1232 bool &UsedAssumedInformation,
1233 bool CheckBBLivenessOnly,
DepClassTy DepClass) {
1236 isAssumedDead(*CtxI, QueryingAA, FnLivenessAA, UsedAssumedInformation,
1241 if (CheckBBLivenessOnly)
1247 IsDeadAA = &getOrCreateAAFor<AAIsDead>(
1253 if (QueryingAA == IsDeadAA)
1260 UsedAssumedInformation =
true;
1286 bool CheckBBLivenessOnly,
DepClassTy LivenessDepClass,
1287 bool IgnoreDroppableUses,
1299 Worklist.push_back(&U);
1302 <<
" initial uses to check\n");
1305 const auto *LivenessAA =
1310 while (!Worklist.empty()) {
1312 if (isa<PHINode>(U->getUser()) && !Visited.
insert(U).second)
1315 if (
auto *Fn = dyn_cast<Function>(U->getUser()))
1316 dbgs() <<
"[Attributor] Check use: " << **U <<
" in " << Fn->
getName()
1319 dbgs() <<
"[Attributor] Check use: " << **U <<
" in " << *U->getUser()
1322 bool UsedAssumedInformation =
false;
1323 if (
isAssumedDead(*U, &QueryingAA, LivenessAA, UsedAssumedInformation,
1324 CheckBBLivenessOnly, LivenessDepClass)) {
1328 if (IgnoreDroppableUses && U->getUser()->isDroppable()) {
1333 if (
auto *
SI = dyn_cast<StoreInst>(U->getUser())) {
1334 if (&
SI->getOperandUse(0) == U) {
1335 if (!Visited.
insert(U).second)
1339 *
this, *
SI, PotentialCopies, QueryingAA, UsedAssumedInformation,
1341 LLVM_DEBUG(
dbgs() <<
"[Attributor] Value is stored, continue with "
1342 << PotentialCopies.
size()
1343 <<
" potential copies instead!\n");
1344 for (
Value *PotentialCopy : PotentialCopies)
1345 for (
const Use &CopyUse : PotentialCopy->
uses()) {
1346 if (EquivalentUseCB && !EquivalentUseCB(*U, CopyUse)) {
1348 "rejected by the equivalence call back: "
1349 << *CopyUse <<
"!\n");
1352 Worklist.push_back(&CopyUse);
1359 bool Follow =
false;
1360 if (!Pred(*U, Follow))
1364 for (
const Use &UU : U->getUser()->
uses())
1365 Worklist.push_back(&UU);
1373 bool RequireAllCallSites,
1374 bool &UsedAssumedInformation) {
1380 if (!AssociatedFunction) {
1381 LLVM_DEBUG(
dbgs() <<
"[Attributor] No function associated with " << IRP
1387 &QueryingAA, UsedAssumedInformation);
1392 bool RequireAllCallSites,
1394 bool &UsedAssumedInformation) {
1398 <<
"[Attributor] Function " << Fn.
getName()
1399 <<
" has no internal linkage, hence not all call sites are known\n");
1404 for (
unsigned u = 0; u <
Uses.size(); ++u) {
1407 if (
auto *Fn = dyn_cast<Function>(U))
1408 dbgs() <<
"[Attributor] Check use: " << Fn->
getName() <<
" in "
1411 dbgs() <<
"[Attributor] Check use: " << *U <<
" in " << *U.
getUser()
1414 if (
isAssumedDead(U, QueryingAA,
nullptr, UsedAssumedInformation,
1420 if (CE->isCast() && CE->getType()->isPointerTy()) {
1422 dbgs() <<
"[Attributor] Use, is constant cast expression, add "
1424 <<
" uses of that expression instead!\n");
1425 for (
const Use &CEU : CE->uses())
1426 Uses.push_back(&CEU);
1434 <<
" has non call site use " << *U.
get() <<
" in "
1437 if (isa<BlockAddress>(U.
getUser()))
1442 const Use *EffectiveUse =
1445 if (!RequireAllCallSites) {
1446 LLVM_DEBUG(
dbgs() <<
"[Attributor] User " << *EffectiveUse->getUser()
1447 <<
" is not a call of " << Fn.
getName()
1451 LLVM_DEBUG(
dbgs() <<
"[Attributor] User " << *EffectiveUse->getUser()
1452 <<
" is an invalid use of " << Fn.
getName() <<
"\n");
1460 unsigned MinArgsParams =
1462 for (
unsigned u = 0; u < MinArgsParams; ++u) {
1466 dbgs() <<
"[Attributor] Call site / callee argument type mismatch ["
1467 << u <<
"@" << Fn.
getName() <<
": "
1477 LLVM_DEBUG(
dbgs() <<
"[Attributor] Call site callback failed for "
1485 bool Attributor::shouldPropagateCallBaseContext(
const IRPosition &IRP) {
1500 if (!AssociatedFunction)
1507 const auto &AARetVal =
1509 if (!AARetVal.getState().isValidState())
1512 return AARetVal.checkForAllReturnedValuesAndReturnInsts(Pred);
1520 if (!AssociatedFunction)
1526 const auto &AARetVal =
1528 if (!AARetVal.getState().isValidState())
1531 return AARetVal.checkForAllReturnedValuesAndReturnInsts(
1541 bool &UsedAssumedInformation,
bool CheckBBLivenessOnly =
false,
1542 bool CheckPotentiallyDead =
false) {
1543 for (
unsigned Opcode : Opcodes) {
1545 auto *Insts = OpcodeInstMap.
lookup(Opcode);
1551 if (A && !CheckPotentiallyDead &&
1553 UsedAssumedInformation, CheckBBLivenessOnly)) {
1555 <<
" is potentially dead, skip!\n";);
1570 bool &UsedAssumedInformation,
1571 bool CheckBBLivenessOnly,
1572 bool CheckPotentiallyDead) {
1579 const auto *LivenessAA =
1580 (CheckBBLivenessOnly || CheckPotentiallyDead)
1586 LivenessAA, Opcodes, UsedAssumedInformation,
1587 CheckBBLivenessOnly, CheckPotentiallyDead))
1596 bool &UsedAssumedInformation,
1597 bool CheckBBLivenessOnly,
1598 bool CheckPotentiallyDead) {
1602 UsedAssumedInformation, CheckBBLivenessOnly,
1603 CheckPotentiallyDead);
1608 bool &UsedAssumedInformation) {
1610 const Function *AssociatedFunction =
1612 if (!AssociatedFunction)
1617 const auto &LivenessAA =
1624 UsedAssumedInformation))
1634 void Attributor::runTillFixpoint() {
1638 <<
" abstract attributes.\n");
1643 unsigned IterationCounter = 1;
1644 unsigned MaxIterations =
1654 LLVM_DEBUG(
dbgs() <<
"\n\n[Attributor] #Iteration: " << IterationCounter
1655 <<
", Worklist size: " << Worklist.
size() <<
"\n");
1660 for (
unsigned u = 0; u < InvalidAAs.
size(); ++u) {
1664 LLVM_DEBUG(
dbgs() <<
"[Attributor] InvalidAA: " << *InvalidAA <<
" has "
1665 << InvalidAA->
Deps.size()
1666 <<
" required & optional dependences\n");
1667 while (!InvalidAA->
Deps.empty()) {
1668 const auto &Dep = InvalidAA->
Deps.back();
1669 InvalidAA->
Deps.pop_back();
1680 InvalidAAs.
insert(DepAA);
1682 ChangedAAs.push_back(DepAA);
1689 while (!ChangedAA->Deps.empty()) {
1691 cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
1692 ChangedAA->Deps.pop_back();
1695 LLVM_DEBUG(
dbgs() <<
"[Attributor] #Iteration: " << IterationCounter
1696 <<
", Worklist+Dependent size: " << Worklist.
size()
1706 const auto &AAState =
AA->getState();
1707 if (!AAState.isAtFixpoint())
1709 ChangedAAs.push_back(
AA);
1713 if (!AAState.isValidState())
1725 Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
1726 Worklist.insert(QueryAAsAwaitingUpdate.begin(),
1727 QueryAAsAwaitingUpdate.end());
1728 QueryAAsAwaitingUpdate.clear();
1730 }
while (!Worklist.empty() &&
1733 if (IterationCounter > MaxIterations && !Functions.
empty()) {
1735 return ORM <<
"Attributor did not reach a fixpoint after "
1736 <<
ore::NV(
"Iterations", MaxIterations) <<
" iterations.";
1739 emitRemark<OptimizationRemarkMissed>(
F,
"FixedPoint", Remark);
1742 LLVM_DEBUG(
dbgs() <<
"\n[Attributor] Fixpoint iteration done after: "
1743 << IterationCounter <<
"/" << MaxIterations
1744 <<
" iterations\n");
1752 for (
unsigned u = 0; u < ChangedAAs.size(); u++) {
1754 if (!Visited.
insert(ChangedAA).second)
1761 NumAttributesTimedOut++;
1764 while (!ChangedAA->
Deps.empty()) {
1765 ChangedAAs.push_back(
1766 cast<AbstractAttribute>(ChangedAA->
Deps.back().getPointer()));
1767 ChangedAA->
Deps.pop_back();
1772 if (!Visited.
empty())
1773 dbgs() <<
"\n[Attributor] Finalized " << Visited.
size()
1774 <<
" abstract attributes.\n";
1778 errs() <<
"\n[Attributor] Fixpoint iteration done after: "
1779 << IterationCounter <<
"/" <<
MaxIterations <<
" iterations\n";
1780 llvm_unreachable(
"The fixpoint was not reached with exactly the number of "
1781 "specified iterations!");
1787 "Non-query AAs should not be required to register for updates!");
1788 QueryAAsAwaitingUpdate.insert(&
AA);
1795 unsigned NumManifested = 0;
1796 unsigned NumAtFixpoint = 0;
1810 if (
AA->hasCallBaseContext())
1816 if (
AA->getCtxI() && !
isRunOn(*
AA->getAnchorScope()))
1820 bool UsedAssumedInformation =
false;
1831 AA->trackStatistics();
1832 LLVM_DEBUG(
dbgs() <<
"[Attributor] Manifest " << LocalChange <<
" : " << *
AA
1835 ManifestChange = ManifestChange | LocalChange;
1841 (void)NumManifested;
1842 (void)NumAtFixpoint;
1843 LLVM_DEBUG(
dbgs() <<
"\n[Attributor] Manifested " << NumManifested
1844 <<
" arguments while " << NumAtFixpoint
1845 <<
" were in a valid fixpoint state\n");
1847 NumAttributesManifested += NumManifested;
1848 NumAttributesValidFixpoint += NumAtFixpoint;
1853 errs() <<
"Unexpected abstract attribute: "
1858 .getAssociatedValue()
1861 "remain unchanged!");
1863 return ManifestChange;
1866 void Attributor::identifyDeadInternalFunctions() {
1877 if (
F->hasLocalLinkage())
1878 InternalFns.push_back(
F);
1881 bool FoundLiveInternal =
true;
1882 while (FoundLiveInternal) {
1883 FoundLiveInternal =
false;
1884 for (
unsigned u = 0,
e = InternalFns.size(); u <
e; ++u) {
1889 bool UsedAssumedInformation =
false;
1893 return ToBeDeletedFunctions.count(Callee) ||
1894 (Functions.count(Callee) &&
Callee->hasLocalLinkage() &&
1895 !LiveInternalFns.
count(Callee));
1897 *
F,
true,
nullptr, UsedAssumedInformation)) {
1902 InternalFns[u] =
nullptr;
1903 FoundLiveInternal =
true;
1907 for (
unsigned u = 0,
e = InternalFns.size(); u <
e; ++u)
1909 ToBeDeletedFunctions.insert(
F);
1916 << ToBeDeletedFunctions.size() <<
" functions and "
1917 << ToBeDeletedBlocks.size() <<
" blocks and "
1918 << ToBeDeletedInsts.size() <<
" instructions and "
1919 << ToBeChangedValues.size() <<
" values and "
1920 << ToBeChangedUses.size() <<
" uses. To insert "
1921 << ToBeChangedToUnreachableInsts.size() <<
" unreachables."
1922 <<
"Preserve manifest added " << ManifestAddedBlocks.size()
1928 auto ReplaceUse = [&](
Use *U,
Value *NewV) {
1929 Value *OldV = U->get();
1933 const auto &Entry = ToBeChangedValues.lookup(NewV);
1941 "Cannot replace an instruction outside the current SCC!");
1945 if (
auto *RI = dyn_cast_or_null<ReturnInst>(
I)) {
1947 if (CI->isMustTailCall() && !ToBeDeletedInsts.count(CI))
1951 if (!isa<Argument>(NewV))
1952 for (
auto &
Arg : RI->getFunction()->args())
1953 Arg.removeAttr(Attribute::Returned);
1957 if (
auto *CB = dyn_cast_or_null<CallBase>(
I))
1958 if (CB->isCallee(U))
1962 <<
" instead of " << *OldV <<
"\n");
1966 CGModifiedFunctions.insert(
I->getFunction());
1967 if (!isa<PHINode>(
I) && !ToBeDeletedInsts.count(
I) &&
1969 DeadInsts.push_back(
I);
1971 if (isa<UndefValue>(NewV) && isa<CallBase>(U->getUser())) {
1972 auto *CB = cast<CallBase>(U->getUser());
1973 if (CB->isArgOperand(U)) {
1974 unsigned Idx = CB->getArgOperandNo(U);
1975 CB->removeParamAttr(Idx, Attribute::NoUndef);
1976 Function *Fn = CB->getCalledFunction();
1981 if (isa<Constant>(NewV) && isa<BranchInst>(U->getUser())) {
1982 Instruction *UserI = cast<Instruction>(U->getUser());
1983 if (isa<UndefValue>(NewV)) {
1984 ToBeChangedToUnreachableInsts.insert(UserI);
1986 TerminatorsToFold.push_back(UserI);
1991 for (
auto &It : ToBeChangedUses) {
1993 Value *NewV = It.second;
1994 ReplaceUse(U, NewV);
1998 for (
auto &It : ToBeChangedValues) {
1999 Value *OldV = It.first;
2000 auto &Entry = It.second;
2001 Value *NewV = Entry.first;
2003 for (
auto &U : OldV->
uses())
2007 if (
auto *
I = dyn_cast<Instruction>(U->getUser()))
2010 ReplaceUse(U, NewV);
2014 for (
auto &V : InvokeWithDeadSuccessor)
2015 if (
InvokeInst *II = dyn_cast_or_null<InvokeInst>(V)) {
2017 "Cannot replace an invoke outside the current SCC!");
2018 bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind);
2019 bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn);
2020 bool Invoke2CallAllowed =
2022 assert((UnwindBBIsDead || NormalBBIsDead) &&
2023 "Invoke does not have dead successors!");
2025 BasicBlock *NormalDestBB = II->getNormalDest();
2026 if (UnwindBBIsDead) {
2028 if (Invoke2CallAllowed) {
2030 NormalNextIP =
BB->getTerminator();
2033 ToBeChangedToUnreachableInsts.insert(NormalNextIP);
2035 assert(NormalBBIsDead &&
"Broken invariant!");
2038 ToBeChangedToUnreachableInsts.insert(&NormalDestBB->
front());
2043 "Cannot replace a terminator outside the current SCC!");
2044 CGModifiedFunctions.insert(
I->getFunction());
2047 for (
auto &V : ToBeChangedToUnreachableInsts)
2048 if (
Instruction *
I = dyn_cast_or_null<Instruction>(V)) {
2050 "Cannot replace an instruction outside the current SCC!");
2051 CGModifiedFunctions.insert(
I->getFunction());
2055 for (
auto &V : ToBeDeletedInsts) {
2056 if (
Instruction *
I = dyn_cast_or_null<Instruction>(V)) {
2057 if (
auto *CB = dyn_cast<CallBase>(
I)) {
2059 "Cannot delete an instruction outside the current SCC!");
2060 if (!isa<IntrinsicInst>(CB))
2063 I->dropDroppableUses();
2064 CGModifiedFunctions.insert(
I->getFunction());
2065 if (!
I->getType()->isVoidTy())
2068 DeadInsts.push_back(
I);
2070 I->eraseFromParent();
2077 dbgs() <<
"[Attributor] DeadInsts size: " << DeadInsts.size() <<
"\n";
2078 for (
auto &
I : DeadInsts)
2080 dbgs() <<
" - " << *
I <<
"\n";
2085 if (
unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) {
2087 ToBeDeletedBBs.
reserve(NumDeadBlocks);
2090 "Cannot delete a block outside the current SCC!");
2091 CGModifiedFunctions.insert(
BB->getParent());
2093 if (ManifestAddedBlocks.contains(
BB))
2095 ToBeDeletedBBs.push_back(
BB);
2103 identifyDeadInternalFunctions();
2106 ChangeStatus ManifestChange = rewriteFunctionSignatures(CGModifiedFunctions);
2108 for (
Function *Fn : CGModifiedFunctions)
2109 if (!ToBeDeletedFunctions.count(Fn) && Functions.count(Fn))
2112 for (
Function *Fn : ToBeDeletedFunctions) {
2113 if (!Functions.count(Fn))
2118 if (!ToBeChangedUses.empty())
2121 if (!ToBeChangedToUnreachableInsts.empty())
2124 if (!ToBeDeletedFunctions.empty())
2127 if (!ToBeDeletedBlocks.empty())
2130 if (!ToBeDeletedInsts.empty())
2133 if (!InvokeWithDeadSuccessor.empty())
2136 if (!DeadInsts.empty())
2139 NumFnDeleted += ToBeDeletedFunctions.size();
2141 LLVM_DEBUG(
dbgs() <<
"[Attributor] Deleted " << ToBeDeletedFunctions.size()
2142 <<
" functions after manifest.\n");
2144 #ifdef EXPENSIVE_CHECKS
2146 if (ToBeDeletedFunctions.count(
F))
2152 return ManifestChange;
2162 Phase = AttributorPhase::UPDATE;
2175 Phase = AttributorPhase::MANIFEST;
2178 Phase = AttributorPhase::CLEANUP;
2184 return ManifestChange | CleanupChange;
2191 assert(Phase == AttributorPhase::UPDATE &&
2192 "We can update AA only in the update stage!");
2195 DependenceVector DV;
2196 DependenceStack.push_back(&DV);
2198 auto &AAState =
AA.getState();
2200 bool UsedAssumedInformation =
false;
2203 CS =
AA.update(*
this);
2205 if (!
AA.isQueryAA() && DV.empty()) {
2208 AAState.indicateOptimisticFixpoint();
2211 if (!AAState.isAtFixpoint())
2212 rememberDependences();
2216 DependenceVector *PoppedDV = DependenceStack.pop_back_val();
2218 assert(PoppedDV == &DV &&
"Inconsistent usage of the dependence stack!");
2224 assert(!
F.isDeclaration() &&
"Cannot create a wrapper around a declaration!");
2233 M.getFunctionList().insert(
F.getIterator(),
Wrapper);
2238 assert(
F.use_empty() &&
"Uses remained after wrapper was created!");
2243 F.setComdat(
nullptr);
2247 F.getAllMetadata(MDs);
2248 for (
auto MDIt : MDs)
2249 Wrapper->addMetadata(MDIt.first, *MDIt.second);
2250 Wrapper->setAttributes(
F.getAttributes());
2267 NumFnShallowWrappersCreated++;
2271 if (
F.isDeclaration() ||
F.hasLocalLinkage() ||
2287 return InternalizedFns[&
F];
2305 F->getName() +
".internalized");
2308 for (
auto &
Arg :
F->args()) {
2309 auto ArgName =
Arg.getName();
2310 NewFArgIt->setName(ArgName);
2311 VMap[&
Arg] = &(*NewFArgIt++);
2326 F->getAllMetadata(MDs);
2327 for (
auto MDIt : MDs)
2331 M.getFunctionList().insert(
F->getIterator(), Copied);
2339 auto &InternalizedFn = FnMap[
F];
2340 auto IsNotInternalized = [&](
Use &U) ->
bool {
2341 if (
auto *CB = dyn_cast<CallBase>(U.
getUser()))
2342 return !FnMap.
lookup(CB->getCaller());
2345 F->replaceUsesWithIf(InternalizedFn, IsNotInternalized);
2374 LLVM_DEBUG(
dbgs() <<
"[Attributor] Cannot rewrite var-args functions\n");
2385 dbgs() <<
"[Attributor] Cannot rewrite due to complex attribute\n");
2390 bool UsedAssumedInformation =
false;
2392 UsedAssumedInformation)) {
2393 LLVM_DEBUG(
dbgs() <<
"[Attributor] Cannot rewrite all call sites\n");
2398 if (
auto *CI = dyn_cast<CallInst>(&
I))
2399 return !CI->isMustTailCall();
2408 UsedAssumedInformation)) {
2409 LLVM_DEBUG(
dbgs() <<
"[Attributor] Cannot rewrite due to instructions\n");
2421 <<
Arg.getParent()->getName() <<
" with "
2422 << ReplacementTypes.
size() <<
" replacements\n");
2424 "Cannot register an invalid rewrite");
2428 ArgumentReplacementMap[Fn];
2434 std::unique_ptr<ArgumentReplacementInfo> &ARI = ARIs[
Arg.getArgNo()];
2435 if (ARI && ARI->getNumReplacementArgs() <= ReplacementTypes.
size()) {
2436 LLVM_DEBUG(
dbgs() <<
"[Attributor] Existing rewrite is preferred\n");
2445 <<
Arg.getParent()->getName() <<
" with "
2446 << ReplacementTypes.
size() <<
" replacements\n");
2472 for (
auto &It : ArgumentReplacementMap) {
2476 if (!Functions.count(OldFn) || ToBeDeletedFunctions.count(OldFn))
2481 assert(ARIs.size() == OldFn->
arg_size() &&
"Inconsistent state!");
2489 if (
const std::unique_ptr<ArgumentReplacementInfo> &ARI =
2490 ARIs[
Arg.getArgNo()]) {
2491 NewArgumentTypes.
append(ARI->ReplacementTypes.begin(),
2492 ARI->ReplacementTypes.end());
2493 NewArgumentAttributes.
append(ARI->getNumReplacementArgs(),
2496 NewArgumentTypes.push_back(
Arg.getType());
2497 NewArgumentAttributes.push_back(
2503 for (
auto *
I : NewArgumentTypes)
2504 if (
auto *VT = dyn_cast<llvm::VectorType>(
I))
2506 LargestVectorWidth, VT->getPrimitiveSizeInBits().getKnownMinSize());
2517 << *NewFnTy <<
"\n");
2522 Functions.insert(NewFn);
2536 NewArgumentAttributes));
2548 if (
auto *BA = dyn_cast<BlockAddress>(U))
2549 BlockAddresses.push_back(BA);
2550 for (
auto *BA : BlockAddresses)
2565 for (
unsigned OldArgNum = 0; OldArgNum < ARIs.size(); ++OldArgNum) {
2566 unsigned NewFirstArgNum = NewArgOperands.size();
2567 (void)NewFirstArgNum;
2568 if (
const std::unique_ptr<ArgumentReplacementInfo> &ARI =
2570 if (ARI->ACSRepairCB)
2571 ARI->ACSRepairCB(*ARI, ACS, NewArgOperands);
2572 assert(ARI->getNumReplacementArgs() + NewFirstArgNum ==
2573 NewArgOperands.size() &&
2574 "ACS repair callback did not provide as many operand as new "
2575 "types were registered!");
2577 NewArgOperandAttributes.
append(ARI->ReplacementTypes.size(),
2581 NewArgOperandAttributes.push_back(
2586 assert(NewArgOperands.size() == NewArgOperandAttributes.size() &&
2587 "Mismatch # argument operands vs. # argument operand attributes!");
2589 "Mismatch # argument operands vs. # function arguments!");
2596 if (
InvokeInst *II = dyn_cast<InvokeInst>(OldCB)) {
2599 NewArgOperands, OperandBundleDefs,
"", OldCB);
2603 NewCI->setTailCallKind(cast<CallInst>(OldCB)->getTailCallKind());
2608 NewCB->
copyMetadata(*OldCB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});
2613 OldCallAttributeList.
getRetAttrs(), NewArgOperandAttributes));
2616 LargestVectorWidth);
2618 CallSitePairs.push_back({OldCB, NewCB});
2623 bool UsedAssumedInformation =
false;
2625 true,
nullptr, UsedAssumedInformation);
2627 assert(
Success &&
"Assumed call site replacement to succeed!");
2632 for (
unsigned OldArgNum = 0; OldArgNum < ARIs.size();
2633 ++OldArgNum, ++OldFnArgIt) {
2634 if (
const std::unique_ptr<ArgumentReplacementInfo> &ARI =
2636 if (ARI->CalleeRepairCB)
2637 ARI->CalleeRepairCB(*ARI, *NewFn, NewFnArgIt);
2638 if (ARI->ReplacementTypes.empty())
2641 NewFnArgIt += ARI->ReplacementTypes.size();
2643 NewFnArgIt->
takeName(&*OldFnArgIt);
2650 for (
auto &CallSitePair : CallSitePairs) {
2651 CallBase &OldCB = *CallSitePair.first;
2652 CallBase &NewCB = *CallSitePair.second;
2654 "Cannot handle call sites with different types!");
2666 if (ModifiedFns.
remove(OldFn))
2667 ModifiedFns.
insert(NewFn);
2675 void InformationCache::initializeInformationCache(
const Function &CF,
2691 auto AddToAssumeUsesMap = [&](
const Value &V) ->
void {
2693 if (
auto *
I = dyn_cast<Instruction>(&V))
2694 Worklist.push_back(
I);
2695 while (!Worklist.empty()) {
2699 NumUses =
I->getNumUses();
2703 AssumeOnlyValues.insert(
I);
2704 for (
const Value *
Op :
I->operands())
2705 if (
auto *OpI = dyn_cast<Instruction>(
Op))
2706 Worklist.push_back(OpI);
2711 bool IsInterestingOpcode =
false;
2718 switch (
I.getOpcode()) {
2721 "New call base instruction type needs to be known in the "
2728 if (
auto *Assume = dyn_cast<AssumeInst>(&
I)) {
2730 AddToAssumeUsesMap(*Assume->getArgOperand(0));
2732 FI.ContainsMustTailCall =
true;
2734 getFunctionInfo(*Callee).CalledViaMustTail =
true;
2737 case Instruction::CallBr:
2738 case Instruction::Invoke:
2739 case Instruction::CleanupRet:
2740 case Instruction::CatchSwitch:
2741 case Instruction::AtomicRMW:
2742 case Instruction::AtomicCmpXchg:
2743 case Instruction::Br:
2744 case Instruction::Resume:
2750 case Instruction::Alloca:
2751 case Instruction::AddrSpaceCast:
2752 IsInterestingOpcode =
true;
2754 if (IsInterestingOpcode) {
2755 auto *&Insts = FI.OpcodeInstMap[
I.getOpcode()];
2758 Insts->push_back(&
I);
2760 if (
I.mayReadOrWriteMemory())
2761 FI.RWInsts.push_back(&
I);
2764 if (
F.hasFnAttribute(Attribute::AlwaysInline) &&
2766 InlineableFunctions.insert(&
F);
2773 InformationCache::FunctionInfo::~FunctionInfo() {
2776 for (
auto &It : OpcodeInstMap)
2777 It.getSecond()->~InstructionVectorTy();
2788 if (DependenceStack.empty())
2792 DependenceStack.back()->push_back({&FromAA, &ToAA, DepClass});
2795 void Attributor::rememberDependences() {
2796 assert(!DependenceStack.empty() &&
"No dependences to remember!");
2798 for (DepInfo &DI : *DependenceStack.back()) {
2801 "Expected required or optional dependence (1 bit)!");
2809 if (!VisitedFunctions.insert(&
F).second)
2811 if (
F.isDeclaration())
2817 InformationCache::FunctionInfo &FI = InfoCache.getFunctionInfo(
F);
2819 for (
const Use &U :
F.uses())
2820 if (
const auto *CB = dyn_cast<CallBase>(U.
getUser()))
2821 if (CB->isCallee(&U) && CB->isMustTailCall())
2822 FI.CalledViaMustTail =
true;
2830 getOrCreateAAFor<AAIsDead>(FPos);
2833 getOrCreateAAFor<AAWillReturn>(FPos);
2836 getOrCreateAAFor<AAUndefinedBehavior>(FPos);
2839 getOrCreateAAFor<AANoUnwind>(FPos);
2842 getOrCreateAAFor<AANoSync>(FPos);
2845 getOrCreateAAFor<AANoFree>(FPos);
2848 getOrCreateAAFor<AANoReturn>(FPos);
2851 getOrCreateAAFor<AANoRecurse>(FPos);
2854 getOrCreateAAFor<AAMemoryBehavior>(FPos);
2857 getOrCreateAAFor<AAMemoryLocation>(FPos);
2860 getOrCreateAAFor<AAAssumptionInfo>(FPos);
2864 getOrCreateAAFor<AAHeapToStack>(FPos);
2871 getOrCreateAAFor<AAReturnedValues>(FPos);
2876 getOrCreateAAFor<AAIsDead>(RetPos);
2879 bool UsedAssumedInformation =
false;
2883 getOrCreateAAFor<AANoUndef>(RetPos);
2888 getOrCreateAAFor<AAAlign>(RetPos);
2891 getOrCreateAAFor<AANonNull>(RetPos);
2894 getOrCreateAAFor<AANoAlias>(RetPos);
2898 getOrCreateAAFor<AADereferenceable>(RetPos);
2908 bool UsedAssumedInformation =
false;
2912 getOrCreateAAFor<AAIsDead>(ArgPos);
2915 getOrCreateAAFor<AANoUndef>(ArgPos);
2917 if (
Arg.getType()->isPointerTy()) {
2919 getOrCreateAAFor<AANonNull>(ArgPos);
2922 getOrCreateAAFor<AANoAlias>(ArgPos);
2925 getOrCreateAAFor<AADereferenceable>(ArgPos);
2928 getOrCreateAAFor<AAAlign>(ArgPos);
2931 getOrCreateAAFor<AANoCapture>(ArgPos);
2935 getOrCreateAAFor<AAMemoryBehavior>(ArgPos);
2938 getOrCreateAAFor<AANoFree>(ArgPos);
2941 getOrCreateAAFor<AAPrivatizablePtr>(ArgPos);
2946 auto &CB = cast<CallBase>(
I);
2952 getOrCreateAAFor<AAIsDead>(CBInstPos);
2961 getOrCreateAAFor<AAAssumptionInfo>(CBFnPos);
2966 !
Callee->hasMetadata(LLVMContext::MD_callback))
2969 if (!
Callee->getReturnType()->isVoidTy() && !CB.use_empty()) {
2972 bool UsedAssumedInformation =
false;
2976 for (
int I = 0,
E = CB.arg_size();
I <
E; ++
I) {
2981 getOrCreateAAFor<AAIsDead>(CBArgPos);
2986 bool UsedAssumedInformation =
false;
2990 getOrCreateAAFor<AANoUndef>(CBArgPos);
2992 if (!CB.getArgOperand(
I)->getType()->isPointerTy())
2996 getOrCreateAAFor<AANonNull>(CBArgPos);
2999 getOrCreateAAFor<AANoCapture>(CBArgPos);
3002 getOrCreateAAFor<AANoAlias>(CBArgPos);
3005 getOrCreateAAFor<AADereferenceable>(CBArgPos);
3008 getOrCreateAAFor<AAAlign>(CBArgPos);
3012 getOrCreateAAFor<AAMemoryBehavior>(CBArgPos);
3015 getOrCreateAAFor<AANoFree>(CBArgPos);
3022 bool UsedAssumedInformation =
false;
3024 nullptr, OpcodeInstMap, CallSitePred,
nullptr,
nullptr,
3025 {(unsigned)Instruction::Invoke, (
unsigned)Instruction::CallBr,
3027 UsedAssumedInformation);
3029 assert(
Success &&
"Expected the check call to be successful!");
3032 if (isa<LoadInst>(
I)) {
3033 getOrCreateAAFor<AAAlign>(
3037 UsedAssumedInformation);
3039 auto &
SI = cast<StoreInst>(
I);
3042 UsedAssumedInformation);
3048 nullptr, OpcodeInstMap, LoadStorePred,
nullptr,
nullptr,
3050 UsedAssumedInformation);
3052 assert(
Success &&
"Expected the check call to be successful!");
3069 return OS <<
"fn_ret";
3071 return OS <<
"cs_ret";
3079 return OS <<
"cs_arg";
3095 OS <<
"range-state(" <<
S.getBitWidth() <<
")<";
3096 S.getKnown().print(OS);
3098 S.getAssumed().print(OS);
3101 return OS << static_cast<const AbstractState &>(
S);
3105 return OS << (!
S.isValidState() ?
"top" : (
S.isAtFixpoint() ?
"fix" :
""));
3115 OS <<
"set-state(< {";
3116 if (!
S.isValidState())
3119 for (
auto &It :
S.getAssumedSet())
3121 if (
S.undefIsContained())
3132 OS <<
"] for CtxI ";
3139 OS <<
"<<null inst>>";
3148 for (
const auto &DepAA :
Deps) {
3149 auto *
AA = DepAA.getPointer();
3166 OS <<
" [ <unknown> ]";
3180 bool DeleteFns,
bool IsModulePass) {
3181 if (Functions.
empty())
3185 dbgs() <<
"[Attributor] Run on module with " << Functions.
size()
3194 AC.IsModulePass = IsModulePass;
3195 AC.DeleteFns = DeleteFns;
3201 if (!A.isFunctionIPOAmendable(*
F))
3209 unsigned FunSize = Functions.size();
3210 for (
unsigned u = 0; u < FunSize; u++) {
3212 if (!
F->isDeclaration() && !
F->isDefinitionExact() &&
F->getNumUses() &&
3215 assert(NewF &&
"Could not internalize function.");
3216 Functions.insert(NewF);
3220 for (
const Use &U : NewF->
uses())
3222 auto *CallerF = CB->getCaller();
3230 if (
F->hasExactDefinition())
3231 NumFnWithExactDefinition++;
3233 NumFnWithoutExactDefinition++;
3238 if (
F->hasLocalLinkage()) {
3240 const auto *CB = dyn_cast<CallBase>(U.getUser());
3241 return CB && CB->isCallee(&U) &&
3242 Functions.count(const_cast<Function *>(CB->getCaller()));
3249 A.identifyDefaultAbstractAttributes(*
F);
3254 LLVM_DEBUG(
dbgs() <<
"[Attributor] Done with " << Functions.size()
3255 <<
" functions, result: " << Changed <<
".\n");
3262 static std::atomic<int> CallTimes;
3269 std::string Filename =
3272 outs() <<
"Dependency graph dump to " << Filename <<
".\n";
3285 cast<AbstractAttribute>(DepAA.getPointer())->printWithDeps(
outs());
3318 Functions.
insert(&
N.getFunction());
3320 if (Functions.
empty())
3349 using ChildIteratorType =
3362 using nodes_iterator =
3375 std::string AAString;
3386 struct AttributorLegacyPass :
public ModulePass {
3393 bool runOnModule(
Module &M)
override {
3433 if (Functions.
empty())
3459 return new AttributorCGSCCLegacyPass();
3466 "Deduce and propagate attributes",
false,
false)
bool isValidAtPosition(const ValueAndContext &VAC, InformationCache &InfoCache)
Return true if the value of VAC is a valid at the position of VAC, that is a constant,...
virtual bool isKnownDead() const =0
Returns true if the underlying value is known dead.
A set of analyses that are preserved following a run of a transformation pass.
Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph.
static NodeRef getEntryNode(AADepGraphNode *DGN)
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
This class represents an incoming formal argument to a Function.
bool isAssumedNoSync() const
Returns true if "nosync" is assumed.
A manager for alias analyses.
static const IRPosition function(const Function &F, const CallBaseContext *CBContext=nullptr)
Create a position describing the function scope of F.
Value * getCalledOperand() const
Return the pointer to function that is being called.
static StringRef getName(Value *V)
void initializeAttributorLegacyPassPass(PassRegistry &)
This is an optimization pass for GlobalISel generic memory operations.
bool isEnumAttribute() const
Return true if the attribute is an Attribute::AttrKind type.
static ChildIteratorType child_end(NodeRef N)
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
iterator_range< arg_iterator > args()
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
The TimeTraceScope is a helper class to call the begin and end functions of the time trace profiler.
void setTailCall(bool IsTc=true)
Return a value (possibly void), from a function.
Value handle that is nullable, but tries to track the Value.
const CallBaseContext * getCallBaseContext() const
Get the call base context from the position.
bool checkForAllUses(function_ref< bool(const Use &, bool &)> Pred, const AbstractAttribute &QueryingAA, const Value &V, bool CheckBBLivenessOnly=false, DepClassTy LivenessDepClass=DepClassTy::OPTIONAL, bool IgnoreDroppableUses=true, function_ref< bool(const Use &OldU, const Use &NewU)> EquivalentUseCB=nullptr)
Check Pred on all (transitive) uses of V.
Function * getAssociatedFunction() const
Return the associated function, if any.
static void getCallbackUses(const CallBase &CB, SmallVectorImpl< const Use * > &CallbackUses)
Add operand uses of CB that represent callback uses into CallbackUses.
bool hasAttrSomewhere(Attribute::AttrKind Kind, unsigned *Index=nullptr) const
Return true if the specified attribute is set for at least one parameter or for the return value.
static nodes_iterator nodes_begin(AADepGraph *DG)
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
bool isPointerTy() const
True if this is an instance of PointerType.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Helper struct used in the communication between an abstract attribute (AA) that wants to change the s...
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
static cl::opt< bool > EnableHeapToStack("enable-heap-to-stack-conversion", cl::init(true), cl::Hidden)
LinkageTypes getLinkage() const
static Function * getFunction(Constant *C)
LocationClass< Ty > location(Ty &L)
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
bool replaceCallSite(CallBase &OldCS, CallBase &NewCS)
Replace OldCS with the new call site NewCS.
ChangeStatus update(Attributor &A)
Hook for the Attributor to trigger an update of the internal state.
bool isKnownReadNone() const
Return true if we know that the associated functions has no observable accesses.
A raw_ostream that writes to an std::string.
size_type size() const
Determine the number of elements in the SetVector.
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
An abstract attribute for norecurse.
An abstract interface to determine reachability of point A to B.
static bool isNoSyncIntrinsic(const Instruction *I)
Helper function specific for intrinsics which are potentially volatile.
amdgpu aa AMDGPU Address space based Alias Analysis Wrapper
static const IRPosition value(const Value &V, const CallBaseContext *CBContext=nullptr)
Create a position describing the value of V.
static bool isNonRelaxedAtomic(const Instruction *I)
Helper function used to determine whether an instruction is non-relaxed atomic.
DISubprogram * getSubprogram() const
Get the attached subprogram.
static NodeRef getEntryNode(AADepGraph *DG)
virtual const std::string getName() const =0
This function should return the name of the AbstractAttribute.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
SubsumingPositionIterator(const IRPosition &IRP)
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
The basic data container for the call graph of a Module of IR.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionAnalysisManager FAM
void getAttrs(ArrayRef< Attribute::AttrKind > AKs, SmallVectorImpl< Attribute > &Attrs, bool IgnoreSubsumingPositions=false, Attributor *A=nullptr) const
Return the attributes of any kind in AKs existing in the IR at a position that will affect this one.
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
void dumpGraph()
Dump graph to file.
void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)
Replace contents of every block in BBs with single unreachable instruction.
bool isRunOn(Function &Fn) const
Return true if we derive attributes for Fn.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
virtual ChangeStatus indicatePessimisticFixpoint()=0
Indicate that the abstract state should converge to the pessimistic state.
The instances of the Type class are immutable: once they are created, they are never changed.
AttributeList getAttributes() const
Return the parameter attributes for this call.
Type * getAssociatedType() const
Return the type this abstract attribute is associated with.
AttributeSet getFnAttrs() const
The function attributes are returned.
static bool checkForAllInstructionsImpl(Attributor *A, InformationCache::OpcodeInstMapTy &OpcodeInstMap, function_ref< bool(Instruction &)> Pred, const AbstractAttribute *QueryingAA, const AAIsDead *LivenessAA, const ArrayRef< unsigned > &Opcodes, bool &UsedAssumedInformation, bool CheckBBLivenessOnly=false, bool CheckPotentiallyDead=false)
INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor", "Deduce and propagate attributes", false, false) INITIALIZE_PASS_END(AttributorLegacyPass
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Configuration for the Attributor.
InlineResult isInlineViable(Function &Callee)
Minimal filter to detect invalid constructs for inlining.
@ DefaultVisibility
The GV is visible.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
AADepGraphNode SyntheticRoot
There is no root node for the dependency graph.
Instruction * getRemoteInst() const
Return the actual instruction that causes the access.
void recordDependence(const AbstractAttribute &FromAA, const AbstractAttribute &ToAA, DepClassTy DepClass)
Explicitly record a dependence from FromAA to ToAA, that is if FromAA changes ToAA should be updated ...
DiagnosticInfoOptimizationBase::Argument NV
static bool isMustTailCall(Value *V)
ChangeStatus run()
Run the analyses until a fixpoint is reached or enforced (timeout).
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ IRP_ARGUMENT
An attribute for a function argument.
bool isWrittenValueUnknown() const
Return true if the value written cannot be determined at all.
@ IRP_RETURNED
An attribute for the function return value.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
Deduce and propagate attributes
void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)
ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, then cleanup.
Pass * createAttributorLegacyPass()
bool checkForAllReturnedValues(function_ref< bool(Value &)> Pred, const AbstractAttribute &QueryingAA)
Check Pred on all values potentially returned by the function associated with QueryingAA.
CallInst * changeToCall(InvokeInst *II, DomTreeUpdater *DTU=nullptr)
This function converts the specified invoek into a normall call.
LLVM_NODISCARD T pop_back_val()
An abstract Attribute for computing reachability between functions.
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
We currently generate a but we really shouldn eax ecx xorl edx divl ecx eax divl ecx movl eax ret A similar code sequence works for division We currently compile i32 v2 eax eax jo LBB1_2 and
bool hasCallBaseContext() const
Check if the position has any call base context.
unsigned getNumArgOperands() const
Return the number of parameters of the callee.
static bool mayCatchAsynchronousExceptions(const Function &F)
Determine if F might catch asynchronous exceptions.
@ IRP_FLOAT
A position that is not associated with a spot suitable for attributes.
void setDSOLocal(bool Local)
unsigned MaxInitializationChainLength
The value passed to the line option that defines the maximal initialization chain length.
static cl::opt< bool > AnnotateDeclarationCallSites("attributor-annotate-decl-cs", cl::Hidden, cl::desc("Annotate call sites of function declarations."), cl::init(false))
void addAttributeAtIndex(unsigned i, Attribute Attr)
adds the attribute to the list of attributes.
static Constant * getPointerCast(Constant *C, Type *Ty)
Create a BitCast, AddrSpaceCast, or a PtrToInt cast constant expression.
SmallPtrSet< MachineInstr *, 2 > Uses
static cl::opt< bool > DumpDepGraph("attributor-dump-dep-graph", cl::Hidden, cl::desc("Dump the dependency graph to dot files."), cl::init(false))
LLVM Basic Block Representation.
constexpr bool hasValue() const
Pass * createAttributorCGSCCLegacyPass()
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isKnownReadNone() const
Return true if we know that the underlying value is not read or accessed in its respective scope.
static cl::list< std::string > FunctionSeedAllowList("attributor-function-seed-allow-list", cl::Hidden, cl::desc("Comma seperated list of function names that are " "allowed to be seeded."), cl::CommaSeparated)
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
bool checkForAllCallSites(function_ref< bool(AbstractCallSite)> Pred, const AbstractAttribute &QueryingAA, bool RequireAllCallSites, bool &UsedAssumedInformation)
Check Pred on all function call sites.
bool DeleteFns
Flag to determine if we can delete functions or keep dead ones around.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
bool remove(const value_type &X)
Remove an item from the set vector.
uint64_t getValueAsInt() const
Return the attribute's value as an integer.
bool hasAttributeAtIndex(unsigned Index, Attribute::AttrKind Kind) const
Return true if the attribute exists at the given index.
An information struct used to provide DenseMap with the various necessary components for a given valu...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
bool AreStatisticsEnabled()
Check if statistics are enabled.
static ChildIteratorType child_begin(NodeRef N)
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
An SCC of the call graph.
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
raw_fd_ostream & outs()
This returns a reference to a raw_fd_ostream for standard output.
An abstract interface for memory access kind related attributes (readnone/readonly/writeonly).
Value * getWrittenValue() const
Return the value writen, if any.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
virtual StateType & getState()=0
Return the internal abstract state for inspection.
static const IRPosition inst(const Instruction &I, const CallBaseContext *CBContext=nullptr)
Create a position describing the instruction I.
static cl::opt< bool > AllowShallowWrappers("attributor-allow-shallow-wrappers", cl::Hidden, cl::desc("Allow the Attributor to create shallow " "wrappers for non-exact definitions."), cl::init(false))
static cl::opt< bool > PrintCallGraph("attributor-print-call-graph", cl::Hidden, cl::desc("Print Attributor's internal call graph"), cl::init(false))
(vector float) vec_cmpeq(*A, *B) C
virtual void printWithDeps(raw_ostream &OS) const
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Represent the analysis usage information of a pass.
static cl::opt< bool > AllowDeepWrapper("attributor-allow-deep-wrappers", cl::Hidden, cl::desc("Allow the Attributor to use IP information " "derived from non-exact functions via cloning"), cl::init(false))
AADepGraphNode * GetEntryNode()
void print()
Print dependency graph.
An abstract interface for all memory location attributes (readnone/argmemonly/inaccessiblememonly/ina...
iterator_range< use_iterator > uses()
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static cl::opt< std::string > DepGraphDotFileNamePrefix("attributor-depgraph-dot-filename-prefix", cl::Hidden, cl::desc("The prefix used for the CallGraph dot file names."))
modulo schedule Modulo Schedule test pass
bool checkForAllInstructions(function_ref< bool(Instruction &)> Pred, const Function *Fn, const AbstractAttribute &QueryingAA, const ArrayRef< unsigned > &Opcodes, bool &UsedAssumedInformation, bool CheckBBLivenessOnly=false, bool CheckPotentiallyDead=false)
Check Pred on all instructions in Fn with an opcode present in Opcodes.
bool hasAttr(ArrayRef< Attribute::AttrKind > AKs, bool IgnoreSubsumingPositions=false, Attributor *A=nullptr) const
TODO: Figure out if the attribute related helper functions should live here or somewhere else.
virtual bool isValidState() const =0
Return if this abstract state is in a valid state.
static bool shouldExecute(unsigned CounterName)
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
Kind getPositionKind() const
Return the associated position kind.
Instruction * getCtxI() const
Return the context instruction, if any.
@ OPTIONAL
The target may be valid if the source is not.
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
STATISTIC(NumFunctions, "Total number of functions")
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
This class implements an extremely fast bulk output stream that can only output to a stream.
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
removes the attribute from the list of attributes.
void addMetadata(unsigned KindID, MDNode &MD)
Add a metadata attachment.
State for an integer range.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
User * getUser() const
Returns the User that contains this Use.
StringRef getKindAsString() const
Return the attribute's kind as a string.
A node in the call graph for a module.
bool isStringAttribute() const
Return true if the attribute is a string (target-dependent) attribute.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
CallBase * getInstruction() const
Return the underlying instruction.
static nodes_iterator nodes_end(AADepGraph *DG)
bool getPotentialCopiesOfStoredValue(Attributor &A, StoreInst &SI, SmallSetVector< Value *, 4 > &PotentialCopies, const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation, bool OnlyExact=false)
Collect all potential values of the one stored by SI into PotentialCopies.
@ InternalLinkage
Rename collisions when linking (static functions).
CallingConv::ID getCallingConv() const
bool empty() const
Determine if the SetVector is empty or not.
static const IRPosition EmptyKey
Special DenseMap key values.
bool findInContextOf(const Instruction *I, const Instruction *PP)
Helper to look for I in the context of PP.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
virtual bool isAtFixpoint() const =0
Return if this abstract state is fixed, thus does not need to be updated if information changes as it...
Analysis::Result * getAnalysis(const Function &F)
TinyPtrVector< DepTy > Deps
Set of dependency graph nodes which should be updated if this one is updated.
virtual const std::string getAsStr() const =0
This function should return the "summarized" assumed state as string.
Function * getCaller()
Helper to get the caller (the parent function).
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
@ OF_TextWithCRLF
The file should be opened in text mode and use a carriage linefeed '\r '.
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
AttributeList getAttributes() const
Return the attribute list for this Function.
bool isValidInScope(const Value &V, const Function *Scope)
Return true if V is a valid value in Scope, that is a constant or an instruction/argument of Scope.
bool isPotentiallyReachable(Attributor &A, const Instruction &FromI, const Instruction &ToI, const AbstractAttribute &QueryingAA, std::function< bool(const Function &F)> GoBackwardsCB=nullptr)
Return true if ToI is potentially reachable from FromI.
bool isIntegerTy() const
True if this is an instance of IntegerType.
An efficient, type-erasing, non-owning reference to a callable.
AccessKind getKind() const
Return the access kind.
PointerTy getPointer() const
static void createShallowWrapper(Function &F)
Create a shallow wrapper for F such that F has internal linkage afterwards.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
static cl::opt< bool > PrintDependencies("attributor-print-dep", cl::Hidden, cl::desc("Print attribute dependencies"), cl::init(false))
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
static const IRPosition callsite_argument(const CallBase &CB, unsigned ArgNo)
Create a position describing the argument of CB at position ArgNo.
inst_range instructions(Function *F)
Attribute getAttributeAtIndex(unsigned i, Attribute::AttrKind Kind) const
gets the attribute from the list of attributes.
An instruction for storing to memory.
std::function< void(const ArgumentReplacementInfo &, AbstractCallSite, SmallVectorImpl< Value * > &)> ACSRepairCBTy
Abstract call site (ACS) repair callback type.
AttributeSet getRetAttrs() const
The attributes for the ret value are returned.
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
This is an important base class in LLVM.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
@ NONE
Do not track a dependence between source and target.
CallGraphUpdater & CGUpdater
Helper to update an underlying call graph and to delete functions.
APInt operator|(APInt a, const APInt &b)
Type * getReturnType() const
Returns the type of the ret val.
Base struct for all "concrete attribute" deductions.
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph.
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
Optional< Constant * > getAssumedConstant(const IRPosition &IRP, const AbstractAttribute &AA, bool &UsedAssumedInformation)
If IRP is assumed to be a constant, return it, if it is unclear yet, return None, otherwise return nu...
@ REQUIRED
The target cannot be valid if the source is not.
Module * getParent()
Get the module that this global value is contained inside of...
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void preserve()
Mark an analysis as preserved.
bool RewriteSignatures
Flag to determine if we rewrite function signatures.
Optional< Value * > getContent() const
Return the written value which can be llvm::null if it is not yet determined.
Allocate memory in an ever growing pool, as if by bump-pointer.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
This is an important class for using LLVM in a threaded context.
@ IRP_FUNCTION
An attribute for a function (scope).
Value & getAnchorValue() const
Return the value this abstract attribute is anchored with.
DEBUG_COUNTER(ManifestDBGCounter, "attributor-manifest", "Determine what attributes are manifested in the IR")
bool registerFunctionSignatureRewrite(Argument &Arg, ArrayRef< Type * > ReplacementTypes, ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB, ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB)
Register a rewrite for a function signature.
The ModulePass which wraps up a CallGraph and the logic to build it.
void fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result)
Insert into the map all the informations contained in the operand bundles of the llvm....
Attribute::AttrKind getKindAsEnum() const
Return the attribute's kind as an enum (Attribute::AttrKind).
static const Function * getCalledFunction(const Value *V, bool &IsNoBuiltin)
Value & getAssociatedValue() const
Return the value this abstract attribute is associated with.
Value * getWithType(Value &V, Type &Ty)
Try to convert V to type Ty without introducing new instructions.
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
initializer< Ty > init(const Ty &Val)
Argument * getAssociatedArgument() const
Return the associated argument, if any.
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
void setLinkage(LinkageTypes LT)
unsigned getAttrIdx() const
Return the index in the attribute list for this position.
An abstract interface for liveness abstract attribute.
iterator & begin(const Instruction *PP)
Return an iterator to explore the context around PP.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
An interface to query the internal state of an abstract attribute.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr const T & getValue() const &
StandardInstrumentations SI(Debug, VerifyEach)
bool hasLocalLinkage() const
raw_ostream & WriteGraph(raw_ostream &O, const GraphType &G, bool ShortNames=false, const Twine &Title="")
Helper to describe and deal with positions in the LLVM-IR.
print Print MemDeps of function
bool isVoidTy() const
Return true if this is 'void'.
static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, AttributeList &Attrs, int AttrIdx, bool ForceReplace=false)
Return true if the information provided by Attr was added to the attribute list Attrs.
static std::string getNodeLabel(const AADepGraphNode *Node, const AADepGraph *DG)
A Module instance is used to store all the information related to an LLVM module.
const Use & getCalleeUseForCallback() const
Return the use of the callee value in the underlying instruction.
bool checkForAllReadWriteInstructions(function_ref< bool(Instruction &)> Pred, AbstractAttribute &QueryingAA, bool &UsedAssumedInformation)
Check Pred on all Read/Write instructions.
A "must be executed context" for a given program point PP is the set of instructions,...
A node in the call graph.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
const Function & getFunction() const
bool isDroppable() const
A droppable user is a user for which uses can be dropped without affecting correctness and should be ...
bool isCallbackCall() const
Return true if this ACS represents a callback call.
bool isWrittenValueYetUndetermined() const
Return true if the value written is not known yet.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool isAssumedReadNone(Attributor &A, const IRPosition &IRP, const AbstractAttribute &QueryingAA, bool &IsKnown)
Return true if IRP is readnone.
void identifyDefaultAbstractAttributes(Function &F)
Determine opportunities to derive 'default' attributes in F and create abstract attribute objects for...
@ IRP_CALL_SITE_RETURNED
An attribute for a call site return value.
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool getPotentiallyLoadedValues(Attributor &A, LoadInst &LI, SmallSetVector< Value *, 4 > &PotentialValues, SmallSetVector< Instruction *, 4 > &PotentialValueOrigins, const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation, bool OnlyExact=false)
Collect all potential values LI could read into PotentialValues.
iterator & end()
Return an universal end iterator.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA, const Value &V, bool ForAnalysisOnly=true)
Return true if V is dynamically unique, that is, there are no two "instances" of V at runtime with di...
@ IRP_INVALID
An invalid position.
Scope
Defines the scope in which this symbol should be visible: Default – Visible in the public interface o...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
StringRef - Represent a constant reference to a string, i.e.
void populateAll() const
Force populate the entire call graph.
bool getAssumedUnderlyingObjects(Attributor &A, const Value &Ptr, SmallVectorImpl< Value * > &Objects, const AbstractAttribute &QueryingAA, const Instruction *CtxI, bool &UsedAssumedInformation, AA::ValueScope VS=Interprocedural)
Collect all potential underlying objects of Ptr at position CtxI in Objects.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)
Type * getType() const
All values are typed, get the type of this value.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
An abstract interface for struct information.
const Function * getFunction() const
Return the function this instruction belongs to.
static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP, const ArrayRef< Attribute > &DeducedAttrs, bool ForceReplace=false)
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
static cl::opt< unsigned, true > MaxInitializationChainLengthX("attributor-max-initialization-chain-length", cl::Hidden, cl::desc("Maximal number of chained initializations (to avoid stack overflows)"), cl::location(MaxInitializationChainLength), cl::init(1024))
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
static bool isEqualOrWorse(const Attribute &New, const Attribute &Old)
Return true if New is equal or worse than Old.
bool hasMetadata() const
Return true if this value has any metadata attached to it.
void updateMinLegalVectorWidthAttr(Function &Fn, uint64_t Width)
Update min-legal-vector-width if it is in Attribute and less than Width.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
static cl::opt< bool > VerifyMaxFixpointIterations("attributor-max-iterations-verify", cl::Hidden, cl::desc("Verify that max-iterations is a tight bound for a fixpoint"), cl::init(false))
const FunctionListType & getFunctionList() const
Get the Module's list of functions (constant).
static bool isInternalizable(Function &F)
Returns true if the function F can be internalized.
virtual ChangeStatus indicateOptimisticFixpoint()=0
Indicate that the abstract state should converge to the optimistic state.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
StringRef getName() const
Return a constant reference to the value's name.
An instruction for reading from memory.
A raw_ostream that writes to a file descriptor.
static Function * internalizeFunction(Function &F, bool Force=false)
Make another copy of the function F such that the copied version has internal linkage afterwards and ...
bool isWrite() const
Return true if this is a write access.
@ IRP_CALL_SITE_ARGUMENT
An attribute for a call site argument.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
const Instruction * getCtxI() const
const Instruction & front() const
LLVM_NODISCARD bool empty() const
Function * getAnchorScope() const
Return the Function surrounding the anchor value.
amdgpu Simplify well known AMD library false FunctionCallee Callee
void clear()
Completely clear the SetVector.
static bool getPotentialCopiesOfMemoryValue(Attributor &A, Ty &I, SmallSetVector< Value *, 4 > &PotentialCopies, SmallSetVector< Instruction *, 4 > &PotentialValueOrigins, const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation, bool OnlyExact)
APInt operator&(APInt a, const APInt &b)
bool isValidFunctionSignatureRewrite(Argument &Arg, ArrayRef< Type * > ReplacementTypes)
Check if we can rewrite a function signature.
bool isAssumedReadOnly(Attributor &A, const IRPosition &IRP, const AbstractAttribute &QueryingAA, bool &IsKnown)
Return true if IRP is readonly.
virtual bool isRemovableStore() const
Return true if the underlying value is a store that is known to be removable.
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
A constant value that is initialized with an expression using other constant values.
@ IRP_CALL_SITE
An attribute for a call site (function scope).
int getCallSiteArgNo() const
Return the call site argument number of the associated value if it is an argument or call site argume...
static cl::opt< bool > EnableCallSiteSpecific("attributor-enable-call-site-specific-deduction", cl::Hidden, cl::desc("Allow the Attributor to do call site specific analysis"), cl::init(false))
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
void removeAttributeAtIndex(unsigned i, Attribute::AttrKind Kind)
removes the attribute from the list of attributes.
static bool isInterposableLinkage(LinkageTypes Linkage)
Whether the definition of this global may be replaced by something non-equivalent at link time.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Argument * getArg(unsigned i) const
void replaceFunctionWith(Function &OldFn, Function &NewFn)
Replace OldFn in the call graph (and SCC) with NewFn.
bool isNoSyncInst(Attributor &A, const Instruction &I, const AbstractAttribute &QueryingAA)
Return true if I is a nosync instruction.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Provides information about what library functions are available for the current target.
The fixpoint analysis framework that orchestrates the attribute deduction.
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
Instruction * getLocalInst() const
Return the instruction that causes the access with respect to the local scope of the associated attri...
void * getOpaqueValue() const
FunctionType * getFunctionType() const
Returns the FunctionType for me.
static const IRPosition argument(const Argument &Arg, const CallBaseContext *CBContext=nullptr)
Create a position describing the argument Arg.
const T & front() const
Return the first element of the SetVector.
Attribute getAttributeAtIndex(unsigned Index, Attribute::AttrKind Kind) const
Return the attribute object that exists at the given index.
static const IRPosition callsite_function(const CallBase &CB)
Create a position describing the function scope of CB.
void print(raw_ostream &OS) const override
Helper functions, for debug purposes only.
static Constant * getFPTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static bool isSimple(Instruction *I)
Optional< Value * > combineOptionalValuesInAAValueLatice(const Optional< Value * > &A, const Optional< Value * > &B, Type *Ty)
Return the combination of A and B such that the result is a possible value of both.
TinyPtrVector< DepTy >::iterator ChildEdgeIteratorType
unsigned getAddressSpace() const
The data structure for the dependency graph.
Deduce and propagate false attributor cgscc
Analysis pass which computes a DominatorTree.
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Pass interface - Implemented by all 'passes'.
void removeFunction(Function &Fn)
Remove Fn from the call graph.
@ PrivateLinkage
Like Internal, but omit from symbol table.
PointerIntPair - This class implements a pair of a pointer and small integer.
DOTGraphTraits(bool isSimple=false)
static bool isPotentiallyReachable(Attributor &A, const Instruction &FromI, const Instruction *ToI, const Function &ToFn, const AbstractAttribute &QueryingAA, std::function< bool(const Function &F)> GoBackwardsCB)
static const IRPosition TombstoneKey
bool isKnown(base_t BitsEncoding) const
Return true if the bits set in BitsEncoding are "known bits".
virtual ChangeStatus updateImpl(Attributor &A)=0
The actual update/transfer function which has to be implemented by the derived classes.
Constant * getInitialValueForObj(Value &Obj, Type &Ty, const TargetLibraryInfo *TLI)
Return the initial value of Obj with type Ty if that is a constant.
LLVM_NODISCARD bool empty() const
const BasicBlock * getParent() const
std::string to_string(const T &Value)
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
size_t size() const
size - Get the array size.
bool isCallee(Value::const_user_iterator UI) const
Return true if UI is the use that defines the callee of this ACS.
Wrapper for FunctoinAnalysisManager.
static NodeRef DepGetVal(DepTy &DT)
bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA, bool &UsedAssumedInformation, bool CheckBBLivenessOnly=false, DepClassTy DepClass=DepClassTy::OPTIONAL)
Return true if AA (or its context instruction) is assumed dead.
virtual bool isAssumedDead() const =0
The query functions are protected such that other attributes need to go through the Attributor interf...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Optional< Value * > translateArgumentToCallSiteContent(Optional< Value * > V, CallBase &CB, const AbstractAttribute &AA, bool &UsedAssumedInformation)
Translate V from the callee context into the call site context.
Optional< Value * > getAssumedSimplified(const IRPosition &IRP, const AbstractAttribute &AA, bool &UsedAssumedInformation)
If V is assumed simplified, return it, if it is unclear yet, return None, otherwise return nullptr.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
bool isIntAttribute() const
Return true if the attribute is an integer attribute.
A visitor class for IR positions.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void registerForUpdate(AbstractAttribute &AA)
Allows a query AA to request an update if a new query was received.
PointerType * getType() const
Global values are always pointers.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
A SetVector that performs no allocations if smaller than a certain size.
const T & back() const
Return the last element of the SetVector.
Kind
The positions we distinguish in the IR.
A container for analyses that lazily runs them and caches their results.
std::function< void(const ArgumentReplacementInfo &, Function &, Function::arg_iterator)> CalleeRepairCBTy
Callee repair callback type.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
This class represents a function call, abstracting a target machine's calling convention.
void initializeAttributorCGSCCLegacyPassPass(PassRegistry &)
void CloneFunctionInto(Function *NewFunc, const Function *OldFunc, ValueToValueMapTy &VMap, CloneFunctionChangeType Changes, SmallVectorImpl< ReturnInst * > &Returns, const char *NameSuffix="", ClonedCodeInfo *CodeInfo=nullptr, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Clone OldFunc into NewFunc, transforming the old arguments into references to VMap values.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
An abstract interface to track if a value leaves it's defining function instance.
static cl::list< std::string > SeedAllowList("attributor-seed-allow-list", cl::Hidden, cl::desc("Comma seperated list of attribute names that are " "allowed to be seeded."), cl::CommaSeparated)
AnalysisUsage & addRequired()
static cl::opt< bool > ViewDepGraph("attributor-view-dep-graph", cl::Hidden, cl::desc("View the dependency graph."), cl::init(false))
void takeName(Value *V)
Transfer the name from V to this value.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
bool isAssumedUniqueForAnalysis() const
Return true if we assume that the underlying value is unique in its scope wrt.
bool checkForAllReturnedValuesAndReturnInsts(function_ref< bool(Value &, const SmallSetVector< ReturnInst *, 4 > &)> Pred, const AbstractAttribute &QueryingAA)
Check Pred on all values potentially returned by F.
A lazily constructed view of the call graph of a module.
const IRPosition & getIRPosition() const
Return an IR position, see struct IRPosition.
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
Function * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it's an indirect...
void initialize(CallGraph &CG, CallGraphSCC &SCC)
Initializers for usage outside of a CGSCC pass, inside a CGSCC pass in the old and new pass manager (...
void reanalyzeFunction(Function &Fn)
After an CGSCC pass changes a function in ways that affect the call graph, this method can be called ...
A vector that has set insertion semantics.
AttributeSet getParamAttrs(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
void reserve(size_type N)
static const IRPosition callsite_returned(const CallBase &CB)
Create a position describing the returned value of CB.
A proxy from a FunctionAnalysisManager to an SCC.
Value * getCallArgOperand(Argument &Arg) const
Return the operand of the underlying instruction associated with Arg.
bool isModulePass() const
Return true if this is a module pass, false otherwise.
void setAttributes(AttributeList Attrs)
Set the attribute list for this Function.
void setVisibility(VisibilityTypes V)
Optional< unsigned > MaxFixpointIterations
Maximum number of iterations to run until fixpoint.
constexpr T value_or(U &&alt) const &
bool isRead() const
Return true if this is a read access.
Type * getReturnType() const
LLVM Value Representation.
iterator_range< user_iterator > users()
static bool isAssumedReadOnlyOrReadNone(Attributor &A, const IRPosition &IRP, const AbstractAttribute &QueryingAA, bool RequireReadNone, bool &IsKnown)
static bool runAttributorOnFunctions(InformationCache &InfoCache, SetVector< Function * > &Functions, AnalysisGetter &AG, CallGraphUpdater &CGUpdater, bool DeleteFns, bool IsModulePass)
}
int getCallArgOperandNo(Argument &Arg) const
Return the operand index of the underlying instruction associated with Arg.
static const IRPosition returned(const Function &F, const CallBaseContext *CBContext=nullptr)
Create a position describing the returned value of F.
static cl::opt< bool > SimplifyAllLoads("attributor-simplify-all-loads", cl::Hidden, cl::desc("Try to simplify all loads."), cl::init(true))
void setCallingConv(CallingConv::ID CC)
Class to represent function types.
A Use represents the edge between a Value definition and its users.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static bool internalizeFunctions(SmallPtrSetImpl< Function * > &FnSet, DenseMap< Function *, Function * > &FnMap)
Make copies of each function in the set FnSet such that the copied version has internal linkage after...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
static cl::opt< unsigned > SetFixpointIterations("attributor-max-iterations", cl::Hidden, cl::desc("Maximal number of fixpoint iterations."), cl::init(32))
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.