LLVM  10.0.0svn
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/Analysis/CFG.h"
13 #include "llvm/Analysis/LoopInfo.h"
14 #include "llvm/Analysis/Passes.h"
17 #include "llvm/IR/DataLayout.h"
18 #include "llvm/IR/InstIterator.h"
19 #include "llvm/IR/LLVMContext.h"
20 #include "llvm/IR/Module.h"
24 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "must-execute"
28 
31  return BlockColors;
32 }
33 
35  ColorVector &ColorsForNewBlock = BlockColors[New];
36  ColorVector &ColorsForOldBlock = BlockColors[Old];
37  ColorsForNewBlock = ColorsForOldBlock;
38 }
39 
41  (void)BB;
42  return anyBlockMayThrow();
43 }
44 
46  return MayThrow;
47 }
48 
50  assert(CurLoop != nullptr && "CurLoop can't be null");
51  BasicBlock *Header = CurLoop->getHeader();
52  // Iterate over header and compute safety info.
53  HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
54  MayThrow = HeaderMayThrow;
55  // Iterate over loop instructions and compute safety info.
56  // Skip header as it has been computed and stored in HeaderMayThrow.
57  // The first block in loopinfo.Blocks is guaranteed to be the header.
58  assert(Header == *CurLoop->getBlocks().begin() &&
59  "First block must be header");
60  for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
61  BBE = CurLoop->block_end();
62  (BB != BBE) && !MayThrow; ++BB)
64 
65  computeBlockColors(CurLoop);
66 }
67 
69  return ICF.hasICF(BB);
70 }
71 
73  return MayThrow;
74 }
75 
77  assert(CurLoop != nullptr && "CurLoop can't be null");
78  ICF.clear();
79  MW.clear();
80  MayThrow = false;
81  // Figure out the fact that at least one block may throw.
82  for (auto &BB : CurLoop->blocks())
83  if (ICF.hasICF(&*BB)) {
84  MayThrow = true;
85  break;
86  }
87  computeBlockColors(CurLoop);
88 }
89 
91  const BasicBlock *BB) {
92  ICF.insertInstructionTo(Inst, BB);
93  MW.insertInstructionTo(Inst, BB);
94 }
95 
97  ICF.removeInstruction(Inst);
98  MW.removeInstruction(Inst);
99 }
100 
102  // Compute funclet colors if we might sink/hoist in a function with a funclet
103  // personality routine.
104  Function *Fn = CurLoop->getHeader()->getParent();
105  if (Fn->hasPersonalityFn())
106  if (Constant *PersonalityFn = Fn->getPersonalityFn())
107  if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
108  BlockColors = colorEHFunclets(*Fn);
109 }
110 
111 /// Return true if we can prove that the given ExitBlock is not reached on the
112 /// first iteration of the given loop. That is, the backedge of the loop must
113 /// be executed before the ExitBlock is executed in any dynamic execution trace.
114 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
115  const DominatorTree *DT,
116  const Loop *CurLoop) {
117  auto *CondExitBlock = ExitBlock->getSinglePredecessor();
118  if (!CondExitBlock)
119  // expect unique exits
120  return false;
121  assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
122  auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
123  if (!BI || !BI->isConditional())
124  return false;
125  // If condition is constant and false leads to ExitBlock then we always
126  // execute the true branch.
127  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
128  return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
129  auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
130  if (!Cond)
131  return false;
132  // todo: this would be a lot more powerful if we used scev, but all the
133  // plumbing is currently missing to pass a pointer in from the pass
134  // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
135  auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
136  auto *RHS = Cond->getOperand(1);
137  if (!LHS || LHS->getParent() != CurLoop->getHeader())
138  return false;
139  auto DL = ExitBlock->getModule()->getDataLayout();
140  auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
141  auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
142  IVStart, RHS,
143  {DL, /*TLI*/ nullptr,
144  DT, /*AC*/ nullptr, BI});
145  auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
146  if (!SimpleCst)
147  return false;
148  if (ExitBlock == BI->getSuccessor(0))
149  return SimpleCst->isZeroValue();
150  assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
151  return SimpleCst->isAllOnesValue();
152 }
153 
154 /// Collect all blocks from \p CurLoop which lie on all possible paths from
155 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
156 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
158  const Loop *CurLoop, const BasicBlock *BB,
159  SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
160  assert(Predecessors.empty() && "Garbage in predecessors set?");
161  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
162  if (BB == CurLoop->getHeader())
163  return;
165  for (auto *Pred : predecessors(BB)) {
166  Predecessors.insert(Pred);
167  WorkList.push_back(Pred);
168  }
169  while (!WorkList.empty()) {
170  auto *Pred = WorkList.pop_back_val();
171  assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
172  // We are not interested in backedges and we don't want to leave loop.
173  if (Pred == CurLoop->getHeader())
174  continue;
175  // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
176  // blocks of this inner loop, even those that are always executed AFTER the
177  // BB. It may make our analysis more conservative than it could be, see test
178  // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
179  // We can ignore backedge of all loops containing BB to get a sligtly more
180  // optimistic result.
181  for (auto *PredPred : predecessors(Pred))
182  if (Predecessors.insert(PredPred).second)
183  WorkList.push_back(PredPred);
184  }
185 }
186 
188  const BasicBlock *BB,
189  const DominatorTree *DT) const {
190  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
191 
192  // Fast path: header is always reached once the loop is entered.
193  if (BB == CurLoop->getHeader())
194  return true;
195 
196  // Collect all transitive predecessors of BB in the same loop. This set will
197  // be a subset of the blocks within the loop.
199  collectTransitivePredecessors(CurLoop, BB, Predecessors);
200 
201  // Make sure that all successors of, all predecessors of BB which are not
202  // dominated by BB, are either:
203  // 1) BB,
204  // 2) Also predecessors of BB,
205  // 3) Exit blocks which are not taken on 1st iteration.
206  // Memoize blocks we've already checked.
207  SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
208  for (auto *Pred : Predecessors) {
209  // Predecessor block may throw, so it has a side exit.
210  if (blockMayThrow(Pred))
211  return false;
212 
213  // BB dominates Pred, so if Pred runs, BB must run.
214  // This is true when Pred is a loop latch.
215  if (DT->dominates(BB, Pred))
216  continue;
217 
218  for (auto *Succ : successors(Pred))
219  if (CheckedSuccessors.insert(Succ).second &&
220  Succ != BB && !Predecessors.count(Succ))
221  // By discharging conditions that are not executed on the 1st iteration,
222  // we guarantee that *at least* on the first iteration all paths from
223  // header that *may* execute will lead us to the block of interest. So
224  // that if we had virtually peeled one iteration away, in this peeled
225  // iteration the set of predecessors would contain only paths from
226  // header to BB without any exiting edges that may execute.
227  //
228  // TODO: We only do it for exiting edges currently. We could use the
229  // same function to skip some of the edges within the loop if we know
230  // that they will not be taken on the 1st iteration.
231  //
232  // TODO: If we somehow know the number of iterations in loop, the same
233  // check may be done for any arbitrary N-th iteration as long as N is
234  // not greater than minimum number of iterations in this loop.
235  if (CurLoop->contains(Succ) ||
236  !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
237  return false;
238  }
239 
240  // All predecessors can only lead us to BB.
241  return true;
242 }
243 
244 /// Returns true if the instruction in a loop is guaranteed to execute at least
245 /// once.
247  const DominatorTree *DT,
248  const Loop *CurLoop) const {
249  // If the instruction is in the header block for the loop (which is very
250  // common), it is always guaranteed to dominate the exit blocks. Since this
251  // is a common case, and can save some work, check it now.
252  if (Inst.getParent() == CurLoop->getHeader())
253  // If there's a throw in the header block, we can't guarantee we'll reach
254  // Inst unless we can prove that Inst comes before the potential implicit
255  // exit. At the moment, we use a (cheap) hack for the common case where
256  // the instruction of interest is the first one in the block.
257  return !HeaderMayThrow ||
258  Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
259 
260  // If there is a path from header to exit or latch that doesn't lead to our
261  // instruction's block, return false.
262  return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
263 }
264 
266  const DominatorTree *DT,
267  const Loop *CurLoop) const {
268  return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
269  allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
270 }
271 
273  const Loop *CurLoop) const {
274  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
275 
276  // Fast path: there are no instructions before header.
277  if (BB == CurLoop->getHeader())
278  return true;
279 
280  // Collect all transitive predecessors of BB in the same loop. This set will
281  // be a subset of the blocks within the loop.
283  collectTransitivePredecessors(CurLoop, BB, Predecessors);
284  // Find if there any instruction in either predecessor that could write
285  // to memory.
286  for (auto *Pred : Predecessors)
287  if (MW.mayWriteToMemory(Pred))
288  return false;
289  return true;
290 }
291 
293  const Loop *CurLoop) const {
294  auto *BB = I.getParent();
295  assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
296  return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
297  doesNotWriteMemoryBefore(BB, CurLoop);
298 }
299 
300 namespace {
301  struct MustExecutePrinter : public FunctionPass {
302 
303  static char ID; // Pass identification, replacement for typeid
304  MustExecutePrinter() : FunctionPass(ID) {
306  }
307  void getAnalysisUsage(AnalysisUsage &AU) const override {
308  AU.setPreservesAll();
311  }
312  bool runOnFunction(Function &F) override;
313  };
314  struct MustBeExecutedContextPrinter : public ModulePass {
315  static char ID;
316 
317  MustBeExecutedContextPrinter() : ModulePass(ID) {
319  }
320  void getAnalysisUsage(AnalysisUsage &AU) const override {
321  AU.setPreservesAll();
322  }
323  bool runOnModule(Module &M) override;
324  };
325 }
326 
327 char MustExecutePrinter::ID = 0;
328 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
329  "Instructions which execute on loop entry", false, true)
332 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
333  "Instructions which execute on loop entry", false, true)
334 
336  return new MustExecutePrinter();
337 }
338 
341  MustBeExecutedContextPrinter, "print-must-be-executed-contexts",
342  "print the must-be-executed-contexed for all instructions", false, true)
346 INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
347  "print-must-be-executed-contexts",
348  "print the must-be-executed-contexed for all instructions",
349  false, true)
350 
352  return new MustBeExecutedContextPrinter();
353 }
354 
355 bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
356  MustBeExecutedContextExplorer Explorer(true);
357  for (Function &F : M) {
358  for (Instruction &I : instructions(F)) {
359  dbgs() << "-- Explore context of: " << I << "\n";
360  for (const Instruction *CI : Explorer.range(&I))
361  dbgs() << " [F: " << CI->getFunction()->getName() << "] " << *CI
362  << "\n";
363  }
364  }
365 
366  return false;
367 }
368 
369 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
370  // TODO: merge these two routines. For the moment, we display the best
371  // result obtained by *either* implementation. This is a bit unfair since no
372  // caller actually gets the full power at the moment.
374  LSI.computeLoopSafetyInfo(L);
375  return LSI.isGuaranteedToExecute(I, DT, L) ||
377 }
378 
379 namespace {
380 /// An assembly annotator class to print must execute information in
381 /// comments.
382 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
384 
385 public:
386  MustExecuteAnnotatedWriter(const Function &F,
387  DominatorTree &DT, LoopInfo &LI) {
388  for (auto &I: instructions(F)) {
389  Loop *L = LI.getLoopFor(I.getParent());
390  while (L) {
391  if (isMustExecuteIn(I, L, &DT)) {
392  MustExec[&I].push_back(L);
393  }
394  L = L->getParentLoop();
395  };
396  }
397  }
398  MustExecuteAnnotatedWriter(const Module &M,
399  DominatorTree &DT, LoopInfo &LI) {
400  for (auto &F : M)
401  for (auto &I: instructions(F)) {
402  Loop *L = LI.getLoopFor(I.getParent());
403  while (L) {
404  if (isMustExecuteIn(I, L, &DT)) {
405  MustExec[&I].push_back(L);
406  }
407  L = L->getParentLoop();
408  };
409  }
410  }
411 
412 
413  void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
414  if (!MustExec.count(&V))
415  return;
416 
417  const auto &Loops = MustExec.lookup(&V);
418  const auto NumLoops = Loops.size();
419  if (NumLoops > 1)
420  OS << " ; (mustexec in " << NumLoops << " loops: ";
421  else
422  OS << " ; (mustexec in: ";
423 
424  bool first = true;
425  for (const Loop *L : Loops) {
426  if (!first)
427  OS << ", ";
428  first = false;
429  OS << L->getHeader()->getName();
430  }
431  OS << ")";
432  }
433 };
434 } // namespace
435 
437  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
438  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
439 
440  MustExecuteAnnotatedWriter Writer(F, DT, LI);
441  F.print(dbgs(), &Writer);
442 
443  return false;
444 }
445 
446 const Instruction *
448  MustBeExecutedIterator &It, const Instruction *PP) {
449  if (!PP)
450  return PP;
451  LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
452 
453  // If we explore only inside a given basic block we stop at terminators.
454  if (!ExploreInterBlock && PP->isTerminator()) {
455  LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
456  return nullptr;
457  }
458 
459  // If we do not traverse the call graph we check if we can make progress in
460  // the current function. First, check if the instruction is guaranteed to
461  // transfer execution to the successor.
462  bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
463  if (!TransfersExecution)
464  return nullptr;
465 
466  // If this is not a terminator we know that there is a single instruction
467  // after this one that is executed next if control is transfered. If not,
468  // we can try to go back to a call site we entered earlier. If none exists, we
469  // do not know any instruction that has to be executd next.
470  if (!PP->isTerminator()) {
471  const Instruction *NextPP = PP->getNextNode();
472  LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
473  return NextPP;
474  }
475 
476  // Finally, we have to handle terminators, trivial ones first.
477  assert(PP->isTerminator() && "Expected a terminator!");
478 
479  // A terminator without a successor is not handled yet.
480  if (PP->getNumSuccessors() == 0) {
481  LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
482  return nullptr;
483  }
484 
485  // A terminator with a single successor, we will continue at the beginning of
486  // that one.
487  if (PP->getNumSuccessors() == 1) {
488  LLVM_DEBUG(
489  dbgs() << "\tUnconditional terminator, continue with successor\n");
490  return &PP->getSuccessor(0)->front();
491  }
492 
493  LLVM_DEBUG(dbgs() << "\tNo join point found\n");
494  return nullptr;
495 }
496 
498  MustBeExecutedContextExplorer &Explorer, const Instruction *I)
499  : Explorer(Explorer), CurInst(I) {
500  reset(I);
501 }
502 
503 void MustBeExecutedIterator::reset(const Instruction *I) {
504  CurInst = I;
505  Visited.clear();
506  Visited.insert(I);
507 }
508 
509 const Instruction *MustBeExecutedIterator::advance() {
510  assert(CurInst && "Cannot advance an end iterator!");
511  const Instruction *Next =
512  Explorer.getMustBeExecutedNextInstruction(*this, CurInst);
513  if (Next && !Visited.insert(Next).second)
514  Next = nullptr;
515  return Next;
516 }
virtual void computeLoopSafetyInfo(const Loop *CurLoop)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:49
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:90
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
virtual bool blockMayThrow(const BasicBlock *BB) const =0
Returns true iff the block BB potentially may throw exception.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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...
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:160
bool isTerminator() const
Definition: Instruction.h:128
virtual bool anyBlockMayThrow() const =0
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
virtual bool blockMayThrow(const BasicBlock *BB) const
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:68
void initializeMustBeExecutedContextPrinterPass(PassRegistry &)
BasicBlock * getSuccessor(unsigned i) const
F(f)
block Block Frequency true
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
Simple and conservative implementation of LoopSafetyInfo that can give false-positive answers to its ...
Definition: MustExecute.h:104
AnalysisUsage & addRequired()
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:140
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Hexagon Hardware Loops
virtual void computeLoopSafetyInfo(const Loop *CurLoop)
Computes safety information for a loop checks loop body & header for the possibility of may throw exc...
Definition: MustExecute.cpp:76
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:928
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
virtual bool anyBlockMayThrow() const
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:72
BlockT * getHeader() const
Definition: LoopInfo.h:105
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...
bool isScopedEHPersonality(EHPersonality Pers)
Returns true if this personality uses scope-style EH IR instructions: catchswitch, catchpad/ret, and cleanuppad/ret.
llvm::iterator_range< iterator > range(const Instruction *PP)
}
Definition: MustExecute.h:413
Must be executed iterators visit stretches of instructions that are guaranteed to be executed togethe...
Definition: MustExecute.h:266
Value * SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
virtual bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const
Returns true if the instruction in a loop is guaranteed to execute at least once. ...
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW=nullptr, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the function to an output stream with an optional AssemblyAnnotationWriter. ...
Definition: AsmWriter.cpp:4184
const Instruction * getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP)
}
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:732
void copyColors(BasicBlock *New, BasicBlock *Old)
Copy colors of block Old into the block New.
Definition: MustExecute.cpp:34
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
FunctionPass * createMustExecutePrinter()
static bool runOnFunction(Function &F, bool PostInlining)
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
virtual bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop) const
Returns true if the instruction in a loop is guaranteed to execute at least once (under the assumptio...
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:240
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Conditional or Unconditional Branch instruction.
This is an important base class in LLVM.
Definition: Constant.h:41
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
const Instruction & front() const
Definition: BasicBlock.h:285
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:370
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Represent the analysis usage information of a pass.
MustBeExecutedIterator(const MustBeExecutedIterator &Other)
Definition: MustExecute.h:278
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute", "Instructions which execute on loop entry", false, true) INITIALIZE_PASS_END(MustExecutePrinter
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
unsigned first
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
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...
void removeInstruction(const Instruction *Inst)
Inform safety info that we are planning to remove the instruction Inst from its block.
Definition: MustExecute.cpp:96
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
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...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Module.h This file contains the declarations for the Module class.
static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT)
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
void computeBlockColors(const Loop *CurLoop)
Computes block colors.
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void setPreservesAll()
Set by analyses that do not transform their input at all.
A "must be executed context" for a given program point PP is the set of instructions, potentially before and after PP, that are executed always when PP is reached.
Definition: MustExecute.h:368
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
print mustexecute
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:154
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass * createMustBeExecutedContextPrinter()
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
block_iterator block_end() const
Definition: LoopInfo.h:160
virtual bool blockMayThrow(const BasicBlock *BB) const
Returns true iff the block BB potentially may throw exception.
Definition: MustExecute.cpp:40
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 ...
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
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:185
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1441
succ_range successors(Instruction *I)
Definition: CFG.h:259
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1208
print Instructions which execute on loop entry
inst_range instructions(Function *F)
Definition: InstIterator.h:133
void initializeMustExecutePrinterPass(PassRegistry &)
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:203
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
virtual bool anyBlockMayThrow() const
Returns true iff any block of the loop for which this info is contains an instruction that may throw ...
Definition: MustExecute.cpp:45
DenseMap< BasicBlock *, ColorVector > colorEHFunclets(Function &F)
If an EH funclet personality is in use (see isFuncletEHPersonality), this will recompute which blocks...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:161
block_iterator block_begin() const
Definition: LoopInfo.h:159
const BasicBlock * getParent() const
Definition: Instruction.h:66
const DenseMap< BasicBlock *, ColorVector > & getBlockColors() const
Returns block colors map that is used to update funclet operand bundles.
Definition: MustExecute.cpp:30