1 //===- llvm/Transforms/Utils/OrderedInstructions.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 an efficient way to check for dominance relation between 2 10 // instructions. 11 // 12 // This interface dispatches to appropriate dominance check given 2 13 // instructions, i.e. in case the instructions are in the same basic block, 14 // OrderedBasicBlock (with instruction numbering and caching) are used. 15 // Otherwise, dominator tree is used. 16 // 17 //===----------------------------------------------------------------------===// 18 19 #ifndef LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H 20 #define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H 21 22 #include "llvm/ADT/DenseMap.h" 23 #include "llvm/Analysis/OrderedBasicBlock.h" 24 #include "llvm/IR/Dominators.h" 25 #include "llvm/IR/Operator.h" 26 27 namespace llvm { 28 29 class OrderedInstructions { 30 /// Used to check dominance for instructions in same basic block. 31 mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> 32 OBBMap; 33 34 /// The dominator tree of the parent function. 35 DominatorTree *DT; 36 37 /// Return true if the first instruction comes before the second in the 38 /// same basic block. It will create an ordered basic block, if it does 39 /// not yet exist in OBBMap. 40 bool localDominates(const Instruction *, const Instruction *) const; 41 42 public: 43 /// Constructor. OrderedInstructions(DominatorTree * DT)44 OrderedInstructions(DominatorTree *DT) : DT(DT) {} 45 46 /// Return true if first instruction dominates the second. 47 bool dominates(const Instruction *, const Instruction *) const; 48 49 /// Return true if the first instruction comes before the second in the 50 /// dominator tree DFS traversal if they are in different basic blocks, 51 /// or if the first instruction comes before the second in the same basic 52 /// block. 53 bool dfsBefore(const Instruction *, const Instruction *) const; 54 55 /// Invalidate the OrderedBasicBlock cache when its basic block changes. 56 /// i.e. If an instruction is deleted or added to the basic block, the user 57 /// should call this function to invalidate the OrderedBasicBlock cache for 58 /// this basic block. invalidateBlock(const BasicBlock * BB)59 void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); } 60 }; 61 62 } // end namespace llvm 63 64 #endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H 65