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 28namespace llvm { 29 30class Instruction; 31class BasicBlock; 32 33class OrderedBasicBlock { 34private: 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 53public: 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