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
150
151
152
153
154
155
156
157
158
159
160
| //===-- InstructionPrecedenceTracking.cpp -----------------------*- 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.
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/InstructionPrecedenceTracking.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/PatternMatch.h"
using namespace llvm;
#ifndef NDEBUG
static cl::opt<bool> ExpensiveAsserts(
"ipt-expensive-asserts",
cl::desc("Perform expensive assert validation on every query to Instruction"
" Precedence Tracking"),
cl::init(false), cl::Hidden);
#endif
const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
const BasicBlock *BB) {
#ifndef NDEBUG
// If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
// catch this situation as early as possible.
if (ExpensiveAsserts)
validateAll();
else
validate(BB);
#endif
if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
fill(BB);
assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
}
return FirstSpecialInsts[BB];
}
bool InstructionPrecedenceTracking::hasSpecialInstructions(
const BasicBlock *BB) {
return getFirstSpecialInstruction(BB) != nullptr;
}
bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
const Instruction *Insn) {
const Instruction *MaybeFirstSpecial =
getFirstSpecialInstruction(Insn->getParent());
return MaybeFirstSpecial && OI.dominates(MaybeFirstSpecial, Insn);
}
void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
FirstSpecialInsts.erase(BB);
for (auto &I : *BB)
if (isSpecialInstruction(&I)) {
FirstSpecialInsts[BB] = &I;
return;
}
// Mark this block as having no special instructions.
FirstSpecialInsts[BB] = nullptr;
}
#ifndef NDEBUG
void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
auto It = FirstSpecialInsts.find(BB);
// Bail if we don't have anything cached for this block.
if (It == FirstSpecialInsts.end())
return;
for (const Instruction &Insn : *BB)
if (isSpecialInstruction(&Insn)) {
assert(It->second == &Insn &&
"Cached first special instruction is wrong!");
return;
}
assert(It->second == nullptr &&
"Block is marked as having special instructions but in fact it has "
"none!");
}
void InstructionPrecedenceTracking::validateAll() const {
// Check that for every known block the cached value is correct.
for (auto &It : FirstSpecialInsts)
validate(It.first);
}
#endif
void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
const BasicBlock *BB) {
if (isSpecialInstruction(Inst))
FirstSpecialInsts.erase(BB);
OI.invalidateBlock(BB);
}
void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
if (isSpecialInstruction(Inst))
FirstSpecialInsts.erase(Inst->getParent());
OI.invalidateBlock(Inst->getParent());
}
void InstructionPrecedenceTracking::clear() {
for (auto It : FirstSpecialInsts)
OI.invalidateBlock(It.first);
FirstSpecialInsts.clear();
#ifndef NDEBUG
// The map should be valid after clearing (at least empty).
validateAll();
#endif
}
bool ImplicitControlFlowTracking::isSpecialInstruction(
const Instruction *Insn) const {
// If a block's instruction doesn't always pass the control to its successor
// instruction, mark the block as having implicit control flow. We use them
// to avoid wrong assumptions of sort "if A is executed and B post-dominates
// A, then B is also executed". This is not true is there is an implicit
// control flow instruction (e.g. a guard) between them.
//
// TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
// for volatile stores and loads because they can trap. The discussion on
// whether or not it is correct is still ongoing. We might want to get rid
// of this logic in the future. Anyways, trapping instructions shouldn't
// introduce implicit control flow, so we explicitly allow them here. This
// must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
if (isGuaranteedToTransferExecutionToSuccessor(Insn))
return false;
if (isa<LoadInst>(Insn)) {
assert(cast<LoadInst>(Insn)->isVolatile() &&
"Non-volatile load should transfer execution to successor!");
return false;
}
if (isa<StoreInst>(Insn)) {
assert(cast<StoreInst>(Insn)->isVolatile() &&
"Non-volatile store should transfer execution to successor!");
return false;
}
return true;
}
bool MemoryWriteTracking::isSpecialInstruction(
const Instruction *Insn) const {
using namespace PatternMatch;
if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
return false;
return Insn->mayWriteToMemory();
}
|