LCOV - code coverage report
Current view: top level - lib/Analysis - InstructionPrecedenceTracking.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 26 29 89.7 %
Date: 2018-10-20 13:21:21 Functions: 6 7 85.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- InstructionPrecedenceTracking.cpp -----------------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : // Implements a class that is able to define some instructions as "special"
      10             : // (e.g. as having implicit control flow, or writing memory, or having another
      11             : // interesting property) and then efficiently answers queries of the types:
      12             : // 1. Are there any special instructions in the block of interest?
      13             : // 2. Return first of the special instructions in the given block;
      14             : // 3. Check if the given instruction is preceeded by the first special
      15             : //    instruction in the same block.
      16             : // The class provides caching that allows to answer these queries quickly. The
      17             : // user must make sure that the cached data is invalidated properly whenever
      18             : // a content of some tracked block is changed.
      19             : //===----------------------------------------------------------------------===//
      20             : 
      21             : #include "llvm/Analysis/InstructionPrecedenceTracking.h"
      22             : #include "llvm/Analysis/ValueTracking.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        4059 : 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        4059 :   if (FirstSpecialInsts.find(BB) == FirstSpecialInsts.end()) {
      46        3632 :     fill(BB);
      47             :     assert(FirstSpecialInsts.find(BB) != FirstSpecialInsts.end() && "Must be!");
      48             :   }
      49        4059 :   return FirstSpecialInsts[BB];
      50             : }
      51             : 
      52           0 : bool InstructionPrecedenceTracking::hasSpecialInstructions(
      53             :     const BasicBlock *BB) {
      54           0 :   return getFirstSpecialInstruction(BB) != nullptr;
      55             : }
      56             : 
      57        4059 : bool InstructionPrecedenceTracking::isPreceededBySpecialInstruction(
      58             :     const Instruction *Insn) {
      59             :   const Instruction *MaybeFirstSpecial =
      60        4059 :       getFirstSpecialInstruction(Insn->getParent());
      61        4059 :   return MaybeFirstSpecial && OI.dominates(MaybeFirstSpecial, Insn);
      62             : }
      63             : 
      64        3632 : void InstructionPrecedenceTracking::fill(const BasicBlock *BB) {
      65        3632 :   FirstSpecialInsts.erase(BB);
      66       44733 :   for (auto &I : *BB)
      67       41735 :     if (isSpecialInstruction(&I)) {
      68         634 :       FirstSpecialInsts[BB] = &I;
      69             :       return;
      70             :     }
      71             : 
      72             :   // Mark this block as having no special instructions.
      73        2998 :   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       25929 : void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
     103       25929 :   OI.invalidateBlock(BB);
     104       25929 :   FirstSpecialInsts.erase(BB);
     105       25929 : }
     106             : 
     107       91495 : void InstructionPrecedenceTracking::clear() {
     108       94256 :   for (auto It : FirstSpecialInsts)
     109        2761 :     OI.invalidateBlock(It.first);
     110       91495 :   FirstSpecialInsts.clear();
     111             : #ifndef NDEBUG
     112             :   // The map should be valid after clearing (at least empty).
     113             :   validateAll();
     114             : #endif
     115       91495 : }
     116             : 
     117       41735 : bool ImplicitControlFlowTracking::isSpecialInstruction(
     118             :     const Instruction *Insn) const {
     119             :   // If a block's instruction doesn't always pass the control to its successor
     120             :   // instruction, mark the block as having implicit control flow. We use them
     121             :   // to avoid wrong assumptions of sort "if A is executed and B post-dominates
     122             :   // A, then B is also executed". This is not true is there is an implicit
     123             :   // control flow instruction (e.g. a guard) between them.
     124             :   //
     125             :   // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
     126             :   // for volatile stores and loads because they can trap. The discussion on
     127             :   // whether or not it is correct is still ongoing. We might want to get rid
     128             :   // of this logic in the future. Anyways, trapping instructions shouldn't
     129             :   // introduce implicit control flow, so we explicitly allow them here. This
     130             :   // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
     131       41735 :   if (isGuaranteedToTransferExecutionToSuccessor(Insn))
     132             :     return false;
     133         636 :   if (isa<LoadInst>(Insn)) {
     134             :     assert(cast<LoadInst>(Insn)->isVolatile() &&
     135             :            "Non-volatile load should transfer execution to successor!");
     136             :     return false;
     137             :   }
     138         634 :   if (isa<StoreInst>(Insn)) {
     139             :     assert(cast<StoreInst>(Insn)->isVolatile() &&
     140             :            "Non-volatile store should transfer execution to successor!");
     141           0 :     return false;
     142             :   }
     143             :   return true;
     144             : }

Generated by: LCOV version 1.13