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 : // These are protected so that they can be accessed by unittests.
96 :
97 : // Frequency information for the whole block graph (includes basic block
98 : // information).
99 : IndexedFrequencyMap frequencies_;
100 :
101 : // The image layout to which the profile data applies.
102 : const ImageLayout* image_layout_;
103 :
104 : // The global temperature of the block graph.
105 : double global_temperature_;
106 :
107 : // The profiles for blocks of the block_graph.
108 : ProfileMap profiles_;
109 :
110 : // A empty profile used for all block never executed.
111 : scoped_ptr<BlockProfile> empty_profile_;
112 :
113 : private:
114 : DISALLOW_COPY_AND_ASSIGN(ApplicationProfile);
115 : };
116 :
117 : // This class contains profile information for a block (function).
118 : class ApplicationProfile::BlockProfile {
119 : public:
120 : // Default constructor. Produce information for a block never executed.
121 E : BlockProfile()
122 : : count_(0), temperature_(0), percentile_(0) {
123 E : }
124 :
125 : // Constructor.
126 : // @param count the block entry count.
127 : // @param temperature the temperature of a block is the sum of the basic
128 : // blocks entry counts.
129 E : BlockProfile(EntryCountType count, double temperature)
130 : : count_(count), temperature_(temperature), percentile_(0) {
131 E : }
132 :
133 : // Accessors.
134 : // @{
135 E : EntryCountType count() const { return count_; }
136 E : double temperature() const { return temperature_; }
137 :
138 E : double percentile() const { return percentile_; }
139 E : void set_percentile(double p) { percentile_ = p; }
140 : // @}
141 :
142 : protected:
143 : // The entry count of the block.
144 : EntryCountType count_;
145 :
146 : // The temperature of the whole block.
147 : double temperature_;
148 :
149 : // The rank of this block's temperature as compared to all blocks in the block
150 : // graph. The value is between 0 and 1.
151 : double percentile_;
152 : };
153 :
154 : // This class contains profile information for a subgraph.
155 : class SubGraphProfile {
156 : public:
157 : // Forward declaration.
158 : class BasicBlockProfile;
159 :
160 : typedef block_graph::BasicCodeBlock BasicCodeBlock;
161 : typedef grinder::basic_block_util::EntryCountType EntryCountType;
162 : typedef std::map<const BasicCodeBlock*, BasicBlockProfile>
163 : BasicBlockProfileMap;
164 :
165 : // Constructor
166 : SubGraphProfile();
167 :
168 : // Retrieve the profile for a given basic block.
169 : // @param block the basic block to find profile information.
170 : // @returns the profile of the basic block or singleton empty profile when
171 : // there is no information available.
172 : const BasicBlockProfile* GetBasicBlockProfile(
173 : const BasicCodeBlock* block) const;
174 :
175 : protected:
176 : // These are protected so that they can be accessed by unittests.
177 :
178 : // Allow ApplicationProfile to create and modify instances of this class.
179 : friend class ApplicationProfile;
180 :
181 : // Map basic blocks to their profile.
182 : BasicBlockProfileMap basic_blocks_;
183 :
184 : // An empty profile used for all basic blocks never executed.
185 : scoped_ptr<BasicBlockProfile> empty_profile_;
186 : };
187 :
188 : // This class contains profile information for a basic-block.
189 : class SubGraphProfile::BasicBlockProfile {
190 : public:
191 : typedef block_graph::BasicCodeBlock BasicCodeBlock;
192 : typedef std::map<const BasicCodeBlock*, EntryCountType> SuccessorsCountMap;
193 :
194 E : BasicBlockProfile() : count_(0), mispredicted_(0) {
195 E : }
196 :
197 : // Returns the entry count of a basic block.
198 : // @returns the basic block entry count.
199 E : EntryCountType count() const { return count_; }
200 :
201 : // Returns the ratio of misprediction to jumps to successors.
202 : // @returns the basic block entry count ratio.
203 : double GetMispredictedRatio() const;
204 :
205 : // Returns the number of times a given successor was taken from this basic
206 : // block.
207 : // @param successor the successor to retrieve the corresponding count.
208 : // @returns the arc count between this block and the successor.
209 : EntryCountType GetSuccessorCount(const BasicCodeBlock* successor) const;
210 :
211 : // Returns the ratio of branch taken from the basic block to |successor|.
212 : // @returns the successors ratio for @successor.
213 : double GetSuccessorRatio(const BasicCodeBlock* successor) const;
214 :
215 : protected:
216 : // These are protected so that they can be accessed by unittests.
217 :
218 : // Allow ApplicationProfile to modify private fields.
219 : friend class ApplicationProfile;
220 :
221 : // The entry count of the basic block.
222 : EntryCountType count_;
223 :
224 : // The count of mispredictions to jumps to successors.
225 : EntryCountType mispredicted_;
226 :
227 : // Maps successors to the taken count.
228 : SuccessorsCountMap successors_;
229 : };
230 :
231 : } // namespace optimize
232 :
233 : #endif // SYZYGY_OPTIMIZE_APPLICATION_PROFILE_H_
|