LLVM  15.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 (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
63  BBE = CurLoop->block_end();
64  (BB != BBE) && !MayThrow; ++BB)
66 
67  computeBlockColors(CurLoop);
68 }
69 
71  return ICF.hasICF(BB);
72 }
73 
75  return MayThrow;
76 }
77 
79  assert(CurLoop != nullptr && "CurLoop can't be null");
80  ICF.clear();
81  MW.clear();
82  MayThrow = false;
83  // Figure out the fact that at least one block may throw.
84  for (auto &BB : CurLoop->blocks())
85  if (ICF.hasICF(&*BB)) {
86  MayThrow = true;
87  break;
88  }
89  computeBlockColors(CurLoop);
90 }
91 
93  const BasicBlock *BB) {
94  ICF.insertInstructionTo(Inst, BB);
95  MW.insertInstructionTo(Inst, BB);
96 }
97 
99  ICF.removeInstruction(Inst);
100  MW.removeInstruction(Inst);
101 }
102 
104  // Compute funclet colors if we might sink/hoist in a function with a funclet
105  // personality routine.
106  Function *Fn = CurLoop->getHeader()->getParent();
107  if (Fn->hasPersonalityFn())
108  if (Constant *PersonalityFn = Fn->getPersonalityFn())
109  if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
110  BlockColors = colorEHFunclets(*Fn);
111 }
112 
113 /// Return true if we can prove that the given ExitBlock is not reached on the
114 /// first iteration of the given loop. That is, the backedge of the loop must
115 /// be executed before the ExitBlock is executed in any dynamic execution trace.
116 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
117  const DominatorTree *DT,
118  const Loop *CurLoop) {
119  auto *CondExitBlock = ExitBlock->getSinglePredecessor();
120  if (!CondExitBlock)
121  // expect unique exits
122  return false;
123  assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
124  auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
125  if (!BI || !BI->isConditional())
126  return false;
127  // If condition is constant and false leads to ExitBlock then we always
128  // execute the true branch.
129  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
130  return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
131  auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
132  if (!Cond)
133  return false;
134  // todo: this would be a lot more powerful if we used scev, but all the
135  // plumbing is currently missing to pass a pointer in from the pass
136  // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
137  auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
138  auto *RHS = Cond->getOperand(1);
139  if (!LHS || LHS->getParent() != CurLoop->getHeader())
140  return false;
141  auto DL = ExitBlock->getModule()->getDataLayout();
142  auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
143  auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
144  IVStart, RHS,
145  {DL, /*TLI*/ nullptr,
146  DT, /*AC*/ nullptr, BI});
147  auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
148  if (!SimpleCst)
149  return false;
150  if (ExitBlock == BI->getSuccessor(0))
151  return SimpleCst->isZeroValue();
152  assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
153  return SimpleCst->isAllOnesValue();
154 }
155 
156 /// Collect all blocks from \p CurLoop which lie on all possible paths from
157 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
158 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
160  const Loop *CurLoop, const BasicBlock *BB,
161  SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
162  assert(Predecessors.empty() && "Garbage in predecessors set?");
163  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
164  if (BB == CurLoop->getHeader())
165  return;
167  for (auto *Pred : predecessors(BB)) {
168  Predecessors.insert(Pred);
169  WorkList.push_back(Pred);
170  }
171  while (!WorkList.empty()) {
172  auto *Pred = WorkList.pop_back_val();
173  assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
174  // We are not interested in backedges and we don't want to leave loop.
175  if (Pred == CurLoop->getHeader())
176  continue;
177  // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
178  // blocks of this inner loop, even those that are always executed AFTER the
179  // BB. It may make our analysis more conservative than it could be, see test
180  // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
181  // We can ignore backedge of all loops containing BB to get a sligtly more
182  // optimistic result.
183  for (auto *PredPred : predecessors(Pred))
184  if (Predecessors.insert(PredPred).second)
185  WorkList.push_back(PredPred);
186  }
187 }
188 
190  const BasicBlock *BB,
191  const DominatorTree *DT) const {
192  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
193 
194  // Fast path: header is always reached once the loop is entered.
195  if (BB == CurLoop->getHeader())
196  return true;
197 
198  // Collect all transitive predecessors of BB in the same loop. This set will
199  // be a subset of the blocks within the loop.
201  collectTransitivePredecessors(CurLoop, BB, Predecessors);
202 
203  // Make sure that all successors of, all predecessors of BB which are not
204  // dominated by BB, are either:
205  // 1) BB,
206  // 2) Also predecessors of BB,
207  // 3) Exit blocks which are not taken on 1st iteration.
208  // Memoize blocks we've already checked.
209  SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
210  for (auto *Pred : Predecessors) {
211  // Predecessor block may throw, so it has a side exit.
212  if (blockMayThrow(Pred))
213  return false;
214 
215  // BB dominates Pred, so if Pred runs, BB must run.
216  // This is true when Pred is a loop latch.
217  if (DT->dominates(BB, Pred))
218  continue;
219 
220  for (auto *Succ : successors(Pred))
221  if (CheckedSuccessors.insert(Succ).second &&
222  Succ != BB && !Predecessors.count(Succ))
223  // By discharging conditions that are not executed on the 1st iteration,
224  // we guarantee that *at least* on the first iteration all paths from
225  // header that *may* execute will lead us to the block of interest. So
226  // that if we had virtually peeled one iteration away, in this peeled
227  // iteration the set of predecessors would contain only paths from
228  // header to BB without any exiting edges that may execute.
229  //
230  // TODO: We only do it for exiting edges currently. We could use the
231  // same function to skip some of the edges within the loop if we know
232  // that they will not be taken on the 1st iteration.
233  //
234  // TODO: If we somehow know the number of iterations in loop, the same
235  // check may be done for any arbitrary N-th iteration as long as N is
236  // not greater than minimum number of iterations in this loop.
237  if (CurLoop->contains(Succ) ||
238  !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
239  return false;
240  }
241 
242  // All predecessors can only lead us to BB.
243  return true;
244 }
245 
246 /// Returns true if the instruction in a loop is guaranteed to execute at least
247 /// once.
249  const DominatorTree *DT,
250  const Loop *CurLoop) const {
251  // If the instruction is in the header block for the loop (which is very
252  // common), it is always guaranteed to dominate the exit blocks. Since this
253  // is a common case, and can save some work, check it now.
254  if (Inst.getParent() == CurLoop->getHeader())
255  // If there's a throw in the header block, we can't guarantee we'll reach
256  // Inst unless we can prove that Inst comes before the potential implicit
257  // exit. At the moment, we use a (cheap) hack for the common case where
258  // the instruction of interest is the first one in the block.
259  return !HeaderMayThrow ||
260  Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
261 
262  // If there is a path from header to exit or latch that doesn't lead to our
263  // instruction's block, return false.
264  return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
265 }
266 
268  const DominatorTree *DT,
269  const Loop *CurLoop) const {
270  return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
271  allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
272 }
273 
275  const Loop *CurLoop) const {
276  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
277 
278  // Fast path: there are no instructions before header.
279  if (BB == CurLoop->getHeader())
280  return true;
281 
282  // Collect all transitive predecessors of BB in the same loop. This set will
283  // be a subset of the blocks within the loop.
285  collectTransitivePredecessors(CurLoop, BB, Predecessors);
286  // Find if there any instruction in either predecessor that could write
287  // to memory.
288  for (auto *Pred : Predecessors)
289  if (MW.mayWriteToMemory(Pred))
290  return false;
291  return true;
292 }
293 
295  const Loop *CurLoop) const {
296  auto *BB = I.getParent();
297  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
299  doesNotWriteMemoryBefore(BB, CurLoop);
300 }
301 
302 namespace {
303 struct MustExecutePrinter : public FunctionPass {
304 
305  static char ID; // Pass identification, replacement for typeid
306  MustExecutePrinter() : FunctionPass(ID) {
308  }
309  void getAnalysisUsage(AnalysisUsage &AU) const override {
310  AU.setPreservesAll();
313  }
314  bool runOnFunction(Function &F) override;
315 };
316 struct MustBeExecutedContextPrinter : public ModulePass {
317  static char ID;
318 
319  MustBeExecutedContextPrinter() : ModulePass(ID) {
322  }
323  void getAnalysisUsage(AnalysisUsage &AU) const override {
324  AU.setPreservesAll();
325  }
326  bool runOnModule(Module &M) override;
327 };
328 }
329 
330 char MustExecutePrinter::ID = 0;
331 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
332  "Instructions which execute on loop entry", false, true)
335 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
336  "Instructions which execute on loop entry", false, true)
337 
339  return new MustExecutePrinter();
340 }
341 
343 INITIALIZE_PASS_BEGIN(MustBeExecutedContextPrinter,
344  "print-must-be-executed-contexts",
345  "print the must-be-executed-context for all instructions",
346  false, true)
350 INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
351  "print-must-be-executed-contexts",
352  "print the must-be-executed-context for all instructions",
353  false, true)
354 
356  return new MustBeExecutedContextPrinter();
357 }
358 
359 bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
360  // We provide non-PM analysis here because the old PM doesn't like to query
361  // function passes from a module pass.
365 
366  GetterTy<LoopInfo> LIGetter = [&](const Function &F) {
367  DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function &>(F)));
368  LIs.push_back(std::make_unique<LoopInfo>(*DTs.back()));
369  return LIs.back().get();
370  };
371  GetterTy<DominatorTree> DTGetter = [&](const Function &F) {
372  DTs.push_back(std::make_unique<DominatorTree>(const_cast<Function&>(F)));
373  return DTs.back().get();
374  };
375  GetterTy<PostDominatorTree> PDTGetter = [&](const Function &F) {
376  PDTs.push_back(
377  std::make_unique<PostDominatorTree>(const_cast<Function &>(F)));
378  return PDTs.back().get();
379  };
381  /* ExploreInterBlock */ true,
382  /* ExploreCFGForward */ true,
383  /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
384 
385  for (Function &F : M) {
386  for (Instruction &I : instructions(F)) {
387  dbgs() << "-- Explore context of: " << I << "\n";
388  for (const Instruction *CI : Explorer.range(&I))
389  dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI
390  << "\n";
391  }
392  }
393 
394  return false;
395 }
396 
397 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
398  // TODO: merge these two routines. For the moment, we display the best
399  // result obtained by *either* implementation. This is a bit unfair since no
400  // caller actually gets the full power at the moment.
402  LSI.computeLoopSafetyInfo(L);
403  return LSI.isGuaranteedToExecute(I, DT, L) ||
405 }
406 
407 namespace {
408 /// An assembly annotator class to print must execute information in
409 /// comments.
410 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
412 
413 public:
414  MustExecuteAnnotatedWriter(const Function &F,
415  DominatorTree &DT, LoopInfo &LI) {
416  for (auto &I: instructions(F)) {
417  Loop *L = LI.getLoopFor(I.getParent());
418  while (L) {
419  if (isMustExecuteIn(I, L, &DT)) {
420  MustExec[&I].push_back(L);
421  }
422  L = L->getParentLoop();
423  };
424  }
425  }
426  MustExecuteAnnotatedWriter(const Module &M,
427  DominatorTree &DT, LoopInfo &LI) {
428  for (auto &F : M)
429  for (auto &I: instructions(F)) {
430  Loop *L = LI.getLoopFor(I.getParent());
431  while (L) {
432  if (isMustExecuteIn(I, L, &DT)) {
433  MustExec[&I].push_back(L);
434  }
435  L = L->getParentLoop();
436  };
437  }
438  }
439 
440 
441  void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
442  if (!MustExec.count(&V))
443  return;
444 
445  const auto &Loops = MustExec.lookup(&V);
446  const auto NumLoops = Loops.size();
447  if (NumLoops > 1)
448  OS << " ; (mustexec in " << NumLoops << " loops: ";
449  else
450  OS << " ; (mustexec in: ";
451 
452  ListSeparator LS;
453  for (const Loop *L : Loops)
454  OS << LS << L->getHeader()->getName();
455  OS << ")";
456  }
457 };
458 } // namespace
459 
461  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
462  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
463 
464  MustExecuteAnnotatedWriter Writer(F, DT, LI);
465  F.print(dbgs(), &Writer);
466 
467  return false;
468 }
469 
470 /// Return true if \p L might be an endless loop.
471 static bool maybeEndlessLoop(const Loop &L) {
472  if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn))
473  return false;
474  // TODO: Actually try to prove it is not.
475  // TODO: If maybeEndlessLoop is going to be expensive, cache it.
476  return true;
477 }
478 
480  if (!LI)
481  return false;
482  using RPOTraversal = ReversePostOrderTraversal<const Function *>;
483  RPOTraversal FuncRPOT(&F);
484  return containsIrreducibleCFG<const BasicBlock *, const RPOTraversal,
485  const LoopInfo>(FuncRPOT, *LI);
486 }
487 
488 /// Lookup \p Key in \p Map and return the result, potentially after
489 /// initializing the optional through \p Fn(\p args).
490 template <typename K, typename V, typename FnTy, typename... ArgsTy>
492  FnTy &&Fn, ArgsTy&&... args) {
493  Optional<V> &OptVal = Map[Key];
494  if (!OptVal.hasValue())
495  OptVal = Fn(std::forward<ArgsTy>(args)...);
496  return OptVal.getValue();
497 }
498 
499 const BasicBlock *
501  const LoopInfo *LI = LIGetter(*InitBB->getParent());
502  const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent());
503 
504  LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName()
505  << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : ""));
506 
507  const Function &F = *InitBB->getParent();
508  const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
509  const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB;
510  bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) ||
511  (L && !maybeEndlessLoop(*L))) &&
512  F.doesNotThrow();
513  LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "")
514  << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "")
515  << "\n");
516 
517  // Determine the adjacent blocks in the given direction but exclude (self)
518  // loops under certain circumstances.
520  for (const BasicBlock *SuccBB : successors(InitBB)) {
521  bool IsLatch = SuccBB == HeaderBB;
522  // Loop latches are ignored in forward propagation if the loop cannot be
523  // endless and may not throw: control has to go somewhere.
524  if (!WillReturnAndNoThrow || !IsLatch)
525  Worklist.push_back(SuccBB);
526  }
527  LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n");
528 
529  // If there are no other adjacent blocks, there is no join point.
530  if (Worklist.empty())
531  return nullptr;
532 
533  // If there is one adjacent block, it is the join point.
534  if (Worklist.size() == 1)
535  return Worklist[0];
536 
537  // Try to determine a join block through the help of the post-dominance
538  // tree. If no tree was provided, we perform simple pattern matching for one
539  // block conditionals and one block loops only.
540  const BasicBlock *JoinBB = nullptr;
541  if (PDT)
542  if (const auto *InitNode = PDT->getNode(InitBB))
543  if (const auto *IDomNode = InitNode->getIDom())
544  JoinBB = IDomNode->getBlock();
545 
546  if (!JoinBB && Worklist.size() == 2) {
547  const BasicBlock *Succ0 = Worklist[0];
548  const BasicBlock *Succ1 = Worklist[1];
549  const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor();
550  const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor();
551  if (Succ0UniqueSucc == InitBB) {
552  // InitBB -> Succ0 -> InitBB
553  // InitBB -> Succ1 = JoinBB
554  JoinBB = Succ1;
555  } else if (Succ1UniqueSucc == InitBB) {
556  // InitBB -> Succ1 -> InitBB
557  // InitBB -> Succ0 = JoinBB
558  JoinBB = Succ0;
559  } else if (Succ0 == Succ1UniqueSucc) {
560  // InitBB -> Succ0 = JoinBB
561  // InitBB -> Succ1 -> Succ0 = JoinBB
562  JoinBB = Succ0;
563  } else if (Succ1 == Succ0UniqueSucc) {
564  // InitBB -> Succ0 -> Succ1 = JoinBB
565  // InitBB -> Succ1 = JoinBB
566  JoinBB = Succ1;
567  } else if (Succ0UniqueSucc == Succ1UniqueSucc) {
568  // InitBB -> Succ0 -> JoinBB
569  // InitBB -> Succ1 -> JoinBB
570  JoinBB = Succ0UniqueSucc;
571  }
572  }
573 
574  if (!JoinBB && L)
575  JoinBB = L->getUniqueExitBlock();
576 
577  if (!JoinBB)
578  return nullptr;
579 
580  LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n");
581 
582  // In forward direction we check if control will for sure reach JoinBB from
583  // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control
584  // are: infinite loops and instructions that do not necessarily transfer
585  // execution to their successor. To check for them we traverse the CFG from
586  // the adjacent blocks to the JoinBB, looking at all intermediate blocks.
587 
588  // If we know the function is "will-return" and "no-throw" there is no need
589  // for futher checks.
590  if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) {
591 
592  auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) {
594  };
595 
597  while (!Worklist.empty()) {
598  const BasicBlock *ToBB = Worklist.pop_back_val();
599  if (ToBB == JoinBB)
600  continue;
601 
602  // Make sure all loops in-between are finite.
603  if (!Visited.insert(ToBB).second) {
604  if (!F.hasFnAttribute(Attribute::WillReturn)) {
605  if (!LI)
606  return nullptr;
607 
608  bool MayContainIrreducibleControl = getOrCreateCachedOptional(
609  &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI);
610  if (MayContainIrreducibleControl)
611  return nullptr;
612 
613  const Loop *L = LI->getLoopFor(ToBB);
614  if (L && maybeEndlessLoop(*L))
615  return nullptr;
616  }
617 
618  continue;
619  }
620 
621  // Make sure the block has no instructions that could stop control
622  // transfer.
623  bool TransfersExecution = getOrCreateCachedOptional(
624  ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB);
625  if (!TransfersExecution)
626  return nullptr;
627 
628  append_range(Worklist, successors(ToBB));
629  }
630  }
631 
632  LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n");
633  return JoinBB;
634 }
635 const BasicBlock *
637  const LoopInfo *LI = LIGetter(*InitBB->getParent());
638  const DominatorTree *DT = DTGetter(*InitBB->getParent());
639  LLVM_DEBUG(dbgs() << "\tFind backward join point for " << InitBB->getName()
640  << (LI ? " [LI]" : "") << (DT ? " [DT]" : ""));
641 
642  // Try to determine a join block through the help of the dominance tree. If no
643  // tree was provided, we perform simple pattern matching for one block
644  // conditionals only.
645  if (DT)
646  if (const auto *InitNode = DT->getNode(InitBB))
647  if (const auto *IDomNode = InitNode->getIDom())
648  return IDomNode->getBlock();
649 
650  const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr;
651  const BasicBlock *HeaderBB = L ? L->getHeader() : nullptr;
652 
653  // Determine the predecessor blocks but ignore backedges.
655  for (const BasicBlock *PredBB : predecessors(InitBB)) {
656  bool IsBackedge =
657  (PredBB == InitBB) || (HeaderBB == InitBB && L->contains(PredBB));
658  // Loop backedges are ignored in backwards propagation: control has to come
659  // from somewhere.
660  if (!IsBackedge)
661  Worklist.push_back(PredBB);
662  }
663 
664  // If there are no other predecessor blocks, there is no join point.
665  if (Worklist.empty())
666  return nullptr;
667 
668  // If there is one predecessor block, it is the join point.
669  if (Worklist.size() == 1)
670  return Worklist[0];
671 
672  const BasicBlock *JoinBB = nullptr;
673  if (Worklist.size() == 2) {
674  const BasicBlock *Pred0 = Worklist[0];
675  const BasicBlock *Pred1 = Worklist[1];
676  const BasicBlock *Pred0UniquePred = Pred0->getUniquePredecessor();
677  const BasicBlock *Pred1UniquePred = Pred1->getUniquePredecessor();
678  if (Pred0 == Pred1UniquePred) {
679  // InitBB <- Pred0 = JoinBB
680  // InitBB <- Pred1 <- Pred0 = JoinBB
681  JoinBB = Pred0;
682  } else if (Pred1 == Pred0UniquePred) {
683  // InitBB <- Pred0 <- Pred1 = JoinBB
684  // InitBB <- Pred1 = JoinBB
685  JoinBB = Pred1;
686  } else if (Pred0UniquePred == Pred1UniquePred) {
687  // InitBB <- Pred0 <- JoinBB
688  // InitBB <- Pred1 <- JoinBB
689  JoinBB = Pred0UniquePred;
690  }
691  }
692 
693  if (!JoinBB && L)
694  JoinBB = L->getHeader();
695 
696  // In backwards direction there is no need to show termination of previous
697  // instructions. If they do not terminate, the code afterward is dead, making
698  // any information/transformation correct anyway.
699  return JoinBB;
700 }
701 
702 const Instruction *
704  MustBeExecutedIterator &It, const Instruction *PP) {
705  if (!PP)
706  return PP;
707  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
708 
709  // If we explore only inside a given basic block we stop at terminators.
710  if (!ExploreInterBlock && PP->isTerminator()) {
711  LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
712  return nullptr;
713  }
714 
715  // If we do not traverse the call graph we check if we can make progress in
716  // the current function. First, check if the instruction is guaranteed to
717  // transfer execution to the successor.
718  bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
719  if (!TransfersExecution)
720  return nullptr;
721 
722  // If this is not a terminator we know that there is a single instruction
723  // after this one that is executed next if control is transfered. If not,
724  // we can try to go back to a call site we entered earlier. If none exists, we
725  // do not know any instruction that has to be executd next.
726  if (!PP->isTerminator()) {
727  const Instruction *NextPP = PP->getNextNode();
728  LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
729  return NextPP;
730  }
731 
732  // Finally, we have to handle terminators, trivial ones first.
733  assert(PP->isTerminator() && "Expected a terminator!");
734 
735  // A terminator without a successor is not handled yet.
736  if (PP->getNumSuccessors() == 0) {
737  LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
738  return nullptr;
739  }
740 
741  // A terminator with a single successor, we will continue at the beginning of
742  // that one.
743  if (PP->getNumSuccessors() == 1) {
744  LLVM_DEBUG(
745  dbgs() << "\tUnconditional terminator, continue with successor\n");
746  return &PP->getSuccessor(0)->front();
747  }
748 
749  // Multiple successors mean we need to find the join point where control flow
750  // converges again. We use the findForwardJoinPoint helper function with
751  // information about the function and helper analyses, if available.
752  if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent()))
753  return &JoinBB->front();
754 
755  LLVM_DEBUG(dbgs() << "\tNo join point found\n");
756  return nullptr;
757 }
758 
759 const Instruction *
761  MustBeExecutedIterator &It, const Instruction *PP) {
762  if (!PP)
763  return PP;
764 
765  bool IsFirst = !(PP->getPrevNode());
766  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP
767  << (IsFirst ? " [IsFirst]" : "") << "\n");
768 
769  // If we explore only inside a given basic block we stop at the first
770  // instruction.
771  if (!ExploreInterBlock && IsFirst) {
772  LLVM_DEBUG(dbgs() << "\tReached block front in intra-block mode, done\n");
773  return nullptr;
774  }
775 
776  // The block and function that contains the current position.
777  const BasicBlock *PPBlock = PP->getParent();
778 
779  // If we are inside a block we know what instruction was executed before, the
780  // previous one.
781  if (!IsFirst) {
782  const Instruction *PrevPP = PP->getPrevNode();
783  LLVM_DEBUG(
784  dbgs() << "\tIntermediate instruction, continue with previous\n");
785  // We did not enter a callee so we simply return the previous instruction.
786  return PrevPP;
787  }
788 
789  // Finally, we have to handle the case where the program point is the first in
790  // a block but not in the function. We use the findBackwardJoinPoint helper
791  // function with information about the function and helper analyses, if
792  // available.
793  if (const BasicBlock *JoinBB = findBackwardJoinPoint(PPBlock))
794  return &JoinBB->back();
795 
796  LLVM_DEBUG(dbgs() << "\tNo join point found\n");
797  return nullptr;
798 }
799 
801  MustBeExecutedContextExplorer &Explorer, const Instruction *I)
802  : Explorer(Explorer), CurInst(I) {
803  reset(I);
804 }
805 
806 void MustBeExecutedIterator::reset(const Instruction *I) {
807  Visited.clear();
808  resetInstruction(I);
809 }
810 
811 void MustBeExecutedIterator::resetInstruction(const Instruction *I) {
812  CurInst = I;
813  Head = Tail = nullptr;
816  if (Explorer.ExploreCFGForward)
817  Head = I;
818  if (Explorer.ExploreCFGBackward)
819  Tail = I;
820 }
821 
822 const Instruction *MustBeExecutedIterator::advance() {
823  assert(CurInst && "Cannot advance an end iterator!");
824  Head = Explorer.getMustBeExecutedNextInstruction(*this, Head);
825  if (Head && Visited.insert({Head, ExplorationDirection ::FORWARD}).second)
826  return Head;
827  Head = nullptr;
828 
829  Tail = Explorer.getMustBeExecutedPrevInstruction(*this, Tail);
830  if (Tail && Visited.insert({Tail, ExplorationDirection ::BACKWARD}).second)
831  return Tail;
832  Tail = nullptr;
833  return nullptr;
834 }
835 
838  auto &LI = AM.getResult<LoopAnalysis>(F);
839  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
840 
841  MustExecuteAnnotatedWriter Writer(F, DT, LI);
842  F.print(OS, &Writer);
843  return PreservedAnalyses::all();
844 }
845 
850  GetterTy<const LoopInfo> LIGetter = [&](const Function &F) {
851  return &FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
852  };
853  GetterTy<const DominatorTree> DTGetter = [&](const Function &F) {
854  return &FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
855  };
856  GetterTy<const PostDominatorTree> PDTGetter = [&](const Function &F) {
857  return &FAM.getResult<PostDominatorTreeAnalysis>(const_cast<Function &>(F));
858  };
859 
861  /* ExploreInterBlock */ true,
862  /* ExploreCFGForward */ true,
863  /* ExploreCFGBackward */ true, LIGetter, DTGetter, PDTGetter);
864 
865  for (Function &F : M) {
866  for (Instruction &I : instructions(F)) {
867  OS << "-- Explore context of: " << I << "\n";
868  for (const Instruction *CI : Explorer.range(&I))
869  OS << " [F: " << CI->getFunction()->getName() << "] " << *CI << "\n";
870  }
871  }
872  return PreservedAnalyses::all();
873 }
llvm::LoopSafetyInfo::computeBlockColors
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
Definition: MustExecute.cpp:103
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:338
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:703
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:160
llvm::createMustBeExecutedContextPrinter
ModulePass * createMustBeExecutedContextPrinter()
Definition: MustExecute.cpp:355
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:189
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
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:152
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:780
llvm::ICFLoopSafetyInfo::blockMayThrow
bool blockMayThrow(const BasicBlock *BB) const override
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:70
InstIterator.h
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:199
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
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:1185
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:1895
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:1271
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:147
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:5560
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:261
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
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:299
llvm::LoopBase::block_end
block_iterator block_end() const
Definition: LoopInfo.h:177
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::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:283
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:21
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:777
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
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:178
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:171
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:777
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:789
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:159
llvm::LoopBase::block_begin
block_iterator block_begin() const
Definition: LoopInfo.h:176
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::MustBeExecutedContextPrinterPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: MustExecute.cpp:847
llvm::Function::hasFnAttribute
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:625
llvm::LoopBase< BasicBlock, Loop >::block_iterator
ArrayRef< BasicBlock * >::const_iterator block_iterator
Definition: LoopInfo.h:175
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:5339
llvm::MustExecutePrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MustExecute.cpp:836
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:81
llvm::MustBeExecutedContextExplorer::ExploreCFGBackward
const bool ExploreCFGBackward
Definition: MustExecute.h:518
isMustExecuteIn
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
Definition: MustExecute.cpp:397
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:716
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:74
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:970
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:274
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())
llvm::Optional::getValue
constexpr const T & getValue() const &
Definition: Optional.h:279
mustexecute
print mustexecute
Definition: MustExecute.cpp:335
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:351
llvm::LoopInfo
Definition: LoopInfo.h:1086
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:178
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:491
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:269
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1811
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:92
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:305
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:309
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:98
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:5277
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:471
llvm::Function::getPersonalityFn
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1895
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:760
PostOrderIterator.h
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
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:78
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::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:937
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:116
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:267
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:248
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:636
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:500
InitializePasses.h
llvm::MustBeExecutedIterator::MustBeExecutedIterator
MustBeExecutedIterator(const MustBeExecutedIterator &Other)=default
llvm::mayContainIrreducibleControl
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
Definition: MustExecute.cpp:479
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:336
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1246
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:37