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());
62   return MaybeFirstSpecial && OI.dominates(MaybeFirstSpecial, Insn);
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.
129   //
130   // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
131   // for volatile stores and loads because they can trap. The discussion on
132   // whether or not it is correct is still ongoing. We might want to get rid
133   // of this logic in the future. Anyways, trapping instructions shouldn't
134   // introduce implicit control flow, so we explicitly allow them here. This
135   // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
136   if (isGuaranteedToTransferExecutionToSuccessor(Insn))
137     return false;
138   if (isa<LoadInst>(Insn)) {
139     assert(cast<LoadInst>(Insn)->isVolatile() &&
140            "Non-volatile load should transfer execution to successor!");
141     return false;
142   }
143   if (isa<StoreInst>(Insn)) {
144     assert(cast<StoreInst>(Insn)->isVolatile() &&
145            "Non-volatile store should transfer execution to successor!");
146     return false;
147   }
148   return true;
149 }
150 
151 bool MemoryWriteTracking::isSpecialInstruction(
152     const Instruction *Insn) const {
153   using namespace PatternMatch;
154   if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
155     return false;
156   return Insn->mayWriteToMemory();
157 }
158