blob: a3817c29551c954391a873dd413642b2c457f3f7 (
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
|
//===-- 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/ValueTracking.h"
#include "llvm/Transforms/Utils/InstructionPrecedenceTracking.h"
using namespace llvm;
const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
const BasicBlock *BB) {
if (!KnownBlocks.count(BB))
fill(BB);
auto *FirstICF = FirstImplicitControlFlowInsts.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) {
FirstImplicitControlFlowInsts.erase(BB);
for (auto &I : *BB)
if (isSpecialInstruction(&I)) {
FirstImplicitControlFlowInsts[BB] = &I;
break;
}
// Mark this block as having a known result.
KnownBlocks.insert(BB);
}
void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
OI.invalidateBlock(BB);
FirstImplicitControlFlowInsts.erase(BB);
KnownBlocks.erase(BB);
}
void InstructionPrecedenceTracking::clear() {
for (auto It : FirstImplicitControlFlowInsts)
OI.invalidateBlock(It.first);
FirstImplicitControlFlowInsts.clear();
KnownBlocks.clear();
}
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;
}
|
