Bug Summary

File:lib/Transforms/Coroutines/CoroFrame.cpp
Warning:line 421, 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~svn303373/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~svn303373/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// We need to make room to insert a spill after initial PHIs, but before
351// catchswitch instruction. Placing it before violates the requirement that
352// catchswitch, like all other EHPads must be the first nonPHI in a block.
353//
354// Split away catchswitch into a separate block and insert in its place:
355//
356// cleanuppad <InsertPt> cleanupret.
357//
358// cleanupret instruction will act as an insert point for the spill.
359static Instruction *splitBeforeCatchSwitch(CatchSwitchInst *CatchSwitch) {
360 BasicBlock *CurrentBlock = CatchSwitch->getParent();
361 BasicBlock *NewBlock = CurrentBlock->splitBasicBlock(CatchSwitch);
362 CurrentBlock->getTerminator()->eraseFromParent();
363
364 auto *CleanupPad =
365 CleanupPadInst::Create(CatchSwitch->getParentPad(), {}, "", CurrentBlock);
366 auto *CleanupRet =
367 CleanupReturnInst::Create(CleanupPad, NewBlock, CurrentBlock);
368 return CleanupRet;
369}
370
371// Replace all alloca and SSA values that are accessed across suspend points
372// with GetElementPointer from coroutine frame + loads and stores. Create an
373// AllocaSpillBB that will become the new entry block for the resume parts of
374// the coroutine:
375//
376// %hdl = coro.begin(...)
377// whatever
378//
379// becomes:
380//
381// %hdl = coro.begin(...)
382// %FramePtr = bitcast i8* hdl to %f.frame*
383// br label %AllocaSpillBB
384//
385// AllocaSpillBB:
386// ; geps corresponding to allocas that were moved to coroutine frame
387// br label PostSpill
388//
389// PostSpill:
390// whatever
391//
392//
393static Instruction *insertSpills(SpillInfo &Spills, coro::Shape &Shape) {
394 auto *CB = Shape.CoroBegin;
395 IRBuilder<> Builder(CB->getNextNode());
396 PointerType *FramePtrTy = Shape.FrameTy->getPointerTo();
397 auto *FramePtr =
398 cast<Instruction>(Builder.CreateBitCast(CB, FramePtrTy, "FramePtr"));
399 Type *FrameTy = FramePtrTy->getElementType();
400
401 Value *CurrentValue = nullptr;
6
'CurrentValue' initialized to a null pointer value
402 BasicBlock *CurrentBlock = nullptr;
403 Value *CurrentReload = nullptr;
404 unsigned Index = coro::Shape::LastKnownField;
405
406 // We need to keep track of any allocas that need "spilling"
407 // since they will live in the coroutine frame now, all access to them
408 // need to be changed, not just the access across suspend points
409 // we remember allocas and their indices to be handled once we processed
410 // all the spills.
411 SmallVector<std::pair<AllocaInst *, unsigned>, 4> Allocas;
412 // Promise alloca (if present) has a fixed field number (Shape::PromiseField)
413 if (Shape.PromiseAlloca)
7
Taking false branch
414 Allocas.emplace_back(Shape.PromiseAlloca, coro::Shape::PromiseField);
415
416 // Create a load instruction to reload the spilled value from the coroutine
417 // frame.
418 auto CreateReload = [&](Instruction *InsertBefore) {
419 Builder.SetInsertPoint(InsertBefore);
420 auto *G = Builder.CreateConstInBoundsGEP2_32(FrameTy, FramePtr, 0, Index,
421 CurrentValue->getName() +
29
Called C++ object pointer is null
422 Twine(".reload.addr"));
423 return isa<AllocaInst>(CurrentValue)
424 ? G
425 : Builder.CreateLoad(G,
426 CurrentValue->getName() + Twine(".reload"));
427 };
428
429 for (auto const &E : Spills) {
8
Assuming '__begin' is not equal to '__end'
430 // If we have not seen the value, generate a spill.
431 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
432 CurrentValue = E.def();
433 CurrentBlock = nullptr;
434 CurrentReload = nullptr;
435
436 ++Index;
437
438 if (auto *AI = dyn_cast<AllocaInst>(CurrentValue)) {
439 // Spilled AllocaInst will be replaced with GEP from the coroutine frame
440 // there is no spill required.
441 Allocas.emplace_back(AI, Index);
442 if (!AI->isStaticAlloca())
443 report_fatal_error("Coroutines cannot handle non static allocas yet");
444 } else {
445 // Otherwise, create a store instruction storing the value into the
446 // coroutine frame.
447
448 Instruction *InsertPt = nullptr;
449 if (isa<Argument>(CurrentValue)) {
450 // For arguments, we will place the store instruction right after
451 // the coroutine frame pointer instruction, i.e. bitcast of
452 // coro.begin from i8* to %f.frame*.
453 InsertPt = FramePtr->getNextNode();
454 } else if (auto *II = dyn_cast<InvokeInst>(CurrentValue)) {
455 // If we are spilling the result of the invoke instruction, split the
456 // normal edge and insert the spill in the new block.
457 auto NewBB = SplitEdge(II->getParent(), II->getNormalDest());
458 InsertPt = NewBB->getTerminator();
459 } else if (dyn_cast<PHINode>(CurrentValue)) {
460 // Skip the PHINodes and EH pads instructions.
461 BasicBlock *DefBlock = cast<Instruction>(E.def())->getParent();
462 if (auto *CSI = dyn_cast<CatchSwitchInst>(DefBlock->getTerminator()))
463 InsertPt = splitBeforeCatchSwitch(CSI);
464 else
465 InsertPt = &*DefBlock->getFirstInsertionPt();
466 } else {
467 // For all other values, the spill is placed immediately after
468 // the definition.
469 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~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 469, __PRETTY_FUNCTION__))
;
470 InsertPt = cast<Instruction>(E.def())->getNextNode();
471 }
472
473 Builder.SetInsertPoint(InsertPt);
474 auto *G = Builder.CreateConstInBoundsGEP2_32(
475 FrameTy, FramePtr, 0, Index,
476 CurrentValue->getName() + Twine(".spill.addr"));
477 Builder.CreateStore(CurrentValue, G);
478 }
479 }
480
481 // If we have not seen the use block, generate a reload in it.
482 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
483 CurrentBlock = E.userBlock();
484 CurrentReload = CreateReload(&*CurrentBlock->getFirstInsertionPt());
28
Calling 'operator()'
485 }
486
487 // If we have a single edge PHINode, remove it and replace it with a reload
488 // from the coroutine frame. (We already took care of multi edge PHINodes
489 // by rewriting them in the rewritePHIs function).
490 if (auto *PN = dyn_cast<PHINode>(E.user())) {
13
Taking false branch
18
Taking false branch
23
Taking false branch
491 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~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 492, __PRETTY_FUNCTION__))
492 "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~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 492, __PRETTY_FUNCTION__))
;
493 PN->replaceAllUsesWith(CurrentReload);
494 PN->eraseFromParent();
495 continue;
496 }
497
498 // Replace all uses of CurrentValue in the current instruction with reload.
499 E.user()->replaceUsesOfWith(CurrentValue, CurrentReload);
500 }
501
502 BasicBlock *FramePtrBB = FramePtr->getParent();
503 Shape.AllocaSpillBlock =
504 FramePtrBB->splitBasicBlock(FramePtr->getNextNode(), "AllocaSpillBB");
505 Shape.AllocaSpillBlock->splitBasicBlock(&Shape.AllocaSpillBlock->front(),
506 "PostSpill");
507
508 Builder.SetInsertPoint(&Shape.AllocaSpillBlock->front());
509 // If we found any allocas, replace all of their remaining uses with Geps.
510 for (auto &P : Allocas) {
511 auto *G =
512 Builder.CreateConstInBoundsGEP2_32(FrameTy, FramePtr, 0, P.second);
513 // We are not using ReplaceInstWithInst(P.first, cast<Instruction>(G)) here,
514 // as we are changing location of the instruction.
515 G->takeName(P.first);
516 P.first->replaceAllUsesWith(G);
517 P.first->eraseFromParent();
518 }
519 return FramePtr;
520}
521
522// Sets the unwind edge of an instruction to a particular successor.
523static void setUnwindEdgeTo(TerminatorInst *TI, BasicBlock *Succ) {
524 if (auto *II = dyn_cast<InvokeInst>(TI))
525 II->setUnwindDest(Succ);
526 else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))
527 CS->setUnwindDest(Succ);
528 else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))
529 CR->setUnwindDest(Succ);
530 else
531 llvm_unreachable("unexpected terminator instruction")::llvm::llvm_unreachable_internal("unexpected terminator instruction"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 531)
;
532}
533
534// Replaces all uses of OldPred with the NewPred block in all PHINodes in a
535// block.
536static void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,
537 BasicBlock *NewPred,
538 PHINode *LandingPadReplacement) {
539 unsigned BBIdx = 0;
540 for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
541 PHINode *PN = cast<PHINode>(I);
542
543 // We manually update the LandingPadReplacement PHINode and it is the last
544 // PHI Node. So, if we find it, we are done.
545 if (LandingPadReplacement == PN)
546 break;
547
548 // Reuse the previous value of BBIdx if it lines up. In cases where we
549 // have multiple phi nodes with *lots* of predecessors, this is a speed
550 // win because we don't have to scan the PHI looking for TIBB. This
551 // happens because the BB list of PHI nodes are usually in the same
552 // order.
553 if (PN->getIncomingBlock(BBIdx) != OldPred)
554 BBIdx = PN->getBasicBlockIndex(OldPred);
555
556 assert(BBIdx != (unsigned)-1 && "Invalid PHI Index!")((BBIdx != (unsigned)-1 && "Invalid PHI Index!") ? static_cast
<void> (0) : __assert_fail ("BBIdx != (unsigned)-1 && \"Invalid PHI Index!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 556, __PRETTY_FUNCTION__))
;
557 PN->setIncomingBlock(BBIdx, NewPred);
558 }
559}
560
561// Uses SplitEdge unless the successor block is an EHPad, in which case do EH
562// specific handling.
563static BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ,
564 LandingPadInst *OriginalPad,
565 PHINode *LandingPadReplacement) {
566 auto *PadInst = Succ->getFirstNonPHI();
567 if (!LandingPadReplacement && !PadInst->isEHPad())
568 return SplitEdge(BB, Succ);
569
570 auto *NewBB = BasicBlock::Create(BB->getContext(), "", BB->getParent(), Succ);
571 setUnwindEdgeTo(BB->getTerminator(), NewBB);
572 updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);
573
574 if (LandingPadReplacement) {
575 auto *NewLP = OriginalPad->clone();
576 auto *Terminator = BranchInst::Create(Succ, NewBB);
577 NewLP->insertBefore(Terminator);
578 LandingPadReplacement->addIncoming(NewLP, NewBB);
579 return NewBB;
580 }
581 Value *ParentPad = nullptr;
582 if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))
583 ParentPad = FuncletPad->getParentPad();
584 else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))
585 ParentPad = CatchSwitch->getParentPad();
586 else
587 llvm_unreachable("handling for other EHPads not implemented yet")::llvm::llvm_unreachable_internal("handling for other EHPads not implemented yet"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 587)
;
588
589 auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, "", NewBB);
590 CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);
591 return NewBB;
592}
593
594static void rewritePHIs(BasicBlock &BB) {
595 // For every incoming edge we will create a block holding all
596 // incoming values in a single PHI nodes.
597 //
598 // loop:
599 // %n.val = phi i32[%n, %entry], [%inc, %loop]
600 //
601 // It will create:
602 //
603 // loop.from.entry:
604 // %n.loop.pre = phi i32 [%n, %entry]
605 // br %label loop
606 // loop.from.loop:
607 // %inc.loop.pre = phi i32 [%inc, %loop]
608 // br %label loop
609 //
610 // After this rewrite, further analysis will ignore any phi nodes with more
611 // than one incoming edge.
612
613 // TODO: Simplify PHINodes in the basic block to remove duplicate
614 // predecessors.
615
616 LandingPadInst *LandingPad = nullptr;
617 PHINode *ReplPHI = nullptr;
618 if ((LandingPad = dyn_cast_or_null<LandingPadInst>(BB.getFirstNonPHI()))) {
619 // ehAwareSplitEdge will clone the LandingPad in all the edge blocks.
620 // We replace the original landing pad with a PHINode that will collect the
621 // results from all of them.
622 ReplPHI = PHINode::Create(LandingPad->getType(), 1, "", LandingPad);
623 ReplPHI->takeName(LandingPad);
624 LandingPad->replaceAllUsesWith(ReplPHI);
625 // We will erase the original landing pad at the end of this function after
626 // ehAwareSplitEdge cloned it in the transition blocks.
627 }
628
629 SmallVector<BasicBlock *, 8> Preds(pred_begin(&BB), pred_end(&BB));
630 for (BasicBlock *Pred : Preds) {
631 auto *IncomingBB = ehAwareSplitEdge(Pred, &BB, LandingPad, ReplPHI);
632 IncomingBB->setName(BB.getName() + Twine(".from.") + Pred->getName());
633 auto *PN = cast<PHINode>(&BB.front());
634 do {
635 int Index = PN->getBasicBlockIndex(IncomingBB);
636 Value *V = PN->getIncomingValue(Index);
637 PHINode *InputV = PHINode::Create(
638 V->getType(), 1, V->getName() + Twine(".") + BB.getName(),
639 &IncomingBB->front());
640 InputV->addIncoming(V, Pred);
641 PN->setIncomingValue(Index, InputV);
642 PN = dyn_cast<PHINode>(PN->getNextNode());
643 } while (PN != ReplPHI); // ReplPHI is either null or the PHI that replaced
644 // the landing pad.
645 }
646
647 if (LandingPad) {
648 // Calls to ehAwareSplitEdge function cloned the original lading pad.
649 // No longer need it.
650 LandingPad->eraseFromParent();
651 }
652}
653
654static void rewritePHIs(Function &F) {
655 SmallVector<BasicBlock *, 8> WorkList;
656
657 for (BasicBlock &BB : F)
658 if (auto *PN = dyn_cast<PHINode>(&BB.front()))
659 if (PN->getNumIncomingValues() > 1)
660 WorkList.push_back(&BB);
661
662 for (BasicBlock *BB : WorkList)
663 rewritePHIs(*BB);
664}
665
666// Check for instructions that we can recreate on resume as opposed to spill
667// the result into a coroutine frame.
668static bool materializable(Instruction &V) {
669 return isa<CastInst>(&V) || isa<GetElementPtrInst>(&V) ||
670 isa<BinaryOperator>(&V) || isa<CmpInst>(&V) || isa<SelectInst>(&V);
671}
672
673// Check for structural coroutine intrinsics that should not be spilled into
674// the coroutine frame.
675static bool isCoroutineStructureIntrinsic(Instruction &I) {
676 return isa<CoroIdInst>(&I) || isa<CoroBeginInst>(&I) ||
677 isa<CoroSaveInst>(&I) || isa<CoroSuspendInst>(&I);
678}
679
680// For every use of the value that is across suspend point, recreate that value
681// after a suspend point.
682static void rewriteMaterializableInstructions(IRBuilder<> &IRB,
683 SpillInfo const &Spills) {
684 BasicBlock *CurrentBlock = nullptr;
685 Instruction *CurrentMaterialization = nullptr;
686 Instruction *CurrentDef = nullptr;
687
688 for (auto const &E : Spills) {
689 // If it is a new definition, update CurrentXXX variables.
690 if (CurrentDef != E.def()) {
691 CurrentDef = cast<Instruction>(E.def());
692 CurrentBlock = nullptr;
693 CurrentMaterialization = nullptr;
694 }
695
696 // If we have not seen this block, materialize the value.
697 if (CurrentBlock != E.userBlock()) {
698 CurrentBlock = E.userBlock();
699 CurrentMaterialization = cast<Instruction>(CurrentDef)->clone();
700 CurrentMaterialization->setName(CurrentDef->getName());
701 CurrentMaterialization->insertBefore(
702 &*CurrentBlock->getFirstInsertionPt());
703 }
704
705 if (auto *PN = dyn_cast<PHINode>(E.user())) {
706 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~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 707, __PRETTY_FUNCTION__))
707 "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~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 707, __PRETTY_FUNCTION__))
;
708 PN->replaceAllUsesWith(CurrentMaterialization);
709 PN->eraseFromParent();
710 continue;
711 }
712
713 // Replace all uses of CurrentDef in the current instruction with the
714 // CurrentMaterialization for the block.
715 E.user()->replaceUsesOfWith(CurrentDef, CurrentMaterialization);
716 }
717}
718
719// Move early uses of spilled variable after CoroBegin.
720// For example, if a parameter had address taken, we may end up with the code
721// like:
722// define @f(i32 %n) {
723// %n.addr = alloca i32
724// store %n, %n.addr
725// ...
726// call @coro.begin
727// we need to move the store after coro.begin
728static void moveSpillUsesAfterCoroBegin(Function &F, SpillInfo const &Spills,
729 CoroBeginInst *CoroBegin) {
730 DominatorTree DT(F);
731 SmallVector<Instruction *, 8> NeedsMoving;
732
733 Value *CurrentValue = nullptr;
734
735 for (auto const &E : Spills) {
736 if (CurrentValue == E.def())
737 continue;
738
739 CurrentValue = E.def();
740
741 for (User *U : CurrentValue->users()) {
742 Instruction *I = cast<Instruction>(U);
743 if (!DT.dominates(CoroBegin, I)) {
744 // TODO: Make this more robust. Currently if we run into a situation
745 // where simple instruction move won't work we panic and
746 // report_fatal_error.
747 for (User *UI : I->users()) {
748 if (!DT.dominates(CoroBegin, cast<Instruction>(UI)))
749 report_fatal_error("cannot move instruction since its users are not"
750 " dominated by CoroBegin");
751 }
752
753 DEBUG(dbgs() << "will move: " << *I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dbgs() << "will move: " << *I <<
"\n"; } } while (false)
;
754 NeedsMoving.push_back(I);
755 }
756 }
757 }
758
759 Instruction *InsertPt = CoroBegin->getNextNode();
760 for (Instruction *I : NeedsMoving)
761 I->moveBefore(InsertPt);
762}
763
764// Splits the block at a particular instruction unless it is the first
765// instruction in the block with a single predecessor.
766static BasicBlock *splitBlockIfNotFirst(Instruction *I, const Twine &Name) {
767 auto *BB = I->getParent();
768 if (&BB->front() == I) {
769 if (BB->getSinglePredecessor()) {
770 BB->setName(Name);
771 return BB;
772 }
773 }
774 return BB->splitBasicBlock(I, Name);
775}
776
777// Split above and below a particular instruction so that it
778// will be all alone by itself in a block.
779static void splitAround(Instruction *I, const Twine &Name) {
780 splitBlockIfNotFirst(I, Name);
781 splitBlockIfNotFirst(I->getNextNode(), "After" + Name);
782}
783
784void coro::buildCoroutineFrame(Function &F, Shape &Shape) {
785 // Lower coro.dbg.declare to coro.dbg.value, since we are going to rewrite
786 // access to local variables.
787 LowerDbgDeclare(F);
788
789 Shape.PromiseAlloca = Shape.CoroBegin->getId()->getPromise();
790 if (Shape.PromiseAlloca) {
1
Assuming the condition is false
2
Taking false branch
791 Shape.CoroBegin->getId()->clearPromise();
792 }
793
794 // Make sure that all coro.save, coro.suspend and the fallthrough coro.end
795 // intrinsics are in their own blocks to simplify the logic of building up
796 // SuspendCrossing data.
797 for (CoroSuspendInst *CSI : Shape.CoroSuspends) {
3
Assuming '__begin' is equal to '__end'
798 splitAround(CSI->getCoroSave(), "CoroSave");
799 splitAround(CSI, "CoroSuspend");
800 }
801
802 // Put fallthrough CoroEnd into its own block. Note: Shape::buildFrom places
803 // the fallthrough coro.end as the first element of CoroEnds array.
804 splitAround(Shape.CoroEnds.front(), "CoroEnd");
805
806 // Transforms multi-edge PHI Nodes, so that any value feeding into a PHI will
807 // never has its definition separated from the PHI by the suspend point.
808 rewritePHIs(F);
809
810 // Build suspend crossing info.
811 SuspendCrossingInfo Checker(F, Shape);
812
813 IRBuilder<> Builder(F.getContext());
814 SpillInfo Spills;
815
816 // See if there are materializable instructions across suspend points.
817 for (Instruction &I : instructions(F))
818 if (materializable(I))
819 for (User *U : I.users())
820 if (Checker.isDefinitionAcrossSuspend(I, U))
821 Spills.emplace_back(&I, U);
822
823 // Rewrite materializable instructions to be materialized at the use point.
824 DEBUG(dump("Materializations", Spills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("Materializations", Spills); } } while
(false)
;
825 rewriteMaterializableInstructions(Builder, Spills);
826
827 // Collect the spills for arguments and other not-materializable values.
828 Spills.clear();
829 for (Argument &A : F.args())
4
Assuming '__begin' is equal to '__end'
830 for (User *U : A.users())
831 if (Checker.isDefinitionAcrossSuspend(A, U))
832 Spills.emplace_back(&A, U);
833
834 for (Instruction &I : instructions(F)) {
835 // Values returned from coroutine structure intrinsics should not be part
836 // of the Coroutine Frame.
837 if (isCoroutineStructureIntrinsic(I))
838 continue;
839 // The Coroutine Promise always included into coroutine frame, no need to
840 // check for suspend crossing.
841 if (Shape.PromiseAlloca == &I)
842 continue;
843
844 for (User *U : I.users())
845 if (Checker.isDefinitionAcrossSuspend(I, U)) {
846 // We cannot spill a token.
847 if (I.getType()->isTokenTy())
848 report_fatal_error(
849 "token definition is separated from the use by a suspend point");
850 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~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 851, __PRETTY_FUNCTION__))
851 "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~svn303373/lib/Transforms/Coroutines/CoroFrame.cpp"
, 851, __PRETTY_FUNCTION__))
;
852 Spills.emplace_back(&I, U);
853 }
854 }
855 DEBUG(dump("Spills", Spills))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("coro-frame")) { dump("Spills", Spills); } } while (false)
;
856 moveSpillUsesAfterCoroBegin(F, Spills, Shape.CoroBegin);
857 Shape.FrameTy = buildFrameType(F, Shape, Spills);
858 Shape.FramePtr = insertSpills(Spills, Shape);
5
Calling 'insertSpills'
859}