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 CFG including adding/removing BBs due to its use of BB
12// ptrs in the BlockToIndexMapping.
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Coroutines/SuspendCrossingInfo.h"
16#include "llvm/IR/ModuleSlotTracker.h"
17
18// The "coro-suspend-crossing" flag is very noisy. There is another debug type,
19// "coro-frame", which results in leaner debug spew.
20#define DEBUG_TYPE "coro-suspend-crossing"
21
22namespace llvm {
23#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
24static void dumpBasicBlockLabel(const BasicBlock *BB, ModuleSlotTracker &MST) {
25 if (BB->hasName()) {
26 dbgs() << BB->getName();
27 return;
28 }
29
30 dbgs() << MST.getLocalSlot(BB);
31}
32
33LLVM_DUMP_METHOD void
34SuspendCrossingInfo::dump(StringRef Label, BitVector const &BV,
35 const ReversePostOrderTraversal<Function *> &RPOT,
36 ModuleSlotTracker &MST) const {
37 dbgs() << Label << ":";
38 for (const BasicBlock *BB : RPOT) {
39 auto BBNo = Mapping.blockToIndex(BB);
40 if (BV[BBNo]) {
41 dbgs() << " ";
42 dumpBasicBlockLabel(BB, MST);
43 }
44 }
45 dbgs() << "\n";
46}
47
48LLVM_DUMP_METHOD void SuspendCrossingInfo::dump() const {
49 if (Block.empty())
50 return;
51
52 BasicBlock *const B = Mapping.indexToBlock(0);
53 Function *F = B->getParent();
54
55 ModuleSlotTracker MST(F->getParent());
56 MST.incorporateFunction(*F);
57
58 ReversePostOrderTraversal<Function *> RPOT(F);
59 for (const BasicBlock *BB : RPOT) {
60 auto BBNo = Mapping.blockToIndex(BB);
61 dumpBasicBlockLabel(BB, MST);
62 dbgs() << ":\n";
63 dump(" Consumes", Block[BBNo].Consumes, RPOT, MST);
64 dump(" Kills", Block[BBNo].Kills, RPOT, MST);
65 }
66 dbgs() << "\n";
67}
68#endif
69
70bool SuspendCrossingInfo::hasPathCrossingSuspendPoint(BasicBlock *From,
71 BasicBlock *To) const {
72 size_t const FromIndex = Mapping.blockToIndex(BB: From);
73 size_t const ToIndex = Mapping.blockToIndex(BB: To);
74 bool const Result = Block[ToIndex].Kills[FromIndex];
75 LLVM_DEBUG(if (Result) dbgs() << From->getName() << " => " << To->getName()
76 << " crosses suspend point\n");
77 return Result;
78}
79
80bool SuspendCrossingInfo::hasPathOrLoopCrossingSuspendPoint(
81 BasicBlock *From, BasicBlock *To) const {
82 size_t const FromIndex = Mapping.blockToIndex(BB: From);
83 size_t const ToIndex = Mapping.blockToIndex(BB: To);
84 bool Result = Block[ToIndex].Kills[FromIndex] ||
85 (From == To && Block[ToIndex].KillLoop);
86 LLVM_DEBUG(if (Result) dbgs() << From->getName() << " => " << To->getName()
87 << " crosses suspend point (path or loop)\n");
88 return Result;
89}
90
91template <bool Initialize>
92bool SuspendCrossingInfo::computeBlockData(
93 const ReversePostOrderTraversal<Function *> &RPOT) {
94 bool Changed = false;
95
96 for (const BasicBlock *BB : RPOT) {
97 auto BBNo = Mapping.blockToIndex(BB);
98 auto &B = Block[BBNo];
99
100 // We don't need to count the predecessors when initialization.
101 if constexpr (!Initialize)
102 // If all the predecessors of the current Block don't change,
103 // the BlockData for the current block must not change too.
104 if (all_of(predecessors(BD: B), [this](BasicBlock *BB) {
105 return !Block[Mapping.blockToIndex(BB)].Changed;
106 })) {
107 B.Changed = false;
108 continue;
109 }
110
111 // Saved Consumes and Kills bitsets so that it is easy to see
112 // if anything changed after propagation.
113 auto SavedConsumes = B.Consumes;
114 auto SavedKills = B.Kills;
115
116 for (BasicBlock *PI : predecessors(BD: B)) {
117 auto PrevNo = Mapping.blockToIndex(BB: PI);
118 auto &P = Block[PrevNo];
119
120 // Propagate Kills and Consumes from predecessors into B.
121 B.Consumes |= P.Consumes;
122 B.Kills |= P.Kills;
123
124 if (P.isAlwaysKill())
125 B.Kills |= P.Consumes;
126 }
127
128 if (B.isAlwaysKill()) {
129 B.Kills |= B.Consumes;
130 } else if (B.isNeverKill()) {
131 B.Kills.reset();
132 } else {
133 // This is reached when B block it not Suspend nor coro.end and it
134 // need to make sure that it is not in the kill set.
135 B.KillLoop |= B.Kills[BBNo];
136 B.Kills.reset(Idx: BBNo);
137 }
138
139 if constexpr (!Initialize) {
140 B.Changed = (B.Kills != SavedKills) || (B.Consumes != SavedConsumes);
141 Changed |= B.Changed;
142 }
143 }
144
145 return Changed;
146}
147
148SuspendCrossingInfo::SuspendCrossingInfo(Function &F, const coro::Shape &Shape)
149 : Mapping(F) {
150 const size_t N = Mapping.size();
151 Block.resize(N);
152
153 // Initialize every block so that it consumes itself
154 for (size_t I = 0; I < N; ++I) {
155 auto &B = Block[I];
156 B.Consumes.resize(N);
157 B.Kills.resize(N);
158 B.Consumes.set(I);
159 B.Changed = true;
160 }
161
162 // Mark all CoroEnd Blocks. We do not propagate Kills beyond coro.ends as
163 // the code beyond coro.end is reachable during initial invocation of the
164 // coroutine.
165 for (auto *CE : Shape.CoroEnds) {
166 // Verify CoroEnd was normalized
167 assert(CE->getParent()->getFirstInsertionPt() == CE->getIterator() &&
168 CE->getParent()->size() <= 2 && "CoroEnd must be in its own BB");
169
170 getBlockData(BB: CE->getParent()).setNeverKill();
171 }
172
173 for (auto *InRamp : Shape.CoroIsInRampInsts)
174 for (auto *U : InRamp->users())
175 if (auto *Br = dyn_cast<CondBrInst>(Val: U)) {
176 auto *TrueBB = Br->getSuccessor(i: 0);
177 if (TrueBB->getSinglePredecessor())
178 getBlockData(BB: TrueBB).setNeverKill();
179 }
180
181 // Mark all suspend blocks and indicate that they kill everything they
182 // consume. Note, that crossing coro.save also requires a spill, as any code
183 // between coro.save and coro.suspend may resume the coroutine and all of the
184 // state needs to be saved by that time.
185 auto markSuspendBlock = [&](IntrinsicInst *BarrierInst) {
186 BasicBlock *SuspendBlock = BarrierInst->getParent();
187 auto &B = getBlockData(BB: SuspendBlock);
188 B.setAlwaysKill();
189 B.Kills |= B.Consumes;
190 };
191 for (auto *CSI : Shape.CoroSuspends) {
192 // Verify CoroSuspend was normalized
193 assert(CSI->getParent()->getFirstInsertionPt() == CSI->getIterator() &&
194 CSI->getParent()->size() <= 2 &&
195 "CoroSuspend must be in its own BB");
196
197 markSuspendBlock(CSI);
198 if (auto *Save = CSI->getCoroSave())
199 markSuspendBlock(Save);
200 }
201
202 // It is considered to be faster to use RPO traversal for forward-edges
203 // dataflow analysis.
204 ReversePostOrderTraversal<Function *> RPOT(&F);
205 computeBlockData</*Initialize=*/true>(RPOT);
206 while (computeBlockData</*Initialize*/ false>(RPOT))
207 ;
208
209 LLVM_DEBUG(dump());
210}
211
212} // namespace llvm
213