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 : // Implementation of basic block decomposer.
16 :
17 : #include "syzygy/block_graph/basic_block_decomposer.h"
18 :
19 : #include <algorithm>
20 : #include <vector>
21 :
22 : #include "base/logging.h"
23 : #include "base/strings/stringprintf.h"
24 : #include "syzygy/block_graph/basic_block.h"
25 : #include "syzygy/block_graph/basic_block_subgraph.h"
26 : #include "syzygy/block_graph/block_graph.h"
27 : #include "syzygy/block_graph/block_util.h"
28 :
29 : #include "mnemonics.h" // NOLINT
30 :
31 : namespace block_graph {
32 :
33 : namespace {
34 :
35 : using block_graph::BasicBlock;
36 : using block_graph::BasicBlockReference;
37 : using block_graph::BasicBlockReferrer;
38 : using block_graph::BasicBlockSubGraph;
39 : using block_graph::BlockGraph;
40 : using block_graph::Instruction;
41 : using block_graph::Successor;
42 : using core::Disassembler;
43 :
44 : typedef BlockGraph::Block Block;
45 : typedef BlockGraph::Offset Offset;
46 : typedef BlockGraph::Size Size;
47 : typedef core::AddressSpace<Offset, size_t, BasicBlock*> BBAddressSpace;
48 : typedef BBAddressSpace::Range Range;
49 : typedef BBAddressSpace::RangeMap RangeMap;
50 : typedef BBAddressSpace::RangeMapConstIter RangeMapConstIter;
51 : typedef BBAddressSpace::RangeMapIter RangeMapIter;
52 :
53 : const size_t kPointerSize = BlockGraph::Reference::kMaximumSize;
54 :
55 : // We use a (somewhat) arbitrary value as the disassembly address for a block
56 : // so we can tell the difference between a reference to the beginning of the
57 : // block (offset=0) and a null address.
58 : const size_t kDisassemblyAddress = 65536;
59 :
60 : // Look up the reference made from an instruction's byte range within the
61 : // given block. The reference should start AFTER the instruction starts
62 : // and there should be exactly 1 reference in the byte range.
63 : // Returns true if the reference was found, false otherwise.
64 : bool GetReferenceOfInstructionAt(const Block* block,
65 : Offset instr_offset,
66 : Size instr_size,
67 E : BlockGraph::Reference* ref) {
68 E : DCHECK(block != NULL);
69 E : DCHECK_LE(0, instr_offset);
70 E : DCHECK_LT(0U, instr_size);
71 E : DCHECK(ref != NULL);
72 :
73 : // Find the first reference following the instruction offset.
74 : Block::ReferenceMap::const_iterator ref_iter =
75 E : block->references().upper_bound(instr_offset);
76 :
77 : // If no reference is found then we're done.
78 E : if (ref_iter == block->references().end())
79 E : return false;
80 :
81 : // If the reference occurs outside the instruction then we're done.
82 E : Offset next_instr_offset = instr_offset + instr_size;
83 E : if (ref_iter->first >= next_instr_offset)
84 E : return false;
85 :
86 : // Otherwise, the reference should fit into the instruction.
87 E : CHECK_LE(static_cast<size_t>(next_instr_offset),
88 E : ref_iter->first + ref_iter->second.size());
89 :
90 : // And it should be the only reference in the instruction.
91 E : if (ref_iter != block->references().begin()) {
92 E : Block::ReferenceMap::const_iterator prev_iter = ref_iter;
93 E : --prev_iter;
94 E : CHECK_GE(static_cast<size_t>(instr_offset),
95 E : prev_iter->first + prev_iter->second.size());
96 : }
97 E : Block::ReferenceMap::const_iterator next_iter = ref_iter;
98 E : ++next_iter;
99 E : CHECK(next_iter == block->references().end() ||
100 : next_iter->first >= next_instr_offset);
101 :
102 E : *ref = ref_iter->second;
103 E : return true;
104 E : }
105 :
106 : // Transfer instructions from original to tail, starting with the instruction
107 : // starting at offset.
108 : bool SplitInstructionListAt(Offset offset,
109 : BasicBlock::Instructions* original,
110 E : BasicBlock::Instructions* tail) {
111 E : DCHECK(original != NULL);
112 E : DCHECK(tail != NULL && tail->empty());
113 :
114 E : BasicBlock::Instructions::iterator it(original->begin());
115 E : while (offset > 0 && it != original->end()) {
116 E : offset -= it->size();
117 E : ++it;
118 E : }
119 :
120 : // Did we terminate at an instruction boundary?
121 E : if (offset != 0)
122 i : return false;
123 :
124 E : tail->splice(tail->end(), *original, it, original->end());
125 E : return true;
126 E : }
127 :
128 : } // namespace
129 :
130 : BasicBlockDecomposer::BasicBlockDecomposer(const BlockGraph::Block* block,
131 : BasicBlockSubGraph* subgraph)
132 E : : block_(block),
133 E : subgraph_(subgraph),
134 E : current_block_start_(0),
135 E : check_decomposition_results_(true),
136 E : contains_unsupported_instructions_(false) {
137 : // TODO(rogerm): Once we're certain this is stable for all input binaries
138 : // turn on check_decomposition_results_ by default only ifndef NDEBUG.
139 E : DCHECK(block != NULL);
140 E : DCHECK(block->type() == BlockGraph::CODE_BLOCK);
141 :
142 : // If no subgraph was provided then use a scratch one.
143 E : if (subgraph == NULL) {
144 E : scratch_subgraph_.reset(new BasicBlockSubGraph());
145 E : subgraph_ = scratch_subgraph_.get();
146 : }
147 E : }
148 :
149 E : bool BasicBlockDecomposer::Decompose() {
150 E : DCHECK(subgraph_->basic_blocks().empty());
151 E : DCHECK(subgraph_->block_descriptions().empty());
152 E : DCHECK(original_address_space_.empty());
153 E : subgraph_->set_original_block(block_);
154 :
155 E : bool disassembled = Disassemble();
156 E : if (contains_unsupported_instructions_) {
157 E : CHECK(!disassembled);
158 E : return false;
159 : }
160 :
161 : // It's entirely possible for the policy object to have allowed
162 : // decomposition of a function that contains assembly. In this case the
163 : // decomposition may fail. However that is the only case in which this
164 : // should fail.
165 E : if (!disassembled) {
166 E : if (!(block_->attributes() & BlockGraph::HAS_INLINE_ASSEMBLY)) {
167 i : LOG(FATAL) << "Unexpectedly failed to disassemble block."
168 : << " Name: " << block_->name()
169 : << " Compiland: " << block_->compiland_name();
170 : }
171 E : return false;
172 : }
173 :
174 : // Don't bother with the following bookkeeping work if the results aren't
175 : // being looked at.
176 E : if (scratch_subgraph_.get() != NULL)
177 E : return true;
178 :
179 : // TODO(cseri): Decomposition of blocks with nonzero alignment offset is not
180 : // yet supported.
181 E : CHECK_EQ(0, block_->alignment_offset());
182 :
183 : typedef BasicBlockSubGraph::BlockDescription BlockDescription;
184 E : subgraph_->block_descriptions().push_back(BlockDescription());
185 E : BlockDescription& desc = subgraph_->block_descriptions().back();
186 E : desc.name = block_->name();
187 E : desc.compiland_name = block_->compiland_name();
188 E : desc.type = block_->type();
189 E : desc.alignment = block_->alignment();
190 E : desc.padding_before = block_->padding_before();
191 E : desc.attributes = block_->attributes();
192 E : desc.section = block_->section();
193 :
194 : // Add the basic blocks to the block descriptor.
195 E : Offset offset = 0;
196 E : RangeMapConstIter it = original_address_space_.begin();
197 E : for (; it != original_address_space_.end(); ++it) {
198 E : DCHECK_EQ(it->first.start(), offset);
199 E : desc.basic_block_order.push_back(it->second);
200 :
201 : // Any data basic blocks (jump and case tables) with 0 mod 4 alignment
202 : // are marked so that the alignment is preserved by the block builder.
203 : if (desc.alignment >= kPointerSize &&
204 E : it->second->type() == BasicBlock::BASIC_DATA_BLOCK &&
205 : (offset % kPointerSize) == 0) {
206 E : it->second->set_alignment(kPointerSize);
207 : }
208 :
209 E : offset += it->first.size();
210 E : }
211 :
212 E : return true;
213 E : }
214 :
215 : bool BasicBlockDecomposer::DecodeInstruction(Offset offset,
216 : Offset code_end_offset,
217 E : Instruction* instruction) const {
218 : // The entire offset range should fall within the extent of block_ and the
219 : // output instruction pointer must not be NULL.
220 E : DCHECK_LE(0, offset);
221 E : DCHECK_LT(offset, code_end_offset);
222 E : DCHECK_LE(static_cast<Size>(code_end_offset), block_->size());
223 E : DCHECK(instruction != NULL);
224 :
225 : // Decode the instruction.
226 E : const uint8_t* buffer = block_->data() + offset;
227 E : uint32_t max_length = code_end_offset - offset;
228 E : if (!Instruction::FromBuffer(buffer, max_length, instruction)) {
229 E : VLOG(1) << "Failed to decode instruction at offset " << offset
230 : << " of block '" << block_->name() << "'.";
231 :
232 : // Dump the bytes to aid in debugging.
233 E : std::string dump;
234 E : size_t dump_length = std::min(max_length, Instruction::kMaxSize);
235 E : for (size_t i = 0; i < dump_length; ++i)
236 E : base::StringAppendF(&dump, " %02X", buffer[i]);
237 E : VLOG(2) << ".text =" << dump << (dump_length < max_length ? "..." : ".");
238 :
239 : // Return false to indicate an error.
240 E : return false;
241 : }
242 :
243 E : VLOG(3) << "Disassembled " << instruction->GetName()
244 : << " instruction (" << instruction->size()
245 : << " bytes) at offset " << offset << ".";
246 :
247 : // Track the source range.
248 E : instruction->set_source_range(
249 : GetSourceRange(offset, instruction->size()));
250 :
251 : // If the block is labeled, preserve the label.
252 E : BlockGraph::Label label;
253 E : if (block_->GetLabel(offset, &label)) {
254 : // If this instruction has run into known data, then we have a problem!
255 E : CHECK(!label.has_attributes(BlockGraph::DATA_LABEL))
256 : << "Disassembling into data at offset " << offset << " of "
257 : << block_->name() << ".";
258 E : instruction->set_label(label);
259 : }
260 :
261 E : return true;
262 E : }
263 :
264 : BasicBlockDecomposer::SourceRange BasicBlockDecomposer::GetSourceRange(
265 E : Offset offset, Size size) const {
266 : // Find the source range for the original bytes. We may not have a data
267 : // range for bytes that were synthesized in other transformations. As a
268 : // rule, however, there should be a covered data range for each instruction,
269 : // successor, that relates back to the original image.
270 : const Block::SourceRanges::RangePair* range_pair =
271 E : block_->source_ranges().FindRangePair(offset, size);
272 : // Return an empty range if we found nothing.
273 E : if (range_pair == NULL)
274 E : return SourceRange();
275 :
276 E : const Block::DataRange& data_range = range_pair->first;
277 E : const Block::SourceRange& source_range = range_pair->second;
278 E : if (offset == data_range.start() && size == data_range.size()) {
279 : // We match a data range exactly, so let's use the entire
280 : // matching source range.
281 E : return source_range;
282 : }
283 :
284 : // The data range doesn't match exactly, so let's slice the corresponding
285 : // source range. The assumption here is that no transformation will ever
286 : // slice the data or source ranges for an instruction, so we should always
287 : // have a covering data and source ranges.
288 E : DCHECK_GE(offset, data_range.start());
289 E : DCHECK_LE(offset + size, data_range.start() + data_range.size());
290 :
291 E : Offset start_offs = offset - data_range.start();
292 E : return SourceRange(source_range.start() + start_offs, size);
293 E : }
294 :
295 : bool BasicBlockDecomposer::FindBasicBlock(Offset offset,
296 : BasicBlock** basic_block,
297 E : Range* range) const {
298 E : DCHECK_LE(0, offset);
299 E : DCHECK(basic_block != NULL);
300 E : DCHECK(range != NULL);
301 E : DCHECK(subgraph_->original_block() != NULL);
302 E : DCHECK_GE(subgraph_->original_block()->size(), static_cast<size_t>(offset));
303 :
304 : RangeMapConstIter bb_iter =
305 E : original_address_space_.FindFirstIntersection(Range(offset, 1));
306 :
307 E : if (bb_iter == original_address_space_.end())
308 i : return false;
309 :
310 E : *basic_block = bb_iter->second;
311 E : *range = bb_iter->first;
312 E : return true;
313 E : }
314 :
315 E : BasicBlock* BasicBlockDecomposer::GetBasicBlockAt(Offset offset) const {
316 E : DCHECK_LE(0, offset);
317 E : DCHECK(subgraph_->original_block() != NULL);
318 E : DCHECK_GE(subgraph_->original_block()->size(), static_cast<size_t>(offset));
319 :
320 E : BasicBlock* bb = NULL;
321 E : Range range;
322 E : CHECK(FindBasicBlock(offset, &bb, &range));
323 E : DCHECK(bb != NULL);
324 E : DCHECK_EQ(offset, range.start());
325 E : return bb;
326 E : }
327 :
328 E : void BasicBlockDecomposer::InitJumpTargets(Offset code_end_offset) {
329 E : DCHECK_LE(static_cast<Size>(code_end_offset), block_->size());
330 :
331 : // Make sure the jump target set is empty.
332 E : jump_targets_.clear();
333 :
334 : // For each referrer, check if it references code. If so, it's a jump target.
335 : BlockGraph::Block::ReferrerSet::const_iterator ref_iter =
336 E : block_->referrers().begin();
337 E : for (; ref_iter != block_->referrers().end(); ++ref_iter) {
338 E : BlockGraph::Reference ref;
339 E : bool found = ref_iter->first->GetReference(ref_iter->second, &ref);
340 E : DCHECK(found);
341 E : DCHECK_EQ(block_, ref.referenced());
342 E : DCHECK_LE(0, ref.base());
343 E : DCHECK_LE(static_cast<size_t>(ref.base()), block_->size());
344 :
345 : // Ignore references to the data portion of the block.
346 E : if (ref.base() >= code_end_offset)
347 E : continue;
348 :
349 E : jump_targets_.insert(ref.base());
350 E : }
351 E : }
352 :
353 : bool BasicBlockDecomposer::HandleInstruction(const Instruction& instruction,
354 E : Offset offset) {
355 : // We do not handle the SYS* instructions. These should ONLY occur inside
356 : // the OS system libraries, mediated by an OS system call. We expect that
357 : // they NEVER occur in application code.
358 E : if (instruction.IsSystemCall()) {
359 i : VLOG(1) << "Encountered an unexpected " << instruction.GetName()
360 : << " instruction at offset " << offset << " of block '"
361 : << block_->name() << "'.";
362 i : return false;
363 : }
364 :
365 : // Calculate the offset of the next instruction. We'll need this if this
366 : // instruction marks the end of a basic block.
367 E : Offset next_instruction_offset = offset + instruction.size();
368 :
369 : // If the instruction is not a branch then it needs to be appended to the
370 : // current basic block... which we close if the instruction is a return or
371 : // a call to a non-returning function.
372 E : if (!instruction.IsBranch()) {
373 E : current_instructions_.push_back(instruction);
374 E : if (instruction.IsReturn()) {
375 E : EndCurrentBasicBlock(next_instruction_offset);
376 E : } else if (instruction.IsCall()) {
377 E : BlockGraph::Reference ref;
378 E : bool found = GetReferenceOfInstructionAt(
379 : block_, offset, instruction.size(), &ref);
380 E : if (found && Instruction::IsCallToNonReturningFunction(
381 : instruction.representation(), ref.referenced(), ref.offset())) {
382 E : EndCurrentBasicBlock(next_instruction_offset);
383 : }
384 : }
385 E : return true;
386 : }
387 :
388 : // If the branch is not PC-Relative then it also needs to be appended to
389 : // the current basic block... which we then close.
390 E : if (!instruction.HasPcRelativeOperand(0)) {
391 E : current_instructions_.push_back(instruction);
392 E : EndCurrentBasicBlock(next_instruction_offset);
393 E : return true;
394 : }
395 :
396 : // Otherwise, we're dealing with a branch whose destination is explicit.
397 E : DCHECK(instruction.IsBranch());
398 E : DCHECK(instruction.HasPcRelativeOperand(0));
399 :
400 : // Make sure we understand the branching condition. If we don't, then
401 : // there's an instruction we have failed (or are unable) to consider.
402 : // This failure is by design, as we can't represent instructions like
403 : // JECZX or LOOPZ, as discussed in basic_block.cc.
404 E : Successor::Condition condition = Successor::OpCodeToCondition(
405 : instruction.opcode());
406 E : if (condition == Successor::kInvalidCondition) {
407 E : VLOG(1) << "Received unknown condition for branch instruction: "
408 : << instruction.GetName() << ".";
409 E : contains_unsupported_instructions_ = true;
410 E : return false;
411 : }
412 :
413 : // If this is a conditional branch add the inverse conditional successor
414 : // to represent the fall-through. If we don't understand the inverse, then
415 : // there's an instruction we have failed to consider.
416 E : if (instruction.IsConditionalBranch()) {
417 : Successor::Condition inverse_condition =
418 E : Successor::InvertCondition(condition);
419 E : CHECK_NE(Successor::kInvalidCondition, inverse_condition)
420 : << "Non-invertible condition seen for branch instruction: "
421 i : << instruction.GetName() << ".";
422 :
423 : // Create an (unresolved) successor pointing to the next instruction.
424 E : BasicBlockReference ref(BlockGraph::PC_RELATIVE_REF,
425 : 1, // The size is irrelevant in successors.
426 : const_cast<Block*>(block_),
427 : next_instruction_offset,
428 : next_instruction_offset);
429 E : current_successors_.push_front(Successor(inverse_condition, ref, 0));
430 E : jump_targets_.insert(next_instruction_offset);
431 E : }
432 :
433 : // Attempt to figure out where the branch is going by finding a
434 : // reference inside the instruction's byte range.
435 E : BlockGraph::Reference ref;
436 E : bool found = GetReferenceOfInstructionAt(
437 : block_, offset, instruction.size(), &ref);
438 :
439 : // If a reference was found, prefer its destination information to the
440 : // information conveyed by the bytes in the instruction. This should
441 : // handle all inter-block jumps (thunks, tail-call elimination, etc).
442 : // Otherwise, create a reference into the current block.
443 E : if (found) {
444 : // This is an explicit branching instruction so we expect the reference to
445 : // be direct.
446 E : if (!ref.IsDirect()) {
447 i : VLOG(1) << "Encountered an explicit control flow instruction containing "
448 : << "an indirect reference.";
449 i : return false;
450 : }
451 E : } else {
452 : Offset target_offset =
453 E : next_instruction_offset + instruction.representation().imm.addr;
454 :
455 : // If we don't have a reference (coming from a fixup) for a PC-relative jump
456 : // then we expect its destination to be in the block. We only see otherwise
457 : // in assembly generated code where section contributions don't correspond
458 : // to entire function bodies.
459 E : if (target_offset < 0 ||
460 : static_cast<Size>(target_offset) >= block_->size()) {
461 i : VLOG(1) << "Unexpected PC-relative target offset is external to block.";
462 i : return false;
463 : }
464 :
465 E : ref = BlockGraph::Reference(BlockGraph::PC_RELATIVE_REF,
466 : 1, // Size is irrelevant in successors.
467 : const_cast<Block*>(block_),
468 : target_offset,
469 : target_offset);
470 : }
471 :
472 : // If the reference points to the current block, track the target offset.
473 E : if (ref.referenced() == block_)
474 E : jump_targets_.insert(ref.offset());
475 :
476 : // Create the successor, preserving the source range and label.
477 E : BasicBlockReference bb_ref(
478 : ref.type(), ref.size(), ref.referenced(), ref.offset(), ref.base());
479 E : Successor succ(condition, bb_ref, instruction.size());
480 E : succ.set_source_range(instruction.source_range());
481 E : succ.set_label(instruction.label());
482 E : current_successors_.push_front(succ);
483 :
484 : // Having just branched, we need to end the current basic block.
485 E : EndCurrentBasicBlock(next_instruction_offset);
486 E : return true;
487 E : }
488 :
489 E : bool BasicBlockDecomposer::EndCurrentBasicBlock(Offset end_offset) {
490 : // We have reached the end of the current walk or we handled a conditional
491 : // branch. Let's mark this as the end of a basic block.
492 E : int basic_block_size = end_offset - current_block_start_;
493 E : DCHECK_LT(0, basic_block_size);
494 E : if (!InsertBasicBlockRange(current_block_start_,
495 : basic_block_size,
496 : BasicBlock::BASIC_CODE_BLOCK)) {
497 i : return false;
498 : }
499 :
500 : // Remember the end offset as the start of the next basic block.
501 E : current_block_start_ = end_offset;
502 E : return true;
503 E : }
504 :
505 E : bool BasicBlockDecomposer::GetCodeRangeAndCreateDataBasicBlocks(Offset* end) {
506 E : DCHECK_NE(reinterpret_cast<Offset*>(NULL), end);
507 :
508 E : *end = 0;
509 :
510 : // By default, we assume the entire block is code.
511 E : Offset code_end = block_->size();
512 :
513 : // Iterate over all labels, looking for data labels.
514 : BlockGraph::Block::LabelMap::const_reverse_iterator it =
515 E : block_->labels().rbegin();
516 E : bool saw_non_data_label = false;
517 E : for (; it != block_->labels().rend(); ++it) {
518 E : const BlockGraph::Label& label = it->second;
519 E : if (label.has_attributes(BlockGraph::DATA_LABEL)) {
520 : // There should never be data labels beyond the end of the block.
521 E : if (it->first >= static_cast<Offset>(block_->size())) {
522 i : VLOG(1) << "Encountered a data label at offset " << it->first
523 : << "of block \"" << block_->name() << "\" of size "
524 : << block_->size() << ".";
525 i : return false;
526 : }
527 :
528 : // If a non-data label was already encountered, and now there's another
529 : // data label then bail: the block does not respect the 'code first,
530 : // data second' supported layout requirement.
531 E : if (saw_non_data_label) {
532 i : VLOG(1) << "Block \"" << block_->name() << "\" has an unsupported "
533 : << "code-data layout.";
534 i : VLOG(1) << "Unexpected data label at offset " << it->first << ".";
535 i : return false;
536 : }
537 :
538 : // Create a data block and update the end-of-code offset. This should
539 : // never fail because this is the first time blocks are being created and
540 : // they are strictly non-overlapping by the iteration logic of this
541 : // function.
542 E : size_t size = code_end - it->first;
543 E : CHECK(InsertBasicBlockRange(it->first, size,
544 : BasicBlock::BASIC_DATA_BLOCK));
545 E : code_end = it->first;
546 E : } else {
547 : // We ignore the debug-end label, as it can come after block data.
548 E : if (label.attributes() == BlockGraph::DEBUG_END_LABEL)
549 E : continue;
550 :
551 : // Remember that a non-data label was seen. No further data labels should
552 : // be encountered.
553 E : saw_non_data_label = true;
554 : }
555 E : }
556 :
557 E : *end = code_end;
558 :
559 E : return true;
560 E : }
561 :
562 E : bool BasicBlockDecomposer::ParseInstructions() {
563 : // Find the beginning and ending offsets of code bytes within the block.
564 E : Offset code_end_offset = 0;
565 E : if (!GetCodeRangeAndCreateDataBasicBlocks(&code_end_offset))
566 i : return false;
567 :
568 : // Initialize jump_targets_ to include un-discoverable targets.
569 E : InitJumpTargets(code_end_offset);
570 :
571 : // Disassemble the instruction stream into rudimentary basic blocks.
572 E : Offset offset = 0;
573 E : current_block_start_ = offset;
574 E : while (offset < code_end_offset) {
575 : // Decode the next instruction.
576 E : Instruction instruction;
577 E : if (!DecodeInstruction(offset, code_end_offset, &instruction))
578 E : return false;
579 :
580 : // Handle the decoded instruction.
581 E : if (!HandleInstruction(instruction, offset))
582 E : return false;
583 :
584 : // Advance the instruction offset.
585 E : offset += instruction.size();
586 E : }
587 :
588 : // If we get here then we must have successfully consumed the entire code
589 : // range; otherwise, we should have failed to decode a partial instruction.
590 E : CHECK_EQ(offset, code_end_offset);
591 :
592 : // If the last bb we were working on didn't end with a RET or branch then
593 : // we need to close it now. We can detect this if the current_block_start_
594 : // does not match the current (end) offset.
595 E : if (current_block_start_ != code_end_offset)
596 E : EndCurrentBasicBlock(code_end_offset);
597 :
598 E : return true;
599 E : }
600 :
601 E : bool BasicBlockDecomposer::Disassemble() {
602 : // Parse the code bytes into instructions and rudimentary basic blocks.
603 E : if (!ParseInstructions())
604 E : return false;
605 :
606 : // Everything below this point is simply book-keeping that can't fail. These
607 : // can safely be skipped in a dry-run.
608 E : if (scratch_subgraph_.get() != NULL)
609 E : return true;
610 :
611 : // Split the basic blocks at branch targets.
612 E : SplitCodeBlocksAtBranchTargets();
613 :
614 : // At this point we have basic blocks for all code and data. Now create a
615 : // basic-block to represent the end of the block. This will potentially carry
616 : // labels and references beyond the end of the block.
617 E : CHECK(InsertBasicBlockRange(block_->size(), 0, BasicBlock::BASIC_END_BLOCK));
618 :
619 : // By this point, we should have basic blocks for all visited code.
620 E : CheckAllJumpTargetsStartABasicCodeBlock();
621 :
622 : // We should now have contiguous block ranges that cover every byte in the
623 : // macro block. Verify that this is so.
624 E : CheckHasCompleteBasicBlockCoverage();
625 :
626 : // We should have propagated all of the labels in the original block into
627 : // the basic-block subgraph.
628 E : CheckAllLabelsArePreserved();
629 :
630 : // Populate the referrers in the basic block data structures by copying
631 : // them from the original source block.
632 E : CopyExternalReferrers();
633 :
634 : // Populate the references in the basic block data structures by copying
635 : // them from the original source block. This does not handle the successor
636 : // references.
637 E : CopyReferences();
638 :
639 : // Wire up the basic-block successors. These are not handled by
640 : // CopyReferences(), above.
641 E : ResolveSuccessors();
642 :
643 : // All the control flow we have derived should be valid.
644 E : CheckAllControlFlowIsValid();
645 :
646 : // Mark all unreachable code blocks as padding.
647 E : MarkUnreachableCodeAsPadding();
648 :
649 : // ... and we're done.
650 E : return true;
651 E : }
652 :
653 E : void BasicBlockDecomposer::CheckAllJumpTargetsStartABasicCodeBlock() const {
654 E : if (!check_decomposition_results_)
655 i : return;
656 :
657 E : JumpTargets::const_iterator offset_iter(jump_targets_.begin());
658 E : for (; offset_iter != jump_targets_.end(); ++offset_iter) {
659 : // The target basic-block should be a code basic-block.
660 E : BasicBlock* target_bb = GetBasicBlockAt(*offset_iter);
661 E : CHECK(target_bb != NULL);
662 E : CHECK_EQ(BasicBlock::BASIC_CODE_BLOCK, target_bb->type());
663 E : }
664 E : }
665 :
666 E : void BasicBlockDecomposer::CheckHasCompleteBasicBlockCoverage() const {
667 E : if (!check_decomposition_results_)
668 i : return;
669 :
670 : // Walk through the basic-block address space.
671 E : Offset next_start = 0;
672 E : RangeMapConstIter it(original_address_space_.begin());
673 E : for (; it != original_address_space_.end(); ++it) {
674 E : CHECK_EQ(it->first.start(), next_start);
675 E : CHECK_EQ(it->first.start(), it->second->offset());
676 :
677 E : size_t size = it->first.size();
678 :
679 E : BasicDataBlock* data_block = BasicDataBlock::Cast(it->second);
680 E : if (data_block != NULL) {
681 : // Data block's size should match the address segment exactly.
682 E : CHECK_EQ(size, data_block->size());
683 : }
684 :
685 E : BasicCodeBlock* code_block = BasicCodeBlock::Cast(it->second);
686 E : if (code_block != NULL) {
687 : // Code blocks may be short the trailing successor instruction.
688 E : BasicCodeBlock::Successors::const_iterator succ_it(
689 : code_block->successors().begin());
690 E : Size block_size = code_block->GetInstructionSize();
691 E : for (; succ_it != code_block->successors().end(); ++succ_it)
692 E : block_size += succ_it->instruction_size();
693 :
694 E : CHECK_GE(size, block_size);
695 : }
696 :
697 E : BasicEndBlock* end_block = BasicEndBlock::Cast(it->second);
698 E : if (end_block != NULL) {
699 E : CHECK_EQ(0u, end_block->size());
700 E : size = 0;
701 : }
702 :
703 : // The basic-block must have parsed as one of the fundamental types.
704 E : CHECK(data_block != NULL || code_block != NULL || end_block != NULL);
705 :
706 E : next_start += size;
707 E : }
708 :
709 : // At this point, if there were no gaps, next start will be the same as the
710 : // full size of the block we're decomposing.
711 E : CHECK_EQ(block_->size(), static_cast<size_t>(next_start));
712 E : }
713 :
714 E : void BasicBlockDecomposer::CheckAllControlFlowIsValid() const {
715 E : if (!check_decomposition_results_)
716 i : return;
717 :
718 : // Check that the subgraph is valid. This will make sure that the
719 : // instructions and successors generally make sense.
720 E : CHECK(subgraph_->IsValid());
721 :
722 : // The only thing left to check is that synthesized flow-through
723 : // successors refer to the adjacent basic-blocks.
724 E : RangeMapConstIter it(original_address_space_.begin());
725 E : for (; it != original_address_space_.end(); ++it) {
726 E : const BasicCodeBlock* bb = BasicCodeBlock::Cast(it->second);
727 E : if (bb == NULL)
728 E : continue;
729 :
730 E : const BasicBlock::Successors& successors = bb->successors();
731 :
732 : // There may be at most 2 successors.
733 E : switch (successors.size()) {
734 : case 0:
735 E : break;
736 :
737 : case 1:
738 : // If the successor is synthesized, then flow is from this basic-block
739 : // to the next adjacent one.
740 E : if (successors.back().instruction_size() == 0) {
741 E : RangeMapConstIter next(it);
742 E : ++next;
743 E : CHECK(next != original_address_space_.end());
744 E : CHECK_EQ(successors.back().reference().basic_block(), next->second);
745 : }
746 E : break;
747 :
748 : case 2: {
749 : // Exactly one of the successors should have been synthesized.
750 E : bool front_synthesized = successors.front().instruction_size() == 0;
751 E : bool back_synthesized = successors.back().instruction_size() == 0;
752 E : CHECK_NE(front_synthesized, back_synthesized);
753 :
754 : // The synthesized successor flows from this basic-block to the next
755 : // adjacent one.
756 E : const Successor& synthesized =
757 : front_synthesized ? successors.front() : successors.back();
758 E : RangeMapConstIter next(it);
759 E : ++next;
760 E : CHECK(next != original_address_space_.end());
761 E : CHECK_EQ(synthesized.reference().basic_block(), next->second);
762 E : break;
763 : }
764 :
765 : default:
766 i : NOTREACHED();
767 : }
768 E : }
769 E : }
770 :
771 E : void BasicBlockDecomposer::CheckAllLabelsArePreserved() const {
772 E : if (!check_decomposition_results_)
773 i : return;
774 :
775 E : const Block* original_block = subgraph_->original_block();
776 E : if (original_block == NULL)
777 i : return;
778 :
779 : // Remove any labels that fall *after* the given block. This can happen for
780 : // scope and debug-end labels when the function has no epilog. It is rare, but
781 : // has been observed in the wild.
782 : // TODO(chrisha): Find a way to preserve these. We may need the notion of an
783 : // empty basic-block which gets assigned the label, or we may need to
784 : // augment BBs/instructions with the ability to have two labels: one tied
785 : // to the beginning of the object, and one to the end.
786 : Block::LabelMap::const_iterator it_past_block_end =
787 E : original_block->labels().lower_bound(original_block->size());
788 :
789 : // Grab a copy of the original labels (except any that are beyond the end of
790 : // the block data). We will be matching against these to ensure that they are
791 : // preserved in the BB decomposition.
792 E : const Block::LabelMap original_labels(original_block->labels().begin(),
793 : it_past_block_end);
794 E : if (original_labels.empty())
795 E : return;
796 :
797 : // A map to track which labels (by offset) have been found in the subgraph.
798 E : std::map<Offset, bool> labels_found;
799 :
800 : // Initialize the map of labels found in the subgraph.
801 E : Block::LabelMap::const_iterator label_iter = original_labels.begin();
802 E : for (; label_iter != original_labels.end(); ++label_iter)
803 E : labels_found.insert(std::make_pair(label_iter->first, false));
804 :
805 : // Walk through the subgraph and mark all of the labels found.
806 : BasicBlockSubGraph::BBCollection::const_iterator bb_iter =
807 E : subgraph_->basic_blocks().begin();
808 E : for (; bb_iter != subgraph_->basic_blocks().end(); ++bb_iter) {
809 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(*bb_iter);
810 E : if (data_block != NULL) {
811 : // Account for labels attached to basic-blocks.
812 E : if (data_block->has_label()) {
813 E : BlockGraph::Label label;
814 E : CHECK(original_block->GetLabel(data_block->offset(), &label));
815 E : CHECK(data_block->label() == label);
816 E : labels_found[data_block->offset()] = true;
817 E : }
818 : }
819 :
820 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(*bb_iter);
821 E : if (code_block != NULL) {
822 : // Account for labels attached to instructions.
823 : BasicBlock::Instructions::const_iterator inst_iter =
824 E : code_block->instructions().begin();
825 E : Offset inst_offset = code_block->offset();
826 E : for (; inst_iter != code_block->instructions().end(); ++inst_iter) {
827 E : const Instruction& inst = *inst_iter;
828 E : if (inst.has_label()) {
829 E : BlockGraph::Label label;
830 E : CHECK(original_block->GetLabel(inst_offset, &label));
831 E : CHECK(inst.label() == label);
832 E : labels_found[inst_offset] = true;
833 E : }
834 E : inst_offset += inst.size();
835 E : }
836 :
837 : // Account for labels attached to successors.
838 : BasicBlock::Successors::const_iterator succ_iter =
839 E : code_block->successors().begin();
840 E : for (; succ_iter != code_block->successors().end(); ++succ_iter) {
841 E : const Successor& succ = *succ_iter;
842 E : if (succ.has_label()) {
843 E : BlockGraph::Label label;
844 E : CHECK_NE(0U, succ.instruction_size());
845 E : CHECK(original_block->GetLabel(inst_offset, &label));
846 E : CHECK(succ.label() == label);
847 E : labels_found[inst_offset] = true;
848 E : }
849 E : inst_offset += succ.instruction_size();
850 E : }
851 : }
852 E : }
853 :
854 : // We should have the right number of labels_found (check if we added
855 : // something to the wrong place).
856 E : CHECK_EQ(original_labels.size(), labels_found.size());
857 :
858 : // Make sure all of the items in labels_found have been set to true.
859 E : std::map<Offset, bool>::const_iterator found_iter = labels_found.begin();
860 E : for (; found_iter != labels_found.end(); ++found_iter) {
861 E : CHECK(found_iter->second);
862 E : }
863 E : }
864 :
865 : bool BasicBlockDecomposer::InsertBasicBlockRange(Offset offset,
866 : size_t size,
867 E : BasicBlockType type) {
868 E : DCHECK_LE(0, offset);
869 E : DCHECK_LE(offset + size, block_->size());
870 E : DCHECK(type == BasicBlock::BASIC_CODE_BLOCK || current_instructions_.empty());
871 E : DCHECK(type == BasicBlock::BASIC_CODE_BLOCK || current_successors_.empty());
872 :
873 : // Find or create a name for this basic block. Reserve the label, if any,
874 : // to propagate to the basic block if there are no instructions in the
875 : // block to carry the label(s).
876 E : BlockGraph::Label label;
877 E : std::string basic_block_name;
878 E : bool have_label = block_->GetLabel(offset, &label);
879 E : if (have_label) {
880 E : basic_block_name = label.ToString();
881 E : } else {
882 E : basic_block_name =
883 : base::StringPrintf("<%s+%04X-%s>",
884 : block_->name().c_str(),
885 : offset,
886 : BasicBlock::BasicBlockTypeToString(type));
887 : }
888 :
889 : // Pre-flight address space insertion to make sure there's no
890 : // pre-existing conflicting range.
891 E : Range byte_range(offset, size);
892 E : if (original_address_space_.FindFirstIntersection(byte_range) !=
893 : original_address_space_.end()) {
894 i : LOG(ERROR) << "Attempted to insert overlapping basic block.";
895 i : return false;
896 : }
897 :
898 E : if (type == BasicBlock::BASIC_CODE_BLOCK) {
899 E : DCHECK_LT(0u, size);
900 :
901 : // Create the code block.
902 E : BasicCodeBlock* code_block = subgraph_->AddBasicCodeBlock(basic_block_name);
903 E : if (code_block == NULL)
904 i : return false;
905 E : CHECK(original_address_space_.Insert(byte_range, code_block));
906 :
907 : // Populate code basic-block with instructions and successors.
908 E : code_block->set_offset(offset);
909 E : code_block->instructions().swap(current_instructions_);
910 E : code_block->successors().swap(current_successors_);
911 E : } else if (type == BasicBlock::BASIC_DATA_BLOCK) {
912 E : DCHECK_LT(0u, size);
913 :
914 : // Create the data block.
915 E : BasicDataBlock* data_block = subgraph_->AddBasicDataBlock(
916 : basic_block_name, size, block_->data() + offset);
917 E : if (data_block == NULL)
918 i : return false;
919 E : CHECK(original_address_space_.Insert(byte_range, data_block));
920 :
921 : // Capture the source range (if any) for the data block.
922 E : data_block->set_source_range(GetSourceRange(offset, size));
923 :
924 : // Data basic-blocks carry their labels at the head of the basic blocks.
925 : // A padding basic-block might also be labeled if the block contains
926 : // unreachable code (for example, INT3 or NOP instructions following a call
927 : // to a non-returning function).
928 E : data_block->set_offset(offset);
929 E : if (have_label)
930 E : data_block->set_label(label);
931 E : } else {
932 E : DCHECK_EQ(0u, size);
933 E : DCHECK_EQ(BasicBlock::BASIC_END_BLOCK, type);
934 :
935 : // Create the end block.
936 E : BasicEndBlock* end_block = subgraph_->AddBasicEndBlock();
937 E : if (end_block == NULL)
938 i : return false;
939 :
940 : // We insert the basic end block with a size of 1, as the address space
941 : // does not support empty blocks. However, the block itself has no length.
942 : // This is only for internal book-keeping, and does not affect the
943 : // BasicBlockSubGraph representation.
944 E : CHECK(original_address_space_.Insert(Range(offset, 1), end_block));
945 :
946 : // Set the offset and any labels.
947 E : end_block->set_offset(offset);
948 E : if (have_label)
949 E : end_block->set_label(label);
950 : }
951 :
952 E : return true;
953 E : }
954 :
955 E : void BasicBlockDecomposer::SplitCodeBlocksAtBranchTargets() {
956 E : JumpTargets::const_iterator jump_target_iter(jump_targets_.begin());
957 E : for (; jump_target_iter != jump_targets_.end(); ++jump_target_iter) {
958 : // Resolve the target basic-block.
959 E : Offset target_offset = *jump_target_iter;
960 E : BasicBlock* target_bb = NULL;
961 E : Range target_bb_range;
962 E : CHECK(FindBasicBlock(target_offset, &target_bb, &target_bb_range));
963 :
964 : // If we're jumping to the start of a basic block, there isn't any work
965 : // to do.
966 E : if (target_offset == target_bb_range.start())
967 E : continue;
968 :
969 : // The target must be a code block.
970 E : BasicCodeBlock* target_code_block = BasicCodeBlock::Cast(target_bb);
971 E : CHECK(target_code_block != NULL);
972 :
973 : // Otherwise, we have found a basic-block that we need to split.
974 : // Let's contract the range the original occupies in the basic-block
975 : // address space, then add a second block at the target offset.
976 E : size_t left_split_size = target_offset - target_bb_range.start();
977 E : bool removed = original_address_space_.Remove(target_bb_range);
978 E : DCHECK(removed);
979 :
980 E : Range left_split_range(target_bb_range.start(), left_split_size);
981 : bool inserted =
982 E : original_address_space_.Insert(left_split_range, target_code_block);
983 E : DCHECK(inserted);
984 :
985 : // Now we split up containing_range into two new ranges and replace
986 : // containing_range with the two new entries.
987 :
988 : // Slice the trailing half of the instructions and the successors
989 : // off the block.
990 E : DCHECK(current_instructions_.empty());
991 E : DCHECK(current_successors_.empty());
992 E : bool split = SplitInstructionListAt(left_split_size,
993 : &target_code_block->instructions(),
994 : ¤t_instructions_);
995 E : DCHECK(split);
996 E : target_code_block->successors().swap(current_successors_);
997 :
998 : // Set-up the flow-through successor for the first "half".
999 E : BasicBlockReference ref(BlockGraph::PC_RELATIVE_REF,
1000 : 1, // Size is immaterial in successors.
1001 : const_cast<Block*>(block_),
1002 : target_offset,
1003 : target_offset);
1004 E : target_code_block->successors().push_back(
1005 : Successor(Successor::kConditionTrue, ref, 0));
1006 :
1007 : // This shouldn't fail because the range used to exist, and we just resized
1008 : // it.
1009 E : CHECK(InsertBasicBlockRange(target_offset,
1010 : target_bb_range.size() - left_split_size,
1011 : target_code_block->type()));
1012 E : }
1013 E : }
1014 :
1015 E : void BasicBlockDecomposer::CopyExternalReferrers() {
1016 E : const BlockGraph::Block::ReferrerSet& referrers = block_->referrers();
1017 E : BlockGraph::Block::ReferrerSet::const_iterator iter = referrers.begin();
1018 E : for (; iter != referrers.end(); ++iter) {
1019 : // Find the reference this referrer record describes.
1020 E : const BlockGraph::Block* referrer = iter->first;
1021 E : DCHECK(referrer != NULL);
1022 :
1023 : // We only care about external referrers.
1024 E : if (referrer == block_)
1025 E : continue;
1026 :
1027 : // This is an external referrer. Find the reference in the referring block.
1028 E : Offset source_offset = iter->second;
1029 E : BlockGraph::Reference reference;
1030 E : bool found = referrer->GetReference(source_offset, &reference);
1031 E : DCHECK(found);
1032 :
1033 : // Find the basic block the reference refers to.
1034 E : BasicBlock* target_bb = GetBasicBlockAt(reference.base());
1035 E : DCHECK(target_bb != NULL);
1036 :
1037 : // Insert the referrer into the target bb's referrer set. Note that there
1038 : // is no corresponding reference update to the referring block. The
1039 : // target bb will track these so a BlockBuilder can properly update
1040 : // the referrers when merging a subgraph back into the block-graph.
1041 : bool inserted = target_bb->referrers().insert(
1042 E : BasicBlockReferrer(referrer, source_offset)).second;
1043 E : DCHECK(inserted);
1044 E : }
1045 E : }
1046 :
1047 : void BasicBlockDecomposer::CopyReferences(
1048 E : Offset item_offset, Size item_size, BasicBlockReferenceMap* refs) {
1049 E : DCHECK_LE(0, item_offset);
1050 E : DCHECK_LT(0U, item_size);
1051 E : DCHECK(refs != NULL);
1052 :
1053 : // Figure out the bounds of item.
1054 E : BlockGraph::Offset end_offset = item_offset + item_size;
1055 :
1056 : // Get iterators encompassing all references within the bounds of item.
1057 : BlockGraph::Block::ReferenceMap::const_iterator ref_iter =
1058 E : block_->references().lower_bound(item_offset);
1059 : BlockGraph::Block::ReferenceMap::const_iterator end_iter =
1060 E : block_->references().lower_bound(end_offset);
1061 :
1062 E : for (; ref_iter != end_iter; ++ref_iter) {
1063 : // Calculate the local offset of this reference within item.
1064 E : BlockGraph::Offset local_offset = ref_iter->first - item_offset;
1065 E : const BlockGraph::Reference& reference = ref_iter->second;
1066 :
1067 : // We expect long references for everything except flow control.
1068 E : CHECK_EQ(4U, reference.size());
1069 E : DCHECK_LE(local_offset + reference.size(), static_cast<Size>(end_offset));
1070 :
1071 E : if (reference.referenced() != block_) {
1072 : // For external references, we can directly reference the other block.
1073 : bool inserted = refs->insert(std::make_pair(
1074 : local_offset,
1075 : BasicBlockReference(reference.type(), reference.size(),
1076 : reference.referenced(), reference.offset(),
1077 E : reference.base()))).second;
1078 E : DCHECK(inserted);
1079 E : } else {
1080 : // For intra block_ references, find the corresponding basic block in
1081 : // the basic block address space.
1082 E : BasicBlock* target_bb = GetBasicBlockAt(reference.base());
1083 E : DCHECK(target_bb != NULL);
1084 :
1085 : // Create target basic-block relative values for the base and offset.
1086 : // TODO(chrisha): Make BasicBlockReferences handle indirect references.
1087 E : CHECK_EQ(reference.offset(), reference.base());
1088 :
1089 : // Insert a reference to the target basic block.
1090 : bool inserted = refs->insert(std::make_pair(
1091 : local_offset,
1092 : BasicBlockReference(reference.type(),
1093 : reference.size(),
1094 E : target_bb))).second;
1095 E : DCHECK(inserted);
1096 : }
1097 E : }
1098 E : }
1099 :
1100 E : void BasicBlockDecomposer::CopyReferences() {
1101 : // Copy the references for the source range of each basic-block (by
1102 : // instruction for code basic-blocks). External referrers and successors are
1103 : // handled in separate passes.
1104 : BasicBlockSubGraph::BBCollection::iterator bb_iter =
1105 E : subgraph_->basic_blocks().begin();
1106 E : for (; bb_iter != subgraph_->basic_blocks().end(); ++bb_iter) {
1107 E : BasicCodeBlock* code_block = BasicCodeBlock::Cast(*bb_iter);
1108 E : if (code_block != NULL) {
1109 E : DCHECK_EQ(BasicBlock::BASIC_CODE_BLOCK, code_block->type());
1110 :
1111 E : Offset inst_offset = code_block->offset();
1112 : BasicBlock::Instructions::iterator inst_iter =
1113 E : code_block->instructions().begin();
1114 E : for (; inst_iter != code_block->instructions().end(); ++inst_iter) {
1115 E : CopyReferences(inst_offset,
1116 : inst_iter->size(),
1117 : &inst_iter->references());
1118 E : inst_offset += inst_iter->size();
1119 E : }
1120 : }
1121 :
1122 E : BasicDataBlock* data_block = BasicDataBlock::Cast(*bb_iter);
1123 E : if (data_block != NULL) {
1124 E : DCHECK_NE(BasicBlock::BASIC_CODE_BLOCK, data_block->type());
1125 E : CopyReferences(data_block->offset(),
1126 : data_block->size(),
1127 : &data_block->references());
1128 : }
1129 E : }
1130 E : }
1131 :
1132 E : void BasicBlockDecomposer::ResolveSuccessors() {
1133 : BasicBlockSubGraph::BBCollection::iterator bb_iter =
1134 E : subgraph_->basic_blocks().begin();
1135 E : for (; bb_iter != subgraph_->basic_blocks().end(); ++bb_iter) {
1136 : // Only code basic-blocks have successors and instructions.
1137 E : BasicCodeBlock* code_block = BasicCodeBlock::Cast(*bb_iter);
1138 E : if (code_block == NULL)
1139 E : continue;
1140 :
1141 : BasicBlock::Successors::iterator succ_iter =
1142 E : code_block->successors().begin();
1143 : BasicBlock::Successors::iterator succ_iter_end =
1144 E : code_block->successors().end();
1145 E : for (; succ_iter != succ_iter_end; ++succ_iter) {
1146 E : if (succ_iter->reference().block() != block_)
1147 E : continue;
1148 :
1149 : // Find the basic block the successor references.
1150 : BasicBlock* target_code_block =
1151 E : GetBasicBlockAt(succ_iter->reference().offset());
1152 E : DCHECK(target_code_block != NULL);
1153 :
1154 : // We transform all successor branches into 4-byte pc-relative targets.
1155 E : succ_iter->set_reference(
1156 : BasicBlockReference(
1157 : BlockGraph::PC_RELATIVE_REF, 4, target_code_block));
1158 E : DCHECK(succ_iter->reference().IsValid());
1159 E : }
1160 E : }
1161 E : }
1162 :
1163 E : void BasicBlockDecomposer::MarkUnreachableCodeAsPadding() {
1164 E : BasicBlockSubGraph::ReachabilityMap rm;
1165 E : subgraph_->GetReachabilityMap(&rm);
1166 E : DCHECK_EQ(rm.size(), subgraph_->basic_blocks().size());
1167 : BasicBlockSubGraph::BBCollection::iterator bb_iter =
1168 E : subgraph_->basic_blocks().begin();
1169 E : for (; bb_iter != subgraph_->basic_blocks().end(); ++bb_iter) {
1170 E : BasicCodeBlock* code_bb = BasicCodeBlock::Cast(*bb_iter);
1171 E : if (code_bb != NULL) {
1172 E : if (!subgraph_->IsReachable(rm, code_bb))
1173 E : code_bb->MarkAsPadding();
1174 : }
1175 E : }
1176 E : }
1177 :
1178 : } // namespace block_graph
|