contrib/llvm-project/llvm/include/llvm/Analysis/MustExecute.h

   1 //===- MustExecute.h - Is an instruction known to execute--------*- C++ -*-===//
   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 /// \file
   9 /// Contains a collection of routines for determining if a given instruction is
  10 /// guaranteed to execute if a given point in control flow is reached.  The most
  11 /// common example is an instruction within a loop being provably executed if we
  12 /// branch to the header of it's containing loop.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
  17 #define LLVM_ANALYSIS_MUSTEXECUTE_H
  18
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/Analysis/EHPersonalities.h"
  21 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
  22 #include "llvm/Analysis/LoopInfo.h"
  23 #include "llvm/IR/BasicBlock.h"
  24 #include "llvm/IR/Dominators.h"
  25 #include "llvm/IR/Instruction.h"
  26
  27 namespace llvm {
  28
  29 class Instruction;
  30 class DominatorTree;
  31 class Loop;
  32
  33 /// Captures loop safety information.
  34 /// It keep information for loop blocks may throw exception or otherwise
  35 /// exit abnormaly on any iteration of the loop which might actually execute
  36 /// at runtime.  The primary way to consume this infromation is via
  37 /// isGuaranteedToExecute below, but some callers bailout or fallback to
  38 /// alternate reasoning if a loop contains any implicit control flow.
  39 /// NOTE: LoopSafetyInfo contains cached information regarding loops and their
  40 /// particular blocks. This information is only dropped on invocation of
  41 /// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if
  42 /// any thrower instructions have been added or removed from them, or if the
  43 /// control flow has changed, or in case of other meaningful modifications, the
  44 /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
  45 /// loop were made and the info wasn't recomputed properly, the behavior of all
  46 /// methods except for computeLoopSafetyInfo is undefined.
  47 class LoopSafetyInfo {
  48   // Used to update funclet bundle operands.
  49   DenseMap<BasicBlock *, ColorVector> BlockColors;
  50
  51 protected:
  52   /// Computes block colors.
  53   void computeBlockColors(const Loop *CurLoop);
  54
  55 public:
  56   /// Returns block colors map that is used to update funclet operand bundles.
  57   const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const;
  58
  59   /// Copy colors of block \p Old into the block \p New.
  60   void copyColors(BasicBlock *New, BasicBlock *Old);
  61
  62   /// Returns true iff the block \p BB potentially may throw exception. It can
  63   /// be false-positive in cases when we want to avoid complex analysis.
  64   virtual bool blockMayThrow(const BasicBlock *BB) const = 0;
  65
  66   /// Returns true iff any block of the loop for which this info is contains an
  67   /// instruction that may throw or otherwise exit abnormally.
  68   virtual bool anyBlockMayThrow() const = 0;
  69
  70   /// Return true if we must reach the block \p BB under assumption that the
  71   /// loop \p CurLoop is entered.
  72   bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
  73                                const DominatorTree *DT) const;
  74
  75   /// Computes safety information for a loop checks loop body & header for
  76   /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
  77   /// as argument. Updates safety information in LoopSafetyInfo argument.
  78   /// Note: This is defined to clear and reinitialize an already initialized
  79   /// LoopSafetyInfo.  Some callers rely on this fact.
  80   virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0;
  81
  82   /// Returns true if the instruction in a loop is guaranteed to execute at
  83   /// least once (under the assumption that the loop is entered).
  84   virtual bool isGuaranteedToExecute(const Instruction &Inst,
  85                                      const DominatorTree *DT,
  86                                      const Loop *CurLoop) const = 0;
  87
  88   LoopSafetyInfo() = default;
  89
  90   virtual ~LoopSafetyInfo() = default;
  91 };
  92
  93
  94 /// Simple and conservative implementation of LoopSafetyInfo that can give
  95 /// false-positive answers to its queries in order to avoid complicated
  96 /// analysis.
  97 class SimpleLoopSafetyInfo: public LoopSafetyInfo {
  98   bool MayThrow = false;       // The current loop contains an instruction which
  99                                // may throw.
 100   bool HeaderMayThrow = false; // Same as previous, but specific to loop header
 101
 102 public:
 103   virtual bool blockMayThrow(const BasicBlock *BB) const;
 104
 105   virtual bool anyBlockMayThrow() const;
 106
 107   virtual void computeLoopSafetyInfo(const Loop *CurLoop);
 108
 109   virtual bool isGuaranteedToExecute(const Instruction &Inst,
 110                                      const DominatorTree *DT,
 111                                      const Loop *CurLoop) const;
 112
 113   SimpleLoopSafetyInfo() : LoopSafetyInfo() {};
 114
 115   virtual ~SimpleLoopSafetyInfo() {};
 116 };
 117
 118 /// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
 119 /// give precise answers on "may throw" queries. This implementation uses cache
 120 /// that should be invalidated by calling the methods insertInstructionTo and
 121 /// removeInstruction whenever we modify a basic block's contents by adding or
 122 /// removing instructions.
 123 class ICFLoopSafetyInfo: public LoopSafetyInfo {
 124   bool MayThrow = false;       // The current loop contains an instruction which
 125                                // may throw.
 126   // Contains information about implicit control flow in this loop's blocks.
 127   mutable ImplicitControlFlowTracking ICF;
 128   // Contains information about instruction that may possibly write memory.
 129   mutable MemoryWriteTracking MW;
 130
 131 public:
 132   virtual bool blockMayThrow(const BasicBlock *BB) const;
 133
 134   virtual bool anyBlockMayThrow() const;
 135
 136   virtual void computeLoopSafetyInfo(const Loop *CurLoop);
 137
 138   virtual bool isGuaranteedToExecute(const Instruction &Inst,
 139                                      const DominatorTree *DT,
 140                                      const Loop *CurLoop) const;
 141
 142   /// Returns true if we could not execute a memory-modifying instruction before
 143   /// we enter \p BB under assumption that \p CurLoop is entered.
 144   bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop)
 145       const;
 146
 147   /// Returns true if we could not execute a memory-modifying instruction before
 148   /// we execute \p I under assumption that \p CurLoop is entered.
 149   bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop)
 150       const;
 151
 152   /// Inform the safety info that we are planning to insert a new instruction
 153   /// \p Inst into the basic block \p BB. It will make all cache updates to keep
 154   /// it correct after this insertion.
 155   void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
 156
 157   /// Inform safety info that we are planning to remove the instruction \p Inst
 158   /// from its block. It will make all cache updates to keep it correct after
 159   /// this removal.
 160   void removeInstruction(const Instruction *Inst);
 161
 162   ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
 163
 164   virtual ~ICFLoopSafetyInfo() {};
 165 };
 166
 167 }
 168
 169 #endif