Line data Source code
1 : //===-- InstructionPrecedenceTracking.cpp -----------------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : // Implements a class that is able to define some instructions as "special"
10 : // (e.g. as having implicit control flow, or writing memory, or having another
11 : // interesting property) and then efficiently answers queries of the types:
12 : // 1. Are there any special instructions in the block of interest?
13 : // 2. Return first of the special instructions in the given block;
14 : // 3. Check if the given instruction is preceeded by the first special
15 : // instruction in the same block.
16 : // The class provides caching that allows to answer these queries quickly. The
17 : // user must make sure that the cached data is invalidated properly whenever
18 : // a content of some tracked block is changed.
19 : //===----------------------------------------------------------------------===//
20 :
21 : #include "llvm/Analysis/InstructionPrecedenceTracking.h"
22 : #include "llvm/Analysis/ValueTracking.h"
23 :
24 : using namespace llvm;
25 :
26 : #ifndef NDEBUG
27 : static cl::opt<bool> ExpensiveAsserts(
28 : "ipt-expensive-asserts",
29 : cl::desc("Perform expensive assert validation on every query to Instruction"
30 : " Precedence Tracking"),
31 : cl::init(false), cl::Hidden);
32 : #endif
33 :
34 4059 : const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
35 : const BasicBlock *BB) {
36 : #ifndef NDEBUG
37 : // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
38 : // catch this situation as early as possible.
39 : if (ExpensiveAsserts)
40 : validateAll();
41 : else
42 : validate(BB);
43 : #endif
44 :
45 4059 : if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
46 3632 : fill(BB);
47 : assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
48 : }
49 4059 : return FirstSpecialInsts[BB];
50 : }
51 :
52 0 : bool InstructionPrecedenceTracking::hasSpecialInstructions(
53 : const BasicBlock *BB) {
54 0 : return getFirstSpecialInstruction(BB) != nullptr;
55 : }
56 :
57 4059 : bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
58 : const Instruction *Insn) {
59 : const Instruction *MaybeFirstSpecial =
60 4059 : getFirstSpecialInstruction(Insn->getParent());
61 4059 : return MaybeFirstSpecial && OI.dominates(MaybeFirstSpecial, Insn);
62 : }
63 :
64 3632 : void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
65 3632 : FirstSpecialInsts.erase(BB);
66 44733 : for (auto &I : *BB)
67 41735 : if (isSpecialInstruction(&I)) {
68 634 : FirstSpecialInsts[BB] = &I;
69 : return;
70 : }
71 :
72 : // Mark this block as having no special instructions.
73 2998 : FirstSpecialInsts[BB] = nullptr;
74 : }
75 :
76 : #ifndef NDEBUG
77 : void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
78 : auto It = FirstSpecialInsts.find(BB);
79 : // Bail if we don't have anything cached for this block.
80 : if (It == FirstSpecialInsts.end())
81 : return;
82 :
83 : for (const Instruction &Insn : *BB)
84 : if (isSpecialInstruction(&Insn)) {
85 : assert(It->second == &Insn &&
86 : "Cached first special instruction is wrong!");
87 : return;
88 : }
89 :
90 : assert(It->second == nullptr &&
91 : "Block is marked as having special instructions but in fact it has "
92 : "none!");
93 : }
94 :
95 : void InstructionPrecedenceTracking::validateAll() const {
96 : // Check that for every known block the cached value is correct.
97 : for (auto &It : FirstSpecialInsts)
98 : validate(It.first);
99 : }
100 : #endif
101 :
102 25929 : void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
103 25929 : OI.invalidateBlock(BB);
104 25929 : FirstSpecialInsts.erase(BB);
105 25929 : }
106 :
107 91495 : void InstructionPrecedenceTracking::clear() {
108 94256 : for (auto It : FirstSpecialInsts)
109 2761 : OI.invalidateBlock(It.first);
110 91495 : FirstSpecialInsts.clear();
111 : #ifndef NDEBUG
112 : // The map should be valid after clearing (at least empty).
113 : validateAll();
114 : #endif
115 91495 : }
116 :
117 41735 : bool ImplicitControlFlowTracking::isSpecialInstruction(
118 : const Instruction *Insn) const {
119 : // If a block's instruction doesn't always pass the control to its successor
120 : // instruction, mark the block as having implicit control flow. We use them
121 : // to avoid wrong assumptions of sort "if A is executed and B post-dominates
122 : // A, then B is also executed". This is not true is there is an implicit
123 : // control flow instruction (e.g. a guard) between them.
124 : //
125 : // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
126 : // for volatile stores and loads because they can trap. The discussion on
127 : // whether or not it is correct is still ongoing. We might want to get rid
128 : // of this logic in the future. Anyways, trapping instructions shouldn't
129 : // introduce implicit control flow, so we explicitly allow them here. This
130 : // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
131 41735 : if (isGuaranteedToTransferExecutionToSuccessor(Insn))
132 : return false;
133 636 : if (isa<LoadInst>(Insn)) {
134 : assert(cast<LoadInst>(Insn)->isVolatile() &&
135 : "Non-volatile load should transfer execution to successor!");
136 : return false;
137 : }
138 634 : if (isa<StoreInst>(Insn)) {
139 : assert(cast<StoreInst>(Insn)->isVolatile() &&
140 : "Non-volatile store should transfer execution to successor!");
141 0 : return false;
142 : }
143 : return true;
144 : }
|
