1 //===- llvm/Transforms/Utils/OrderedInstructions.h -------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines an efficient way to check for dominance relation between 2
13 // This interface dispatches to appropriate dominance check given 2
14 // instructions, i.e. in case the instructions are in the same basic block,
15 // OrderedBasicBlock (with instruction numbering and caching) are used.
16 // Otherwise, dominator tree is used.
18 //===----------------------------------------------------------------------===//
20 #ifndef LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
21 #define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/Analysis/OrderedBasicBlock.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/Operator.h"
30 class OrderedInstructions {
31 /// Used to check dominance for instructions in same basic block.
32 mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
35 /// The dominator tree of the parent function.
38 /// Return true if the first instruction comes before the second in the
39 /// same basic block. It will create an ordered basic block, if it does
40 /// not yet exist in OBBMap.
41 bool localDominates(const Instruction *, const Instruction *) const;
45 OrderedInstructions(DominatorTree *DT) : DT(DT) {}
47 /// Return true if first instruction dominates the second.
48 bool dominates(const Instruction *, const Instruction *) const;
50 /// Return true if the first instruction comes before the second in the
51 /// dominator tree DFS traversal if they are in different basic blocks,
52 /// or if the first instruction comes before the second in the same basic
54 bool dfsBefore(const Instruction *, const Instruction *) const;
56 /// Invalidate the OrderedBasicBlock cache when its basic block changes.
57 /// i.e. If an instruction is deleted or added to the basic block, the user
58 /// should call this function to invalidate the OrderedBasicBlock cache for
60 void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
63 } // end namespace llvm
65 #endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H