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 /// There are two interfaces available to determine if an instruction is
  15 /// executed once a given point in the control flow is reached:
  16 /// 1) A loop-centric one derived from LoopSafetyInfo.
  17 /// 2) A "must be executed context"-based one implemented in the
  18 ///    MustBeExecutedContextExplorer.
  19 /// Please refer to the class comments for more information.
  20 ///
  21 //===----------------------------------------------------------------------===//
  22
  23 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
  24 #define LLVM_ANALYSIS_MUSTEXECUTE_H
  25
  26 #include "llvm/ADT/DenseMap.h"
  27 #include "llvm/Analysis/EHPersonalities.h"
  28 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
  29 #include "llvm/Analysis/LoopInfo.h"
  30 #include "llvm/IR/BasicBlock.h"
  31 #include "llvm/IR/Dominators.h"
  32 #include "llvm/IR/Instruction.h"
  33
  34 namespace llvm {
  35
  36 class Instruction;
  37 class DominatorTree;
  38 class Loop;
  39
  40 /// Captures loop safety information.
  41 /// It keep information for loop blocks may throw exception or otherwise
  42 /// exit abnormaly on any iteration of the loop which might actually execute
  43 /// at runtime.  The primary way to consume this infromation is via
  44 /// isGuaranteedToExecute below, but some callers bailout or fallback to
  45 /// alternate reasoning if a loop contains any implicit control flow.
  46 /// NOTE: LoopSafetyInfo contains cached information regarding loops and their
  47 /// particular blocks. This information is only dropped on invocation of
  48 /// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if
  49 /// any thrower instructions have been added or removed from them, or if the
  50 /// control flow has changed, or in case of other meaningful modifications, the
  51 /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
  52 /// loop were made and the info wasn't recomputed properly, the behavior of all
  53 /// methods except for computeLoopSafetyInfo is undefined.
  54 class LoopSafetyInfo {
  55   // Used to update funclet bundle operands.
  56   DenseMap<BasicBlock *, ColorVector> BlockColors;
  57
  58 protected:
  59   /// Computes block colors.
  60   void computeBlockColors(const Loop *CurLoop);
  61
  62 public:
  63   /// Returns block colors map that is used to update funclet operand bundles.
  64   const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const;
  65
  66   /// Copy colors of block \p Old into the block \p New.
  67   void copyColors(BasicBlock *New, BasicBlock *Old);
  68
  69   /// Returns true iff the block \p BB potentially may throw exception. It can
  70   /// be false-positive in cases when we want to avoid complex analysis.
  71   virtual bool blockMayThrow(const BasicBlock *BB) const = 0;
  72
  73   /// Returns true iff any block of the loop for which this info is contains an
  74   /// instruction that may throw or otherwise exit abnormally.
  75   virtual bool anyBlockMayThrow() const = 0;
  76
  77   /// Return true if we must reach the block \p BB under assumption that the
  78   /// loop \p CurLoop is entered.
  79   bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
  80                                const DominatorTree *DT) const;
  81
  82   /// Computes safety information for a loop checks loop body & header for
  83   /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
  84   /// as argument. Updates safety information in LoopSafetyInfo argument.
  85   /// Note: This is defined to clear and reinitialize an already initialized
  86   /// LoopSafetyInfo.  Some callers rely on this fact.
  87   virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0;
  88
  89   /// Returns true if the instruction in a loop is guaranteed to execute at
  90   /// least once (under the assumption that the loop is entered).
  91   virtual bool isGuaranteedToExecute(const Instruction &Inst,
  92                                      const DominatorTree *DT,
  93                                      const Loop *CurLoop) const = 0;
  94
  95   LoopSafetyInfo() = default;
  96
  97   virtual ~LoopSafetyInfo() = default;
  98 };
  99
 100
 101 /// Simple and conservative implementation of LoopSafetyInfo that can give
 102 /// false-positive answers to its queries in order to avoid complicated
 103 /// analysis.
 104 class SimpleLoopSafetyInfo: public LoopSafetyInfo {
 105   bool MayThrow = false;       // The current loop contains an instruction which
 106                                // may throw.
 107   bool HeaderMayThrow = false; // Same as previous, but specific to loop header
 108
 109 public:
 110   virtual bool blockMayThrow(const BasicBlock *BB) const;
 111
 112   virtual bool anyBlockMayThrow() const;
 113
 114   virtual void computeLoopSafetyInfo(const Loop *CurLoop);
 115
 116   virtual bool isGuaranteedToExecute(const Instruction &Inst,
 117                                      const DominatorTree *DT,
 118                                      const Loop *CurLoop) const;
 119
 120   SimpleLoopSafetyInfo() : LoopSafetyInfo() {};
 121
 122   virtual ~SimpleLoopSafetyInfo() {};
 123 };
 124
 125 /// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
 126 /// give precise answers on "may throw" queries. This implementation uses cache
 127 /// that should be invalidated by calling the methods insertInstructionTo and
 128 /// removeInstruction whenever we modify a basic block's contents by adding or
 129 /// removing instructions.
 130 class ICFLoopSafetyInfo: public LoopSafetyInfo {
 131   bool MayThrow = false;       // The current loop contains an instruction which
 132                                // may throw.
 133   // Contains information about implicit control flow in this loop's blocks.
 134   mutable ImplicitControlFlowTracking ICF;
 135   // Contains information about instruction that may possibly write memory.
 136   mutable MemoryWriteTracking MW;
 137
 138 public:
 139   virtual bool blockMayThrow(const BasicBlock *BB) const;
 140
 141   virtual bool anyBlockMayThrow() const;
 142
 143   virtual void computeLoopSafetyInfo(const Loop *CurLoop);
 144
 145   virtual bool isGuaranteedToExecute(const Instruction &Inst,
 146                                      const DominatorTree *DT,
 147                                      const Loop *CurLoop) const;
 148
 149   /// Returns true if we could not execute a memory-modifying instruction before
 150   /// we enter \p BB under assumption that \p CurLoop is entered.
 151   bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop)
 152       const;
 153
 154   /// Returns true if we could not execute a memory-modifying instruction before
 155   /// we execute \p I under assumption that \p CurLoop is entered.
 156   bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop)
 157       const;
 158
 159   /// Inform the safety info that we are planning to insert a new instruction
 160   /// \p Inst into the basic block \p BB. It will make all cache updates to keep
 161   /// it correct after this insertion.
 162   void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
 163
 164   /// Inform safety info that we are planning to remove the instruction \p Inst
 165   /// from its block. It will make all cache updates to keep it correct after
 166   /// this removal.
 167   void removeInstruction(const Instruction *Inst);
 168
 169   ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
 170
 171   virtual ~ICFLoopSafetyInfo() {};
 172 };
 173
 174 struct MustBeExecutedContextExplorer;
 175
 176 /// Must be executed iterators visit stretches of instructions that are
 177 /// guaranteed to be executed together, potentially with other instruction
 178 /// executed in-between.
 179 ///
 180 /// Given the following code, and assuming all statements are single
 181 /// instructions which transfer execution to the successor (see
 182 /// isGuaranteedToTransferExecutionToSuccessor), there are two possible
 183 /// outcomes. If we start the iterator at A, B, or E, we will visit only A, B,
 184 /// and E. If we start at C or D, we will visit all instructions A-E.
 185 ///
 186 /// \code
 187 ///   A;
 188 ///   B;
 189 ///   if (...) {
 190 ///     C;
 191 ///     D;
 192 ///   }
 193 ///   E;
 194 /// \endcode
 195 ///
 196 ///
 197 /// Below is the example extneded with instructions F and G. Now we assume F
 198 /// might not transfer execution to it's successor G. As a result we get the
 199 /// following visit sets:
 200 ///
 201 /// Start Instruction   | Visit Set
 202 /// A                   | A, B,       E, F
 203 ///    B                | A, B,       E, F
 204 ///       C             | A, B, C, D, E, F
 205 ///          D          | A, B, C, D, E, F
 206 ///             E       | A, B,       E, F
 207 ///                F    | A, B,       E, F
 208 ///                   G | A, B,       E, F, G
 209 ///
 210 ///
 211 /// \code
 212 ///   A;
 213 ///   B;
 214 ///   if (...) {
 215 ///     C;
 216 ///     D;
 217 ///   }
 218 ///   E;
 219 ///   F;  // Might not transfer execution to its successor G.
 220 ///   G;
 221 /// \endcode
 222 ///
 223 ///
 224 /// A more complex example involving conditionals, loops, break, and continue
 225 /// is shown below. We again assume all instructions will transmit control to
 226 /// the successor and we assume we can prove the inner loop to be finite. We
 227 /// omit non-trivial branch conditions as the exploration is oblivious to them.
 228 /// Constant branches are assumed to be unconditional in the CFG. The resulting
 229 /// visist sets are shown in the table below.
 230 ///
 231 /// \code
 232 ///   A;
 233 ///   while (true) {
 234 ///     B;
 235 ///     if (...)
 236 ///       C;
 237 ///     if (...)
 238 ///       continue;
 239 ///     D;
 240 ///     if (...)
 241 ///       break;
 242 ///     do {
 243 ///       if (...)
 244 ///         continue;
 245 ///       E;
 246 ///     } while (...);
 247 ///     F;
 248 ///   }
 249 ///   G;
 250 /// \endcode
 251 ///
 252 /// Start Instruction    | Visit Set
 253 /// A                    | A, B
 254 ///    B                 | A, B
 255 ///       C              | A, B, C
 256 ///          D           | A, B,    D
 257 ///             E        | A, B,    D, E, F
 258 ///                F     | A, B,    D,    F
 259 ///                   G  | A, B,    D,       G
 260 ///
 261 ///
 262 /// Note that the examples show optimal visist sets but not necessarily the ones
 263 /// derived by the explorer depending on the available CFG analyses (see
 264 /// MustBeExecutedContextExplorer). Also note that we, depending on the options,
 265 /// the visit set can contain instructions from other functions.
 266 struct MustBeExecutedIterator {
 267   /// Type declarations that make his class an input iterator.
 268   ///{
 269   typedef const Instruction *value_type;
 270   typedef std::ptrdiff_t difference_type;
 271   typedef const Instruction **pointer;
 272   typedef const Instruction *&reference;
 273   typedef std::input_iterator_tag iterator_category;
 274   ///}
 275
 276   using ExplorerTy = MustBeExecutedContextExplorer;
 277
 278   MustBeExecutedIterator(const MustBeExecutedIterator &Other)
 279       : Visited(Other.Visited), Explorer(Other.Explorer),
 280         CurInst(Other.CurInst) {}
 281
 282   MustBeExecutedIterator(MustBeExecutedIterator &&Other)
 283       : Visited(std::move(Other.Visited)), Explorer(Other.Explorer),
 284         CurInst(Other.CurInst) {}
 285
 286   MustBeExecutedIterator &operator=(MustBeExecutedIterator &&Other) {
 287     if (this != &Other) {
 288       std::swap(Visited, Other.Visited);
 289       std::swap(CurInst, Other.CurInst);
 290     }
 291     return *this;
 292   }
 293
 294   ~MustBeExecutedIterator() {}
 295
 296   /// Pre- and post-increment operators.
 297   ///{
 298   MustBeExecutedIterator &operator++() {
 299     CurInst = advance();
 300     return *this;
 301   }
 302
 303   MustBeExecutedIterator operator++(int) {
 304     MustBeExecutedIterator tmp(*this);
 305     operator++();
 306     return tmp;
 307   }
 308   ///}
 309
 310   /// Equality and inequality operators. Note that we ignore the history here.
 311   ///{
 312   bool operator==(const MustBeExecutedIterator &Other) const {
 313     return CurInst == Other.CurInst;
 314   }
 315
 316   bool operator!=(const MustBeExecutedIterator &Other) const {
 317     return !(*this == Other);
 318   }
 319   ///}
 320
 321   /// Return the underlying instruction.
 322   const Instruction *&operator*() { return CurInst; }
 323   const Instruction *getCurrentInst() const { return CurInst; }
 324
 325   /// Return true if \p I was encountered by this iterator already.
 326   bool count(const Instruction *I) const { return Visited.count(I); }
 327
 328 private:
 329   using VisitedSetTy = DenseSet<const Instruction *>;
 330
 331   /// Private constructors.
 332   MustBeExecutedIterator(ExplorerTy &Explorer, const Instruction *I);
 333
 334   /// Reset the iterator to its initial state pointing at \p I.
 335   void reset(const Instruction *I);
 336
 337   /// Try to advance one of the underlying positions (Head or Tail).
 338   ///
 339   /// \return The next instruction in the must be executed context, or nullptr
 340   ///         if none was found.
 341   const Instruction *advance();
 342
 343   /// A set to track the visited instructions in order to deal with endless
 344   /// loops and recursion.
 345   VisitedSetTy Visited;
 346
 347   /// A reference to the explorer that created this iterator.
 348   ExplorerTy &Explorer;
 349
 350   /// The instruction we are currently exposing to the user. There is always an
 351   /// instruction that we know is executed with the given program point,
 352   /// initially the program point itself.
 353   const Instruction *CurInst;
 354
 355   friend struct MustBeExecutedContextExplorer;
 356 };
 357
 358 /// A "must be executed context" for a given program point PP is the set of
 359 /// instructions, potentially before and after PP, that are executed always when
 360 /// PP is reached. The MustBeExecutedContextExplorer an interface to explore
 361 /// "must be executed contexts" in a module through the use of
 362 /// MustBeExecutedIterator.
 363 ///
 364 /// The explorer exposes "must be executed iterators" that traverse the must be
 365 /// executed context. There is little information sharing between iterators as
 366 /// the expected use case involves few iterators for "far apart" instructions.
 367 /// If that changes, we should consider caching more intermediate results.
 368 struct MustBeExecutedContextExplorer {
 369
 370   /// In the description of the parameters we use PP to denote a program point
 371   /// for which the must be executed context is explored, or put differently,
 372   /// for which the MustBeExecutedIterator is created.
 373   ///
 374   /// \param ExploreInterBlock    Flag to indicate if instructions in blocks
 375   ///                             other than the parent of PP should be
 376   ///                             explored.
 377   MustBeExecutedContextExplorer(bool ExploreInterBlock)
 378       : ExploreInterBlock(ExploreInterBlock), EndIterator(*this, nullptr) {}
 379
 380   /// Clean up the dynamically allocated iterators.
 381   ~MustBeExecutedContextExplorer() {
 382     DeleteContainerSeconds(InstructionIteratorMap);
 383   }
 384
 385   /// Iterator-based interface. \see MustBeExecutedIterator.
 386   ///{
 387   using iterator = MustBeExecutedIterator;
 388   using const_iterator = const MustBeExecutedIterator;
 389
 390   /// Return an iterator to explore the context around \p PP.
 391   iterator &begin(const Instruction *PP) {
 392     auto *&It = InstructionIteratorMap[PP];
 393     if (!It)
 394       It = new iterator(*this, PP);
 395     return *It;
 396   }
 397
 398   /// Return an iterator to explore the cached context around \p PP.
 399   const_iterator &begin(const Instruction *PP) const {
 400     return *InstructionIteratorMap.lookup(PP);
 401   }
 402
 403   /// Return an universal end iterator.
 404   ///{
 405   iterator &end() { return EndIterator; }
 406   iterator &end(const Instruction *) { return EndIterator; }
 407
 408   const_iterator &end() const { return EndIterator; }
 409   const_iterator &end(const Instruction *) const { return EndIterator; }
 410   ///}
 411
 412   /// Return an iterator range to explore the context around \p PP.
 413   llvm::iterator_range<iterator> range(const Instruction *PP) {
 414     return llvm::make_range(begin(PP), end(PP));
 415   }
 416
 417   /// Return an iterator range to explore the cached context around \p PP.
 418   llvm::iterator_range<const_iterator> range(const Instruction *PP) const {
 419     return llvm::make_range(begin(PP), end(PP));
 420   }
 421   ///}
 422
 423   /// Return the next instruction that is guaranteed to be executed after \p PP.
 424   ///
 425   /// \param It              The iterator that is used to traverse the must be
 426   ///                        executed context.
 427   /// \param PP              The program point for which the next instruction
 428   ///                        that is guaranteed to execute is determined.
 429   const Instruction *
 430   getMustBeExecutedNextInstruction(MustBeExecutedIterator &It,
 431                                    const Instruction *PP);
 432
 433   /// Parameter that limit the performed exploration. See the constructor for
 434   /// their meaning.
 435   ///{
 436   const bool ExploreInterBlock;
 437   ///}
 438
 439 private:
 440   /// Map from instructions to associated must be executed iterators.
 441   DenseMap<const Instruction *, MustBeExecutedIterator *>
 442       InstructionIteratorMap;
 443
 444   /// A unique end iterator.
 445   MustBeExecutedIterator EndIterator;
 446 };
 447
 448 } // namespace llvm
 449
 450 #endif