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 
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   if (!FirstSpecialInsts.contains(BB)) {
51     fill(BB);
52     assert(FirstSpecialInsts.contains(BB) && "Must be!");
53   }
54   return FirstSpecialInsts[BB];
55 }
56 
57 bool InstructionPrecedenceTracking::hasSpecialInstructions(
58     const BasicBlock *BB) {
59   return getFirstSpecialInstruction(BB) != nullptr;
60 }
61 
62 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
63     const Instruction *Insn) {
64   const Instruction *MaybeFirstSpecial =
65       getFirstSpecialInstruction(Insn->getParent());
66   return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn);
67 }
68 
69 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
70   FirstSpecialInsts.erase(BB);
71   for (const auto &I : *BB) {
72     NumInstScanned++;
73     if (isSpecialInstruction(&I)) {
74       FirstSpecialInsts[BB] = &I;
75       return;
76     }
77   }
78 
79   // Mark this block as having no special instructions.
80   FirstSpecialInsts[BB] = nullptr;
81 }
82 
83 #ifndef NDEBUG
84 void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
85   auto It = FirstSpecialInsts.find(BB);
86   // Bail if we don't have anything cached for this block.
87   if (It == FirstSpecialInsts.end())
88     return;
89 
90   for (const Instruction &Insn : *BB)
91     if (isSpecialInstruction(&Insn)) {
92       assert(It->second == &Insn &&
93              "Cached first special instruction is wrong!");
94       return;
95     }
96 
97   assert(It->second == nullptr &&
98          "Block is marked as having special instructions but in fact it  has "
99          "none!");
100 }
101 
102 void InstructionPrecedenceTracking::validateAll() const {
103   // Check that for every known block the cached value is correct.
104   for (const auto &It : FirstSpecialInsts)
105     validate(It.first);
106 }
107 #endif
108 
109 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
110                                                         const BasicBlock *BB) {
111   if (isSpecialInstruction(Inst))
112     FirstSpecialInsts.erase(BB);
113 }
114 
115 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
116   auto *BB = Inst->getParent();
117   assert(BB && "must be called before instruction is actually removed");
118   if (FirstSpecialInsts.count(BB) && FirstSpecialInsts[BB] == Inst)
119     FirstSpecialInsts.erase(BB);
120 }
121 
122 void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
123   for (const auto *U : Inst->users()) {
124     if (const auto *UI = dyn_cast<Instruction>(U))
125       removeInstruction(UI);
126   }
127 }
128 
129 void InstructionPrecedenceTracking::clear() {
130   FirstSpecialInsts.clear();
131 #ifndef NDEBUG
132   // The map should be valid after clearing (at least empty).
133   validateAll();
134 #endif
135 }
136 
137 bool ImplicitControlFlowTracking::isSpecialInstruction(
138     const Instruction *Insn) const {
139   // If a block's instruction doesn't always pass the control to its successor
140   // instruction, mark the block as having implicit control flow. We use them
141   // to avoid wrong assumptions of sort "if A is executed and B post-dominates
142   // A, then B is also executed". This is not true is there is an implicit
143   // control flow instruction (e.g. a guard) between them.
144   return !isGuaranteedToTransferExecutionToSuccessor(Insn);
145 }
146 
147 bool MemoryWriteTracking::isSpecialInstruction(
148     const Instruction *Insn) const {
149   using namespace PatternMatch;
150   if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
151     return false;
152   return Insn->mayWriteToMemory();
153 }
154