include/llvm/Analysis/OrderedBasicBlock.h

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