include/llvm/Analysis/OrderedInstructions.h

   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.
  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.
  59   void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
  60 };
  61
  62 } // end namespace llvm
  63
  64 #endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H