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