/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 *>; |