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
|
//===-- 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"
#include "llvm/Support/CommandLine.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 && MaybeFirstSpecial->comesBefore(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);
}
void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
if (isSpecialInstruction(Inst))
FirstSpecialInsts.erase(Inst->getParent());
}
void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
for (const auto *U : Inst->users()) {
if (const auto *UI = dyn_cast<Instruction>(U))
removeInstruction(UI);
}
}
void InstructionPrecedenceTracking::clear() {
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.
return !isGuaranteedToTransferExecutionToSuccessor(Insn);
}
bool MemoryWriteTracking::isSpecialInstruction(
const Instruction *Insn) const {
using namespace PatternMatch;
if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
return false;
return Insn->mayWriteToMemory();
}
|
