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 
23 using namespace llvm;
24 
25 #ifndef NDEBUG
26 static cl::opt<bool> ExpensiveAsserts(
27     "ipt-expensive-asserts",
28     cl::desc("Perform expensive assert validation on every query to Instruction"
29              " Precedence Tracking"),
30     cl::init(false), cl::Hidden);
31 #endif
32 
33 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
34     const BasicBlock *BB) {
35 #ifndef NDEBUG
36   // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
37   // catch this situation as early as possible.
38   if (ExpensiveAsserts)
39     validateAll();
40   else
41     validate(BB);
42 #endif
43 
44   if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
45     fill(BB);
46     assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
47   }
48   return FirstSpecialInsts[BB];
49 }
50 
51 bool InstructionPrecedenceTracking::hasSpecialInstructions(
52     const BasicBlock *BB) {
53   return getFirstSpecialInstruction(BB) != nullptr;
54 }
55 
56 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
57     const Instruction *Insn) {
58   const Instruction *MaybeFirstSpecial =
59       getFirstSpecialInstruction(Insn->getParent());
60   return MaybeFirstSpecial && OI.dominates(MaybeFirstSpecial, Insn);
61 }
62 
63 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
64   FirstSpecialInsts.erase(BB);
65   for (auto &I : *BB)
66     if (isSpecialInstruction(&I)) {
67       FirstSpecialInsts[BB] = &I;
68       return;
69     }
70 
71   // Mark this block as having no special instructions.
72   FirstSpecialInsts[BB] = nullptr;
73 }
74 
75 #ifndef NDEBUG
76 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 
94 void InstructionPrecedenceTracking::validateAll() const {
95   // Check that for every known block the cached value is correct.
96   for (auto &It : FirstSpecialInsts)
97     validate(It.first);
98 }
99 #endif
100 
101 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
102                                                         const BasicBlock *BB) {
103   if (isSpecialInstruction(Inst))
104     FirstSpecialInsts.erase(BB);
105   OI.invalidateBlock(BB);
106 }
107 
108 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
109   if (isSpecialInstruction(Inst))
110     FirstSpecialInsts.erase(Inst->getParent());
111   OI.invalidateBlock(Inst->getParent());
112 }
113 
114 void InstructionPrecedenceTracking::clear() {
115   for (auto It : FirstSpecialInsts)
116     OI.invalidateBlock(It.first);
117   FirstSpecialInsts.clear();
118 #ifndef NDEBUG
119   // The map should be valid after clearing (at least empty).
120   validateAll();
121 #endif
122 }
123 
124 bool ImplicitControlFlowTracking::isSpecialInstruction(
125     const Instruction *Insn) const {
126   // If a block's instruction doesn't always pass the control to its successor
127   // instruction, mark the block as having implicit control flow. We use them
128   // to avoid wrong assumptions of sort "if A is executed and B post-dominates
129   // A, then B is also executed". This is not true is there is an implicit
130   // control flow instruction (e.g. a guard) between them.
131   //
132   // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
133   // for volatile stores and loads because they can trap. The discussion on
134   // whether or not it is correct is still ongoing. We might want to get rid
135   // of this logic in the future. Anyways, trapping instructions shouldn't
136   // introduce implicit control flow, so we explicitly allow them here. This
137   // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
138   if (isGuaranteedToTransferExecutionToSuccessor(Insn))
139     return false;
140   if (isa<LoadInst>(Insn)) {
141     assert(cast<LoadInst>(Insn)->isVolatile() &&
142            "Non-volatile load should transfer execution to successor!");
143     return false;
144   }
145   if (isa<StoreInst>(Insn)) {
146     assert(cast<StoreInst>(Insn)->isVolatile() &&
147            "Non-volatile store should transfer execution to successor!");
148     return false;
149   }
150   return true;
151 }
152 
153 bool MemoryWriteTracking::isSpecialInstruction(
154     const Instruction *Insn) const {
155   return Insn->mayWriteToMemory();
156 }
157