1 //===-- InstructionPrecedenceTracking.h -------------------------*- C++ -*-===//
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
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 //===----------------------------------------------------------------------===//
20 #ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
21 #define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
23 #include "llvm/ADT/DenseMap.h"
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;
36 // Fills information about the given block's special instructions.
37 void fill(const BasicBlock *BB);
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;
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;
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);
56 /// Returns true iff at least one instruction from the basic block \p BB is
58 bool hasSpecialInstructions(const BasicBlock *BB);
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);
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
69 virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
71 virtual ~InstructionPrecedenceTracking() = default;
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);
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);
83 /// Invalidates all information from this tracking.
87 /// This class allows to keep track on instructions with implicit control flow.
88 /// These are instructions that may not pass execution to their successors. For
89 /// example, throwing calls and guards do not always do this. If we need to know
90 /// for sure that some instruction is guaranteed to execute if the given block
91 /// is reached, then we need to make sure that there is no implicit control flow
92 /// instruction (ICFI) preceding it. For example, this check is required if we
93 /// perform PRE moving non-speculable instruction to other place.
94 class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {
96 /// Returns the topmost instruction with implicit control flow from the given
97 /// basic block. Returns nullptr if there is no such instructions in the block.
98 const Instruction *getFirstICFI(const BasicBlock *BB) {
99 return getFirstSpecialInstruction(BB);
102 /// Returns true if at least one instruction from the given basic block has
103 /// implicit control flow.
104 bool hasICF(const BasicBlock *BB) {
105 return hasSpecialInstructions(BB);
108 /// Returns true if the first ICFI of Insn's block exists and dominates Insn.
109 bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {
110 return isPreceededBySpecialInstruction(Insn);
113 bool isSpecialInstruction(const Instruction *Insn) const override;
116 class MemoryWriteTracking : public InstructionPrecedenceTracking {
118 /// Returns the topmost instruction that may write memory from the given
119 /// basic block. Returns nullptr if there is no such instructions in the block.
120 const Instruction *getFirstMemoryWrite(const BasicBlock *BB) {
121 return getFirstSpecialInstruction(BB);
124 /// Returns true if at least one instruction from the given basic block may
126 bool mayWriteToMemory(const BasicBlock *BB) {
127 return hasSpecialInstructions(BB);
130 /// Returns true if the first memory writing instruction of Insn's block
131 /// exists and dominates Insn.
132 bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn) {
133 return isPreceededBySpecialInstruction(Insn);
136 bool isSpecialInstruction(const Instruction *Insn) const override;
141 #endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H