Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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/ADT/DenseMap.h"
  24.  
  25. namespace llvm {
  26.  
  27. class BasicBlock;
  28. class Instruction;
  29.  
  30. class InstructionPrecedenceTracking {
  31.   // Maps a block to the topmost special instruction in it. If the value is
  32.   // nullptr, it means that it is known that this block does not contain any
  33.   // special instructions.
  34.   DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts;
  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.   /// Returns the topmost special instruction from the block \p BB. Returns
  53.   /// nullptr if there is no special instructions in the block.
  54.   const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);
  55.  
  56.   /// Returns true iff at least one instruction from the basic block \p BB is
  57.   /// special.
  58.   bool hasSpecialInstructions(const BasicBlock *BB);
  59.  
  60.   /// Returns true iff the first special instruction of \p Insn's block exists
  61.   /// and dominates \p Insn.
  62.   bool isPreceededBySpecialInstruction(const Instruction *Insn);
  63.  
  64.   /// A predicate that defines whether or not the instruction \p Insn is
  65.   /// considered special and needs to be tracked. Implementing this method in
  66.   /// children classes allows to implement tracking of implicit control flow,
  67.   /// memory writing instructions or any other kinds of instructions we might
  68.   /// be interested in.
  69.   virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
  70.  
  71.   virtual ~InstructionPrecedenceTracking() = default;
  72.  
  73. public:
  74.   /// Notifies this tracking that we are going to insert a new instruction \p
  75.   /// Inst to the basic block \p BB. It makes all necessary updates to internal
  76.   /// caches to keep them consistent.
  77.   void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
  78.  
  79.   /// Notifies this tracking that we are going to remove the instruction \p Inst
  80.   /// It makes all necessary updates to internal caches to keep them consistent.
  81.   void removeInstruction(const Instruction *Inst);
  82.  
  83.   /// Notifies this tracking that we are going to replace all uses of \p Inst.
  84.   /// It makes all necessary updates to internal caches to keep them consistent.
  85.   /// Should typically be called before a RAUW.
  86.   void removeUsersOf(const Instruction *Inst);
  87.  
  88.   /// Invalidates all information from this tracking.
  89.   void clear();
  90. };
  91.  
  92. /// This class allows to keep track on instructions with implicit control flow.
  93. /// These are instructions that may not pass execution to their successors. For
  94. /// example, throwing calls and guards do not always do this. If we need to know
  95. /// for sure that some instruction is guaranteed to execute if the given block
  96. /// is reached, then we need to make sure that there is no implicit control flow
  97. /// instruction (ICFI) preceding it. For example, this check is required if we
  98. /// perform PRE moving non-speculable instruction to other place.
  99. class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {
  100. public:
  101.   /// Returns the topmost instruction with implicit control flow from the given
  102.   /// basic block. Returns nullptr if there is no such instructions in the block.
  103.   const Instruction *getFirstICFI(const BasicBlock *BB) {
  104.     return getFirstSpecialInstruction(BB);
  105.   }
  106.  
  107.   /// Returns true if at least one instruction from the given basic block has
  108.   /// implicit control flow.
  109.   bool hasICF(const BasicBlock *BB) {
  110.     return hasSpecialInstructions(BB);
  111.   }
  112.  
  113.   /// Returns true if the first ICFI of Insn's block exists and dominates Insn.
  114.   bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {
  115.     return isPreceededBySpecialInstruction(Insn);
  116.   }
  117.  
  118.   bool isSpecialInstruction(const Instruction *Insn) const override;
  119. };
  120.  
  121. class MemoryWriteTracking : public InstructionPrecedenceTracking {
  122. public:
  123.   /// Returns the topmost instruction that may write memory from the given
  124.   /// basic block. Returns nullptr if there is no such instructions in the block.
  125.   const Instruction *getFirstMemoryWrite(const BasicBlock *BB) {
  126.     return getFirstSpecialInstruction(BB);
  127.   }
  128.  
  129.   /// Returns true if at least one instruction from the given basic block may
  130.   /// write memory.
  131.   bool mayWriteToMemory(const BasicBlock *BB) {
  132.     return hasSpecialInstructions(BB);
  133.   }
  134.  
  135.   /// Returns true if the first memory writing instruction of Insn's block
  136.   /// exists and dominates Insn.
  137.   bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn) {
  138.     return isPreceededBySpecialInstruction(Insn);
  139.   }
  140.  
  141.   bool isSpecialInstruction(const Instruction *Insn) const override;
  142. };
  143.  
  144. } // llvm
  145.  
  146. #endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
  147.