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 : #include "syzygy/optimize/application_profile.h"
16 :
17 : #include "gmock/gmock.h"
18 : #include "gtest/gtest.h"
19 : #include "syzygy/block_graph/basic_block_decomposer.h"
20 : #include "syzygy/block_graph/basic_block_subgraph.h"
21 :
22 : namespace optimize {
23 :
24 : namespace {
25 :
26 : using block_graph::BasicBlockDecomposer;
27 : using block_graph::BasicBlockSubGraph;
28 : using block_graph::BlockGraph;
29 : using grinder::basic_block_util::IndexedFrequencyMap;
30 : using grinder::basic_block_util::IndexedFrequencyOffset;
31 : using testing::ContainerEq;
32 :
33 : typedef ApplicationProfile::BlockProfile BlockProfile;
34 : typedef BasicBlockSubGraph::BasicCodeBlock BasicCodeBlock;
35 : typedef BasicBlockSubGraph::BasicEndBlock BasicEndBlock;
36 : typedef BlockGraph::Offset Offset;
37 : typedef SubGraphProfile::BasicBlockProfile BasicBlockProfile;
38 : typedef core::RelativeAddress RelativeAddress;
39 : typedef grinder::basic_block_util::EntryCountType EntryCountType;
40 : typedef pe::ImageLayout ImageLayout;
41 :
42 : const size_t kEntryCountColumn = 0;
43 : const size_t kTakenCountColumn = 1;
44 : const size_t kMissPredictedColumn = 2;
45 :
46 : const size_t kBlock1Count = 42;
47 : const size_t kBlock2Count = 128;
48 : const size_t kBlock2BodyCount = 256;
49 : const size_t kBlock3Count = 0;
50 :
51 E : const core::RelativeAddress kSmallCodeAddress(0x3000);
52 : const Offset kBasicBlockOffset0 = 0;
53 : const Offset kBasicBlockOffset1 = 4;
54 : const Offset kBasicBlockOffset2 = 7;
55 : const EntryCountType kBasicBlockCount0 = 100;
56 : const EntryCountType kBasicBlockCount1 = 80;
57 : const EntryCountType kBasicBlockCount2 = 20;
58 : const uint8_t kSmallCode[] = {
59 : 0x3B,
60 : 0xC1, // cmp %eax, %ecx
61 : 0x7D,
62 : 0x03, // jge +7
63 : 0x03,
64 : 0xC1, // add %eax, %ecx
65 : 0xC3, // ret
66 : 0x2B,
67 : 0xC1, // sub %eax, %ecx
68 : 0xC3 // ret
69 : };
70 :
71 : class TestBlockProfile : public ApplicationProfile::BlockProfile {
72 : public:
73 : using ApplicationProfile::BlockProfile::count_;
74 : using ApplicationProfile::BlockProfile::temperature_;
75 : using ApplicationProfile::BlockProfile::percentile_;
76 : };
77 :
78 : class TestAplicationProfile : public ApplicationProfile {
79 : public:
80 : using ApplicationProfile::frequencies_;
81 : using ApplicationProfile::image_layout_;
82 : using ApplicationProfile::global_temperature_;
83 : using ApplicationProfile::profiles_;
84 : using ApplicationProfile::empty_profile_;
85 :
86 E : explicit TestAplicationProfile(ImageLayout* layout)
87 E : : ApplicationProfile(layout) {
88 E : DCHECK_NE(reinterpret_cast<ImageLayout*>(NULL), layout);
89 E : }
90 : };
91 :
92 : class ApplicationProfileTest : public testing::Test {
93 : public:
94 E : ApplicationProfileTest() : layout_(&block_graph_) {
95 E : }
96 :
97 E : void PopulateLayout() {
98 : // Build a dummy block graph.
99 E : BlockGraph::Section* section1 = block_graph_.AddSection(".text", 0);
100 E : BlockGraph::Section* section2 = block_graph_.AddSection(".text_cold", 0);
101 E : BlockGraph::Section* section3 = block_graph_.AddSection(".text_sub", 0);
102 E : block1_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 10, "block1");
103 E : block2_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 10, "block2");
104 E : block3_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK, 10, "block3");
105 E : block1_->set_section(section1->id());
106 E : block2_->set_section(section2->id());
107 E : block3_->set_section(section2->id());
108 :
109 E : block_code_ = block_graph_.AddBlock(BlockGraph::CODE_BLOCK,
110 : sizeof(kSmallCode),
111 : "SmallCode");
112 :
113 : // Build a dummy image layout.
114 E : pe::ImageLayout::SectionInfo section_info1 = {};
115 E : section_info1.name = section1->name();
116 E : section_info1.addr = core::RelativeAddress(0x1000);
117 E : section_info1.size = 0x1000;
118 E : section_info1.data_size = 0x1000;
119 E : layout_.sections.push_back(section_info1);
120 :
121 E : pe::ImageLayout::SectionInfo section_info2 = {};
122 E : section_info2.name = section2->name();
123 E : section_info2.addr = core::RelativeAddress(0x2000);
124 E : section_info2.size = 0x1000;
125 E : section_info2.data_size = 0x1000;
126 E : layout_.sections.push_back(section_info2);
127 :
128 E : pe::ImageLayout::SectionInfo section_info3 = {};
129 E : section_info3.name = section3->name();
130 E : section_info3.addr = kSmallCodeAddress;
131 E : section_info3.size = 0x1000;
132 E : section_info3.data_size = 0x1000;
133 E : layout_.sections.push_back(section_info3);
134 :
135 : // Insert blocks into the image layout.
136 E : layout_.blocks.InsertBlock(section_info1.addr, block1_);
137 E : layout_.blocks.InsertBlock(section_info2.addr, block2_);
138 E : layout_.blocks.InsertBlock(section_info2.addr + block2_->size(), block3_);
139 E : layout_.blocks.InsertBlock(section_info3.addr, block_code_);
140 :
141 E : block_code_->SetData(kSmallCode, sizeof(kSmallCode));
142 E : }
143 :
144 E : void PopulateFrequencies(IndexedFrequencyMap* frequencies) {
145 : // Insert frequency for block 1.
146 E : const RelativeAddress kBlock1Address = RelativeAddress(0x1000);
147 E : (*frequencies)[std::make_pair(kBlock1Address, kEntryCountColumn)] =
148 : kBlock1Count;
149 :
150 : // Insert frequency for block 2 (inner basic block at block + 2).
151 E : const RelativeAddress kBlock2Address = RelativeAddress(0x2000);
152 E : (*frequencies)[std::make_pair(kBlock2Address, kEntryCountColumn)] =
153 : kBlock2Count;
154 :
155 E : const RelativeAddress kBlock2AddressBB = RelativeAddress(0x2000 + 2);
156 E : (*frequencies)[std::make_pair(kBlock2AddressBB, kEntryCountColumn)] =
157 : kBlock2BodyCount;
158 E : }
159 :
160 E : void PopulateSubgraphFrequencies(IndexedFrequencyMap* frequencies) {
161 : // Insert frequencies for SmallCode.
162 : const RelativeAddress kBlockAddress0 =
163 E : RelativeAddress(kSmallCodeAddress + kBasicBlockOffset0);
164 : const RelativeAddress kBlockAddress1 =
165 E : RelativeAddress(kSmallCodeAddress + kBasicBlockOffset1);
166 : const RelativeAddress kBlockAddress2 =
167 E : RelativeAddress(kSmallCodeAddress + kBasicBlockOffset2);
168 :
169 E : (*frequencies)[std::make_pair(kBlockAddress0, kEntryCountColumn)] =
170 : kBasicBlockCount0;
171 E : (*frequencies)[std::make_pair(kBlockAddress1, kEntryCountColumn)] =
172 : kBasicBlockCount1;
173 E : (*frequencies)[std::make_pair(kBlockAddress2, kEntryCountColumn)] =
174 : kBasicBlockCount2;
175 :
176 E : (*frequencies)[std::make_pair(kBlockAddress0, kTakenCountColumn)] =
177 : kBasicBlockCount2;
178 :
179 E : (*frequencies)[std::make_pair(kBlockAddress0, kMissPredictedColumn)] =
180 : kBasicBlockCount2;
181 E : }
182 :
183 : BlockGraph block_graph_;
184 : ImageLayout layout_;
185 : BlockGraph::Block* block1_;
186 : BlockGraph::Block* block2_;
187 : BlockGraph::Block* block3_;
188 : BlockGraph::Block* block_code_;
189 : };
190 :
191 : } // namespace
192 :
193 E : TEST(BlockProfileTest, Constructor) {
194 E : ApplicationProfile::BlockProfile profile(0, 0);
195 E : EXPECT_EQ(0U, profile.count());
196 E : EXPECT_EQ(0, profile.temperature());
197 E : EXPECT_EQ(0, profile.percentile());
198 E : }
199 :
200 E : TEST(BlockProfileTest, ConstructorWithValues) {
201 E : ApplicationProfile::BlockProfile profile(12, 42);
202 E : EXPECT_EQ(12U, profile.count());
203 E : EXPECT_EQ(42, profile.temperature());
204 :
205 E : EXPECT_EQ(0, profile.percentile());
206 E : profile.set_percentile(0.05);
207 E : EXPECT_EQ(0.05, profile.percentile());
208 E : }
209 :
210 E : TEST_F(ApplicationProfileTest, DefaultConstructor) {
211 E : TestAplicationProfile app(&layout_);
212 :
213 E : EXPECT_TRUE(app.frequencies_.empty());
214 E : EXPECT_EQ(&layout_, app.image_layout_);
215 E : EXPECT_EQ(0, app.global_temperature_);
216 E : EXPECT_TRUE(app.profiles_.empty());
217 E : }
218 :
219 E : TEST_F(ApplicationProfileTest, BuildApplicationProfile) {
220 E : TestAplicationProfile app(&layout_);
221 E : IndexedFrequencyMap frequencies;
222 E : ASSERT_NO_FATAL_FAILURE(PopulateLayout());
223 E : ASSERT_NO_FATAL_FAILURE(PopulateFrequencies(&frequencies));
224 E : ASSERT_TRUE(app.ImportFrequencies(frequencies));
225 E : ASSERT_TRUE(app.ComputeGlobalProfile());
226 :
227 : // Check the global temperature.
228 E : EXPECT_THAT(frequencies, ContainerEq(app.frequencies_));
229 E : EXPECT_EQ(static_cast<double>(kBlock1Count + kBlock2Count + kBlock2BodyCount),
230 E : app.global_temperature());
231 :
232 : // Retrieve and check block profile.
233 E : const BlockProfile* profile1 = app.GetBlockProfile(block1_);
234 E : const BlockProfile* profile2 = app.GetBlockProfile(block2_);
235 E : const BlockProfile* profile3 = app.GetBlockProfile(block3_);
236 :
237 E : ASSERT_NE(reinterpret_cast<const BlockProfile*>(NULL), profile1);
238 E : ASSERT_NE(reinterpret_cast<const BlockProfile*>(NULL), profile2);
239 E : ASSERT_NE(reinterpret_cast<const BlockProfile*>(NULL), profile3);
240 :
241 E : EXPECT_EQ(kBlock1Count, profile1->count());
242 E : EXPECT_EQ(kBlock2Count, profile2->count());
243 :
244 E : EXPECT_EQ(kBlock1Count, profile1->temperature());
245 E : EXPECT_EQ(kBlock2Count + kBlock2BodyCount, profile2->temperature());
246 :
247 E : EXPECT_LT(0.90, profile1->percentile());
248 E : EXPECT_GT(0.10, profile2->percentile());
249 :
250 E : EXPECT_EQ(app.empty_profile_.get(), profile3);
251 E : EXPECT_EQ(1.0, app.empty_profile_->percentile());
252 E : }
253 :
254 E : TEST_F(ApplicationProfileTest, ComputeSubGraphProfile) {
255 : // Build global profile.
256 E : TestAplicationProfile app(&layout_);
257 E : IndexedFrequencyMap frequencies;
258 E : ASSERT_NO_FATAL_FAILURE(PopulateLayout());
259 E : ASSERT_NO_FATAL_FAILURE(PopulateSubgraphFrequencies(&frequencies));
260 E : ASSERT_TRUE(app.ImportFrequencies(frequencies));
261 E : ASSERT_TRUE(app.ComputeGlobalProfile());
262 :
263 : // Decompose to subgraph.
264 E : BasicBlockSubGraph subgraph;
265 E : BasicBlockDecomposer decomposer(block_code_, &subgraph);
266 E : ASSERT_TRUE(decomposer.Decompose());
267 :
268 : // Build subgraph profile.
269 E : std::unique_ptr<SubGraphProfile> subgraph_profile;
270 E : ASSERT_NO_FATAL_FAILURE(
271 E : app.ComputeSubGraphProfile(&subgraph, &subgraph_profile));
272 :
273 : // Retrieve Basic Blocks.
274 E : ASSERT_EQ(1U, subgraph.block_descriptions().size());
275 E : const BasicBlockSubGraph::BasicBlockOrdering& original_order =
276 : subgraph.block_descriptions().front().basic_block_order;
277 E : ASSERT_EQ(4U, original_order.size());
278 : BasicBlockSubGraph::BasicBlockOrdering::const_iterator it =
279 E : original_order.begin();
280 E : BasicCodeBlock* bb0 = BasicCodeBlock::Cast(*it);
281 E : ++it;
282 E : BasicCodeBlock* bb1 = BasicCodeBlock::Cast(*it);
283 E : ++it;
284 E : BasicCodeBlock* bb2 = BasicCodeBlock::Cast(*it);
285 E : ++it;
286 E : BasicEndBlock* bb3 = BasicEndBlock::Cast(*it);
287 :
288 E : ASSERT_NE(reinterpret_cast<BasicCodeBlock*>(NULL), bb0);
289 E : ASSERT_NE(reinterpret_cast<BasicCodeBlock*>(NULL), bb1);
290 E : ASSERT_NE(reinterpret_cast<BasicCodeBlock*>(NULL), bb2);
291 E : ASSERT_NE(reinterpret_cast<BasicEndBlock*>(NULL), bb3);
292 :
293 E : ASSERT_EQ(kBasicBlockOffset0, bb0->offset());
294 E : ASSERT_EQ(kBasicBlockOffset1, bb1->offset());
295 E : ASSERT_EQ(kBasicBlockOffset2, bb2->offset());
296 E : ASSERT_EQ(block_code_->size(), bb3->offset());
297 :
298 : // Retrieve basic block profiles.
299 : const BasicBlockProfile* profile0 =
300 E : subgraph_profile->GetBasicBlockProfile(bb0);
301 : const BasicBlockProfile* profile1 =
302 E : subgraph_profile->GetBasicBlockProfile(bb1);
303 : const BasicBlockProfile* profile2 =
304 E : subgraph_profile->GetBasicBlockProfile(bb2);
305 :
306 E : ASSERT_NE(reinterpret_cast<const BasicBlockProfile*>(NULL), profile0);
307 E : ASSERT_NE(reinterpret_cast<const BasicBlockProfile*>(NULL), profile1);
308 E : ASSERT_NE(reinterpret_cast<const BasicBlockProfile*>(NULL), profile2);
309 :
310 : // Validate basic block profiles.
311 E : EXPECT_EQ(100, profile0->count());
312 E : EXPECT_EQ(80, profile1->count());
313 E : EXPECT_EQ(20, profile2->count());
314 :
315 E : EXPECT_EQ(.20, profile0->GetMispredictedRatio());
316 E : EXPECT_EQ(0, profile1->GetMispredictedRatio());
317 E : EXPECT_EQ(0, profile2->GetMispredictedRatio());
318 :
319 E : EXPECT_EQ(0, profile0->GetSuccessorCount(bb0));
320 E : EXPECT_EQ(80, profile0->GetSuccessorCount(bb1));
321 E : EXPECT_EQ(20, profile0->GetSuccessorCount(bb2));
322 :
323 E : EXPECT_EQ(0, profile0->GetSuccessorRatio(bb0));
324 E : EXPECT_EQ(.80, profile0->GetSuccessorRatio(bb1));
325 E : EXPECT_EQ(.20, profile0->GetSuccessorRatio(bb2));
326 E : }
327 :
328 E : TEST_F(ApplicationProfileTest, RetrieveEmptySubGraphProfile) {
329 E : BasicBlockSubGraph subgraph;
330 E : SubGraphProfile profile;
331 E : BasicCodeBlock* bb = subgraph.AddBasicCodeBlock("bb");
332 E : const BasicBlockProfile* bb_profile = profile.GetBasicBlockProfile(bb);
333 :
334 E : EXPECT_NE(reinterpret_cast<const BasicBlockProfile*>(NULL), bb_profile);
335 E : EXPECT_EQ(0U, bb_profile->count());
336 E : }
337 :
338 : } // namespace optimize
|