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/ADT/Statistic.h"
23 #include "llvm/IR/PatternMatch.h"
24 #include "llvm/Support/CommandLine.h"
25
26 using namespace llvm;
27
28 #define DEBUG_TYPE "ipt"
29 STATISTIC(NumInstScanned, "Number of insts scanned while updating ibt");
30
31 #ifndef NDEBUG
32 static cl::opt<bool> ExpensiveAsserts(
33 "ipt-expensive-asserts",
34 cl::desc("Perform expensive assert validation on every query to Instruction"
35 " Precedence Tracking"),
36 cl::init(false), cl::Hidden);
37 #endif
38
getFirstSpecialInstruction(const BasicBlock * BB)39 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
40 const BasicBlock *BB) {
41 #ifndef NDEBUG
42 // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
43 // catch this situation as early as possible.
44 if (ExpensiveAsserts)
45 validateAll();
46 else
47 validate(BB);
48 #endif
49
50 auto [It, Inserted] = FirstSpecialInsts.try_emplace(BB);
51 if (Inserted) {
52 for (const auto &I : *BB) {
53 NumInstScanned++;
54 if (isSpecialInstruction(&I)) {
55 It->second = &I;
56 break;
57 }
58 }
59 }
60 return It->second;
61 }
62
hasSpecialInstructions(const BasicBlock * BB)63 bool InstructionPrecedenceTracking::hasSpecialInstructions(
64 const BasicBlock *BB) {
65 return getFirstSpecialInstruction(BB) != nullptr;
66 }
67
isPreceededBySpecialInstruction(const Instruction * Insn)68 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
69 const Instruction *Insn) {
70 const Instruction *MaybeFirstSpecial =
71 getFirstSpecialInstruction(Insn->getParent());
72 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn);
73 }
74
75 #ifndef NDEBUG
validate(const BasicBlock * BB) const76 void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
77 auto It = FirstSpecialInsts.find(BB);
78 // Bail if we don't have anything cached for this block.
79 if (It == FirstSpecialInsts.end())
80 return;
81
82 for (const Instruction &Insn : *BB)
83 if (isSpecialInstruction(&Insn)) {
84 assert(It->second == &Insn &&
85 "Cached first special instruction is wrong!");
86 return;
87 }
88
89 assert(It->second == nullptr &&
90 "Block is marked as having special instructions but in fact it has "
91 "none!");
92 }
93
validateAll() const94 void InstructionPrecedenceTracking::validateAll() const {
95 // Check that for every known block the cached value is correct.
96 for (const auto &It : FirstSpecialInsts)
97 validate(It.first);
98 }
99 #endif
100
insertInstructionTo(const Instruction * Inst,const BasicBlock * BB)101 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
102 const BasicBlock *BB) {
103 if (isSpecialInstruction(Inst))
104 FirstSpecialInsts.erase(BB);
105 }
106
removeInstruction(const Instruction * Inst)107 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
108 auto *BB = Inst->getParent();
109 assert(BB && "must be called before instruction is actually removed");
110 auto It = FirstSpecialInsts.find(BB);
111 if (It != FirstSpecialInsts.end() && It->second == Inst)
112 FirstSpecialInsts.erase(It);
113 }
114
removeUsersOf(const Instruction * Inst)115 void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
116 for (const auto *U : Inst->users()) {
117 if (const auto *UI = dyn_cast<Instruction>(U))
118 removeInstruction(UI);
119 }
120 }
121
clear()122 void InstructionPrecedenceTracking::clear() {
123 FirstSpecialInsts.clear();
124 #ifndef NDEBUG
125 // The map should be valid after clearing (at least empty).
126 validateAll();
127 #endif
128 }
129
isSpecialInstruction(const Instruction * Insn) const130 bool ImplicitControlFlowTracking::isSpecialInstruction(
131 const Instruction *Insn) const {
132 // If a block's instruction doesn't always pass the control to its successor
133 // instruction, mark the block as having implicit control flow. We use them
134 // to avoid wrong assumptions of sort "if A is executed and B post-dominates
135 // A, then B is also executed". This is not true is there is an implicit
136 // control flow instruction (e.g. a guard) between them.
137 return !isGuaranteedToTransferExecutionToSuccessor(Insn);
138 }
139
isSpecialInstruction(const Instruction * Insn) const140 bool MemoryWriteTracking::isSpecialInstruction(
141 const Instruction *Insn) const {
142 using namespace PatternMatch;
143 if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
144 return false;
145 return Insn->mayWriteToMemory();
146 }
147