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/transforms/basic_block_reordering_transform.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/block_builder.h"
21 : #include "syzygy/block_graph/block_graph.h"
22 : #include "syzygy/pe/pe_transform_policy.h"
23 :
24 : namespace optimize {
25 : namespace transforms {
26 :
27 : namespace {
28 :
29 : using block_graph::BasicBlock;
30 : using block_graph::BasicBlockDecomposer;
31 : using block_graph::BasicBlockReference;
32 : using block_graph::BasicBlockSubGraph;
33 : using block_graph::BasicCodeBlock;
34 : using block_graph::BlockBuilder;
35 : using block_graph::BlockGraph;
36 : using block_graph::Successor;
37 : using pe::ImageLayout;
38 : using testing::ElementsAre;
39 : using testing::ElementsAreArray;
40 :
41 : typedef block_graph::analysis::ControlFlowAnalysis::BasicBlockOrdering
42 : BasicBlockOrdering;
43 : typedef grinder::basic_block_util::EntryCountType EntryCountType;
44 :
45 : // _asm je here
46 : // _asm xor eax, eax
47 : // here:
48 : // _asm ret
49 : const uint8 kCodeJump[] = { 0x74, 0x02, 0x33, 0xC0, 0xC3 };
50 :
51 : // _asm jne here
52 : // leave:
53 : // _asm ret
54 : // here:
55 : // _asm xor eax, eax
56 : // _asm jmp leave
57 : const uint8 kCodeJumpInv[] = { 0x75, 0x01, 0xC3, 0x33, 0xC0, 0xEB, 0xFB };
58 :
59 : const EntryCountType kRunMoreThanOnce = 100;
60 : const EntryCountType kHot = 100;
61 :
62 : class TestApplicationProfile : public ApplicationProfile {
63 : public:
64 E : explicit TestApplicationProfile(const ImageLayout* image_layout)
65 : : ApplicationProfile(image_layout) {
66 E : }
67 :
68 : using ApplicationProfile::profiles_;
69 : };
70 :
71 : class TestSubGraphProfile : public SubGraphProfile {
72 : public:
73 : using SubGraphProfile::basic_blocks_;
74 : };
75 :
76 : class TestBasicBlockProfile : public SubGraphProfile::BasicBlockProfile {
77 : public:
78 : using SubGraphProfile::BasicBlockProfile::count_;
79 : using SubGraphProfile::BasicBlockProfile::mispredicted_;
80 : using SubGraphProfile::BasicBlockProfile::successors_;
81 :
82 E : TestBasicBlockProfile(EntryCountType count,
83 : EntryCountType mispredicted,
84 : EntryCountType taken) {
85 E : count_ = count;
86 E : mispredicted_ = mispredicted;
87 E : taken_ = taken;
88 E : }
89 :
90 : EntryCountType taken_;
91 : };
92 :
93 : class TestBasicBlockReorderingTransform : public BasicBlockReorderingTransform {
94 : public:
95 : using BasicBlockReorderingTransform::EvaluateCost;
96 : using BasicBlockReorderingTransform::CommitOrdering;
97 : using BasicBlockReorderingTransform::FlattenStructuralTreeToAnOrder;
98 : };
99 :
100 : class BasicBlockReorderingTransformTest : public testing::Test {
101 : public:
102 : BasicBlockReorderingTransformTest()
103 : : image_(&block_graph_),
104 E : profile_(&image_) {
105 E : }
106 :
107 : void SetUp() override;
108 : void ApplyTransform(BlockGraph::Block** block);
109 : void ApplyTransform(BlockGraph::Block** block,
110 : TestBasicBlockProfile* bb_profiles,
111 : size_t bb_profiles_length);
112 : protected:
113 : pe::PETransformPolicy policy_;
114 : BlockGraph block_graph_;
115 : BasicBlockSubGraph subgraph_;
116 : ImageLayout image_;
117 : BasicBlockReorderingTransform tx_;
118 : TestApplicationProfile profile_;
119 : TestSubGraphProfile subgraph_profile_;
120 : BasicCodeBlock* b1_;
121 : BasicCodeBlock* b2_;
122 : BasicCodeBlock* b3_;
123 : BasicCodeBlock* b4_;
124 : BasicCodeBlock* b5_;
125 : };
126 :
127 : void AddSuccessorBetween(
128 : Successor::Condition condition,
129 : BasicCodeBlock* from,
130 E : BasicCodeBlock* to) {
131 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), from);
132 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), to);
133 E : DCHECK_LT(from->successors().size(), 2U);
134 :
135 : from->successors().push_back(
136 : Successor(condition,
137 : BasicBlockReference(BlockGraph::RELATIVE_REF,
138 : BlockGraph::Reference::kMaximumSize,
139 : to),
140 E : 0));
141 E : }
142 :
143 : void Connect1(BasicCodeBlock* from,
144 : BasicCodeBlock* to,
145 : size_t to_count,
146 E : TestBasicBlockProfile* profile) {
147 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), from);
148 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), to);
149 E : DCHECK_NE(reinterpret_cast<TestBasicBlockProfile*>(NULL), profile);
150 E : DCHECK_LT(from->successors().size(), 1U);
151 :
152 E : AddSuccessorBetween(Successor::kConditionTrue, from, to);
153 :
154 E : profile->successors_[to] = to_count;
155 E : }
156 :
157 : void Connect2(BasicCodeBlock* from,
158 : BasicCodeBlock* to1,
159 : BasicCodeBlock* to2,
160 : size_t to1_count,
161 : size_t to2_count,
162 E : TestBasicBlockProfile* profile) {
163 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), from);
164 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), to1);
165 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), to2);
166 E : DCHECK_LT(from->successors().size(), 1U);
167 :
168 E : AddSuccessorBetween(Successor::kConditionEqual, from, to1);
169 E : AddSuccessorBetween(Successor::kConditionNotEqual, from, to2);
170 :
171 E : profile->successors_[to1] = to1_count;
172 E : profile->successors_[to2] = to2_count;
173 E : }
174 :
175 E : void BasicBlockReorderingTransformTest::SetUp() {
176 : // The control flow graph and frequencies built.
177 : //
178 : // /------\
179 : // (b1 [10]) |
180 : // / \ |
181 : // (b2 [4]) (b3 [6]) |
182 : // \ / |
183 : // (b4 [10])------/
184 : // |
185 : // (b5 [1])
186 :
187 E : b1_ = subgraph_.AddBasicCodeBlock("b1");
188 E : b2_ = subgraph_.AddBasicCodeBlock("b2");
189 E : b3_ = subgraph_.AddBasicCodeBlock("b3");
190 E : b4_ = subgraph_.AddBasicCodeBlock("b4");
191 E : b5_ = subgraph_.AddBasicCodeBlock("b5");
192 :
193 E : ASSERT_NE(reinterpret_cast<BasicCodeBlock*>(NULL), b1_);
194 E : ASSERT_NE(reinterpret_cast<BasicCodeBlock*>(NULL), b2_);
195 E : ASSERT_NE(reinterpret_cast<BasicCodeBlock*>(NULL), b3_);
196 E : ASSERT_NE(reinterpret_cast<BasicCodeBlock*>(NULL), b4_);
197 E : ASSERT_NE(reinterpret_cast<BasicCodeBlock*>(NULL), b5_);
198 :
199 E : TestBasicBlockProfile profile_b1(10, 0, 6);
200 E : TestBasicBlockProfile profile_b2(4, 0, 4);
201 E : TestBasicBlockProfile profile_b3(6, 0, 6);
202 E : TestBasicBlockProfile profile_b4(10, 0, 9);
203 E : TestBasicBlockProfile profile_b5(1, 0, 1);
204 :
205 E : Connect2(b1_, b2_, b3_, 4, 6, &profile_b1);
206 E : Connect1(b2_, b4_, 4, &profile_b2);
207 E : Connect1(b3_, b4_, 6, &profile_b3);
208 E : Connect2(b4_, b1_, b5_, 9, 1, &profile_b4);
209 :
210 E : subgraph_profile_.basic_blocks_[b1_] = profile_b1;
211 E : subgraph_profile_.basic_blocks_[b2_] = profile_b2;
212 E : subgraph_profile_.basic_blocks_[b3_] = profile_b3;
213 E : subgraph_profile_.basic_blocks_[b4_] = profile_b4;
214 E : subgraph_profile_.basic_blocks_[b5_] = profile_b5;
215 :
216 : BasicBlockSubGraph::BlockDescription* description =
217 : subgraph_.AddBlockDescription(
218 E : "bb1", "test.obj", BlockGraph::CODE_BLOCK, 7, 2, 42);
219 E : description->basic_block_order.push_back(b1_);
220 E : description->basic_block_order.push_back(b5_);
221 E : description->basic_block_order.push_back(b4_);
222 E : description->basic_block_order.push_back(b3_);
223 E : description->basic_block_order.push_back(b2_);
224 E : }
225 :
226 : void BasicBlockReorderingTransformTest::ApplyTransform(
227 E : BlockGraph::Block** block) {
228 E : ApplyTransform(block, NULL, 0);
229 E : }
230 :
231 : // Apply a basic block reordering pass on |block| driven by the basic block
232 : // profiles received in |bb_profiles|.
233 : //
234 : // This method
235 : // - decomposes the block into a subgraph,
236 : // - populates a subgraph profile based on |bb_profiles|,
237 : // - applies the transform,
238 : // - rebuilds the block.
239 : //
240 : // The |bb_profiles| is an array of |bb_profiles_length| profiles which maps
241 : // one to one to the basic code blocks in the decomposed basic block.
242 : // The parameter |block| receives the rebuilt block.
243 : void BasicBlockReorderingTransformTest::ApplyTransform(
244 : BlockGraph::Block** block,
245 : TestBasicBlockProfile* bb_profiles,
246 E : size_t bb_profiles_length) {
247 : // Decompose to subgraph.
248 E : BasicBlockSubGraph subgraph;
249 E : BasicBlockDecomposer decomposer(*block, &subgraph);
250 E : ASSERT_TRUE(decomposer.Decompose());
251 :
252 : // Apply the requested basic block profiles.
253 E : if (bb_profiles != NULL) {
254 : // Retrieve the original ordering of this subgraph.
255 : BasicBlockSubGraph::BlockDescriptionList& descriptions =
256 E : subgraph.block_descriptions();
257 E : DCHECK_EQ(1U, descriptions.size());
258 : BasicBlockSubGraph::BasicBlockOrdering& order =
259 E : descriptions.begin()->basic_block_order;
260 :
261 : // There's no profile for the trailing end-block.
262 E : DCHECK_EQ(subgraph.basic_blocks().size(), bb_profiles_length + 1);
263 E : DCHECK_EQ(order.size(), bb_profiles_length + 1);
264 :
265 : // Commit the basic block profiles in the subgraph profile.
266 E : size_t i = 0;
267 E : BasicBlockSubGraph::BasicBlockOrdering::iterator bb = order.begin();
268 E : for (; i < bb_profiles_length && bb != order.end(); ++i, ++bb) {
269 E : BasicCodeBlock* code = BasicCodeBlock::Cast(*bb);
270 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), code);
271 :
272 : // Commit successors profile in the subgraph profile.
273 E : const BasicBlock::Successors& successors = code->successors();
274 E : switch (successors.size()) {
275 : case 1: {
276 : BasicCodeBlock* succ = BasicCodeBlock::Cast(
277 E : successors.front().reference().basic_block());
278 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), succ);
279 E : bb_profiles[i].successors_[succ] = bb_profiles[i].taken_;
280 E : break;
281 : }
282 : case 2: {
283 : BasicCodeBlock* succ1 = BasicCodeBlock::Cast(
284 E : successors.front().reference().basic_block());
285 : BasicCodeBlock* succ2 = BasicCodeBlock::Cast(
286 E : successors.back().reference().basic_block());
287 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), succ1);
288 E : DCHECK_NE(reinterpret_cast<BasicCodeBlock*>(NULL), succ2);
289 :
290 : EntryCountType untaken =
291 E : bb_profiles[i].count_ - bb_profiles[i].taken_;
292 :
293 E : bb_profiles[i].successors_[succ1] = bb_profiles[i].taken_;
294 E : bb_profiles[i].successors_[succ2] = untaken;
295 : break;
296 : }
297 : }
298 :
299 E : subgraph_profile_.basic_blocks_[code] = bb_profiles[i];
300 E : }
301 : }
302 :
303 : // Apply block transform.
304 : ASSERT_TRUE(
305 : tx_.TransformBasicBlockSubGraph(&policy_, &block_graph_, &subgraph,
306 E : &profile_, &subgraph_profile_));
307 :
308 : // Rebuild block.
309 E : BlockBuilder builder(&block_graph_);
310 E : ASSERT_TRUE(builder.Merge(&subgraph));
311 E : CHECK_EQ(1u, builder.new_blocks().size());
312 E : *block = *builder.new_blocks().begin();
313 E : }
314 :
315 : } // namespace
316 :
317 E : TEST_F(BasicBlockReorderingTransformTest, EvaluateSequentialCost) {
318 : // Validate a sequential ordering.
319 E : BasicBlockOrdering order;
320 E : order.push_back(b1_);
321 E : order.push_back(b2_);
322 E : order.push_back(b3_);
323 E : order.push_back(b4_);
324 E : order.push_back(b5_);
325 E : uint64 expected_cost = 19;
326 : EXPECT_EQ(expected_cost,
327 : TestBasicBlockReorderingTransform::EvaluateCost(order,
328 E : subgraph_profile_));
329 E : }
330 :
331 E : TEST_F(BasicBlockReorderingTransformTest, EvaluateIfUnlikelyCost) {
332 : // Validate an unlikely-if ordering.
333 E : BasicBlockOrdering order;
334 E : order.push_back(b1_);
335 E : order.push_back(b3_);
336 E : order.push_back(b4_);
337 E : order.push_back(b5_);
338 E : order.push_back(b2_);
339 E : uint64 expected_cost = 17;
340 : EXPECT_EQ(expected_cost,
341 : TestBasicBlockReorderingTransform::EvaluateCost(order,
342 E : subgraph_profile_));
343 E : }
344 :
345 E : TEST_F(BasicBlockReorderingTransformTest, EvaluateBadOrderCost) {
346 : // Validate a really bad ordering.
347 E : BasicBlockOrdering order;
348 E : order.push_back(b1_);
349 E : order.push_back(b5_);
350 E : order.push_back(b4_);
351 E : order.push_back(b3_);
352 E : order.push_back(b2_);
353 E : uint64 expected_cost = 30;
354 : EXPECT_EQ(expected_cost,
355 : TestBasicBlockReorderingTransform::EvaluateCost(order,
356 E : subgraph_profile_));
357 E : }
358 :
359 E : TEST_F(BasicBlockReorderingTransformTest, CommitOrdering) {
360 : // Create an original order.
361 E : BasicBlockSubGraph::BasicBlockOrdering target;
362 E : target.push_back(b1_);
363 E : target.push_back(b2_);
364 E : target.push_back(b3_);
365 E : target.push_back(b4_);
366 E : target.push_back(b5_);
367 :
368 : // Create the requested order.
369 E : BasicBlockOrdering order;
370 E : order.push_back(b1_);
371 E : order.push_back(b5_);
372 E : order.push_back(b4_);
373 E : order.push_back(b3_);
374 E : order.push_back(b2_);
375 :
376 : // Commit the requested order.
377 : ASSERT_NO_FATAL_FAILURE(TestBasicBlockReorderingTransform::CommitOrdering(
378 E : order, NULL, &target));
379 :
380 E : EXPECT_EQ(5U, target.size());
381 E : EXPECT_THAT(target, ElementsAre(b1_, b5_, b4_, b3_, b2_));
382 E : }
383 :
384 E : TEST_F(BasicBlockReorderingTransformTest, FlattenStructuralTreeToAnOrder) {
385 : // Flatten to a structural tree and perform reordering for a block without
386 : // profile information.
387 E : TestSubGraphProfile subgraph_profile;
388 E : BasicBlockOrdering order;
389 : ASSERT_TRUE(
390 : TestBasicBlockReorderingTransform::FlattenStructuralTreeToAnOrder(
391 E : &subgraph_, &subgraph_profile_, &order));
392 :
393 E : EXPECT_EQ(5U, order.size());
394 E : EXPECT_THAT(order, ElementsAre(b1_, b2_, b3_, b4_, b5_));
395 E : }
396 :
397 E : TEST_F(BasicBlockReorderingTransformTest, ApplyTransformWithoutProfile) {
398 : BlockGraph::Block* block =
399 E : block_graph_.AddBlock(BlockGraph::CODE_BLOCK, sizeof(kCodeJump), "jump");
400 E : DCHECK_NE(reinterpret_cast<BlockGraph::Block*>(NULL), block);
401 E : block->SetData(kCodeJump, sizeof(kCodeJump));
402 :
403 E : ASSERT_NO_FATAL_FAILURE(ApplyTransform(&block));
404 :
405 : // This block has a profile been never run, thus it must be unchanged.
406 E : EXPECT_THAT(kCodeJump, ElementsAreArray(block->data(), block->size()));
407 E : }
408 :
409 E : TEST_F(BasicBlockReorderingTransformTest, ApplyTransformWithProfile) {
410 : BlockGraph::Block* block =
411 E : block_graph_.AddBlock(BlockGraph::CODE_BLOCK, sizeof(kCodeJump), "jump");
412 E : DCHECK_NE(reinterpret_cast<BlockGraph::Block*>(NULL), block);
413 E : block->SetData(kCodeJump, sizeof(kCodeJump));
414 :
415 : // Insert the block profile into the profile map.
416 E : ApplicationProfile::BlockProfile block_profile(kRunMoreThanOnce, kHot);
417 E : profile_.profiles_.insert(std::make_pair(block->id(), block_profile));
418 :
419 E : ASSERT_NO_FATAL_FAILURE(ApplyTransform(&block));
420 :
421 : // This block must be unchanged.
422 E : EXPECT_THAT(kCodeJump, ElementsAreArray(block->data(), block->size()));
423 E : }
424 :
425 E : TEST_F(BasicBlockReorderingTransformTest, ApplyTransformWithProfileAndGain) {
426 : BlockGraph::Block* block =
427 : block_graph_.AddBlock(BlockGraph::CODE_BLOCK,
428 : sizeof(kCodeJumpInv),
429 E : "jump");
430 E : DCHECK_NE(reinterpret_cast<BlockGraph::Block*>(NULL), block);
431 E : block->SetData(kCodeJumpInv, sizeof(kCodeJumpInv));
432 :
433 : // Insert the block profile into the profile map.
434 E : ApplicationProfile::BlockProfile block_profile(kRunMoreThanOnce, kHot);
435 E : profile_.profiles_.insert(std::make_pair(block->id(), block_profile));
436 :
437 : TestBasicBlockProfile bb_profiles[] = {
438 : TestBasicBlockProfile(kRunMoreThanOnce, kHot, kRunMoreThanOnce),
439 : TestBasicBlockProfile(kRunMoreThanOnce, kHot, kRunMoreThanOnce),
440 : TestBasicBlockProfile(kRunMoreThanOnce, kHot, kRunMoreThanOnce)
441 E : };
442 :
443 : ASSERT_NO_FATAL_FAILURE(
444 E : ApplyTransform(&block, bb_profiles, arraysize(bb_profiles)));
445 :
446 : // This block must be changed to a less expensive block.
447 E : EXPECT_THAT(kCodeJump, ElementsAreArray(block->data(), block->size()));
448 E : }
449 :
450 : } // namespace transforms
451 : } // namespace optimize
|