Home | History | Annotate | Line # | Download | only in Analysis 
      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 
     25 using namespace llvm;
     26 
     27 #ifndef NDEBUG
     28 static 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 
     35 const 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 
     53 bool InstructionPrecedenceTracking::hasSpecialInstructions(
     54     const BasicBlock *BB) {
     55   return getFirstSpecialInstruction(BB) != nullptr;
     56 }
     57 
     58 bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
     59     const Instruction *Insn) {
     60   const Instruction *MaybeFirstSpecial =
     61       getFirstSpecialInstruction(Insn->getParent());
     62   return MaybeFirstSpecial && MaybeFirstSpecial->comesBefore(Insn);
     63 }
     64 
     65 void 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
     78 void 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 
     96 void 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 
    103 void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
    104                                                         const BasicBlock *BB) {
    105   if (isSpecialInstruction(Inst))
    106     FirstSpecialInsts.erase(BB);
    107 }
    108 
    109 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
    110   if (isSpecialInstruction(Inst))
    111     FirstSpecialInsts.erase(Inst->getParent());
    112 }
    113 
    114 void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
    115   for (const auto *U : Inst->users()) {
    116     if (const auto *UI = dyn_cast<Instruction>(U))
    117       removeInstruction(UI);
    118   }
    119 }
    120 
    121 void InstructionPrecedenceTracking::clear() {
    122   FirstSpecialInsts.clear();
    123 #ifndef NDEBUG
    124   // The map should be valid after clearing (at least empty).
    125   validateAll();
    126 #endif
    127 }
    128 
    129 bool ImplicitControlFlowTracking::isSpecialInstruction(
    130     const Instruction *Insn) const {
    131   // If a block's instruction doesn't always pass the control to its successor
    132   // instruction, mark the block as having implicit control flow. We use them
    133   // to avoid wrong assumptions of sort "if A is executed and B post-dominates
    134   // A, then B is also executed". This is not true is there is an implicit
    135   // control flow instruction (e.g. a guard) between them.
    136   return !isGuaranteedToTransferExecutionToSuccessor(Insn);
    137 }
    138 
    139 bool MemoryWriteTracking::isSpecialInstruction(
    140     const Instruction *Insn) const {
    141   using namespace PatternMatch;
    142   if (match(Insn, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
    143     return false;
    144   return Insn->mayWriteToMemory();
    145 }
    146