/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h
Line | Count | Source (jump to first uncovered line) |
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, bool IsPostDom> |
46 | | class IDFCalculator { |
47 | | public: |
48 | | IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT) |
49 | 846k | : DT(DT), useLiveIn(false) {} llvm::IDFCalculator<llvm::BasicBlock*, false>::IDFCalculator(llvm::DominatorTreeBase<llvm::BasicBlock, false>&) Line | Count | Source | 49 | 635k | : DT(DT), useLiveIn(false) {} |
llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::IDFCalculator(llvm::DominatorTreeBase<llvm::BasicBlock, true>&) Line | Count | Source | 49 | 210k | : 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. |
56 | 849k | void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { |
57 | 849k | DefBlocks = &Blocks; |
58 | 849k | } llvm::IDFCalculator<llvm::BasicBlock*, false>::setDefiningBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&) Line | Count | Source | 56 | 639k | void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { | 57 | 639k | DefBlocks = &Blocks; | 58 | 639k | } |
llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::setDefiningBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&) Line | Count | Source | 56 | 210k | void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { | 57 | 210k | DefBlocks = &Blocks; | 58 | 210k | } |
|
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 | | |
66 | 332k | void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { |
67 | 332k | LiveInBlocks = &Blocks; |
68 | 332k | useLiveIn = true; |
69 | 332k | } llvm::IDFCalculator<llvm::BasicBlock*, false>::setLiveInBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&) Line | Count | Source | 66 | 122k | void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { | 67 | 122k | LiveInBlocks = &Blocks; | 68 | 122k | useLiveIn = true; | 69 | 122k | } |
llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::setLiveInBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&) Line | Count | Source | 66 | 210k | void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) { | 67 | 210k | LiveInBlocks = &Blocks; | 68 | 210k | useLiveIn = true; | 69 | 210k | } |
|
70 | | |
71 | | /// \brief Reset the live-in block set to be empty, and tell the IDF |
72 | | /// calculator to not use liveness anymore. |
73 | 0 | void resetLiveInBlocks() { |
74 | 0 | LiveInBlocks = nullptr; |
75 | 0 | useLiveIn = false; |
76 | 0 | } Unexecuted instantiation: llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::resetLiveInBlocks() Unexecuted instantiation: llvm::IDFCalculator<llvm::BasicBlock*, false>::resetLiveInBlocks() |
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, IsPostDom> &DT; |
88 | | bool useLiveIn; |
89 | | const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks; |
90 | | const SmallPtrSetImpl<BasicBlock *> *DefBlocks; |
91 | | }; |
92 | | typedef IDFCalculator<BasicBlock *, false> ForwardIDFCalculator; |
93 | | typedef IDFCalculator<Inverse<BasicBlock *>, true> ReverseIDFCalculator; |
94 | | } |
95 | | #endif |