1 : // Copyright 2013 Google Inc. 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 : // The ApplicationProfile class is used to hold metrics taken by instrumenting
16 : // and running the application. Profile guided optimisations use this class to
17 : // retrieve information about runtime metrics.
18 : //
19 : // Example:
20 : // ApplicationProfile profile(&image_layout);
21 : // profile.ImportFrequencies(frequencies);
22 : // profile.ComputeGlobalProfile();
23 : //
24 : // foreach block in block_graph {
25 : // ApplicationProfile::BlockProfile* bp = profile.GetBlockProfile();
26 : // if (bp->percentile() < 0.05)
27 : // LOG(INFO) << "This function is probably hot: " << block->name();
28 : // }
29 : //
30 : // Transformations are responsible for updating metrics when possible.
31 :
32 : #ifndef SYZYGY_OPTIMIZE_APPLICATION_PROFILE_H_
33 : #define SYZYGY_OPTIMIZE_APPLICATION_PROFILE_H_
34 :
35 : #include <map>
36 :
37 : #include "syzygy/block_graph/basic_block.h"
38 : #include "syzygy/block_graph/basic_block_subgraph.h"
39 : #include "syzygy/grinder/basic_block_util.h"
40 : #include "syzygy/pe/image_layout.h"
41 :
42 : namespace optimize {
43 :
44 : // Forward declaration.
45 : class SubGraphProfile;
46 :
47 : // This class holds profile information for a block_graph.
48 : class ApplicationProfile {
49 : public:
50 : typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
51 : typedef block_graph::BlockGraph BlockGraph;
52 : typedef grinder::basic_block_util::IndexedFrequencyMap IndexedFrequencyMap;
53 : typedef grinder::basic_block_util::EntryCountType EntryCountType;
54 : typedef pe::ImageLayout ImageLayout;
55 :
56 : // Forward declaration.
57 : class BlockProfile;
58 : typedef std::map<BlockGraph::BlockId, BlockProfile> ProfileMap;
59 :
60 : // Constructor.
61 : // @param image_layout The image layout.
62 : // @note |image_layout| must remains alive until this class get destroyed.
63 : explicit ApplicationProfile(const ImageLayout* image_layout);
64 :
65 : // Retrieve the profile for a given block.
66 : // @param block the block to find profile information.
67 : // @returns the profile of the block or singleton empty profile when there is
68 : // no information available.
69 : const BlockProfile* GetBlockProfile(const BlockGraph::Block* block) const;
70 :
71 : // @returns the global temperature of the basic block;
72 : // @note Invalid until the call to ComputeGlobalProfile.
73 E : double global_temperature() const { return global_temperature_; }
74 :
75 : // Compute global profile and update block profiles contribution.
76 : // @returns true on success, false otherwise.
77 : // @note BlockProfile.percentile() and GetGlobalTemperature() aren't valid
78 : // before this function is called.
79 : bool ComputeGlobalProfile();
80 :
81 : // Compute profile information for basic blocks of a subgraph.
82 : // @param subgraph subgraph for which to calculate profiler information.
83 : // @param profile receives the profile information.
84 : void ComputeSubGraphProfile(const BasicBlockSubGraph* subgraph,
85 : scoped_ptr<SubGraphProfile>* profile);
86 :
87 : // Import the frequency information of an application.
88 : // @param frequencies the branches frequencies.
89 : // @returns true on success, false otherwise.
90 : // @note This function should only be called once.
91 : // TODO(etienneb): Support multiple importation.
92 : bool ImportFrequencies(const IndexedFrequencyMap& frequencies);
93 :
94 : protected:
95 : // Frequency information for the whole block graph (includes basic block
96 : // information).
97 : IndexedFrequencyMap frequencies_;
98 :
99 : // The image layout to which the profile data applies.
100 : const ImageLayout* image_layout_;
101 :
102 : // The global temperature of the block graph.
103 : double global_temperature_;
104 :
105 : // The profiles for blocks of the block_graph.
106 : ProfileMap profiles_;
107 :
108 : // A empty profile used for all block never executed.
109 : scoped_ptr<BlockProfile> empty_profile_;
110 :
111 : private:
112 : DISALLOW_COPY_AND_ASSIGN(ApplicationProfile);
113 : };
114 :
115 : // This class contains profile information for a block (function).
116 : class ApplicationProfile::BlockProfile {
117 : public:
118 : // Default constructor. Produce information for a block never executed.
119 E : BlockProfile()
120 : : count_(0), temperature_(0), percentile_(0) {
121 E : }
122 :
123 : // Constructor.
124 : // @param count the block entry count.
125 : // @param temperature the temperature of a block is the sum of the basic
126 : // blocks entry counts.
127 E : BlockProfile(EntryCountType count, double temperature)
128 : : count_(count), temperature_(temperature), percentile_(0) {
129 E : }
130 :
131 : // Accessors.
132 : // @{
133 E : EntryCountType count() const { return count_; }
134 E : double temperature() const { return temperature_; }
135 :
136 E : double percentile() const { return percentile_; }
137 E : void set_percentile(double p) { percentile_ = p; }
138 : // @}
139 :
140 : protected:
141 : // The entry count of the block.
142 : EntryCountType count_;
143 :
144 : // The temperature of the whole block.
145 : double temperature_;
146 :
147 : // The rank of this block's temperature as compared to all blocks in the block
148 : // graph. The value is between 0 and 1.
149 : double percentile_;
150 : };
151 :
152 : // This class contains profile information for a subgraph.
153 : class SubGraphProfile {
154 : public:
155 : // Forward declaration.
156 : class BasicBlockProfile;
157 :
158 : typedef block_graph::BasicCodeBlock BasicCodeBlock;
159 : typedef grinder::basic_block_util::EntryCountType EntryCountType;
160 : typedef std::map<const BasicCodeBlock*, BasicBlockProfile>
161 : BasicBlockProfileMap;
162 :
163 : // Constructor
164 E : SubGraphProfile() { }
165 :
166 : // Retrieve the profile for a given basic block.
167 : // @param block the basic block to find profile information.
168 : // @returns the profile of the basic block or singleton empty profile when
169 : // there is no information available.
170 : const BasicBlockProfile* GetBasicBlockProfile(
171 : const BasicCodeBlock* block) const;
172 :
173 : private:
174 : // Allow ApplicationProfile to create and modify instances of this class.
175 : friend class ApplicationProfile;
176 :
177 : // Map basic blocks to their profile.
178 : BasicBlockProfileMap basic_blocks_;
179 :
180 : // An empty profile used for all basic blocks never executed.
181 : scoped_ptr<BasicBlockProfile> empty_profile_;
182 : };
183 :
184 : // This class contains profile information for a basic-block.
185 : class SubGraphProfile::BasicBlockProfile {
186 : public:
187 : typedef block_graph::BasicCodeBlock BasicCodeBlock;
188 : typedef std::map<const BasicCodeBlock*, EntryCountType> SuccessorsCountMap;
189 :
190 E : BasicBlockProfile() : count_(0), mispredicted_(0) {
191 E : }
192 :
193 : // Returns the entry count of a basic block.
194 : // @returns the basic block entry count.
195 E : EntryCountType count() const { return count_; }
196 :
197 : // Returns the ratio of misprediction to jumps to successors.
198 : // @returns the basic block entry count ratio.
199 : double GetMispredictedRatio() const;
200 :
201 : // Returns the number of times a given successor was taken from this basic
202 : // block.
203 : // @param successor the successor to retrieve the corresponding count.
204 : // @returns the arc count between this block and the successor.
205 : EntryCountType GetSuccessorCount(const BasicCodeBlock* successor) const;
206 :
207 : // Returns the ratio of branch taken from the basic block to |successor|.
208 : // @returns the successors ratio for @successor.
209 : double GetSuccessorRatio(const BasicCodeBlock* successor) const;
210 :
211 : private:
212 : // Allow ApplicationProfile to modify private fields.
213 : friend class ApplicationProfile;
214 :
215 : // The entry count of the basic block.
216 : EntryCountType count_;
217 :
218 : // The count of mispredictions to jumps to successors.
219 : EntryCountType mispredicted_;
220 :
221 : // Maps successors to the taken count.
222 : SuccessorsCountMap successors_;
223 : };
224 :
225 : } // namespace optimize
226 :
227 : #endif // SYZYGY_OPTIMIZE_APPLICATION_PROFILE_H_
|