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