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 auto [It, Inserted] = FirstSpecialInsts.try_emplace(BB); 51 if (Inserted) { 52 for (const auto &I : *BB) { 53 NumInstScanned++; 54 if (isSpecialInstruction(&I)) { 55 It->second = &I; 56 break; 57 } 58 } 59 } 60 return It->second; 61 } 62 63 bool InstructionPrecedenceTracking::hasSpecialInstructions( 64 const BasicBlock *BB) { 65 return getFirstSpecialInstruction(BB) != nullptr; 66 } 67 68 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction( 69 const Instruction *Insn) { 70 const Instruction *MaybeFirstSpecial = 71 getFirstSpecialInstruction(Insn->getParent()); 72 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn); 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 (const 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 } 106 107 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) { 108 auto *BB = Inst->getParent(); 109 assert(BB && "must be called before instruction is actually removed"); 110 auto It = FirstSpecialInsts.find(BB); 111 if (It != FirstSpecialInsts.end() && It->second == Inst) 112 FirstSpecialInsts.erase(It); 113 } 114 115 void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) { 116 for (const auto *U : Inst->users()) { 117 if (const auto *UI = dyn_cast<Instruction>(U)) 118 removeInstruction(UI); 119 } 120 } 121 122 void InstructionPrecedenceTracking::clear() { 123 FirstSpecialInsts.clear(); 124 #ifndef NDEBUG 125 // The map should be valid after clearing (at least empty). 126 validateAll(); 127 #endif 128 } 129 130 bool ImplicitControlFlowTracking::isSpecialInstruction( 131 const Instruction *Insn) const { 132 // If a block's instruction doesn't always pass the control to its successor 133 // instruction, mark the block as having implicit control flow. We use them 134 // to avoid wrong assumptions of sort "if A is executed and B post-dominates 135 // A, then B is also executed". This is not true is there is an implicit 136 // control flow instruction (e.g. a guard) between them. 137 return !isGuaranteedToTransferExecutionToSuccessor(Insn); 138 } 139 140 bool MemoryWriteTracking::isSpecialInstruction( 141 const Instruction *Insn) const { 142 using namespace PatternMatch; 143 if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) 144 return false; 145 return Insn->mayWriteToMemory(); 146 } 147