79 #define DEBUG_TYPE "rewrite-statepoints-for-gc"
99 #ifdef EXPENSIVE_CHECKS
130 bool Changed =
false;
134 if (
F.isDeclaration() ||
F.empty())
163 class RewriteStatepointsForGCLegacyPass :
public ModulePass {
169 RewriteStatepointsForGCLegacyPass() :
ModulePass(
ID), Impl() {
174 bool runOnModule(
Module &M)
override {
175 bool Changed =
false;
178 if (
F.isDeclaration() ||
F.empty())
187 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
189 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
190 auto &DT = getAnalysis<DominatorTreeWrapperPass>(
F).getDomTree();
219 return new RewriteStatepointsForGCLegacyPass();
223 "rewrite-statepoints-for-gc",
224 "Make relocations explicit at statepoints",
false,
false)
294 "Found non-leaf call without deopt info!");
303 GCPtrLivenessData &
Data);
314 if (
auto *PT = dyn_cast<PointerType>(
T))
318 return PT->getAddressSpace() == 1;
332 if (
auto VT = dyn_cast<VectorType>(
T))
344 if (
VectorType *VT = dyn_cast<VectorType>(Ty))
346 if (
ArrayType *AT = dyn_cast<ArrayType>(Ty))
374 PartiallyConstructedSafepointRecord &Result) {
379 dbgs() <<
"Live Variables:\n";
380 for (
Value *V : LiveSet)
381 dbgs() <<
" " << V->getName() <<
" " << *V <<
"\n";
384 dbgs() <<
"Safepoint For: " << Call->getCalledOperand()->getName() <<
"\n";
385 dbgs() <<
"Number live values: " << LiveSet.size() <<
"\n";
387 Result.LiveSet = LiveSet;
407 struct BaseDefiningValueResult {
413 const bool IsKnownBase;
415 BaseDefiningValueResult(
Value *BDV,
bool IsKnownBase)
416 : BDV(BDV), IsKnownBase(IsKnownBase) {
421 assert(!MustBeBase || MustBeBase == IsKnownBase);
439 static BaseDefiningValueResult
444 if (isa<Argument>(
I))
446 return BaseDefiningValueResult(
I,
true);
448 if (isa<Constant>(
I))
454 if (isa<LoadInst>(
I))
455 return BaseDefiningValueResult(
I,
true);
457 if (isa<InsertElementInst>(
I))
461 return BaseDefiningValueResult(
I,
false);
463 if (isa<ShuffleVectorInst>(
I))
469 return BaseDefiningValueResult(
I,
false);
473 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
I))
478 if (
auto *BC = dyn_cast<BitCastInst>(
I))
484 if (isa<CallInst>(
I) || isa<InvokeInst>(
I))
485 return BaseDefiningValueResult(
I,
true);
489 assert((isa<SelectInst>(
I) || isa<PHINode>(
I)) &&
490 "unknown vector instruction - no base found for vector element");
491 return BaseDefiningValueResult(
I,
false);
499 assert(
I->getType()->isPtrOrPtrVectorTy() &&
500 "Illegal to ask for the base pointer of a non-pointer type");
502 if (
I->getType()->isVectorTy())
505 if (isa<Argument>(
I))
508 return BaseDefiningValueResult(
I,
true);
510 if (isa<Constant>(
I)) {
521 return BaseDefiningValueResult(
525 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
526 Value *
Def = CI->stripPointerCasts();
529 assert(cast<PointerType>(
Def->getType())->getAddressSpace() ==
530 cast<PointerType>(CI->getType())->getAddressSpace() &&
531 "unsupported addrspacecast");
535 assert(!isa<CastInst>(
Def) &&
"shouldn't find another cast here");
539 if (isa<LoadInst>(
I))
541 return BaseDefiningValueResult(
I,
true);
548 switch (II->getIntrinsicID()) {
552 case Intrinsic::experimental_gc_statepoint:
554 case Intrinsic::experimental_gc_relocate:
559 case Intrinsic::gcroot:
564 "interaction with the gcroot mechanism is not supported");
570 if (isa<CallInst>(
I) || isa<InvokeInst>(
I))
571 return BaseDefiningValueResult(
I,
true);
575 assert(!isa<LandingPadInst>(
I) &&
"Landing Pad is unimplemented");
577 if (isa<AtomicCmpXchgInst>(
I))
581 return BaseDefiningValueResult(
I,
true);
583 assert(!isa<AtomicRMWInst>(
I) &&
"Xchg handled above, all others are "
584 "binary ops which don't apply to pointers");
589 if (isa<ExtractValueInst>(
I))
590 return BaseDefiningValueResult(
I,
true);
594 assert(!isa<InsertValueInst>(
I) &&
595 "Base pointer for a struct is meaningless");
601 if (isa<ExtractElementInst>(
I))
605 return BaseDefiningValueResult(
I,
false);
611 assert((isa<SelectInst>(
I) || isa<PHINode>(
I)) &&
612 "missing instruction case in findBaseDefiningValing");
613 return BaseDefiningValueResult(
I,
false);
618 Value *&Cached = Cache[
I];
632 auto Found = Cache.find(
Def);
633 if (Found != Cache.end()) {
635 return Found->second;
645 return !isa<PHINode>(V) && !isa<SelectInst>(V) &&
646 !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&
647 !isa<ShuffleVectorInst>(V);
655 if (isa<Instruction>(V) &&
656 cast<Instruction>(V)->getMetadata(
"is_base_value")) {
668 return isa<VectorType>(
First->getType()) ==
669 isa<VectorType>(Second->
getType());
694 explicit BDVState(
Value *OriginalValue)
695 : OriginalValue(OriginalValue) {}
696 explicit BDVState(
Value *OriginalValue, StatusTy
Status,
Value *BaseValue =
nullptr)
697 : OriginalValue(OriginalValue),
Status(
Status), BaseValue(BaseValue) {
701 StatusTy getStatus()
const {
return Status; }
702 Value *getOriginalValue()
const {
return OriginalValue; }
703 Value *getBaseValue()
const {
return BaseValue; }
705 bool isBase()
const {
return getStatus() == Base; }
706 bool isUnknown()
const {
return getStatus() ==
Unknown; }
707 bool isConflict()
const {
return getStatus() == Conflict; }
712 void meet(
const BDVState &Other) {
713 auto markConflict = [&]() {
714 Status = BDVState::Conflict;
723 BaseValue =
Other.getBaseValue();
727 assert(isBase() &&
"Unknown state");
729 if (
Other.isUnknown())
732 if (
Other.isConflict())
733 return markConflict();
737 if (getBaseValue() !=
Other.getBaseValue())
738 return markConflict();
742 bool operator==(
const BDVState &Other)
const {
743 return OriginalValue == OriginalValue && BaseValue ==
Other.BaseValue &&
747 bool operator!=(
const BDVState &other)
const {
return !(*
this == other); }
756 switch (getStatus()) {
767 OS <<
" (base " << getBaseValue() <<
" - "
768 << (getBaseValue() ? getBaseValue()->getName() :
"nullptr") <<
")"
769 <<
" for " << OriginalValue->getName() <<
":";
820 auto isExpectedBDVType = [](
Value *BDV) {
821 return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||
822 isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||
823 isa<ShuffleVectorInst>(BDV);
835 auto VerifyStates = [&]() {
836 for (
auto &Entry : States) {
837 assert(Entry.first == Entry.second.getOriginalValue());
843 if (
PHINode *PN = dyn_cast<PHINode>(BDV)) {
844 for (
Value *InVal : PN->incoming_values())
846 }
else if (
SelectInst *
SI = dyn_cast<SelectInst>(BDV)) {
847 F(
SI->getTrueValue());
848 F(
SI->getFalseValue());
849 }
else if (
auto *EE = dyn_cast<ExtractElementInst>(BDV)) {
850 F(EE->getVectorOperand());
851 }
else if (
auto *
IE = dyn_cast<InsertElementInst>(BDV)) {
852 F(
IE->getOperand(0));
853 F(
IE->getOperand(1));
854 }
else if (
auto *SV = dyn_cast<ShuffleVectorInst>(BDV)) {
857 F(SV->getOperand(0));
858 if (!SV->isZeroEltSplat())
859 F(SV->getOperand(1));
870 Worklist.push_back(
Def);
872 while (!Worklist.empty()) {
876 auto visitIncomingValue = [&](
Value *InVal) {
885 assert(isExpectedBDVType(Base) &&
"the only non-base values "
886 "we see should be base defining values");
887 if (States.
insert(std::make_pair(Base, BDVState(Base))).second)
888 Worklist.push_back(Base);
891 visitBDVOperands(Current, visitIncomingValue);
898 for (
auto Pair : States) {
899 LLVM_DEBUG(
dbgs() <<
" " << Pair.second <<
" for " << *Pair.first <<
"\n");
911 for (
auto Pair : States) {
912 Value *BDV = Pair.first;
913 auto canPruneInput = [&](
Value *V) {
915 if (V->stripPointerCasts() != BDV)
919 return States.count(BDV) == 0;
922 bool CanPrune =
true;
923 visitBDVOperands(BDV, [&](
Value *
Op) {
924 CanPrune = CanPrune && canPruneInput(
Op);
937 if (!States.count(
Def))
942 auto GetStateForBDV = [&](
Value *BaseValue,
Value *Input) {
943 auto I = States.find(BaseValue);
944 if (
I != States.end())
947 return BDVState(BaseValue, BDVState::Base, BaseValue);
950 bool Progress =
true;
953 const size_t OldSize = States.size();
960 for (
auto Pair : States) {
961 Value *BDV = Pair.first;
967 "why did it get added?");
969 BDVState NewState(BDV);
970 visitBDVOperands(BDV, [&](
Value *
Op) {
972 auto OpState = GetStateForBDV(BDV,
Op);
973 NewState.meet(OpState);
976 BDVState OldState = States[BDV];
977 if (OldState != NewState) {
979 States[BDV] = NewState;
983 assert(OldSize == States.size() &&
984 "fixed point shouldn't be adding any new nodes to state");
990 for (
auto Pair : States) {
991 LLVM_DEBUG(
dbgs() <<
" " << Pair.second <<
" for " << *Pair.first <<
"\n");
997 for (
auto Pair : States) {
999 BDVState State = Pair.second;
1000 auto *BaseValue = State.getBaseValue();
1005 "why did it get added?");
1006 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1008 if (!State.isBase() || !isa<VectorType>(BaseValue->
getType()))
1014 if (isa<ExtractElementInst>(
I)) {
1015 auto *EE = cast<ExtractElementInst>(
I);
1020 State.getBaseValue(), EE->getIndexOperand(),
"base_ee", EE);
1021 BaseInst->setMetadata(
"is_base_value",
MDNode::get(
I->getContext(), {}));
1022 States[
I] = BDVState(
I, BDVState::Base, BaseInst);
1023 }
else if (!isa<VectorType>(
I->getType())) {
1029 States[
I] = BDVState(
I, BDVState::Conflict);
1039 for (
auto Pair : States) {
1041 BDVState State = Pair.second;
1046 "why did it get added?");
1047 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1052 assert(!isa<InsertElementInst>(
I) || State.isConflict());
1054 if (!State.isConflict())
1057 auto getMangledName = [](
Instruction *
I) -> std::string {
1058 if (isa<PHINode>(
I)) {
1060 }
else if (isa<SelectInst>(
I)) {
1062 }
else if (isa<ExtractElementInst>(
I)) {
1064 }
else if (isa<InsertElementInst>(
I)) {
1073 BaseInst->
setName(getMangledName(
I));
1076 States[
I] = BDVState(
I, BDVState::Conflict, BaseInst);
1093 Value *Base =
nullptr;
1094 if (!States.count(BDV)) {
1099 assert(States.count(BDV));
1100 Base = States[BDV].getBaseValue();
1102 assert(Base &&
"Can't be null");
1112 for (
auto Pair : States) {
1114 BDVState State = Pair.second;
1121 "why did it get added?");
1122 assert(!State.isUnknown() &&
"Optimistic algorithm didn't complete!");
1123 if (!State.isConflict())
1126 if (
PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {
1127 PHINode *PN = cast<PHINode>(BDV);
1135 for (
unsigned i = 0;
i < NumPHIValues;
i++) {
1138 if (!BlockToValue.
count(InBB))
1139 BlockToValue[InBB] = getBaseForInput(InVal, InBB->
getTerminator());
1142 Value *OldBase = BlockToValue[InBB];
1143 Value *Base = getBaseForInput(InVal,
nullptr);
1151 "Sanity -- findBaseOrBDV should be pure!");
1154 Value *Base = BlockToValue[InBB];
1155 BasePHI->setIncomingValue(
i, Base);
1158 dyn_cast<SelectInst>(State.getBaseValue())) {
1163 BaseSI->setTrueValue(getBaseForInput(
SI->getTrueValue(), BaseSI));
1164 BaseSI->setFalseValue(getBaseForInput(
SI->getFalseValue(), BaseSI));
1165 }
else if (
auto *BaseEE =
1166 dyn_cast<ExtractElementInst>(State.getBaseValue())) {
1167 Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();
1170 BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));
1171 }
else if (
auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){
1172 auto *BdvIE = cast<InsertElementInst>(BDV);
1173 auto UpdateOperand = [&](
int OperandIdx) {
1174 Value *InVal = BdvIE->getOperand(OperandIdx);
1175 Value *Base = getBaseForInput(InVal, BaseIE);
1176 BaseIE->setOperand(OperandIdx, Base);
1181 auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());
1182 auto *BdvSV = cast<ShuffleVectorInst>(BDV);
1183 auto UpdateOperand = [&](
int OperandIdx) {
1184 Value *InVal = BdvSV->getOperand(OperandIdx);
1185 Value *Base = getBaseForInput(InVal, BaseSV);
1186 BaseSV->setOperand(OperandIdx, Base);
1189 if (!BdvSV->isZeroEltSplat())
1193 Value *InVal = BdvSV->getOperand(1);
1206 for (
auto Pair : States) {
1207 auto *BDV = Pair.first;
1208 Value *Base = Pair.second.getBaseValue();
1214 "why did it get added?");
1217 dbgs() <<
"Updating base value cache"
1218 <<
" for: " << BDV->
getName() <<
" from: "
1219 << (Cache.count(BDV) ? Cache[BDV]->getName().str() :
"none")
1220 <<
" to: " << Base->
getName() <<
"\n");
1247 for (
Value *ptr : live) {
1249 assert(
base &&
"failed to find base pointer");
1250 PointerToBase[ptr] =
base;
1251 assert((!isa<Instruction>(
base) || !isa<Instruction>(ptr) ||
1253 cast<Instruction>(ptr)->getParent())) &&
1254 "The base we found better dominate the derived pointer");
1262 PartiallyConstructedSafepointRecord &
result) {
1271 for (
Value *V : Opt->Inputs) {
1272 if (!PotentiallyDerivedPointers.count(V))
1274 PotentiallyDerivedPointers.remove(V);
1275 PointerToBase[V] = V;
1280 errs() <<
"Base Pairs (w/o Relocation):\n";
1281 for (
auto &Pair : PointerToBase) {
1282 errs() <<
" derived ";
1283 Pair.first->printAsOperand(
errs(),
false);
1285 Pair.second->printAsOperand(
errs(),
false);
1290 result.PointerToBase = PointerToBase;
1297 PartiallyConstructedSafepointRecord &
result);
1304 GCPtrLivenessData RevisedLivenessData;
1306 for (
size_t i = 0;
i < records.
size();
i++) {
1307 struct PartiallyConstructedSafepointRecord &
info = records[
i];
1322 if (!
BB->getUniquePredecessor())
1329 "All PHI nodes should have been removed!");
1346 Attribute::NoSync, Attribute::NoFree})
1376 assert(ValIt != LiveVec.
end() &&
"Val not found in LiveVec!");
1377 size_t Index = std::distance(LiveVec.
begin(), ValIt);
1390 auto getGCRelocateDecl = [&] (
Type *Ty) {
1392 auto AS = Ty->getScalarType()->getPointerAddressSpace();
1394 if (
auto *VT = dyn_cast<VectorType>(Ty))
1396 cast<FixedVectorType>(VT)->getNumElements());
1412 if (!TypeToDeclMap.
count(Ty))
1413 TypeToDeclMap[Ty] = getGCRelocateDecl(Ty);
1414 Function *GCRelocateDecl = TypeToDeclMap[Ty];
1418 GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},
1430 class DeferredReplacement {
1433 bool IsDeoptimize =
false;
1435 DeferredReplacement() =
default;
1439 assert(Old != New && Old && New &&
1440 "Cannot RAUW equal values or to / from null!");
1442 DeferredReplacement
D;
1448 static DeferredReplacement createDelete(
Instruction *ToErase) {
1449 DeferredReplacement
D;
1454 static DeferredReplacement createDeoptimizeReplacement(
Instruction *Old) {
1456 auto *
F = cast<CallInst>(Old)->getCalledFunction();
1457 assert(
F &&
F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&
1458 "Only way to construct a deoptimize deferred replacement");
1460 DeferredReplacement
D;
1462 D.IsDeoptimize =
true;
1467 void doReplacement() {
1471 assert(OldI != NewI &&
"Disallowed at construction?!");
1472 assert((!IsDeoptimize || !New) &&
1473 "Deoptimize intrinsics are not replaced!");
1486 RI->eraseFromParent();
1496 const char *DeoptLowering =
"deopt-lowering";
1497 if (Call->hasFnAttr(DeoptLowering)) {
1504 Function *
F = Call->getCalledFunction();
1505 assert(
F &&
F->hasFnAttribute(DeoptLowering));
1506 return F->getFnAttribute(DeoptLowering).getValueAsString();
1508 return "live-through";
1515 PartiallyConstructedSafepointRecord &Result,
1516 std::vector<DeferredReplacement> &Replacements) {
1533 DeoptArgs = Bundle->Inputs;
1536 TransitionArgs = Bundle->Inputs;
1544 bool IsDeoptimize =
false;
1555 if (DeoptLowering.
equals(
"live-in"))
1558 assert(DeoptLowering.
equals(
"live-through") &&
"Unsupported value!");
1561 Value *CallTarget = Call->getCalledOperand();
1562 if (
Function *
F = dyn_cast<Function>(CallTarget)) {
1563 auto IID =
F->getIntrinsicID();
1564 if (IID == Intrinsic::experimental_deoptimize) {
1571 DomainTy.push_back(
Arg->getType());
1579 CallTarget =
F->getParent()
1580 ->getOrInsertFunction(
"__llvm_deoptimize", FTy)
1583 IsDeoptimize =
true;
1584 }
else if (IID == Intrinsic::memcpy_element_unordered_atomic ||
1585 IID == Intrinsic::memmove_element_unordered_atomic) {
1602 auto &
Context = Call->getContext();
1603 auto &
DL = Call->getModule()->getDataLayout();
1604 auto GetBaseAndOffset = [&](
Value *Derived) {
1605 assert(Result.PointerToBase.count(Derived));
1606 unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
1608 Value *Base = Result.PointerToBase.find(Derived)->second;
1613 return std::make_pair(Base,
Builder.CreateSub(Derived_int, Base_int));
1616 auto *Dest = CallArgs[0];
1617 Value *DestBase, *DestOffset;
1618 std::tie(DestBase, DestOffset) = GetBaseAndOffset(Dest);
1620 auto *
Source = CallArgs[1];
1621 Value *SourceBase, *SourceOffset;
1622 std::tie(SourceBase, SourceOffset) = GetBaseAndOffset(
Source);
1624 auto *LengthInBytes = CallArgs[2];
1625 auto *ElementSizeCI = cast<ConstantInt>(CallArgs[3]);
1628 CallArgs.push_back(DestBase);
1629 CallArgs.push_back(DestOffset);
1630 CallArgs.push_back(SourceBase);
1631 CallArgs.push_back(SourceOffset);
1632 CallArgs.push_back(LengthInBytes);
1636 DomainTy.push_back(
Arg->getType());
1641 uint64_t ElementSize = ElementSizeCI->getZExtValue();
1642 if (IID == Intrinsic::memcpy_element_unordered_atomic) {
1643 switch (ElementSize) {
1645 return "__llvm_memcpy_element_unordered_atomic_safepoint_1";
1647 return "__llvm_memcpy_element_unordered_atomic_safepoint_2";
1649 return "__llvm_memcpy_element_unordered_atomic_safepoint_4";
1651 return "__llvm_memcpy_element_unordered_atomic_safepoint_8";
1653 return "__llvm_memcpy_element_unordered_atomic_safepoint_16";
1658 assert(IID == Intrinsic::memmove_element_unordered_atomic);
1659 switch (ElementSize) {
1661 return "__llvm_memmove_element_unordered_atomic_safepoint_1";
1663 return "__llvm_memmove_element_unordered_atomic_safepoint_2";
1665 return "__llvm_memmove_element_unordered_atomic_safepoint_4";
1667 return "__llvm_memmove_element_unordered_atomic_safepoint_8";
1669 return "__llvm_memmove_element_unordered_atomic_safepoint_16";
1677 ->getOrInsertFunction(GetFunctionName(IID, ElementSizeCI), FTy)
1684 if (
auto *CI = dyn_cast<CallInst>(Call)) {
1686 StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
1687 TransitionArgs, DeoptArgs, GCArgs,
"safepoint_token");
1699 Token = cast<GCStatepointInst>(SPCall);
1703 assert(CI->getNextNode() &&
"Not a terminator, must have next!");
1704 Builder.SetInsertPoint(CI->getNextNode());
1705 Builder.SetCurrentDebugLocation(CI->getNextNode()->getDebugLoc());
1707 auto *II = cast<InvokeInst>(Call);
1713 StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(),
1714 II->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs, GCArgs,
1715 "statepoint_token");
1726 Token = cast<GCStatepointInst>(SPInvoke);
1729 BasicBlock *UnwindBlock = II->getUnwindDest();
1732 "can't safely insert in this block!");
1735 Builder.SetCurrentDebugLocation(II->getDebugLoc());
1739 Result.UnwindToken = ExceptionalToken;
1744 BasicBlock *NormalDest = II->getNormalDest();
1747 "can't safely insert in this block!");
1754 assert(Token &&
"Should be set in one of the above branches!");
1760 Replacements.push_back(
1761 DeferredReplacement::createDeoptimizeReplacement(Call));
1763 Token->
setName(
"statepoint_token");
1764 if (!Call->getType()->isVoidTy() && !Call->use_empty()) {
1769 Call->getAttributes().getRetAttributes()));
1777 Replacements.emplace_back(
1778 DeferredReplacement::createRAUW(Call, GCResult));
1780 Replacements.emplace_back(DeferredReplacement::createDelete(Call));
1784 Result.StatepointToken = Token;
1797 PartiallyConstructedSafepointRecord &Result,
1798 std::vector<DeferredReplacement> &Replacements) {
1799 const auto &LiveSet = Result.LiveSet;
1800 const auto &PointerToBase = Result.PointerToBase;
1804 LiveVec.
reserve(LiveSet.size());
1805 BaseVec.
reserve(LiveSet.size());
1806 for (
Value *L : LiveSet) {
1807 LiveVec.push_back(L);
1808 assert(PointerToBase.count(L));
1809 Value *Base = PointerToBase.find(L)->second;
1810 BaseVec.push_back(Base);
1812 assert(LiveVec.size() == BaseVec.size());
1828 for (
User *U : GCRelocs) {
1835 Value *Alloca = AllocaMap[OriginalValue];
1841 "Should always have one since it's not a terminator");
1843 Value *CastedRelocatedValue =
1844 Builder.CreateBitCast(Relocate,
1845 cast<AllocaInst>(Alloca)->getAllocatedType(),
1848 new StoreInst(CastedRelocatedValue, Alloca,
1849 cast<Instruction>(CastedRelocatedValue)->getNextNode());
1852 VisitedLiveValues.
insert(OriginalValue);
1863 for (
auto RematerializedValuePair: RematerializedValues) {
1864 Instruction *RematerializedValue = RematerializedValuePair.first;
1865 Value *OriginalValue = RematerializedValuePair.second;
1868 "Can not find alloca for rematerialized value");
1869 Value *Alloca = AllocaMap[OriginalValue];
1871 new StoreInst(RematerializedValue, Alloca,
1875 VisitedLiveValues.
insert(OriginalValue);
1887 int InitialAllocaNum = 0;
1889 if (isa<AllocaInst>(
I))
1897 std::size_t NumRematerializedValues = 0;
1903 auto emitAllocaFor = [&](
Value *LiveValue) {
1905 DL.getAllocaAddrSpace(),
"",
1906 F.getEntryBlock().getFirstNonPHI());
1907 AllocaMap[LiveValue] = Alloca;
1908 PromotableAllocas.push_back(Alloca);
1912 for (
Value *V : Live)
1916 for (
const auto &
Info : Records)
1917 for (
auto RematerializedValuePair :
Info.RematerializedValues) {
1918 Value *OriginalValue = RematerializedValuePair.second;
1919 if (AllocaMap.
count(OriginalValue) != 0)
1922 emitAllocaFor(OriginalValue);
1923 ++NumRematerializedValues;
1935 for (
const auto &
Info : Records) {
1936 Value *Statepoint =
Info.StatepointToken;
1946 if (isa<InvokeInst>(Statepoint)) {
1962 for (
auto Pair : AllocaMap) {
1967 if (VisitedLiveValues.
count(
Def)) {
1970 ToClobber.push_back(Alloca);
1974 for (
auto *AI : ToClobber) {
1975 auto PT = cast<PointerType>(AI->getAllocatedType());
1983 if (
auto II = dyn_cast<InvokeInst>(Statepoint)) {
1984 InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt());
1985 InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt());
1987 InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode());
1993 for (
auto Pair : AllocaMap) {
2002 Uses.reserve(
Def->getNumUses());
2003 for (
User *U :
Def->users()) {
2004 if (!isa<ConstantExpr>(U)) {
2010 Uses.push_back(cast<Instruction>(U));
2015 auto Last = std::unique(
Uses.begin(),
Uses.end());
2019 if (isa<PHINode>(
Use)) {
2040 DL.getABITypeAlign(
Def->getType()));
2042 if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {
2045 BasicBlock *NormalDest = Invoke->getNormalDest();
2048 assert(!Inst->isTerminator() &&
2049 "The only terminator that can produce a value is "
2050 "InvokeInst which is handled above.");
2051 Store->insertAfter(Inst);
2055 Store->insertAfter(cast<Instruction>(Alloca));
2059 assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&
2060 "we must have the same allocas with lives");
2061 if (!PromotableAllocas.empty()) {
2067 for (
auto &
I :
F.getEntryBlock())
2068 if (isa<AllocaInst>(
I))
2070 assert(InitialAllocaNum == 0 &&
"We must not introduce any extra allocas");
2090 Module *
M = Call->getModule();
2094 if (isa<CallInst>(Call)) {
2102 auto *II = cast<InvokeInst>(Call);
2104 Func, Values,
"", &*II->getNormalDest()->getFirstInsertionPt()));
2106 Func, Values,
"", &*II->getUnwindDest()->getFirstInsertionPt()));
2112 GCPtrLivenessData OriginalLivenessData;
2114 for (
size_t i = 0;
i < records.
size();
i++) {
2115 struct PartiallyConstructedSafepointRecord &
info = records[
i];
2128 Value *CurrentValue) {
2130 ChainToBase.push_back(
GEP);
2132 GEP->getPointerOperand());
2135 if (
CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
2136 if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
2139 ChainToBase.push_back(CI);
2146 return CurrentValue;
2157 if (
CastInst *CI = dyn_cast<CastInst>(Instr)) {
2158 assert(CI->isNoopCast(CI->getModule()->getDataLayout()) &&
2159 "non noop cast is found during rematerialization");
2161 Type *SrcTy = CI->getOperand(0)->getType();
2168 Type *ValTy =
GEP->getSourceElementType();
2174 if (!
GEP->hasAllConstantIndices())
2193 for (
unsigned i = 0;
i < PhiNum;
i++)
2199 for (
unsigned i = 0;
i < PhiNum;
i++) {
2202 if (CIVI == CurrentIncomingValues.
end())
2204 BasicBlock *CurrentIncomingBB = CIVI->second;
2216 PartiallyConstructedSafepointRecord &
Info,
2218 const unsigned int ChainLengthThreshold = 10;
2228 Value *RootOfChain =
2233 if ( ChainToBase.size() == 0 ||
2234 ChainToBase.size() > ChainLengthThreshold)
2239 if (RootOfChain !=
Info.PointerToBase[LiveValue]) {
2240 PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
2241 PHINode *AlternateRootPhi = dyn_cast<PHINode>(
Info.PointerToBase[LiveValue]);
2242 if (!OrigRootPhi || !AlternateRootPhi)
2258 assert(
Info.LiveSet.count(AlternateRootPhi));
2269 if (isa<InvokeInst>(
Call)) {
2277 LiveValuesToBeDeleted.push_back(LiveValue);
2287 auto rematerializeChain = [&ChainToBase](
2296 assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
2300 ClonedValue->
setName(Instr->getName() +
".remat");
2304 if (LastClonedValue) {
2312 "incorrect use in rematerialization chain");
2315 assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);
2324 if (RootOfChain != AlternateLiveBase)
2328 LastClonedValue = ClonedValue;
2332 return LastClonedValue;
2337 if (isa<CallInst>(
Call)) {
2340 Instruction *RematerializedValue = rematerializeChain(
2341 InsertBefore, RootOfChain,
Info.PointerToBase[LiveValue]);
2342 Info.RematerializedValues[RematerializedValue] = LiveValue;
2344 auto *Invoke = cast<InvokeInst>(
Call);
2347 &*Invoke->getNormalDest()->getFirstInsertionPt();
2349 &*Invoke->getUnwindDest()->getFirstInsertionPt();
2351 Instruction *NormalRematerializedValue = rematerializeChain(
2352 NormalInsertBefore, RootOfChain,
Info.PointerToBase[LiveValue]);
2353 Instruction *UnwindRematerializedValue = rematerializeChain(
2354 UnwindInsertBefore, RootOfChain,
Info.PointerToBase[LiveValue]);
2356 Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
2357 Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
2362 for (
auto LiveValue: LiveValuesToBeDeleted) {
2363 Info.LiveSet.remove(LiveValue);
2372 std::set<CallBase *> Uniqued;
2373 Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
2374 assert(Uniqued.size() == ToUpdate.size() &&
"no duplicates please!");
2385 auto *II = dyn_cast<InvokeInst>(
Call);
2405 "support for FCA unimplemented");
2407 DeoptValues.push_back(
Arg);
2426 for (
size_t i = 0;
i < Records.size();
i++) {
2427 PartiallyConstructedSafepointRecord &
info = Records[
i];
2445 Holders.
reserve(Holders.size() + Records.size());
2446 for (
size_t i = 0;
i < Records.size();
i++) {
2447 PartiallyConstructedSafepointRecord &
Info = Records[
i];
2450 for (
auto Pair :
Info.PointerToBase)
2451 Bases.push_back(Pair.second);
2462 for (
auto &
Info : Records) {
2463 errs() <<
"Base Pairs: (w/Relocation)\n";
2464 for (
auto Pair :
Info.PointerToBase) {
2465 errs() <<
" derived ";
2466 Pair.first->printAsOperand(
errs(),
false);
2468 Pair.second->printAsOperand(
errs(),
false);
2482 for (
auto &
Info : Records)
2483 for (
auto &BasePair :
Info.PointerToBase)
2484 if (isa<Constant>(BasePair.second))
2485 Info.LiveSet.remove(BasePair.first);
2488 CI->eraseFromParent();
2495 for (
size_t i = 0;
i < Records.size();
i++)
2501 std::vector<DeferredReplacement> Replacements;
2509 for (
size_t i = 0;
i < Records.size();
i++)
2514 for (
auto &PR : Replacements)
2517 Replacements.clear();
2519 for (
auto &
Info : Records) {
2528 Info.LiveSet.clear();
2529 Info.PointerToBase.clear();
2534 for (
size_t i = 0;
i < Records.size();
i++) {
2535 PartiallyConstructedSafepointRecord &
Info = Records[
i];
2549 "statepoint must be reachable or liveness is meaningless");
2550 for (
Value *V :
Info.StatepointToken->gc_args()) {
2551 if (!isa<Instruction>(V))
2554 auto *LiveInst = cast<Instruction>(V);
2556 "unreachable values should never be live");
2558 "basic SSA liveness expectation violated by liveness analysis");
2566 for (
auto *Ptr : Live)
2568 "must be a gc pointer type");
2572 return !Records.empty();
2576 template <
typename AttrHolder>
2580 if (
AH.getDereferenceableBytes(
Index))
2582 AH.getDereferenceableBytes(
Index)));
2583 if (
AH.getDereferenceableOrNullBytes(
Index))
2585 AH.getDereferenceableOrNullBytes(
Index)));
2586 for (
auto Attr : {Attribute::NoAlias, Attribute::NoFree})
2587 if (
AH.getAttributes().hasAttribute(
Index, Attr))
2588 R.addAttribute(Attr);
2591 AH.setAttributes(
AH.getAttributes().removeAttributes(Ctx,
Index,
R));
2598 if (isa<PointerType>(
A.getType()))
2602 if (isa<PointerType>(
F.getReturnType()))
2605 for (
auto Attr : {Attribute::NoSync, Attribute::NoFree})
2606 F.removeFnAttr(Attr);
2613 if (!isa<LoadInst>(
I) && !isa<StoreInst>(
I))
2628 unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,
2629 LLVMContext::MD_range,
2630 LLVMContext::MD_alias_scope,
2631 LLVMContext::MD_nontemporal,
2632 LLVMContext::MD_nonnull,
2633 LLVMContext::MD_align,
2634 LLVMContext::MD_type};
2637 I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);
2658 if (
auto *II = dyn_cast<IntrinsicInst>(&
I))
2659 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
2660 InvariantStartInstructions.push_back(II);
2664 if (
MDNode *
Tag =
I.getMetadata(LLVMContext::MD_tbaa)) {
2666 I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
2671 if (
auto *
Call = dyn_cast<CallBase>(&
I)) {
2672 for (
int i = 0,
e =
Call->arg_size();
i !=
e;
i++)
2673 if (isa<PointerType>(
Call->getArgOperand(
i)->getType()))
2676 if (isa<PointerType>(
Call->getType()))
2682 for (
auto *II : InvariantStartInstructions) {
2684 II->eraseFromParent();
2693 const auto &FunctionGCName =
F.getGC();
2694 const StringRef StatepointExampleName(
"statepoint-example");
2696 return (StatepointExampleName == FunctionGCName) ||
2697 (CoreCLRName == FunctionGCName);
2717 assert(!
F.isDeclaration() && !
F.empty() &&
2718 "need function body to rewrite statepoints in");
2722 if (
const auto *
Call = dyn_cast<CallBase>(&
I)) {
2723 if (isa<GCStatepointInst>(
Call))
2737 assert((isa<AtomicMemCpyInst>(
Call) || isa<AtomicMemMoveInst>(
Call)) &&
2738 "Don't expect any other calls here!");
2760 if (NeedsRewrite(
I)) {
2766 "no unreachable blocks expected");
2767 ParsePointNeeded.push_back(cast<CallBase>(&
I));
2772 if (ParsePointNeeded.empty())
2780 if (
BB.getUniquePredecessor())
2797 if (
auto *BI = dyn_cast<BranchInst>(TI))
2798 if (BI->isConditional())
2799 return dyn_cast<Instruction>(BI->getCondition());
2805 if (
auto *
Cond = getConditionInst(TI))
2808 if (isa<ICmpInst>(
Cond) &&
Cond->hasOneUse()) {
2810 Cond->moveBefore(TI);
2820 if (!isa<GetElementPtrInst>(
I))
2824 for (
unsigned i = 0;
i <
I.getNumOperands();
i++)
2825 if (
auto *OpndVTy = dyn_cast<VectorType>(
I.getOperand(
i)->getType())) {
2827 VF == cast<FixedVectorType>(OpndVTy)->getNumElements());
2828 VF = cast<FixedVectorType>(OpndVTy)->getNumElements();
2833 if (!
I.getOperand(0)->getType()->isVectorTy() && VF != 0) {
2835 auto *Splat =
B.CreateVectorSplat(VF,
I.getOperand(0));
2836 I.setOperand(0, Splat);
2862 if (isa<PHINode>(
I))
2866 for (
Value *V :
I.operands()) {
2868 "support for FCA unimplemented");
2888 for (
auto &
I : *Succ) {
2889 PHINode *PN = dyn_cast<PHINode>(&
I);
2895 "support for FCA unimplemented");
2915 for (
Value *V : Live) {
2916 if (
auto *
I = dyn_cast<Instruction>(V)) {
2920 if (TermOkay && TI ==
I)
2923 "basic SSA liveness expectation violated by liveness analysis");
2940 GCPtrLivenessData &
Data) {
2946 Data.LiveSet[&
BB].clear();
2959 if (!
Data.LiveIn[&
BB].empty())
2964 while (!Worklist.
empty()) {
2970 const auto OldLiveOutSize = LiveOut.
size();
2976 if (OldLiveOutSize == LiveOut.
size()) {
2982 Data.LiveOut[
BB] = LiveOut;
2992 if (OldLiveIn.
size() != LiveTmp.
size()) {
2993 Data.LiveIn[
BB] = LiveTmp;
3021 Out.insert(LiveOut.
begin(), LiveOut.
end());
3026 PartiallyConstructedSafepointRecord &
Info) {
3032 for (
auto V : Updated)
3033 Info.PointerToBase.insert({V, V});
3036 for (
auto V : Updated)
3038 "Must be able to find base for live value!");
3044 for (
auto KVPair :
Info.PointerToBase)
3045 if (!Updated.count(KVPair.first))
3046 ToErase.
insert(KVPair.first);
3048 for (
auto *V : ToErase)
3049 Info.PointerToBase.erase(V);
3052 for (
auto KVPair :
Info.PointerToBase)
3053 assert(Updated.count(KVPair.first) &&
"record for non-live value");
3056 Info.LiveSet = Updated;