|
150
|
1 //===-- InstructionPrecedenceTracking.cpp -----------------------*- C++ -*-===//
|
|
|
2 //
|
|
|
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
|
4 // See https://llvm.org/LICENSE.txt for license information.
|
|
|
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8 // Implements a class that is able to define some instructions as "special"
|
|
|
9 // (e.g. as having implicit control flow, or writing memory, or having another
|
|
|
10 // interesting property) and then efficiently answers queries of the types:
|
|
|
11 // 1. Are there any special instructions in the block of interest?
|
|
|
12 // 2. Return first of the special instructions in the given block;
|
|
|
13 // 3. Check if the given instruction is preceeded by the first special
|
|
|
14 // instruction in the same block.
|
|
|
15 // The class provides caching that allows to answer these queries quickly. The
|
|
|
16 // user must make sure that the cached data is invalidated properly whenever
|
|
|
17 // a content of some tracked block is changed.
|
|
|
18 //===----------------------------------------------------------------------===//
|
|
|
19
|
|
|
20 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
|
|
|
21 #include "llvm/Analysis/ValueTracking.h"
|
|
|
22 #include "llvm/IR/PatternMatch.h"
|
|
|
23 #include "llvm/Support/CommandLine.h"
|
|
|
24
|
|
|
25 using namespace llvm;
|
|
|
26
|
|
|
27 #ifndef NDEBUG
|
|
|
28 static cl::opt<bool> ExpensiveAsserts(
|
|
|
29 "ipt-expensive-asserts",
|
|
|
30 cl::desc("Perform expensive assert validation on every query to Instruction"
|
|
|
31 " Precedence Tracking"),
|
|
|
32 cl::init(false), cl::Hidden);
|
|
|
33 #endif
|
|
|
34
|
|
|
35 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
|
|
|
36 const BasicBlock *BB) {
|
|
|
37 #ifndef NDEBUG
|
|
|
38 // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
|
|
|
39 // catch this situation as early as possible.
|
|
|
40 if (ExpensiveAsserts)
|
|
|
41 validateAll();
|
|
|
42 else
|
|
|
43 validate(BB);
|
|
|
44 #endif
|
|
|
45
|
|
|
46 if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
|
|
|
47 fill(BB);
|
|
|
48 assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
|
|
|
49 }
|
|
|
50 return FirstSpecialInsts[BB];
|
|
|
51 }
|
|
|
52
|
|
|
53 bool InstructionPrecedenceTracking::hasSpecialInstructions(
|
|
|
54 const BasicBlock *BB) {
|
|
|
55 return getFirstSpecialInstruction(BB) != nullptr;
|
|
|
56 }
|
|
|
57
|
|
|
58 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
|
|
|
59 const Instruction *Insn) {
|
|
|
60 const Instruction *MaybeFirstSpecial =
|
|
|
61 getFirstSpecialInstruction(Insn->getParent());
|
|
173
|
62 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn);
|
|
150
|
63 }
|
|
|
64
|
|
|
65 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
|
|
|
66 FirstSpecialInsts.erase(BB);
|
|
|
67 for (auto &I : *BB)
|
|
|
68 if (isSpecialInstruction(&I)) {
|
|
|
69 FirstSpecialInsts[BB] = &I;
|
|
|
70 return;
|
|
|
71 }
|
|
|
72
|
|
|
73 // Mark this block as having no special instructions.
|
|
|
74 FirstSpecialInsts[BB] = nullptr;
|
|
|
75 }
|
|
|
76
|
|
|
77 #ifndef NDEBUG
|
|
|
78 void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
|
|
|
79 auto It = FirstSpecialInsts.find(BB);
|
|
|
80 // Bail if we don't have anything cached for this block.
|
|
|
81 if (It == FirstSpecialInsts.end())
|
|
|
82 return;
|
|
|
83
|
|
|
84 for (const Instruction &Insn : *BB)
|
|
|
85 if (isSpecialInstruction(&Insn)) {
|
|
|
86 assert(It->second == &Insn &&
|
|
|
87 "Cached first special instruction is wrong!");
|
|
|
88 return;
|
|
|
89 }
|
|
|
90
|
|
|
91 assert(It->second == nullptr &&
|
|
|
92 "Block is marked as having special instructions but in fact it has "
|
|
|
93 "none!");
|
|
|
94 }
|
|
|
95
|
|
|
96 void InstructionPrecedenceTracking::validateAll() const {
|
|
|
97 // Check that for every known block the cached value is correct.
|
|
|
98 for (auto &It : FirstSpecialInsts)
|
|
|
99 validate(It.first);
|
|
|
100 }
|
|
|
101 #endif
|
|
|
102
|
|
|
103 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
|
|
|
104 const BasicBlock *BB) {
|
|
|
105 if (isSpecialInstruction(Inst))
|
|
|
106 FirstSpecialInsts.erase(BB);
|
|
|
107 }
|
|
|
108
|
|
|
109 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
|
|
|
110 if (isSpecialInstruction(Inst))
|
|
|
111 FirstSpecialInsts.erase(Inst->getParent());
|
|
|
112 }
|
|
|
113
|
|
|
114 void InstructionPrecedenceTracking::clear() {
|
|
|
115 FirstSpecialInsts.clear();
|
|
|
116 #ifndef NDEBUG
|
|
|
117 // The map should be valid after clearing (at least empty).
|
|
|
118 validateAll();
|
|
|
119 #endif
|
|
|
120 }
|
|
|
121
|
|
|
122 bool ImplicitControlFlowTracking::isSpecialInstruction(
|
|
|
123 const Instruction *Insn) const {
|
|
|
124 // If a block's instruction doesn't always pass the control to its successor
|
|
|
125 // instruction, mark the block as having implicit control flow. We use them
|
|
|
126 // to avoid wrong assumptions of sort "if A is executed and B post-dominates
|
|
|
127 // A, then B is also executed". This is not true is there is an implicit
|
|
|
128 // control flow instruction (e.g. a guard) between them.
|
|
173
|
129 return !isGuaranteedToTransferExecutionToSuccessor(Insn);
|
|
150
|
130 }
|
|
|
131
|
|
|
132 bool MemoryWriteTracking::isSpecialInstruction(
|
|
|
133 const Instruction *Insn) const {
|
|
|
134 using namespace PatternMatch;
|
|
|
135 if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
|
|
|
136 return false;
|
|
|
137 return Insn->mayWriteToMemory();
|
|
|
138 }
|
