LLVM 19.0.0git
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/ADT/DenseMap.h"
24
25namespace llvm {
26
27class BasicBlock;
28class Instruction;
29
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.
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
51protected:
52 /// Returns the topmost special instruction from the block \p BB. Returns
53 /// nullptr if there is no special instructions in the block.
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.
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
73public:
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.
100public:
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.
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.
116 }
117
118 bool isSpecialInstruction(const Instruction *Insn) const override;
119};
120
122public:
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.
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.
139 }
140
141 bool isSpecialInstruction(const Instruction *Insn) const override;
142};
143
144} // llvm
145
146#endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
This file defines the DenseMap class.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
This class allows to keep track on instructions with implicit control flow.
const Instruction * getFirstICFI(const BasicBlock *BB)
Returns the topmost instruction with implicit control flow from the given basic block.
bool isDominatedByICFIFromSameBlock(const Instruction *Insn)
Returns true if the first ICFI of Insn's block exists and dominates Insn.
bool hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow.
bool isSpecialInstruction(const Instruction *Insn) const override
A predicate that defines whether or not the instruction Insn is considered special and needs to be tr...
void clear()
Invalidates all information from this tracking.
void removeUsersOf(const Instruction *Inst)
Notifies this tracking that we are going to replace all uses of Inst.
virtual ~InstructionPrecedenceTracking()=default
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...
const Instruction * getFirstSpecialInstruction(const BasicBlock *BB)
Returns the topmost special instruction from the block BB.
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 hasSpecialInstructions(const BasicBlock *BB)
Returns true iff at least one instruction from the basic block BB is special.
bool isPreceededBySpecialInstruction(const Instruction *Insn)
Returns true iff the first special instruction of Insn's block exists and dominates Insn.
bool mayWriteToMemory(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block may write memory.
bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn)
Returns true if the first memory writing instruction of Insn's block exists and dominates Insn.
bool isSpecialInstruction(const Instruction *Insn) const override
A predicate that defines whether or not the instruction Insn is considered special and needs to be tr...
const Instruction * getFirstMemoryWrite(const BasicBlock *BB)
Returns the topmost instruction that may write memory from the given basic block.
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18