LLVM  10.0.0svn
InstructionPrecedenceTracking.h
Go to the documentation of this file.
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"
25 
26 namespace llvm {
27 
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.
33  // Allows to answer queries about precedence of instructions within one block.
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:
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.
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.
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.
98 public:
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.
116  return isPreceededBySpecialInstruction(Insn);
117  }
118 
119  virtual bool isSpecialInstruction(const Instruction *Insn) const;
120 };
121 
123 public:
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.
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.
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void clear()
Invalidates all information from this tracking.
bool hasSpecialInstructions(const BasicBlock *BB)
Returns true iff at least one instruction from the basic block BB is special.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
const Instruction * getFirstICFI(const BasicBlock *BB)
Returns the topmost instruction with implicit control flow from the given basic block.
bool hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow...
bool isDominatedByICFIFromSameBlock(const Instruction *Insn)
Returns true if the first ICFI of Insn's block exists and dominates Insn.
const Instruction * getFirstSpecialInstruction(const BasicBlock *BB)
Returns the topmost special instruction from the block BB.
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Notifies this tracking that we are going to insert a new instruction Inst to the basic block BB...
void removeInstruction(const Instruction *Inst)
Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...
bool isPreceededBySpecialInstruction(const Instruction *Insn)
Returns true iff the first special instruction of Insn's block exists and dominates Insn...
This class allows to keep track on instructions with implicit control flow.
virtual bool isSpecialInstruction(const Instruction *Insn) const =0
A predicate that defines whether or not the instruction Insn is considered special and needs to be tr...
bool mayWriteToMemory(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block may write memory.
virtual ~InstructionPrecedenceTracking()=default
const Instruction * getFirstMemoryWrite(const BasicBlock *BB)
Returns the topmost instruction that may write memory from the given basic block. ...
bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn)
Returns true if the first memory writing instruction of Insn's block exists and dominates Insn...