1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
| //===-- InstructionPrecedenceTracking.h -------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// Implements a class that is able to define some instructions as "special"
// (e.g. as having implicit control flow, or writing memory, or having another
// interesting property) and then efficiently answers queries of the types:
// 1. Are there any special instructions in the block of interest?
// 2. Return first of the special instructions in the given block;
// 3. Check if the given instruction is preceeded by the first special
// instruction in the same block.
// The class provides caching that allows to answer these queries quickly. The
// user must make sure that the cached data is invalidated properly whenever
// a content of some tracked block is changed.
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
#define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
#include "llvm/IR/Dominators.h"
#include "llvm/Analysis/OrderedInstructions.h"
namespace llvm {
class InstructionPrecedenceTracking {
// Maps a block to the topmost special instruction in it. If the value is
// nullptr, it means that it is known that this block does not contain any
// special instructions.
DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts;
// Allows to answer queries about precedence of instructions within one block.
OrderedInstructions OI;
// Fills information about the given block's special instructions.
void fill(const BasicBlock *BB);
#ifndef NDEBUG
/// Asserts that the cached info for \p BB is up-to-date. This helps to catch
/// the usage error of accessing a block without properly invalidating after a
/// previous transform.
void validate(const BasicBlock *BB) const;
/// Asserts whether or not the contents of this tracking is up-to-date. This
/// helps to catch the usage error of accessing a block without properly
/// invalidating after a previous transform.
void validateAll() const;
#endif
protected:
InstructionPrecedenceTracking(DominatorTree *DT)
: OI(OrderedInstructions(DT)) {}
/// Returns the topmost special instruction from the block \p BB. Returns
/// nullptr if there is no special instructions in the block.
const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);
/// Returns true iff at least one instruction from the basic block \p BB is
/// special.
bool hasSpecialInstructions(const BasicBlock *BB);
/// Returns true iff the first special instruction of \p Insn's block exists
/// and dominates \p Insn.
bool isPreceededBySpecialInstruction(const Instruction *Insn);
/// A predicate that defines whether or not the instruction \p Insn is
/// considered special and needs to be tracked. Implementing this method in
/// children classes allows to implement tracking of implicit control flow,
/// memory writing instructions or any other kinds of instructions we might
/// be interested in.
virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
virtual ~InstructionPrecedenceTracking() = default;
public:
/// Notifies this tracking that we are going to insert a new instruction \p
/// Inst to the basic block \p BB. It makes all necessary updates to internal
/// caches to keep them consistent.
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
/// Notifies this tracking that we are going to remove the instruction \p Inst
/// It makes all necessary updates to internal caches to keep them consistent.
void removeInstruction(const Instruction *Inst);
/// Invalidates all information from this tracking.
void clear();
};
/// This class allows to keep track on instructions with implicit control flow.
/// These are instructions that may not pass execution to their successors. For
/// example, throwing calls and guards do not always do this. If we need to know
/// for sure that some instruction is guaranteed to execute if the given block
/// is reached, then we need to make sure that there is no implicit control flow
/// instruction (ICFI) preceding it. For example, this check is required if we
/// perform PRE moving non-speculable instruction to other place.
class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {
public:
ImplicitControlFlowTracking(DominatorTree *DT)
: InstructionPrecedenceTracking(DT) {}
/// Returns the topmost instruction with implicit control flow from the given
/// basic block. Returns nullptr if there is no such instructions in the block.
const Instruction *getFirstICFI(const BasicBlock *BB) {
return getFirstSpecialInstruction(BB);
}
/// Returns true if at least one instruction from the given basic block has
/// implicit control flow.
bool hasICF(const BasicBlock *BB) {
return hasSpecialInstructions(BB);
}
/// Returns true if the first ICFI of Insn's block exists and dominates Insn.
bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {
return isPreceededBySpecialInstruction(Insn);
}
virtual bool isSpecialInstruction(const Instruction *Insn) const;
};
class MemoryWriteTracking : public InstructionPrecedenceTracking {
public:
MemoryWriteTracking(DominatorTree *DT) : InstructionPrecedenceTracking(DT) {}
/// Returns the topmost instruction that may write memory from the given
/// basic block. Returns nullptr if there is no such instructions in the block.
const Instruction *getFirstMemoryWrite(const BasicBlock *BB) {
return getFirstSpecialInstruction(BB);
}
/// Returns true if at least one instruction from the given basic block may
/// write memory.
bool mayWriteToMemory(const BasicBlock *BB) {
return hasSpecialInstructions(BB);
}
/// Returns true if the first memory writing instruction of Insn's block
/// exists and dominates Insn.
bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn) {
return isPreceededBySpecialInstruction(Insn);
}
virtual bool isSpecialInstruction(const Instruction *Insn) const;
};
} // llvm
#endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
|