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 | |