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 75