Coverage Report

Created: 2019-02-15 18:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h
Line
Count
Source (jump to first uncovered line)
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
1.14M
       : DT(DT), GD(nullptr), useLiveIn(false) {}
llvm::IDFCalculator<llvm::BasicBlock*, false>::IDFCalculator(llvm::DominatorTreeBase<llvm::BasicBlock, false>&)
Line
Count
Source
49
988k
       : DT(DT), GD(nullptr), useLiveIn(false) {}
llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::IDFCalculator(llvm::DominatorTreeBase<llvm::BasicBlock, true>&)
Line
Count
Source
49
159k
       : DT(DT), GD(nullptr), useLiveIn(false) {}
50
51
   IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT,
52
                 const GraphDiff<BasicBlock *, IsPostDom> *GD)
53
0
       : DT(DT), GD(GD), useLiveIn(false) {}
Unexecuted instantiation: llvm::IDFCalculator<llvm::BasicBlock*, false>::IDFCalculator(llvm::DominatorTreeBase<llvm::BasicBlock, false>&, llvm::GraphDiff<llvm::BasicBlock*, false> const*)
Unexecuted instantiation: llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::IDFCalculator(llvm::DominatorTreeBase<llvm::BasicBlock, true>&, llvm::GraphDiff<llvm::BasicBlock*, true> const*)
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
1.00M
   void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
61
1.00M
     DefBlocks = &Blocks;
62
1.00M
   }
llvm::IDFCalculator<llvm::BasicBlock*, false>::setDefiningBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&)
Line
Count
Source
60
850k
   void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
61
850k
     DefBlocks = &Blocks;
62
850k
   }
llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::setDefiningBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&)
Line
Count
Source
60
158k
   void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
61
158k
     DefBlocks = &Blocks;
62
158k
   }
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
294k
  void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
71
294k
    LiveInBlocks = &Blocks;
72
294k
    useLiveIn = true;
73
294k
  }
llvm::IDFCalculator<llvm::BasicBlock*, false>::setLiveInBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&)
Line
Count
Source
70
135k
  void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
71
135k
    LiveInBlocks = &Blocks;
72
135k
    useLiveIn = true;
73
135k
  }
llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::setLiveInBlocks(llvm::SmallPtrSetImpl<llvm::BasicBlock*> const&)
Line
Count
Source
70
158k
  void setLiveInBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
71
158k
    LiveInBlocks = &Blocks;
72
158k
    useLiveIn = true;
73
158k
  }
74
75
  /// Reset the live-in block set to be empty, and tell the IDF
76
  /// calculator to not use liveness anymore.
77
6
  void resetLiveInBlocks() {
78
6
    LiveInBlocks = nullptr;
79
6
    useLiveIn = false;
80
6
  }
llvm::IDFCalculator<llvm::BasicBlock*, false>::resetLiveInBlocks()
Line
Count
Source
77
6
  void resetLiveInBlocks() {
78
6
    LiveInBlocks = nullptr;
79
6
    useLiveIn = false;
80
6
  }
Unexecuted instantiation: llvm::IDFCalculator<llvm::Inverse<llvm::BasicBlock*>, true>::resetLiveInBlocks()
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