24#include "llvm/Config/llvm-config.h"
48#define DEBUG_TYPE "coro-suspend-crossing"
54class BlockToIndexMapping {
58 size_t size()
const {
return V.size(); }
68 assert(
I !=
V.end() && *
I == BB &&
"BasicBlockNumberng: Unknown block");
92class SuspendCrossingInfo {
93 BlockToIndexMapping Mapping;
100 bool KillLoop =
false;
101 bool Changed =
false;
106 BasicBlock *BB = Mapping.indexToBlock(&BD - &Block[0]);
111 return Block[Mapping.blockToIndex(BB)];
118 template <
bool Initialize = false>
bool computeBlockData();
121#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
131 size_t const FromIndex = Mapping.blockToIndex(
From);
132 size_t const ToIndex = Mapping.blockToIndex(To);
133 bool const Result =
Block[ToIndex].Kills[FromIndex];
135 <<
" answer is " << Result <<
"\n");
144 size_t const FromIndex = Mapping.blockToIndex(
From);
145 size_t const ToIndex = Mapping.blockToIndex(To);
149 <<
" answer is " << Result <<
" (path or loop)\n");
153 bool isDefinitionAcrossSuspend(
BasicBlock *DefBB,
User *U)
const {
154 auto *
I = cast<Instruction>(U);
158 if (
auto *PN = dyn_cast<PHINode>(
I))
159 if (PN->getNumIncomingValues() > 1)
167 if (isa<CoroSuspendRetconInst>(
I) || isa<CoroSuspendAsyncInst>(
I)) {
169 assert(UseBB &&
"should have split coro.suspend into its own block");
172 return hasPathCrossingSuspendPoint(DefBB, UseBB);
176 return isDefinitionAcrossSuspend(&
A.getParent()->getEntryBlock(), U);
180 auto *DefBB =
I.getParent();
185 if (isa<AnyCoroSuspendInst>(
I)) {
187 assert(DefBB &&
"should have split coro.suspend into its own block");
190 return isDefinitionAcrossSuspend(DefBB, U);
193 bool isDefinitionAcrossSuspend(
Value &V,
User *U)
const {
194 if (
auto *
Arg = dyn_cast<Argument>(&V))
195 return isDefinitionAcrossSuspend(*
Arg, U);
196 if (
auto *Inst = dyn_cast<Instruction>(&V))
197 return isDefinitionAcrossSuspend(*Inst, U);
200 "Coroutine could only collect Argument and Instruction now.");
205#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
209 for (
size_t I = 0,
N = BV.
size();
I <
N; ++
I)
211 dbgs() <<
" " << Mapping.indexToBlock(
I)->getName();
216 for (
size_t I = 0,
N =
Block.size();
I <
N; ++
I) {
218 dbgs() <<
B->getName() <<
":\n";
219 dump(
" Consumes", Block[
I].Consumes);
220 dump(
" Kills", Block[
I].Kills);
226template <
bool Initialize>
bool SuspendCrossingInfo::computeBlockData() {
227 const size_t N = Mapping.size();
228 bool Changed =
false;
230 for (
size_t I = 0;
I <
N; ++
I) {
234 if constexpr (!Initialize)
238 return !
Block[Mapping.blockToIndex(BB)].Changed;
246 auto SavedConsumes =
B.Consumes;
247 auto SavedKills =
B.Kills;
250 auto PrevNo = Mapping.blockToIndex(PI);
254 B.Consumes |=
P.Consumes;
260 B.Kills |=
P.Consumes;
266 B.Kills |=
B.Consumes;
276 B.KillLoop |=
B.Kills[
I];
280 if constexpr (!Initialize) {
281 B.Changed = (
B.Kills != SavedKills) || (
B.Consumes != SavedConsumes);
282 Changed |=
B.Changed;
286 if constexpr (Initialize)
294 const size_t N = Mapping.size();
298 for (
size_t I = 0;
I <
N; ++
I) {
300 B.Consumes.resize(
N);
310 getBlockData(
CE->getParent()).End =
true;
318 auto &
B = getBlockData(SuspendBlock);
320 B.Kills |=
B.Consumes;
323 markSuspendBlock(CSI);
324 if (
auto *Save = CSI->getCoroSave())
325 markSuspendBlock(Save);
328 computeBlockData<
true>();
330 while (computeBlockData())
350 RematNode() =
default;
354 RematNode *EntryNode;
359 SuspendCrossingInfo &Checker;
361 RematGraph(
const std::function<
bool(
Instruction &)> &MaterializableCallback,
363 : MaterializableCallback(MaterializableCallback), Checker(Checker) {
364 std::unique_ptr<RematNode> FirstNode = std::make_unique<RematNode>(
I);
365 EntryNode = FirstNode.get();
366 std::deque<std::unique_ptr<RematNode>> WorkList;
367 addNode(std::move(FirstNode), WorkList, cast<User>(
I));
368 while (WorkList.size()) {
369 std::unique_ptr<RematNode>
N = std::move(WorkList.front());
370 WorkList.pop_front();
371 addNode(std::move(
N), WorkList, cast<User>(
I));
375 void addNode(std::unique_ptr<RematNode> NUPtr,
376 std::deque<std::unique_ptr<RematNode>> &WorkList,
378 RematNode *
N = NUPtr.get();
379 if (Remats.count(
N->Node))
383 Remats[
N->Node] = std::move(NUPtr);
384 for (
auto &Def :
N->Node->operands()) {
386 if (!
D || !MaterializableCallback(*
D) ||
387 !Checker.isDefinitionAcrossSuspend(*
D, FirstUse))
390 if (Remats.count(
D)) {
392 N->Operands.push_back(Remats[
D].
get());
397 for (
auto &
I : WorkList) {
400 N->Operands.push_back(
I.get());
406 std::unique_ptr<RematNode> ChildNode = std::make_unique<RematNode>(
D);
407 N->Operands.push_back(ChildNode.get());
408 WorkList.push_back(std::move(ChildNode));
413#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
416 if (EntryNode->Node->getParent()->hasName())
417 dbgs() << EntryNode->Node->getParent()->getName();
419 EntryNode->Node->getParent()->printAsOperand(
dbgs(),
false);
420 dbgs() <<
") : " << *EntryNode->Node <<
"\n";
421 for (
auto &
E : Remats) {
422 dbgs() << *(
E.first) <<
"\n";
423 for (RematNode *U :
E.second->Operands)
424 dbgs() <<
" " << *
U->Node <<
"\n";
439 return N->Operands.begin();
447#define DEBUG_TYPE "coro-frame"
450class FrameTypeBuilder;
456 bool MayWriteBeforeCoroBegin;
459 bool MayWriteBeforeCoroBegin)
460 : Alloca(Alloca), Aliases(std::move(Aliases)),
461 MayWriteBeforeCoroBegin(MayWriteBeforeCoroBegin) {}
463struct FrameDataInfo {
473 for (
const auto &
P : Spills)
475 for (
const auto &
A : Allocas)
481 auto Itr = FieldIndexMap.find(V);
482 assert(Itr != FieldIndexMap.end() &&
483 "Value does not have a frame field index");
488 assert((LayoutIndexUpdateStarted || FieldIndexMap.count(V) == 0) &&
489 "Cannot set the index for the same field twice.");
490 FieldIndexMap[V] =
Index;
494 auto Iter = FieldAlignMap.find(V);
495 assert(Iter != FieldAlignMap.end());
500 assert(FieldAlignMap.count(V) == 0);
501 FieldAlignMap.insert({V, AL});
505 auto Iter = FieldDynamicAlignMap.find(V);
506 assert(Iter != FieldDynamicAlignMap.end());
511 assert(FieldDynamicAlignMap.count(V) == 0);
512 FieldDynamicAlignMap.insert({V,
Align});
516 auto Iter = FieldOffsetMap.find(V);
517 assert(Iter != FieldOffsetMap.end());
522 assert(FieldOffsetMap.count(V) == 0);
523 FieldOffsetMap.insert({V,
Offset});
527 void updateLayoutIndex(FrameTypeBuilder &
B);
532 bool LayoutIndexUpdateStarted =
false;
549 dbgs() <<
"------------- " << Title <<
"--------------\n";
550 for (
const auto &
E : Spills) {
553 for (
auto *
I :
E.second)
560 dbgs() <<
"------------- " << Title <<
"--------------\n";
561 for (
const auto &
E : RM) {
568 dbgs() <<
"------------- Allocas --------------\n";
569 for (
const auto &
A : Allocas) {
576using FieldIDType = size_t;
581class FrameTypeBuilder {
587 FieldIDType LayoutFieldIndex;
597 bool IsFinished =
false;
599 std::optional<Align> MaxFrameAlignment;
606 std::optional<Align> MaxFrameAlignment)
611 [[nodiscard]] FieldIDType addFieldForAlloca(
AllocaInst *AI,
612 bool IsHeader =
false) {
617 if (
auto *CI = dyn_cast<ConstantInt>(AI->
getArraySize()))
618 Ty = ArrayType::get(Ty, CI->getValue().getZExtValue());
623 return addField(Ty, AI->
getAlign(), IsHeader);
653 void addFieldForAllocas(
const Function &
F, FrameDataInfo &FrameData,
657 [[nodiscard]] FieldIDType addField(
Type *Ty,
MaybeAlign MaybeFieldAlignment,
658 bool IsHeader =
false,
659 bool IsSpillOfValue =
false) {
660 assert(!IsFinished &&
"adding fields to a finished builder");
661 assert(Ty &&
"must provide a type for a field");
668 if (FieldSize == 0) {
676 Align ABIAlign =
DL.getABITypeAlign(Ty);
677 Align TyAlignment = ABIAlign;
678 if (IsSpillOfValue && MaxFrameAlignment && *MaxFrameAlignment < ABIAlign)
679 TyAlignment = *MaxFrameAlignment;
680 Align FieldAlignment = MaybeFieldAlignment.value_or(TyAlignment);
686 if (MaxFrameAlignment && (FieldAlignment > *MaxFrameAlignment)) {
689 FieldAlignment = *MaxFrameAlignment;
690 FieldSize = FieldSize + DynamicAlignBuffer;
697 StructSize =
Offset + FieldSize;
704 Fields.
push_back({FieldSize,
Offset, Ty, 0, FieldAlignment, TyAlignment,
705 DynamicAlignBuffer});
706 return Fields.
size() - 1;
713 assert(IsFinished &&
"not yet finished!");
717 Align getStructAlign()
const {
718 assert(IsFinished &&
"not yet finished!");
722 FieldIDType getLayoutFieldIndex(FieldIDType Id)
const {
723 assert(IsFinished &&
"not yet finished!");
724 return Fields[
Id].LayoutFieldIndex;
727 Field getLayoutField(FieldIDType Id)
const {
728 assert(IsFinished &&
"not yet finished!");
734void FrameDataInfo::updateLayoutIndex(FrameTypeBuilder &
B) {
735 auto Updater = [&](
Value *
I) {
736 auto Field =
B.getLayoutField(getFieldIndex(
I));
737 setFieldIndex(
I,
Field.LayoutFieldIndex);
740 Field.DynamicAlignBuffer
743 setDynamicAlign(
I, dynamicAlign);
746 LayoutIndexUpdateStarted =
true;
747 for (
auto &S : Spills)
749 for (
const auto &
A : Allocas)
751 LayoutIndexUpdateStarted =
false;
754void FrameTypeBuilder::addFieldForAllocas(
const Function &
F,
755 FrameDataInfo &FrameData,
762 for (
auto AllocaList : NonOverlapedAllocas) {
763 auto *LargestAI = *AllocaList.begin();
764 FieldIDType
Id = addFieldForAlloca(LargestAI);
765 for (
auto *Alloca : AllocaList)
773 NonOverlapedAllocas.emplace_back(AllocaSetType(1, Alloca));
793 if (
auto *ConstSWI = dyn_cast<SwitchInst>(U)) {
794 auto *SWI =
const_cast<SwitchInst *
>(ConstSWI);
795 DefaultSuspendDest[SWI] = SWI->getDefaultDest();
796 SWI->setDefaultDest(SWI->getSuccessor(1));
801 auto ExtractAllocas = [&]() {
802 AllocaSetType Allocas;
805 Allocas.push_back(
A.Alloca);
809 StackLifetime::LivenessType::May);
810 StackLifetimeAnalyzer.run();
812 return StackLifetimeAnalyzer.getLiveRange(AI1).overlaps(
813 StackLifetimeAnalyzer.getLiveRange(AI2));
815 auto GetAllocaSize = [&](
const AllocaInfo &
A) {
816 std::optional<TypeSize> RetSize =
A.Alloca->getAllocationSize(
DL);
817 assert(RetSize &&
"Variable Length Arrays (VLA) are not supported.\n");
818 assert(!RetSize->isScalable() &&
"Scalable vectors are not yet supported");
819 return RetSize->getFixedValue();
825 sort(
FrameData.Allocas, [&](
const auto &Iter1,
const auto &Iter2) {
826 return GetAllocaSize(Iter1) > GetAllocaSize(Iter2);
834 for (
auto &AllocaSet : NonOverlapedAllocas) {
835 assert(!AllocaSet.empty() &&
"Processing Alloca Set is not empty.\n");
836 bool NoInference =
none_of(AllocaSet, [&](
auto Iter) {
837 return IsAllocaInferenre(Alloca, Iter);
845 bool Alignable = [&]() ->
bool {
846 auto *LargestAlloca = *AllocaSet.begin();
847 return LargestAlloca->getAlign().value() % Alloca->
getAlign().
value() ==
850 bool CouldMerge = NoInference && Alignable;
853 AllocaSet.push_back(Alloca);
858 NonOverlapedAllocas.emplace_back(AllocaSetType(1, Alloca));
863 for (
auto SwitchAndDefaultDest : DefaultSuspendDest) {
865 BasicBlock *DestBB = SwitchAndDefaultDest.second;
870 : NonOverlapedAllocas) {
871 if (AllocaSet.size() > 1) {
872 dbgs() <<
"In Function:" << F.getName() <<
"\n";
873 dbgs() <<
"Find Union Set "
875 dbgs() <<
"\tAllocas are \n";
876 for (auto Alloca : AllocaSet)
877 dbgs() <<
"\t\t" << *Alloca <<
"\n";
882void FrameTypeBuilder::finish(
StructType *Ty) {
883 assert(!IsFinished &&
"already finished!");
889 for (
auto &
Field : Fields) {
896 StructSize = SizeAndAlign.first;
897 StructAlign = SizeAndAlign.second;
900 return *
static_cast<Field *
>(
const_cast<void*
>(LayoutField.Id));
906 for (
auto &LayoutField : LayoutFields) {
907 auto &
F = getField(LayoutField);
908 if (!
isAligned(
F.TyAlignment, LayoutField.Offset))
916 FieldTypes.
reserve(LayoutFields.size() * 3 / 2);
918 for (
auto &LayoutField : LayoutFields) {
919 auto &
F = getField(LayoutField);
921 auto Offset = LayoutField.Offset;
927 if (
Offset != LastOffset) {
934 F.LayoutFieldIndex = FieldTypes.
size();
937 if (
F.DynamicAlignBuffer) {
944 Ty->
setBody(FieldTypes, Packed);
948 auto Layout =
DL.getStructLayout(Ty);
949 for (
auto &
F : Fields) {
951 assert(Layout->getElementOffset(
F.LayoutFieldIndex) ==
F.Offset);
960 for (
auto *V : FrameData.getAllDefs()) {
969 DIVarCache.
insert({V, (*I)->getVariable()});
980 OS <<
"__int_" << cast<IntegerType>(Ty)->getBitWidth();
982 return MDName->getString();
990 return "__floating_type_";
993 if (
auto *PtrTy = dyn_cast<PointerType>(Ty)) {
994 if (PtrTy->isOpaque())
995 return "PointerType";
998 if (
Name ==
"UnknownType")
999 return "PointerType";
1003 return MDName->getString();
1007 if (!cast<StructType>(Ty)->hasName())
1008 return "__LiteralStructType_";
1013 for (
auto &Iter : Buffer)
1014 if (Iter ==
'.' || Iter ==
':')
1017 return MDName->getString();
1020 return "UnknownType";
1032 DIType *RetType =
nullptr;
1035 auto BitWidth = cast<IntegerType>(Ty)->getBitWidth();
1037 llvm::DINode::FlagArtificial);
1040 dwarf::DW_ATE_float,
1041 llvm::DINode::FlagArtificial);
1053 std::nullopt,
Name);
1055 auto *DIStruct =
Builder.createStructType(
1058 llvm::DINode::FlagArtificial,
nullptr, llvm::DINodeArray());
1060 auto *StructTy = cast<StructType>(Ty);
1062 for (
unsigned I = 0;
I < StructTy->getNumElements();
I++) {
1064 Scope, LineNum, DITypeCache);
1066 Elements.push_back(
Builder.createMemberType(
1067 Scope, DITy->
getName(), Scope->getFile(), LineNum,
1070 llvm::DINode::FlagArtificial, DITy));
1073 Builder.replaceArrays(DIStruct,
Builder.getOrCreateArray(Elements));
1079 auto *CharSizeType =
Builder.createBasicType(
1080 Name, 8, dwarf::DW_ATE_unsigned_char, llvm::DINode::FlagArtificial);
1083 RetType = CharSizeType;
1088 RetType =
Builder.createArrayType(
1094 DITypeCache.
insert({Ty, RetType});
1111 FrameDataInfo &FrameData) {
1116 if (!DIS || !DIS->getUnit() ||
1121 assert(Shape.
ABI == coro::ABI::Switch &&
1122 "We could only build debug infomation for C++ coroutine now.\n");
1128 "Coroutine with switch ABI should own Promise alloca");
1139 unsigned LineNum = PromiseDIVariable->
getLine();
1142 DIS->getUnit(),
Twine(
F.getName() +
".coro_frame_ty").
str(),
1145 llvm::DINodeArray());
1148 DataLayout Layout =
F.getParent()->getDataLayout();
1158 NameCache.
insert({ResumeIndex,
"__resume_fn"});
1159 NameCache.
insert({DestroyIndex,
"__destroy_fn"});
1160 NameCache.
insert({IndexIndex,
"__coro_index"});
1181 dwarf::DW_ATE_unsigned_char)});
1183 for (
auto *V : FrameData.getAllDefs()) {
1187 auto Index = FrameData.getFieldIndex(V);
1189 NameCache.
insert({
Index, DIVarCache[V]->getName()});
1190 TyCache.
insert({
Index, DIVarCache[V]->getType()});
1196 OffsetCache.
insert({ResumeIndex, {8, 0}});
1197 OffsetCache.
insert({DestroyIndex, {8, 8}});
1202 for (
auto *V : FrameData.getAllDefs()) {
1203 auto Index = FrameData.getFieldIndex(V);
1206 {
Index, {FrameData.getAlign(V).
value(), FrameData.getOffset(V)}});
1214 unsigned UnknownTypeNum = 0;
1226 assert(Ty->
isSized() &&
"We can't handle type which is not sized.\n");
1228 AlignInBits = OffsetCache[
Index].first * 8;
1229 OffsetInBits = OffsetCache[
Index].second * 8;
1233 DITy = TyCache[
Index];
1235 DITy =
solveDIType(DBuilder, Ty, Layout, FrameDITy, LineNum, DITypeCache);
1236 assert(DITy &&
"SolveDIType shouldn't return nullptr.\n");
1238 Name +=
"_" + std::to_string(UnknownTypeNum);
1243 FrameDITy,
Name, DFile, LineNum, SizeInBits, AlignInBits, OffsetInBits,
1244 llvm::DINode::FlagArtificial, DITy));
1250 DFile, LineNum, FrameDITy,
1251 true, DINode::FlagArtificial);
1261 if (
auto *SubProgram = dyn_cast<DISubprogram>(PromiseDIScope)) {
1262 auto RetainedNodes = SubProgram->getRetainedNodes();
1264 RetainedNodes.end());
1266 SubProgram->replaceOperandWith(
1270 DBuilder.insertDeclare(Shape.
FramePtr, FrameDIVar,
1284 FrameDataInfo &FrameData) {
1289 Name.append(
".Frame");
1294 std::optional<Align> MaxFrameAlignment;
1295 if (Shape.
ABI == coro::ABI::Async)
1297 FrameTypeBuilder
B(
C,
DL, MaxFrameAlignment);
1300 std::optional<FieldIDType> SwitchIndexFieldId;
1302 if (Shape.
ABI == coro::ABI::Switch) {
1306 auto *FnPtrTy = FnTy->getPointerTo();
1310 (void)
B.addField(FnPtrTy, std::nullopt,
true);
1311 (void)
B.addField(FnPtrTy, std::nullopt,
true);
1317 FrameData.setFieldIndex(
1318 PromiseAlloca,
B.addFieldForAlloca(PromiseAlloca,
true));
1325 SwitchIndexFieldId =
B.addField(IndexType, std::nullopt);
1327 assert(PromiseAlloca ==
nullptr &&
"lowering doesn't support promises");
1332 B.addFieldForAllocas(
F, FrameData, Shape);
1337 if (Shape.
ABI == coro::ABI::Switch && PromiseAlloca)
1340 FrameData.Allocas.emplace_back(
1343 for (
auto &S : FrameData.Spills) {
1344 Type *FieldType = S.first->getType();
1347 if (
const Argument *
A = dyn_cast<Argument>(S.first))
1348 if (
A->hasByValAttr())
1349 FieldType =
A->getParamByValType();
1350 FieldIDType Id =
B.addField(FieldType, std::nullopt,
false ,
1352 FrameData.setFieldIndex(S.first, Id);
1356 FrameData.updateLayoutIndex(
B);
1360 switch (Shape.
ABI) {
1361 case coro::ABI::Switch: {
1363 auto IndexField =
B.getLayoutField(*SwitchIndexFieldId);
1375 case coro::ABI::Retcon:
1376 case coro::ABI::RetconOnce: {
1379 = (
B.getStructSize() <= Id->getStorageSize() &&
1380 B.getStructAlign() <= Id->getStorageAlignment());
1383 case coro::ABI::Async: {
1393 "The alignment requirment of frame variables cannot be higher than "
1394 "the alignment of the async function context");
1432 const CoroBeginInst &CB,
const SuspendCrossingInfo &Checker,
1433 bool ShouldUseLifetimeStartInfo)
1435 ShouldUseLifetimeStartInfo(ShouldUseLifetimeStartInfo) {}
1442 if (PI.isEscaped() && !DT.dominates(&CoroBegin, PI.getEscapingInst())) {
1443 MayWriteBeforeCoroBegin =
true;
1465 if (
SI.getValueOperand() !=
U->get())
1478 auto IsSimpleStoreThenLoad = [&]() {
1479 auto *AI = dyn_cast<AllocaInst>(
SI.getPointerOperand());
1487 while (!StoreAliases.
empty()) {
1489 for (
User *U :
I->users()) {
1492 if (
auto *LI = dyn_cast<LoadInst>(U)) {
1499 if (
auto *S = dyn_cast<StoreInst>(U))
1500 if (S->getPointerOperand() ==
I)
1502 if (
auto *II = dyn_cast<IntrinsicInst>(U))
1503 if (II->isLifetimeStartOrEnd())
1507 if (
auto *BI = dyn_cast<BitCastInst>(U)) {
1518 if (!IsSimpleStoreThenLoad())
1545 if (II.
getIntrinsicID() != Intrinsic::lifetime_start || !IsOffsetKnown ||
1548 LifetimeStarts.insert(&II);
1552 for (
unsigned Op = 0, OpCount = CB.
arg_size(); Op < OpCount; ++Op)
1558 bool getShouldLiveOnFrame()
const {
1559 if (!ShouldLiveOnFrame)
1560 ShouldLiveOnFrame = computeShouldLiveOnFrame();
1561 return *ShouldLiveOnFrame;
1564 bool getMayWriteBeforeCoroBegin()
const {
return MayWriteBeforeCoroBegin; }
1567 assert(getShouldLiveOnFrame() &&
"This method should only be called if the "
1568 "alloca needs to live on the frame.");
1569 for (
const auto &
P : AliasOffetMap)
1572 "created before CoroBegin.");
1573 return AliasOffetMap;
1579 const SuspendCrossingInfo &Checker;
1586 bool MayWriteBeforeCoroBegin{
false};
1587 bool ShouldUseLifetimeStartInfo{
true};
1589 mutable std::optional<bool> ShouldLiveOnFrame{};
1591 bool computeShouldLiveOnFrame()
const {
1596 if (ShouldUseLifetimeStartInfo && !LifetimeStarts.empty()) {
1597 for (
auto *
I : Users)
1598 for (
auto *S : LifetimeStarts)
1599 if (Checker.isDefinitionAcrossSuspend(*S,
I))
1605 if (PI.isEscaped()) {
1606 for (
auto *
A : LifetimeStarts) {
1607 for (
auto *
B : LifetimeStarts) {
1608 if (Checker.hasPathOrLoopCrossingSuspendPoint(
A->getParent(),
1629 for (
auto *U1 : Users)
1630 for (
auto *U2 : Users)
1631 if (Checker.isDefinitionAcrossSuspend(*U1, U2))
1639 MayWriteBeforeCoroBegin =
true;
1643 for (
auto &U :
I.uses())
1653 if (DT.
dominates(&CoroBegin, &
I) || !usedAfterCoroBegin(
I))
1656 if (!IsOffsetKnown) {
1657 AliasOffetMap[&
I].reset();
1659 auto Itr = AliasOffetMap.
find(&
I);
1660 if (Itr == AliasOffetMap.end()) {
1662 }
else if (Itr->second && *Itr->second !=
Offset) {
1665 AliasOffetMap[&
I].reset();
1699 cast<Instruction>(
Builder.CreateBitCast(CB, FramePtrTy,
"FramePtr"));
1737 auto GetFramePointer = [&](
Value *Orig) ->
Value * {
1738 FieldIDType
Index = FrameData.getFieldIndex(Orig);
1744 if (
auto *AI = dyn_cast<AllocaInst>(Orig)) {
1745 if (
auto *CI = dyn_cast<ConstantInt>(AI->
getArraySize())) {
1746 auto Count = CI->getValue().getZExtValue();
1755 auto GEP = cast<GetElementPtrInst>(
1757 if (
auto *AI = dyn_cast<AllocaInst>(Orig)) {
1758 if (FrameData.getDynamicAlign(Orig) != 0) {
1761 auto *IntPtrTy = M->getDataLayout().getIntPtrType(AI->
getType());
1762 auto *PtrValue =
Builder.CreatePtrToInt(
GEP, IntPtrTy);
1765 PtrValue =
Builder.CreateAdd(PtrValue, AlignMask);
1766 PtrValue =
Builder.CreateAnd(PtrValue,
Builder.CreateNot(AlignMask));
1776 if (
GEP->getType() != Orig->getType())
1777 return Builder.CreateBitCast(
GEP, Orig->getType(),
1778 Orig->getName() +
Twine(
".cast"));
1783 for (
auto const &
E : FrameData.Spills) {
1785 auto SpillAlignment =
Align(FrameData.getAlign(Def));
1789 Type *ByValTy =
nullptr;
1790 if (
auto *
Arg = dyn_cast<Argument>(Def)) {
1798 Arg->getParent()->removeParamAttr(
Arg->getArgNo(), Attribute::NoCapture);
1800 if (
Arg->hasByValAttr())
1801 ByValTy =
Arg->getParamByValType();
1802 }
else if (
auto *CSI = dyn_cast<AnyCoroSuspendInst>(Def)) {
1807 auto *
I = cast<Instruction>(Def);
1812 }
else if (
auto *II = dyn_cast<InvokeInst>(
I)) {
1816 InsertPt = NewBB->getTerminator();
1817 }
else if (isa<PHINode>(
I)) {
1820 if (
auto *CSI = dyn_cast<CatchSwitchInst>(DefBlock->
getTerminator()))
1825 assert(!
I->isTerminator() &&
"unexpected terminator");
1828 InsertPt =
I->getNextNode();
1832 auto Index = FrameData.getFieldIndex(Def);
1833 Builder.SetInsertPoint(InsertPt);
1834 auto *
G =
Builder.CreateConstInBoundsGEP2_32(
1842 Builder.CreateAlignedStore(Def,
G, SpillAlignment);
1846 Value *CurrentReload =
nullptr;
1847 for (
auto *U :
E.second) {
1851 if (CurrentBlock != U->getParent()) {
1852 CurrentBlock = U->getParent();
1855 auto *
GEP = GetFramePointer(
E.first);
1856 GEP->setName(
E.first->getName() +
Twine(
".reload.addr"));
1858 CurrentReload =
GEP;
1860 CurrentReload =
Builder.CreateAlignedLoad(
1862 SpillAlignment,
E.first->getName() +
Twine(
".reload"));
1868 if (
F->getSubprogram()) {
1870 while (DIs.
empty() && isa<LoadInst>(CurDef)) {
1871 auto *LdInst = cast<LoadInst>(CurDef);
1873 if (LdInst->getPointerOperandType() != LdInst->getType())
1875 CurDef = LdInst->getPointerOperand();
1881 bool AllowUnresolved =
false;
1886 .insertDeclare(CurrentReload, DDI->getVariable(),
1887 DDI->getExpression(), DDI->getDebugLoc(),
1898 if (
auto *PN = dyn_cast<PHINode>(U)) {
1899 assert(PN->getNumIncomingValues() == 1 &&
1900 "unexpected number of incoming "
1901 "values in the PHINode");
1902 PN->replaceAllUsesWith(CurrentReload);
1903 PN->eraseFromParent();
1909 U->replaceUsesOfWith(Def, CurrentReload);
1921 if (Shape.
ABI == coro::ABI::Retcon || Shape.
ABI == coro::ABI::RetconOnce ||
1922 Shape.
ABI == coro::ABI::Async) {
1924 Builder.SetInsertPoint(&SpillBlock->front());
1925 for (
const auto &
P : FrameData.Allocas) {
1927 auto *
G = GetFramePointer(Alloca);
1931 G->takeName(Alloca);
1945 for (
const auto &
A : FrameData.Allocas) {
1947 UsersToUpdate.
clear();
1949 auto *
I = cast<Instruction>(U);
1953 if (UsersToUpdate.
empty())
1955 auto *
G = GetFramePointer(Alloca);
1960 for (
auto *DVI : DIs)
1961 DVI->replaceUsesOfWith(Alloca,
G);
1967 if (
I->isLifetimeStartOrEnd()) {
1968 I->eraseFromParent();
1972 I->replaceUsesOfWith(Alloca,
G);
1976 for (
const auto &
A : FrameData.Allocas) {
1978 if (
A.MayWriteBeforeCoroBegin) {
1982 "Coroutines cannot handle copying of array allocas yet");
1984 auto *
G = GetFramePointer(Alloca);
1991 for (
const auto &Alias :
A.Aliases) {
1992 auto *
FramePtr = GetFramePointer(Alloca);
1995 auto &
Value = *Alias.second;
1999 auto *AliasPtrTyped =
2000 Builder.CreateBitCast(AliasPtr, Alias.first->getType());
2001 Alias.first->replaceUsesWithIf(
2002 AliasPtrTyped, [&](
Use &U) {
return DT.
dominates(CB, U); });
2014 auto *Inst = dyn_cast<Instruction>(U.getUser());
2015 if (!Inst || DT.dominates(CB, Inst))
2018 if (auto *CI = dyn_cast<CallInst>(Inst)) {
2023 if (CI->onlyReadsMemory() ||
2024 CI->onlyReadsMemory(CI->getArgOperandNo(&U)))
2029 return isa<StoreInst>(Inst) ||
2032 isa<GetElementPtrInst>(Inst) ||
2037 isa<BitCastInst>(Inst);
2039 if (HasAccessingPromiseBeforeCB) {
2041 auto *
G = GetFramePointer(PA);
2042 auto *
Value =
Builder.CreateLoad(PA->getAllocatedType(), PA);
2053 PHINode *UntilPHI =
nullptr) {
2054 auto *PN = cast<PHINode>(&SuccBB->
front());
2056 int Index = PN->getBasicBlockIndex(InsertedBB);
2059 V->getType(), 1, V->getName() +
Twine(
".") + SuccBB->
getName(),
2060 &InsertedBB->
front());
2062 PN->setIncomingValue(
Index, InputV);
2063 PN = dyn_cast<PHINode>(PN->getNextNode());
2064 }
while (PN != UntilPHI);
2104 auto *NewCleanupPadBB =
2107 CleanupPadBB->
getParent(), CleanupPadBB);
2108 Builder.SetInsertPoint(NewCleanupPadBB);
2109 auto *SwitchType =
Builder.getInt8Ty();
2110 auto *SetDispatchValuePN =
2114 auto *SwitchOnDispatch =
Builder.CreateSwitch(SetDispatchValuePN, UnreachBB,
2117 int SwitchIndex = 0;
2123 Twine(
".from.") + Pred->getName(),
2124 CleanupPadBB->
getParent(), CleanupPadBB);
2126 CaseBB->setName(CleanupPadBB->
getName() +
Twine(
".from.") +
2128 Builder.SetInsertPoint(CaseBB);
2129 Builder.CreateBr(CleanupPadBB);
2137 SetDispatchValuePN->addIncoming(SwitchConstant, Pred);
2138 SwitchOnDispatch->addCase(SwitchConstant, CaseBB);
2145 for (
auto &BB :
F) {
2146 for (
auto &Phi : BB.
phis()) {
2147 if (Phi.getNumIncomingValues() == 1) {
2153 while (!Worklist.
empty()) {
2155 auto *OriginalValue = Phi->getIncomingValue(0);
2156 Phi->replaceAllUsesWith(OriginalValue);
2184 if (
auto *CleanupPad =
2189 dyn_cast<CatchSwitchInst>(Pred->getTerminator())) {
2192 assert(CS->getUnwindDest() == &BB);
2202 if ((LandingPad = dyn_cast_or_null<LandingPadInst>(BB.
getFirstNonPHI()))) {
2216 IncomingBB->setName(BB.
getName() +
Twine(
".from.") + Pred->getName());
2234 if (
auto *PN = dyn_cast<PHINode>(&BB.
front()))
2235 if (PN->getNumIncomingValues() > 1)
2246 return (isa<CastInst>(&V) || isa<GetElementPtrInst>(&V) ||
2247 isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<SelectInst>(&V));
2253 return isa<CoroIdInst>(&
I) || isa<CoroSaveInst>(&
I) ||
2254 isa<CoroSuspendInst>(&
I);
2276 for (
const auto &
E : AllRemats) {
2279 RematGraph *RG =
E.second.get();
2287 auto InsertPoint = &*
Use->getParent()->getFirstInsertionPt();
2288 if (isa<AnyCoroSuspendInst>(
Use)) {
2290 Use->getParent()->getSinglePredecessor();
2291 assert(SuspendPredecessorBlock &&
"malformed coro suspend instruction");
2299 for (;
I != RPOT.
end(); ++
I) {
2301 CurrentMaterialization =
D->clone();
2302 CurrentMaterialization->
setName(
D->getName());
2304 InsertPoint = CurrentMaterialization;
2308 for (
auto &
I : InstructionsToProcess)
2309 I->replaceUsesOfWith(
D, CurrentMaterialization);
2314 for (
unsigned i = 0,
E =
Use->getNumOperands(); i !=
E; ++i)
2315 if (
Use->getOperand(i) ==
D)
2317 {
Use,
D, CurrentMaterialization});
2319 InstructionsToProcess.push_back(CurrentMaterialization);
2324 for (
auto &R : FinalInstructionsToProcess) {
2325 if (
auto *PN = dyn_cast<PHINode>(R.Use)) {
2326 assert(PN->getNumIncomingValues() == 1 &&
"unexpected number of incoming "
2327 "values in the PHINode");
2328 PN->replaceAllUsesWith(R.Remat);
2329 PN->eraseFromParent();
2332 R.Use->replaceUsesOfWith(R.Def, R.Remat);
2339 auto *BB =
I->getParent();
2357 return isa<AnyCoroSuspendInst>(BB->
front());
2392 if (
auto FI = dyn_cast<CoroAllocaFreeInst>(
User))
2393 VisitedOrFreeBBs.
insert(FI->getParent());
2402 unsigned depth = 3) {
2405 if (depth == 0)
return false;
2424 for (
auto *U : AI->
users()) {
2425 auto FI = dyn_cast<CoroAllocaFreeInst>(U);
2440 for (
auto *AI : LocalAllocas) {
2446 Value *StackSave =
nullptr;
2448 StackSave =
Builder.CreateCall(
2452 auto Alloca =
Builder.CreateAlloca(
Builder.getInt8Ty(), AI->getSize());
2455 for (
auto *U : AI->
users()) {
2457 if (isa<CoroAllocaGetInst>(U)) {
2458 U->replaceAllUsesWith(Alloca);
2464 auto FI = cast<CoroAllocaFreeInst>(U);
2472 DeadInsts.
push_back(cast<Instruction>(U));
2489 if (isa<CoroAllocaGetInst>(U)) {
2490 U->replaceAllUsesWith(Alloc);
2492 auto FI = cast<CoroAllocaFreeInst>(U);
2496 DeadInsts.
push_back(cast<Instruction>(U));
2503 return cast<Instruction>(Alloc);
2510 auto FnTy = FunctionType::get(ValueTy, {},
false);
2513 auto Call =
Builder.CreateCall(FnTy, Fn, {});
2525 auto FnTy = FunctionType::get(V->getType()->getPointerTo(),
2526 {V->getType()},
false);
2529 auto Call =
Builder.CreateCall(FnTy, Fn, { V });
2548 auto ValueBeforeCall =
Builder.CreateLoad(ValueTy, Alloca);
2554 if (isa<CallInst>(Call)) {
2555 Builder.SetInsertPoint(Call->getNextNode());
2557 auto Invoke = cast<InvokeInst>(Call);
2558 Builder.SetInsertPoint(Invoke->getNormalDest()->getFirstNonPHIOrDbg());
2563 Builder.CreateStore(ValueAfterCall, Alloca);
2576 if (isa<LoadInst>(
User) || isa<StoreInst>(
User))
2580 auto Call = cast<Instruction>(
User);
2601 auto ArgTy = cast<PointerType>(
Arg.getType());
2604 auto ValueTy = ArgTy->isOpaque() ? PointerType::getUnqual(
F.getContext())
2605 : ArgTy->getNonOpaquePointerElementType();
2610 auto Alloca =
Builder.CreateAlloca(ValueTy, ArgTy->getAddressSpace());
2611 Arg.replaceAllUsesWith(Alloca);
2615 Builder.CreateStore(InitialValue, Alloca);
2625 auto FinalValue =
Builder.CreateLoad(ValueTy, Alloca);
2640 for (
auto &
Arg :
F.args()) {
2641 if (!
Arg.hasSwiftErrorAttr())
continue;
2648 for (
auto &Inst :
F.getEntryBlock()) {
2649 auto Alloca = dyn_cast<AllocaInst>(&Inst);
2661 if (!AllocasToPromote.
empty()) {
2670 const FrameDataInfo &FrameData,
2678 for (
auto *Def : FrameData.getAllDefs()) {
2679 for (
User *U : Def->users()) {
2680 auto Inst = cast<Instruction>(U);
2681 if (Inst->getParent() != CoroBegin->
getParent() ||
2689 while (!Worklist.
empty()) {
2691 for (
User *U : Def->users()) {
2692 auto Inst = cast<Instruction>(U);
2717 SuspendCrossingInfo &Checker) {
2725 DomSet.
insert(&
F.getEntryBlock());
2729 "should have split coro.suspend into its own block");
2743 if (
auto* II = dyn_cast<IntrinsicInst>(
I))
2753 if (!U->hasOneUse() || U->stripPointerCasts() != AI)
2769 Checker.isDefinitionAcrossSuspend(DomBB, UI)) {
2772 if (collectLifetimeStart(UI, AI))
2780 if (Valid && Lifetimes.
size() != 0) {
2783 if (isa<AllocaInst>(Lifetimes[0]->getOperand(1)))
2787 DomBB->getTerminator());
2790 auto *NewLifetime = Lifetimes[0]->clone();
2791 NewLifetime->replaceUsesOfWith(NewLifetime->getOperand(1), NewBitCast);
2792 NewLifetime->insertBefore(DomBB->getTerminator());
2796 S->eraseFromParent();
2805 const SuspendCrossingInfo &Checker,
2819 bool ShouldUseLifetimeStartInfo =
2820 (Shape.
ABI != coro::ABI::Async && Shape.
ABI != coro::ABI::Retcon &&
2821 Shape.
ABI != coro::ABI::RetconOnce);
2824 ShouldUseLifetimeStartInfo};
2825 Visitor.visitPtr(*AI);
2826 if (!Visitor.getShouldLiveOnFrame())
2829 Visitor.getMayWriteBeforeCoroBegin());
2837 auto InsertPt =
F->getEntryBlock().getFirstInsertionPt();
2838 while (isa<IntrinsicInst>(InsertPt))
2840 Builder.SetInsertPoint(&
F->getEntryBlock(), InsertPt);
2844 bool SkipOutermostLoad = !isa<DbgValueInst>(DVI);
2846 Value *OriginalStorage = Storage;
2848 while (
auto *Inst = dyn_cast_or_null<Instruction>(Storage)) {
2849 if (
auto *LdInst = dyn_cast<LoadInst>(Inst)) {
2850 Storage = LdInst->getPointerOperand();
2857 if (!SkipOutermostLoad)
2859 }
else if (
auto *StInst = dyn_cast<StoreInst>(Inst)) {
2860 Storage = StInst->getValueOperand();
2867 if (!Op || !AdditionalValues.
empty()) {
2875 SkipOutermostLoad =
false;
2880 auto *StorageAsArg = dyn_cast<Argument>(Storage);
2881 const bool IsSwiftAsyncArg =
2882 StorageAsArg && StorageAsArg->hasAttribute(Attribute::SwiftAsync);
2894 if (StorageAsArg && !OptimizeFrame && !IsSwiftAsyncArg) {
2895 auto &Cached = ArgToAllocaMap[StorageAsArg];
2898 Storage->
getName() +
".debug");
2899 Builder.CreateStore(Storage, Cached);
2917 if (isa<DbgDeclareInst>(DVI)) {
2919 if (
auto *
I = dyn_cast<Instruction>(Storage))
2920 InsertPt =
I->getInsertionPointAfterDef();
2921 else if (isa<Argument>(Storage))
2922 InsertPt = &*
F->getEntryBlock().begin();
2929 Function &
F, SuspendCrossingInfo &Checker,
2930 const std::function<
bool(
Instruction &)> &MaterializableCallback) {
2940 if (!MaterializableCallback(
I))
2942 for (
User *U :
I.users())
2943 if (Checker.isDefinitionAcrossSuspend(
I, U))
2944 Spills[&
I].push_back(cast<Instruction>(U));
2963 for (
auto &
E : Spills) {
2967 if (AllRemats.
count(U))
2972 std::make_unique<RematGraph>(MaterializableCallback, U, Checker);
2976 for (
auto I = RPOT.begin();
I != RPOT.end();
2977 ++
I) { (*I)->Node->dump(); }
dbgs()
2980 AllRemats[U] = std::move(RematUPtr);
2992 const std::function<
bool(
Instruction &)> &MaterializableCallback) {
2997 if (
Shape.
ABI == coro::ABI::Switch &&
3006 if (
auto *Save = CSI->getCoroSave())
3019 if (
auto *AsyncEnd = dyn_cast<CoroAsyncEndInst>(CE)) {
3020 auto *MustTailCallFn = AsyncEnd->getMustTailCallFunction();
3021 if (!MustTailCallFn)
3041 SuspendCrossingInfo Checker(
F,
Shape);
3045 FrameDataInfo FrameData;
3049 Shape.
ABI != coro::ABI::RetconOnce)
3054 for (
User *U :
A.users())
3055 if (Checker.isDefinitionAcrossSuspend(
A, U))
3056 FrameData.Spills[&
A].push_back(cast<Instruction>(U));
3066 if (
auto AI = dyn_cast<CoroAllocaAllocInst>(&
I)) {
3080 for (
User *U : Alloc->users()) {
3081 if (Checker.isDefinitionAcrossSuspend(*Alloc, U))
3082 FrameData.Spills[Alloc].push_back(cast<Instruction>(U));
3088 if (isa<CoroAllocaGetInst>(
I))
3091 if (
auto *AI = dyn_cast<AllocaInst>(&
I)) {
3096 for (
User *U :
I.users())
3097 if (Checker.isDefinitionAcrossSuspend(
I, U)) {
3099 if (
I.getType()->isTokenTy())
3101 "token definition is separated from the use by a suspend point");
3102 FrameData.Spills[&
I].push_back(cast<Instruction>(U));
3112 for (
auto &Iter : FrameData.Spills) {
3113 auto *V = Iter.first;
3117 if (Checker.isDefinitionAcrossSuspend(*V, DVI))
3118 FrameData.Spills[V].push_back(DVI);
3122 if (
Shape.
ABI == coro::ABI::Retcon ||
Shape.
ABI == coro::ABI::RetconOnce ||
3132 for (
auto *
I : DeadInstructions)
3133 I->eraseFromParent();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
AMDGPU Lower Kernel Arguments
This file implements the BitVector class.
BlockVerifier::State From
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")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static void cleanupSinglePredPHIs(Function &F)
static bool isSuspendReachableFrom(BasicBlock *From, VisitedBlocksSet &VisitedOrFreeBBs)
Does control flow starting at the given block ever reach a suspend instruction before reaching a bloc...
static bool isCoroutineStructureIntrinsic(Instruction &I)
SmallPtrSet< BasicBlock *, 8 > VisitedBlocksSet
static void createFramePtr(coro::Shape &Shape)
static Instruction * lowerNonLocalAlloca(CoroAllocaAllocInst *AI, coro::Shape &Shape, SmallVectorImpl< Instruction * > &DeadInsts)
Turn the given coro.alloca.alloc call into a dynamic allocation.
static Instruction * splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch)
static void eliminateSwiftError(Function &F, coro::Shape &Shape)
Eliminate all problematic uses of swifterror arguments and allocas from the function.
static void lowerLocalAllocas(ArrayRef< CoroAllocaAllocInst * > LocalAllocas, SmallVectorImpl< Instruction * > &DeadInsts)
Turn each of the given local allocas into a normal (dynamic) alloca instruction.
static bool isLocalAlloca(CoroAllocaAllocInst *AI)
Is the given alloca "local", i.e.
static Value * emitSetSwiftErrorValue(IRBuilder<> &Builder, Value *V, coro::Shape &Shape)
Set the given value as the current swifterror value.
static Value * emitSetAndGetSwiftErrorValueAround(Instruction *Call, AllocaInst *Alloca, coro::Shape &Shape)
Set the swifterror value from the given alloca before a call, then put in back in the alloca afterwar...
static void cacheDIVar(FrameDataInfo &FrameData, DenseMap< Value *, DILocalVariable * > &DIVarCache)
static void collectFrameAlloca(AllocaInst *AI, coro::Shape &Shape, const SuspendCrossingInfo &Checker, SmallVectorImpl< AllocaInfo > &Allocas, const DominatorTree &DT)
static bool localAllocaNeedsStackSave(CoroAllocaAllocInst *AI)
static void splitAround(Instruction *I, const Twine &Name)
static void eliminateSwiftErrorAlloca(Function &F, AllocaInst *Alloca, coro::Shape &Shape)
Eliminate a formerly-swifterror alloca by inserting the get/set intrinsics and attempting to MemToReg...
static void rewritePHIs(BasicBlock &BB)
static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB, BasicBlock *InsertedBB, BasicBlock *PredBB, PHINode *UntilPHI=nullptr)
static DIType * solveDIType(DIBuilder &Builder, Type *Ty, const DataLayout &Layout, DIScope *Scope, unsigned LineNum, DenseMap< Type *, DIType * > &DITypeCache)
static bool willLeaveFunctionImmediatelyAfter(BasicBlock *BB, unsigned depth=3)
After we split the coroutine, will the given basic block be along an obvious exit path for the resump...
static void eliminateSwiftErrorArgument(Function &F, Argument &Arg, coro::Shape &Shape, SmallVectorImpl< AllocaInst * > &AllocasToPromote)
"Eliminate" a swifterror argument by reducing it to the alloca case and then loading and storing in t...
static void buildFrameDebugInfo(Function &F, coro::Shape &Shape, FrameDataInfo &FrameData)
Build artificial debug info for C++ coroutine frames to allow users to inspect the contents of the fr...
static StructType * buildFrameType(Function &F, coro::Shape &Shape, FrameDataInfo &FrameData)
static BasicBlock * splitBlockIfNotFirst(Instruction *I, const Twine &Name)
static void sinkSpillUsesAfterCoroBegin(Function &F, const FrameDataInfo &FrameData, CoroBeginInst *CoroBegin)
retcon and retcon.once conventions assume that all spill uses can be sunk after the coro....
static void sinkLifetimeStartMarkers(Function &F, coro::Shape &Shape, SuspendCrossingInfo &Checker)
For each local variable that all of its user are only used inside one of suspended region,...
static bool isSuspendBlock(BasicBlock *BB)
static void rewritePHIsForCleanupPad(BasicBlock *CleanupPadBB, CleanupPadInst *CleanupPad)
static void rewriteMaterializableInstructions(const SmallMapVector< Instruction *, std::unique_ptr< RematGraph >, 8 > &AllRemats)
static void dumpAllocas(const SmallVectorImpl< AllocaInfo > &Allocas)
static StringRef solveTypeName(Type *Ty)
Create name for Type.
static void dumpSpills(StringRef Title, const SpillInfo &Spills)
static void doRematerializations(Function &F, SuspendCrossingInfo &Checker, const std::function< bool(Instruction &)> &MaterializableCallback)
static Value * emitGetSwiftErrorValue(IRBuilder<> &Builder, Type *ValueTy, coro::Shape &Shape)
Get the current swifterror value.
static void dumpRemats(StringRef Title, const SmallMapVector< Instruction *, std::unique_ptr< RematGraph >, 8 > &RM)
static void insertSpills(const FrameDataInfo &FrameData, coro::Shape &Shape)
Given that RA is a live value
static bool isLifetimeStart(const Instruction *Inst)
static MaybeAlign getAlign(Value *Ptr)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
mir Rename Register Operands
print must be executed print the must be executed context for all instructions
This file provides an interface for laying out a sequence of fields as a struct in a way that attempt...
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file provides a collection of visitors which walk the (instruction) uses of a pointer.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallString class.
static const unsigned FramePtr
This class represents a conversion between pointers from one address space to another.
an instruction to allocate memory on the stack
bool isSwiftError() const
Return true if this alloca is used as a swifterror argument to a call.
void setSwiftError(bool V)
Specify whether this alloca is used to represent a swifterror.
Align getAlign() const
Return the alignment of the memory that is being allocated by the instruction.
PointerType * getType() const
Overload to return most specific pointer type.
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1.
void setAlignment(Align Align)
const Value * getArraySize() const
Get the number of elements allocated.
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),...
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVMContext & getContext() const
Get the context in which this basic block lives.
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.
size_type size() const
size - Returns the number of bits in this bitvector.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Value * getArgOperand(unsigned i) const
unsigned arg_size() const
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Value * getParentPad() const
static CleanupPadInst * Create(Value *ParentPad, ArrayRef< Value * > Args=std::nullopt, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
This represents the llvm.coro.alloca.alloc instruction.
This class represents the llvm.coro.begin instruction.
This represents the llvm.coro.suspend instruction.
DICompositeType * createStructType(DIScope *Scope, StringRef Name, DIFile *File, unsigned LineNumber, uint64_t SizeInBits, uint32_t AlignInBits, DINode::DIFlags Flags, DIType *DerivedFrom, DINodeArray Elements, unsigned RunTimeLang=0, DIType *VTableHolder=nullptr, StringRef UniqueIdentifier="")
Create debugging information entry for a struct.
DIDerivedType * createPointerType(DIType *PointeeTy, uint64_t SizeInBits, uint32_t AlignInBits=0, std::optional< unsigned > DWARFAddressSpace=std::nullopt, StringRef Name="", DINodeArray Annotations=nullptr)
Create debugging information entry for a pointer.
DIExpression * createExpression(ArrayRef< uint64_t > Addr=std::nullopt)
Create a new descriptor for the specified variable which has a complex address expression for its add...
DIBasicType * createBasicType(StringRef Name, uint64_t SizeInBits, unsigned Encoding, DINode::DIFlags Flags=DINode::FlagZero)
Create debugging information entry for a basic type.
DINodeArray getOrCreateArray(ArrayRef< Metadata * > Elements)
Get a DINodeArray, create one if required.
DIDerivedType * createMemberType(DIScope *Scope, StringRef Name, DIFile *File, unsigned LineNo, uint64_t SizeInBits, uint32_t AlignInBits, uint64_t OffsetInBits, DINode::DIFlags Flags, DIType *Ty, DINodeArray Annotations=nullptr)
Create debugging information entry for a member.
DILocalVariable * createAutoVariable(DIScope *Scope, StringRef Name, DIFile *File, unsigned LineNo, DIType *Ty, bool AlwaysPreserve=false, DINode::DIFlags Flags=DINode::FlagZero, uint32_t AlignInBits=0)
Create a new descriptor for an auto variable.
void replaceArrays(DICompositeType *&T, DINodeArray Elements, DINodeArray TParams=DINodeArray())
Replace arrays on a composite type.
bool isEntryValue() const
Check if the expression consists of exactly one entry value operand.
static DIExpression * appendOpsToArg(const DIExpression *Expr, ArrayRef< uint64_t > Ops, unsigned ArgNo, bool StackValue=false)
Create a copy of Expr by appending the given list of Ops to each instance of the operand DW_OP_LLVM_a...
uint64_t getNumLocationOperands() const
Return the number of unique location operands referred to (via DW_OP_LLVM_arg) in this expression; th...
static DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...
DILocalScope * getScope() const
Get the local scope for this variable.
Base class for scope-like contexts.
StringRef getName() const
uint64_t getSizeInBits() const
uint32_t getAlignInBits() const
A parsed version of the target data layout string in and methods for querying it.
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Align getABITypeAlign(Type *Ty) const
Returns the minimum ABI-required alignment for the specified type.
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Align getPrefTypeAlign(Type *Ty) const
Returns the preferred stack/global alignment for the specified type.
This represents the llvm.dbg.declare instruction.
This represents the llvm.dbg.value instruction.
This is the common base class for debug info intrinsics for variables.
void replaceVariableLocationOp(Value *OldValue, Value *NewValue)
Value * getVariableLocationOp(unsigned OpIdx) const
void setExpression(DIExpression *NewExpr)
DILocalVariable * getVariable() const
DIExpression * getExpression() const
DILocation * get() const
Get the underlying DILocation.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void visitIntrinsicInst(IntrinsicInst &I)
void visitBitCastInst(BitCastInst &I)
void visit(Iterator Start, Iterator End)
void visitPHINode(PHINode &I)
void visitAddrSpaceCastInst(AddrSpaceCastInst &I)
void visitSelectInst(SelectInst &I)
void visitGetElementPtrInst(GetElementPtrInst &I)
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
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
const Function * getFunction() const
Return the function this instruction belongs to.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
This is an important class for using LLVM in a threaded context.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
static MDString * get(LLVMContext &Context, StringRef Str)
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
size_type count(const KeyT &Key) const
This is the common base class for memset/memcpy/memmove.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
A base class for visitors over the uses of a pointer value.
void visitCallBase(CallBase &CB)
void visitGetElementPtrInst(GetElementPtrInst &GEPI)
void visitAddrSpaceCastInst(AddrSpaceCastInst &ASC)
void visitBitCastInst(BitCastInst &BC)
void visitStoreInst(StoreInst &SI)
void visitIntrinsicInst(IntrinsicInst &II)
void visitMemIntrinsic(MemIntrinsic &I)
This class represents the LLVM 'select' instruction.
bool insert(const value_type &X)
Insert a new element into the SetVector.
iterator begin()
Get an iterator to the beginning of the SetVector.
iterator end()
Get an iterator to the end of the SetVector.
iterator find(ConstPtrType Ptr) const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...
StringRef str() const
Explicit conversion to StringRef.
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.
Compute live ranges of allocas.
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.
TypeSize getElementOffsetInBits(unsigned Idx) const
Class to represent struct types.
void setBody(ArrayRef< Type * > Elements, bool isPacked=false)
Specify a body for an opaque identified type.
static StructType * create(LLVMContext &Context, StringRef Name)
This creates an identified struct.
unsigned getNumElements() const
Random access to the elements.
Type * getElementType(unsigned N) const
void setDefaultDest(BasicBlock *DefaultCase)
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
std::string str() const
Return the twine contents as a std::string.
StringRef toStringRef(SmallVectorImpl< char > &Out) const
This returns the twine as a single StringRef if it can be represented as such.
static constexpr TypeSize Fixed(ScalarTy ExactSize)
The instances of the Type class are immutable: once they are created, they are never changed.
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
bool isPointerTy() const
True if this is an instance of PointerType.
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
Type * getNonOpaquePointerElementType() const
Only use this method in code that is not reachable with opaque pointers, or part of deprecated method...
StringRef getStructName() const
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
static Type * getVoidTy(LLVMContext &C)
bool isStructTy() const
True if this is an instance of StructType.
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
static IntegerType * getInt8Ty(LLVMContext &C)
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
User * getUser() const
Returns the User that contains this Use.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
APInt Offset
The constant offset of the use if that is known.
void enqueueUsers(Instruction &I)
Enqueue the users of this instruction in the visit worklist.
constexpr ScalarTy getFixedValue() const
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
A range adaptor for a pair of iterators.
A raw_ostream that writes to an SmallVector or SmallString.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
@ CE
Windows NT (Windows on ARM)
void salvageDebugInfo(SmallDenseMap< Argument *, AllocaInst *, 4 > &ArgToAllocaMap, DbgVariableIntrinsic *DVI, bool OptimizeFrame)
Attempts to rewrite the location operand of debug intrinsics in terms of the coroutine frame pointer,...
void buildCoroutineFrame(Function &F, Shape &Shape, const std::function< bool(Instruction &)> &MaterializableCallback)
bool defaultMaterializable(Instruction &V)
Default materializable callback.
CallInst * createMustTailCall(DebugLoc Loc, Function *MustTailCallFn, ArrayRef< Value * > Arguments, IRBuilder<> &)
bool isCPlusPlus(SourceLanguage S)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
TinyPtrVector< DbgDeclareInst * > FindDbgDeclareUses(Value *V)
Finds dbg.declare intrinsics declaring local variables as living in the memory that 'V' points to.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
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...
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
unsigned Log2_64_Ceil(uint64_t Value)
Return the ceil log base 2 of the specified value, 64 if the value is zero.
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
auto successors(const MachineBasicBlock *BB)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
bool isAllocaPromotable(const AllocaInst *AI)
Return true if this alloca is legal for promotion.
static Error getOffset(const SymbolRef &Sym, SectionRef Sec, uint64_t &Result)
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 findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
BasicBlock * ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, LandingPadInst *OriginalPad=nullptr, PHINode *LandingPadReplacement=nullptr, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
Split the edge connect the specficed blocks in the case that Succ is an Exception Handling Block.
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Value * salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Ops, SmallVectorImpl< Value * > &AdditionalValues)
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
std::pair< uint64_t, Align > performOptimizedStructLayout(MutableArrayRef< OptimizedStructLayoutField > Fields)
Compute a layout for a struct containing the given fields, making a best-effort attempt to minimize t...
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
constexpr unsigned BitWidth
void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, BasicBlock *NewPred, PHINode *Until=nullptr)
Replaces all uses of OldPred with the NewPred block in all PHINodes in a block.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
auto predecessors(const MachineBasicBlock *BB)
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ)
Sets the unwind edge of an instruction to a particular successor.
unsigned pred_size(const MachineBasicBlock *BB)
This struct is a compact representation of a valid (non-zero power of two) alignment.
uint64_t value() const
This is a hole in the type system and should not be abused.
RematGraph::RematNode * NodeRef
static ChildIteratorType child_end(NodeRef N)
RematGraph::RematNode ** ChildIteratorType
static NodeRef getEntryNode(RematGraph *G)
static ChildIteratorType child_begin(NodeRef N)
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Align Alignment
The required alignment of this field.
uint64_t Offset
The offset of this field in the final layout.
uint64_t Size
The required size of this field in bytes.
static constexpr uint64_t FlexibleOffset
A special value for Offset indicating that the field can be moved anywhere.
A MapVector that performs no allocations if smaller than a certain size.
Align getContextAlignment() const
uint64_t ContextHeaderSize
bool IsFrameInlineInStorage
AllocaInst * PromiseAlloca
AsyncLoweringStorage AsyncLowering
AnyCoroIdRetconInst * getRetconCoroId() const
CoroIdInst * getSwitchCoroId() const
Instruction * getInsertPtAfterFramePtr() const
SmallVector< AnyCoroSuspendInst *, 4 > CoroSuspends
Value * emitAlloc(IRBuilder<> &Builder, Value *Size, CallGraph *CG) const
Allocate memory according to the rules of the active lowering.
SmallVector< CallInst *, 2 > SwiftErrorOps
AllocaInst * getPromiseAlloca() const
bool OptimizeFrame
This would only be true if optimization are enabled.
SwitchLoweringStorage SwitchLowering
CoroBeginInst * CoroBegin
void emitDealloc(IRBuilder<> &Builder, Value *Ptr, CallGraph *CG) const
Deallocate memory according to the rules of the active lowering.
RetconLoweringStorage RetconLowering
SmallVector< AnyCoroEndInst *, 4 > CoroEnds
BasicBlock * AllocaSpillBlock