blob: 8e96809ef9fe3b2ac97ee8570e1dc10478a87159 (
plain)
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
|
//===-- InstructionPrecedenceTracking.cpp -----------------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
// 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"
using namespace llvm;
const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
const BasicBlock *BB) {
#ifndef NDEBUG
// Make sure that we are making this request to tracking which is up-to-date.
validate();
#endif
if (!KnownBlocks.count(BB))
fill(BB);
auto *FirstICF = FirstSpecialInsts.lookup(BB);
assert((!FirstICF || FirstICF->getParent() == BB) && "Inconsistent cache!");
return FirstICF;
}
bool InstructionPrecedenceTracking::hasSpecialInstructions(
const BasicBlock *BB) {
return getFirstSpecialInstruction(BB) != nullptr;
}
bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
const Instruction *Insn) {
const Instruction *MaybeFirstICF =
getFirstSpecialInstruction(Insn->getParent());
return MaybeFirstICF && OI.dominates(MaybeFirstICF, Insn);
}
void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
FirstSpecialInsts.erase(BB);
for (auto &I : *BB)
if (isSpecialInstruction(&I)) {
FirstSpecialInsts[BB] = &I;
break;
}
// Mark this block as having a known result.
KnownBlocks.insert(BB);
}
#ifndef NDEBUG
void InstructionPrecedenceTracking::validate() const {
unsigned NumNoSpecialBlocks = 0;
// Check that for every known block we have something cached for it.
for (auto *BB : KnownBlocks) {
auto It = FirstSpecialInsts.find(BB);
bool BlockHasSpecialInsns = false;
for (const Instruction &Insn : *BB) {
if (isSpecialInstruction(&Insn)) {
assert(It != FirstSpecialInsts.end() &&
"Blocked marked as known but we have no cached value for it!");
assert(It->second == &Insn &&
"Cached first special instruction is wrong!");
BlockHasSpecialInsns = true;
break;
}
}
if (!BlockHasSpecialInsns) {
assert(It == FirstSpecialInsts.end() &&
"Block is marked as having special instructions but in fact it "
"has none!");
++NumNoSpecialBlocks;
}
}
assert(KnownBlocks.size() == NumNoSpecialBlocks + FirstSpecialInsts.size() &&
"We don't have info for some blocks?");
}
#endif
void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
OI.invalidateBlock(BB);
FirstSpecialInsts.erase(BB);
KnownBlocks.erase(BB);
}
void InstructionPrecedenceTracking::clear() {
for (auto It : FirstSpecialInsts)
OI.invalidateBlock(It.first);
FirstSpecialInsts.clear();
KnownBlocks.clear();
#ifndef NDEBUG
// The map should be valid after clearing (at least empty).
validate();
#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;
}
|
