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 67