LLVM  16.0.0git
MustExecute.cpp
Go to the documentation of this file.
1 //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
11 #include "llvm/ADT/StringExtras.h"
12 #include "llvm/Analysis/CFG.h"
14 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/Analysis/Passes.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/InstIterator.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/InitializePasses.h"
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "must-execute"
30 
33  return BlockColors;
34 }
35 
37  ColorVector &ColorsForNewBlock = BlockColors[New];
38  ColorVector &ColorsForOldBlock = BlockColors[Old];
39  ColorsForNewBlock = ColorsForOldBlock;
40 }
41 
43  (void)BB;
44  return anyBlockMayThrow();
45 }
46 
48  return MayThrow;
49 }
50 
52  assert(CurLoop != nullptr && "CurLoop can't be null");
53  BasicBlock *Header = CurLoop->getHeader();
54  // Iterate over header and compute safety info.
55  HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
56  MayThrow = HeaderMayThrow;
57  // Iterate over loop instructions and compute safety info.
58  // Skip header as it has been computed and stored in HeaderMayThrow.
59  // The first block in loopinfo.Blocks is guaranteed to be the header.
60  assert(Header == *CurLoop->getBlocks().begin() &&
61  "First block must be header");
62  for (const BasicBlock *BB : llvm::drop_begin(CurLoop->blocks())) {
64  if (MayThrow)
65  break;
66  }
67 
68  computeBlockColors(CurLoop);
69 }
70 
72  return ICF.hasICF(BB);
73 }
74 
76  return MayThrow;
77 }
78 
80  assert(CurLoop != nullptr && "CurLoop can't be null");
81  ICF.clear();
82  MW.clear();
83  MayThrow = false;
84  // Figure out the fact that at least one block may throw.
85  for (const auto &BB : CurLoop->blocks())
86  if (ICF.hasICF(&*BB)) {
87  MayThrow = true;
88  break;
89  }
90  computeBlockColors(CurLoop);
91 }
92 
94  const BasicBlock *BB) {
95  ICF.insertInstructionTo(Inst, BB);
96  MW.insertInstructionTo(Inst, BB);
97 }
98 
100  ICF.removeInstruction(Inst);
101  MW.removeInstruction(Inst);
102 }
103 
105  // Compute funclet colors if we might sink/hoist in a function with a funclet
106  // personality routine.
107  Function *Fn = CurLoop->getHeader()->getParent();
108  if (Fn->hasPersonalityFn())
109  if (Constant *PersonalityFn = Fn->getPersonalityFn())
110  if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
111  BlockColors = colorEHFunclets(*Fn);
112 }
113 
114 /// Return true if we can prove that the given ExitBlock is not reached on the
115 /// first iteration of the given loop. That is, the backedge of the loop must
116 /// be executed before the ExitBlock is executed in any dynamic execution trace.
117 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
118  const DominatorTree *DT,
119  const Loop *CurLoop) {
120  auto *CondExitBlock = ExitBlock->getSinglePredecessor();
121  if (!CondExitBlock)
122  // expect unique exits
123  return false;
124  assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
125  auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
126  if (!BI || !BI->isConditional())
127  return false;
128  // If condition is constant and false leads to ExitBlock then we always
129  // execute the true branch.
130  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
131  return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
132  auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
133  if (!Cond)
134  return false;
135  // todo: this would be a lot more powerful if we used scev, but all the
136  // plumbing is currently missing to pass a pointer in from the pass
137  // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
138  auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
139  auto *RHS = Cond->getOperand(1);
140  if (!LHS || LHS->getParent() != CurLoop->getHeader())
141  return false;
142  auto DL = ExitBlock->getModule()->getDataLayout();
143  auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
144  auto *SimpleValOrNull = simplifyCmpInst(Cond->getPredicate(),
145  IVStart, RHS,
146  {DL, /*TLI*/ nullptr,
147  DT, /*AC*/ nullptr, BI});
148  auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
149  if (!SimpleCst)
150  return false;
151  if (ExitBlock == BI->getSuccessor(0))
152  return SimpleCst->isZeroValue();
153  assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
154  return SimpleCst->isAllOnesValue();
155 }
156 
157 /// Collect all blocks from \p CurLoop which lie on all possible paths from
158 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
159 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
161  const Loop *CurLoop, const BasicBlock *BB,
162  SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
163  assert(Predecessors.empty() && "Garbage in predecessors set?");
164  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
165  if (BB == CurLoop->getHeader())
166  return;
168  for (const auto *Pred : predecessors(BB)) {
169  Predecessors.insert(Pred);
170  WorkList.push_back(Pred);
171  }
172  while (!WorkList.empty()) {
173  auto *Pred = WorkList.pop_back_val();
174  assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
175  // We are not interested in backedges and we don't want to leave loop.
176  if (Pred == CurLoop->getHeader())
177  continue;
178  // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
179  // blocks of this inner loop, even those that are always executed AFTER the
180  // BB. It may make our analysis more conservative than it could be, see test
181  // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
182  // We can ignore backedge of all loops containing BB to get a sligtly more
183  // optimistic result.
184  for (const auto *PredPred : predecessors(Pred))
185  if (Predecessors.insert(PredPred).second)
186  WorkList.push_back(PredPred);
187  }
188 }
189 
191  const BasicBlock *BB,
192  const DominatorTree *DT) const {
193  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
194 
195  // Fast path: header is always reached once the loop is entered.
196  if (BB == CurLoop->getHeader())
197  return true;
198 
199  // Collect all transitive predecessors of BB in the same loop. This set will
200  // be a subset of the blocks within the loop.
202  collectTransitivePredecessors(CurLoop, BB, Predecessors);
203 
204  // Make sure that all successors of, all predecessors of BB which are not
205  // dominated by BB, are either:
206  // 1) BB,
207  // 2) Also predecessors of BB,
208  // 3) Exit blocks which are not taken on 1st iteration.
209  // Memoize blocks we've already checked.
210  SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
211  for (const auto *Pred : Predecessors) {
212  // Predecessor block may throw, so it has a side exit.
213  if (blockMayThrow(Pred))
214  return false;
215 
216  // BB dominates Pred, so if Pred runs, BB must run.
217  // This is true when Pred is a loop latch.
218  if (DT->dominates(BB, Pred))
219  continue;
220 
221  for (const auto *Succ : successors(Pred))
222  if (CheckedSuccessors.insert(Succ).second &&
223  Succ != BB && !Predecessors.count(Succ))
224  // By discharging conditions that are not executed on the 1st iteration,
225  // we guarantee that *at least* on the first iteration all paths from
226  // header that *may* execute will lead us to the block of interest. So
227  // that if we had virtually peeled one iteration away, in this peeled
228  // iteration the set of predecessors would contain only paths from
229  // header to BB without any exiting edges that may execute.
230  //
231  // TODO: We only do it for exiting edges currently. We could use the
232  // same function to skip some of the edges within the loop if we know
233  // that they will not be taken on the 1st iteration.
234  //
235  // TODO: If we somehow know the number of iterations in loop, the same
236  // check may be done for any arbitrary N-th iteration as long as N is
237  // not greater than minimum number of iterations in this loop.
238  if (CurLoop->contains(Succ) ||
239  !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
240  return false;
241  }
242 
243  // All predecessors can only lead us to BB.
244  return true;
245 }
246 
247 /// Returns true if the instruction in a loop is guaranteed to execute at least
248 /// once.
250  const DominatorTree *DT,
251  const Loop *CurLoop) const {
252  // If the instruction is in the header block for the loop (which is very
253  // common), it is always guaranteed to dominate the exit blocks. Since this
254  // is a common case, and can save some work, check it now.
255  if (Inst.getParent() == CurLoop->getHeader())
256  // If there's a throw in the header block, we can't guarantee we'll reach
257  // Inst unless we can prove that Inst comes before the potential implicit
258  // exit. At the moment, we use a (cheap) hack for the common case where
259  // the instruction of interest is the first one in the block.
260  return !HeaderMayThrow ||
261  Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
262 
263  // If there is a path from header to exit or latch that doesn't lead to our
264  // instruction's block, return false.
265  return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
266 }
267 
269  const DominatorTree *DT,
270  const Loop *CurLoop) const {
271  return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
272  allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
273 }
274 
276  const Loop *CurLoop) const {
277  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
278 
279  // Fast path: there are no instructions before header.
280  if (BB == CurLoop->getHeader())
281  return true;
282 
283  // Collect all transitive predecessors of BB in the same loop. This set will
284  // be a subset of the blocks within the loop.
286  collectTransitivePredecessors(CurLoop, BB, Predecessors);
287  // Find if there any instruction in either predecessor that could write
288  // to memory.
289  for (const auto *Pred : Predecessors)
290  if (MW.mayWriteToMemory(Pred))
291  return false;
292  return true;
293 }
294 
296  const Loop *CurLoop) const {
297  auto *BB = I.getParent();
298  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
300  doesNotWriteMemoryBefore(BB, CurLoop);
301 }
302 
303 namespace {
304 struct MustExecutePrinter : public FunctionPass {
305 
306  static char ID; // Pass identification, replacement for typeid
307  MustExecutePrinter() : FunctionPass(ID) {
309  }
310  void getAnalysisUsage(AnalysisUsage &AU) const override {
311  AU.setPreservesAll();
314  }
315  bool runOnFunction(Function &F) override;
316 };
317 struct MustBeExecutedContextPrinter : public ModulePass {
318  static char ID;
319 
320  MustBeExecutedContextPrinter() : ModulePass(ID) {
323  }
324  void getAnalysisUsage(AnalysisUsage &AU) const override {
325  AU.setPreservesAll();
326  }
327  bool runOnModule(Module &M) override;
328 };
329 }
330 
331 char MustExecutePrinter::ID = 0;
332 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
333  "Instructions which execute on loop entry", false, true)
336 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
337  "Instructions which execute on loop entry", false, true)
338 
340  return new MustExecutePrinter();
341 }
342 
344 INITIALIZE_PASS_BEGIN(MustBeExecutedContextPrinter,
345  "print-must-be-executed-contexts",
346  "print the must-be-executed-context for all instructions",
347  false, true)
351 INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
352  "print-must-be-executed-contexts",
353  "print the must-be-executed-context for all instructions",
354  false, true)
355 
357  return new MustBeExecutedContextPrinter();
358 }
359 
360 bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
361  // We provide non-PM analysis here because the old PM doesn't like to query
362  // function passes from a module pass.
366 
367  GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
368  DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function &>(F)));
369  LIs.push_back(std::make_unique<LoopInfo>(*DTs.back()));
370  return LIs.back().get();
371  };
372  GetterTy<DominatorTree> DTGetter = [&](const Function &F) {
373  DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function&>(F)));
374  return DTs.back().get();
375  };
376  GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
377  PDTs.push_back(
378  std::make_unique<PostDominatorTree>(const_cast<Function &>(F)));
379  return PDTs.back().get();
380  };
382  /* ExploreInterBlock */ true,
383  /* ExploreCFGForward */ true,
384  /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
385 
386  for (Function &F : M) {
387  for (Instruction &I : instructions(F)) {
388  dbgs() << "-- Explore context of: " << I << "\n";
389  for (const Instruction *CI : Explorer.range(&I))
390  dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI
391  << "\n";
392  }
393  }
394 
395  return false;
396 }
397 
398 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
399  // TODO: merge these two routines. For the moment, we display the best
400  // result obtained by *either* implementation. This is a bit unfair since no
401  // caller actually gets the full power at the moment.
403  LSI.computeLoopSafetyInfo(L);
404  return LSI.isGuaranteedToExecute(I, DT, L) ||
406 }
407 
408 namespace {
409 /// An assembly annotator class to print must execute information in
410 /// comments.
411 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
413 
414 public:
415  MustExecuteAnnotatedWriter(const Function &F,
416  DominatorTree &DT, LoopInfo &LI) {
417  for (const auto &I: instructions(F)) {
418  Loop *L = LI.getLoopFor(I.getParent());
419  while (L) {
420  if (isMustExecuteIn(I, L, &DT)) {
421  MustExec[&I].push_back(L);
422  }
423  L = L->getParentLoop();
424  };
425  }
426  }
427  MustExecuteAnnotatedWriter(const Module &M,
428  DominatorTree &DT, LoopInfo &LI) {
429  for (const auto &F : M)
430  for (const auto &I: instructions(F)) {
431  Loop *L = LI.getLoopFor(I.getParent());
432  while (L) {
433  if (isMustExecuteIn(I, L, &DT)) {
434  MustExec[&I].push_back(L);
435  }
436  L = L->getParentLoop();
437  };
438  }
439  }
440 
441 
442  void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
443  if (!MustExec.count(&V))
444  return;
445 
446  const auto &Loops = MustExec.lookup(&V);
447  const auto NumLoops = Loops.size();
448  if (NumLoops > 1)
449  OS << " ; (mustexec in " << NumLoops << " loops: ";
450  else
451  OS << " ; (mustexec in: ";
452 
453  ListSeparator LS;
454  for (const Loop *L : Loops)
455  OS << LS << L->getHeader()->getName();
456  OS << ")";
457  }
458 };
459 } // namespace
460 
462  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
463  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
464 
465  MustExecuteAnnotatedWriter Writer(F, DT, LI);
466  F.print(dbgs(), &Writer);
467 
468  return false;
469 }
470 
471 /// Return true if \p L might be an endless loop.
472 static bool maybeEndlessLoop(const Loop &L) {
473  if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
474  return false;
475  // TODO: Actually try to prove it is not.
476  // TODO: If maybeEndlessLoop is going to be expensive, cache it.
477  return true;
478 }
479 
481  if (!LI)
482  return false;
483  using RPOTraversal = ReversePostOrderTraversal<const Function *>;
484  RPOTraversal FuncRPOT(&F);
485  return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
486  const LoopInfo>(FuncRPOT, *LI);
487 }
488 
489 /// Lookup \p Key in \p Map and return the result, potentially after
490 /// initializing the optional through \p Fn(\p args).
491 template <typename K, typename V, typename FnTy, typename... ArgsTy>
493  FnTy &&Fn, ArgsTy&&... args) {
494  Optional<V> &OptVal = Map[Key];
495  if (!OptVal)
496  OptVal = Fn(std::forward<ArgsTy>(args)...);
497  return OptVal.value();
498 }
499 
500 const BasicBlock *
502  const LoopInfo *LI = LIGetter(*InitBB->getParent());
503  const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
504 
505  LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
506  << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
507 
508  const Function &F = *InitBB->getParent();
509  const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
510  const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
511  bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
512  (L && !maybeEndlessLoop(*L))) &&
513  F.doesNotThrow();
514  LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
515  << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
516  << "\n");
517 
518  // Determine the adjacent blocks in the given direction but exclude (self)
519  // loops under certain circumstances.
521  for (const BasicBlock *SuccBB : successors(InitBB)) {
522  bool IsLatch = SuccBB == HeaderBB;
523  // Loop latches are ignored in forward propagation if the loop cannot be
524  // endless and may not throw: control has to go somewhere.
525  if (!WillReturnAndNoThrow || !IsLatch)
526  Worklist.push_back(SuccBB);
527  }
528  LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
529 
530  // If there are no other adjacent blocks, there is no join point.
531  if (Worklist.empty())
532  return nullptr;
533 
534  // If there is one adjacent block, it is the join point.
535  if (Worklist.size() == 1)
536  return Worklist[0];
537 
538  // Try to determine a join block through the help of the post-dominance
539  // tree. If no tree was provided, we perform simple pattern matching for one
540  // block conditionals and one block loops only.
541  const BasicBlock *JoinBB = nullptr;
542  if (PDT)
543  if (const auto *InitNode = PDT->getNode(InitBB))
544  if (const auto *IDomNode = InitNode->getIDom())
545  JoinBB = IDomNode->getBlock();
546 
547  if (!JoinBB && Worklist.size() == 2) {
548  const BasicBlock *Succ0 = Worklist[0];
549  const BasicBlock *Succ1 = Worklist[1];
550  const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
551  const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
552  if (Succ0UniqueSucc == InitBB) {
553  // InitBB -> Succ0 -> InitBB
554  // InitBB -> Succ1 = JoinBB
555  JoinBB = Succ1;
556  } else if (Succ1UniqueSucc == InitBB) {
557  // InitBB -> Succ1 -> InitBB
558  // InitBB -> Succ0 = JoinBB
559  JoinBB = Succ0;
560  } else if (Succ0 == Succ1UniqueSucc) {
561  // InitBB -> Succ0 = JoinBB
562  // InitBB -> Succ1 -> Succ0 = JoinBB
563  JoinBB = Succ0;
564  } else if (Succ1 == Succ0UniqueSucc) {
565  // InitBB -> Succ0 -> Succ1 = JoinBB
566  // InitBB -> Succ1 = JoinBB
567  JoinBB = Succ1;
568  } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
569  // InitBB -> Succ0 -> JoinBB
570  // InitBB -> Succ1 -> JoinBB
571  JoinBB = Succ0UniqueSucc;
572  }
573  }
574 
575  if (!JoinBB && L)
576  JoinBB = L->getUniqueExitBlock();
577 
578  if (!JoinBB)
579  return nullptr;
580 
581  LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
582 
583  // In forward direction we check if control will for sure reach JoinBB from
584  // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
585  // are: infinite loops and instructions that do not necessarily transfer
586  // execution to their successor. To check for them we traverse the CFG from
587  // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
588 
589  // If we know the function is "will-return" and "no-throw" there is no need
590  // for futher checks.
591  if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
592 
593  auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
595  };
596 
598  while (!Worklist.empty()) {
599  const BasicBlock *ToBB = Worklist.pop_back_val();
600  if (ToBB == JoinBB)
601  continue;
602 
603  // Make sure all loops in-between are finite.
604  if (!Visited.insert(ToBB).second) {
605  if (!F.hasFnAttribute(Attribute::WillReturn)) {
606  if (!LI)
607  return nullptr;
608 
609  bool MayContainIrreducibleControl = getOrCreateCachedOptional(
610  &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
611  if (MayContainIrreducibleControl)
612  return nullptr;
613 
614  const Loop *L = LI->getLoopFor(ToBB);
615  if (L && maybeEndlessLoop(*L))
616  return nullptr;
617  }
618 
619  continue;
620  }
621 
622  // Make sure the block has no instructions that could stop control
623  // transfer.
624  bool TransfersExecution = getOrCreateCachedOptional(
625  ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
626  if (!TransfersExecution)
627  return nullptr;
628 
629  append_range(Worklist, successors(ToBB));
630  }
631  }
632 
633  LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
634  return JoinBB;
635 }
636 const BasicBlock *
638  const LoopInfo *LI = LIGetter(*InitBB->getParent());
639  const DominatorTree *DT = DTGetter(*InitBB->getParent());
640  LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
641  << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
642 
643  // Try to determine a join block through the help of the dominance tree. If no
644  // tree was provided, we perform simple pattern matching for one block
645  // conditionals only.
646  if (DT)
647  if (const auto *InitNode = DT->getNode(InitBB))
648  if (const auto *IDomNode = InitNode->getIDom())
649  return IDomNode->getBlock();
650 
651  const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
652  const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
653 
654  // Determine the predecessor blocks but ignore backedges.
656  for (const BasicBlock *PredBB : predecessors(InitBB)) {
657  bool IsBackedge =
658  (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
659  // Loop backedges are ignored in backwards propagation: control has to come
660  // from somewhere.
661  if (!IsBackedge)
662  Worklist.push_back(PredBB);
663  }
664 
665  // If there are no other predecessor blocks, there is no join point.
666  if (Worklist.empty())
667  return nullptr;
668 
669  // If there is one predecessor block, it is the join point.
670  if (Worklist.size() == 1)
671  return Worklist[0];
672 
673  const BasicBlock *JoinBB = nullptr;
674  if (Worklist.size() == 2) {
675  const BasicBlock *Pred0 = Worklist[0];
676  const BasicBlock *Pred1 = Worklist[1];
677  const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
678  const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
679  if (Pred0 == Pred1UniquePred) {
680  // InitBB <- Pred0 = JoinBB
681  // InitBB <- Pred1 <- Pred0 = JoinBB
682  JoinBB = Pred0;
683  } else if (Pred1 == Pred0UniquePred) {
684  // InitBB <- Pred0 <- Pred1 = JoinBB
685  // InitBB <- Pred1 = JoinBB
686  JoinBB = Pred1;
687  } else if (Pred0UniquePred == Pred1UniquePred) {
688  // InitBB <- Pred0 <- JoinBB
689  // InitBB <- Pred1 <- JoinBB
690  JoinBB = Pred0UniquePred;
691  }
692  }
693 
694  if (!JoinBB && L)
695  JoinBB = L->getHeader();
696 
697  // In backwards direction there is no need to show termination of previous
698  // instructions. If they do not terminate, the code afterward is dead, making
699  // any information/transformation correct anyway.
700  return JoinBB;
701 }
702 
703 const Instruction *
705  MustBeExecutedIterator &It, const Instruction *PP) {
706  if (!PP)
707  return PP;
708  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
709 
710  // If we explore only inside a given basic block we stop at terminators.
711  if (!ExploreInterBlock && PP->isTerminator()) {
712  LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
713  return nullptr;
714  }
715 
716  // If we do not traverse the call graph we check if we can make progress in
717  // the current function. First, check if the instruction is guaranteed to
718  // transfer execution to the successor.
719  bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
720  if (!TransfersExecution)
721  return nullptr;
722 
723  // If this is not a terminator we know that there is a single instruction
724  // after this one that is executed next if control is transfered. If not,
725  // we can try to go back to a call site we entered earlier. If none exists, we
726  // do not know any instruction that has to be executd next.
727  if (!PP->isTerminator()) {
728  const Instruction *NextPP = PP->getNextNode();
729  LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
730  return NextPP;
731  }
732 
733  // Finally, we have to handle terminators, trivial ones first.
734  assert(PP->isTerminator() && "Expected a terminator!");
735 
736  // A terminator without a successor is not handled yet.
737  if (PP->getNumSuccessors() == 0) {
738  LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
739  return nullptr;
740  }
741 
742  // A terminator with a single successor, we will continue at the beginning of
743  // that one.
744  if (PP->getNumSuccessors() == 1) {
745  LLVM_DEBUG(
746  dbgs() << "\tUnconditional terminator, continue with successor\n");
747  return &PP->getSuccessor(0)->front();
748  }
749 
750  // Multiple successors mean we need to find the join point where control flow
751  // converges again. We use the findForwardJoinPoint helper function with
752  // information about the function and helper analyses, if available.
753  if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
754  return &JoinBB->front();
755 
756  LLVM_DEBUG(dbgs() << "\tNo join point found\n");
757  return nullptr;
758 }
759 
760 const Instruction *
762  MustBeExecutedIterator &It, const Instruction *PP) {
763  if (!PP)
764  return PP;
765 
766  bool IsFirst = !(PP->getPrevNode());
767  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
768  << (IsFirst ? " [IsFirst]" : "") << "\n");
769 
770  // If we explore only inside a given basic block we stop at the first
771  // instruction.
772  if (!ExploreInterBlock && IsFirst) {
773  LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
774  return nullptr;
775  }
776 
777  // The block and function that contains the current position.
778  const BasicBlock *PPBlock = PP->getParent();
779 
780  // If we are inside a block we know what instruction was executed before, the
781  // previous one.
782  if (!IsFirst) {
783  const Instruction *PrevPP = PP->getPrevNode();
784  LLVM_DEBUG(
785  dbgs() << "\tIntermediate instruction, continue with previous\n");
786  // We did not enter a callee so we simply return the previous instruction.
787  return PrevPP;
788  }
789 
790  // Finally, we have to handle the case where the program point is the first in
791  // a block but not in the function. We use the findBackwardJoinPoint helper
792  // function with information about the function and helper analyses, if
793  // available.
794  if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
795  return &JoinBB->back();
796 
797  LLVM_DEBUG(dbgs() << "\tNo join point found\n");
798  return nullptr;
799 }
800 
802  MustBeExecutedContextExplorer &Explorer, const Instruction *I)
803  : Explorer(Explorer), CurInst(I) {
804  reset(I);
805 }
806 
807 void MustBeExecutedIterator::reset(const Instruction *I) {
808  Visited.clear();
809  resetInstruction(I);
810 }
811 
812 void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
813  CurInst = I;
814  Head = Tail = nullptr;
817  if (Explorer.ExploreCFGForward)
818  Head = I;
819  if (Explorer.ExploreCFGBackward)
820  Tail = I;
821 }
822 
823 const Instruction *MustBeExecutedIterator::advance() {
824  assert(CurInst && "Cannot advance an end iterator!");
825  Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
826  if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
827  return Head;
828  Head = nullptr;
829 
830  Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
831  if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
832  return Tail;
833  Tail = nullptr;
834  return nullptr;
835 }
836 
839  auto &LI = AM.getResult<LoopAnalysis>(F);
840  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
841 
842  MustExecuteAnnotatedWriter Writer(F, DT, LI);
843  F.print(OS, &Writer);
844  return PreservedAnalyses::all();
845 }
846 
851  GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
852  return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
853  };
854  GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
855  return &FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
856  };
857  GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
858  return &FAM.getResult<PostDominatorTreeAnalysis>(const_cast<Function &>(F));
859  };
860 
862  /* ExploreInterBlock */ true,
863  /* ExploreCFGForward */ true,
864  /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
865 
866  for (Function &F : M) {
867  for (Instruction &I : instructions(F)) {
868  OS << "-- Explore context of: " << I << "\n";
869  for (const Instruction *CI : Explorer.range(&I))
870  OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
871  }
872  }
873  return PreservedAnalyses::all();
874 }
llvm::LoopSafetyInfo::computeBlockColors
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
Definition: MustExecute.cpp:104
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::createMustExecutePrinter
FunctionPass * createMustExecutePrinter()
Definition: MustExecute.cpp:339
llvm::MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction
const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the next instruction that is guaranteed to be executed after PP.
Definition: MustExecute.cpp:704
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:167
llvm::createMustBeExecutedContextPrinter
ModulePass * createMustBeExecutedContextPrinter()
Definition: MustExecute.cpp:356
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:137
llvm::LoopSafetyInfo::allLoopPathsLeadToBlock
bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB, const DominatorTree *DT) const
Return true if we must reach the block BB under assumption that the loop CurLoop is entered.
Definition: MustExecute.cpp:190
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::MustBeExecutedContextExplorer::range
llvm::iterator_range< iterator > range(const Instruction *PP)
}
Definition: MustExecute.h:442
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:268
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::initializeMustExecutePrinterPass
void initializeMustExecutePrinterPass(PassRegistry &)
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
llvm::ICFLoopSafetyInfo::blockMayThrow
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:71
InstIterator.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::MustBeExecutedContextExplorer::ExploreInterBlock
const bool ExploreInterBlock
Parameter that limit the performed exploration.
Definition: MustExecute.h:516
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
llvm::InstructionPrecedenceTracking::insertInstructionTo
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Notifies this tracking that we are going to insert a new instruction Inst to the basic block BB.
Definition: InstructionPrecedenceTracking.cpp:109
ValueTracking.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1835
Instructions
Code Generation Notes for reduce the size of the ISel and reduce repetition in the implementation In a small number of this can cause even when no optimisation has taken place Instructions
Definition: MSA.txt:11
Module.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1290
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::Optional
Definition: APInt.h:33
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
llvm::SmallPtrSet< const BasicBlock *, 4 >
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:285
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::MustBeExecutedContextExplorer::ExploreCFGForward
const bool ExploreCFGForward
Definition: MustExecute.h:517
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::SimpleLoopSafetyInfo
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
Definition: MustExecute.h:110
MustExecute.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock::getUniqueSuccessor
const BasicBlock * getUniqueSuccessor() const
Return the successor of this block if it has a unique successor.
Definition: BasicBlock.cpp:323
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::classifyEHPersonality
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Definition: EHPersonalities.cpp:22
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
FormattedStream.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:803
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
PostDominators.h
llvm::PostDominatorTreeWrapperPass
Definition: PostDominators.h:73
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:194
llvm::LoopSafetyInfo::getBlockColors
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
Definition: MustExecute.cpp:32
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
false
Definition: StackSlotColoring.cpp:141
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:187
llvm::Instruction
Definition: Instruction.h:42
be
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can be
Definition: README.txt:14
llvm::MustBeExecutedIterator
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
Definition: MustExecute.h:272
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::MemoryWriteTracking::mayWriteToMemory
bool mayWriteToMemory(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block may write memory.
Definition: InstructionPrecedenceTracking.h:131
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::Function::hasPersonalityFn
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:778
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute", "Instructions which execute on loop entry", false, true) INITIALIZE_PASS_END(MustExecutePrinter
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:815
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:147
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
collectTransitivePredecessors
static void collectTransitivePredecessors(const Loop *CurLoop, const BasicBlock *BB, SmallPtrSetImpl< const BasicBlock * > &Predecessors)
Collect all blocks from CurLoop which lie on all possible paths from the header of CurLoop (inclusive...
Definition: MustExecute.cpp:160
llvm::MemoryWriteTracking::isDominatedByMemoryWriteFromSameBlock
bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn)
Returns true if the first memory writing instruction of Insn's block exists and dominates Insn.
Definition: InstructionPrecedenceTracking.h:137
AssemblyAnnotationWriter.h
llvm::SmallPtrSetImplBase::empty
bool empty() const
Definition: SmallPtrSet.h:92
llvm::MustBeExecutedContextPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: MustExecute.cpp:848
llvm::Function::hasFnAttribute
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:628
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::isGuaranteedToExecuteForEveryIteration
bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)
Return true if this function can prove that the instruction I is executed for every iteration of the ...
Definition: ValueTracking.cpp:5535
llvm::MustExecutePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MustExecute.cpp:837
llvm::colorEHFunclets
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
Definition: EHPersonalities.cpp:85
llvm::MustBeExecutedContextExplorer::ExploreCFGBackward
const bool ExploreCFGBackward
Definition: MustExecute.h:518
isMustExecuteIn
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
Definition: MustExecute.cpp:398
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LegalityPredicates::all
Predicate all(Predicate P0, Predicate P1)
True iff P0 and P1 are true.
Definition: LegalizerInfo.h:228
llvm::DenseMap
Definition: DenseMap.h:714
llvm::ICFLoopSafetyInfo::anyBlockMayThrow
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:75
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:989
I
#define I(x, y, z)
Definition: MD5.cpp:58
StringExtras.h
llvm::isScopedEHPersonality
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch,...
Definition: EHPersonalities.h:79
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
llvm::ICFLoopSafetyInfo::doesNotWriteMemoryBefore
bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop) const
Returns true if we could not execute a memory-modifying instruction before we enter BB under assumpti...
Definition: MustExecute.cpp:275
llvm::InstructionPrecedenceTracking::removeInstruction
void removeInstruction(const Instruction *Inst)
Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...
Definition: InstructionPrecedenceTracking.cpp:115
llvm::formatted_raw_ostream
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
Definition: FormattedStream.h:30
llvm::initializeMustBeExecutedContextPrinterPass
void initializeMustBeExecutedContextPrinterPass(PassRegistry &)
llvm::ilist_node_with_parent::getPrevNode
NodeTy * getPrevNode()
Definition: ilist_node.h:275
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
mustexecute
print mustexecute
Definition: MustExecute.cpp:336
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::SimpleLoopSafetyInfo::computeLoopSafetyInfo
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:51
llvm::MustBeExecutedContextExplorer
A "must be executed context" for a given program point PP is the set of instructions,...
Definition: MustExecute.h:386
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
CFG.h
contexts
print must be executed contexts
Definition: MustExecute.cpp:352
llvm::LoopInfo
Definition: LoopInfo.h:1105
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
getOrCreateCachedOptional
static V getOrCreateCachedOptional(K Key, DenseMap< K, Optional< V >> &Map, FnTy &&Fn, ArgsTy &&... args)
Lookup Key in Map and return the result, potentially after initializing the optional through Fn(args)...
Definition: MustExecute.cpp:492
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:293
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1818
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoopSafetyInfo::blockMayThrow
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
llvm::ICFLoopSafetyInfo::insertInstructionTo
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Inform the safety info that we are planning to insert a new instruction Inst into the basic block BB.
Definition: MustExecute.cpp:93
llvm::ImplicitControlFlowTracking::isDominatedByICFIFromSameBlock
bool isDominatedByICFIFromSameBlock(const Instruction *Insn)
Returns true if the first ICFI of Insn's block exists and dominates Insn.
Definition: InstructionPrecedenceTracking.h:114
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::SimpleLoopSafetyInfo::anyBlockMayThrow
bool anyBlockMayThrow() const override
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:47
llvm::InstructionPrecedenceTracking::clear
void clear()
Invalidates all information from this tracking.
Definition: InstructionPrecedenceTracking.cpp:129
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:318
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::ICFLoopSafetyInfo::removeInstruction
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
Definition: MustExecute.cpp:99
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::AssemblyAnnotationWriter
Definition: AssemblyAnnotationWriter.h:27
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5473
llvm::AArch64CC::LS
@ LS
Definition: AArch64BaseInfo.h:264
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
PassManager.h
llvm::LoopSafetyInfo::copyColors
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
Definition: MustExecute.cpp:36
llvm::ImplicitControlFlowTracking::hasICF
bool hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow.
Definition: InstructionPrecedenceTracking.h:109
maybeEndlessLoop
static bool maybeEndlessLoop(const Loop &L)
Return true if L might be an endless loop.
Definition: MustExecute.cpp:472
llvm::Function::getPersonalityFn
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1908
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::ExplorationDirection::FORWARD
@ FORWARD
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction
const Instruction * getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, const Instruction *PP)
Return the previous instr.
Definition: MustExecute.cpp:761
PostOrderIterator.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:659
llvm::ICFLoopSafetyInfo::computeLoopSafetyInfo
void computeLoopSafetyInfo(const Loop *CurLoop) override
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:79
llvm::BasicBlock::getFirstNonPHIOrDbg
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:216
llvm::Optional::value
constexpr const T & value() const &
Definition: Optional.h:313
llvm::ExplorationDirection::BACKWARD
@ BACKWARD
llvm::SimpleLoopSafetyInfo::blockMayThrow
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:42
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
llvm::SmallPtrSetImpl< const BasicBlock * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:931
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
CanProveNotTakenFirstIteration
static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, const DominatorTree *DT, const Loop *CurLoop)
Return true if we can prove that the given ExitBlock is not reached on the first iteration of the giv...
Definition: MustExecute.cpp:117
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::ICFLoopSafetyInfo::isGuaranteedToExecute
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
Definition: MustExecute.cpp:268
llvm::PostDominatorTreeAnalysis
Analysis pass which computes a PostDominatorTree.
Definition: PostDominators.h:47
llvm::SimpleLoopSafetyInfo::isGuaranteedToExecute
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const override
Returns true if the instruction in a loop is guaranteed to execute at least once.
Definition: MustExecute.cpp:249
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::MustBeExecutedContextExplorer::findBackwardJoinPoint
const BasicBlock * findBackwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in backward direction.
Definition: MustExecute.cpp:637
llvm::simplifyCmpInst
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
Definition: InstructionSimplify.cpp:5619
raw_ostream.h
llvm::TinyPtrVector
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
llvm::MustBeExecutedContextExplorer::findForwardJoinPoint
const BasicBlock * findForwardJoinPoint(const BasicBlock *InitBB)
Find the next join point from InitBB in forward direction.
Definition: MustExecute.cpp:501
InitializePasses.h
llvm::MustBeExecutedIterator::MustBeExecutedIterator
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default
llvm::mayContainIrreducibleControl
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
Definition: MustExecute.cpp:480
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:337
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1265
llvm::containsIrreducibleCFG
bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)
Return true if the control flow in RPOTraversal is irreducible.
Definition: CFG.h:136
Passes.h
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38