include/llvm/Analysis/InstructionPrecedenceTracking.h

   1 //===-- InstructionPrecedenceTracking.h -------------------------*- 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 // Implements a class that is able to define some instructions as "special"
   9 // (e.g. as having implicit control flow, or writing memory, or having another
  10 // interesting property) and then efficiently answers queries of the types:
  11 // 1. Are there any special instructions in the block of interest?
  12 // 2. Return first of the special instructions in the given block;
  13 // 3. Check if the given instruction is preceeded by the first special
  14 //    instruction in the same block.
  15 // The class provides caching that allows to answer these queries quickly. The
  16 // user must make sure that the cached data is invalidated properly whenever
  17 // a content of some tracked block is changed.
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
  21 #define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
  22
  23 #include "llvm/IR/Dominators.h"
  24 #include "llvm/Analysis/OrderedInstructions.h"
  25
  26 namespace llvm {
  27
  28 class InstructionPrecedenceTracking {
  29   // Maps a block to the topmost special instruction in it. If the value is
  30   // nullptr, it means that it is known that this block does not contain any
  31   // special instructions.
  32   DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts;
  33   // Allows to answer queries about precedence of instructions within one block.
  34   OrderedInstructions OI;
  35
  36   // Fills information about the given block's special instructions.
  37   void fill(const BasicBlock *BB);
  38
  39 #ifndef NDEBUG
  40   /// Asserts that the cached info for \p BB is up-to-date. This helps to catch
  41   /// the usage error of accessing a block without properly invalidating after a
  42   /// previous transform.
  43   void validate(const BasicBlock *BB) const;
  44
  45   /// Asserts whether or not the contents of this tracking is up-to-date. This
  46   /// helps to catch the usage error of accessing a block without properly
  47   /// invalidating after a previous transform.
  48   void validateAll() const;
  49 #endif
  50
  51 protected:
  52   InstructionPrecedenceTracking(DominatorTree *DT)
  53       : OI(OrderedInstructions(DT)) {}
  54
  55   /// Returns the topmost special instruction from the block \p BB. Returns
  56   /// nullptr if there is no special instructions in the block.
  57   const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);
  58
  59   /// Returns true iff at least one instruction from the basic block \p BB is
  60   /// special.
  61   bool hasSpecialInstructions(const BasicBlock *BB);
  62
  63   /// Returns true iff the first special instruction of \p Insn's block exists
  64   /// and dominates \p Insn.
  65   bool isPreceededBySpecialInstruction(const Instruction *Insn);
  66
  67   /// A predicate that defines whether or not the instruction \p Insn is
  68   /// considered special and needs to be tracked. Implementing this method in
  69   /// children classes allows to implement tracking of implicit control flow,
  70   /// memory writing instructions or any other kinds of instructions we might
  71   /// be interested in.
  72   virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
  73
  74   virtual ~InstructionPrecedenceTracking() = default;
  75
  76 public:
  77   /// Notifies this tracking that we are going to insert a new instruction \p
  78   /// Inst to the basic block \p BB. It makes all necessary updates to internal
  79   /// caches to keep them consistent.
  80   void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
  81
  82   /// Notifies this tracking that we are going to remove the instruction \p Inst
  83   /// It makes all necessary updates to internal caches to keep them consistent.
  84   void removeInstruction(const Instruction *Inst);
  85
  86   /// Invalidates all information from this tracking.
  87   void clear();
  88 };
  89
  90 /// This class allows to keep track on instructions with implicit control flow.
  91 /// These are instructions that may not pass execution to their successors. For
  92 /// example, throwing calls and guards do not always do this. If we need to know
  93 /// for sure that some instruction is guaranteed to execute if the given block
  94 /// is reached, then we need to make sure that there is no implicit control flow
  95 /// instruction (ICFI) preceding it. For example, this check is required if we
  96 /// perform PRE moving non-speculable instruction to other place.
  97 class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {
  98 public:
  99   ImplicitControlFlowTracking(DominatorTree *DT)
 100       : InstructionPrecedenceTracking(DT) {}
 101
 102   /// Returns the topmost instruction with implicit control flow from the given
 103   /// basic block. Returns nullptr if there is no such instructions in the block.
 104   const Instruction *getFirstICFI(const BasicBlock *BB) {
 105     return getFirstSpecialInstruction(BB);
 106   }
 107
 108   /// Returns true if at least one instruction from the given basic block has
 109   /// implicit control flow.
 110   bool hasICF(const BasicBlock *BB) {
 111     return hasSpecialInstructions(BB);
 112   }
 113
 114   /// Returns true if the first ICFI of Insn's block exists and dominates Insn.
 115   bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {
 116     return isPreceededBySpecialInstruction(Insn);
 117   }
 118
 119   virtual bool isSpecialInstruction(const Instruction *Insn) const;
 120 };
 121
 122 class MemoryWriteTracking : public InstructionPrecedenceTracking {
 123 public:
 124   MemoryWriteTracking(DominatorTree *DT) : InstructionPrecedenceTracking(DT) {}
 125
 126   /// Returns the topmost instruction that may write memory from the given
 127   /// basic block. Returns nullptr if there is no such instructions in the block.
 128   const Instruction *getFirstMemoryWrite(const BasicBlock *BB) {
 129     return getFirstSpecialInstruction(BB);
 130   }
 131
 132   /// Returns true if at least one instruction from the given basic block may
 133   /// write memory.
 134   bool mayWriteToMemory(const BasicBlock *BB) {
 135     return hasSpecialInstructions(BB);
 136   }
 137
 138   /// Returns true if the first memory writing instruction of Insn's block
 139   /// exists and dominates Insn.
 140   bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn) {
 141     return isPreceededBySpecialInstruction(Insn);
 142   }
 143
 144   virtual bool isSpecialInstruction(const Instruction *Insn) const;
 145 };
 146
 147 } // llvm
 148
 149 #endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H