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