include/llvm/Analysis/IteratedDominanceFrontier.h

   1 //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- 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 /// \file
   9 /// Compute iterated dominance frontiers using a linear time algorithm.
  10 ///
  11 /// The algorithm used here is based on:
  12 ///
  13 ///   Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
  14 ///   In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
  15 ///   Programming Languages
  16 ///   POPL '95. ACM, New York, NY, 62-73.
  17 ///
  18 /// It has been modified to not explicitly use the DJ graph data structure and
  19 /// to directly compute pruned SSA using per-variable liveness information.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #ifndef LLVM_ANALYSIS_IDF_H
  24 #define LLVM_ANALYSIS_IDF_H
  25
  26 #include "llvm/ADT/DenseMap.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/ADT/SmallVector.h"
  29 #include "llvm/IR/BasicBlock.h"
  30 #include "llvm/IR/CFGDiff.h"
  31 #include "llvm/IR/Dominators.h"
  32
  33 namespace llvm {
  34
  35 /// Determine the iterated dominance frontier, given a set of defining
  36 /// blocks, and optionally, a set of live-in blocks.
  37 ///
  38 /// In turn, the results can be used to place phi nodes.
  39 ///
  40 /// This algorithm is a linear time computation of Iterated Dominance Frontiers,
  41 /// pruned using the live-in set.
  42 /// By default, liveness is not used to prune the IDF computation.
  43 /// The template parameters should be either BasicBlock* or Inverse<BasicBlock
  44 /// *>, depending on if you want the forward or reverse IDF.
  45 template <class NodeTy, bool IsPostDom>
  46 class IDFCalculator {
  47  public:
  48    IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT)
  49        : DT(DT), GD(nullptr), useLiveIn(false) {}
  50
  51    IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT,
  52                  const GraphDiff<BasicBlock *, IsPostDom> *GD)
  53        : DT(DT), GD(GD), useLiveIn(false) {}
  54
  55    /// Give the IDF calculator the set of blocks in which the value is
  56    /// defined.  This is equivalent to the set of starting blocks it should be
  57    /// calculating the IDF for (though later gets pruned based on liveness).
  58    ///
  59    /// Note: This set *must* live for the entire lifetime of the IDF calculator.
  60    void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
  61      DefBlocks = &Blocks;
  62    }
  63
  64   /// Give the IDF calculator the set of blocks in which the value is
  65   /// live on entry to the block.   This is used to prune the IDF calculation to
  66   /// not include blocks where any phi insertion would be dead.
  67   ///
  68   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
  69
  70   void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
  71     LiveInBlocks = &Blocks;
  72     useLiveIn = true;
  73   }
  74
  75   /// Reset the live-in block set to be empty, and tell the IDF
  76   /// calculator to not use liveness anymore.
  77   void resetLiveInBlocks() {
  78     LiveInBlocks = nullptr;
  79     useLiveIn = false;
  80   }
  81
  82   /// Calculate iterated dominance frontiers
  83   ///
  84   /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
  85   /// the file-level comment.  It performs DF->IDF pruning using the live-in
  86   /// set, to avoid computing the IDF for blocks where an inserted PHI node
  87   /// would be dead.
  88   void calculate(SmallVectorImpl<BasicBlock *> &IDFBlocks);
  89
  90 private:
  91  DominatorTreeBase<BasicBlock, IsPostDom> &DT;
  92  const GraphDiff<BasicBlock *, IsPostDom> *GD;
  93  bool useLiveIn;
  94  const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
  95  const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
  96 };
  97 typedef IDFCalculator<BasicBlock *, false> ForwardIDFCalculator;
  98 typedef IDFCalculator<Inverse<BasicBlock *>, true> ReverseIDFCalculator;
  99 }
 100 #endif