llvm/test/CodeGen/X86/llc-override-mcpu-mattr.ll: Tweak not to be affected by x64...
[oota-llvm.git] / lib / Transforms / Scalar / PlaceSafepoints.cpp
1 //===- PlaceSafepoints.cpp - Place GC Safepoints --------------------------===//
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 //
10 // Place garbage collection safepoints at appropriate locations in the IR. This
11 // does not make relocation semantics or variable liveness explicit.  That's
12 // done by RewriteStatepointsForGC.
13 //
14 // Terminology:
15 // - A call is said to be "parseable" if there is a stack map generated for the
16 // return PC of the call.  A runtime can determine where values listed in the
17 // deopt arguments and (after RewriteStatepointsForGC) gc arguments are located
18 // on the stack when the code is suspended inside such a call.  Every parse
19 // point is represented by a call wrapped in an gc.statepoint intrinsic.  
20 // - A "poll" is an explicit check in the generated code to determine if the
21 // runtime needs the generated code to cooperate by calling a helper routine
22 // and thus suspending its execution at a known state. The call to the helper
23 // routine will be parseable.  The (gc & runtime specific) logic of a poll is
24 // assumed to be provided in a function of the name "gc.safepoint_poll".
25 //
26 // We aim to insert polls such that running code can quickly be brought to a
27 // well defined state for inspection by the collector.  In the current
28 // implementation, this is done via the insertion of poll sites at method entry
29 // and the backedge of most loops.  We try to avoid inserting more polls than
30 // are neccessary to ensure a finite period between poll sites.  This is not
31 // because the poll itself is expensive in the generated code; it's not.  Polls
32 // do tend to impact the optimizer itself in negative ways; we'd like to avoid
33 // perturbing the optimization of the method as much as we can.
34 //
35 // We also need to make most call sites parseable.  The callee might execute a
36 // poll (or otherwise be inspected by the GC).  If so, the entire stack
37 // (including the suspended frame of the current method) must be parseable.
38 //
39 // This pass will insert:
40 // - Call parse points ("call safepoints") for any call which may need to
41 // reach a safepoint during the execution of the callee function.
42 // - Backedge safepoint polls and entry safepoint polls to ensure that
43 // executing code reaches a safepoint poll in a finite amount of time.
44 //
45 // We do not currently support return statepoints, but adding them would not
46 // be hard.  They are not required for correctness - entry safepoints are an
47 // alternative - but some GCs may prefer them.  Patches welcome.
48 //
49 //===----------------------------------------------------------------------===//
50
51 #include "llvm/Pass.h"
52 #include "llvm/IR/LegacyPassManager.h"
53 #include "llvm/ADT/SetOperations.h"
54 #include "llvm/ADT/Statistic.h"
55 #include "llvm/Analysis/LoopPass.h"
56 #include "llvm/Analysis/LoopInfo.h"
57 #include "llvm/Analysis/ScalarEvolution.h"
58 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
59 #include "llvm/Analysis/CFG.h"
60 #include "llvm/Analysis/InstructionSimplify.h"
61 #include "llvm/IR/BasicBlock.h"
62 #include "llvm/IR/CallSite.h"
63 #include "llvm/IR/Dominators.h"
64 #include "llvm/IR/Function.h"
65 #include "llvm/IR/IRBuilder.h"
66 #include "llvm/IR/InstIterator.h"
67 #include "llvm/IR/Instructions.h"
68 #include "llvm/IR/Intrinsics.h"
69 #include "llvm/IR/IntrinsicInst.h"
70 #include "llvm/IR/Module.h"
71 #include "llvm/IR/Statepoint.h"
72 #include "llvm/IR/Value.h"
73 #include "llvm/IR/Verifier.h"
74 #include "llvm/Support/Debug.h"
75 #include "llvm/Support/CommandLine.h"
76 #include "llvm/Support/raw_ostream.h"
77 #include "llvm/Transforms/Scalar.h"
78 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
79 #include "llvm/Transforms/Utils/Cloning.h"
80 #include "llvm/Transforms/Utils/Local.h"
81
82 #define DEBUG_TYPE "safepoint-placement"
83 STATISTIC(NumEntrySafepoints, "Number of entry safepoints inserted");
84 STATISTIC(NumCallSafepoints, "Number of call safepoints inserted");
85 STATISTIC(NumBackedgeSafepoints, "Number of backedge safepoints inserted");
86
87 STATISTIC(CallInLoop, "Number of loops w/o safepoints due to calls in loop");
88 STATISTIC(FiniteExecution, "Number of loops w/o safepoints finite execution");
89
90 using namespace llvm;
91
92 // Ignore oppurtunities to avoid placing safepoints on backedges, useful for
93 // validation
94 static cl::opt<bool> AllBackedges("spp-all-backedges", cl::Hidden,
95                                   cl::init(false));
96
97 /// If true, do not place backedge safepoints in counted loops.
98 static cl::opt<bool> SkipCounted("spp-counted", cl::Hidden, cl::init(true));
99
100 // If true, split the backedge of a loop when placing the safepoint, otherwise
101 // split the latch block itself.  Both are useful to support for
102 // experimentation, but in practice, it looks like splitting the backedge
103 // optimizes better.
104 static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::Hidden,
105                                    cl::init(false));
106
107 // Print tracing output
108 static cl::opt<bool> TraceLSP("spp-trace", cl::Hidden, cl::init(false));
109
110 namespace {
111
112 /** An analysis pass whose purpose is to identify each of the backedges in
113     the function which require a safepoint poll to be inserted. */
114 struct PlaceBackedgeSafepointsImpl : public LoopPass {
115   static char ID;
116
117   /// The output of the pass - gives a list of each backedge (described by
118   /// pointing at the branch) which need a poll inserted.
119   std::vector<TerminatorInst *> PollLocations;
120
121   /// True unless we're running spp-no-calls in which case we need to disable
122   /// the call dependend placement opts.
123   bool CallSafepointsEnabled;
124   PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
125       : LoopPass(ID), CallSafepointsEnabled(CallSafepoints) {
126     initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry());
127   }
128
129   bool runOnLoop(Loop *, LPPassManager &LPM) override;
130
131   void getAnalysisUsage(AnalysisUsage &AU) const override {
132     // needed for determining if the loop is finite
133     AU.addRequired<ScalarEvolution>();
134     // to ensure each edge has a single backedge
135     // TODO: is this still required?
136     AU.addRequiredID(LoopSimplifyID);
137
138     // We no longer modify the IR at all in this pass.  Thus all
139     // analysis are preserved.
140     AU.setPreservesAll();
141   }
142 };
143 }
144
145 static cl::opt<bool> NoEntry("spp-no-entry", cl::Hidden, cl::init(false));
146 static cl::opt<bool> NoCall("spp-no-call", cl::Hidden, cl::init(false));
147 static cl::opt<bool> NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false));
148
149 namespace {
150 struct PlaceSafepoints : public ModulePass {
151   static char ID; // Pass identification, replacement for typeid
152
153   PlaceSafepoints() : ModulePass(ID) {
154     initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
155   }
156   bool runOnModule(Module &M) override {
157     bool modified = false;
158     for (Function &F : M) {
159       modified |= runOnFunction(F);
160     }
161     return modified;
162   }
163   bool runOnFunction(Function &F);
164
165   void getAnalysisUsage(AnalysisUsage &AU) const override {
166     // We modify the graph wholesale (inlining, block insertion, etc).  We
167     // preserve nothing at the moment.  We could potentially preserve dom tree
168     // if that was worth doing
169   }
170 };
171 }
172
173 // Insert a safepoint poll immediately before the given instruction.  Does
174 // not handle the parsability of state at the runtime call, that's the
175 // callers job.
176 static void
177 InsertSafepointPoll(DominatorTree &DT, Instruction *after,
178                     std::vector<CallSite> &ParsePointsNeeded /*rval*/);
179
180 static bool isGCLeafFunction(const CallSite &CS);
181
182 static bool needsStatepoint(const CallSite &CS) {
183   if (isGCLeafFunction(CS))
184     return false;
185   if (CS.isCall()) {
186     CallInst *call = cast<CallInst>(CS.getInstruction());
187     if (call->isInlineAsm())
188       return false;
189   }
190   if (isStatepoint(CS) || isGCRelocate(CS) || isGCResult(CS)) {
191     return false;
192   }
193   return true;
194 }
195
196 static Value *ReplaceWithStatepoint(const CallSite &CS, Pass *P);
197
198 /// Returns true if this loop is known to contain a call safepoint which
199 /// must unconditionally execute on any iteration of the loop which returns
200 /// to the loop header via an edge from Pred.  Returns a conservative correct
201 /// answer; i.e. false is always valid.
202 static bool containsUnconditionalCallSafepoint(Loop *L, BasicBlock *Header,
203                                                BasicBlock *Pred,
204                                                DominatorTree &DT) {
205   // In general, we're looking for any cut of the graph which ensures
206   // there's a call safepoint along every edge between Header and Pred.
207   // For the moment, we look only for the 'cuts' that consist of a single call
208   // instruction in a block which is dominated by the Header and dominates the
209   // loop latch (Pred) block.  Somewhat surprisingly, walking the entire chain
210   // of such dominating blocks gets substaintially more occurences than just
211   // checking the Pred and Header blocks themselves.  This may be due to the
212   // density of loop exit conditions caused by range and null checks.
213   // TODO: structure this as an analysis pass, cache the result for subloops,
214   // avoid dom tree recalculations
215   assert(DT.dominates(Header, Pred) && "loop latch not dominated by header?");
216
217   BasicBlock *Current = Pred;
218   while (true) {
219     for (Instruction &I : *Current) {
220       if (auto CS = CallSite(&I))
221         // Note: Technically, needing a safepoint isn't quite the right
222         // condition here.  We should instead be checking if the target method
223         // has an
224         // unconditional poll. In practice, this is only a theoretical concern
225         // since we don't have any methods with conditional-only safepoint
226         // polls.
227         if (needsStatepoint(CS))
228           return true;
229     }
230
231     if (Current == Header)
232       break;
233     Current = DT.getNode(Current)->getIDom()->getBlock();
234   }
235
236   return false;
237 }
238
239 /// Returns true if this loop is known to terminate in a finite number of
240 /// iterations.  Note that this function may return false for a loop which
241 /// does actual terminate in a finite constant number of iterations due to
242 /// conservatism in the analysis.
243 static bool mustBeFiniteCountedLoop(Loop *L, ScalarEvolution *SE,
244                                     BasicBlock *Pred) {
245   // Only used when SkipCounted is off
246   const unsigned upperTripBound = 8192;
247
248   // A conservative bound on the loop as a whole.
249   const SCEV *MaxTrips = SE->getMaxBackedgeTakenCount(L);
250   if (MaxTrips != SE->getCouldNotCompute()) {
251     if (SE->getUnsignedRange(MaxTrips).getUnsignedMax().ult(upperTripBound))
252       return true;
253     if (SkipCounted &&
254         SE->getUnsignedRange(MaxTrips).getUnsignedMax().isIntN(32))
255       return true;
256   }
257
258   // If this is a conditional branch to the header with the alternate path
259   // being outside the loop, we can ask questions about the execution frequency
260   // of the exit block.
261   if (L->isLoopExiting(Pred)) {
262     // This returns an exact expression only.  TODO: We really only need an
263     // upper bound here, but SE doesn't expose that.
264     const SCEV *MaxExec = SE->getExitCount(L, Pred);
265     if (MaxExec != SE->getCouldNotCompute()) {
266       if (SE->getUnsignedRange(MaxExec).getUnsignedMax().ult(upperTripBound))
267         return true;
268       if (SkipCounted &&
269           SE->getUnsignedRange(MaxExec).getUnsignedMax().isIntN(32))
270         return true;
271     }
272   }
273
274   return /* not finite */ false;
275 }
276
277 static void scanOneBB(Instruction *start, Instruction *end,
278                       std::vector<CallInst *> &calls,
279                       std::set<BasicBlock *> &seen,
280                       std::vector<BasicBlock *> &worklist) {
281   for (BasicBlock::iterator itr(start);
282        itr != start->getParent()->end() && itr != BasicBlock::iterator(end);
283        itr++) {
284     if (CallInst *CI = dyn_cast<CallInst>(&*itr)) {
285       calls.push_back(CI);
286     }
287     // FIXME: This code does not handle invokes
288     assert(!dyn_cast<InvokeInst>(&*itr) &&
289            "support for invokes in poll code needed");
290     // Only add the successor blocks if we reach the terminator instruction
291     // without encountering end first
292     if (itr->isTerminator()) {
293       BasicBlock *BB = itr->getParent();
294       for (BasicBlock *Succ : successors(BB)) {
295         if (seen.count(Succ) == 0) {
296           worklist.push_back(Succ);
297           seen.insert(Succ);
298         }
299       }
300     }
301   }
302 }
303 static void scanInlinedCode(Instruction *start, Instruction *end,
304                             std::vector<CallInst *> &calls,
305                             std::set<BasicBlock *> &seen) {
306   calls.clear();
307   std::vector<BasicBlock *> worklist;
308   seen.insert(start->getParent());
309   scanOneBB(start, end, calls, seen, worklist);
310   while (!worklist.empty()) {
311     BasicBlock *BB = worklist.back();
312     worklist.pop_back();
313     scanOneBB(&*BB->begin(), end, calls, seen, worklist);
314   }
315 }
316
317 bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L, LPPassManager &LPM) {
318   ScalarEvolution *SE = &getAnalysis<ScalarEvolution>();
319
320   // Loop through all predecessors of the loop header and identify all
321   // backedges.  We need to place a safepoint on every backedge (potentially).
322   // Note: Due to LoopSimplify there should only be one.  Assert?  Or can we
323   // relax this?
324   BasicBlock *header = L->getHeader();
325
326   // TODO: Use the analysis pass infrastructure for this.  There is no reason
327   // to recalculate this here.
328   DominatorTree DT;
329   DT.recalculate(*header->getParent());
330
331   bool modified = false;
332   for (BasicBlock *pred : predecessors(header)) {
333     if (!L->contains(pred)) {
334       // This is not a backedge, it's coming from outside the loop
335       continue;
336     }
337
338     // Make a policy decision about whether this loop needs a safepoint or
339     // not.  Note that this is about unburdening the optimizer in loops, not
340     // avoiding the runtime cost of the actual safepoint.
341     if (!AllBackedges) {
342       if (mustBeFiniteCountedLoop(L, SE, pred)) {
343         if (TraceLSP)
344           errs() << "skipping safepoint placement in finite loop\n";
345         FiniteExecution++;
346         continue;
347       }
348       if (CallSafepointsEnabled &&
349           containsUnconditionalCallSafepoint(L, header, pred, DT)) {
350         // Note: This is only semantically legal since we won't do any further
351         // IPO or inlining before the actual call insertion..  If we hadn't, we
352         // might latter loose this call safepoint.
353         if (TraceLSP)
354           errs() << "skipping safepoint placement due to unconditional call\n";
355         CallInLoop++;
356         continue;
357       }
358     }
359
360     // TODO: We can create an inner loop which runs a finite number of
361     // iterations with an outer loop which contains a safepoint.  This would
362     // not help runtime performance that much, but it might help our ability to
363     // optimize the inner loop.
364
365     // We're unconditionally going to modify this loop.
366     modified = true;
367
368     // Safepoint insertion would involve creating a new basic block (as the
369     // target of the current backedge) which does the safepoint (of all live
370     // variables) and branches to the true header
371     TerminatorInst *term = pred->getTerminator();
372
373     if (TraceLSP) {
374       errs() << "[LSP] terminator instruction: ";
375       term->dump();
376     }
377
378     PollLocations.push_back(term);
379   }
380
381   return modified;
382 }
383
384 static Instruction *findLocationForEntrySafepoint(Function &F,
385                                                   DominatorTree &DT) {
386
387   // Conceptually, this poll needs to be on method entry, but in
388   // practice, we place it as late in the entry block as possible.  We
389   // can place it as late as we want as long as it dominates all calls
390   // that can grow the stack.  This, combined with backedge polls,
391   // give us all the progress guarantees we need.
392
393   // Due to the way the frontend generates IR, we may have a couple of initial
394   // basic blocks before the first bytecode.  These will be single-entry
395   // single-exit blocks which conceptually are just part of the first 'real
396   // basic block'.  Since we don't have deopt state until the first bytecode,
397   // walk forward until we've found the first unconditional branch or merge.
398
399   // hasNextInstruction and nextInstruction are used to iterate
400   // through a "straight line" execution sequence.
401
402   auto hasNextInstruction = [](Instruction *I) {
403     if (!I->isTerminator()) {
404       return true;
405     }
406     BasicBlock *nextBB = I->getParent()->getUniqueSuccessor();
407     return nextBB && (nextBB->getUniquePredecessor() != nullptr);
408   };
409
410   auto nextInstruction = [&hasNextInstruction](Instruction *I) {
411     assert(hasNextInstruction(I) &&
412            "first check if there is a next instruction!");
413     if (I->isTerminator()) {
414       return I->getParent()->getUniqueSuccessor()->begin();
415     } else {
416       return std::next(BasicBlock::iterator(I));
417     }
418   };
419
420   Instruction *cursor = nullptr;
421   for (cursor = F.getEntryBlock().begin(); hasNextInstruction(cursor);
422        cursor = nextInstruction(cursor)) {
423
424     // We need to stop going forward as soon as we see a call that can
425     // grow the stack (i.e. the call target has a non-zero frame
426     // size).
427     if (CallSite(cursor)) {
428       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(cursor)) {
429         // llvm.assume(...) are not really calls.
430         if (II->getIntrinsicID() == Intrinsic::assume) {
431           continue;
432         }
433         // llvm.frameescape() intrinsic is not a real call. The intrinsic can 
434         // exist only in the entry block.
435         // Inserting a statepoint before llvm.frameescape() may split the 
436         // entry block, and push the intrinsic out of the entry block.
437         if (II->getIntrinsicID() == Intrinsic::frameescape) {
438           continue;
439         }
440       }
441       break;
442     }
443   }
444
445   assert((hasNextInstruction(cursor) || cursor->isTerminator()) &&
446          "either we stopped because of a call, or because of terminator");
447
448   if (cursor->isTerminator()) {
449     return cursor;
450   }
451
452   BasicBlock *BB = cursor->getParent();
453   SplitBlock(BB, cursor, nullptr);
454
455   // Note: SplitBlock modifies the DT.  Simply passing a Pass (which is a
456   // module pass) is not enough.
457   DT.recalculate(F);
458
459   // SplitBlock updates the DT
460   DEBUG(DT.verifyDomTree());
461
462   return BB->getTerminator();
463 }
464
465 /// Identify the list of call sites which need to be have parseable state
466 static void findCallSafepoints(Function &F,
467                                std::vector<CallSite> &Found /*rval*/) {
468   assert(Found.empty() && "must be empty!");
469   for (Instruction &I : inst_range(F)) {
470     Instruction *inst = &I;
471     if (isa<CallInst>(inst) || isa<InvokeInst>(inst)) {
472       CallSite CS(inst);
473
474       // No safepoint needed or wanted
475       if (!needsStatepoint(CS)) {
476         continue;
477       }
478
479       Found.push_back(CS);
480     }
481   }
482 }
483
484 /// Implement a unique function which doesn't require we sort the input
485 /// vector.  Doing so has the effect of changing the output of a couple of
486 /// tests in ways which make them less useful in testing fused safepoints.
487 template <typename T> static void unique_unsorted(std::vector<T> &vec) {
488   std::set<T> seen;
489   std::vector<T> tmp;
490   vec.reserve(vec.size());
491   std::swap(tmp, vec);
492   for (auto V : tmp) {
493     if (seen.insert(V).second) {
494       vec.push_back(V);
495     }
496   }
497 }
498
499 static std::string GCSafepointPollName("gc.safepoint_poll");
500
501 static bool isGCSafepointPoll(Function &F) {
502   return F.getName().equals(GCSafepointPollName);
503 }
504
505 /// Returns true if this function should be rewritten to include safepoint
506 /// polls and parseable call sites.  The main point of this function is to be
507 /// an extension point for custom logic. 
508 static bool shouldRewriteFunction(Function &F) {
509   // TODO: This should check the GCStrategy
510   if (F.hasGC()) {
511     const std::string StatepointExampleName("statepoint-example");
512     return StatepointExampleName == F.getGC();
513   } else
514     return false;
515 }
516
517 // TODO: These should become properties of the GCStrategy, possibly with
518 // command line overrides.
519 static bool enableEntrySafepoints(Function &F) { return !NoEntry; }
520 static bool enableBackedgeSafepoints(Function &F) { return !NoBackedge; }
521 static bool enableCallSafepoints(Function &F) { return !NoCall; }
522
523
524 bool PlaceSafepoints::runOnFunction(Function &F) {
525   if (F.isDeclaration() || F.empty()) {
526     // This is a declaration, nothing to do.  Must exit early to avoid crash in
527     // dom tree calculation
528     return false;
529   }
530
531   if (isGCSafepointPoll(F)) {
532     // Given we're inlining this inside of safepoint poll insertion, this
533     // doesn't make any sense.  Note that we do make any contained calls
534     // parseable after we inline a poll.  
535     return false;
536   }
537
538   if (!shouldRewriteFunction(F))
539     return false;
540
541   bool modified = false;
542
543   // In various bits below, we rely on the fact that uses are reachable from
544   // defs.  When there are basic blocks unreachable from the entry, dominance
545   // and reachablity queries return non-sensical results.  Thus, we preprocess
546   // the function to ensure these properties hold.
547   modified |= removeUnreachableBlocks(F);
548
549   // STEP 1 - Insert the safepoint polling locations.  We do not need to
550   // actually insert parse points yet.  That will be done for all polls and
551   // calls in a single pass.
552
553   // Note: With the migration, we need to recompute this for each 'pass'.  Once
554   // we merge these, we'll do it once before the analysis
555   DominatorTree DT;
556
557   std::vector<CallSite> ParsePointNeeded;
558
559   if (enableBackedgeSafepoints(F)) {
560     // Construct a pass manager to run the LoopPass backedge logic.  We
561     // need the pass manager to handle scheduling all the loop passes
562     // appropriately.  Doing this by hand is painful and just not worth messing
563     // with for the moment.
564     legacy::FunctionPassManager FPM(F.getParent());
565     bool CanAssumeCallSafepoints = enableCallSafepoints(F);
566     PlaceBackedgeSafepointsImpl *PBS =
567       new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints);
568     FPM.add(PBS);
569     // Note: While the analysis pass itself won't modify the IR, LoopSimplify
570     // (which it depends on) may.  i.e. analysis must be recalculated after run
571     FPM.run(F);
572
573     // We preserve dominance information when inserting the poll, otherwise
574     // we'd have to recalculate this on every insert
575     DT.recalculate(F);
576
577     // Insert a poll at each point the analysis pass identified
578     for (size_t i = 0; i < PBS->PollLocations.size(); i++) {
579       // We are inserting a poll, the function is modified
580       modified = true;
581
582       // The poll location must be the terminator of a loop latch block.
583       TerminatorInst *Term = PBS->PollLocations[i];
584
585       std::vector<CallSite> ParsePoints;
586       if (SplitBackedge) {
587         // Split the backedge of the loop and insert the poll within that new
588         // basic block.  This creates a loop with two latches per original
589         // latch (which is non-ideal), but this appears to be easier to
590         // optimize in practice than inserting the poll immediately before the
591         // latch test.
592
593         // Since this is a latch, at least one of the successors must dominate
594         // it. Its possible that we have a) duplicate edges to the same header
595         // and b) edges to distinct loop headers.  We need to insert pools on
596         // each. (Note: This still relies on LoopSimplify.)
597         DenseSet<BasicBlock *> Headers;
598         for (unsigned i = 0; i < Term->getNumSuccessors(); i++) {
599           BasicBlock *Succ = Term->getSuccessor(i);
600           if (DT.dominates(Succ, Term->getParent())) {
601             Headers.insert(Succ);
602           }
603         }
604         assert(!Headers.empty() && "poll location is not a loop latch?");
605
606         // The split loop structure here is so that we only need to recalculate
607         // the dominator tree once.  Alternatively, we could just keep it up to
608         // date and use a more natural merged loop.
609         DenseSet<BasicBlock *> SplitBackedges;
610         for (BasicBlock *Header : Headers) {
611           BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, nullptr);
612           SplitBackedges.insert(NewBB);
613         }
614         DT.recalculate(F);
615         for (BasicBlock *NewBB : SplitBackedges) {
616           InsertSafepointPoll(DT, NewBB->getTerminator(), ParsePoints);
617           NumBackedgeSafepoints++;
618         }
619
620       } else {
621         // Split the latch block itself, right before the terminator.
622         InsertSafepointPoll(DT, Term, ParsePoints);
623         NumBackedgeSafepoints++;
624       }
625
626       // Record the parse points for later use
627       ParsePointNeeded.insert(ParsePointNeeded.end(), ParsePoints.begin(),
628                               ParsePoints.end());
629     }
630   }
631
632   if (enableEntrySafepoints(F)) {
633     DT.recalculate(F);
634     Instruction *term = findLocationForEntrySafepoint(F, DT);
635     if (!term) {
636       // policy choice not to insert?
637     } else {
638       std::vector<CallSite> RuntimeCalls;
639       InsertSafepointPoll(DT, term, RuntimeCalls);
640       modified = true;
641       NumEntrySafepoints++;
642       ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
643                               RuntimeCalls.end());
644     }
645   }
646
647   if (enableCallSafepoints(F)) {
648     DT.recalculate(F);
649     std::vector<CallSite> Calls;
650     findCallSafepoints(F, Calls);
651     NumCallSafepoints += Calls.size();
652     ParsePointNeeded.insert(ParsePointNeeded.end(), Calls.begin(), Calls.end());
653   }
654
655   // Unique the vectors since we can end up with duplicates if we scan the call
656   // site for call safepoints after we add it for entry or backedge.  The
657   // only reason we need tracking at all is that some functions might have
658   // polls but not call safepoints and thus we might miss marking the runtime
659   // calls for the polls. (This is useful in test cases!)
660   unique_unsorted(ParsePointNeeded);
661
662   // Any parse point (no matter what source) will be handled here
663   DT.recalculate(F); // Needed?
664
665   // We're about to start modifying the function
666   if (!ParsePointNeeded.empty())
667     modified = true;
668
669   // Now run through and insert the safepoints, but do _NOT_ update or remove
670   // any existing uses.  We have references to live variables that need to
671   // survive to the last iteration of this loop.
672   std::vector<Value *> Results;
673   Results.reserve(ParsePointNeeded.size());
674   for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
675     CallSite &CS = ParsePointNeeded[i];
676     Value *GCResult = ReplaceWithStatepoint(CS, nullptr);
677     Results.push_back(GCResult);
678   }
679   assert(Results.size() == ParsePointNeeded.size());
680
681   // Adjust all users of the old call sites to use the new ones instead
682   for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
683     CallSite &CS = ParsePointNeeded[i];
684     Value *GCResult = Results[i];
685     if (GCResult) {
686       // In case if we inserted result in a different basic block than the
687       // original safepoint (this can happen for invokes). We need to be sure
688       // that
689       // original result value was not used in any of the phi nodes at the
690       // beginning of basic block with gc result. Because we know that all such
691       // blocks will have single predecessor we can safely assume that all phi
692       // nodes have single entry (because of normalizeBBForInvokeSafepoint).
693       // Just remove them all here.
694       if (CS.isInvoke()) {
695         FoldSingleEntryPHINodes(cast<Instruction>(GCResult)->getParent(),
696                                 nullptr);
697         assert(
698             !isa<PHINode>(cast<Instruction>(GCResult)->getParent()->begin()));
699       }
700
701       // Replace all uses with the new call
702       CS.getInstruction()->replaceAllUsesWith(GCResult);
703     }
704
705     // Now that we've handled all uses, remove the original call itself
706     // Note: The insert point can't be the deleted instruction!
707     CS.getInstruction()->eraseFromParent();
708   }
709   return modified;
710 }
711
712 char PlaceBackedgeSafepointsImpl::ID = 0;
713 char PlaceSafepoints::ID = 0;
714
715 ModulePass *llvm::createPlaceSafepointsPass() { return new PlaceSafepoints(); }
716
717 INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
718                       "place-backedge-safepoints-impl",
719                       "Place Backedge Safepoints", false, false)
720 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
721 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
722 INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl,
723                     "place-backedge-safepoints-impl",
724                     "Place Backedge Safepoints", false, false)
725
726 INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints",
727                       false, false)
728 INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints",
729                     false, false)
730
731 static bool isGCLeafFunction(const CallSite &CS) {
732   Instruction *inst = CS.getInstruction();
733   if (isa<IntrinsicInst>(inst)) {
734     // Most LLVM intrinsics are things which can never take a safepoint.
735     // As a result, we don't need to have the stack parsable at the
736     // callsite.  This is a highly useful optimization since intrinsic
737     // calls are fairly prevelent, particularly in debug builds.
738     return true;
739   }
740
741   // If this function is marked explicitly as a leaf call, we don't need to
742   // place a safepoint of it.  In fact, for correctness we *can't* in many
743   // cases.  Note: Indirect calls return Null for the called function,
744   // these obviously aren't runtime functions with attributes
745   // TODO: Support attributes on the call site as well.
746   const Function *F = CS.getCalledFunction();
747   bool isLeaf =
748       F &&
749       F->getFnAttribute("gc-leaf-function").getValueAsString().equals("true");
750   if (isLeaf) {
751     return true;
752   }
753   return false;
754 }
755
756 static void
757 InsertSafepointPoll(DominatorTree &DT, Instruction *term,
758                     std::vector<CallSite> &ParsePointsNeeded /*rval*/) {
759   Module *M = term->getParent()->getParent()->getParent();
760   assert(M);
761
762   // Inline the safepoint poll implementation - this will get all the branch,
763   // control flow, etc..  Most importantly, it will introduce the actual slow
764   // path call - where we need to insert a safepoint (parsepoint).
765   FunctionType *ftype =
766       FunctionType::get(Type::getVoidTy(M->getContext()), false);
767   assert(ftype && "null?");
768   // Note: This cast can fail if there's a function of the same name with a
769   // different type inserted previously
770   Function *F =
771       dyn_cast<Function>(M->getOrInsertFunction("gc.safepoint_poll", ftype));
772   assert(F && "void @gc.safepoint_poll() must be defined");
773   assert(!F->empty() && "gc.safepoint_poll must be a non-empty function");
774   CallInst *poll = CallInst::Create(F, "", term);
775
776   // Record some information about the call site we're replacing
777   BasicBlock *OrigBB = term->getParent();
778   BasicBlock::iterator before(poll), after(poll);
779   bool isBegin(false);
780   if (before == term->getParent()->begin()) {
781     isBegin = true;
782   } else {
783     before--;
784   }
785   after++;
786   assert(after != poll->getParent()->end() && "must have successor");
787   assert(DT.dominates(before, after) && "trivially true");
788
789   // do the actual inlining
790   InlineFunctionInfo IFI;
791   bool inlineStatus = InlineFunction(poll, IFI);
792   assert(inlineStatus && "inline must succeed");
793   (void)inlineStatus; // suppress warning in release-asserts
794
795   // Check post conditions
796   assert(IFI.StaticAllocas.empty() && "can't have allocs");
797
798   std::vector<CallInst *> calls; // new calls
799   std::set<BasicBlock *> BBs;    // new BBs + insertee
800   // Include only the newly inserted instructions, Note: begin may not be valid
801   // if we inserted to the beginning of the basic block
802   BasicBlock::iterator start;
803   if (isBegin) {
804     start = OrigBB->begin();
805   } else {
806     start = before;
807     start++;
808   }
809
810   // If your poll function includes an unreachable at the end, that's not
811   // valid.  Bugpoint likes to create this, so check for it.
812   assert(isPotentiallyReachable(&*start, &*after, nullptr, nullptr) &&
813          "malformed poll function");
814
815   scanInlinedCode(&*(start), &*(after), calls, BBs);
816
817   // Recompute since we've invalidated cached data.  Conceptually we
818   // shouldn't need to do this, but implementation wise we appear to.  Needed
819   // so we can insert safepoints correctly.
820   // TODO: update more cheaply
821   DT.recalculate(*after->getParent()->getParent());
822
823   assert(!calls.empty() && "slow path not found for safepoint poll");
824
825   // Record the fact we need a parsable state at the runtime call contained in
826   // the poll function.  This is required so that the runtime knows how to
827   // parse the last frame when we actually take  the safepoint (i.e. execute
828   // the slow path)
829   assert(ParsePointsNeeded.empty());
830   for (size_t i = 0; i < calls.size(); i++) {
831
832     // No safepoint needed or wanted
833     if (!needsStatepoint(calls[i])) {
834       continue;
835     }
836
837     // These are likely runtime calls.  Should we assert that via calling
838     // convention or something?
839     ParsePointsNeeded.push_back(CallSite(calls[i]));
840   }
841   assert(ParsePointsNeeded.size() <= calls.size());
842 }
843
844 // Normalize basic block to make it ready to be target of invoke statepoint.
845 // It means spliting it to have single predecessor. Return newly created BB
846 // ready to be successor of invoke statepoint.
847 static BasicBlock *normalizeBBForInvokeSafepoint(BasicBlock *BB,
848                                                  BasicBlock *InvokeParent) {
849   BasicBlock *ret = BB;
850
851   if (!BB->getUniquePredecessor()) {
852     ret = SplitBlockPredecessors(BB, InvokeParent, "");
853   }
854
855   // Another requirement for such basic blocks is to not have any phi nodes.
856   // Since we just ensured that new BB will have single predecessor,
857   // all phi nodes in it will have one value. Here it would be naturall place
858   // to
859   // remove them all. But we can not do this because we are risking to remove
860   // one of the values stored in liveset of another statepoint. We will do it
861   // later after placing all safepoints.
862
863   return ret;
864 }
865
866 /// Replaces the given call site (Call or Invoke) with a gc.statepoint
867 /// intrinsic with an empty deoptimization arguments list.  This does
868 /// NOT do explicit relocation for GC support.
869 static Value *ReplaceWithStatepoint(const CallSite &CS, /* to replace */
870                                     Pass *P) {
871   BasicBlock *BB = CS.getInstruction()->getParent();
872   Function *F = BB->getParent();
873   Module *M = F->getParent();
874   assert(M && "must be set");
875
876   // TODO: technically, a pass is not allowed to get functions from within a
877   // function pass since it might trigger a new function addition.  Refactor
878   // this logic out to the initialization of the pass.  Doesn't appear to
879   // matter in practice.
880
881   // Then go ahead and use the builder do actually do the inserts.  We insert
882   // immediately before the previous instruction under the assumption that all
883   // arguments will be available here.  We can't insert afterwards since we may
884   // be replacing a terminator.
885   IRBuilder<> Builder(CS.getInstruction());
886
887   // Note: The gc args are not filled in at this time, that's handled by
888   // RewriteStatepointsForGC (which is currently under review).
889
890   // Create the statepoint given all the arguments
891   Instruction *Token = nullptr;
892   AttributeSet OriginalAttrs;
893
894   if (CS.isCall()) {
895     CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
896     CallInst *Call = Builder.CreateGCStatepointCall(
897         CS.getCalledValue(), makeArrayRef(CS.arg_begin(), CS.arg_end()), None,
898         None, "safepoint_token");
899     Call->setTailCall(ToReplace->isTailCall());
900     Call->setCallingConv(ToReplace->getCallingConv());
901
902     // Before we have to worry about GC semantics, all attributes are legal
903     // TODO: handle param attributes
904     OriginalAttrs = ToReplace->getAttributes();
905
906     // In case if we can handle this set of attributes - set up function
907     // attributes directly on statepoint and return attributes later for
908     // gc_result intrinsic.
909     Call->setAttributes(OriginalAttrs.getFnAttributes());
910
911     Token = Call;
912
913     // Put the following gc_result and gc_relocate calls immediately after the
914     // the old call (which we're about to delete).
915     assert(ToReplace->getNextNode() && "not a terminator, must have next");
916     Builder.SetInsertPoint(ToReplace->getNextNode());
917     Builder.SetCurrentDebugLocation(ToReplace->getNextNode()->getDebugLoc());
918   } else if (CS.isInvoke()) {
919     InvokeInst *ToReplace = cast<InvokeInst>(CS.getInstruction());
920
921     // Insert the new invoke into the old block.  We'll remove the old one in a
922     // moment at which point this will become the new terminator for the
923     // original block.
924     Builder.SetInsertPoint(ToReplace->getParent());
925     InvokeInst *Invoke = Builder.CreateGCStatepointInvoke(
926         CS.getCalledValue(), ToReplace->getNormalDest(),
927         ToReplace->getUnwindDest(), makeArrayRef(CS.arg_begin(), CS.arg_end()),
928         Builder.getInt32(0), None, "safepoint_token");
929
930     // Currently we will fail on parameter attributes and on certain
931     // function attributes.
932     OriginalAttrs = ToReplace->getAttributes();
933
934     // In case if we can handle this set of attributes - set up function
935     // attributes directly on statepoint and return attributes later for
936     // gc_result intrinsic.
937     Invoke->setAttributes(OriginalAttrs.getFnAttributes());
938
939     Token = Invoke;
940
941     // We'll insert the gc.result into the normal block
942     BasicBlock *NormalDest = normalizeBBForInvokeSafepoint(
943         ToReplace->getNormalDest(), Invoke->getParent());
944     Builder.SetInsertPoint(NormalDest->getFirstInsertionPt());
945   } else {
946     llvm_unreachable("unexpect type of CallSite");
947   }
948   assert(Token);
949
950   // Handle the return value of the original call - update all uses to use a
951   // gc_result hanging off the statepoint node we just inserted
952
953   // Only add the gc_result iff there is actually a used result
954   if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
955     std::string TakenName =
956         CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "";
957     CallInst *GCResult = Builder.CreateGCResult(Token, CS.getType(), TakenName);
958     GCResult->setAttributes(OriginalAttrs.getRetAttributes());
959     return GCResult;
960   } else {
961     // No return value for the call.
962     return nullptr;
963   }
964 }