79#define DEBUG_TYPE "rewrite-statepoints-for-gc"
99#ifdef EXPENSIVE_CHECKS
136 bool Changed =
false;
140 if (
F.isDeclaration() ||
F.empty())
169class RewriteStatepointsForGCLegacyPass :
public ModulePass {
175 RewriteStatepointsForGCLegacyPass() :
ModulePass(
ID), Impl() {
180 bool runOnModule(
Module &M)
override {
181 bool Changed =
false;
184 if (
F.isDeclaration() ||
F.empty())
193 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
195 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
196 auto &DT = getAnalysis<DominatorTreeWrapperPass>(
F).getDomTree();
222char RewriteStatepointsForGCLegacyPass::ID = 0;
225 return new RewriteStatepointsForGCLegacyPass();
229 "rewrite-statepoints-for-gc",
230 "Make relocations explicit at statepoints",
false,
false)
304 std::optional<OperandBundleUse> DeoptBundle =
309 "Found non-leaf call without deopt info!");
313 return DeoptBundle->Inputs;
326 assert(GC &&
"GC Strategy for isGCPointerType cannot be null");
328 if (!isa<PointerType>(
T))
332 return GC->isGCManagedPointer(
T).value_or(
true);
345 if (
auto VT = dyn_cast<VectorType>(
T))
357 if (
VectorType *VT = dyn_cast<VectorType>(Ty))
359 if (
ArrayType *AT = dyn_cast<ArrayType>(Ty))
361 if (
StructType *ST = dyn_cast<StructType>(Ty))
363 [GC](
Type *Ty) { return containsGCPtrType(Ty, GC); });
379 return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.
str();
388 PartiallyConstructedSafepointRecord &Result,
GCStrategy *GC) {
389 StatepointLiveSetTy LiveSet;
393 dbgs() <<
"Live Variables:\n";
394 for (
Value *V : LiveSet)
395 dbgs() <<
" " << V->getName() <<
" " << *V <<
"\n";
398 dbgs() <<
"Safepoint For: " << Call->getCalledOperand()->getName() <<
"\n";
399 dbgs() <<
"Number live values: " << LiveSet.size() <<
"\n";
401 Result.LiveSet = LiveSet;
410 IsKnownBaseMapTy &KnownBases);
413 IsKnownBaseMapTy &KnownBases);
425 IsKnownBaseMapTy &KnownBases) {
429 auto Cached = Cache.find(
I);
430 if (Cached != Cache.end())
431 return Cached->second;
433 if (isa<Argument>(
I)) {
440 if (isa<Constant>(
I)) {
449 if (isa<LoadInst>(
I)) {
455 if (isa<InsertElementInst>(
I)) {
464 if (isa<ShuffleVectorInst>(
I)) {
477 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I)) {
486 if (
auto *Freeze = dyn_cast<FreezeInst>(
I)) {
494 if (
auto *BC = dyn_cast<BitCastInst>(
I)) {
503 if (isa<CallInst>(
I) || isa<InvokeInst>(
I)) {
511 assert((isa<SelectInst>(
I) || isa<PHINode>(
I)) &&
512 "unknown vector instruction - no base found for vector element");
523 IsKnownBaseMapTy &KnownBases) {
524 assert(
I->getType()->isPtrOrPtrVectorTy() &&
525 "Illegal to ask for the base pointer of a non-pointer type");
526 auto Cached = Cache.find(
I);
527 if (Cached != Cache.end())
528 return Cached->second;
530 if (
I->getType()->isVectorTy())
533 if (isa<Argument>(
I)) {
541 if (isa<Constant>(
I)) {
563 if (isa<IntToPtrInst>(
I)) {
569 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
570 Value *Def = CI->stripPointerCasts();
573 assert(cast<PointerType>(Def->getType())->getAddressSpace() ==
574 cast<PointerType>(CI->getType())->getAddressSpace() &&
575 "unsupported addrspacecast");
579 assert(!isa<CastInst>(Def) &&
"shouldn't find another cast here");
585 if (isa<LoadInst>(
I)) {
600 if (
auto *Freeze = dyn_cast<FreezeInst>(
I)) {
607 switch (II->getIntrinsicID()) {
611 case Intrinsic::experimental_gc_statepoint:
613 case Intrinsic::experimental_gc_relocate:
618 case Intrinsic::gcroot:
623 "interaction with the gcroot mechanism is not supported");
624 case Intrinsic::experimental_gc_get_pointer_base:
633 if (isa<CallInst>(
I) || isa<InvokeInst>(
I)) {
641 assert(!isa<LandingPadInst>(
I) &&
"Landing Pad is unimplemented");
643 if (isa<AtomicCmpXchgInst>(
I)) {
652 assert(!isa<AtomicRMWInst>(
I) &&
"Xchg handled above, all others are "
653 "binary ops which don't apply to pointers");
658 if (isa<ExtractValueInst>(
I)) {
666 assert(!isa<InsertValueInst>(
I) &&
667 "Base pointer for a struct is meaningless");
672 isa<Instruction>(
I) && cast<Instruction>(
I)->getMetadata(
"is_base_value");
680 if (isa<ExtractElementInst>(
I))
690 assert((isa<SelectInst>(
I) || isa<PHINode>(
I)) &&
691 "missing instruction case in findBaseDefiningValue");
697 IsKnownBaseMapTy &KnownBases) {
698 if (!Cache.contains(
I)) {
702 << Cache[
I]->getName() <<
", is known base = "
703 << KnownBases[
I] <<
"\n");
706 assert(KnownBases.contains(Cache[
I]) &&
707 "Cached value must be present in known bases map");
714 IsKnownBaseMapTy &KnownBases) {
716 auto Found = Cache.find(Def);
717 if (Found != Cache.end()) {
719 return Found->second;
730 return !isa<PHINode>(V) && !isa<SelectInst>(V) &&
731 !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&
732 !isa<ShuffleVectorInst>(V);
737 auto It = KnownBases.find(V);
738 assert(It != KnownBases.end() &&
"Value not present in the map");
743 IsKnownBaseMapTy &KnownBases) {
745 auto It = KnownBases.find(V);
746 if (It != KnownBases.end())
747 assert(It->second == IsKnownBase &&
"Changing already present value");
749 KnownBases[V] = IsKnownBase;
754 return isa<VectorType>(First->getType()) ==
755 isa<VectorType>(Second->
getType());
780 explicit BDVState(
Value *OriginalValue)
781 : OriginalValue(OriginalValue) {}
782 explicit BDVState(
Value *OriginalValue, StatusTy
Status,
Value *BaseValue =
nullptr)
783 : OriginalValue(OriginalValue),
Status(
Status), BaseValue(BaseValue) {
787 StatusTy getStatus()
const {
return Status; }
788 Value *getOriginalValue()
const {
return OriginalValue; }
789 Value *getBaseValue()
const {
return BaseValue; }
791 bool isBase()
const {
return getStatus() ==
Base; }
792 bool isUnknown()
const {
return getStatus() ==
Unknown; }
793 bool isConflict()
const {
return getStatus() == Conflict; }
798 void meet(
const BDVState &
Other) {
799 auto markConflict = [&]() {
800 Status = BDVState::Conflict;
809 BaseValue =
Other.getBaseValue();
813 assert(isBase() &&
"Unknown state");
815 if (
Other.isUnknown())
818 if (
Other.isConflict())
819 return markConflict();
823 if (getBaseValue() !=
Other.getBaseValue())
824 return markConflict();
829 return OriginalValue ==
Other.OriginalValue && BaseValue ==
Other.BaseValue &&
833 bool operator!=(
const BDVState &other)
const {
return !(*
this == other); }
842 switch (getStatus()) {
853 OS <<
" (base " << getBaseValue() <<
" - "
854 << (getBaseValue() ? getBaseValue()->getName() :
"nullptr") <<
")"
855 <<
" for " << OriginalValue->getName() <<
":";
878 IsKnownBaseMapTy &KnownBases) {
907 auto isExpectedBDVType = [](
Value *BDV) {
908 return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||
909 isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||
910 isa<ShuffleVectorInst>(BDV);
922 auto VerifyStates = [&]() {
923 for (
auto &Entry : States) {
924 assert(Entry.first == Entry.second.getOriginalValue());
929 auto visitBDVOperands = [](
Value *BDV, std::function<void (
Value*)>
F) {
930 if (
PHINode *PN = dyn_cast<PHINode>(BDV)) {
931 for (
Value *InVal : PN->incoming_values())
933 }
else if (
SelectInst *
SI = dyn_cast<SelectInst>(BDV)) {
934 F(
SI->getTrueValue());
935 F(
SI->getFalseValue());
936 }
else if (
auto *EE = dyn_cast<ExtractElementInst>(BDV)) {
937 F(EE->getVectorOperand());
938 }
else if (
auto *IE = dyn_cast<InsertElementInst>(BDV)) {
939 F(IE->getOperand(0));
940 F(IE->getOperand(1));
941 }
else if (
auto *SV = dyn_cast<ShuffleVectorInst>(BDV)) {
944 F(SV->getOperand(0));
945 if (!SV->isZeroEltSplat())
946 F(SV->getOperand(1));
958 States.
insert({Def, BDVState(Def)});
959 while (!Worklist.
empty()) {
963 auto visitIncomingValue = [&](
Value *InVal) {
972 assert(isExpectedBDVType(
Base) &&
"the only non-base values "
973 "we see should be base defining values");
978 visitBDVOperands(Current, visitIncomingValue);
985 for (
const auto &Pair : States) {
986 LLVM_DEBUG(
dbgs() <<
" " << Pair.second <<
" for " << *Pair.first <<
"\n");
998 for (
auto Pair : States) {
999 Value *BDV = Pair.first;
1000 auto canPruneInput = [&](
Value *V) {
1003 if (V->stripPointerCasts() == BDV)
1006 if (V->stripPointerCasts() != VBDV)
1010 return States.count(VBDV) == 0;
1013 bool CanPrune =
true;
1014 visitBDVOperands(BDV, [&](
Value *Op) {
1015 CanPrune = CanPrune && canPruneInput(Op);
1028 if (!States.
count(Def))
1033 auto GetStateForBDV = [&](
Value *BaseValue,
Value *Input) {
1034 auto I = States.
find(BaseValue);
1035 if (
I != States.
end())
1038 return BDVState(BaseValue, BDVState::Base, BaseValue);
1041 bool Progress =
true;
1044 const size_t OldSize = States.
size();
1051 for (
auto Pair : States) {
1052 Value *BDV = Pair.first;
1058 "why did it get added?");
1060 BDVState NewState(BDV);
1061 visitBDVOperands(BDV, [&](
Value *Op) {
1063 auto OpState = GetStateForBDV(BDV, Op);
1064 NewState.meet(OpState);
1067 BDVState OldState = States[BDV];
1068 if (OldState != NewState) {
1070 States[BDV] = NewState;
1074 assert(OldSize == States.size() &&
1075 "fixed point shouldn't be adding any new nodes to state");
1081 for (
const auto &Pair : States) {
1082 LLVM_DEBUG(
dbgs() <<
" " << Pair.second <<
" for " << *Pair.first <<
"\n");
1088 for (
auto Pair : States) {
1090 BDVState State = Pair.second;
1091 auto *BaseValue = State.getBaseValue();
1097 "why did it get added?");
1098 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1100 if (!State.isBase() || !isa<VectorType>(BaseValue->
getType()))
1106 if (isa<ExtractElementInst>(
I)) {
1107 auto *EE = cast<ExtractElementInst>(
I);
1112 State.getBaseValue(), EE->getIndexOperand(),
"base_ee", EE);
1113 BaseInst->setMetadata(
"is_base_value",
MDNode::get(
I->getContext(), {}));
1114 States[
I] = BDVState(
I, BDVState::Base, BaseInst);
1116 }
else if (!isa<VectorType>(
I->getType())) {
1122 States[
I] = BDVState(
I, BDVState::Conflict);
1132 for (
auto Pair : States) {
1134 BDVState State = Pair.second;
1140 "why did it get added?");
1141 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1146 assert(!isa<InsertElementInst>(
I) || State.isConflict());
1148 if (!State.isConflict())
1151 auto getMangledName = [](
Instruction *
I) -> std::string {
1152 if (isa<PHINode>(
I)) {
1154 }
else if (isa<SelectInst>(
I)) {
1156 }
else if (isa<ExtractElementInst>(
I)) {
1158 }
else if (isa<InsertElementInst>(
I)) {
1167 BaseInst->
setName(getMangledName(
I));
1170 States[
I] = BDVState(
I, BDVState::Conflict, BaseInst);
1189 if (!States.
count(BDV)) {
1195 Base = States[BDV].getBaseValue();
1199 if (
Base->getType() != Input->
getType() && InsertPt)
1207 for (
auto Pair : States) {
1209 BDVState State = Pair.second;
1216 "why did it get added?");
1217 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1218 if (!State.isConflict())
1221 if (
PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {
1222 PHINode *PN = cast<PHINode>(BDV);
1230 for (
unsigned i = 0; i < NumPHIValues; i++) {
1233 if (!BlockToValue.
count(InBB))
1234 BlockToValue[InBB] = getBaseForInput(InVal, InBB->
getTerminator());
1237 Value *OldBase = BlockToValue[InBB];
1238 Value *
Base = getBaseForInput(InVal,
nullptr);
1242 auto StripBitCasts = [](
Value *V) ->
Value * {
1243 while (
auto *BC = dyn_cast<BitCastInst>(V))
1244 V = BC->getOperand(0);
1253 assert(StripBitCasts(
Base) == StripBitCasts(OldBase) &&
1254 "findBaseOrBDV should be pure!");
1258 BasePHI->setIncomingValue(i,
Base);
1261 dyn_cast<SelectInst>(State.getBaseValue())) {
1266 BaseSI->setTrueValue(getBaseForInput(
SI->getTrueValue(), BaseSI));
1267 BaseSI->setFalseValue(getBaseForInput(
SI->getFalseValue(), BaseSI));
1268 }
else if (
auto *BaseEE =
1269 dyn_cast<ExtractElementInst>(State.getBaseValue())) {
1270 Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();
1273 BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));
1274 }
else if (
auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){
1275 auto *BdvIE = cast<InsertElementInst>(BDV);
1276 auto UpdateOperand = [&](
int OperandIdx) {
1277 Value *InVal = BdvIE->getOperand(OperandIdx);
1278 Value *
Base = getBaseForInput(InVal, BaseIE);
1279 BaseIE->setOperand(OperandIdx,
Base);
1284 auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());
1285 auto *BdvSV = cast<ShuffleVectorInst>(BDV);
1286 auto UpdateOperand = [&](
int OperandIdx) {
1287 Value *InVal = BdvSV->getOperand(OperandIdx);
1288 Value *
Base = getBaseForInput(InVal, BaseSV);
1289 BaseSV->setOperand(OperandIdx,
Base);
1292 if (!BdvSV->isZeroEltSplat())
1296 Value *InVal = BdvSV->getOperand(1);
1309 for (
auto Pair : States) {
1310 auto *BDV = Pair.first;
1311 Value *
Base = Pair.second.getBaseValue();
1318 "why did it get added?");
1321 dbgs() <<
"Updating base value cache"
1322 <<
" for: " << BDV->
getName() <<
" from: "
1323 << (Cache.count(BDV) ? Cache[BDV]->getName().str() :
"none")
1324 <<
" to: " <<
Base->getName() <<
"\n");
1328 assert(Cache.count(Def));
1349 DefiningValueMapTy &DVCache,
1350 IsKnownBaseMapTy &KnownBases) {
1353 assert(base &&
"failed to find base pointer");
1354 PointerToBase[ptr] = base;
1355 assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||
1356 DT->
dominates(cast<Instruction>(base)->getParent(),
1357 cast<Instruction>(ptr)->getParent())) &&
1358 "The base we found better dominate the derived pointer");
1366 PartiallyConstructedSafepointRecord &result,
1367 PointerToBaseTy &PointerToBase,
1368 IsKnownBaseMapTy &KnownBases) {
1369 StatepointLiveSetTy PotentiallyDerivedPointers = result.LiveSet;
1376 for (
Value *V : Opt->Inputs) {
1377 if (!PotentiallyDerivedPointers.count(V))
1379 PotentiallyDerivedPointers.
remove(V);
1380 PointerToBase[V] = V;
1390 PartiallyConstructedSafepointRecord &result,
1391 PointerToBaseTy &PointerToBase,
1397 PointerToBaseTy &PointerToBase,
GCStrategy *GC) {
1400 GCPtrLivenessData RevisedLivenessData;
1402 for (
size_t i = 0; i < records.
size(); i++) {
1403 struct PartiallyConstructedSafepointRecord &
info = records[i];
1415 Value *AlternateLiveBase) {
1425 assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
1429 ClonedValue->
setName(Instr->getName() +
".remat");
1433 if (LastClonedValue) {
1441 "incorrect use in rematerialization chain");
1444 assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);
1453 if (RootOfChain != AlternateLiveBase)
1457 LastClonedValue = ClonedValue;
1461 return LastClonedValue;
1480 assert(!isa<PHINode>(Ret->begin()) &&
1481 "All PHI nodes should have been removed!");
1494 {Attribute::Memory, Attribute::NoSync, Attribute::NoFree};
1502 return StatepointAL;
1535 assert(ValIt != LiveVec.
end() &&
"Val not found in LiveVec!");
1536 size_t Index = std::distance(LiveVec.
begin(), ValIt);
1549 auto getGCRelocateDecl = [&](
Type *Ty) {
1551 auto AS = Ty->getScalarType()->getPointerAddressSpace();
1553 if (
auto *VT = dyn_cast<VectorType>(Ty))
1555 cast<FixedVectorType>(VT)->getNumElements());
1571 if (!TypeToDeclMap.
count(Ty))
1572 TypeToDeclMap[Ty] = getGCRelocateDecl(Ty);
1573 Function *GCRelocateDecl = TypeToDeclMap[Ty];
1577 GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
1589class DeferredReplacement {
1592 bool IsDeoptimize =
false;
1594 DeferredReplacement() =
default;
1598 assert(Old != New && Old && New &&
1599 "Cannot RAUW equal values or to / from null!");
1601 DeferredReplacement
D;
1607 static DeferredReplacement createDelete(
Instruction *ToErase) {
1608 DeferredReplacement
D;
1613 static DeferredReplacement createDeoptimizeReplacement(
Instruction *Old) {
1615 auto *
F = cast<CallInst>(Old)->getCalledFunction();
1616 assert(
F &&
F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&
1617 "Only way to construct a deoptimize deferred replacement");
1619 DeferredReplacement
D;
1621 D.IsDeoptimize =
true;
1626 void doReplacement() {
1630 assert(OldI != NewI &&
"Disallowed at construction?!");
1631 assert((!IsDeoptimize || !New) &&
1632 "Deoptimize intrinsics are not replaced!");
1645 RI->eraseFromParent();
1655 const char *DeoptLowering =
"deopt-lowering";
1656 if (Call->hasFnAttr(DeoptLowering)) {
1662 Function *
F = Call->getCalledFunction();
1663 assert(
F &&
F->hasFnAttribute(DeoptLowering));
1664 return F->getFnAttribute(DeoptLowering).getValueAsString();
1666 return "live-through";
1673 PartiallyConstructedSafepointRecord &Result,
1674 std::vector<DeferredReplacement> &Replacements,
1675 const PointerToBaseTy &PointerToBase,
1691 std::optional<ArrayRef<Use>> DeoptArgs;
1693 DeoptArgs = Bundle->Inputs;
1694 std::optional<ArrayRef<Use>> TransitionArgs;
1696 TransitionArgs = Bundle->Inputs;
1704 bool IsDeoptimize =
false;
1715 if (DeoptLowering.
equals(
"live-in"))
1718 assert(DeoptLowering.
equals(
"live-through") &&
"Unsupported value!");
1721 FunctionCallee CallTarget(Call->getFunctionType(), Call->getCalledOperand());
1723 auto IID =
F->getIntrinsicID();
1724 if (IID == Intrinsic::experimental_deoptimize) {
1739 CallTarget =
F->getParent()
1740 ->getOrInsertFunction(
"__llvm_deoptimize", FTy);
1742 IsDeoptimize =
true;
1743 }
else if (IID == Intrinsic::memcpy_element_unordered_atomic ||
1744 IID == Intrinsic::memmove_element_unordered_atomic) {
1761 auto &
Context = Call->getContext();
1762 auto &
DL = Call->getModule()->getDataLayout();
1763 auto GetBaseAndOffset = [&](
Value *Derived) {
1769 if (isa<Constant>(Derived))
1773 assert(PointerToBase.count(Derived));
1774 Base = PointerToBase.find(Derived)->second;
1776 unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
1782 return std::make_pair(
Base,
Builder.CreateSub(Derived_int, Base_int));
1785 auto *Dest = CallArgs[0];
1786 Value *DestBase, *DestOffset;
1787 std::tie(DestBase, DestOffset) = GetBaseAndOffset(Dest);
1789 auto *Source = CallArgs[1];
1790 Value *SourceBase, *SourceOffset;
1791 std::tie(SourceBase, SourceOffset) = GetBaseAndOffset(Source);
1793 auto *LengthInBytes = CallArgs[2];
1794 auto *ElementSizeCI = cast<ConstantInt>(CallArgs[3]);
1810 uint64_t ElementSize = ElementSizeCI->getZExtValue();
1811 if (IID == Intrinsic::memcpy_element_unordered_atomic) {
1812 switch (ElementSize) {
1814 return "__llvm_memcpy_element_unordered_atomic_safepoint_1";
1816 return "__llvm_memcpy_element_unordered_atomic_safepoint_2";
1818 return "__llvm_memcpy_element_unordered_atomic_safepoint_4";
1820 return "__llvm_memcpy_element_unordered_atomic_safepoint_8";
1822 return "__llvm_memcpy_element_unordered_atomic_safepoint_16";
1827 assert(IID == Intrinsic::memmove_element_unordered_atomic);
1828 switch (ElementSize) {
1830 return "__llvm_memmove_element_unordered_atomic_safepoint_1";
1832 return "__llvm_memmove_element_unordered_atomic_safepoint_2";
1834 return "__llvm_memmove_element_unordered_atomic_safepoint_4";
1836 return "__llvm_memmove_element_unordered_atomic_safepoint_8";
1838 return "__llvm_memmove_element_unordered_atomic_safepoint_16";
1846 ->getOrInsertFunction(GetFunctionName(IID, ElementSizeCI), FTy);
1852 if (
auto *CI = dyn_cast<CallInst>(Call)) {
1854 StatepointID, NumPatchBytes, CallTarget,
Flags, CallArgs,
1855 TransitionArgs, DeoptArgs, GCArgs,
"safepoint_token");
1865 CI->getContext(), CI->getAttributes(), SPCall->
getAttributes()));
1867 Token = cast<GCStatepointInst>(SPCall);
1871 assert(CI->getNextNode() &&
"Not a terminator, must have next!");
1872 Builder.SetInsertPoint(CI->getNextNode());
1873 Builder.SetCurrentDebugLocation(CI->getNextNode()->getDebugLoc());
1875 auto *II = cast<InvokeInst>(Call);
1881 StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(),
1882 II->getUnwindDest(),
Flags, CallArgs, TransitionArgs, DeoptArgs, GCArgs,
1883 "statepoint_token");
1892 II->getContext(), II->getAttributes(), SPInvoke->
getAttributes()));
1894 Token = cast<GCStatepointInst>(SPInvoke);
1897 BasicBlock *UnwindBlock = II->getUnwindDest();
1900 "can't safely insert in this block!");
1903 Builder.SetCurrentDebugLocation(II->getDebugLoc());
1907 Result.UnwindToken = ExceptionalToken;
1912 BasicBlock *NormalDest = II->getNormalDest();
1915 "can't safely insert in this block!");
1922 assert(Token &&
"Should be set in one of the above branches!");
1928 Replacements.push_back(
1929 DeferredReplacement::createDeoptimizeReplacement(Call));
1931 Token->
setName(
"statepoint_token");
1932 if (!Call->getType()->isVoidTy() && !Call->use_empty()) {
1937 Call->getAttributes().getRetAttrs()));
1945 Replacements.emplace_back(
1946 DeferredReplacement::createRAUW(Call, GCResult));
1948 Replacements.emplace_back(DeferredReplacement::createDelete(Call));
1952 Result.StatepointToken = Token;
1965 PartiallyConstructedSafepointRecord &Result,
1966 std::vector<DeferredReplacement> &Replacements,
1967 const PointerToBaseTy &PointerToBase,
GCStrategy *GC) {
1968 const auto &LiveSet = Result.LiveSet;
1972 LiveVec.
reserve(LiveSet.size());
1973 BaseVec.
reserve(LiveSet.size());
1974 for (
Value *L : LiveSet) {
1976 assert(PointerToBase.count(L));
1977 Value *
Base = PointerToBase.find(L)->second;
1997 for (
User *U : GCRelocs) {
2004 Value *Alloca = AllocaMap[OriginalValue];
2010 "Should always have one since it's not a terminator");
2012 Value *CastedRelocatedValue =
2013 Builder.CreateBitCast(Relocate,
2014 cast<AllocaInst>(Alloca)->getAllocatedType(),
2017 new StoreInst(CastedRelocatedValue, Alloca,
2018 cast<Instruction>(CastedRelocatedValue)->getNextNode());
2021 VisitedLiveValues.
insert(OriginalValue);
2029 const RematerializedValueMapTy &RematerializedValues,
2032 for (
auto RematerializedValuePair: RematerializedValues) {
2033 Instruction *RematerializedValue = RematerializedValuePair.first;
2034 Value *OriginalValue = RematerializedValuePair.second;
2037 "Can not find alloca for rematerialized value");
2038 Value *Alloca = AllocaMap[OriginalValue];
2040 new StoreInst(RematerializedValue, Alloca,
2044 VisitedLiveValues.
insert(OriginalValue);
2056 int InitialAllocaNum = 0;
2058 if (isa<AllocaInst>(
I))
2066 std::size_t NumRematerializedValues = 0;
2072 auto emitAllocaFor = [&](
Value *LiveValue) {
2074 DL.getAllocaAddrSpace(),
"",
2075 F.getEntryBlock().getFirstNonPHI());
2076 AllocaMap[LiveValue] = Alloca;
2085 for (
const auto &
Info : Records)
2086 for (
auto RematerializedValuePair :
Info.RematerializedValues) {
2087 Value *OriginalValue = RematerializedValuePair.second;
2088 if (AllocaMap.
count(OriginalValue) != 0)
2091 emitAllocaFor(OriginalValue);
2092 ++NumRematerializedValues;
2104 for (
const auto &
Info : Records) {
2105 Value *Statepoint =
Info.StatepointToken;
2115 if (isa<InvokeInst>(Statepoint)) {
2131 for (
auto Pair : AllocaMap) {
2132 Value *Def = Pair.first;
2136 if (VisitedLiveValues.
count(Def)) {
2143 for (
auto *AI : ToClobber) {
2144 auto AT = AI->getAllocatedType();
2146 if (AT->isVectorTy())
2156 if (
auto II = dyn_cast<InvokeInst>(Statepoint)) {
2157 InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt());
2158 InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt());
2160 InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode());
2166 for (
auto Pair : AllocaMap) {
2167 Value *Def = Pair.first;
2175 Uses.reserve(Def->getNumUses());
2176 for (
User *U : Def->users()) {
2177 if (!isa<ConstantExpr>(U)) {
2183 Uses.push_back(cast<Instruction>(U));
2192 if (isa<PHINode>(
Use)) {
2205 Use->replaceUsesOfWith(Def, Load);
2213 DL.getABITypeAlign(Def->getType()));
2214 if (
Instruction *Inst = dyn_cast<Instruction>(Def)) {
2215 if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {
2218 BasicBlock *NormalDest = Invoke->getNormalDest();
2221 assert(!Inst->isTerminator() &&
2222 "The only terminator that can produce a value is "
2223 "InvokeInst which is handled above.");
2224 Store->insertAfter(Inst);
2227 assert(isa<Argument>(Def));
2228 Store->insertAfter(cast<Instruction>(Alloca));
2232 assert(PromotableAllocas.
size() ==
Live.size() + NumRematerializedValues &&
2233 "we must have the same allocas with lives");
2234 (void) NumRematerializedValues;
2235 if (!PromotableAllocas.
empty()) {
2241 for (
auto &
I :
F.getEntryBlock())
2242 if (isa<AllocaInst>(
I))
2244 assert(InitialAllocaNum == 0 &&
"We must not introduce any extra allocas");
2264 Module *M = Call->getModule();
2268 if (isa<CallInst>(Call)) {
2276 auto *II = cast<InvokeInst>(Call);
2278 Func, Values,
"", &*II->getNormalDest()->getFirstInsertionPt()));
2280 Func, Values,
"", &*II->getUnwindDest()->getFirstInsertionPt()));
2287 GCPtrLivenessData OriginalLivenessData;
2289 for (
size_t i = 0; i < records.
size(); i++) {
2290 struct PartiallyConstructedSafepointRecord &
info = records[i];
2303 Value *CurrentValue) {
2307 GEP->getPointerOperand());
2310 if (
CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
2311 if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
2321 return CurrentValue;
2332 if (
CastInst *CI = dyn_cast<CastInst>(Instr)) {
2333 assert(CI->isNoopCast(CI->getModule()->getDataLayout()) &&
2334 "non noop cast is found during rematerialization");
2336 Type *SrcTy = CI->getOperand(0)->getType();
2343 Type *ValTy =
GEP->getSourceElementType();
2349 if (!
GEP->hasAllConstantIndices())
2368 for (
unsigned i = 0; i < PhiNum; i++)
2374 for (
unsigned i = 0; i < PhiNum; i++) {
2377 if (CIVI == CurrentIncomingValues.
end())
2379 BasicBlock *CurrentIncomingBB = CIVI->second;
2390 RematCandTy &RematerizationCandidates,
2392 const unsigned int ChainLengthThreshold = 10;
2394 for (
auto P2B : PointerToBase) {
2395 auto *Derived = P2B.first;
2396 auto *
Base = P2B.second;
2398 if (Derived ==
Base)
2403 Value *RootOfChain =
2407 if ( ChainToBase.
size() == 0 ||
2408 ChainToBase.
size() > ChainLengthThreshold)
2413 if (RootOfChain != PointerToBase[Derived]) {
2414 PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
2415 PHINode *AlternateRootPhi = dyn_cast<PHINode>(PointerToBase[Derived]);
2416 if (!OrigRootPhi || !AlternateRootPhi)
2438 RematerizlizationCandidateRecord
Record;
2439 Record.ChainToBase = ChainToBase;
2440 Record.RootOfChain = RootOfChain;
2442 RematerizationCandidates.insert({ Derived,
Record });
2451 RematCandTy &RematerizationCandidates,
2453 PointerToBaseTy &PointerToBase) {
2460 <<
"Num statepoints: " << Records.
size() <<
'\n');
2462 for (
auto &It : RematerizationCandidates) {
2464 auto &
Record = It.second;
2474 if (U->getParent() == Cand->
getParent())
2479 [](
const auto *U) { return isa<PHINode>(U); }))
2491 Records, [Cand](
const auto &R) {
return R.LiveSet.contains(Cand); });
2494 LLVM_DEBUG(
dbgs() <<
"Num uses: " << NumUses <<
" Num live statepoints: "
2495 << NumLiveStatepoints <<
" ");
2497 if (NumLiveStatepoints < NumUses) {
2505 if (NumLiveStatepoints == NumUses &&
Record.Cost > 0) {
2517 if (
Record.ChainToBase.size() > 1) {
2518 Record.ChainToBase.clear();
2534 Record.ChainToBase, UserI,
Record.RootOfChain, PointerToBase[Cand]);
2536 PointerToBase[RematChain] = PointerToBase[Cand];
2542 <<
" derived pointers\n");
2543 for (
auto *Cand : LiveValuesToBeDeleted) {
2544 assert(Cand->use_empty() &&
"Unexpected user remain");
2545 RematerizationCandidates.erase(Cand);
2546 for (
auto &R : Records) {
2547 assert(!R.LiveSet.contains(Cand) ||
2548 R.LiveSet.contains(PointerToBase[Cand]));
2549 R.LiveSet.remove(Cand);
2555 if (!LiveValuesToBeDeleted.
empty()) {
2556 for (
auto &
P : RematerizationCandidates) {
2558 if (R.ChainToBase.size() > 1) {
2559 R.ChainToBase.clear();
2571 PartiallyConstructedSafepointRecord &
Info,
2572 PointerToBaseTy &PointerToBase,
2573 RematCandTy &RematerizationCandidates,
2580 auto It = RematerizationCandidates.find(LiveValue);
2581 if (It == RematerizationCandidates.end())
2584 RematerizlizationCandidateRecord &
Record = It->second;
2589 if (isa<InvokeInst>(Call))
2597 LiveValuesToBeDeleted.
push_back(LiveValue);
2603 if (isa<CallInst>(Call)) {
2608 Record.RootOfChain, PointerToBase[LiveValue]);
2609 Info.RematerializedValues[RematerializedValue] = LiveValue;
2611 auto *Invoke = cast<InvokeInst>(Call);
2614 &*Invoke->getNormalDest()->getFirstInsertionPt();
2616 &*Invoke->getUnwindDest()->getFirstInsertionPt();
2620 Record.RootOfChain, PointerToBase[LiveValue]);
2623 Record.RootOfChain, PointerToBase[LiveValue]);
2625 Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
2626 Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
2631 for (
auto *LiveValue: LiveValuesToBeDeleted) {
2632 Info.LiveSet.remove(LiveValue);
2638 DefiningValueMapTy &DVCache,
2639 IsKnownBaseMapTy &KnownBases) {
2641 auto &
DL =
F.getParent()->getDataLayout();
2642 bool Changed =
false;
2644 for (
auto *Callsite : Intrinsics)
2645 switch (Callsite->getIntrinsicID()) {
2646 case Intrinsic::experimental_gc_get_pointer_base: {
2650 assert(!DVCache.count(Callsite));
2654 DVCache[BaseBC] =
Base;
2655 Callsite->replaceAllUsesWith(BaseBC);
2656 if (!BaseBC->hasName())
2657 BaseBC->takeName(Callsite);
2658 Callsite->eraseFromParent();
2661 case Intrinsic::experimental_gc_get_pointer_offset: {
2663 Value *Derived = Callsite->getOperand(0);
2665 assert(!DVCache.count(Callsite));
2676 Callsite->replaceAllUsesWith(
Offset);
2677 Offset->takeName(Callsite);
2678 Callsite->eraseFromParent();
2691 DefiningValueMapTy &DVCache,
2692 IsKnownBaseMapTy &KnownBases) {
2697 std::set<CallBase *> Uniqued;
2698 Uniqued.insert(ToUpdate.
begin(), ToUpdate.
end());
2699 assert(Uniqued.size() == ToUpdate.
size() &&
"no duplicates please!");
2702 assert(Call->getFunction() == &
F);
2710 auto *II = dyn_cast<InvokeInst>(Call);
2730 "support for FCA unimplemented");
2745 PointerToBaseTy PointerToBase;
2748 for (
size_t i = 0; i < Records.
size(); i++) {
2749 PartiallyConstructedSafepointRecord &
info = Records[i];
2753 errs() <<
"Base Pairs (w/o Relocation):\n";
2754 for (
auto &Pair : PointerToBase) {
2755 errs() <<
" derived ";
2756 Pair.first->printAsOperand(
errs(),
false);
2758 Pair.second->printAsOperand(
errs(),
false);
2778 for (
size_t i = 0; i < Records.
size(); i++) {
2779 PartiallyConstructedSafepointRecord &
Info = Records[i];
2782 for (
auto *Derived :
Info.LiveSet) {
2783 assert(PointerToBase.count(Derived) &&
"Missed base for derived pointer");
2784 Bases.
push_back(PointerToBase[Derived]);
2796 errs() <<
"Base Pairs: (w/Relocation)\n";
2797 for (
auto Pair : PointerToBase) {
2798 errs() <<
" derived ";
2799 Pair.first->printAsOperand(
errs(),
false);
2801 Pair.second->printAsOperand(
errs(),
false);
2814 for (
auto &
Info : Records) {
2815 Info.LiveSet.remove_if([&](
Value *LiveV) {
2816 assert(PointerToBase.count(LiveV) &&
"Missed base for derived pointer");
2817 return isa<Constant>(PointerToBase[LiveV]);
2822 CI->eraseFromParent();
2827 RematCandTy RematerizationCandidates;
2836 for (
size_t i = 0; i < Records.
size(); i++)
2838 RematerizationCandidates,
TTI);
2843 std::vector<DeferredReplacement> Replacements;
2851 for (
size_t i = 0; i < Records.
size(); i++)
2853 PointerToBase, GC.get());
2857 for (
auto &PR : Replacements)
2860 Replacements.clear();
2862 for (
auto &
Info : Records) {
2871 Info.LiveSet.clear();
2873 PointerToBase.clear();
2877 for (
const PartiallyConstructedSafepointRecord &
Info : Records) {
2890 "statepoint must be reachable or liveness is meaningless");
2891 for (
Value *V :
Info.StatepointToken->gc_args()) {
2892 if (!isa<Instruction>(V))
2895 auto *LiveInst = cast<Instruction>(V);
2897 "unreachable values should never be live");
2899 "basic SSA liveness expectation violated by liveness analysis");
2909 "must be a gc pointer type");
2913 return !Records.
empty();
2921 R.addAttribute(Attribute::Dereferenceable);
2922 R.addAttribute(Attribute::DereferenceableOrNull);
2923 R.addAttribute(Attribute::ReadNone);
2924 R.addAttribute(Attribute::ReadOnly);
2925 R.addAttribute(Attribute::WriteOnly);
2926 R.addAttribute(Attribute::NoAlias);
2927 R.addAttribute(Attribute::NoFree);
2946 if (isa<PointerType>(
A.getType()))
2947 F.removeParamAttrs(
A.getArgNo(), R);
2949 if (isa<PointerType>(
F.getReturnType()))
2950 F.removeRetAttrs(R);
2953 F.removeFnAttr(Attr);
2960 if (!isa<LoadInst>(
I) && !isa<StoreInst>(
I))
2975 unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,
2976 LLVMContext::MD_range,
2977 LLVMContext::MD_alias_scope,
2978 LLVMContext::MD_nontemporal,
2979 LLVMContext::MD_nonnull,
2980 LLVMContext::MD_align,
2981 LLVMContext::MD_type};
2984 I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);
3005 if (
auto *II = dyn_cast<IntrinsicInst>(&
I))
3006 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
3007 InvariantStartInstructions.
push_back(II);
3011 if (
MDNode *
Tag =
I.getMetadata(LLVMContext::MD_tbaa)) {
3013 I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
3019 if (
auto *Call = dyn_cast<CallBase>(&
I)) {
3020 for (
int i = 0, e = Call->arg_size(); i != e; i++)
3021 if (isa<PointerType>(Call->getArgOperand(i)->getType()))
3022 Call->removeParamAttrs(i, R);
3023 if (isa<PointerType>(Call->getType()))
3024 Call->removeRetAttrs(R);
3029 for (
auto *II : InvariantStartInstructions) {
3031 II->eraseFromParent();
3052 assert(Strategy &&
"GC strategy is required by function, but was not found");
3054 return Strategy->useRS4GC();
3072 assert(!
F.isDeclaration() && !
F.empty() &&
3073 "need function body to rewrite statepoints in");
3077 if (
const auto *Call = dyn_cast<CallBase>(&
I)) {
3078 if (isa<GCStatepointInst>(Call))
3092 assert((isa<AtomicMemCpyInst>(Call) || isa<AtomicMemMoveInst>(Call)) &&
3093 "Don't expect any other calls here!");
3116 if (NeedsRewrite(
I)) {
3122 "no unreachable blocks expected");
3123 ParsePointNeeded.
push_back(cast<CallBase>(&
I));
3125 if (
auto *CI = dyn_cast<CallInst>(&
I))
3126 if (CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_base ||
3127 CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_offset)
3132 if (ParsePointNeeded.
empty() && Intrinsics.
empty())
3140 if (BB.getUniquePredecessor())
3157 if (
auto *BI = dyn_cast<BranchInst>(TI))
3158 if (BI->isConditional())
3159 return dyn_cast<Instruction>(BI->getCondition());
3165 if (
auto *
Cond = getConditionInst(TI))
3168 if (isa<ICmpInst>(
Cond) &&
Cond->hasOneUse()) {
3170 Cond->moveBefore(TI);
3180 if (!isa<GetElementPtrInst>(
I))
3184 for (
unsigned i = 0; i <
I.getNumOperands(); i++)
3185 if (
auto *OpndVTy = dyn_cast<VectorType>(
I.getOperand(i)->getType())) {
3187 VF == cast<FixedVectorType>(OpndVTy)->getNumElements());
3188 VF = cast<FixedVectorType>(OpndVTy)->getNumElements();
3193 if (!
I.getOperand(0)->getType()->isVectorTy() && VF != 0) {
3195 auto *Splat =
B.CreateVectorSplat(VF,
I.getOperand(0));
3196 I.setOperand(0, Splat);
3205 DefiningValueMapTy DVCache;
3209 IsKnownBaseMapTy KnownBases;
3211 if (!Intrinsics.
empty())
3216 if (!ParsePointNeeded.
empty())
3240 if (isa<PHINode>(
I))
3244 for (
Value *V :
I.operands()) {
3246 "support for FCA unimplemented");
3267 for (
auto &
I : *Succ) {
3268 PHINode *PN = dyn_cast<PHINode>(&
I);
3274 "support for FCA unimplemented");
3295 if (
auto *
I = dyn_cast<Instruction>(V)) {
3299 if (TermOkay && TI ==
I)
3302 "basic SSA liveness expectation violated by liveness analysis");
3325 Data.LiveSet[&BB].clear();
3330 assert(!
Data.LiveSet[&BB].count(Kill) &&
"live set contains kill");
3335 Data.LiveIn[&BB] =
Data.LiveSet[&BB];
3336 Data.LiveIn[&BB].set_union(
Data.LiveOut[&BB]);
3337 Data.LiveIn[&BB].set_subtract(
Data.KillSet[&BB]);
3338 if (!
Data.LiveIn[&BB].empty())
3343 while (!Worklist.
empty()) {
3349 const auto OldLiveOutSize = LiveOut.
size();
3355 if (OldLiveOutSize == LiveOut.
size()) {
3361 Data.LiveOut[BB] = LiveOut;
3371 if (OldLiveIn.
size() != LiveTmp.
size()) {
3372 Data.LiveIn[BB] = LiveTmp;
3400 Out.insert(LiveOut.
begin(), LiveOut.
end());
3405 PartiallyConstructedSafepointRecord &
Info,
3406 PointerToBaseTy &PointerToBase,
3408 StatepointLiveSetTy Updated;
3413 for (
auto *V : Updated)
3414 PointerToBase.insert({ V, V });
3416 Info.LiveSet = Updated;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
ReachingDefAnalysis InstSet & ToRemove
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
This file contains the simple types necessary to represent the attributes associated with functions a...
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Analysis containing CSE Info
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Checks Use for liveness in LiveValues If Use is not live
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
std::optional< std::vector< StOtherPiece > > Other
Rewrite Partial Register Uses
This file implements a map that provides insertion order iteration.
Module.h This file contains the declarations for the Module class.
print must be executed print the must be executed context for all instructions
FunctionAnalysisManager FAM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static bool rewrite(Function &F)
rewrite statepoints for gc
static void makeStatepointExplicitImpl(CallBase *Call, const SmallVectorImpl< Value * > &BasePtrs, const SmallVectorImpl< Value * > &LiveVariables, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC)
rewrite statepoints for Make relocations at statepoints
static void rematerializeLiveValues(CallBase *Call, PartiallyConstructedSafepointRecord &Info, PointerToBaseTy &PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)
static void findRematerializationCandidates(PointerToBaseTy PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)
static std::unique_ptr< GCStrategy > findGCStrategy(Function &F)
Looks up the GC strategy for a given function, returning null if the function doesn't have a GC tag.
static Instruction * rematerializeChain(ArrayRef< Instruction * > ChainToBase, Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase)
static void unique_unsorted(SmallVectorImpl< T > &Vec)
Implement a unique function which doesn't require we sort the input vector.
static void stripNonValidDataFromBody(Function &F)
static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases)
Returns true if V is a known base.
static Value * findBasePointer(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
For a given value or instruction, figure out what base ptr its derived from.
static cl::opt< bool, true > ClobberNonLiveOverride("rs4gc-clobber-non-live", cl::location(ClobberNonLive), cl::Hidden)
static void insertRelocationStores(iterator_range< Value::user_iterator > GCRelocs, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)
static BasicBlock * normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent, DominatorTree &DT)
static void analyzeParsePointLiveness(DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &Result, GCStrategy *GC)
static AttributeList legalizeCallAttributes(LLVMContext &Ctx, AttributeList OrigAL, AttributeList StatepointAL)
static void computeLiveOutSeed(BasicBlock *BB, SetVector< Value * > &LiveTmp, GCStrategy *GC)
static void relocationViaAlloca(Function &F, DominatorTree &DT, ArrayRef< Value * > Live, ArrayRef< PartiallyConstructedSafepointRecord > Records)
Do all the relocation update via allocas and mem2reg.
static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi)
static cl::opt< unsigned > RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden, cl::init(6))
static Value * findBaseOrBDV(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Return a base pointer for this value if known.
static Value * findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Returns the base defining value for this value.
static void insertUseHolderAfter(CallBase *Call, const ArrayRef< Value * > Values, SmallVectorImpl< CallInst * > &Holders)
Insert holders so that each Value is obviously live through the entire lifetime of the call.
static void insertRematerializationStores(const RematerializedValueMapTy &RematerializedValues, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)
static bool insertParsePoints(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, SmallVectorImpl< CallBase * > &ToUpdate, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
static void findBasePointers(const StatepointLiveSetTy &live, PointerToBaseTy &PointerToBase, DominatorTree *DT, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
static bool shouldRewriteStatepointsIn(Function &F)
Returns true if this function should be rewritten by this pass.
static cl::opt< bool > RematDerivedAtUses("rs4gc-remat-derived-at-uses", cl::Hidden, cl::init(true))
static ArrayRef< Use > GetDeoptBundleOperands(const CallBase *Call)
static void stripNonValidAttributesFromPrototype(Function &F)
static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data, StatepointLiveSetTy &out, GCStrategy *GC)
Given results from the dataflow liveness computation, find the set of live Values at a particular ins...
static void computeLiveInValues(DominatorTree &DT, Function &F, GCPtrLivenessData &Data, GCStrategy *GC)
Compute the live-in set for every basic block in the function.
static void stripInvalidMetadataFromInstruction(Instruction &I)
Certain metadata on instructions are invalid after running RS4GC.
static constexpr Attribute::AttrKind FnAttrsToStrip[]
static bool areBothVectorOrScalar(Value *First, Value *Second)
static void rematerializeLiveValuesAtUses(RematCandTy &RematerizationCandidates, MutableArrayRef< PartiallyConstructedSafepointRecord > Records, PointerToBaseTy &PointerToBase)
static bool isHandledGCPointerType(Type *T, GCStrategy *GC)
static Value * findRematerializableChainToBasePointer(SmallVectorImpl< Instruction * > &ChainToBase, Value *CurrentValue)
static cl::opt< bool > PrintLiveSetSize("spp-print-liveset-size", cl::Hidden, cl::init(false))
static Value * findBaseDefiningValueOfVector(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Return a base defining value for the 'Index' element of the given vector instruction 'I'.
static void stripNonValidData(Module &M)
The IR fed into RewriteStatepointsForGC may have had attributes and metadata implying dereferenceabil...
static InstructionCost chainToBasePointerCost(SmallVectorImpl< Instruction * > &Chain, TargetTransformInfo &TTI)
static bool isUnhandledGCPointerType(Type *Ty, GCStrategy *GC)
static SetVector< Value * > computeKillSet(BasicBlock *BB, GCStrategy *GC)
static bool ClobberNonLive
static cl::opt< bool > PrintBasePointers("spp-print-base-pointers", cl::Hidden, cl::init(false))
static bool isOriginalBaseResult(Value *V)
This value is a base pointer that is not generated by RS4GC, i.e.
static cl::opt< bool > PrintLiveSet("spp-print-liveset", cl::Hidden, cl::init(false))
static void setKnownBase(Value *V, bool IsKnownBase, IsKnownBaseMapTy &KnownBases)
Caches the IsKnownBase flag for a value and asserts that it wasn't present in the cache before.
static cl::opt< bool > AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", cl::Hidden, cl::init(true))
static void makeStatepointExplicit(DominatorTree &DT, CallBase *Call, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC)
static std::string suffixed_name_or(Value *V, StringRef Suffix, StringRef DefaultName)
static void CreateGCRelocates(ArrayRef< Value * > LiveVariables, ArrayRef< Value * > BasePtrs, Instruction *StatepointToken, IRBuilder<> &Builder, GCStrategy *GC)
Helper function to place all gc relocates necessary for the given statepoint.
static void checkBasicSSA(DominatorTree &DT, SetVector< Value * > &Live, Instruction *TI, bool TermOkay=false)
Check that the items in 'Live' dominate 'TI'.
static StringRef getDeoptLowering(CallBase *Call)
static void findLiveReferences(Function &F, DominatorTree &DT, ArrayRef< CallBase * > toUpdate, MutableArrayRef< struct PartiallyConstructedSafepointRecord > records, GCStrategy *GC)
static AttributeMask getParamAndReturnAttributesToRemove()
static bool inlineGetBaseAndOffset(Function &F, SmallVectorImpl< CallInst * > &Intrinsics, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)
static Value * findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)
Helper function for findBasePointer - Will return a value which either a) defines the base pointer fo...
static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &result, PointerToBaseTy &PointerToBase, GCStrategy *GC)
Given an updated version of the dataflow liveness results, update the liveset and base pointer maps f...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
verify safepoint Safepoint IR static false bool isGCPointerType(Type *T)
static bool containsGCPtrType(Type *Ty)
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallSet class.
This file defines the SmallVector class.
an instruction to allocate memory on the stack
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
This class represents an incoming formal argument to a Function.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
reverse_iterator rend() const
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
reverse_iterator rbegin() const
Value handle that asserts if the Value is deleted.
AttrBuilder & removeAttribute(Attribute::AttrKind Val)
Remove an attribute from the builder.
AttributeSet getFnAttrs() const
The function attributes are returned.
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute > > Attrs)
Create an AttributeList with the specified parameters in it.
bool isEmpty() const
Return true if there are no attributes.
AttributeList addFnAttributes(LLVMContext &C, const AttrBuilder &B) const
Add function attribute to the list.
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if the attribute exists for the function.
Attribute getFnAttr(Attribute::AttrKind Kind) const
Return the attribute object that exists for the function.
StringRef getValueAsString() const
Return the attribute's value as a string.
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const LandingPadInst * getLandingPadInst() const
Return the landingpad instruction associated with the landing pad.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
reverse_iterator rbegin()
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
InstListType::reverse_iterator reverse_iterator
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
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...
This class represents a no-op cast from one type to another.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void setCallingConv(CallingConv::ID CC)
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
AttributeList getAttributes() const
Return the parameter attributes for this call.
This class represents a function call, abstracting a target machine's calling convention.
void setTailCallKind(TailCallKind TCK)
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
This is the base class for all instructions that perform data casts.
static ConstantAggregateZero * get(Type *Ty)
This is the shared class of boolean and integer constants.
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Implements a dense probed hash-table based set.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
A handy container for a FunctionType+Callee-pointer pair, which can be passed around as a single enti...
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Represents calls to the gc.relocate intrinsic.
Value * getDerivedPtr() const
Represents a gc.statepoint intrinsic call.
GCStrategy describes a garbage collector algorithm's code generation requirements,...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
A wrapper class for inspecting calls to intrinsic functions.
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
This class implements a map that also provides access to all stored values in a deterministic order.
size_type count(const KeyT &Key) const
iterator find(const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
A Module instance is used to store all the information related to an LLVM module.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserve()
Mark an analysis as preserved.
This class represents the LLVM 'select' instruction.
size_type size() const
Determine the number of elements in the SetVector.
bool remove(const value_type &X)
Remove an item from the set vector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool set_union(const STy &S)
Compute This := This u S, return whether 'This' changed.
bool empty() const
Determine if the SetVector is empty or not.
value_type pop_back_val()
iterator begin()
Get an iterator to the beginning of the SetVector.
void set_subtract(const STy &S)
Compute This := This - B TODO: We should be able to use set_subtract from SetOperations....
iterator end()
Get an iterator to the end of the SetVector.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
StringRef - Represent a constant reference to a string, i.e.
std::string str() const
str - Get the contents as an std::string.
bool equals(StringRef RHS) const
equals - Check for string equality, this is more efficient than compare() when the relative ordering ...
Class to represent struct types.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
static Type * getVoidTy(LLVMContext &C)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
iterator_range< value_op_iterator > operand_values()
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
User * getUniqueUndroppableUser()
Return true if there is exactly one unique user of this value that cannot be dropped (that user can h...
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getNumUses() const
This method computes the number of uses of this Value.
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
ilist_iterator< OptionsT, !IsReverse, IsConst > getReverse() const
Get a reverse iterator to the same node.
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ Cold
Attempts to make code in the caller as efficient as possible under the assumption that the call is no...
AttributeList getAttributes(LLVMContext &C, ID id)
Return the attributes for an intrinsic.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
initializer< Ty > init(const Ty &Val)
LocationClass< Ty > location(Ty &L)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
void PromoteMemToReg(ArrayRef< AllocaInst * > Allocas, DominatorTree &DT, AssumptionCache *AC=nullptr)
Promote the specified list of alloca instructions into scalar registers, inserting PHI nodes as appro...
auto successors(const MachineBasicBlock *BB)
bool operator!=(uint64_t V1, const APInt &V2)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
Interval::pred_iterator pred_end(Interval *I)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
StatepointDirectives parseStatepointDirectivesFromAttrs(AttributeList AS)
Parse out statepoint directives from the function attributes present in AS.
ModulePass * createRewriteStatepointsForGCLegacyPass()
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
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...
bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)
We know that BB has one predecessor.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
@ DeoptLiveIn
Mark the deopt arguments associated with the statepoint as only being "live-in".
@ GCTransition
Indicates that this statepoint is a transition from GC-aware code to code that is not GC-aware.
void initializeRewriteStatepointsForGCLegacyPassPass(PassRegistry &)
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
std::unique_ptr< GCStrategy > getGCStrategy(const StringRef Name)
Lookup the GCStrategy object associated with the given gc name.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool isStatepointDirectiveAttr(Attribute Attr)
Return true if the Attr is an attribute that is a statepoint directive.
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
MapVector< BasicBlock *, SetVector< Value * > > LiveSet
Values used in this block (and thus live); does not included values killed within this block.
MapVector< BasicBlock *, SetVector< Value * > > LiveOut
Values live out of this basic block (i.e.
MapVector< BasicBlock *, SetVector< Value * > > KillSet
Values defined in this block.
MapVector< BasicBlock *, SetVector< Value * > > LiveIn
Values live into this basic block (i.e.
RematerializedValueMapTy RematerializedValues
Record live values we are rematerialized instead of relocating.
Instruction * UnwindToken
Instruction to which exceptional gc relocates are attached Makes it easier to iterate through them du...
GCStatepointInst * StatepointToken
The new gc.statepoint instruction itself.
StatepointLiveSetTy LiveSet
The set of values known to be live across this safepoint.
SmallVector< Instruction *, 3 > ChainToBase
bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &, const TargetLibraryInfo &)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Call sites that get wrapped by a gc.statepoint (currently only in RewriteStatepointsForGC and potenti...
std::optional< uint32_t > NumPatchBytes
std::optional< uint64_t > StatepointID
static const uint64_t DefaultStatepointID