Line data    Source code

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