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