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 25using namespace llvm; 26 27#ifndef NDEBUG 28static 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 35const 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 53bool InstructionPrecedenceTracking::hasSpecialInstructions( 54 const BasicBlock *BB) { 55 return getFirstSpecialInstruction(BB) != nullptr; 56} 57 58bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction( 59 const Instruction *Insn) { 60 const Instruction *MaybeFirstSpecial = 61 getFirstSpecialInstruction(Insn->getParent()); 62 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn); 63} 64 65void 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 78void 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 96void 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 103void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst, 104 const BasicBlock *BB) { 105 if (isSpecialInstruction(Inst)) 106 FirstSpecialInsts.erase(BB); 107} 108 109void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) { 110 if (isSpecialInstruction(Inst)) 111 FirstSpecialInsts.erase(Inst->getParent()); 112} 113 114void 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 122bool 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 return !isGuaranteedToTransferExecutionToSuccessor(Insn); 130} 131 132bool MemoryWriteTracking::isSpecialInstruction( 133 const Instruction *Insn) const { 134 using namespace PatternMatch; 135 if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) 136 return false; 137 return Insn->mayWriteToMemory(); 138} 139