lib/Analysis/OrderedBasicBlock.cpp

   1 //===- OrderedBasicBlock.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 //
   9 // This file implements the OrderedBasicBlock class. OrderedBasicBlock
  10 // maintains an interface where clients can query if one instruction comes
  11 // before another in a BasicBlock. Since BasicBlock currently lacks a reliable
  12 // way to query relative position between instructions one can use
  13 // OrderedBasicBlock to do such queries. OrderedBasicBlock is lazily built on a
  14 // source BasicBlock and maintains an internal Instruction -> Position map. A
  15 // OrderedBasicBlock instance should be discarded whenever the source
  16 // BasicBlock changes.
  17 //
  18 // It's currently used by the CaptureTracker in order to find relative
  19 // positions of a pair of instructions inside a BasicBlock.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #include "llvm/Analysis/OrderedBasicBlock.h"
  24 #include "llvm/IR/Instruction.h"
  25 using namespace llvm;
  26
  27 OrderedBasicBlock::OrderedBasicBlock(const BasicBlock *BasicB)
  28     : NextInstPos(0), BB(BasicB) {
  29   LastInstFound = BB->end();
  30 }
  31
  32 /// Given no cached results, find if \p A comes before \p B in \p BB.
  33 /// Cache and number out instruction while walking \p BB.
  34 bool OrderedBasicBlock::comesBefore(const Instruction *A,
  35                                     const Instruction *B) {
  36   const Instruction *Inst = nullptr;
  37   assert(!(LastInstFound == BB->end() && NextInstPos != 0) &&
  38          "Instruction supposed to be in NumberedInsts");
  39   assert(A->getParent() == BB && "Instruction supposed to be in the block!");
  40   assert(B->getParent() == BB && "Instruction supposed to be in the block!");
  41
  42   // Start the search with the instruction found in the last lookup round.
  43   auto II = BB->begin();
  44   auto IE = BB->end();
  45   if (LastInstFound != IE)
  46     II = std::next(LastInstFound);
  47
  48   // Number all instructions up to the point where we find 'A' or 'B'.
  49   for (; II != IE; ++II) {
  50     Inst = cast<Instruction>(II);
  51     NumberedInsts[Inst] = NextInstPos++;
  52     if (Inst == A || Inst == B)
  53       break;
  54   }
  55
  56   assert(II != IE && "Instruction not found?");
  57   assert((Inst == A || Inst == B) && "Should find A or B");
  58   LastInstFound = II;
  59   return Inst != B;
  60 }
  61
  62 /// Find out whether \p A dominates \p B, meaning whether \p A
  63 /// comes before \p B in \p BB. This is a simplification that considers
  64 /// cached instruction positions and ignores other basic blocks, being
  65 /// only relevant to compare relative instructions positions inside \p BB.
  66 bool OrderedBasicBlock::dominates(const Instruction *A, const Instruction *B) {
  67   assert(A->getParent() == B->getParent() &&
  68          "Instructions must be in the same basic block!");
  69   assert(A->getParent() == BB && "Instructions must be in the tracked block!");
  70
  71   // First we lookup the instructions. If they don't exist, lookup will give us
  72   // back ::end(). If they both exist, we compare the numbers. Otherwise, if NA
  73   // exists and NB doesn't, it means NA must come before NB because we would
  74   // have numbered NB as well if it didn't. The same is true for NB. If it
  75   // exists, but NA does not, NA must come after it. If neither exist, we need
  76   // to number the block and cache the results (by calling comesBefore).
  77   auto NAI = NumberedInsts.find(A);
  78   auto NBI = NumberedInsts.find(B);
  79   if (NAI != NumberedInsts.end() && NBI != NumberedInsts.end())
  80     return NAI->second < NBI->second;
  81   if (NAI != NumberedInsts.end())
  82     return true;
  83   if (NBI != NumberedInsts.end())
  84     return false;
  85
  86   return comesBefore(A, B);
  87 }
  88
  89 void OrderedBasicBlock::eraseInstruction(const Instruction *I) {
  90   if (LastInstFound != BB->end() && I == &*LastInstFound) {
  91     if (LastInstFound == BB->begin()) {
  92       LastInstFound = BB->end();
  93       NextInstPos = 0;
  94     } else
  95       LastInstFound--;
  96   }
  97
  98   NumberedInsts.erase(I);
  99 }
 100
 101 void OrderedBasicBlock::replaceInstruction(const Instruction *Old,
 102                                            const Instruction *New) {
 103   auto OI = NumberedInsts.find(Old);
 104   if (OI == NumberedInsts.end())
 105     return;
 106
 107   NumberedInsts.insert({New, OI->second});
 108   if (LastInstFound != BB->end() && Old == &*LastInstFound)
 109     LastInstFound = New->getIterator();
 110   NumberedInsts.erase(Old);
 111 }