• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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