1 : // Copyright 2012 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/reorder/basic_block_optimizer.h"
16 :
17 : #include "gmock/gmock.h"
18 : #include "gtest/gtest.h"
19 : #include "syzygy/block_graph/basic_block_test_util.h"
20 : #include "syzygy/block_graph/block_graph.h"
21 : #include "syzygy/core/unittest_util.h"
22 : #include "syzygy/pe/pe_utils.h"
23 : #include "syzygy/reorder/order_generator_test.h"
24 :
25 : #include "mnemonics.h" // NOLINT
26 :
27 : namespace reorder {
28 : namespace {
29 :
30 : using block_graph::BasicBlock;
31 : using block_graph::BasicCodeBlock;
32 : using block_graph::BasicDataBlock;
33 : using block_graph::BlockGraph;
34 : using core::RelativeAddress;
35 : using grinder::basic_block_util::EntryCountType;
36 : using grinder::basic_block_util::IndexedFrequencyInformation;
37 : using grinder::basic_block_util::IndexedFrequencyMap;
38 : using grinder::basic_block_util::LoadBasicBlockRanges;
39 : using grinder::basic_block_util::RelativeAddressRange;
40 : using grinder::basic_block_util::RelativeAddressRangeVector;
41 : using pe::ImageLayout;
42 : using testing::GetExeTestDataRelativePath;
43 :
44 : typedef Reorderer::Order Order;
45 :
46 : class TestBasicBlockOrderer : public BasicBlockOptimizer::BasicBlockOrderer {
47 : public:
48 : using BasicBlockOptimizer::BasicBlockOrderer::GetBasicBlockEntryCount;
49 : using BasicBlockOptimizer::BasicBlockOrderer::GetWarmestSuccessor;
50 : using BasicBlockOptimizer::BasicBlockOrderer::GetSortedJumpTargets;
51 : using BasicBlockOptimizer::BasicBlockOrderer::AddRecursiveDataReferences;
52 : using BasicBlockOptimizer::BasicBlockOrderer::AddWarmDataReferences;
53 :
54 : TestBasicBlockOrderer(
55 : const BasicBlockSubGraph& subgraph,
56 : const RelativeAddress& addr,
57 : Size size,
58 : const IndexedFrequencyInformation& entry_counts)
59 : : BasicBlockOptimizer::BasicBlockOrderer(
60 E : subgraph, addr, size, entry_counts) {
61 E : }
62 : };
63 :
64 : class BasicBlockOrdererTest : public testing::BasicBlockTest {
65 : public:
66 E : virtual void SetUp() OVERRIDE {
67 E : ASSERT_NO_FATAL_FAILURE(testing::BasicBlockTest::SetUp());
68 E : ASSERT_NO_FATAL_FAILURE(InitBlockGraph());
69 E : ASSERT_NO_FATAL_FAILURE(InitBasicBlockSubGraph());
70 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(0, 0, 0, 0, 0, 0, 0, 0));
71 : orderer_.reset(new TestBasicBlockOrderer(subgraph_,
72 : start_addr_,
73 : assembly_func_->size(),
74 E : entry_counts_));
75 E : ASSERT_TRUE(orderer_.get() != NULL);
76 E : }
77 :
78 : RelativeAddressRange MakeRange(BlockGraph::Offset offset,
79 : BlockGraph::Size size) {
80 : return RelativeAddressRange(start_addr_ + offset, size);
81 : }
82 :
83 E : BasicBlock* FindBasicBlockAt(BlockGraph::Offset offset) {
84 : typedef BasicBlockSubGraph::BBCollection BBCollection;
85 : BasicBlockSubGraph::BBCollection::iterator it =
86 E : subgraph_.basic_blocks().begin();
87 E : for (; it != subgraph_.basic_blocks().end(); ++it) {
88 E : if ((*it)->offset() == offset)
89 E : return *it;
90 E : }
91 i : return NULL;
92 E : }
93 :
94 : void SetEntryCounts(uint32 bb0, uint32 bb1, uint32 bb2, uint32 bb3,
95 E : uint32 bb4, uint32 bb5, uint32 bb6, uint32 bb7) {
96 E : entry_counts_.num_entries = kNumCodeBasicBlocks;
97 E : entry_counts_.num_columns = 1;
98 : entry_counts_.data_type =
99 E : ::common::IndexedFrequencyData::BASIC_BLOCK_ENTRY;
100 E : entry_counts_.frequency_size = 4;
101 :
102 E : IndexedFrequencyMap& frequency_map = entry_counts_.frequency_map;
103 E : frequency_map.clear();
104 :
105 E : uint32 start = start_addr_.value();
106 E : frequency_map[std::make_pair(start_addr_ + kBasicBlockOffsets[0], 0)] = bb0;
107 E : frequency_map[std::make_pair(start_addr_ + kBasicBlockOffsets[1], 0)] = bb1;
108 E : frequency_map[std::make_pair(start_addr_ + kBasicBlockOffsets[2], 0)] = bb2;
109 E : frequency_map[std::make_pair(start_addr_ + kBasicBlockOffsets[3], 0)] = bb3;
110 E : frequency_map[std::make_pair(start_addr_ + kBasicBlockOffsets[4], 0)] = bb4;
111 E : frequency_map[std::make_pair(start_addr_ + kBasicBlockOffsets[5], 0)] = bb5;
112 E : frequency_map[std::make_pair(start_addr_ + kBasicBlockOffsets[6], 0)] = bb6;
113 E : frequency_map[std::make_pair(start_addr_ + kBasicBlockOffsets[7], 0)] = bb7;
114 E : ASSERT_EQ(kNumCodeBasicBlocks, frequency_map.size());
115 E : }
116 :
117 : static const size_t kBasicBlockOffsets[kNumCodeBasicBlocks];
118 :
119 : IndexedFrequencyInformation entry_counts_;
120 : scoped_ptr<TestBasicBlockOrderer> orderer_;
121 : };
122 :
123 : const size_t BasicBlockOrdererTest::kBasicBlockOffsets[kNumCodeBasicBlocks] =
124 : { 0, 23, 24, 31, 36, 37, 42, 49 };
125 :
126 : class BasicBlockOptimizerTest : public testing::OrderGeneratorTest {
127 : public:
128 : typedef testing::OrderGeneratorTest Super;
129 :
130 : BasicBlockOptimizerTest()
131 : : num_decomposable_blocks_(0),
132 : num_non_decomposable_blocks_(0),
133 E : num_non_code_blocks_(0) {
134 E : }
135 :
136 E : virtual void SetUp() OVERRIDE {
137 E : ASSERT_NO_FATAL_FAILURE(Super::SetUp());
138 E : ASSERT_NO_FATAL_FAILURE(InitBlockCounts());
139 : base::FilePath pdb_path(GetExeTestDataRelativePath(
140 E : testing::kBBEntryInstrumentedTestDllPdbName));
141 E : }
142 :
143 E : void InitBlockCounts() {
144 E : ASSERT_EQ(0U, num_decomposable_blocks_);
145 E : ASSERT_EQ(0U, num_non_decomposable_blocks_);
146 E : ASSERT_EQ(0U, num_non_code_blocks_);
147 :
148 E : for (size_t i = 0; i < image_layout_.sections.size(); ++i) {
149 E : const ImageLayout::SectionInfo& section_info = image_layout_.sections[i];
150 : BlockGraph::AddressSpace::RangeMapConstIterPair ip =
151 : image_layout_.blocks.GetIntersectingBlocks(section_info.addr,
152 E : section_info.size);
153 E : for (; ip.first != ip.second; ++ip.first) {
154 E : const BlockGraph::Block* block = ip.first->second;
155 E : if (block->type() != BlockGraph::CODE_BLOCK) {
156 E : ++num_non_code_blocks_;
157 E : } else if (policy_.BlockIsSafeToBasicBlockDecompose(block)) {
158 E : ++num_decomposable_blocks_;
159 E : } else {
160 E : ++num_non_decomposable_blocks_;
161 : }
162 E : }
163 E : }
164 E : }
165 :
166 : bool FindBlockByName(const base::StringPiece& name,
167 : const BlockGraph::Block** block,
168 E : BlockGraph::AddressSpace::Range* range) {
169 E : DCHECK(block != NULL);
170 E : DCHECK(range != NULL);
171 : BlockGraph::AddressSpace::RangeMapConstIter it =
172 E : image_layout_.blocks.begin();
173 E : for (; it != image_layout_.blocks.end(); ++it) {
174 E : if (it->second->name() == name) {
175 E : *range = it->first;
176 E : *block = it->second;
177 E : return true;
178 : }
179 E : }
180 i : return false;
181 E : }
182 :
183 : protected:
184 : pe::PETransformPolicy policy_;
185 : BasicBlockOptimizer optimizer_;
186 : size_t num_decomposable_blocks_;
187 : size_t num_non_decomposable_blocks_;
188 : size_t num_non_code_blocks_;
189 : };
190 :
191 : } // namespace
192 :
193 E : TEST_F(BasicBlockOrdererTest, GetBlockEntryCount) {
194 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(1, 0, 1, 5, 1, 0, 0, 0));
195 E : EntryCountType entry_count = 0;
196 E : EXPECT_TRUE(orderer_->GetBlockEntryCount(&entry_count));
197 E : EXPECT_EQ(1U, entry_count);
198 :
199 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(17, 0, 1, 5, 1, 0, 0, 0));
200 E : EXPECT_TRUE(orderer_->GetBlockEntryCount(&entry_count));
201 E : EXPECT_EQ(17U, entry_count);
202 E : }
203 :
204 E : TEST_F(BasicBlockOrdererTest, GetWarmestSuccessor) {
205 E : const BasicCodeBlock* sub = BasicCodeBlock::Cast(FindBasicBlockAt(31));
206 E : ASSERT_TRUE(sub != NULL);
207 :
208 E : const BasicCodeBlock* ret = BasicCodeBlock::Cast(FindBasicBlockAt(36));
209 E : ASSERT_TRUE(ret != NULL);
210 :
211 E : TestBasicBlockOrderer::BasicBlockSet placed_bbs;
212 E : const BasicBlock* succ = NULL;
213 :
214 : // Make the fall-through as the warmest successor.
215 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(0, 0, 0, 5, 10, 0, 0, 0));
216 E : ASSERT_TRUE(orderer_->GetWarmestSuccessor(sub, placed_bbs, &succ));
217 E : ASSERT_EQ(ret, succ);
218 :
219 : // Make the branch taken as the warmest successor.
220 E : succ = NULL;
221 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(0, 0, 0, 10, 5, 0, 0, 0));
222 E : ASSERT_TRUE(orderer_->GetWarmestSuccessor(sub, placed_bbs, &succ));
223 E : ASSERT_EQ(sub, succ);
224 :
225 : // Give both branches the same warmth. Should preserve ordering.
226 E : succ = NULL;
227 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(0, 0, 0, 10, 10, 0, 0, 0));
228 E : ASSERT_TRUE(orderer_->GetWarmestSuccessor(sub, placed_bbs, &succ));
229 E : ASSERT_EQ(ret, succ);
230 :
231 : // Let the warmest branch already be placed, should return the other branch.
232 E : succ = NULL;
233 E : placed_bbs.insert(ret);
234 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(0, 0, 0, 5, 10, 0, 0, 0));
235 E : ASSERT_TRUE(orderer_->GetWarmestSuccessor(sub, placed_bbs, &succ));
236 E : ASSERT_EQ(sub, succ);
237 :
238 : // Let the warmest branch already be placed, should return the other branch.
239 : // Note that we initialize succ to non NULL to verify that it becomes NULL.
240 E : succ = sub;
241 E : placed_bbs.insert(sub);
242 E : placed_bbs.insert(ret);
243 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(0, 0, 0, 5, 10, 0, 0, 0));
244 E : ASSERT_TRUE(orderer_->GetWarmestSuccessor(sub, placed_bbs, &succ));
245 E : ASSERT_EQ(NULL, succ);
246 E : }
247 :
248 E : TEST_F(BasicBlockOrdererTest, AddWarmDataReferences) {
249 : // Get basic block pointers to the switch, jump table, and case table.
250 E : const BasicCodeBlock* code_bb = BasicCodeBlock::Cast(FindBasicBlockAt(0));
251 E : const BasicDataBlock* jump_table = BasicDataBlock::Cast(FindBasicBlockAt(52));
252 E : const BasicDataBlock* case_table = BasicDataBlock::Cast(FindBasicBlockAt(64));
253 E : ASSERT_TRUE(code_bb != NULL);
254 E : ASSERT_TRUE(jump_table != NULL);
255 E : ASSERT_TRUE(case_table != NULL);
256 :
257 : // Capture the references from the switch basic block (offset 0).
258 E : TestBasicBlockOrderer::BasicBlockSet references;
259 E : ASSERT_TRUE(orderer_->AddWarmDataReferences(code_bb, &references));
260 E : EXPECT_EQ(2U, references.size());
261 E : EXPECT_EQ(1U, references.count(jump_table));
262 E : EXPECT_EQ(1U, references.count(case_table));
263 :
264 : // Capture the references from the case_0 basic block (offset 24).
265 E : references.clear();
266 E : code_bb = BasicCodeBlock::Cast(FindBasicBlockAt(24));
267 E : ASSERT_TRUE(orderer_->AddWarmDataReferences(code_bb, &references));
268 E : EXPECT_TRUE(references.empty());
269 E : }
270 :
271 E : TEST_F(BasicBlockOrdererTest, GetSortedJumpTargets) {
272 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(0, 0, 2, 0, 0, 1, 3, 0));
273 E : const BasicCodeBlock* first_bb = BasicCodeBlock::Cast(FindBasicBlockAt(0));
274 E : ASSERT_TRUE(first_bb->successors().empty());
275 E : ASSERT_TRUE(!first_bb->instructions().empty());
276 E : const block_graph::Instruction& jmp_inst = first_bb->instructions().back();
277 E : ASSERT_EQ(I_JMP, jmp_inst.representation().opcode);
278 E : logging::SetMinLogLevel(-1);
279 E : std::vector<const BasicCodeBlock*> targets;
280 E : ASSERT_TRUE(orderer_->GetSortedJumpTargets(jmp_inst, &targets));
281 : ASSERT_THAT(targets,
282 : testing::ElementsAre(
283 : BasicCodeBlock::Cast(FindBasicBlockAt(42)),
284 : BasicCodeBlock::Cast(FindBasicBlockAt(24)),
285 E : BasicCodeBlock::Cast(FindBasicBlockAt(37))));
286 E : }
287 :
288 E : TEST_F(BasicBlockOrdererTest, GetStableSortedJumpTargets) {
289 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(0, 0, 1, 0, 0, 2, 1, 0));
290 E : const BasicCodeBlock* first_bb = BasicCodeBlock::Cast(FindBasicBlockAt(0));
291 E : ASSERT_TRUE(first_bb->successors().empty());
292 E : ASSERT_TRUE(!first_bb->instructions().empty());
293 E : const block_graph::Instruction& jmp_inst = first_bb->instructions().back();
294 E : ASSERT_EQ(I_JMP, jmp_inst.representation().opcode);
295 E : logging::SetMinLogLevel(-1);
296 E : std::vector<const BasicCodeBlock*> targets;
297 E : ASSERT_TRUE(orderer_->GetSortedJumpTargets(jmp_inst, &targets));
298 : ASSERT_THAT(targets,
299 : testing::ElementsAre(
300 : BasicCodeBlock::Cast(FindBasicBlockAt(37)),
301 : BasicCodeBlock::Cast(FindBasicBlockAt(24)),
302 E : BasicCodeBlock::Cast(FindBasicBlockAt(42))));
303 E : }
304 :
305 E : TEST_F(BasicBlockOrdererTest, HotColdSeparation) {
306 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(1, 0, 1, 5, 1, 0, 0, 0));
307 E : Order::OffsetVector warm;
308 E : Order::OffsetVector cold;
309 E : ASSERT_TRUE(orderer_->GetBasicBlockOrderings(&warm, &cold));
310 : // Note that the bb's at 52 and 64 are the jump and case tables, respectively.
311 E : EXPECT_THAT(warm, testing::ElementsAre(0, 24, 31, 36, 52, 64));
312 E : EXPECT_THAT(cold, testing::ElementsAre(23, 37, 42, 49));
313 E : }
314 :
315 E : TEST_F(BasicBlockOrdererTest, PathStraightening) {
316 : // The default control flow of the block we construct isn't very interesting
317 : // from a path straightening perspective. So, we modify it here such that the
318 : // jnz instruction the end of the basic block at offset 31 branches to case_1
319 : // (at offset 37), and then give that basic-block an elevated entry count.
320 E : BasicCodeBlock* case_1 = BasicCodeBlock::Cast(FindBasicBlockAt(37));
321 E : ASSERT_TRUE(case_1 != NULL);
322 E : ASSERT_EQ(1U, case_1->instructions().size());
323 E : ASSERT_EQ(I_CALL, case_1->instructions().front().representation().opcode);
324 :
325 E : BasicCodeBlock* jnz_bb = BasicCodeBlock::Cast(FindBasicBlockAt(31));
326 E : ASSERT_TRUE(jnz_bb != NULL);
327 E : ASSERT_EQ(1U, jnz_bb->instructions().size());
328 E : ASSERT_EQ(I_SUB, jnz_bb->instructions().front().representation().opcode);
329 E : ASSERT_EQ(2U, jnz_bb->successors().size());
330 : ASSERT_EQ(block_graph::Successor::kConditionNotEqual,
331 E : jnz_bb->successors().front().condition());
332 : jnz_bb->successors().front().set_reference(
333 E : block_graph::BasicBlockReference(BlockGraph::PC_RELATIVE_REF, 1, case_1));
334 :
335 : // Setup the entry counts such that the jump table stays in the same order
336 : // but case 1 is promoted to follow the jnz basic block.
337 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(1, 0, 10, 5, 1, 7, 0, 0));
338 E : Order::OffsetVector warm;
339 E : Order::OffsetVector cold;
340 E : ASSERT_TRUE(orderer_->GetBasicBlockOrderings(&warm, &cold));
341 : // Note that the bb's at 52 and 64 are the jump and case tables, respectively.
342 E : EXPECT_THAT(warm, testing::ElementsAre(0, 24, 31, 37, 36, 52, 64));
343 E : EXPECT_THAT(cold, testing::ElementsAre(42, 23, 49));
344 E : }
345 :
346 E : TEST_F(BasicBlockOrdererTest, PathStraighteningAcrossJumpTable) {
347 : // Setup the entry counts such that case 1 (at offset 37) is promoted to be
348 : // the warmest path through the jump table.
349 E : ASSERT_NO_FATAL_FAILURE(SetEntryCounts(1, 0, 1, 5, 1, 7, 0, 0));
350 E : Order::OffsetVector warm;
351 E : Order::OffsetVector cold;
352 E : ASSERT_TRUE(orderer_->GetBasicBlockOrderings(&warm, &cold));
353 : // Note that the bb's at 52 and 64 are the jump and case tables, respectively.
354 E : EXPECT_THAT(warm, testing::ElementsAre(0, 37, 24, 31, 36, 52, 64));
355 E : EXPECT_THAT(cold, testing::ElementsAre(42, 23, 49));
356 E : }
357 :
358 E : TEST_F(BasicBlockOptimizerTest, Accessors) {
359 E : const std::string kSectionName(".froboz");
360 E : EXPECT_TRUE(!optimizer_.cold_section_name().empty());
361 E : EXPECT_NE(kSectionName, optimizer_.cold_section_name());
362 E : optimizer_.set_cold_section_name(kSectionName);
363 E : EXPECT_EQ(kSectionName, optimizer_.cold_section_name());
364 E : }
365 :
366 E : TEST_F(BasicBlockOptimizerTest, EmptyOrderingAllCold) {
367 E : Order order;
368 E : IndexedFrequencyInformation entry_counts;
369 E : entry_counts.num_entries = 0;
370 E : entry_counts.num_columns = 1;
371 E : entry_counts.data_type = ::common::IndexedFrequencyData::BASIC_BLOCK_ENTRY;
372 E : entry_counts.frequency_size = 4;
373 :
374 : ASSERT_TRUE(
375 E : optimizer_.Optimize(image_layout_, entry_counts, &order));
376 :
377 E : EXPECT_EQ(image_layout_.sections.size() + 1, order.sections.size());
378 E : EXPECT_EQ(optimizer_.cold_section_name(), order.sections.back().name);
379 E : EXPECT_EQ(Order::SectionSpec::kNewSectionId, order.sections.back().id);
380 E : EXPECT_EQ(pe::kCodeCharacteristics, order.sections.back().characteristics);
381 :
382 : // Count the blocks left in the original sections. This should only include
383 : // non-code blocks.
384 E : size_t num_non_code_blocks = 0;
385 E : size_t num_non_decomposable_blocks = 0;
386 E : for (size_t i = 0; i < image_layout_.sections.size(); ++i) {
387 E : for (size_t k = 0; k < order.sections[i].blocks.size(); ++k) {
388 E : const BlockGraph::Block* block = order.sections[i].blocks[k].block;
389 E : ASSERT_TRUE(block != NULL);
390 E : ASSERT_NE(BlockGraph::CODE_BLOCK, block->type());
391 E : ++num_non_code_blocks;
392 E : }
393 E : }
394 :
395 : // Validate that we have the expected numbers of blocks.
396 E : EXPECT_EQ(num_non_code_blocks_, num_non_code_blocks);
397 : EXPECT_EQ(num_decomposable_blocks_ + num_non_decomposable_blocks_,
398 E : order.sections.back().blocks.size());
399 E : for (size_t i = 0; i < order.sections.back().blocks.size(); ++i) {
400 E : EXPECT_TRUE(order.sections.back().blocks[i].basic_block_offsets.empty());
401 E : }
402 E : }
403 :
404 E : TEST_F(BasicBlockOptimizerTest, HotCold) {
405 : // This test does a simple manipulation of the entry counts for DllMain and
406 : // validates that some minimum number of its blocks get moved into the cold
407 : // section. We defer to the BasicBlockOrdererTest instances above for the
408 : // details Hot/Cold and Path Straightening tests.
409 E : const BlockGraph::Block* dllmain = NULL;
410 E : BlockGraph::AddressSpace::Range range;
411 E : ASSERT_TRUE(FindBlockByName("DllMain", &dllmain, &range));
412 E : ASSERT_TRUE(dllmain != NULL);
413 :
414 : using block_graph::BasicBlockSubGraph;
415 : using block_graph::BasicBlockDecomposer;
416 :
417 E : BasicBlockSubGraph subgraph;
418 E : BasicBlockDecomposer decomposer(dllmain, &subgraph);
419 E : ASSERT_TRUE(decomposer.Decompose());
420 E : ASSERT_EQ(1U, subgraph.block_descriptions().size());
421 :
422 : // Generate an entry count map with a non-zero count for every other BB.
423 E : IndexedFrequencyInformation entry_counts;
424 E : entry_counts.num_entries = 0;
425 E : entry_counts.num_columns = 1;
426 E : entry_counts.data_type = ::common::IndexedFrequencyData::BASIC_BLOCK_ENTRY;
427 E : entry_counts.frequency_size = 4;
428 E : IndexedFrequencyMap& frequency_map = entry_counts.frequency_map;
429 :
430 : const BasicBlockSubGraph::BlockDescription& desc =
431 E : subgraph.block_descriptions().front();
432 : BasicBlockSubGraph::BasicBlockOrdering::const_iterator it(
433 E : desc.basic_block_order.begin());
434 E : size_t num_basic_blocks = desc.basic_block_order.size();
435 E : size_t num_hot_blocks = 0;
436 :
437 E : bool is_hot = true;
438 E : BlockGraph::RelativeAddress start_offs = subgraph.original_block()->addr();
439 E : for (; it != desc.basic_block_order.end(); ++it) {
440 E : if (is_hot && BasicCodeBlock::Cast(*it) != NULL) {
441 E : frequency_map[std::make_pair(start_offs + (*it)->offset(), 0)] = 1;
442 E : ++num_hot_blocks;
443 : }
444 :
445 : // Toggle hotness for next block.
446 E : is_hot = !is_hot;
447 E : }
448 :
449 : // Create an ordering that moves dllmain to a new section.
450 E : std::string section_name(".dllmain");
451 E : Order order;
452 E : order.sections.resize(1);
453 E : order.sections[0].id = Order::SectionSpec::kNewSectionId;
454 E : order.sections[0].name = section_name;
455 E : order.sections[0].characteristics = pe::kCodeCharacteristics;
456 E : order.sections[0].blocks.push_back(Order::BlockSpec(dllmain));
457 :
458 : ASSERT_TRUE(
459 E : optimizer_.Optimize(image_layout_, entry_counts, &order));
460 :
461 E : ASSERT_EQ(image_layout_.sections.size() + 2, order.sections.size());
462 E : ASSERT_EQ(section_name, order.sections[0].name);
463 E : ASSERT_EQ(1U, order.sections[0].blocks.size());
464 E : ASSERT_TRUE(!order.sections.back().blocks.empty());
465 E : ASSERT_EQ(dllmain, order.sections[0].blocks[0].block);
466 E : ASSERT_EQ(dllmain, order.sections.back().blocks[0].block);
467 : ASSERT_LE(num_hot_blocks,
468 E : order.sections[0].blocks[0].basic_block_offsets.size());
469 :
470 : // Since data BBs that are referred to by 'hot' code BBs also make
471 : // it into the hot BB list, there could be fewer cold blocks than expected.
472 : ASSERT_GE(num_basic_blocks - num_hot_blocks,
473 E : order.sections.back().blocks[0].basic_block_offsets.size());
474 E : }
475 :
476 : } // namespace reorder
|