1 /* Copyright 2020 Google LLC. All Rights Reserved.
2 
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
6 
7     http://www.apache.org/licenses/LICENSE-2.0
8 
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
14 ==============================================================================*/
15 
16 #ifndef RUY_RUY_PROFILER_TREEVIEW_H_
17 #define RUY_RUY_PROFILER_TREEVIEW_H_
18 
19 #ifdef RUY_PROFILER
20 
21 #include <functional>
22 #include <map>
23 #include <memory>
24 #include <vector>
25 
26 #include "ruy/profiler/instrumentation.h"
27 
28 namespace ruy {
29 namespace profiler {
30 
31 // A tree view of a profile.
32 class TreeView {
33  public:
34   struct Node {
35     std::vector<std::unique_ptr<Node>> children;
36     Label label;
37     int weight = 0;
38   };
39 
40   void Populate(const std::vector<char>& samples_buf_);
41 
42   // Intentionally an *ordered* map so that threads are enumerated
43   // in an order that's consistent and typically putting the 'main thread'
44   // first.
45   using ThreadRootsMap = std::map<std::uint32_t, std::unique_ptr<Node>>;
46 
thread_roots()47   const ThreadRootsMap& thread_roots() const { return thread_roots_; }
mutable_thread_roots()48   ThreadRootsMap* mutable_thread_roots() { return &thread_roots_; }
49 
50  private:
51   ThreadRootsMap thread_roots_;
52 };
53 
54 /* Below are API functions for manipulating and printing treeviews. */
55 
56 // Prints the treeview to stdout.
57 void Print(const TreeView& treeview);
58 
59 // Prints the treeview below the given node on stdout.
60 void PrintTreeBelow(const TreeView::Node& node);
61 
62 // Returns the tree depth below the given node.
63 int DepthOfTreeBelow(const TreeView::Node& node);
64 
65 // Returns the sum of weights of nodes below the given node and filtered by
66 // the `match` predicate.
67 int WeightBelowNodeMatchingFunction(
68     const TreeView::Node& node, const std::function<bool(const Label&)>& match);
69 
70 // Returns the sum of weights of nodes below the given node and whose
71 // unformatted label (i.e. raw format string) matches the given `format` string.
72 //
73 // This allows to aggregate nodes whose labels differ only by parameter values.
74 int WeightBelowNodeMatchingUnformatted(const TreeView::Node& node,
75                                        const std::string& format);
76 
77 // Returns the sum of weights of nodes below the given node and whose formatted
78 // label matches the `formatted` string.
79 //
80 // In the case of nodes with parametrized labels, this allows to count only
81 // nodes with specific parameter values. For that purpose, one may also instead
82 // use WeightBelowNodeMatchingFunction directly, with a `match` predicate
83 // comparing raw integer parameter values directly, instead of going through
84 // formatted strings.
85 int WeightBelowNodeMatchingFormatted(const TreeView::Node& node,
86                                      const std::string& formatted);
87 
88 // Produces a `node_out` that is a copy of `node_in` but with tree depth below
89 // it clamped at `depth`, with further subtrees aggregated into single leaf
90 // nodes.
91 void CollapseNode(const TreeView::Node& node_in, int depth,
92                   TreeView::Node* node_out);
93 
94 // Calls CollapseNode with the given `depth` on every subnode filtered by the
95 // `match` predicate. Note that this does NOT limit the tree depth below
96 // `node_out` to `depth`, since each collapsed node below `node_out` may be
97 // arbitrarily far below it and `depth` is only used as the collapsing depth
98 // at that point.
99 void CollapseSubnodesMatchingFunction(
100     const TreeView::Node& node_in, int depth,
101     const std::function<bool(const Label&)>& match, TreeView::Node* node_out);
102 
103 // Calls CollapseNode with the given `depth` on every node filtered by the
104 // `match` predicate. Note that this does NOT limit the tree depth below
105 // `node_out` to `depth`, since each collapsed node below `node_out` may be
106 // arbitrarily far below it and `depth` is only used as the collapsing depth
107 // at that point.
108 void CollapseNodesMatchingFunction(
109     const TreeView& treeview_in, int depth,
110     const std::function<bool(const Label&)>& match, TreeView* treeview_out);
111 
112 // Special case of CollapseNodesMatchingFunction matching unformatted labels,
113 // i.e. raw format strings.
114 // See the comment on WeightBelowNodeMatchingUnformatted.
115 void CollapseNodesMatchingUnformatted(const TreeView& treeview_in, int depth,
116                                       const std::string& format,
117                                       TreeView* treeview_out);
118 
119 // Special case of CollapseNodesMatchingFunction matching formatted labels.
120 // See the comment on WeightBelowNodeMatchingFormatted.
121 void CollapseNodesMatchingFormatted(const TreeView& treeview_in, int depth,
122                                     const std::string& formatted,
123                                     TreeView* treeview_out);
124 
125 }  // namespace profiler
126 }  // namespace ruy
127 
128 #endif  // RUY_PROFILER
129 
130 #endif  // RUY_RUY_PROFILER_TREEVIEW_H_
131