LLVM 24.0.0git
SuspendCrossingInfo.cpp
Go to the documentation of this file.
1//===- SuspendCrossingInfo.cpp - Utility for suspend crossing values ------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8// The SuspendCrossingInfo maintains data that allows to answer a question
9// whether given two BasicBlocks A and B there is a path from A to B that
10// passes through a suspend point. Note, SuspendCrossingInfo is invalidated
11// by changes to the block numbering.
12//===----------------------------------------------------------------------===//
13
16
17// The "coro-suspend-crossing" flag is very noisy. There is another debug type,
18// "coro-frame", which results in leaner debug spew.
19#define DEBUG_TYPE "coro-suspend-crossing"
20
21namespace llvm {
22#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
23static void dumpBasicBlockLabel(const BasicBlock *BB, ModuleSlotTracker &MST) {
24 if (BB->hasName()) {
25 dbgs() << BB->getName();
26 return;
27 }
28
29 dbgs() << MST.getLocalSlot(BB);
30}
31
35 ModuleSlotTracker &MST) const {
36 dbgs() << Label << ":";
37 for (const BasicBlock *BB : RPOT) {
38 if (BV[BB->getNumber()]) {
39 dbgs() << " ";
40 dumpBasicBlockLabel(BB, MST);
41 }
42 }
43 dbgs() << "\n";
44}
45
47 if (Block.empty())
48 return;
49
50 ModuleSlotTracker MST(F->getParent());
51 MST.incorporateFunction(*F);
52
54 for (const BasicBlock *BB : RPOT) {
55 dumpBasicBlockLabel(BB, MST);
56 dbgs() << ":\n";
57 dump(" Consumes", Block[BB->getNumber()].Consumes, RPOT, MST);
58 dump(" Kills", Block[BB->getNumber()].Kills, RPOT, MST);
59 }
60 dbgs() << "\n";
61}
62#endif
63
65 BasicBlock *To) const {
66 bool const Result = Block[To->getNumber()].Kills[From->getNumber()];
67 LLVM_DEBUG(if (Result) dbgs() << From->getName() << " => " << To->getName()
68 << " crosses suspend point\n");
69 return Result;
70}
71
73 BasicBlock *From, BasicBlock *To) const {
74 bool Result = Block[To->getNumber()].Kills[From->getNumber()] ||
75 (From == To && Block[To->getNumber()].KillLoop);
76 LLVM_DEBUG(if (Result) dbgs() << From->getName() << " => " << To->getName()
77 << " crosses suspend point (path or loop)\n");
78 return Result;
79}
80
81template <bool Initialize>
82bool SuspendCrossingInfo::computeBlockData(
84 bool Changed = false;
85
86 for (BasicBlock *BB : RPOT) {
87 auto &B = Block[BB->getNumber()];
88
89 // We don't need to count the predecessors when initialization.
90 if constexpr (!Initialize)
91 // If all the predecessors of the current Block don't change,
92 // the BlockData for the current block must not change too.
93 if (all_of(predecessors(BB), [this](BasicBlock *BB) {
94 return !Block[BB->getNumber()].Changed;
95 })) {
96 B.Changed = false;
97 continue;
98 }
99
100 // Saved Consumes and Kills bitsets so that it is easy to see
101 // if anything changed after propagation.
102 auto SavedConsumes = B.Consumes;
103 auto SavedKills = B.Kills;
104
105 for (BasicBlock *PI : predecessors(BB)) {
106 auto &P = Block[PI->getNumber()];
107
108 // Propagate Kills and Consumes from predecessors into B.
109 B.Consumes |= P.Consumes;
110 B.Kills |= P.Kills;
111
112 if (P.isAlwaysKill())
113 B.Kills |= P.Consumes;
114 }
115
116 if (B.isAlwaysKill()) {
117 B.Kills |= B.Consumes;
118 } else if (B.isNeverKill()) {
119 B.Kills.reset();
120 } else {
121 // This is reached when B block it not Suspend nor coro.end and it
122 // need to make sure that it is not in the kill set.
123 B.KillLoop |= B.Kills[BB->getNumber()];
124 B.Kills.reset(BB->getNumber());
125 }
126
127 if constexpr (!Initialize) {
128 B.Changed = (B.Kills != SavedKills) || (B.Consumes != SavedConsumes);
129 Changed |= B.Changed;
130 }
131 }
132
133 return Changed;
134}
135
137 : F(&F) {
138 const size_t N = F.getMaxBlockNumber();
139 Block.resize(N);
140
141 // Initialize every block so that it consumes itself
142 for (size_t I = 0; I < N; ++I) {
143 auto &B = Block[I];
144 B.Consumes.resize(N);
145 B.Kills.resize(N);
146 B.Consumes.set(I);
147 B.Changed = true;
148 }
149
150 // Mark all CoroEnd Blocks. We do not propagate Kills beyond coro.ends as
151 // the code beyond coro.end is reachable during initial invocation of the
152 // coroutine.
153 for (auto *CE : Shape.CoroEnds) {
154 // Verify CoroEnd was normalized
155 assert(CE->getParent()->getFirstInsertionPt() == CE->getIterator() &&
156 CE->getParent()->size() <= 2 && "CoroEnd must be in its own BB");
157
158 Block[CE->getParent()->getNumber()].setNeverKill();
159 }
160
161 for (auto *InRamp : Shape.CoroIsInRampInsts)
162 for (auto *U : InRamp->users())
163 if (auto *Br = dyn_cast<CondBrInst>(U)) {
164 auto *TrueBB = Br->getSuccessor(0);
165 if (TrueBB->getSinglePredecessor())
166 Block[TrueBB->getNumber()].setNeverKill();
167 }
168
169 // Mark all suspend blocks and indicate that they kill everything they
170 // consume. Note, that crossing coro.save also requires a spill, as any code
171 // between coro.save and coro.suspend may resume the coroutine and all of the
172 // state needs to be saved by that time.
173 auto markSuspendBlock = [&](IntrinsicInst *BarrierInst) {
174 BasicBlock *SuspendBlock = BarrierInst->getParent();
175 auto &B = Block[SuspendBlock->getNumber()];
176 B.setAlwaysKill();
177 B.Kills |= B.Consumes;
178 };
179 for (auto *CSI : Shape.CoroSuspends) {
180 // Verify CoroSuspend was normalized
181 assert(CSI->getParent()->getFirstInsertionPt() == CSI->getIterator() &&
182 CSI->getParent()->size() <= 2 &&
183 "CoroSuspend must be in its own BB");
184
185 markSuspendBlock(CSI);
186 if (auto *Save = CSI->getCoroSave())
187 markSuspendBlock(Save);
188 }
189
190 // It is considered to be faster to use RPO traversal for forward-edges
191 // dataflow analysis.
193 computeBlockData</*Initialize=*/true>(RPOT);
194 while (computeBlockData</*Initialize*/ false>(RPOT))
195 ;
196
197 LLVM_DEBUG(dump());
198}
199
200} // namespace llvm
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:702
#define I(x, y, z)
Definition MD5.cpp:57
#define P(N)
if(PassOpts->AAPipeline)
#define LLVM_DEBUG(...)
Definition Debug.h:119
LLVM Basic Block Representation.
Definition BasicBlock.h:62
unsigned getNumber() const
Definition BasicBlock.h:95
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
A wrapper class for inspecting calls to intrinsic functions.
Manage lifetime of a slot tracker for printing IR.
int getLocalSlot(const Value *V)
Return the slot number of the specified local value.
void incorporateFunction(const Function &F)
Incorporate the given function.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
LLVM_ABI bool hasPathCrossingSuspendPoint(BasicBlock *From, BasicBlock *To) const
Returns true if there is a path from From to To crossing a suspend point without crossing From a 2nd ...
LLVM_ABI bool hasPathOrLoopCrossingSuspendPoint(BasicBlock *From, BasicBlock *To) const
Returns true if there is a path from From to To crossing a suspend point without crossing From a 2nd ...
LLVM_ABI SuspendCrossingInfo(Function &F, const coro::Shape &Shape)
bool hasName() const
Definition Value.h:263
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
static void dumpBasicBlockLabel(const BasicBlock *BB, ModuleSlotTracker &MST)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
auto predecessors(const MachineBasicBlock *BB)
#define N
SmallVector< AnyCoroSuspendInst *, 4 > CoroSuspends
Definition CoroShape.h:60
SmallVector< CoroIsInRampInst *, 2 > CoroIsInRampInsts
Definition CoroShape.h:57
SmallVector< AnyCoroEndInst *, 4 > CoroEnds
Definition CoroShape.h:56