Line data    Source code

       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      118207 : class OrderedBasicBlock {
      35             : private:
      36             :   /// Map a instruction to its position in a BasicBlock.
      37             :   SmallDenseMap<const Instruction *, unsigned, 32> NumberedInsts;
      38             : 
      39             :   /// 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             :   /// The position/number to tag the next instruction to be found.
      45             :   unsigned NextInstPos;
      46             : 
      47             :   /// The source BasicBlock to map.
      48             :   const BasicBlock *BB;
      49             : 
      50             :   /// 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             :   /// 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             :   /// Returns false for A == B.
      62             :   bool dominates(const Instruction *A, const Instruction *B);
      63             : };
      64             : 
      65             : } // End llvm namespace
      66             : 
      67             : #endif