include/llvm/Analysis/OrderedBasicBlock.h

   1 //===- llvm/Analysis/OrderedBasicBlock.h --------------------- -*- 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 defines the OrderedBasicBlock class. OrderedBasicBlock maintains
  10 // an interface where clients can query if one instruction comes before another
  11 // in a BasicBlock. Since BasicBlock currently lacks a reliable way to query
  12 // relative position between instructions one can use OrderedBasicBlock to do
  13 // such queries. OrderedBasicBlock is lazily built on a source BasicBlock and
  14 // maintains an internal Instruction -> Position map. A OrderedBasicBlock
  15 // instance should be discarded whenever the source BasicBlock changes.
  16 //
  17 // It's currently used by the CaptureTracker in order to find relative
  18 // positions of a pair of instructions inside a BasicBlock.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_ANALYSIS_ORDEREDBASICBLOCK_H
  23 #define LLVM_ANALYSIS_ORDEREDBASICBLOCK_H
  24
  25 #include "llvm/ADT/DenseMap.h"
  26 #include "llvm/IR/BasicBlock.h"
  27
  28 namespace llvm {
  29
  30 class Instruction;
  31 class BasicBlock;
  32
  33 class OrderedBasicBlock {
  34 private:
  35   /// Map a instruction to its position in a BasicBlock.
  36   SmallDenseMap<const Instruction *, unsigned, 32> NumberedInsts;
  37
  38   /// Keep track of last instruction inserted into \p NumberedInsts.
  39   /// It speeds up queries for uncached instructions by providing a start point
  40   /// for new queries in OrderedBasicBlock::comesBefore.
  41   BasicBlock::const_iterator LastInstFound;
  42
  43   /// The position/number to tag the next instruction to be found.
  44   unsigned NextInstPos;
  45
  46   /// The source BasicBlock to map.
  47   const BasicBlock *BB;
  48
  49   /// Given no cached results, find if \p A comes before \p B in \p BB.
  50   /// Cache and number out instruction while walking \p BB.
  51   bool comesBefore(const Instruction *A, const Instruction *B);
  52
  53 public:
  54   OrderedBasicBlock(const BasicBlock *BasicB);
  55
  56   /// Find out whether \p A dominates \p B, meaning whether \p A
  57   /// comes before \p B in \p BB. This is a simplification that considers
  58   /// cached instruction positions and ignores other basic blocks, being
  59   /// only relevant to compare relative instructions positions inside \p BB.
  60   /// Returns false for A == B.
  61   bool dominates(const Instruction *A, const Instruction *B);
  62
  63   /// Remove \p from the ordering, if it is present.
  64   void eraseInstruction(const Instruction *I);
  65
  66   /// Replace \p Old with \p New in the ordering. \p New is assigned the
  67   /// numbering of \p Old, so it must be inserted at the same position in the
  68   /// IR.
  69   void replaceInstruction(const Instruction *Old, const Instruction *New);
  70 };
  71
  72 } // End llvm namespace
  73
  74 #endif