77#define DEBUG_TYPE "rewrite-statepoints-for-gc"
97#ifdef EXPENSIVE_CHECKS
134 bool Changed =
false;
138 if (
F.isDeclaration() ||
F.empty())
167struct GCPtrLivenessData {
198using RematerializedValueMapTy =
201struct PartiallyConstructedSafepointRecord {
203 StatepointLiveSetTy LiveSet;
216 RematerializedValueMapTy RematerializedValues;
219struct RematerizlizationCandidateRecord {
232 std::optional<OperandBundleUse> DeoptBundle =
237 "Found non-leaf call without deopt info!");
241 return DeoptBundle->Inputs;
254 assert(GC &&
"GC Strategy for isGCPointerType cannot be null");
256 if (!isa<PointerType>(
T))
260 return GC->isGCManagedPointer(
T).value_or(
true);
273 if (
auto VT = dyn_cast<VectorType>(
T))
285 if (
VectorType *VT = dyn_cast<VectorType>(Ty))
287 if (
ArrayType *AT = dyn_cast<ArrayType>(Ty))
289 if (
StructType *ST = dyn_cast<StructType>(Ty))
291 [GC](
Type *Ty) { return containsGCPtrType(Ty, GC); });
307 return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.
str();
316 PartiallyConstructedSafepointRecord &Result,
GCStrategy *GC) {
317 StatepointLiveSetTy LiveSet;
321 dbgs() <<
"Live Variables:\n";
322 for (
Value *V : LiveSet)
323 dbgs() <<
" " << V->getName() <<
" " << *V <<
"\n";
326 dbgs() <<
"Safepoint For: " << Call->getCalledOperand()->getName() <<
"\n";
327 dbgs() <<
"Number live values: " << LiveSet.size() <<
"\n";
329 Result.LiveSet = LiveSet;
338 IsKnownBaseMapTy &KnownBases);
341 IsKnownBaseMapTy &KnownBases);
353 IsKnownBaseMapTy &KnownBases) {
357 auto Cached = Cache.find(
I);
358 if (Cached != Cache.end())
359 return Cached->second;
361 if (isa<Argument>(
I)) {
368 if (isa<Constant>(
I)) {
377 if (isa<LoadInst>(
I)) {
383 if (isa<InsertElementInst>(
I)) {
392 if (isa<ShuffleVectorInst>(
I)) {
405 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I)) {
414 if (
auto *Freeze = dyn_cast<FreezeInst>(
I)) {
422 if (
auto *BC = dyn_cast<BitCastInst>(
I)) {
431 if (isa<CallInst>(
I) || isa<InvokeInst>(
I)) {
439 assert((isa<SelectInst>(
I) || isa<PHINode>(
I)) &&
440 "unknown vector instruction - no base found for vector element");
451 IsKnownBaseMapTy &KnownBases) {
452 assert(
I->getType()->isPtrOrPtrVectorTy() &&
453 "Illegal to ask for the base pointer of a non-pointer type");
454 auto Cached = Cache.find(
I);
455 if (Cached != Cache.end())
456 return Cached->second;
458 if (
I->getType()->isVectorTy())
461 if (isa<Argument>(
I)) {
469 if (isa<Constant>(
I)) {
491 if (isa<IntToPtrInst>(
I)) {
497 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
498 Value *Def = CI->stripPointerCasts();
501 assert(cast<PointerType>(Def->getType())->getAddressSpace() ==
502 cast<PointerType>(CI->getType())->getAddressSpace() &&
503 "unsupported addrspacecast");
507 assert(!isa<CastInst>(Def) &&
"shouldn't find another cast here");
513 if (isa<LoadInst>(
I)) {
528 if (
auto *Freeze = dyn_cast<FreezeInst>(
I)) {
535 switch (II->getIntrinsicID()) {
539 case Intrinsic::experimental_gc_statepoint:
541 case Intrinsic::experimental_gc_relocate:
546 case Intrinsic::gcroot:
551 "interaction with the gcroot mechanism is not supported");
552 case Intrinsic::experimental_gc_get_pointer_base:
561 if (isa<CallInst>(
I) || isa<InvokeInst>(
I)) {
569 assert(!isa<LandingPadInst>(
I) &&
"Landing Pad is unimplemented");
571 if (isa<AtomicCmpXchgInst>(
I)) {
580 assert(!isa<AtomicRMWInst>(
I) &&
"Xchg handled above, all others are "
581 "binary ops which don't apply to pointers");
586 if (isa<ExtractValueInst>(
I)) {
594 assert(!isa<InsertValueInst>(
I) &&
595 "Base pointer for a struct is meaningless");
600 isa<Instruction>(
I) && cast<Instruction>(
I)->getMetadata(
"is_base_value");
608 if (isa<ExtractElementInst>(
I))
618 assert((isa<SelectInst>(
I) || isa<PHINode>(
I)) &&
619 "missing instruction case in findBaseDefiningValue");
625 IsKnownBaseMapTy &KnownBases) {
626 if (!Cache.contains(
I)) {
630 << Cache[
I]->getName() <<
", is known base = "
631 << KnownBases[
I] <<
"\n");
634 assert(KnownBases.contains(Cache[
I]) &&
635 "Cached value must be present in known bases map");
642 IsKnownBaseMapTy &KnownBases) {
644 auto Found = Cache.find(Def);
645 if (Found != Cache.end()) {
647 return Found->second;
658 return !isa<PHINode>(V) && !isa<SelectInst>(V) &&
659 !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&
660 !isa<ShuffleVectorInst>(V);
665 auto It = KnownBases.find(V);
666 assert(It != KnownBases.end() &&
"Value not present in the map");
671 IsKnownBaseMapTy &KnownBases) {
673 auto It = KnownBases.find(V);
674 if (It != KnownBases.end())
675 assert(It->second == IsKnownBase &&
"Changing already present value");
677 KnownBases[V] = IsKnownBase;
682 return isa<VectorType>(
First->getType()) ==
683 isa<VectorType>(Second->
getType());
708 explicit BDVState(
Value *OriginalValue)
709 : OriginalValue(OriginalValue) {}
710 explicit BDVState(
Value *OriginalValue, StatusTy
Status,
Value *BaseValue =
nullptr)
711 : OriginalValue(OriginalValue),
Status(
Status), BaseValue(BaseValue) {
715 StatusTy getStatus()
const {
return Status; }
716 Value *getOriginalValue()
const {
return OriginalValue; }
717 Value *getBaseValue()
const {
return BaseValue; }
719 bool isBase()
const {
return getStatus() ==
Base; }
720 bool isUnknown()
const {
return getStatus() ==
Unknown; }
721 bool isConflict()
const {
return getStatus() == Conflict; }
726 void meet(
const BDVState &
Other) {
727 auto markConflict = [&]() {
728 Status = BDVState::Conflict;
737 BaseValue =
Other.getBaseValue();
741 assert(isBase() &&
"Unknown state");
743 if (
Other.isUnknown())
746 if (
Other.isConflict())
747 return markConflict();
751 if (getBaseValue() !=
Other.getBaseValue())
752 return markConflict();
757 return OriginalValue ==
Other.OriginalValue && BaseValue ==
Other.BaseValue &&
761 bool operator!=(
const BDVState &other)
const {
return !(*
this == other); }
770 switch (getStatus()) {
781 OS <<
" (base " << getBaseValue() <<
" - "
782 << (getBaseValue() ? getBaseValue()->getName() :
"nullptr") <<
")"
783 <<
" for " << OriginalValue->getName() <<
":";
806 IsKnownBaseMapTy &KnownBases) {
835 auto isExpectedBDVType = [](
Value *BDV) {
836 return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||
837 isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||
838 isa<ShuffleVectorInst>(BDV);
850 auto VerifyStates = [&]() {
851 for (
auto &Entry : States) {
852 assert(Entry.first == Entry.second.getOriginalValue());
857 auto visitBDVOperands = [](
Value *BDV, std::function<void (
Value*)>
F) {
858 if (
PHINode *PN = dyn_cast<PHINode>(BDV)) {
859 for (
Value *InVal : PN->incoming_values())
861 }
else if (
SelectInst *SI = dyn_cast<SelectInst>(BDV)) {
862 F(SI->getTrueValue());
863 F(SI->getFalseValue());
864 }
else if (
auto *EE = dyn_cast<ExtractElementInst>(BDV)) {
865 F(EE->getVectorOperand());
866 }
else if (
auto *IE = dyn_cast<InsertElementInst>(BDV)) {
867 F(IE->getOperand(0));
868 F(IE->getOperand(1));
869 }
else if (
auto *SV = dyn_cast<ShuffleVectorInst>(BDV)) {
872 F(SV->getOperand(0));
873 if (!SV->isZeroEltSplat())
874 F(SV->getOperand(1));
886 States.
insert({Def, BDVState(Def)});
887 while (!Worklist.
empty()) {
891 auto visitIncomingValue = [&](
Value *InVal) {
900 assert(isExpectedBDVType(
Base) &&
"the only non-base values "
901 "we see should be base defining values");
906 visitBDVOperands(Current, visitIncomingValue);
913 for (
const auto &Pair : States) {
914 LLVM_DEBUG(
dbgs() <<
" " << Pair.second <<
" for " << *Pair.first <<
"\n");
926 for (
auto Pair : States) {
927 Value *BDV = Pair.first;
928 auto canPruneInput = [&](
Value *V) {
931 if (V->stripPointerCasts() == BDV)
934 if (V->stripPointerCasts() != VBDV)
938 return States.count(VBDV) == 0;
941 bool CanPrune =
true;
942 visitBDVOperands(BDV, [&](
Value *
Op) {
943 CanPrune = CanPrune && canPruneInput(
Op);
956 if (!States.
count(Def))
961 auto GetStateForBDV = [&](
Value *BaseValue,
Value *Input) {
962 auto I = States.
find(BaseValue);
963 if (
I != States.
end())
966 return BDVState(BaseValue, BDVState::Base, BaseValue);
969 bool Progress =
true;
972 const size_t OldSize = States.
size();
979 for (
auto Pair : States) {
980 Value *BDV = Pair.first;
986 "why did it get added?");
988 BDVState NewState(BDV);
989 visitBDVOperands(BDV, [&](
Value *
Op) {
991 auto OpState = GetStateForBDV(BDV,
Op);
992 NewState.meet(OpState);
995 BDVState OldState = States[BDV];
996 if (OldState != NewState) {
998 States[BDV] = NewState;
1002 assert(OldSize == States.size() &&
1003 "fixed point shouldn't be adding any new nodes to state");
1009 for (
const auto &Pair : States) {
1010 LLVM_DEBUG(
dbgs() <<
" " << Pair.second <<
" for " << *Pair.first <<
"\n");
1016 for (
auto Pair : States) {
1018 BDVState State = Pair.second;
1019 auto *BaseValue = State.getBaseValue();
1025 "why did it get added?");
1026 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1028 if (!State.isBase() || !isa<VectorType>(BaseValue->
getType()))
1034 if (isa<ExtractElementInst>(
I)) {
1035 auto *EE = cast<ExtractElementInst>(
I);
1040 State.getBaseValue(), EE->getIndexOperand(),
"base_ee", EE);
1041 BaseInst->setMetadata(
"is_base_value",
MDNode::get(
I->getContext(), {}));
1042 States[
I] = BDVState(
I, BDVState::Base, BaseInst);
1044 }
else if (!isa<VectorType>(
I->getType())) {
1050 States[
I] = BDVState(
I, BDVState::Conflict);
1060 for (
auto Pair : States) {
1062 BDVState State = Pair.second;
1068 "why did it get added?");
1069 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1074 assert(!isa<InsertElementInst>(
I) || State.isConflict());
1076 if (!State.isConflict())
1079 auto getMangledName = [](
Instruction *
I) -> std::string {
1080 if (isa<PHINode>(
I)) {
1082 }
else if (isa<SelectInst>(
I)) {
1084 }
else if (isa<ExtractElementInst>(
I)) {
1086 }
else if (isa<InsertElementInst>(
I)) {
1095 BaseInst->
setName(getMangledName(
I));
1098 States[
I] = BDVState(
I, BDVState::Conflict, BaseInst);
1117 if (!States.
count(BDV)) {
1123 Base = States[BDV].getBaseValue();
1127 if (
Base->getType() != Input->
getType() && InsertPt)
1135 for (
auto Pair : States) {
1137 BDVState State = Pair.second;
1144 "why did it get added?");
1145 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1146 if (!State.isConflict())
1149 if (
PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {
1150 PHINode *PN = cast<PHINode>(BDV);
1158 for (
unsigned i = 0; i < NumPHIValues; i++) {
1161 if (!BlockToValue.
count(InBB))
1162 BlockToValue[InBB] = getBaseForInput(InVal, InBB->
getTerminator());
1165 Value *OldBase = BlockToValue[InBB];
1166 Value *
Base = getBaseForInput(InVal,
nullptr);
1170 auto StripBitCasts = [](
Value *V) ->
Value * {
1171 while (
auto *BC = dyn_cast<BitCastInst>(V))
1172 V = BC->getOperand(0);
1181 assert(StripBitCasts(
Base) == StripBitCasts(OldBase) &&
1182 "findBaseOrBDV should be pure!");
1186 BasePHI->setIncomingValue(i,
Base);
1189 dyn_cast<SelectInst>(State.getBaseValue())) {
1194 BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));
1195 BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));
1196 }
else if (
auto *BaseEE =
1197 dyn_cast<ExtractElementInst>(State.getBaseValue())) {
1198 Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();
1201 BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));
1202 }
else if (
auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){
1203 auto *BdvIE = cast<InsertElementInst>(BDV);
1204 auto UpdateOperand = [&](
int OperandIdx) {
1205 Value *InVal = BdvIE->getOperand(OperandIdx);
1206 Value *
Base = getBaseForInput(InVal, BaseIE);
1207 BaseIE->setOperand(OperandIdx,
Base);
1212 auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());
1213 auto *BdvSV = cast<ShuffleVectorInst>(BDV);
1214 auto UpdateOperand = [&](
int OperandIdx) {
1215 Value *InVal = BdvSV->getOperand(OperandIdx);
1216 Value *
Base = getBaseForInput(InVal, BaseSV);
1217 BaseSV->setOperand(OperandIdx,
Base);
1220 if (!BdvSV->isZeroEltSplat())
1224 Value *InVal = BdvSV->getOperand(1);
1237 for (
auto Pair : States) {
1238 auto *BDV = Pair.first;
1239 Value *
Base = Pair.second.getBaseValue();
1246 "why did it get added?");
1249 dbgs() <<
"Updating base value cache"
1250 <<
" for: " << BDV->
getName() <<
" from: "
1251 << (Cache.count(BDV) ? Cache[BDV]->getName().str() :
"none")
1252 <<
" to: " <<
Base->getName() <<
"\n");
1256 assert(Cache.count(Def));
1277 DefiningValueMapTy &DVCache,
1278 IsKnownBaseMapTy &KnownBases) {
1281 assert(base &&
"failed to find base pointer");
1282 PointerToBase[ptr] = base;
1283 assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||
1284 DT->
dominates(cast<Instruction>(base)->getParent(),
1285 cast<Instruction>(ptr)->getParent())) &&
1286 "The base we found better dominate the derived pointer");
1294 PartiallyConstructedSafepointRecord &result,
1295 PointerToBaseTy &PointerToBase,
1296 IsKnownBaseMapTy &KnownBases) {
1297 StatepointLiveSetTy PotentiallyDerivedPointers = result.LiveSet;
1304 for (
Value *V : Opt->Inputs) {
1305 if (!PotentiallyDerivedPointers.count(V))
1307 PotentiallyDerivedPointers.remove(V);
1308 PointerToBase[V] = V;
1318 PartiallyConstructedSafepointRecord &result,
1319 PointerToBaseTy &PointerToBase,
1325 PointerToBaseTy &PointerToBase,
GCStrategy *GC) {
1328 GCPtrLivenessData RevisedLivenessData;
1330 for (
size_t i = 0; i < records.
size(); i++) {
1331 struct PartiallyConstructedSafepointRecord &
info = records[i];
1343 Value *AlternateLiveBase) {
1353 assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
1357 ClonedValue->
setName(Instr->getName() +
".remat");
1361 if (LastClonedValue) {
1369 "incorrect use in rematerialization chain");
1372 assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);
1381 if (RootOfChain != AlternateLiveBase)
1385 LastClonedValue = ClonedValue;
1389 return LastClonedValue;
1408 assert(!isa<PHINode>(Ret->begin()) &&
1409 "All PHI nodes should have been removed!");
1422 {Attribute::Memory, Attribute::NoSync, Attribute::NoFree};
1430 return StatepointAL;
1463 assert(ValIt != LiveVec.
end() &&
"Val not found in LiveVec!");
1464 size_t Index = std::distance(LiveVec.
begin(), ValIt);
1477 auto getGCRelocateDecl = [&](
Type *Ty) {
1479 auto AS = Ty->getScalarType()->getPointerAddressSpace();
1481 if (
auto *VT = dyn_cast<VectorType>(Ty))
1483 cast<FixedVectorType>(VT)->getNumElements());
1499 if (!TypeToDeclMap.
count(Ty))
1500 TypeToDeclMap[Ty] = getGCRelocateDecl(Ty);
1501 Function *GCRelocateDecl = TypeToDeclMap[Ty];
1505 GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
1517class DeferredReplacement {
1520 bool IsDeoptimize =
false;
1522 DeferredReplacement() =
default;
1526 assert(Old != New && Old && New &&
1527 "Cannot RAUW equal values or to / from null!");
1529 DeferredReplacement
D;
1535 static DeferredReplacement createDelete(
Instruction *ToErase) {
1536 DeferredReplacement
D;
1541 static DeferredReplacement createDeoptimizeReplacement(
Instruction *Old) {
1543 auto *
F = cast<CallInst>(Old)->getCalledFunction();
1544 assert(
F &&
F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&
1545 "Only way to construct a deoptimize deferred replacement");
1547 DeferredReplacement
D;
1549 D.IsDeoptimize =
true;
1554 void doReplacement() {
1558 assert(OldI != NewI &&
"Disallowed at construction?!");
1559 assert((!IsDeoptimize || !New) &&
1560 "Deoptimize intrinsics are not replaced!");
1573 RI->eraseFromParent();
1583 const char *DeoptLowering =
"deopt-lowering";
1584 if (Call->hasFnAttr(DeoptLowering)) {
1590 Function *
F = Call->getCalledFunction();
1591 assert(
F &&
F->hasFnAttribute(DeoptLowering));
1592 return F->getFnAttribute(DeoptLowering).getValueAsString();
1594 return "live-through";
1601 PartiallyConstructedSafepointRecord &Result,
1602 std::vector<DeferredReplacement> &Replacements,
1603 const PointerToBaseTy &PointerToBase,
1619 std::optional<ArrayRef<Use>> DeoptArgs;
1621 DeoptArgs = Bundle->Inputs;
1622 std::optional<ArrayRef<Use>> TransitionArgs;
1624 TransitionArgs = Bundle->Inputs;
1632 bool IsDeoptimize =
false;
1643 if (DeoptLowering.
equals(
"live-in"))
1646 assert(DeoptLowering.
equals(
"live-through") &&
"Unsupported value!");
1649 FunctionCallee CallTarget(Call->getFunctionType(), Call->getCalledOperand());
1651 auto IID =
F->getIntrinsicID();
1652 if (IID == Intrinsic::experimental_deoptimize) {
1658 for (
Value *Arg : CallArgs)
1667 CallTarget =
F->getParent()
1668 ->getOrInsertFunction(
"__llvm_deoptimize", FTy);
1670 IsDeoptimize =
true;
1671 }
else if (IID == Intrinsic::memcpy_element_unordered_atomic ||
1672 IID == Intrinsic::memmove_element_unordered_atomic) {
1689 auto &
Context = Call->getContext();
1690 auto &
DL = Call->getModule()->getDataLayout();
1691 auto GetBaseAndOffset = [&](
Value *Derived) {
1697 if (isa<Constant>(Derived))
1701 assert(PointerToBase.count(Derived));
1702 Base = PointerToBase.find(Derived)->second;
1704 unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
1710 return std::make_pair(
Base,
Builder.CreateSub(Derived_int, Base_int));
1713 auto *Dest = CallArgs[0];
1714 Value *DestBase, *DestOffset;
1715 std::tie(DestBase, DestOffset) = GetBaseAndOffset(Dest);
1717 auto *Source = CallArgs[1];
1718 Value *SourceBase, *SourceOffset;
1719 std::tie(SourceBase, SourceOffset) = GetBaseAndOffset(Source);
1721 auto *LengthInBytes = CallArgs[2];
1722 auto *ElementSizeCI = cast<ConstantInt>(CallArgs[3]);
1732 for (
Value *Arg : CallArgs)
1738 uint64_t ElementSize = ElementSizeCI->getZExtValue();
1739 if (IID == Intrinsic::memcpy_element_unordered_atomic) {
1740 switch (ElementSize) {
1742 return "__llvm_memcpy_element_unordered_atomic_safepoint_1";
1744 return "__llvm_memcpy_element_unordered_atomic_safepoint_2";
1746 return "__llvm_memcpy_element_unordered_atomic_safepoint_4";
1748 return "__llvm_memcpy_element_unordered_atomic_safepoint_8";
1750 return "__llvm_memcpy_element_unordered_atomic_safepoint_16";
1755 assert(IID == Intrinsic::memmove_element_unordered_atomic);
1756 switch (ElementSize) {
1758 return "__llvm_memmove_element_unordered_atomic_safepoint_1";
1760 return "__llvm_memmove_element_unordered_atomic_safepoint_2";
1762 return "__llvm_memmove_element_unordered_atomic_safepoint_4";
1764 return "__llvm_memmove_element_unordered_atomic_safepoint_8";
1766 return "__llvm_memmove_element_unordered_atomic_safepoint_16";
1774 ->getOrInsertFunction(GetFunctionName(IID, ElementSizeCI), FTy);
1780 if (
auto *CI = dyn_cast<CallInst>(Call)) {
1782 StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
1783 TransitionArgs, DeoptArgs, GCArgs,
"safepoint_token");
1793 CI->getContext(), CI->getAttributes(), SPCall->
getAttributes()));
1795 Token = cast<GCStatepointInst>(SPCall);
1799 assert(CI->getNextNode() &&
"Not a terminator, must have next!");
1800 Builder.SetInsertPoint(CI->getNextNode());
1801 Builder.SetCurrentDebugLocation(CI->getNextNode()->getDebugLoc());
1803 auto *II = cast<InvokeInst>(Call);
1809 StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(),
1810 II->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs, GCArgs,
1811 "statepoint_token");
1820 II->getContext(), II->getAttributes(), SPInvoke->
getAttributes()));
1822 Token = cast<GCStatepointInst>(SPInvoke);
1825 BasicBlock *UnwindBlock = II->getUnwindDest();
1828 "can't safely insert in this block!");
1831 Builder.SetCurrentDebugLocation(II->getDebugLoc());
1835 Result.UnwindToken = ExceptionalToken;
1840 BasicBlock *NormalDest = II->getNormalDest();
1843 "can't safely insert in this block!");
1850 assert(Token &&
"Should be set in one of the above branches!");
1856 Replacements.push_back(
1857 DeferredReplacement::createDeoptimizeReplacement(Call));
1859 Token->
setName(
"statepoint_token");
1860 if (!Call->getType()->isVoidTy() && !Call->use_empty()) {
1865 Call->getAttributes().getRetAttrs()));
1873 Replacements.emplace_back(
1874 DeferredReplacement::createRAUW(Call, GCResult));
1876 Replacements.emplace_back(DeferredReplacement::createDelete(Call));
1880 Result.StatepointToken = Token;
1893 PartiallyConstructedSafepointRecord &Result,
1894 std::vector<DeferredReplacement> &Replacements,
1895 const PointerToBaseTy &PointerToBase,
GCStrategy *GC) {
1896 const auto &LiveSet = Result.LiveSet;
1900 LiveVec.
reserve(LiveSet.size());
1901 BaseVec.
reserve(LiveSet.size());
1902 for (
Value *L : LiveSet) {
1904 assert(PointerToBase.count(L));
1905 Value *
Base = PointerToBase.find(L)->second;
1925 for (
User *U : GCRelocs) {
1932 Value *Alloca = AllocaMap[OriginalValue];
1938 "Should always have one since it's not a terminator");
1940 Value *CastedRelocatedValue =
1941 Builder.CreateBitCast(Relocate,
1942 cast<AllocaInst>(Alloca)->getAllocatedType(),
1945 new StoreInst(CastedRelocatedValue, Alloca,
1946 cast<Instruction>(CastedRelocatedValue)->getNextNode());
1949 VisitedLiveValues.
insert(OriginalValue);
1957 const RematerializedValueMapTy &RematerializedValues,
1960 for (
auto RematerializedValuePair: RematerializedValues) {
1961 Instruction *RematerializedValue = RematerializedValuePair.first;
1962 Value *OriginalValue = RematerializedValuePair.second;
1965 "Can not find alloca for rematerialized value");
1966 Value *Alloca = AllocaMap[OriginalValue];
1968 new StoreInst(RematerializedValue, Alloca,
1972 VisitedLiveValues.
insert(OriginalValue);
1984 int InitialAllocaNum = 0;
1986 if (isa<AllocaInst>(
I))
1994 std::size_t NumRematerializedValues = 0;
2000 auto emitAllocaFor = [&](
Value *LiveValue) {
2002 DL.getAllocaAddrSpace(),
"",
2003 F.getEntryBlock().getFirstNonPHI());
2004 AllocaMap[LiveValue] = Alloca;
2013 for (
const auto &
Info : Records)
2014 for (
auto RematerializedValuePair :
Info.RematerializedValues) {
2015 Value *OriginalValue = RematerializedValuePair.second;
2016 if (AllocaMap.
count(OriginalValue) != 0)
2019 emitAllocaFor(OriginalValue);
2020 ++NumRematerializedValues;
2032 for (
const auto &
Info : Records) {
2033 Value *Statepoint =
Info.StatepointToken;
2043 if (isa<InvokeInst>(Statepoint)) {
2059 for (
auto Pair : AllocaMap) {
2060 Value *Def = Pair.first;
2064 if (VisitedLiveValues.
count(Def)) {
2071 for (
auto *AI : ToClobber) {
2072 auto AT = AI->getAllocatedType();
2074 if (AT->isVectorTy())
2084 if (
auto II = dyn_cast<InvokeInst>(Statepoint)) {
2085 InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt());
2086 InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt());
2088 InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode());
2094 for (
auto Pair : AllocaMap) {
2095 Value *Def = Pair.first;
2103 Uses.reserve(Def->getNumUses());
2104 for (
User *U : Def->users()) {
2105 if (!isa<ConstantExpr>(U)) {
2111 Uses.push_back(cast<Instruction>(U));
2120 if (isa<PHINode>(
Use)) {
2122 for (
unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {
2123 if (Def == Phi->getIncomingValue(i)) {
2126 Phi->getIncomingBlock(i)->getTerminator());
2127 Phi->setIncomingValue(i, Load);
2133 Use->replaceUsesOfWith(Def, Load);
2141 DL.getABITypeAlign(Def->getType()));
2142 if (
Instruction *Inst = dyn_cast<Instruction>(Def)) {
2143 if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {
2146 BasicBlock *NormalDest = Invoke->getNormalDest();
2149 assert(!Inst->isTerminator() &&
2150 "The only terminator that can produce a value is "
2151 "InvokeInst which is handled above.");
2152 Store->insertAfter(Inst);
2155 assert(isa<Argument>(Def));
2156 Store->insertAfter(cast<Instruction>(Alloca));
2160 assert(PromotableAllocas.
size() ==
Live.size() + NumRematerializedValues &&
2161 "we must have the same allocas with lives");
2162 (void) NumRematerializedValues;
2163 if (!PromotableAllocas.
empty()) {
2169 for (
auto &
I :
F.getEntryBlock())
2170 if (isa<AllocaInst>(
I))
2172 assert(InitialAllocaNum == 0 &&
"We must not introduce any extra allocas");
2192 Module *M = Call->getModule();
2196 if (isa<CallInst>(Call)) {
2204 auto *II = cast<InvokeInst>(Call);
2206 Func, Values,
"", &*II->getNormalDest()->getFirstInsertionPt()));
2208 Func, Values,
"", &*II->getUnwindDest()->getFirstInsertionPt()));
2215 GCPtrLivenessData OriginalLivenessData;
2217 for (
size_t i = 0; i < records.
size(); i++) {
2218 struct PartiallyConstructedSafepointRecord &
info = records[i];
2231 Value *CurrentValue) {
2235 GEP->getPointerOperand());
2238 if (
CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
2239 if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
2249 return CurrentValue;
2260 if (
CastInst *CI = dyn_cast<CastInst>(Instr)) {
2261 assert(CI->isNoopCast(CI->getModule()->getDataLayout()) &&
2262 "non noop cast is found during rematerialization");
2264 Type *SrcTy = CI->getOperand(0)->getType();
2271 Type *ValTy =
GEP->getSourceElementType();
2277 if (!
GEP->hasAllConstantIndices())
2296 for (
unsigned i = 0; i < PhiNum; i++)
2302 for (
unsigned i = 0; i < PhiNum; i++) {
2305 if (CIVI == CurrentIncomingValues.
end())
2307 BasicBlock *CurrentIncomingBB = CIVI->second;
2318 RematCandTy &RematerizationCandidates,
2320 const unsigned int ChainLengthThreshold = 10;
2322 for (
auto P2B : PointerToBase) {
2323 auto *Derived = P2B.first;
2324 auto *
Base = P2B.second;
2326 if (Derived ==
Base)
2331 Value *RootOfChain =
2335 if ( ChainToBase.
size() == 0 ||
2336 ChainToBase.
size() > ChainLengthThreshold)
2341 if (RootOfChain != PointerToBase[Derived]) {
2342 PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
2343 PHINode *AlternateRootPhi = dyn_cast<PHINode>(PointerToBase[Derived]);
2344 if (!OrigRootPhi || !AlternateRootPhi)
2366 RematerizlizationCandidateRecord
Record;
2367 Record.ChainToBase = ChainToBase;
2368 Record.RootOfChain = RootOfChain;
2370 RematerizationCandidates.insert({ Derived,
Record });
2379 RematCandTy &RematerizationCandidates,
2381 PointerToBaseTy &PointerToBase) {
2388 <<
"Num statepoints: " << Records.
size() <<
'\n');
2390 for (
auto &It : RematerizationCandidates) {
2392 auto &
Record = It.second;
2402 if (U->getParent() == Cand->
getParent())
2407 [](
const auto *U) { return isa<PHINode>(U); }))
2419 Records, [Cand](
const auto &R) {
return R.LiveSet.contains(Cand); });
2422 LLVM_DEBUG(
dbgs() <<
"Num uses: " << NumUses <<
" Num live statepoints: "
2423 << NumLiveStatepoints <<
" ");
2425 if (NumLiveStatepoints < NumUses) {
2433 if (NumLiveStatepoints == NumUses &&
Record.Cost > 0) {
2445 if (
Record.ChainToBase.size() > 1) {
2446 Record.ChainToBase.clear();
2462 Record.ChainToBase, UserI,
Record.RootOfChain, PointerToBase[Cand]);
2464 PointerToBase[RematChain] = PointerToBase[Cand];
2470 <<
" derived pointers\n");
2471 for (
auto *Cand : LiveValuesToBeDeleted) {
2472 assert(Cand->use_empty() &&
"Unexpected user remain");
2473 RematerizationCandidates.erase(Cand);
2474 for (
auto &R : Records) {
2475 assert(!R.LiveSet.contains(Cand) ||
2476 R.LiveSet.contains(PointerToBase[Cand]));
2477 R.LiveSet.remove(Cand);
2483 if (!LiveValuesToBeDeleted.
empty()) {
2484 for (
auto &
P : RematerizationCandidates) {
2486 if (R.ChainToBase.size() > 1) {
2487 R.ChainToBase.clear();
2499 PartiallyConstructedSafepointRecord &
Info,
2500 PointerToBaseTy &PointerToBase,
2501 RematCandTy &RematerizationCandidates,
2508 auto It = RematerizationCandidates.find(LiveValue);
2509 if (It == RematerizationCandidates.end())
2512 RematerizlizationCandidateRecord &
Record = It->second;
2517 if (isa<InvokeInst>(Call))
2525 LiveValuesToBeDeleted.
push_back(LiveValue);
2531 if (isa<CallInst>(Call)) {
2536 Record.RootOfChain, PointerToBase[LiveValue]);
2537 Info.RematerializedValues[RematerializedValue] = LiveValue;
2539 auto *Invoke = cast<InvokeInst>(Call);
2542 &*Invoke->getNormalDest()->getFirstInsertionPt();
2544 &*Invoke->getUnwindDest()->getFirstInsertionPt();
2548 Record.RootOfChain, PointerToBase[LiveValue]);
2551 Record.RootOfChain, PointerToBase[LiveValue]);
2553 Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
2554 Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
2559 for (
auto *LiveValue: LiveValuesToBeDeleted) {
2560 Info.LiveSet.remove(LiveValue);
2566 DefiningValueMapTy &DVCache,
2567 IsKnownBaseMapTy &KnownBases) {
2569 auto &
DL =
F.getParent()->getDataLayout();
2570 bool Changed =
false;
2572 for (
auto *Callsite : Intrinsics)
2573 switch (Callsite->getIntrinsicID()) {
2574 case Intrinsic::experimental_gc_get_pointer_base: {
2578 assert(!DVCache.count(Callsite));
2582 DVCache[BaseBC] =
Base;
2583 Callsite->replaceAllUsesWith(BaseBC);
2584 if (!BaseBC->hasName())
2585 BaseBC->takeName(Callsite);
2586 Callsite->eraseFromParent();
2589 case Intrinsic::experimental_gc_get_pointer_offset: {
2591 Value *Derived = Callsite->getOperand(0);
2593 assert(!DVCache.count(Callsite));
2604 Callsite->replaceAllUsesWith(
Offset);
2605 Offset->takeName(Callsite);
2606 Callsite->eraseFromParent();
2619 DefiningValueMapTy &DVCache,
2620 IsKnownBaseMapTy &KnownBases) {
2625 std::set<CallBase *> Uniqued;
2626 Uniqued.insert(ToUpdate.
begin(), ToUpdate.
end());
2627 assert(Uniqued.size() == ToUpdate.
size() &&
"no duplicates please!");
2630 assert(Call->getFunction() == &
F);
2638 auto *II = dyn_cast<InvokeInst>(Call);
2658 "support for FCA unimplemented");
2673 PointerToBaseTy PointerToBase;
2676 for (
size_t i = 0; i < Records.
size(); i++) {
2677 PartiallyConstructedSafepointRecord &
info = Records[i];
2681 errs() <<
"Base Pairs (w/o Relocation):\n";
2682 for (
auto &Pair : PointerToBase) {
2683 errs() <<
" derived ";
2684 Pair.first->printAsOperand(
errs(),
false);
2686 Pair.second->printAsOperand(
errs(),
false);
2706 for (
size_t i = 0; i < Records.
size(); i++) {
2707 PartiallyConstructedSafepointRecord &
Info = Records[i];
2710 for (
auto *Derived :
Info.LiveSet) {
2711 assert(PointerToBase.count(Derived) &&
"Missed base for derived pointer");
2712 Bases.
push_back(PointerToBase[Derived]);
2724 errs() <<
"Base Pairs: (w/Relocation)\n";
2725 for (
auto Pair : PointerToBase) {
2726 errs() <<
" derived ";
2727 Pair.first->printAsOperand(
errs(),
false);
2729 Pair.second->printAsOperand(
errs(),
false);
2742 for (
auto &
Info : Records) {
2743 Info.LiveSet.remove_if([&](
Value *LiveV) {
2744 assert(PointerToBase.count(LiveV) &&
"Missed base for derived pointer");
2745 return isa<Constant>(PointerToBase[LiveV]);
2750 CI->eraseFromParent();
2755 RematCandTy RematerizationCandidates;
2764 for (
size_t i = 0; i < Records.
size(); i++)
2766 RematerizationCandidates,
TTI);
2771 std::vector<DeferredReplacement> Replacements;
2779 for (
size_t i = 0; i < Records.
size(); i++)
2781 PointerToBase, GC.get());
2785 for (
auto &PR : Replacements)
2788 Replacements.clear();
2790 for (
auto &
Info : Records) {
2799 Info.LiveSet.clear();
2801 PointerToBase.clear();
2805 for (
const PartiallyConstructedSafepointRecord &
Info : Records) {
2818 "statepoint must be reachable or liveness is meaningless");
2819 for (
Value *V :
Info.StatepointToken->gc_args()) {
2820 if (!isa<Instruction>(V))
2823 auto *LiveInst = cast<Instruction>(V);
2825 "unreachable values should never be live");
2827 "basic SSA liveness expectation violated by liveness analysis");
2837 "must be a gc pointer type");
2841 return !Records.
empty();
2849 R.addAttribute(Attribute::Dereferenceable);
2850 R.addAttribute(Attribute::DereferenceableOrNull);
2851 R.addAttribute(Attribute::ReadNone);
2852 R.addAttribute(Attribute::ReadOnly);
2853 R.addAttribute(Attribute::WriteOnly);
2854 R.addAttribute(Attribute::NoAlias);
2855 R.addAttribute(Attribute::NoFree);
2874 if (isa<PointerType>(
A.getType()))
2875 F.removeParamAttrs(
A.getArgNo(), R);
2877 if (isa<PointerType>(
F.getReturnType()))
2878 F.removeRetAttrs(R);
2881 F.removeFnAttr(Attr);
2888 if (!isa<LoadInst>(
I) && !isa<StoreInst>(
I))
2903 unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,
2904 LLVMContext::MD_range,
2905 LLVMContext::MD_alias_scope,
2906 LLVMContext::MD_nontemporal,
2907 LLVMContext::MD_nonnull,
2908 LLVMContext::MD_align,
2909 LLVMContext::MD_type};
2912 I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);
2933 if (
auto *II = dyn_cast<IntrinsicInst>(&
I))
2934 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
2935 InvariantStartInstructions.
push_back(II);
2939 if (
MDNode *
Tag =
I.getMetadata(LLVMContext::MD_tbaa)) {
2941 I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
2947 if (
auto *Call = dyn_cast<CallBase>(&
I)) {
2948 for (
int i = 0, e = Call->arg_size(); i != e; i++)
2949 if (isa<PointerType>(Call->getArgOperand(i)->getType()))
2950 Call->removeParamAttrs(i, R);
2951 if (isa<PointerType>(Call->getType()))
2952 Call->removeRetAttrs(R);
2957 for (
auto *II : InvariantStartInstructions) {
2959 II->eraseFromParent();
2980 assert(Strategy &&
"GC strategy is required by function, but was not found");
2982 return Strategy->useRS4GC();
3000 assert(!
F.isDeclaration() && !
F.empty() &&
3001 "need function body to rewrite statepoints in");
3005 if (
const auto *Call = dyn_cast<CallBase>(&
I)) {
3006 if (isa<GCStatepointInst>(Call))
3020 assert((isa<AtomicMemCpyInst>(Call) || isa<AtomicMemMoveInst>(Call)) &&
3021 "Don't expect any other calls here!");
3044 if (NeedsRewrite(
I)) {
3050 "no unreachable blocks expected");
3051 ParsePointNeeded.
push_back(cast<CallBase>(&
I));
3053 if (
auto *CI = dyn_cast<CallInst>(&
I))
3054 if (CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_base ||
3055 CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_offset)
3060 if (ParsePointNeeded.
empty() && Intrinsics.
empty())
3068 if (BB.getUniquePredecessor())
3085 if (
auto *BI = dyn_cast<BranchInst>(TI))
3086 if (BI->isConditional())
3087 return dyn_cast<Instruction>(BI->getCondition());
3093 if (
auto *
Cond = getConditionInst(TI))
3096 if (isa<ICmpInst>(
Cond) &&
Cond->hasOneUse()) {
3098 Cond->moveBefore(TI);
3108 if (!isa<GetElementPtrInst>(
I))
3112 for (
unsigned i = 0; i <
I.getNumOperands(); i++)
3113 if (
auto *OpndVTy = dyn_cast<VectorType>(
I.getOperand(i)->getType())) {
3115 VF == cast<FixedVectorType>(OpndVTy)->getNumElements());
3116 VF = cast<FixedVectorType>(OpndVTy)->getNumElements();
3121 if (!
I.getOperand(0)->getType()->isVectorTy() && VF != 0) {
3123 auto *
Splat =
B.CreateVectorSplat(VF,
I.getOperand(0));
3133 DefiningValueMapTy DVCache;
3137 IsKnownBaseMapTy KnownBases;
3139 if (!Intrinsics.
empty())
3144 if (!ParsePointNeeded.
empty())
3168 if (isa<PHINode>(
I))
3172 for (
Value *V :
I.operands()) {
3174 "support for FCA unimplemented");
3195 for (
auto &
I : *Succ) {
3196 PHINode *PN = dyn_cast<PHINode>(&
I);
3202 "support for FCA unimplemented");
3223 if (
auto *
I = dyn_cast<Instruction>(V)) {
3227 if (TermOkay && TI ==
I)
3230 "basic SSA liveness expectation violated by liveness analysis");
3253 Data.LiveSet[&BB].clear();
3258 assert(!
Data.LiveSet[&BB].count(Kill) &&
"live set contains kill");
3263 Data.LiveIn[&BB] =
Data.LiveSet[&BB];
3264 Data.LiveIn[&BB].set_union(
Data.LiveOut[&BB]);
3265 Data.LiveIn[&BB].set_subtract(
Data.KillSet[&BB]);
3266 if (!
Data.LiveIn[&BB].empty())
3271 while (!Worklist.
empty()) {
3277 const auto OldLiveOutSize = LiveOut.
size();
3283 if (OldLiveOutSize == LiveOut.
size()) {
3289 Data.LiveOut[BB] = LiveOut;
3299 if (OldLiveIn.
size() != LiveTmp.
size()) {
3300 Data.LiveIn[BB] = LiveTmp;
3328 Out.insert(LiveOut.
begin(), LiveOut.
end());
3333 PartiallyConstructedSafepointRecord &
Info,
3334 PointerToBaseTy &PointerToBase,
3336 StatepointLiveSetTy Updated;
3341 for (
auto *V : Updated)
3342 PointerToBase.insert({ V, V });
3344 Info.LiveSet = Updated;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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...
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
Select target instructions out of generic instructions
This file implements a map that provides insertion order iteration.
Module.h This file contains the declarations for the Module class.
FunctionAnalysisManager FAM
const SmallVectorImpl< MachineOperand > & Cond
static void makeStatepointExplicitImpl(CallBase *Call, const SmallVectorImpl< Value * > &BasePtrs, const SmallVectorImpl< Value * > &LiveVariables, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC)
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.
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.
This class represents an Operation in the Expression.
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.
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...
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)
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...
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 PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
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.
A vector that has set insertion semantics.
bool remove(const value_type &X)
Remove an item from the set vector.
size_type size() const
Determine the number of elements in the SetVector.
bool set_union(const STy &S)
Compute This := This u S, return whether 'This' changed.
iterator end()
Get an iterator to the end of the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
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....
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
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)
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.
@ 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.
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...
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
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.
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.
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