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/find.h"
25 : #include "syzygy/pe/pe_utils.h"
26 :
27 : #include "mnemonics.h" // NOLINT
28 :
29 : namespace reorder {
30 :
31 : namespace {
32 :
33 : using block_graph::BlockGraph;
34 : using block_graph::ConstBlockVector;
35 : using block_graph::BasicBlock;
36 : using block_graph::BasicCodeBlock;
37 : using block_graph::BasicDataBlock;
38 : using block_graph::BasicBlockDecomposer;
39 : using block_graph::BasicBlockSubGraph;
40 : using block_graph::Successor;
41 : using grinder::basic_block_util::EntryCountType;
42 : using grinder::basic_block_util::IndexedFrequencyInformation;
43 : using grinder::basic_block_util::IndexedFrequencyOffset;
44 : using grinder::basic_block_util::IndexedFrequencyMap;
45 : using grinder::basic_block_util::InitModuleInfo;
46 : using grinder::basic_block_util::ModuleInformation;
47 : using grinder::basic_block_util::RelativeAddress;
48 : using grinder::basic_block_util::RelativeAddressRange;
49 : using grinder::basic_block_util::RelativeAddressRangeVector;
50 : using pe::PEFile;
51 : using pe::ImageLayout;
52 :
53 : typedef Reorderer::Order Order;
54 : typedef BlockGraph::Offset Offset;
55 : typedef BlockGraph::Size Size;
56 : typedef BlockGraph::AddressSpace::RangeMapConstIter RangeMapConstIter;
57 : typedef BlockGraph::AddressSpace::RangeMapConstIterPair RangeMapConstIterPair;
58 :
59 : const char kDefaultColdSectionName[] = ".ctext";
60 :
61 : // A helper to fill in (retaining relative ordering) any sections that are in
62 : // the original @p image_layout which are not mentioned in @p order.
63 : void PopulateMissingSections(
64 E : const ImageLayout& image_layout, Order* order) {
65 E : DCHECK(order != NULL);
66 :
67 : // Remember all of the sections mentioned by id.
68 E : std::set<BlockGraph::SectionId> mentioned;
69 E : for (size_t i = 0; i < order->sections.size(); ++i) {
70 E : if (order->sections[i].id != Order::SectionSpec::kNewSectionId) {
71 E : bool inserted = mentioned.insert(order->sections[i].id).second;
72 E : DCHECK(inserted);
73 : }
74 E : }
75 :
76 : // Iterate over all of the sections and append those not mentioned by ID.
77 E : for (BlockGraph::SectionId id = 0; id < image_layout.sections.size(); ++id) {
78 E : const ImageLayout::SectionInfo& info = image_layout.sections[id];
79 E : if (mentioned.count(id) == 0) {
80 E : order->sections.push_back(Order::SectionSpec());
81 E : order->sections.back().id = id;
82 E : order->sections.back().name = info.name;
83 E : order->sections.back().characteristics = info.characteristics;
84 : }
85 E : }
86 E : }
87 :
88 : // Initialize a collection of blocks which are explicitly mentioned by the
89 : // given @p order.
90 E : bool InitExplicitBlocks(const Order* order, ConstBlockVector* explicit_blocks) {
91 E : DCHECK(order != NULL);
92 E : DCHECK(explicit_blocks != NULL);
93 E : explicit_blocks->clear();
94 :
95 : // Put all of the explicitly referenced blocks into explicit_blocks.
96 E : for (size_t i = 0; i < order->sections.size(); ++i) {
97 E : const Order::SectionSpec& section = order->sections[i];
98 E : for (size_t k = 0; k < section.blocks.size(); ++k) {
99 E : if (!section.blocks[k].basic_block_offsets.empty()) {
100 i : LOG(ERROR) << "Expected a block-only ordering.";
101 i : return false;
102 : }
103 E : explicit_blocks->push_back(section.blocks[k].block);
104 E : }
105 E : }
106 :
107 : // If there are no explicit blocks then we are finished.
108 E : if (explicit_blocks->empty())
109 E : return true;
110 :
111 : // Sort the set of explicitly placed blocks. This lets us quickly check if
112 : // a block is in explicit_blocks using binary search.
113 E : std::sort(explicit_blocks->begin(), explicit_blocks->end());
114 :
115 : // Verify that no block has been mentioned more than once.
116 E : ConstBlockVector::const_iterator next_iter = explicit_blocks->begin();
117 E : ConstBlockVector::const_iterator end_iter = --explicit_blocks->end();
118 E : while (next_iter != end_iter) {
119 E : ConstBlockVector::const_iterator curr_iter = next_iter++;
120 E : if (*curr_iter == *next_iter) {
121 i : LOG(ERROR) << "Ordering references a block multiple times.";
122 i : return false;
123 : }
124 E : }
125 :
126 : // And we're done.
127 E : return true;
128 E : }
129 :
130 : // Check if @p block is in @p explicit_blocks.
131 : bool IsExplicitBlock(const ConstBlockVector& explicit_blocks,
132 E : const BlockGraph::Block* block) {
133 : return std::binary_search(explicit_blocks.begin(),
134 : explicit_blocks.end(),
135 E : block);
136 E : }
137 :
138 : // A helper to "cast" the given successor as a BasicCodeBlock.
139 E : const BasicCodeBlock* GetSuccessorBB(const Successor& successor) {
140 E : const BasicBlock* bb = successor.reference().basic_block();
141 :
142 : // This might be in inter block reference (i.e., refers to a block not
143 : // a basic-block).
144 E : if (bb == NULL)
145 E : return NULL;
146 :
147 : // If it's a basic-block then it must be a code basic-block.
148 E : const BasicCodeBlock* code_bb = BasicCodeBlock::Cast(bb);
149 E : DCHECK(code_bb != NULL);
150 E : return code_bb;
151 E : }
152 :
153 : typedef std::pair<EntryCountType, const BasicCodeBlock*> CountForBasicBlock;
154 :
155 : bool HasHigherEntryCount(const CountForBasicBlock& lhs,
156 E : const CountForBasicBlock& rhs) {
157 E : return lhs.first > rhs.first;
158 E : }
159 :
160 : bool GetEntryCountByOffset(const IndexedFrequencyInformation& entry_counts,
161 : const RelativeAddress& base_rva,
162 : Offset offset,
163 E : EntryCountType* entry_count) {
164 E : DCHECK_LE(0, offset);
165 E : DCHECK(entry_count != NULL);
166 :
167 E : *entry_count = 0;
168 E : IndexedFrequencyOffset key = std::make_pair(base_rva + offset, 0);
169 : IndexedFrequencyMap::const_iterator it =
170 E : entry_counts.frequency_map.find(key);
171 E : if (it != entry_counts.frequency_map.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 IndexedFrequencyInformation& 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(
577 : const ImageLayout& image_layout,
578 : const IndexedFrequencyInformation& entry_counts,
579 E : Order* order) {
580 E : DCHECK(order != NULL);
581 :
582 : if (entry_counts.data_type !=
583 : ::common::IndexedFrequencyData::BASIC_BLOCK_ENTRY &&
584 : entry_counts.data_type !=
585 E : ::common::IndexedFrequencyData::BRANCH) {
586 i : LOG(ERROR) << "Invalid frequency data type.";
587 i : return false;
588 : }
589 :
590 : // Keep track of which blocks have been explicitly ordered. This will be used
591 : // when implicitly placing blocks.
592 E : ConstBlockVector explicit_blocks;
593 E : if (!InitExplicitBlocks(order, &explicit_blocks))
594 i : return false;
595 :
596 : // Fill in any sections which were not mentioned by the ordering.
597 E : PopulateMissingSections(image_layout, order);
598 :
599 : // Remember how many sections we started with.
600 E : size_t num_sections = order->sections.size();
601 :
602 : // Add a new section in which to put the cold blocks and basic-blocks.
603 E : order->sections.push_back(Order::SectionSpec());
604 E : Order::SectionSpec* cold_section_spec = &order->sections.back();
605 E : cold_section_spec->name = cold_section_name_;
606 E : cold_section_spec->id = Order::SectionSpec::kNewSectionId;
607 E : cold_section_spec->characteristics = pe::kCodeCharacteristics;
608 :
609 E : pe::PETransformPolicy policy;
610 :
611 : // Iterate over the sections in the original order and update their basic-
612 : // block orderings.
613 E : for (size_t i = 0; i < num_sections; ++i) {
614 E : Order::SectionSpec* section_spec = &order->sections[i];
615 E : Order::BlockSpecVector warm_block_specs;
616 E : Order::BlockSpecVector cold_block_specs;
617 :
618 : // Get the collection of warm and cold block spec for this section.
619 : if (!OptimizeSection(policy,
620 : image_layout,
621 : entry_counts,
622 : explicit_blocks,
623 : section_spec,
624 : &warm_block_specs,
625 E : &cold_block_specs)) {
626 i : return false;
627 : }
628 :
629 : // Replace the block specs in the original section with those found to
630 : // be warm, and append the cold blocks to the end of the cold section.
631 E : section_spec->blocks.swap(warm_block_specs);
632 : cold_section_spec->blocks.insert(cold_section_spec->blocks.end(),
633 : cold_block_specs.begin(),
634 E : cold_block_specs.end());
635 E : }
636 :
637 E : return true;
638 E : }
639 :
640 : // Get an ordered list of warm and cold basic blocks for the given @p block.
641 : bool BasicBlockOptimizer::OptimizeBlock(
642 : const pe::PETransformPolicy& policy,
643 : const BlockGraph::Block* block,
644 : const ImageLayout& image_layout,
645 : const IndexedFrequencyInformation& entry_counts,
646 : Order::BlockSpecVector* warm_block_specs,
647 E : Order::BlockSpecVector* cold_block_specs) {
648 E : DCHECK(block != NULL);
649 E : DCHECK(warm_block_specs != NULL);
650 E : DCHECK(cold_block_specs != NULL);
651 :
652 : // Leave data blocks untouched.
653 E : if (block->type() != BlockGraph::CODE_BLOCK) {
654 E : warm_block_specs->push_back(Order::BlockSpec(block));
655 E : return true;
656 : }
657 :
658 : // Find the start address of the block.
659 E : RelativeAddress addr;
660 E : if (!image_layout.blocks.GetAddressOf(block, &addr)) {
661 i : LOG(ERROR) << "Failed to find " << block->name() << " in image layout.";
662 i : return false;
663 : }
664 :
665 : // Determine the number of times the block has been entered. We use the
666 : // start of the block (with a zero offset) to find it's entry count.
667 E : EntryCountType entry_count = 0;
668 E : if (!GetEntryCountByOffset(entry_counts, addr, 0, &entry_count)) {
669 i : LOG(ERROR) << "Failed to find entry count for '" << block->name() << "'.";
670 i : return false;
671 : }
672 :
673 : // If the function was never invoked, we just move it as is to the cold set.
674 : // We have no information on which to base a basic-block optimization.
675 E : if (entry_count == 0) {
676 E : cold_block_specs->push_back(Order::BlockSpec(block));
677 E : return true;
678 : }
679 :
680 : // Handle non-decomposable code blocks as large opaque basic-blocks. We've
681 : // already established that the block is warm, so just place it as is.
682 E : if (!policy.BlockIsSafeToBasicBlockDecompose(block)) {
683 E : warm_block_specs->push_back(Order::BlockSpec(block));
684 E : return true;
685 : }
686 :
687 : // The function was called at least once and is basic-block decomposable.
688 : // Let's decompose and optimize it.
689 E : BasicBlockSubGraph subgraph;
690 E : BasicBlockDecomposer decomposer(block, &subgraph);
691 E : if (!decomposer.Decompose())
692 i : return false;
693 :
694 : // Create the basic-block orderer.
695 E : BasicBlockOrderer orderer(subgraph, addr, block->size(), entry_counts);
696 E : Order::OffsetVector warm_basic_blocks;
697 E : Order::OffsetVector cold_basic_blocks;
698 : if (!orderer.GetBasicBlockOrderings(&warm_basic_blocks,
699 E : &cold_basic_blocks)) {
700 i : return false;
701 : }
702 :
703 : // Note that we allow the ordering function to return an empty set of
704 : // warm basic-blocks. This denotes that the block should be placed into
705 : // the warm block specs without modification and also implies that there
706 : // should be no cold basic-blocks.
707 : //
708 : // Therefore the following should be true:
709 : // * If there are cold basic-blocks returned then there are also
710 : // warm basic-blocks returned.
711 : // * Either both returned sets are empty or the sum of the warm and
712 : // cold basic-blocks equals the total number of basic-blocks in
713 : // subgraph.
714 E : DCHECK(cold_basic_blocks.empty() || !warm_basic_blocks.empty());
715 : DCHECK((warm_basic_blocks.empty() && cold_basic_blocks.empty()) ||
716 : (warm_basic_blocks.size() + cold_basic_blocks.size() ==
717 E : subgraph.basic_blocks().size()));
718 :
719 : // We know the function was called at least once. Some part of it should
720 : // be into warm_block_specs.
721 E : warm_block_specs->push_back(Order::BlockSpec(block));
722 E : warm_block_specs->back().basic_block_offsets.swap(warm_basic_blocks);
723 :
724 : // But, there may or may not be a cold part.
725 E : if (!cold_basic_blocks.empty()) {
726 E : cold_block_specs->push_back(Order::BlockSpec(block));
727 E : cold_block_specs->back().basic_block_offsets.swap(cold_basic_blocks);
728 : }
729 :
730 E : return true;
731 E : }
732 :
733 : bool BasicBlockOptimizer::OptimizeSection(
734 : const pe::PETransformPolicy& policy,
735 : const ImageLayout& image_layout,
736 : const IndexedFrequencyInformation& entry_counts,
737 : const ConstBlockVector& explicit_blocks,
738 : Order::SectionSpec* orig_section_spec,
739 : Order::BlockSpecVector* warm_block_specs,
740 E : Order::BlockSpecVector* cold_block_specs) {
741 E : DCHECK(orig_section_spec != NULL);
742 E : DCHECK(warm_block_specs != NULL);
743 E : DCHECK(cold_block_specs != NULL);
744 :
745 : // Place all of the explicitly ordered blocks.
746 E : for (size_t i = 0; i < orig_section_spec->blocks.size(); ++i) {
747 E : Order::BlockSpec* block_spec = &orig_section_spec->blocks[i];
748 E : DCHECK(block_spec->block != NULL);
749 E : DCHECK(block_spec->basic_block_offsets.empty());
750 E : DCHECK(IsExplicitBlock(explicit_blocks, block_spec->block));
751 :
752 : if (!OptimizeBlock(policy,
753 : block_spec->block,
754 : image_layout,
755 : entry_counts,
756 : warm_block_specs,
757 E : cold_block_specs)) {
758 i : return false;
759 : }
760 E : }
761 :
762 : // If we are updating a preexisting section, then account for the rest of
763 : // the blocks in the section. We leave these in their original relative
764 : // ordering.
765 E : if (orig_section_spec->id != Order::SectionSpec::kNewSectionId) {
766 E : DCHECK_GT(image_layout.sections.size(), orig_section_spec->id);
767 : const ImageLayout::SectionInfo& section_info =
768 E : image_layout.sections[orig_section_spec->id];
769 :
770 : // Get an iterator pair denoting all of the blocks in the section.
771 : RangeMapConstIterPair iter_pair(
772 : image_layout.blocks.GetIntersectingBlocks(
773 E : RelativeAddress(section_info.addr), section_info.size));
774 E : for (RangeMapConstIter it = iter_pair.first; it != iter_pair.second; ++it) {
775 : // If the block is explicitly mentioned in the ordering then we don't
776 : // have to handle it here. Note that explicit_blocks is populated
777 : // before placing any blocks, so it already accounts for blocks that
778 : // move between sections.
779 E : if (IsExplicitBlock(explicit_blocks, it->second))
780 E : continue;
781 :
782 : // We apply the same optimization as for explicitly placed blocks.
783 : if (!OptimizeBlock(policy,
784 : it->second,
785 : image_layout,
786 : entry_counts,
787 : warm_block_specs,
788 E : cold_block_specs)) {
789 i : return false;
790 : }
791 E : }
792 : }
793 :
794 E : return true;
795 E : }
796 :
797 : } // namespace reorder
|