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