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/IR/PatternMatch.h"
  23
  24 using namespace llvm;
  25
  26 #ifndef NDEBUG
  27 static cl::opt<bool> ExpensiveAsserts(
  28     "ipt-expensive-asserts",
  29     cl::desc("Perform expensive assert validation on every query to Instruction"
  30              " Precedence Tracking"),
  31     cl::init(false), cl::Hidden);
  32 #endif
  33
  34 const Instruction *InstructionPrecedenceTracking::getFirstSpecialInstruction(
  35     const BasicBlock *BB) {
  36 #ifndef NDEBUG
  37   // If there is a bug connected to invalid cache, turn on ExpensiveAsserts to
  38   // catch this situation as early as possible.
  39   if (ExpensiveAsserts)
  40     validateAll();
  41   else
  42     validate(BB);
  43 #endif
  44
  45   if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
  46     fill(BB);
  47     assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
  48   }
  49   return FirstSpecialInsts[BB];
  50 }
  51
  52 bool InstructionPrecedenceTracking::hasSpecialInstructions(
  53     const BasicBlock *BB) {
  54   return getFirstSpecialInstruction(BB) != nullptr;
  55 }
  56
  57 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
  58     const Instruction *Insn) {
  59   const Instruction *MaybeFirstSpecial =
  60       getFirstSpecialInstruction(Insn->getParent());
  61   return MaybeFirstSpecial && OI.dominates(MaybeFirstSpecial, Insn);
  62 }
  63
  64 void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
  65   FirstSpecialInsts.erase(BB);
  66   for (auto &I : *BB)
  67     if (isSpecialInstruction(&I)) {
  68       FirstSpecialInsts[BB] = &I;
  69       return;
  70     }
  71
  72   // Mark this block as having no special instructions.
  73   FirstSpecialInsts[BB] = nullptr;
  74 }
  75
  76 #ifndef NDEBUG
  77 void InstructionPrecedenceTracking::validate(const BasicBlock *BB) const {
  78   auto It = FirstSpecialInsts.find(BB);
  79   // Bail if we don't have anything cached for this block.
  80   if (It == FirstSpecialInsts.end())
  81     return;
  82
  83   for (const Instruction &Insn : *BB)
  84     if (isSpecialInstruction(&Insn)) {
  85       assert(It->second == &Insn &&
  86              "Cached first special instruction is wrong!");
  87       return;
  88     }
  89
  90   assert(It->second == nullptr &&
  91          "Block is marked as having special instructions but in fact it  has "
  92          "none!");
  93 }
  94
  95 void InstructionPrecedenceTracking::validateAll() const {
  96   // Check that for every known block the cached value is correct.
  97   for (auto &It : FirstSpecialInsts)
  98     validate(It.first);
  99 }
 100 #endif
 101
 102 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
 103                                                         const BasicBlock *BB) {
 104   if (isSpecialInstruction(Inst))
 105     FirstSpecialInsts.erase(BB);
 106   OI.invalidateBlock(BB);
 107 }
 108
 109 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
 110   if (isSpecialInstruction(Inst))
 111     FirstSpecialInsts.erase(Inst->getParent());
 112   OI.invalidateBlock(Inst->getParent());
 113 }
 114
 115 void InstructionPrecedenceTracking::clear() {
 116   for (auto It : FirstSpecialInsts)
 117     OI.invalidateBlock(It.first);
 118   FirstSpecialInsts.clear();
 119 #ifndef NDEBUG
 120   // The map should be valid after clearing (at least empty).
 121   validateAll();
 122 #endif
 123 }
 124
 125 bool ImplicitControlFlowTracking::isSpecialInstruction(
 126     const Instruction *Insn) const {
 127   // If a block's instruction doesn't always pass the control to its successor
 128   // instruction, mark the block as having implicit control flow. We use them
 129   // to avoid wrong assumptions of sort "if A is executed and B post-dominates
 130   // A, then B is also executed". This is not true is there is an implicit
 131   // control flow instruction (e.g. a guard) between them.
 132   //
 133   // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
 134   // for volatile stores and loads because they can trap. The discussion on
 135   // whether or not it is correct is still ongoing. We might want to get rid
 136   // of this logic in the future. Anyways, trapping instructions shouldn't
 137   // introduce implicit control flow, so we explicitly allow them here. This
 138   // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
 139   if (isGuaranteedToTransferExecutionToSuccessor(Insn))
 140     return false;
 141   if (isa<LoadInst>(Insn)) {
 142     assert(cast<LoadInst>(Insn)->isVolatile() &&
 143            "Non-volatile load should transfer execution to successor!");
 144     return false;
 145   }
 146   if (isa<StoreInst>(Insn)) {
 147     assert(cast<StoreInst>(Insn)->isVolatile() &&
 148            "Non-volatile store should transfer execution to successor!");
 149     return false;
 150   }
 151   return true;
 152 }
 153
 154 bool MemoryWriteTracking::isSpecialInstruction(
 155     const Instruction *Insn) const {
 156   using namespace PatternMatch;
 157   if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
 158     return false;
 159   return Insn->mayWriteToMemory();
 160 }