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 <algorithm>
18 : #include <deque>
19 : #include <set>
20 :
21 : #include "syzygy/block_graph/basic_block.h"
22 : #include "syzygy/block_graph/basic_block_decomposer.h"
23 : #include "syzygy/block_graph/basic_block_subgraph.h"
24 : #include "syzygy/pe/block_util.h"
25 : #include "syzygy/pe/find.h"
26 : #include "syzygy/pe/pe_utils.h"
27 :
28 : #include "mnemonics.h" // NOLINT
29 :
30 : namespace reorder {
31 :
32 : namespace {
33 :
34 : using block_graph::BlockGraph;
35 : using block_graph::ConstBlockVector;
36 : using block_graph::BasicBlock;
37 : using block_graph::BasicCodeBlock;
38 : using block_graph::BasicDataBlock;
39 : using block_graph::BasicBlockDecomposer;
40 : using block_graph::BasicBlockSubGraph;
41 : using block_graph::Successor;
42 : using grinder::basic_block_util::EntryCountMap;
43 : using grinder::basic_block_util::EntryCountType;
44 : using grinder::basic_block_util::EntryCountMap;
45 : using grinder::basic_block_util::InitModuleInfo;
46 : using grinder::basic_block_util::ModuleEntryCountMap;
47 : using grinder::basic_block_util::ModuleInformation;
48 : using grinder::basic_block_util::RelativeAddress;
49 : using grinder::basic_block_util::RelativeAddressRange;
50 : using grinder::basic_block_util::RelativeAddressRangeVector;
51 : using pe::PEFile;
52 : using pe::ImageLayout;
53 :
54 : typedef Reorderer::Order Order;
55 : typedef BlockGraph::Offset Offset;
56 : typedef BlockGraph::Size Size;
57 : typedef BlockGraph::AddressSpace::RangeMapConstIter RangeMapConstIter;
58 : typedef BlockGraph::AddressSpace::RangeMapConstIterPair RangeMapConstIterPair;
59 :
60 : const char kDefaultColdSectionName[] = ".ctext";
61 :
62 : // A helper to fill in (retaining relative ordering) any sections that are in
63 : // the original @p image_layout which are not mentioned in @p order.
64 : void PopulateMissingSections(
65 E : const ImageLayout& image_layout, Order* order) {
66 E : DCHECK(order != NULL);
67 :
68 : // Remember all of the sections mentioned by id.
69 E : std::set<BlockGraph::SectionId> mentioned;
70 E : for (size_t i = 0; i < order->sections.size(); ++i) {
71 E : if (order->sections[i].id != Order::SectionSpec::kNewSectionId) {
72 E : bool inserted = mentioned.insert(order->sections[i].id).second;
73 E : DCHECK(inserted);
74 : }
75 E : }
76 :
77 : // Iterate over all of the sections and append those not mentioned by ID.
78 E : for (BlockGraph::SectionId id = 0; id < image_layout.sections.size(); ++id) {
79 E : const ImageLayout::SectionInfo& info = image_layout.sections[id];
80 E : if (mentioned.count(id) == 0) {
81 E : order->sections.push_back(Order::SectionSpec());
82 E : order->sections.back().id = id;
83 E : order->sections.back().name = info.name;
84 E : order->sections.back().characteristics = info.characteristics;
85 : }
86 E : }
87 E : }
88 :
89 : // Initialize a collection of blocks which are explicitly mentioned by the
90 : // given @p order.
91 E : bool InitExplicitBlocks(const Order* order, ConstBlockVector* explicit_blocks) {
92 E : DCHECK(order != NULL);
93 E : DCHECK(explicit_blocks != NULL);
94 E : explicit_blocks->clear();
95 :
96 : // Put all of the explicitly referenced blocks into explicit_blocks.
97 E : for (size_t i = 0; i < order->sections.size(); ++i) {
98 E : const Order::SectionSpec& section = order->sections[i];
99 E : for (size_t k = 0; k < section.blocks.size(); ++k) {
100 E : if (!section.blocks[k].basic_block_offsets.empty()) {
101 i : LOG(ERROR) << "Expected a block-only ordering.";
102 i : return false;
103 : }
104 E : explicit_blocks->push_back(section.blocks[k].block);
105 E : }
106 E : }
107 :
108 : // If there are no explicit blocks then we are finished.
109 E : if (explicit_blocks->empty())
110 E : return true;
111 :
112 : // Sort the set of explicitly placed blocks. This lets us quickly check if
113 : // a block is in explicit_blocks using binary search.
114 E : std::sort(explicit_blocks->begin(), explicit_blocks->end());
115 :
116 : // Verify that no block has been mentioned more than once.
117 E : ConstBlockVector::const_iterator next_iter = explicit_blocks->begin();
118 E : ConstBlockVector::const_iterator end_iter = --explicit_blocks->end();
119 E : while (next_iter != end_iter) {
120 E : ConstBlockVector::const_iterator curr_iter = next_iter++;
121 E : if (*curr_iter == *next_iter) {
122 i : LOG(ERROR) << "Ordering references a block multiple times.";
123 i : return false;
124 : }
125 E : }
126 :
127 : // And we're done.
128 E : return true;
129 E : }
130 :
131 : // Check if @p block is in @p explicit_blocks.
132 : bool IsExplicitBlock(const ConstBlockVector& explicit_blocks,
133 E : const BlockGraph::Block* block) {
134 : return std::binary_search(explicit_blocks.begin(),
135 : explicit_blocks.end(),
136 E : block);
137 E : }
138 :
139 : // A helper to "cast" the given successor as a BasicCodeBlock.
140 E : const BasicCodeBlock* GetSuccessorBB(const Successor& successor) {
141 E : const BasicBlock* bb = successor.reference().basic_block();
142 :
143 : // This might be in inter block reference (i.e., refers to a block not
144 : // a basic-block).
145 E : if (bb == NULL)
146 E : return NULL;
147 :
148 : // If it's a basic-block then it must be a code basic-block.
149 E : const BasicCodeBlock* code_bb = BasicCodeBlock::Cast(bb);
150 E : DCHECK(code_bb != NULL);
151 E : return code_bb;
152 E : }
153 :
154 : typedef std::pair<EntryCountType, const BasicCodeBlock*> CountForBasicBlock;
155 :
156 : bool HasHigherEntryCount(const CountForBasicBlock& lhs,
157 E : const CountForBasicBlock& rhs) {
158 E : return lhs.first > rhs.first;
159 E : }
160 :
161 : bool GetEntryCountByOffset(const EntryCountMap& entry_counts,
162 : const RelativeAddress& base_rva,
163 : Offset offset,
164 E : EntryCountType* entry_count) {
165 E : DCHECK_LE(0, offset);
166 E : DCHECK(entry_count != NULL);
167 :
168 E : *entry_count = 0;
169 : EntryCountMap::const_iterator it(
170 E : entry_counts.find(base_rva.value() + offset));
171 E : if (it != entry_counts.end())
172 E : *entry_count = it->second;
173 E : return true;
174 E : }
175 :
176 : } // namespace
177 :
178 : BasicBlockOptimizer::BasicBlockOrderer::BasicBlockOrderer(
179 : const BasicBlockSubGraph& subgraph,
180 : const RelativeAddress& addr,
181 : Size size,
182 : const EntryCountMap& entry_counts)
183 : : subgraph_(subgraph),
184 : addr_(addr),
185 : size_(size),
186 E : entry_counts_(entry_counts) {
187 E : DCHECK_LT(0U, size);
188 E : }
189 :
190 : bool BasicBlockOptimizer::BasicBlockOrderer::GetBlockEntryCount(
191 E : EntryCountType* entry_count) const {
192 E : DCHECK(entry_count != NULL);
193 :
194 E : if (!GetEntryCountByOffset(entry_counts_, addr_, 0, entry_count))
195 i : return false;
196 :
197 E : return true;
198 E : }
199 :
200 : // TODO(rogerm): There are better longest path based orderings in the
201 : // literature, but they require more than just entry-count ordering.
202 : bool BasicBlockOptimizer::BasicBlockOrderer::GetBasicBlockOrderings(
203 : Order::OffsetVector* warm_basic_blocks,
204 E : Order::OffsetVector* cold_basic_blocks) const {
205 E : DCHECK(warm_basic_blocks != NULL);
206 E : DCHECK(cold_basic_blocks != NULL);
207 :
208 : // TODO(rogerm): Create weighted paths by entry-count following the successor
209 : // and predecessor links.
210 : //
211 : // Here's an outline for a potential improvement:
212 : // 1. Set the first bb aside.
213 : // 2. Find the bb with the largest entry_count, then expand out from
214 : // there by surrounding it with its largest predecessor and
215 : // successor. Continuing expanding on both ends until there are no
216 : // more successor/predecessor links to follow.
217 : // 3. If there are unplaced basic blocks, goto 2. This will create as
218 : // many chains as required to represent all of the bbs.
219 : // 4. The resulting ordering should be the first bb followed by each
220 : // path found above.
221 :
222 E : warm_basic_blocks->clear();
223 E : cold_basic_blocks->clear();
224 :
225 : // Place the basic-blocks in order such that each block is followed by its
226 : // successor having the greatest number of entries. We start with the bb
227 : // having offset 0.
228 E : DCHECK_EQ(1U, subgraph_.block_descriptions().size());
229 : const BasicBlockSubGraph::BasicBlockOrdering& original_order =
230 E : subgraph_.block_descriptions().front().basic_block_order;
231 :
232 : // Create a copy of the original ordering to serve as a queue. Henceforth
233 : // known as the BB Queue or bbq. Muahhahaha!
234 : std::deque<const BasicBlock*> bbq(original_order.begin(),
235 E : original_order.end());
236 E : DCHECK(!bbq.empty());
237 E : DCHECK_EQ(0, bbq.front()->offset());
238 :
239 : // The set of basic blocks that we have already placed. Warm basic blocks
240 : // may jump the queue if they were the most common successor of a previously
241 : // seen basic block.
242 E : BasicBlockSet placed_bbs;
243 :
244 : // The set of data basic-blocks referenced from an instruction in any
245 : // warm basic-block. This is used to determine where to place data blocks.
246 E : BasicBlockSet warm_references;
247 :
248 : // Consume the bbq.
249 E : bool have_seen_data_basic_block = false;
250 E : while (!bbq.empty()) {
251 : // Get the next basic block.
252 E : const BasicBlock* bb = bbq.front();
253 E : bbq.pop_front();
254 E : DCHECK(bb != NULL);
255 :
256 : // Insert it into the set of basic-blocks that have already been placed. If
257 : // the insertion is not a new element, then we've already handled this bb.
258 E : bool already_handled = placed_bbs.insert(bb).second == false;
259 E : if (already_handled)
260 E : continue;
261 :
262 : // If it's a code basic block then we send it to the warm or cold list
263 : // based on whether or not its entry count is zero. We also push its
264 : // most common successor to the head of bbq to let it be the next placed
265 : // basic-block. We should not see any more code basic blocks once we
266 : // have encountered a data basic block.
267 E : const BasicCodeBlock* code_bb = BasicCodeBlock::Cast(bb);
268 E : if (code_bb != NULL) {
269 E : DCHECK(!have_seen_data_basic_block);
270 :
271 E : EntryCountType entry_count = 0;
272 E : if (!GetBasicBlockEntryCount(code_bb, &entry_count)) {
273 i : LOG(ERROR) << "Failed to get entry count for " << code_bb->name()
274 : << " (offset=" << code_bb->offset() << ").";
275 i : return false;
276 : }
277 :
278 E : if (entry_count == 0) {
279 : // This is a cold basic-block. We simply add it to the cold
280 : // basic-block ordering.
281 : // TODO(rogerm): Sort cold blocks for minimal encoding size.
282 E : cold_basic_blocks->push_back(code_bb->offset());
283 E : } else {
284 : // This is a warm basic-block. Add it to the warm basic-block ordering.
285 E : warm_basic_blocks->push_back(code_bb->offset());
286 :
287 : // Remember the data blocks referenced from its instructions.
288 E : if (!AddWarmDataReferences(code_bb, &warm_references))
289 i : return false;
290 :
291 : // If the basic-block has one or more successors, schedule the warmest
292 : // not-yet-placed successor (if any) to be next. Otherwise, if the
293 : // basic-block ended with an indirect jump through a jump table, queue
294 : // up the destinations in decreasing entry count order.
295 E : if (!code_bb->successors().empty()) {
296 E : const BasicBlock* successor = NULL;
297 E : if (!GetWarmestSuccessor(code_bb, placed_bbs, &successor))
298 i : return false;
299 E : if (successor != NULL)
300 E : bbq.push_front(successor);
301 E : } else {
302 : // If the instruction is a jump, look for a jump table reference and
303 : // (if one is found) enqueue its referenced basic blocks in sorted
304 : // (by decreasing entry count) order.
305 E : DCHECK(!code_bb->instructions().empty());
306 E : const block_graph::Instruction& inst = code_bb->instructions().back();
307 E : if (inst.representation().opcode == I_JMP) {
308 E : std::vector<const BasicCodeBlock*> targets;
309 E : if (!GetSortedJumpTargets(inst, &targets))
310 i : return false;
311 E : bbq.insert(bbq.begin(), targets.begin(), targets.end());
312 E : }
313 : }
314 : }
315 : }
316 :
317 : // If it's a data basic block then we send it to the warm or cold list
318 : // depending on whether or not it was referenced by something in the warm
319 : // list. Note that the data basic-blocks are at the end of the basic-
320 : // block layout so we will have already seen all of the warm referrers
321 : // by the time this case succeeds.
322 E : const BasicDataBlock* data_bb = BasicDataBlock::Cast(bb);
323 E : if (data_bb != NULL) {
324 E : have_seen_data_basic_block = true;
325 E : if (warm_references.count(bb) != 0)
326 E : warm_basic_blocks->push_back(data_bb->offset());
327 E : else
328 E : cold_basic_blocks->push_back(data_bb->offset());
329 : }
330 E : }
331 :
332 : // TODO(rogerm): If we find that we haven't perturbed the basic-block
333 : // ordering then we could clear both lists and let the block simply
334 : // be copied/moved as is.
335 :
336 : DCHECK_EQ(subgraph_.basic_blocks().size(),
337 E : warm_basic_blocks->size() + cold_basic_blocks->size());
338 E : return true;
339 E : }
340 :
341 : bool BasicBlockOptimizer::BasicBlockOrderer::GetBasicBlockEntryCount(
342 E : const BasicCodeBlock* code_bb, EntryCountType* entry_count) const {
343 E : DCHECK(code_bb != NULL);
344 E : DCHECK(entry_count != NULL);
345 :
346 : if (!GetEntryCountByOffset(
347 E : entry_counts_, addr_, code_bb->offset(), entry_count)) {
348 i : return false;
349 : }
350 :
351 E : return true;
352 E : }
353 :
354 : bool BasicBlockOptimizer::BasicBlockOrderer::GetWarmestSuccessor(
355 : const BasicCodeBlock* code_bb,
356 : const BasicBlockSet& placed_bbs,
357 E : const BasicBlock** succ_bb) const {
358 E : DCHECK(code_bb != NULL);
359 E : DCHECK(succ_bb != NULL);
360 :
361 E : *succ_bb = NULL;
362 :
363 : // If there are no successors then there certainly isn't a warmest one.
364 E : if (code_bb->successors().empty())
365 i : return true;
366 :
367 : // If the first successor is a basic-block but it has already been seen,
368 : // then it is not a candidate for the warmest.
369 E : const BasicCodeBlock* succ1 = GetSuccessorBB(code_bb->successors().front());
370 E : if (succ1 != NULL && placed_bbs.count(succ1) != 0)
371 E : succ1 = NULL;
372 :
373 : // If that was the only successor, then return whatever we have thus far.
374 E : if (code_bb->successors().size() == 1) {
375 E : *succ_bb = succ1;
376 E : return true;
377 : }
378 :
379 E : DCHECK_EQ(2U, code_bb->successors().size());
380 :
381 : // If the second successor is a basic-block but it has already been seen,
382 : // then it is not a candidate for the warmest.
383 E : const BasicCodeBlock* succ2 = GetSuccessorBB(code_bb->successors().back());
384 E : if (succ2 != NULL && placed_bbs.count(succ2) != 0)
385 E : succ2 = NULL;
386 :
387 : // If the first successor is not a candidate, then we can return whatever we
388 : // have for the second successor.
389 E : if (succ1 == NULL) {
390 E : *succ_bb = succ2;
391 E : return true;
392 : }
393 :
394 E : DCHECK(succ1 != NULL);
395 :
396 : // If the second successor is not a candidate, then we can return whatever we
397 : // have for the first successor.
398 E : if (succ2 == NULL) {
399 E : *succ_bb = succ1;
400 E : return true;
401 : }
402 :
403 : // Both successors are valid candidates. We choose the one with the highest
404 : // entry count. Note that we keep the successors in the same order if the
405 : // entry counts are the same. By default we know that succ2 represents the
406 : // fall-through (branch-not-taken) path that immediately follows the
407 : // conditional.
408 E : DCHECK(succ1 != NULL);
409 E : DCHECK(succ2 != NULL);
410 :
411 E : EntryCountType succ1_entry_count = 0;
412 E : if (!GetBasicBlockEntryCount(succ1, &succ1_entry_count)) {
413 i : LOG(ERROR) << "Failed to get entry count for " << succ1->name()
414 : << " (offset=" << succ1->offset() << ").";
415 i : return false;
416 : }
417 :
418 E : EntryCountType succ2_entry_count = 0;
419 E : if (!GetBasicBlockEntryCount(succ2, &succ2_entry_count)) {
420 i : LOG(ERROR) << "Failed to get entry count for " << succ2->name()
421 : << " (offset=" << succ2->offset() << ").";
422 i : return false;
423 : }
424 :
425 E : if (succ1_entry_count > succ2_entry_count)
426 E : *succ_bb = succ1;
427 E : else
428 E : *succ_bb = succ2;
429 :
430 E : return true;
431 E : }
432 :
433 : bool BasicBlockOptimizer::BasicBlockOrderer::GetSortedJumpTargets(
434 : const block_graph::Instruction& jmp_inst,
435 E : std::vector<const BasicCodeBlock*>* targets) const {
436 E : DCHECK_EQ(I_JMP, jmp_inst.representation().opcode);
437 E : DCHECK(targets != NULL);
438 :
439 E : targets->clear();
440 :
441 : // We store the targets and their entry counts in a temporary vector that
442 : // we can sort by entry counts.
443 : typedef std::vector<CountForBasicBlock> TempTargets;
444 E : TempTargets temp_targets;
445 E : temp_targets.reserve(jmp_inst.references().size());
446 :
447 : // Find the jump-table reference.
448 : BasicBlock::BasicBlockReferenceMap::const_iterator ref_iter =
449 E : jmp_inst.references().begin();
450 E : for (; ref_iter != jmp_inst.references().end(); ++ref_iter) {
451 : // We're only interested in referred data basic blocks that are marked
452 : // as being a jump table.
453 : const BasicDataBlock* ref_bb =
454 E : BasicDataBlock::Cast(ref_iter->second.basic_block());
455 : if (ref_bb == NULL ||
456 : !ref_bb->label().IsValid() ||
457 E : !ref_bb->label().has_attributes(BlockGraph::JUMP_TABLE_LABEL)) {
458 i : continue;
459 : }
460 :
461 E : DCHECK(ref_bb != NULL);
462 E : DCHECK(ref_bb->label().IsValid());
463 E : DCHECK(ref_bb->label().has_attributes(BlockGraph::JUMP_TABLE_LABEL));
464 :
465 : // Populate temp_targets with each target and it's entry count.
466 : BasicBlock::BasicBlockReferenceMap::const_iterator target_iter =
467 E : ref_bb->references().begin();
468 E : for (; target_iter != ref_bb->references().end(); ++target_iter) {
469 : const BasicCodeBlock* target_bb =
470 E : BasicCodeBlock::Cast(target_iter->second.basic_block());
471 E : if (target_bb == NULL) {
472 i : LOG(ERROR) << "Found non-code-basic-block reference in a jump table.";
473 i : return false;
474 : }
475 : // Get the entry count.
476 E : EntryCountType entry_count = 0;
477 E : if (!GetBasicBlockEntryCount(target_bb, &entry_count))
478 i : return false;
479 :
480 : // Append the entry count and the target into the temp target vector.
481 E : temp_targets.push_back(std::make_pair(entry_count, target_bb));
482 E : }
483 E : }
484 :
485 : // Perform a stable sort of the temp target vector by decreasing entry count.
486 : std::stable_sort(
487 E : temp_targets.begin(), temp_targets.end(), &HasHigherEntryCount);
488 :
489 : // Copy the resulting basic block ordering into the target vector.
490 E : targets->reserve(temp_targets.size());
491 E : TempTargets::const_iterator temp_target_iter = temp_targets.begin();
492 E : for (; temp_target_iter != temp_targets.end(); ++temp_target_iter) {
493 E : if (temp_target_iter->first > 0)
494 E : targets->push_back(temp_target_iter->second);
495 E : }
496 :
497 E : return true;
498 E : }
499 :
500 : bool BasicBlockOptimizer::BasicBlockOrderer::AddWarmDataReferences(
501 E : const BasicCodeBlock* code_bb, BasicBlockSet* warm_references) const {
502 E : DCHECK(code_bb != NULL);
503 E : DCHECK(warm_references != NULL);
504 :
505 : // Iterate over all of the instructions.
506 : BasicBlock::Instructions::const_iterator inst_iter =
507 E : code_bb->instructions().begin();
508 E : for (; inst_iter != code_bb->instructions().end(); ++inst_iter) {
509 : // For each instruction, iterate over all references it makes.
510 : BasicBlock::BasicBlockReferenceMap::const_iterator ref_iter =
511 E : inst_iter->references().begin();
512 E : for (; ref_iter != inst_iter->references().end(); ++ref_iter) {
513 : // We're only interested in references that refer to basic-blocks.
514 E : const BasicBlock* bb = ref_iter->second.basic_block();
515 E : if (bb == NULL)
516 E : continue;
517 :
518 : // We tolerate code->code references only for the special case of
519 : // self-recursive functions.
520 E : const BasicCodeBlock* code_bb = BasicCodeBlock::Cast(bb);
521 E : if (code_bb != NULL) {
522 i : if (code_bb->offset() == 0) {
523 i : continue;
524 : }
525 :
526 i : DCHECK_NE(0, code_bb->offset());
527 i : LOG(ERROR) << "Invalid code to code reference from instruction.";
528 i : return false;
529 : }
530 :
531 : // For each data reference we recursively add all
532 : // basic data blocks reachable.
533 E : const BasicDataBlock* data_bb = BasicDataBlock::Cast(bb);
534 E : DCHECK(data_bb != NULL);
535 :
536 E : AddRecursiveDataReferences(data_bb, warm_references);
537 E : }
538 E : }
539 E : return true;
540 E : }
541 :
542 : void BasicBlockOptimizer::BasicBlockOrderer::AddRecursiveDataReferences(
543 E : const BasicDataBlock* data_bb, BasicBlockSet* warm_references) const {
544 E : DCHECK(data_bb != NULL);
545 E : DCHECK(warm_references != NULL);
546 :
547 : // Mark the current data basic-block as a warm reference. If this basic-
548 : // block is already in the warm references set, then we don't need to
549 : // recurse its references.
550 E : bool is_new_insertion = !warm_references->insert(data_bb).second;
551 E : if (!is_new_insertion)
552 E : return;
553 :
554 : // Otherwise, iterate over all of the references made from this data
555 : // basic-block. Note that the reference might point to code (a jump
556 : // table, for example). If the reference is to another data basic-block,
557 : // then recursively add its data references.
558 : BasicBlock::BasicBlockReferenceMap::const_iterator ref_iter =
559 i : data_bb->references().begin();
560 i : for (; ref_iter != data_bb->references().end(); ++ref_iter) {
561 : // We're only interested in references that refer to basic-blocks.
562 i : const BasicBlock* bb = ref_iter->second.basic_block();
563 i : if (bb == NULL)
564 i : continue;
565 : // We recurse into data basic-blocks.
566 i : const BasicDataBlock* referred_data_bb = BasicDataBlock::Cast(bb);
567 i : if (referred_data_bb != NULL)
568 i : AddRecursiveDataReferences(referred_data_bb, warm_references);
569 i : }
570 E : }
571 :
572 : BasicBlockOptimizer::BasicBlockOptimizer()
573 E : : cold_section_name_(kDefaultColdSectionName) {
574 E : }
575 :
576 : bool BasicBlockOptimizer::Optimize(const ImageLayout& image_layout,
577 : const EntryCountMap& entry_counts,
578 E : Order* order) {
579 E : DCHECK(order != NULL);
580 :
581 : // Keep track of which blocks have been explicitly ordered. This will be used
582 : // when implicitly placing blocks.
583 E : ConstBlockVector explicit_blocks;
584 E : if (!InitExplicitBlocks(order, &explicit_blocks))
585 i : return false;
586 :
587 : // Fill in any sections which were not mentioned by the ordering.
588 E : PopulateMissingSections(image_layout, order);
589 :
590 : // Remember how many sections we started with.
591 E : size_t num_sections = order->sections.size();
592 :
593 : // Add a new section in which to put the cold blocks and basic-blocks.
594 E : order->sections.push_back(Order::SectionSpec());
595 E : Order::SectionSpec* cold_section_spec = &order->sections.back();
596 E : cold_section_spec->name = cold_section_name_;
597 E : cold_section_spec->id = Order::SectionSpec::kNewSectionId;
598 E : cold_section_spec->characteristics = pe::kCodeCharacteristics;
599 :
600 : // Iterate over the sections in the original order and update their basic-
601 : // block orderings.
602 E : for (size_t i = 0; i < num_sections; ++i) {
603 E : Order::SectionSpec* section_spec = &order->sections[i];
604 E : Order::BlockSpecVector warm_block_specs;
605 E : Order::BlockSpecVector cold_block_specs;
606 :
607 : // Get the collection of warm and cold block spec for this section.
608 : if (!OptimizeSection(image_layout,
609 : entry_counts,
610 : explicit_blocks,
611 : section_spec,
612 : &warm_block_specs,
613 E : &cold_block_specs)) {
614 i : return false;
615 : }
616 :
617 : // Replace the block specs in the original section with those found to
618 : // be warm, and append the cold blocks to the end of the cold section.
619 E : section_spec->blocks.swap(warm_block_specs);
620 : cold_section_spec->blocks.insert(cold_section_spec->blocks.end(),
621 : cold_block_specs.begin(),
622 E : cold_block_specs.end());
623 E : }
624 :
625 E : return true;
626 E : }
627 :
628 : // Get an ordered list of warm and cold basic blocks for the given @p block.
629 : bool BasicBlockOptimizer::OptimizeBlock(
630 : const BlockGraph::Block* block,
631 : const ImageLayout& image_layout,
632 : const EntryCountMap& entry_counts,
633 : Order::BlockSpecVector* warm_block_specs,
634 E : Order::BlockSpecVector* cold_block_specs) {
635 E : DCHECK(block != NULL);
636 E : DCHECK(warm_block_specs != NULL);
637 E : DCHECK(cold_block_specs != NULL);
638 :
639 : // Leave data blocks untouched.
640 E : if (block->type() != BlockGraph::CODE_BLOCK) {
641 E : warm_block_specs->push_back(Order::BlockSpec(block));
642 E : return true;
643 : }
644 :
645 : // Find the start address of the block.
646 E : RelativeAddress addr;
647 E : if (!image_layout.blocks.GetAddressOf(block, &addr)) {
648 i : LOG(ERROR) << "Failed to find " << block->name() << " in image layout.";
649 i : return false;
650 : }
651 :
652 : // Determine the number of times the block has been entered. We use the
653 : // start of the block (with a zero offset) to find it's entry count.
654 E : EntryCountType entry_count = 0;
655 E : if (!GetEntryCountByOffset(entry_counts, addr, 0, &entry_count)) {
656 i : LOG(ERROR) << "Failed to find entry count for '" << block->name() << "'.";
657 i : return false;
658 : }
659 :
660 : // If the function was never invoked, we just move it as is to the cold set.
661 : // We have no information on which to base a basic-block optimization.
662 E : if (entry_count == 0) {
663 E : cold_block_specs->push_back(Order::BlockSpec(block));
664 E : return true;
665 : }
666 :
667 : // Handle non-decomposable code blocks as large opaque basic-blocks. We've
668 : // already established that the block is warm, so just place it as is.
669 E : if (!pe::CodeBlockIsBasicBlockDecomposable(block)) {
670 E : warm_block_specs->push_back(Order::BlockSpec(block));
671 E : return true;
672 : }
673 :
674 : // The function was called at least once and is basic-block decomposable.
675 : // Let's decompose and optimize it.
676 E : BasicBlockSubGraph subgraph;
677 E : BasicBlockDecomposer decomposer(block, &subgraph);
678 E : if (!decomposer.Decompose())
679 i : return false;
680 :
681 : // Create the basic-block orderer.
682 E : BasicBlockOrderer orderer(subgraph, addr, block->size(), entry_counts);
683 E : Order::OffsetVector warm_basic_blocks;
684 E : Order::OffsetVector cold_basic_blocks;
685 : if (!orderer.GetBasicBlockOrderings(&warm_basic_blocks,
686 E : &cold_basic_blocks)) {
687 i : return false;
688 : }
689 :
690 : // Note that we allow the ordering function to return an empty set of
691 : // warm basic-blocks. This denotes that the block should be placed into
692 : // the warm block specs without modification and also implies that there
693 : // should be no cold basic-blocks.
694 : //
695 : // Therefore the following should be true:
696 : // * If there are cold basic-blocks returned then there are also
697 : // warm basic-blocks returned.
698 : // * Either both returned sets are empty or the sum of the warm and
699 : // cold basic-blocks equals the total number of basic-blocks in
700 : // subgraph.
701 E : DCHECK(cold_basic_blocks.empty() || !warm_basic_blocks.empty());
702 : DCHECK((warm_basic_blocks.empty() && cold_basic_blocks.empty()) ||
703 : (warm_basic_blocks.size() + cold_basic_blocks.size() ==
704 E : subgraph.basic_blocks().size()));
705 :
706 : // We know the function was called at least once. Some part of it should
707 : // be into warm_block_specs.
708 E : warm_block_specs->push_back(Order::BlockSpec(block));
709 E : warm_block_specs->back().basic_block_offsets.swap(warm_basic_blocks);
710 :
711 : // But, there may or may not be a cold part.
712 E : if (!cold_basic_blocks.empty()) {
713 E : cold_block_specs->push_back(Order::BlockSpec(block));
714 E : cold_block_specs->back().basic_block_offsets.swap(cold_basic_blocks);
715 : }
716 :
717 E : return true;
718 E : }
719 :
720 : bool BasicBlockOptimizer::OptimizeSection(
721 : const ImageLayout& image_layout,
722 : const EntryCountMap& entry_counts,
723 : const ConstBlockVector& explicit_blocks,
724 : Order::SectionSpec* orig_section_spec,
725 : Order::BlockSpecVector* warm_block_specs,
726 E : Order::BlockSpecVector* cold_block_specs) {
727 E : DCHECK(orig_section_spec != NULL);
728 E : DCHECK(warm_block_specs != NULL);
729 E : DCHECK(cold_block_specs != NULL);
730 :
731 : // Place all of the explicitly ordered blocks.
732 E : for (size_t i = 0; i < orig_section_spec->blocks.size(); ++i) {
733 E : Order::BlockSpec* block_spec = &orig_section_spec->blocks[i];
734 E : DCHECK(block_spec->block != NULL);
735 E : DCHECK(block_spec->basic_block_offsets.empty());
736 E : DCHECK(IsExplicitBlock(explicit_blocks, block_spec->block));
737 :
738 : if (!OptimizeBlock(block_spec->block,
739 : image_layout,
740 : entry_counts,
741 : warm_block_specs,
742 E : cold_block_specs)) {
743 i : return false;
744 : }
745 E : }
746 :
747 : // If we are updating a preexisting section, then account for the rest of
748 : // the blocks in the section. We leave these in their original relative
749 : // ordering.
750 E : if (orig_section_spec->id != Order::SectionSpec::kNewSectionId) {
751 E : DCHECK_GT(image_layout.sections.size(), orig_section_spec->id);
752 : const ImageLayout::SectionInfo& section_info =
753 E : image_layout.sections[orig_section_spec->id];
754 :
755 : // Get an iterator pair denoting all of the blocks in the section.
756 : RangeMapConstIterPair iter_pair(
757 : image_layout.blocks.GetIntersectingBlocks(
758 E : RelativeAddress(section_info.addr), section_info.size));
759 E : for (RangeMapConstIter it = iter_pair.first; it != iter_pair.second; ++it) {
760 : // If the block is explicitly mentioned in the ordering then we don't
761 : // have to handle it here. Note that explicit_blocks is populated
762 : // before placing any blocks, so it already accounts for blocks that
763 : // move between sections.
764 E : if (IsExplicitBlock(explicit_blocks, it->second))
765 E : continue;
766 :
767 : // We apply the same optimization as for explicitly placed blocks.
768 : if (!OptimizeBlock(it->second,
769 : image_layout,
770 : entry_counts,
771 : warm_block_specs,
772 E : cold_block_specs)) {
773 i : return false;
774 : }
775 E : }
776 : }
777 :
778 E : return true;
779 E : }
780 :
781 : } // namespace reorder
|