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