142 lines · cpp
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-exception6//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 another10// 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 special14// instruction in the same block.15// The class provides caching that allows to answer these queries quickly. The16// user must make sure that the cached data is invalidated properly whenever17// 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 NDEBUG28static 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#endif34 35const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(36 const BasicBlock *BB) {37#ifndef NDEBUG38 // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to39 // catch this situation as early as possible.40 if (ExpensiveAsserts)41 validateAll();42 else43 validate(BB);44#endif45 46 auto [It, Inserted] = FirstSpecialInsts.try_emplace(BB);47 if (Inserted) {48 for (const auto &I : *BB) {49 if (isSpecialInstruction(&I)) {50 It->second = &I;51 break;52 }53 }54 }55 return It->second;56}57 58bool InstructionPrecedenceTracking::hasSpecialInstructions(59 const BasicBlock *BB) {60 return getFirstSpecialInstruction(BB) != nullptr;61}62 63bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(64 const Instruction *Insn) {65 const Instruction *MaybeFirstSpecial =66 getFirstSpecialInstruction(Insn->getParent());67 return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn);68}69 70#ifndef NDEBUG71void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {72 auto It = FirstSpecialInsts.find(BB);73 // Bail if we don't have anything cached for this block.74 if (It == FirstSpecialInsts.end())75 return;76 77 for (const Instruction &Insn : *BB)78 if (isSpecialInstruction(&Insn)) {79 assert(It->second == &Insn &&80 "Cached first special instruction is wrong!");81 return;82 }83 84 assert(It->second == nullptr &&85 "Block is marked as having special instructions but in fact it has "86 "none!");87}88 89void InstructionPrecedenceTracking::validateAll() const {90 // Check that for every known block the cached value is correct.91 for (const auto &It : FirstSpecialInsts)92 validate(It.first);93}94#endif95 96void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,97 const BasicBlock *BB) {98 if (isSpecialInstruction(Inst))99 FirstSpecialInsts.erase(BB);100}101 102void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {103 auto *BB = Inst->getParent();104 assert(BB && "must be called before instruction is actually removed");105 auto It = FirstSpecialInsts.find(BB);106 if (It != FirstSpecialInsts.end() && It->second == Inst)107 FirstSpecialInsts.erase(It);108}109 110void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {111 for (const auto *U : Inst->users()) {112 if (const auto *UI = dyn_cast<Instruction>(U))113 removeInstruction(UI);114 }115}116 117void InstructionPrecedenceTracking::clear() {118 FirstSpecialInsts.clear();119#ifndef NDEBUG120 // The map should be valid after clearing (at least empty).121 validateAll();122#endif123}124 125bool ImplicitControlFlowTracking::isSpecialInstruction(126 const Instruction *Insn) const {127 // If a block's instruction doesn't always pass the control to its successor128 // instruction, mark the block as having implicit control flow. We use them129 // to avoid wrong assumptions of sort "if A is executed and B post-dominates130 // A, then B is also executed". This is not true is there is an implicit131 // control flow instruction (e.g. a guard) between them.132 return !isGuaranteedToTransferExecutionToSuccessor(Insn);133}134 135bool MemoryWriteTracking::isSpecialInstruction(136 const Instruction *Insn) const {137 using namespace PatternMatch;138 if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))139 return false;140 return Insn->mayWriteToMemory();141}142