Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/SyntheticCountsUtils.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- SyntheticCountsUtils.cpp - synthetic counts propagation utils ---===//
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 utilities for propagating synthetic counts.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Analysis/SyntheticCountsUtils.h"
14
#include "llvm/ADT/DenseSet.h"
15
#include "llvm/ADT/SCCIterator.h"
16
#include "llvm/Analysis/CallGraph.h"
17
#include "llvm/IR/CallSite.h"
18
#include "llvm/IR/Function.h"
19
#include "llvm/IR/InstIterator.h"
20
#include "llvm/IR/Instructions.h"
21
#include "llvm/IR/ModuleSummaryIndex.h"
22
23
using namespace llvm;
24
25
// Given an SCC, propagate entry counts along the edge of the SCC nodes.
26
template <typename CallGraphType>
27
void SyntheticCountsUtils<CallGraphType>::propagateFromSCC(
28
26
    const SccTy &SCC, GetProfCountTy GetProfCount, AddCountTy AddCount) {
29
26
30
26
  DenseSet<NodeRef> SCCNodes;
31
26
  SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
32
26
33
26
  for (auto &Node : SCC)
34
28
    SCCNodes.insert(Node);
35
26
36
26
  // Partition the edges coming out of the SCC into those whose destination is
37
26
  // in the SCC and the rest.
38
28
  for (const auto &Node : SCCNodes) {
39
28
    for (auto &E : children_edges<CallGraphType>(Node)) {
40
28
      if (SCCNodes.count(CGT::edge_dest(E)))
41
4
        SCCEdges.emplace_back(Node, E);
42
24
      else
43
24
        NonSCCEdges.emplace_back(Node, E);
44
28
    }
45
28
  }
46
26
47
26
  // For nodes in the same SCC, update the counts in two steps:
48
26
  // 1. Compute the additional count for each node by propagating the counts
49
26
  // along all incoming edges to the node that originate from within the same
50
26
  // SCC and summing them up.
51
26
  // 2. Add the additional counts to the nodes in the SCC.
52
26
  // This ensures that the order of
53
26
  // traversal of nodes within the SCC doesn't affect the final result.
54
26
55
26
  DenseMap<NodeRef, Scaled64> AdditionalCounts;
56
26
  for (auto &E : SCCEdges) {
57
4
    auto OptProfCount = GetProfCount(E.first, E.second);
58
4
    if (!OptProfCount)
59
0
      continue;
60
4
    auto Callee = CGT::edge_dest(E.second);
61
4
    AdditionalCounts[Callee] += OptProfCount.getValue();
62
4
  }
63
26
64
26
  // Update the counts for the nodes in the SCC.
65
26
  for (auto &Entry : AdditionalCounts)
66
4
    AddCount(Entry.first, Entry.second);
67
26
68
26
  // Now update the counts for nodes outside the SCC.
69
26
  for (auto &E : NonSCCEdges) {
70
24
    auto OptProfCount = GetProfCount(E.first, E.second);
71
24
    if (!OptProfCount)
72
15
      continue;
73
9
    auto Callee = CGT::edge_dest(E.second);
74
9
    AddCount(Callee, OptProfCount.getValue());
75
9
  }
76
26
}
llvm::SyntheticCountsUtils<llvm::CallGraph const*>::propagateFromSCC(std::__1::vector<llvm::CallGraphNode const*, std::__1::allocator<llvm::CallGraphNode const*> > const&, llvm::function_ref<llvm::Optional<llvm::ScaledNumber<unsigned long long> > (llvm::CallGraphNode const*, std::__1::pair<llvm::WeakTrackingVH, llvm::CallGraphNode*> const&)>, llvm::function_ref<void (llvm::CallGraphNode const*, llvm::ScaledNumber<unsigned long long>)>)
Line
Count
Source
28
17
    const SccTy &SCC, GetProfCountTy GetProfCount, AddCountTy AddCount) {
29
17
30
17
  DenseSet<NodeRef> SCCNodes;
31
17
  SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
32
17
33
17
  for (auto &Node : SCC)
34
19
    SCCNodes.insert(Node);
35
17
36
17
  // Partition the edges coming out of the SCC into those whose destination is
37
17
  // in the SCC and the rest.
38
19
  for (const auto &Node : SCCNodes) {
39
22
    for (auto &E : children_edges<CallGraphType>(Node)) {
40
22
      if (SCCNodes.count(CGT::edge_dest(E)))
41
4
        SCCEdges.emplace_back(Node, E);
42
18
      else
43
18
        NonSCCEdges.emplace_back(Node, E);
44
22
    }
45
19
  }
46
17
47
17
  // For nodes in the same SCC, update the counts in two steps:
48
17
  // 1. Compute the additional count for each node by propagating the counts
49
17
  // along all incoming edges to the node that originate from within the same
50
17
  // SCC and summing them up.
51
17
  // 2. Add the additional counts to the nodes in the SCC.
52
17
  // This ensures that the order of
53
17
  // traversal of nodes within the SCC doesn't affect the final result.
54
17
55
17
  DenseMap<NodeRef, Scaled64> AdditionalCounts;
56
17
  for (auto &E : SCCEdges) {
57
4
    auto OptProfCount = GetProfCount(E.first, E.second);
58
4
    if (!OptProfCount)
59
0
      continue;
60
4
    auto Callee = CGT::edge_dest(E.second);
61
4
    AdditionalCounts[Callee] += OptProfCount.getValue();
62
4
  }
63
17
64
17
  // Update the counts for the nodes in the SCC.
65
17
  for (auto &Entry : AdditionalCounts)
66
4
    AddCount(Entry.first, Entry.second);
67
17
68
17
  // Now update the counts for nodes outside the SCC.
69
18
  for (auto &E : NonSCCEdges) {
70
18
    auto OptProfCount = GetProfCount(E.first, E.second);
71
18
    if (!OptProfCount)
72
15
      continue;
73
3
    auto Callee = CGT::edge_dest(E.second);
74
3
    AddCount(Callee, OptProfCount.getValue());
75
3
  }
76
17
}
llvm::SyntheticCountsUtils<llvm::ModuleSummaryIndex*>::propagateFromSCC(std::__1::vector<llvm::ValueInfo, std::__1::allocator<llvm::ValueInfo> > const&, llvm::function_ref<llvm::Optional<llvm::ScaledNumber<unsigned long long> > (llvm::ValueInfo, std::__1::pair<llvm::ValueInfo, llvm::CalleeInfo>&)>, llvm::function_ref<void (llvm::ValueInfo, llvm::ScaledNumber<unsigned long long>)>)
Line
Count
Source
28
9
    const SccTy &SCC, GetProfCountTy GetProfCount, AddCountTy AddCount) {
29
9
30
9
  DenseSet<NodeRef> SCCNodes;
31
9
  SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
32
9
33
9
  for (auto &Node : SCC)
34
9
    SCCNodes.insert(Node);
35
9
36
9
  // Partition the edges coming out of the SCC into those whose destination is
37
9
  // in the SCC and the rest.
38
9
  for (const auto &Node : SCCNodes) {
39
9
    for (auto &E : children_edges<CallGraphType>(Node)) {
40
6
      if (SCCNodes.count(CGT::edge_dest(E)))
41
0
        SCCEdges.emplace_back(Node, E);
42
6
      else
43
6
        NonSCCEdges.emplace_back(Node, E);
44
6
    }
45
9
  }
46
9
47
9
  // For nodes in the same SCC, update the counts in two steps:
48
9
  // 1. Compute the additional count for each node by propagating the counts
49
9
  // along all incoming edges to the node that originate from within the same
50
9
  // SCC and summing them up.
51
9
  // 2. Add the additional counts to the nodes in the SCC.
52
9
  // This ensures that the order of
53
9
  // traversal of nodes within the SCC doesn't affect the final result.
54
9
55
9
  DenseMap<NodeRef, Scaled64> AdditionalCounts;
56
9
  for (auto &E : SCCEdges) {
57
0
    auto OptProfCount = GetProfCount(E.first, E.second);
58
0
    if (!OptProfCount)
59
0
      continue;
60
0
    auto Callee = CGT::edge_dest(E.second);
61
0
    AdditionalCounts[Callee] += OptProfCount.getValue();
62
0
  }
63
9
64
9
  // Update the counts for the nodes in the SCC.
65
9
  for (auto &Entry : AdditionalCounts)
66
0
    AddCount(Entry.first, Entry.second);
67
9
68
9
  // Now update the counts for nodes outside the SCC.
69
9
  for (auto &E : NonSCCEdges) {
70
6
    auto OptProfCount = GetProfCount(E.first, E.second);
71
6
    if (!OptProfCount)
72
0
      continue;
73
6
    auto Callee = CGT::edge_dest(E.second);
74
6
    AddCount(Callee, OptProfCount.getValue());
75
6
  }
76
9
}
77
78
/// Propgate synthetic entry counts on a callgraph \p CG.
79
///
80
/// This performs a reverse post-order traversal of the callgraph SCC. For each
81
/// SCC, it first propagates the entry counts to the nodes within the SCC
82
/// through call edges and updates them in one shot. Then the entry counts are
83
/// propagated to nodes outside the SCC. This requires \p GraphTraits
84
/// to have a specialization for \p CallGraphType.
85
86
template <typename CallGraphType>
87
void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
88
                                                    GetProfCountTy GetProfCount,
89
6
                                                    AddCountTy AddCount) {
90
6
  std::vector<SccTy> SCCs;
91
6
92
6
  // Collect all the SCCs.
93
32
  for (auto I = scc_begin(CG); !I.isAtEnd(); 
++I26
)
94
26
    SCCs.push_back(*I);
95
6
96
6
  // The callgraph-scc needs to be visited in top-down order for propagation.
97
6
  // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
98
6
  // and call propagateFromSCC.
99
6
  for (auto &SCC : reverse(SCCs))
100
26
    propagateFromSCC(SCC, GetProfCount, AddCount);
101
6
}
llvm::SyntheticCountsUtils<llvm::CallGraph const*>::propagate(llvm::CallGraph const* const&, llvm::function_ref<llvm::Optional<llvm::ScaledNumber<unsigned long long> > (llvm::CallGraphNode const*, std::__1::pair<llvm::WeakTrackingVH, llvm::CallGraphNode*> const&)>, llvm::function_ref<void (llvm::CallGraphNode const*, llvm::ScaledNumber<unsigned long long>)>)
Line
Count
Source
89
3
                                                    AddCountTy AddCount) {
90
3
  std::vector<SccTy> SCCs;
91
3
92
3
  // Collect all the SCCs.
93
20
  for (auto I = scc_begin(CG); !I.isAtEnd(); 
++I17
)
94
17
    SCCs.push_back(*I);
95
3
96
3
  // The callgraph-scc needs to be visited in top-down order for propagation.
97
3
  // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
98
3
  // and call propagateFromSCC.
99
3
  for (auto &SCC : reverse(SCCs))
100
17
    propagateFromSCC(SCC, GetProfCount, AddCount);
101
3
}
llvm::SyntheticCountsUtils<llvm::ModuleSummaryIndex*>::propagate(llvm::ModuleSummaryIndex* const&, llvm::function_ref<llvm::Optional<llvm::ScaledNumber<unsigned long long> > (llvm::ValueInfo, std::__1::pair<llvm::ValueInfo, llvm::CalleeInfo>&)>, llvm::function_ref<void (llvm::ValueInfo, llvm::ScaledNumber<unsigned long long>)>)
Line
Count
Source
89
3
                                                    AddCountTy AddCount) {
90
3
  std::vector<SccTy> SCCs;
91
3
92
3
  // Collect all the SCCs.
93
12
  for (auto I = scc_begin(CG); !I.isAtEnd(); 
++I9
)
94
9
    SCCs.push_back(*I);
95
3
96
3
  // The callgraph-scc needs to be visited in top-down order for propagation.
97
3
  // The scc iterator returns the scc in bottom-up order, so reverse the SCCs
98
3
  // and call propagateFromSCC.
99
3
  for (auto &SCC : reverse(SCCs))
100
9
    propagateFromSCC(SCC, GetProfCount, AddCount);
101
3
}
102
103
template class llvm::SyntheticCountsUtils<const CallGraph *>;
104
template class llvm::SyntheticCountsUtils<ModuleSummaryIndex *>;