• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \brief Compute iterated dominance frontiers using a linear time algorithm.
11 ///
12 /// The algorithm used here is based on:
13 ///
14 ///   Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
15 ///   In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
16 ///   Programming Languages
17 ///   POPL '95. ACM, New York, NY, 62-73.
18 ///
19 /// It has been modified to not explicitly use the DJ graph data structure and
20 /// to directly compute pruned SSA using per-variable liveness information.
21 //
22 //===----------------------------------------------------------------------===//
23 
24 #ifndef LLVM_ANALYSIS_IDF_H
25 #define LLVM_ANALYSIS_IDF_H
26 
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/Dominators.h"
32 
33 namespace llvm {
34 
35 /// \brief 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>
46 class IDFCalculator {
47 
48 public:
IDFCalculator(DominatorTreeBase<BasicBlock> & DT)49   IDFCalculator(DominatorTreeBase<BasicBlock> &DT) : DT(DT), useLiveIn(false) {}
50 
51   /// \brief Give the IDF calculator the set of blocks in which the value is
52   /// defined.  This is equivalent to the set of starting blocks it should be
53   /// calculating the IDF for (though later gets pruned based on liveness).
54   ///
55   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
setDefiningBlocks(const SmallPtrSetImpl<BasicBlock * > & Blocks)56   void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
57     DefBlocks = &Blocks;
58   }
59 
60   /// \brief Give the IDF calculator the set of blocks in which the value is
61   /// live on entry to the block.   This is used to prune the IDF calculation to
62   /// not include blocks where any phi insertion would be dead.
63   ///
64   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
65 
setLiveInBlocks(const SmallPtrSetImpl<BasicBlock * > & Blocks)66   void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
67     LiveInBlocks = &Blocks;
68     useLiveIn = true;
69   }
70 
71   /// \brief Reset the live-in block set to be empty, and tell the IDF
72   /// calculator to not use liveness anymore.
resetLiveInBlocks()73   void resetLiveInBlocks() {
74     LiveInBlocks = nullptr;
75     useLiveIn = false;
76   }
77 
78   /// \brief Calculate iterated dominance frontiers
79   ///
80   /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in
81   /// the file-level comment.  It performs DF->IDF pruning using the live-in
82   /// set, to avoid computing the IDF for blocks where an inserted PHI node
83   /// would be dead.
84   void calculate(SmallVectorImpl<BasicBlock *> &IDFBlocks);
85 
86 private:
87   DominatorTreeBase<BasicBlock> &DT;
88   bool useLiveIn;
89   DenseMap<DomTreeNode *, unsigned> DomLevels;
90   const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
91   const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
92   SmallVector<BasicBlock *, 32> PHIBlocks;
93 };
94 typedef IDFCalculator<BasicBlock *> ForwardIDFCalculator;
95 typedef IDFCalculator<Inverse<BasicBlock *>> ReverseIDFCalculator;
96 }
97 #endif
98