Bug Summary

File:lib/Transforms/Coroutines/CoroFrame.cpp
Warning:line 400, column 50
Called C++ object pointer is null

Annotated Source Code

1//===- CoroFrame.cpp - Builds and manipulates coroutine frame -------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9// This file contains classes used to discover if for a particular value
10// there from sue to definition that crosses a suspend block.
11//
12// Using the information discovered we form a Coroutine Frame structure to
13// contain those values. All uses of those values are replaced with appropriate
14// GEP + load from the coroutine frame. At the point of the definition we spill
15// the value into the coroutine frame.
16//
17// TODO: pack values tightly using liveness info.
18//===----------------------------------------------------------------------===//
19
20#include "CoroInternal.h"
21#include "llvm/ADT/BitVector.h"
22#include "llvm/IR/CFG.h"
23#include "llvm/IR/Dominators.h"
24#include "llvm/IR/IRBuilder.h"
25#include "llvm/IR/InstIterator.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/MathExtras.h"
28#include "llvm/Support/circular_raw_ostream.h"
29#include "llvm/Transforms/Utils/BasicBlockUtils.h"
30#include "llvm/Transforms/Utils/Local.h"
31
32using namespace llvm;
33
34// The "coro-suspend-crossing" flag is very noisy. There is another debug type,
35// "coro-frame", which results in leaner debug spew.
36#define DEBUG_TYPE"coro-frame" "coro-suspend-crossing"
37
38enum { SmallVectorThreshold = 32 };
39
40// Provides two way mapping between the blocks and numbers.
41namespace {
42class BlockToIndexMapping {
43 SmallVector<BasicBlock *, SmallVectorThreshold> V;
44
45public:
46 size_t size() const { return V.size(); }
47
48 BlockToIndexMapping(Function &F) {
49 for (BasicBlock &BB : F)
50 V.push_back(&BB);
51 std::sort(V.begin(), V.end());
52 }
53
54 size_t blockToIndex(BasicBlock *BB) const {
55 auto *I = std::lower_bound(V.begin(), V.end(), BB);
56 assert(I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block")((I != V.end() && *I == BB && "BasicBlockNumberng: Unknown block"
) ? static_cast<void> (0) : __assert_fail ("I != V.end() && *I == BB && \"BasicBlockNumberng: Unknown block\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 56, __PRETTY_FUNCTION__))
;
57 return I - V.begin();
58 }
59
60 BasicBlock *indexToBlock(unsigned Index) const { return V[Index]; }
61};
62} // end anonymous namespace
63
64// The SuspendCrossingInfo maintains data that allows to answer a question
65// whether given two BasicBlocks A and B there is a path from A to B that
66// passes through a suspend point.
67//
68// For every basic block 'i' it maintains a BlockData that consists of:
69// Consumes: a bit vector which contains a set of indices of blocks that can
70// reach block 'i'
71// Kills: a bit vector which contains a set of indices of blocks that can
72// reach block 'i', but one of the path will cross a suspend point
73// Suspend: a boolean indicating whether block 'i' contains a suspend point.
74// End: a boolean indicating whether block 'i' contains a coro.end intrinsic.
75//
76namespace {
77struct SuspendCrossingInfo {
78 BlockToIndexMapping Mapping;
79
80 struct BlockData {
81 BitVector Consumes;
82 BitVector Kills;
83 bool Suspend = false;
84 bool End = false;
85 };
86 SmallVector<BlockData, SmallVectorThreshold> Block;
87
88 iterator_range<succ_iterator> successors(BlockData const &BD) const {
89 BasicBlock *BB = Mapping.indexToBlock(&BD - &Block[0]);
90 return llvm::successors(BB);
91 }
92
93 BlockData &getBlockData(BasicBlock *BB) {
94 return Block[Mapping.blockToIndex(BB)];
95 }
96
97 void dump() const;
98 void dump(StringRef Label, BitVector const &BV) const;
99
100 SuspendCrossingInfo(Function &F, coro::Shape &Shape);
101
102 bool hasPathCrossingSuspendPoint(BasicBlock *DefBB, BasicBlock *UseBB) const {
103 size_t const DefIndex = Mapping.blockToIndex(DefBB);
104 size_t const UseIndex = Mapping.blockToIndex(UseBB);
105
106 assert(Block[UseIndex].Consumes[DefIndex] && "use must consume def")((Block[UseIndex].Consumes[DefIndex] && "use must consume def"
) ? static_cast<void> (0) : __assert_fail ("Block[UseIndex].Consumes[DefIndex] && \"use must consume def\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 106, __PRETTY_FUNCTION__))
;
107 bool const Result = Block[UseIndex].Kills[DefIndex];
108 DEBUG(dbgs() << UseBB->getName() << " => " << DefBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << UseBB->getName() <<
" => " << DefBB->getName() << " answer is "
<< Result << "\n"; } } while (false)
109 << " answer is " << Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << UseBB->getName() <<
" => " << DefBB->getName() << " answer is "
<< Result << "\n"; } } while (false)
;
110 return Result;
111 }
112
113 bool isDefinitionAcrossSuspend(BasicBlock *DefBB, User *U) const {
114 auto *I = cast<Instruction>(U);
115
116 // We rewrote PHINodes, so that only the ones with exactly one incoming
117 // value need to be analyzed.
118 if (auto *PN = dyn_cast<PHINode>(I))
119 if (PN->getNumIncomingValues() > 1)
120 return false;
121
122 BasicBlock *UseBB = I->getParent();
123 return hasPathCrossingSuspendPoint(DefBB, UseBB);
124 }
125
126 bool isDefinitionAcrossSuspend(Argument &A, User *U) const {
127 return isDefinitionAcrossSuspend(&A.getParent()->getEntryBlock(), U);
128 }
129
130 bool isDefinitionAcrossSuspend(Instruction &I, User *U) const {
131 return isDefinitionAcrossSuspend(I.getParent(), U);
132 }
133};
134} // end anonymous namespace
135
136#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
137LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SuspendCrossingInfo::dump(StringRef Label,
138 BitVector const &BV) const {
139 dbgs() << Label << ":";
140 for (size_t I = 0, N = BV.size(); I < N; ++I)
141 if (BV[I])
142 dbgs() << " " << Mapping.indexToBlock(I)->getName();
143 dbgs() << "\n";
144}
145
146LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SuspendCrossingInfo::dump() const {
147 for (size_t I = 0, N = Block.size(); I < N; ++I) {
148 BasicBlock *const B = Mapping.indexToBlock(I);
149 dbgs() << B->getName() << ":\n";
150 dump(" Consumes", Block[I].Consumes);
151 dump(" Kills", Block[I].Kills);
152 }
153 dbgs() << "\n";
154}
155#endif
156
157SuspendCrossingInfo::SuspendCrossingInfo(Function &F, coro::Shape &Shape)
158 : Mapping(F) {
159 const size_t N = Mapping.size();
160 Block.resize(N);
161
162 // Initialize every block so that it consumes itself
163 for (size_t I = 0; I < N; ++I) {
164 auto &B = Block[I];
165 B.Consumes.resize(N);
166 B.Kills.resize(N);
167 B.Consumes.set(I);
168 }
169
170 // Mark all CoroEnd Blocks. We do not propagate Kills beyond coro.ends as
171 // the code beyond coro.end is reachable during initial invocation of the
172 // coroutine.
173 for (auto *CE : Shape.CoroEnds)
174 getBlockData(CE->getParent()).End = true;
175
176 // Mark all suspend blocks and indicate that they kill everything they
177 // consume. Note, that crossing coro.save also requires a spill, as any code
178 // between coro.save and coro.suspend may resume the coroutine and all of the
179 // state needs to be saved by that time.
180 auto markSuspendBlock = [&](IntrinsicInst* BarrierInst) {
181 BasicBlock *SuspendBlock = BarrierInst->getParent();
182 auto &B = getBlockData(SuspendBlock);
183 B.Suspend = true;
184 B.Kills |= B.Consumes;
185 };
186 for (CoroSuspendInst *CSI : Shape.CoroSuspends) {
187 markSuspendBlock(CSI);
188 markSuspendBlock(CSI->getCoroSave());
189 }
190
191 // Iterate propagating consumes and kills until they stop changing.
192 int Iteration = 0;
193 (void)Iteration;
194
195 bool Changed;
196 do {
197 DEBUG(dbgs() << "iteration " << ++Iteration)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "iteration " << ++Iteration
; } } while (false)
;
198 DEBUG(dbgs() << "==============\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "==============\n"; } } while
(false)
;
199
200 Changed = false;
201 for (size_t I = 0; I < N; ++I) {
202 auto &B = Block[I];
203 for (BasicBlock *SI : successors(B)) {
204
205 auto SuccNo = Mapping.blockToIndex(SI);
206
207 // Saved Consumes and Kills bitsets so that it is easy to see
208 // if anything changed after propagation.
209 auto &S = Block[SuccNo];
210 auto SavedConsumes = S.Consumes;
211 auto SavedKills = S.Kills;
212
213 // Propagate Kills and Consumes from block B into its successor S.
214 S.Consumes |= B.Consumes;
215 S.Kills |= B.Kills;
216
217 // If block B is a suspend block, it should propagate kills into the
218 // its successor for every block B consumes.
219 if (B.Suspend) {
220 S.Kills |= B.Consumes;
221 }
222 if (S.Suspend) {
223 // If block S is a suspend block, it should kill all of the blocks it
224 // consumes.
225 S.Kills |= S.Consumes;
226 } else if (S.End) {
227 // If block S is an end block, it should not propagate kills as the
228 // blocks following coro.end() are reached during initial invocation
229 // of the coroutine while all the data are still available on the
230 // stack or in the registers.
231 S.Kills.reset();
232 } else {
233 // This is reached when S block it not Suspend nor coro.end and it
234 // need to make sure that it is not in the kill set.
235 S.Kills.reset(SuccNo);
236 }
237
238 // See if anything changed.
239 Changed |= (S.Kills != SavedKills) || (S.Consumes != SavedConsumes);
240
241 if (S.Kills != SavedKills) {
242 DEBUG(dbgs() << "\nblock " << I << " follower " << SI->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "\nblock " << I <<
" follower " << SI->getName() << "\n"; } } while
(false)
243 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "\nblock " << I <<
" follower " << SI->getName() << "\n"; } } while
(false)
;
244 DEBUG(dump("S.Kills", S.Kills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("S.Kills", S.Kills); } } while (false)
;
245 DEBUG(dump("SavedKills", SavedKills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("SavedKills", SavedKills); } } while (
false)
;
246 }
247 if (S.Consumes != SavedConsumes) {
248 DEBUG(dbgs() << "\nblock " << I << " follower " << SI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "\nblock " << I <<
" follower " << SI << "\n"; } } while (false)
;
249 DEBUG(dump("S.Consume", S.Consumes))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("S.Consume", S.Consumes); } } while (false
)
;
250 DEBUG(dump("SavedCons", SavedConsumes))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("SavedCons", SavedConsumes); } } while
(false)
;
251 }
252 }
253 }
254 } while (Changed);
255 DEBUG(dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump(); } } while (false)
;
256}
257
258#undef DEBUG_TYPE"coro-frame" // "coro-suspend-crossing"
259#define DEBUG_TYPE"coro-frame" "coro-frame"
260
261// We build up the list of spills for every case where a use is separated
262// from the definition by a suspend point.
263
264struct Spill : std::pair<Value *, Instruction *> {
265 using base = std::pair<Value *, Instruction *>;
266
267 Spill(Value *Def, User *U) : base(Def, cast<Instruction>(U)) {}
268
269 Value *def() const { return first; }
270 Instruction *user() const { return second; }
271 BasicBlock *userBlock() const { return second->getParent(); }
272
273 std::pair<Value *, BasicBlock *> getKey() const {
274 return {def(), userBlock()};
275 }
276
277 bool operator<(Spill const &rhs) const { return getKey() < rhs.getKey(); }
278};
279
280// Note that there may be more than one record with the same value of Def in
281// the SpillInfo vector.
282using SpillInfo = SmallVector<Spill, 8>;
283
284#ifndef NDEBUG
285static void dump(StringRef Title, SpillInfo const &Spills) {
286 dbgs() << "------------- " << Title << "--------------\n";
287 Value *CurrentValue = nullptr;
288 for (auto const &E : Spills) {
289 if (CurrentValue != E.def()) {
290 CurrentValue = E.def();
291 CurrentValue->dump();
292 }
293 dbgs() << " user: ";
294 E.user()->dump();
295 }
296}
297#endif
298
299// Build a struct that will keep state for an active coroutine.
300// struct f.frame {
301// ResumeFnTy ResumeFnAddr;
302// ResumeFnTy DestroyFnAddr;
303// int ResumeIndex;
304// ... promise (if present) ...
305// ... spills ...
306// };
307static StructType *buildFrameType(Function &F, coro::Shape &Shape,
308 SpillInfo &Spills) {
309 LLVMContext &C = F.getContext();
310 SmallString<32> Name(F.getName());
311 Name.append(".Frame");
312 StructType *FrameTy = StructType::create(C, Name);
313 auto *FramePtrTy = FrameTy->getPointerTo();
314 auto *FnTy = FunctionType::get(Type::getVoidTy(C), FramePtrTy,
315 /*IsVarArgs=*/false);
316 auto *FnPtrTy = FnTy->getPointerTo();
317
318 // Figure out how wide should be an integer type storing the suspend index.
319 unsigned IndexBits = std::max(1U, Log2_64_Ceil(Shape.CoroSuspends.size()));
320 Type *PromiseType = Shape.PromiseAlloca
321 ? Shape.PromiseAlloca->getType()->getElementType()
322 : Type::getInt1Ty(C);
323 SmallVector<Type *, 8> Types{FnPtrTy, FnPtrTy, PromiseType,
324 Type::getIntNTy(C, IndexBits)};
325 Value *CurrentDef = nullptr;
326
327 // Create an entry for every spilled value.
328 for (auto const &S : Spills) {
329 if (CurrentDef == S.def())
330 continue;
331
332 CurrentDef = S.def();
333 // PromiseAlloca was already added to Types array earlier.
334 if (CurrentDef == Shape.PromiseAlloca)
335 continue;
336
337 Type *Ty = nullptr;
338 if (auto *AI = dyn_cast<AllocaInst>(CurrentDef))
339 Ty = AI->getAllocatedType();
340 else
341 Ty = CurrentDef->getType();
342
343 Types.push_back(Ty);
344 }
345 FrameTy->setBody(Types);
346
347 return FrameTy;
348}
349
350// Replace all alloca and SSA values that are accessed across suspend points
351// with GetElementPointer from coroutine frame + loads and stores. Create an
352// AllocaSpillBB that will become the new entry block for the resume parts of
353// the coroutine:
354//
355// %hdl = coro.begin(...)
356// whatever
357//
358// becomes:
359//
360// %hdl = coro.begin(...)
361// %FramePtr = bitcast i8* hdl to %f.frame*
362// br label %AllocaSpillBB
363//
364// AllocaSpillBB:
365// ; geps corresponding to allocas that were moved to coroutine frame
366// br label PostSpill
367//
368// PostSpill:
369// whatever
370//
371//
372static Instruction *insertSpills(SpillInfo &Spills, coro::Shape &Shape) {
373 auto *CB = Shape.CoroBegin;
374 IRBuilder<> Builder(CB->getNextNode());
375 PointerType *FramePtrTy = Shape.FrameTy->getPointerTo();
376 auto *FramePtr =
377 cast<Instruction>(Builder.CreateBitCast(CB, FramePtrTy, "FramePtr"));
378 Type *FrameTy = FramePtrTy->getElementType();
379
380 Value *CurrentValue = nullptr;
6
'CurrentValue' initialized to a null pointer value
381 BasicBlock *CurrentBlock = nullptr;
382 Value *CurrentReload = nullptr;
383 unsigned Index = coro::Shape::LastKnownField;
384
385 // We need to keep track of any allocas that need "spilling"
386 // since they will live in the coroutine frame now, all access to them
387 // need to be changed, not just the access across suspend points
388 // we remember allocas and their indices to be handled once we processed
389 // all the spills.
390 SmallVector<std::pair<AllocaInst *, unsigned>, 4> Allocas;
391 // Promise alloca (if present) has a fixed field number (Shape::PromiseField)
392 if (Shape.PromiseAlloca)
7
Taking false branch
393 Allocas.emplace_back(Shape.PromiseAlloca, coro::Shape::PromiseField);
394
395 // Create a load instruction to reload the spilled value from the coroutine
396 // frame.
397 auto CreateReload = [&](Instruction *InsertBefore) {
398 Builder.SetInsertPoint(InsertBefore);
399 auto *G = Builder.CreateConstInBoundsGEP2_32(FrameTy, FramePtr, 0, Index,
400 CurrentValue->getName() +
29
Called C++ object pointer is null
401 Twine(".reload.addr"));
402 return isa<AllocaInst>(CurrentValue)
403 ? G
404 : Builder.CreateLoad(G,
405 CurrentValue->getName() + Twine(".reload"));
406 };
407
408 for (auto const &E : Spills) {
8
Assuming '__begin' is not equal to '__end'
409 // If we have not seen the value, generate a spill.
410 if (CurrentValue != E.def()) {
9
Assuming the condition is false
10
Taking false branch
14
Assuming the condition is false
15
Taking false branch
19
Assuming the condition is false
20
Taking false branch
24
Assuming the condition is false
25
Taking false branch
411 CurrentValue = E.def();
412 CurrentBlock = nullptr;
413 CurrentReload = nullptr;
414
415 ++Index;
416
417 if (auto *AI = dyn_cast<AllocaInst>(CurrentValue)) {
418 // Spilled AllocaInst will be replaced with GEP from the coroutine frame
419 // there is no spill required.
420 Allocas.emplace_back(AI, Index);
421 if (!AI->isStaticAlloca())
422 report_fatal_error("Coroutines cannot handle non static allocas yet");
423 } else {
424 // Otherwise, create a store instruction storing the value into the
425 // coroutine frame.
426
427 Instruction *InsertPt = nullptr;
428 if (isa<Argument>(CurrentValue)) {
429 // For arguments, we will place the store instruction right after
430 // the coroutine frame pointer instruction, i.e. bitcast of
431 // coro.begin from i8* to %f.frame*.
432 InsertPt = FramePtr->getNextNode();
433 } else if (auto *II = dyn_cast<InvokeInst>(CurrentValue)) {
434 // If we are spilling the result of the invoke instruction, split the
435 // normal edge and insert the spill in the new block.
436 auto NewBB = SplitEdge(II->getParent(), II->getNormalDest());
437 InsertPt = NewBB->getTerminator();
438 } else if (dyn_cast<PHINode>(CurrentValue)) {
439 // Skip the PHINodes and EH pads instructions.
440 InsertPt =
441 &*cast<Instruction>(E.def())->getParent()->getFirstInsertionPt();
442 } else {
443 // For all other values, the spill is placed immediately after
444 // the definition.
445 assert(!isa<TerminatorInst>(E.def()) && "unexpected terminator")((!isa<TerminatorInst>(E.def()) && "unexpected terminator"
) ? static_cast<void> (0) : __assert_fail ("!isa<TerminatorInst>(E.def()) && \"unexpected terminator\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 445, __PRETTY_FUNCTION__))
;
446 InsertPt = cast<Instruction>(E.def())->getNextNode();
447 }
448
449 Builder.SetInsertPoint(InsertPt);
450 auto *G = Builder.CreateConstInBoundsGEP2_32(
451 FrameTy, FramePtr, 0, Index,
452 CurrentValue->getName() + Twine(".spill.addr"));
453 Builder.CreateStore(CurrentValue, G);
454 }
455 }
456
457 // If we have not seen the use block, generate a reload in it.
458 if (CurrentBlock != E.userBlock()) {
11
Assuming the condition is false
12
Taking false branch
16
Assuming the condition is false
17
Taking false branch
21
Assuming the condition is false
22
Taking false branch
26
Assuming the condition is true
27
Taking true branch
459 CurrentBlock = E.userBlock();
460 CurrentReload = CreateReload(&*CurrentBlock->getFirstInsertionPt());
28
Calling 'operator()'
461 }
462
463 // If we have a single edge PHINode, remove it and replace it with a reload
464 // from the coroutine frame. (We already took care of multi edge PHINodes
465 // by rewriting them in the rewritePHIs function).
466 if (auto *PN = dyn_cast<PHINode>(E.user())) {
13
Taking false branch
18
Taking false branch
23
Taking false branch
467 assert(PN->getNumIncomingValues() == 1 && "unexpected number of incoming "((PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
"values in the PHINode") ? static_cast<void> (0) : __assert_fail
("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 468, __PRETTY_FUNCTION__))
468 "values in the PHINode")((PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
"values in the PHINode") ? static_cast<void> (0) : __assert_fail
("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 468, __PRETTY_FUNCTION__))
;
469 PN->replaceAllUsesWith(CurrentReload);
470 PN->eraseFromParent();
471 continue;
472 }
473
474 // Replace all uses of CurrentValue in the current instruction with reload.
475 E.user()->replaceUsesOfWith(CurrentValue, CurrentReload);
476 }
477
478 BasicBlock *FramePtrBB = FramePtr->getParent();
479 Shape.AllocaSpillBlock =
480 FramePtrBB->splitBasicBlock(FramePtr->getNextNode(), "AllocaSpillBB");
481 Shape.AllocaSpillBlock->splitBasicBlock(&Shape.AllocaSpillBlock->front(),
482 "PostSpill");
483
484 Builder.SetInsertPoint(&Shape.AllocaSpillBlock->front());
485 // If we found any allocas, replace all of their remaining uses with Geps.
486 for (auto &P : Allocas) {
487 auto *G =
488 Builder.CreateConstInBoundsGEP2_32(FrameTy, FramePtr, 0, P.second);
489 // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G)) here,
490 // as we are changing location of the instruction.
491 G->takeName(P.first);
492 P.first->replaceAllUsesWith(G);
493 P.first->eraseFromParent();
494 }
495 return FramePtr;
496}
497
498static void rewritePHIs(BasicBlock &BB) {
499 // For every incoming edge we will create a block holding all
500 // incoming values in a single PHI nodes.
501 //
502 // loop:
503 // %n.val = phi i32[%n, %entry], [%inc, %loop]
504 //
505 // It will create:
506 //
507 // loop.from.entry:
508 // %n.loop.pre = phi i32 [%n, %entry]
509 // br %label loop
510 // loop.from.loop:
511 // %inc.loop.pre = phi i32 [%inc, %loop]
512 // br %label loop
513 //
514 // After this rewrite, further analysis will ignore any phi nodes with more
515 // than one incoming edge.
516
517 // TODO: Simplify PHINodes in the basic block to remove duplicate
518 // predecessors.
519
520 SmallVector<BasicBlock *, 8> Preds(pred_begin(&BB), pred_end(&BB));
521 for (BasicBlock *Pred : Preds) {
522 auto *IncomingBB = SplitEdge(Pred, &BB);
523 IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());
524 auto *PN = cast<PHINode>(&BB.front());
525 do {
526 int Index = PN->getBasicBlockIndex(IncomingBB);
527 Value *V = PN->getIncomingValue(Index);
528 PHINode *InputV = PHINode::Create(
529 V->getType(), 1, V->getName() + Twine(".") + BB.getName(),
530 &IncomingBB->front());
531 InputV->addIncoming(V, Pred);
532 PN->setIncomingValue(Index, InputV);
533 PN = dyn_cast<PHINode>(PN->getNextNode());
534 } while (PN);
535 }
536}
537
538static void rewritePHIs(Function &F) {
539 SmallVector<BasicBlock *, 8> WorkList;
540
541 for (BasicBlock &BB : F)
542 if (auto *PN = dyn_cast<PHINode>(&BB.front()))
543 if (PN->getNumIncomingValues() > 1)
544 WorkList.push_back(&BB);
545
546 for (BasicBlock *BB : WorkList)
547 rewritePHIs(*BB);
548}
549
550// Check for instructions that we can recreate on resume as opposed to spill
551// the result into a coroutine frame.
552static bool materializable(Instruction &V) {
553 return isa<CastInst>(&V) || isa<GetElementPtrInst>(&V) ||
554 isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<SelectInst>(&V);
555}
556
557// Check for structural coroutine intrinsics that should not be spilled into
558// the coroutine frame.
559static bool isCoroutineStructureIntrinsic(Instruction &I) {
560 return isa<CoroIdInst>(&I) || isa<CoroBeginInst>(&I) ||
561 isa<CoroSaveInst>(&I) || isa<CoroSuspendInst>(&I);
562}
563
564// For every use of the value that is across suspend point, recreate that value
565// after a suspend point.
566static void rewriteMaterializableInstructions(IRBuilder<> &IRB,
567 SpillInfo const &Spills) {
568 BasicBlock *CurrentBlock = nullptr;
569 Instruction *CurrentMaterialization = nullptr;
570 Instruction *CurrentDef = nullptr;
571
572 for (auto const &E : Spills) {
573 // If it is a new definition, update CurrentXXX variables.
574 if (CurrentDef != E.def()) {
575 CurrentDef = cast<Instruction>(E.def());
576 CurrentBlock = nullptr;
577 CurrentMaterialization = nullptr;
578 }
579
580 // If we have not seen this block, materialize the value.
581 if (CurrentBlock != E.userBlock()) {
582 CurrentBlock = E.userBlock();
583 CurrentMaterialization = cast<Instruction>(CurrentDef)->clone();
584 CurrentMaterialization->setName(CurrentDef->getName());
585 CurrentMaterialization->insertBefore(
586 &*CurrentBlock->getFirstInsertionPt());
587 }
588
589 if (auto *PN = dyn_cast<PHINode>(E.user())) {
590 assert(PN->getNumIncomingValues() == 1 && "unexpected number of incoming "((PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
"values in the PHINode") ? static_cast<void> (0) : __assert_fail
("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 591, __PRETTY_FUNCTION__))
591 "values in the PHINode")((PN->getNumIncomingValues() == 1 && "unexpected number of incoming "
"values in the PHINode") ? static_cast<void> (0) : __assert_fail
("PN->getNumIncomingValues() == 1 && \"unexpected number of incoming \" \"values in the PHINode\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 591, __PRETTY_FUNCTION__))
;
592 PN->replaceAllUsesWith(CurrentMaterialization);
593 PN->eraseFromParent();
594 continue;
595 }
596
597 // Replace all uses of CurrentDef in the current instruction with the
598 // CurrentMaterialization for the block.
599 E.user()->replaceUsesOfWith(CurrentDef, CurrentMaterialization);
600 }
601}
602
603// Move early uses of spilled variable after CoroBegin.
604// For example, if a parameter had address taken, we may end up with the code
605// like:
606// define @f(i32 %n) {
607// %n.addr = alloca i32
608// store %n, %n.addr
609// ...
610// call @coro.begin
611// we need to move the store after coro.begin
612static void moveSpillUsesAfterCoroBegin(Function &F, SpillInfo const &Spills,
613 CoroBeginInst *CoroBegin) {
614 DominatorTree DT(F);
615 SmallVector<Instruction *, 8> NeedsMoving;
616
617 Value *CurrentValue = nullptr;
618
619 for (auto const &E : Spills) {
620 if (CurrentValue == E.def())
621 continue;
622
623 CurrentValue = E.def();
624
625 for (User *U : CurrentValue->users()) {
626 Instruction *I = cast<Instruction>(U);
627 if (!DT.dominates(CoroBegin, I)) {
628 // TODO: Make this more robust. Currently if we run into a situation
629 // where simple instruction move won't work we panic and
630 // report_fatal_error.
631 for (User *UI : I->users()) {
632 if (!DT.dominates(CoroBegin, cast<Instruction>(UI)))
633 report_fatal_error("cannot move instruction since its users are not"
634 " dominated by CoroBegin");
635 }
636
637 DEBUG(dbgs() << "will move: " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "will move: " << *I <<
"\n"; } } while (false)
;
638 NeedsMoving.push_back(I);
639 }
640 }
641 }
642
643 Instruction *InsertPt = CoroBegin->getNextNode();
644 for (Instruction *I : NeedsMoving)
645 I->moveBefore(InsertPt);
646}
647
648// Splits the block at a particular instruction unless it is the first
649// instruction in the block with a single predecessor.
650static BasicBlock *splitBlockIfNotFirst(Instruction *I, const Twine &Name) {
651 auto *BB = I->getParent();
652 if (&BB->front() == I) {
653 if (BB->getSinglePredecessor()) {
654 BB->setName(Name);
655 return BB;
656 }
657 }
658 return BB->splitBasicBlock(I, Name);
659}
660
661// Split above and below a particular instruction so that it
662// will be all alone by itself in a block.
663static void splitAround(Instruction *I, const Twine &Name) {
664 splitBlockIfNotFirst(I, Name);
665 splitBlockIfNotFirst(I->getNextNode(), "After" + Name);
666}
667
668void coro::buildCoroutineFrame(Function &F, Shape &Shape) {
669 // Lower coro.dbg.declare to coro.dbg.value, since we are going to rewrite
670 // access to local variables.
671 LowerDbgDeclare(F);
672
673 Shape.PromiseAlloca = Shape.CoroBegin->getId()->getPromise();
674 if (Shape.PromiseAlloca) {
1
Assuming the condition is false
2
Taking false branch
675 Shape.CoroBegin->getId()->clearPromise();
676 }
677
678 // Make sure that all coro.save, coro.suspend and the fallthrough coro.end
679 // intrinsics are in their own blocks to simplify the logic of building up
680 // SuspendCrossing data.
681 for (CoroSuspendInst *CSI : Shape.CoroSuspends) {
3
Assuming '__begin' is equal to '__end'
682 splitAround(CSI->getCoroSave(), "CoroSave");
683 splitAround(CSI, "CoroSuspend");
684 }
685
686 // Put fallthrough CoroEnd into its own block. Note: Shape::buildFrom places
687 // the fallthrough coro.end as the first element of CoroEnds array.
688 splitAround(Shape.CoroEnds.front(), "CoroEnd");
689
690 // Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
691 // never has its definition separated from the PHI by the suspend point.
692 rewritePHIs(F);
693
694 // Build suspend crossing info.
695 SuspendCrossingInfo Checker(F, Shape);
696
697 IRBuilder<> Builder(F.getContext());
698 SpillInfo Spills;
699
700 // See if there are materializable instructions across suspend points.
701 for (Instruction &I : instructions(F))
702 if (materializable(I))
703 for (User *U : I.users())
704 if (Checker.isDefinitionAcrossSuspend(I, U))
705 Spills.emplace_back(&I, U);
706
707 // Rewrite materializable instructions to be materialized at the use point.
708 DEBUG(dump("Materializations", Spills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("Materializations", Spills); } } while
(false)
;
709 rewriteMaterializableInstructions(Builder, Spills);
710
711 // Collect the spills for arguments and other not-materializable values.
712 Spills.clear();
713 for (Argument &A : F.args())
4
Assuming '__begin' is equal to '__end'
714 for (User *U : A.users())
715 if (Checker.isDefinitionAcrossSuspend(A, U))
716 Spills.emplace_back(&A, U);
717
718 for (Instruction &I : instructions(F)) {
719 // Values returned from coroutine structure intrinsics should not be part
720 // of the Coroutine Frame.
721 if (isCoroutineStructureIntrinsic(I))
722 continue;
723 // The Coroutine Promise always included into coroutine frame, no need to
724 // check for suspend crossing.
725 if (Shape.PromiseAlloca == &I)
726 continue;
727
728 for (User *U : I.users())
729 if (Checker.isDefinitionAcrossSuspend(I, U)) {
730 // We cannot spill a token.
731 if (I.getType()->isTokenTy())
732 report_fatal_error(
733 "token definition is separated from the use by a suspend point");
734 assert(!materializable(I) &&((!materializable(I) && "rewriteMaterializable did not do its job"
) ? static_cast<void> (0) : __assert_fail ("!materializable(I) && \"rewriteMaterializable did not do its job\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 735, __PRETTY_FUNCTION__))
735 "rewriteMaterializable did not do its job")((!materializable(I) && "rewriteMaterializable did not do its job"
) ? static_cast<void> (0) : __assert_fail ("!materializable(I) && \"rewriteMaterializable did not do its job\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn301093/lib/Transforms/Coroutines/CoroFrame.cpp"
, 735, __PRETTY_FUNCTION__))
;
736 Spills.emplace_back(&I, U);
737 }
738 }
739 DEBUG(dump("Spills", Spills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("Spills", Spills); } } while (false)
;
740 moveSpillUsesAfterCoroBegin(F, Spills, Shape.CoroBegin);
741 Shape.FrameTy = buildFrameType(F, Shape, Spills);
742 Shape.FramePtr = insertSpills(Spills, Shape);
5
Calling 'insertSpills'
743}