1 //===-- InstructionPrecedenceTracking.cpp -----------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 // Implements a class that is able to define some instructions as "special"
10 // (e.g. as having implicit control flow, or writing memory, or having another
11 // interesting property) and then efficiently answers queries of the types:
12 // 1. Are there any special instructions in the block of interest?
13 // 2. Return first of the special instructions in the given block;
14 // 3. Check if the given instruction is preceeded by the first special
15 //    instruction in the same block.
16 // The class provides caching that allows to answer these queries quickly. The
17 // user must make sure that the cached data is invalidated properly whenever
18 // a content of some tracked block is changed.
19 //===----------------------------------------------------------------------===//
20 
21 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 
24 using namespace llvm;
25 
26 #ifndef NDEBUG
27 static cl::opt<bool> ExpensiveAsserts(
28     "ipt-expensive-asserts",
29     cl::desc("Perform expensive assert validation on every query to Instruction"
30              " Precedence Tracking"),
31     cl::init(false), cl::Hidden);
32 #endif
33 
34 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
35     const BasicBlock *BB) {
36 #ifndef NDEBUG
37   // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
38   // catch this situation as early as possible.
39   if (ExpensiveAsserts)
40     validateAll();
41   else
42     validate(BB);
43 #endif
44 
45   if (!KnownBlocks.count(BB))
46     fill(BB);
47   auto *FirstICF = FirstSpecialInsts.lookup(BB);
48   assert((!FirstICF || FirstICF->getParent() == BB) && "Inconsistent cache!");
49   return FirstICF;
50 }
51 
52 bool InstructionPrecedenceTracking::hasSpecialInstructions(
53     const BasicBlock *BB) {
54   return getFirstSpecialInstruction(BB) != nullptr;
55 }
56 
57 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
58     const Instruction *Insn) {
59   const Instruction *MaybeFirstICF =
60       getFirstSpecialInstruction(Insn->getParent());
61   return MaybeFirstICF && OI.dominates(MaybeFirstICF, Insn);
62 }
63 
64 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
65   FirstSpecialInsts.erase(BB);
66   for (auto &I : *BB)
67     if (isSpecialInstruction(&I)) {
68       FirstSpecialInsts[BB] = &I;
69       break;
70     }
71 
72   // Mark this block as having a known result.
73   KnownBlocks.insert(BB);
74 }
75 
76 #ifndef NDEBUG
77 void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
78   // If we don't know anything about this block, make sure we don't store
79   // a bucket for it in FirstSpecialInsts map.
80   if (!KnownBlocks.count(BB)) {
81     assert(FirstSpecialInsts.find(BB) == FirstSpecialInsts.end() && "Must be!");
82     return;
83   }
84 
85   auto It = FirstSpecialInsts.find(BB);
86   bool BlockHasSpecialInsns = false;
87   for (const Instruction &Insn : *BB) {
88     if (isSpecialInstruction(&Insn)) {
89       assert(It != FirstSpecialInsts.end() &&
90              "Blocked marked as known but we have no cached value for it!");
91       assert(It->second == &Insn &&
92              "Cached first special instruction is wrong!");
93       BlockHasSpecialInsns = true;
94       break;
95     }
96   }
97   if (!BlockHasSpecialInsns)
98     assert(It == FirstSpecialInsts.end() &&
99            "Block is marked as having special instructions but in fact it "
100            "has none!");
101 }
102 
103 void InstructionPrecedenceTracking::validateAll() const {
104   // Check that for every known block the cached value is correct.
105   for (auto *BB : KnownBlocks)
106     validate(BB);
107 
108   // Check that all blocks with cached values are marked as known.
109   for (auto &It : FirstSpecialInsts)
110     assert(KnownBlocks.count(It.first) &&
111            "We have a cached value but the block is not marked as known?");
112 }
113 #endif
114 
115 void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
116   OI.invalidateBlock(BB);
117   FirstSpecialInsts.erase(BB);
118   KnownBlocks.erase(BB);
119 }
120 
121 void InstructionPrecedenceTracking::clear() {
122   for (auto It : FirstSpecialInsts)
123     OI.invalidateBlock(It.first);
124   FirstSpecialInsts.clear();
125   KnownBlocks.clear();
126 #ifndef NDEBUG
127   // The map should be valid after clearing (at least empty).
128   validateAll();
129 #endif
130 }
131 
132 bool ImplicitControlFlowTracking::isSpecialInstruction(
133     const Instruction *Insn) const {
134   // If a block's instruction doesn't always pass the control to its successor
135   // instruction, mark the block as having implicit control flow. We use them
136   // to avoid wrong assumptions of sort "if A is executed and B post-dominates
137   // A, then B is also executed". This is not true is there is an implicit
138   // control flow instruction (e.g. a guard) between them.
139   //
140   // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
141   // for volatile stores and loads because they can trap. The discussion on
142   // whether or not it is correct is still ongoing. We might want to get rid
143   // of this logic in the future. Anyways, trapping instructions shouldn't
144   // introduce implicit control flow, so we explicitly allow them here. This
145   // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
146   if (isGuaranteedToTransferExecutionToSuccessor(Insn))
147     return false;
148   if (isa<LoadInst>(Insn)) {
149     assert(cast<LoadInst>(Insn)->isVolatile() &&
150            "Non-volatile load should transfer execution to successor!");
151     return false;
152   }
153   if (isa<StoreInst>(Insn)) {
154     assert(cast<StoreInst>(Insn)->isVolatile() &&
155            "Non-volatile store should transfer execution to successor!");
156     return false;
157   }
158   return true;
159 }
160