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 the BlockBuilder class.
16 : //
17 : // TODO(rogerm): Revisit the BasicBlockDecomposer/BlockBuilder interface
18 : // via the BasicBlockSubgraph. Consider copying out the block data into
19 : // the subgraph instead of having it reference the original block.
20 :
21 : #include "syzygy/block_graph/block_builder.h"
22 :
23 : #include <limits>
24 : #include <map>
25 : #include <utility>
26 : #include <vector>
27 :
28 : #include "syzygy/block_graph/basic_block.h"
29 : #include "syzygy/block_graph/basic_block_assembler.h"
30 : #include "syzygy/block_graph/basic_block_subgraph.h"
31 : #include "syzygy/block_graph/block_graph.h"
32 : #include "syzygy/common/align.h"
33 : #include "syzygy/core/assembler.h"
34 :
35 : namespace block_graph {
36 :
37 : namespace {
38 :
39 : // A bunch of handy typedefs for some verbose types.
40 : typedef BlockGraph::Block Block;
41 : typedef BlockGraph::Offset Offset;
42 : typedef BlockGraph::Size Size;
43 : typedef BasicBlockSubGraph::BlockDescription BlockDescription;
44 : typedef BasicBlockSubGraph::BlockDescriptionList BlockDescriptionList;
45 : typedef BasicBlockSubGraph::BasicBlockOrdering BasicBlockOrdering;
46 : typedef BasicBlockOrdering::const_iterator BasicBlockOrderingConstIter;
47 : typedef BlockDescriptionList::const_iterator BlockDescriptionConstIter;
48 : typedef BasicBlock::Instructions::const_iterator InstructionConstIter;
49 : typedef BasicBlock::Successors::const_iterator SuccessorConstIter;
50 :
51 : // Definitions of various length NOP codes for 32-bit X86. We use the same
52 : // ones that are typically used by MSVC and recommended by Intel.
53 :
54 : // NOP (XCHG EAX, EAX)
55 : const uint8 kNop1[1] = { 0x90 };
56 : // 66 NOP
57 : const uint8 kNop2[2] = { 0x66, 0x90 };
58 : // LEA REG, 0 (REG) (8-bit displacement)
59 : const uint8 kNop3[3] = { 0x66, 0x66, 0x90 };
60 : // NOP DWORD PTR [EAX + 0] (8-bit displacement)
61 : const uint8 kNop4[4] = { 0x0F, 0x1F, 0x40, 0x00 };
62 : // NOP DWORD PTR [EAX + EAX*1 + 0] (8-bit displacement)
63 : const uint8 kNop5[5] = { 0x0F, 0x1F, 0x44, 0x00, 0x00 };
64 : // LEA REG, 0 (REG) (32-bit displacement)
65 : const uint8 kNop6[6] = { 0x66, 0x0F, 0x1F, 0x44, 0x00, 0x00 };
66 : // LEA REG, 0 (REG) (32-bit displacement)
67 : const uint8 kNop7[7] = { 0x0F, 0x1F, 0x80, 0x00, 0x00, 0x00, 0x00 };
68 : // NOP DWORD PTR [EAX + EAX*1 + 0] (32-bit displacement)
69 : const uint8 kNop8[8] = { 0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };
70 : // NOP WORD PTR [EAX + EAX*1 + 0] (32-bit displacement)
71 : const uint8 kNop9[9] = { 0x66, 0x0F, 0x1F, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 };
72 :
73 : // Collect all of the various NOPs in an array indexable by their length.
74 : const uint8* kNops[] = { NULL, kNop1, kNop2, kNop3, kNop4, kNop5, kNop6,
75 : kNop7, kNop8, kNop9 };
76 :
77 : // A utility class to package up the context in which new blocks are generated.
78 : class MergeContext {
79 : public:
80 : // Initialize a MergeContext with the block graph and original block.
81 E : MergeContext(BlockGraph* bg, const Block* ob)
82 : : sub_graph_(NULL), block_graph_(bg), original_block_(ob) {
83 E : DCHECK(bg != NULL);
84 E : }
85 :
86 : // Accessor.
87 E : const BlockVector& new_blocks() const { return new_blocks_; }
88 :
89 : // Generate all of the blocks described in @p subgraph.
90 : // @param subgraph Defines the block properties and basic blocks to use
91 : // for each of the blocks to be created.
92 : bool GenerateBlocks(const BasicBlockSubGraph& subgraph);
93 :
94 : // Transfers incoming references from the original block to the
95 : // newly generated block or blocks.
96 : // @param subgraph The subgraph.
97 : void TransferReferrers(const BasicBlockSubGraph* subgraph) const;
98 :
99 : // A clean-up function to remove the original block from which @p subgraph
100 : // is derived (if any) from the block graph. This must only be performed
101 : // after having updated the block graph with the new blocks and transferred
102 : // all references to the new block(s).
103 : // @param subgraph The subgraph.
104 : void RemoveOriginalBlock(BasicBlockSubGraph* subgraph);
105 :
106 : private:
107 : typedef BlockGraph::Block::SourceRange SourceRange;
108 :
109 : // Temporary data structures used during layouting.
110 : struct SuccessorLayoutInfo {
111 : // The condition flags for this successor.
112 : // Set to Successor::kInvalidCondition if unused.
113 : Successor::Condition condition;
114 : // The reference this condition refers to.
115 : BasicBlockReference reference;
116 : // The size of this successor's manifestation.
117 : Size size;
118 : };
119 : struct BasicBlockLayoutInfo {
120 : // The basic block this layout info concerns. Useful for debugging.
121 : const BasicBlock* basic_block;
122 :
123 : // Stores the block that basic_block will be manifested in.
124 : Block* block;
125 :
126 : // Current start offset for basic_block in block.
127 : Offset start_offset;
128 :
129 : // Size of basic_block.
130 : Size basic_block_size;
131 :
132 : // The label to assign our successor(s), if any.
133 : BlockGraph::Label successor_label;
134 :
135 : // The source range this successor originally occupied, if any.
136 : SourceRange successor_source_range;
137 :
138 : // Layout info for this block's successors.
139 : SuccessorLayoutInfo successors[2];
140 : };
141 : typedef std::map<const BasicBlock*, BasicBlockLayoutInfo>
142 : BasicBlockLayoutInfoMap;
143 :
144 : // Update the new block with the source range for the bytes in the
145 : // range [new_offset, new_offset + new_size).
146 : // @param source_range The source range (if any) to assign.
147 : // @param new_offset The offset in the new block where the original bytes
148 : // will now live.
149 : // @param new_block The block to change.
150 : // @param new_size The number of bytes the new range occupies.
151 : void CopySourceRange(const SourceRange& source_range,
152 : Offset new_offset,
153 : Size new_size,
154 : Block* new_block);
155 :
156 : // Copy @p references to @p new_block, starting at @p offset.
157 : // @param references The references to copy.
158 : // @param offset The starting offset in @p new_block to copy to.
159 : // @param new_block The block to copy the references to.
160 : // @pre Layouting has been done for all referred basic blocks.
161 : void CopyReferences(const BasicBlock::BasicBlockReferenceMap& references,
162 : Offset offset,
163 : Block* new_block);
164 :
165 : // Assemble the instruction(s) to implement the successors in @p info.
166 : // @param info The layout info for the basic block in question.
167 : bool AssembleSuccessors(const BasicBlockLayoutInfo& info);
168 :
169 : // Insert NOPs into the given byte range.
170 : // @param offset the offset at which to insert NOPs.
171 : // @param bytes the number of NOP bytes to insert.
172 : // @param new_block the block in which to insert the NOPs.
173 : bool InsertNops(Offset offset,
174 : Size bytes,
175 : Block* new_block);
176 :
177 : // Copy the given @p instructions to the current working block.
178 : // @param offset The offset where the @p instructions should be inserted.
179 : // @param instructions The instructions to copy.
180 : bool CopyInstructions(const BasicBlock::Instructions& instructions,
181 : Offset offset,
182 : Block* new_block);
183 :
184 : // Copy the data (or padding bytes) in @p basic_block into new working block.
185 : // @param offset The offset where the @p basic_block should be inserted.
186 : // @param basic_block The basic_block to copy.
187 : bool CopyData(const BasicDataBlock* basic_block,
188 : Offset offset,
189 : Block* new_block);
190 :
191 : // Initializes layout information for @p order and stores it in layout_info_.
192 : // @param order The basic block ordering to process.
193 : // @param block The destination block for this ordering.
194 : bool InitializeBlockLayout(const BasicBlockOrdering& order, Block* block);
195 :
196 : // Generates a layout for @p order. This layout will arrange each basic block
197 : // in the ordering back-to-back with minimal reach encodings on each
198 : // successor, while respecting basic block alignments.
199 : // @param order The basic block ordering to process.
200 : bool GenerateBlockLayout(const BasicBlockOrdering& order);
201 :
202 : // Generates a layout for @p subgraph and stores it in layout_info_.
203 : // @param subgraph The subgraph to process.
204 : bool GenerateLayout(const BasicBlockSubGraph& subgraph);
205 :
206 : // Populate a new block with data and/or instructions per
207 : // its corresponding layout.
208 : // @param order their ordering.
209 : bool PopulateBlock(const BasicBlockOrdering& order);
210 :
211 : // Populate all new blocks with data and/or instructions per layout_info_.
212 : // @param order their ordering.
213 : // @param new_block The resultant block.
214 : bool PopulateBlocks(const BasicBlockSubGraph& subgraph);
215 :
216 : // Transfer all external referrers that refer to @p bb to point to
217 : // bb's new location instead of to the original block.
218 : // @param bb The basic block.
219 : void UpdateReferrers(const BasicBlock* bb) const;
220 :
221 : // Returns the minimal successor size for @p condition.
222 : static Size GetShortSuccessorSize(Successor::Condition condition);
223 : // Returns the maximal successor size for @p condition.
224 : static Size GetLongSuccessorSize(Successor::Condition condition);
225 :
226 : // Computes and returns the required successor size for @p successor.
227 : // @param info The layout info for the basic block.
228 : // @param start_offset Offset from the start of @p info.basic_block to
229 : // the first byte of the successor.
230 : // @param successor The successor to size.
231 : Size ComputeRequiredSuccessorSize(const BasicBlockLayoutInfo& info,
232 : Offset start_offset,
233 : const SuccessorLayoutInfo& successor);
234 :
235 : // Finds the layout info for a given basic block.
236 : // @param bb The basic block whose layout info is desired.
237 : BasicBlockLayoutInfo& FindLayoutInfo(const BasicBlock* bb);
238 : const BasicBlockLayoutInfo& FindLayoutInfo(const BasicBlock* bb) const;
239 :
240 : // Resolves a basic block reference to a block reference.
241 : // @param type The desired type of the returned reference.
242 : // @param size The desired size of the returned reference.
243 : // @param ref The basic block reference to resolve.
244 : // @pre GenerateLayout has succeeded.
245 : BlockGraph::Reference ResolveReference(BlockGraph::ReferenceType type,
246 : Size size,
247 : const BasicBlockReference& ref) const;
248 :
249 : // Resolves a basic block reference to a block reference.
250 : // @param ref The basic block reference to resolve.
251 : // @pre GenerateLayout has succeeded.
252 : BlockGraph::Reference ResolveReference(const BasicBlockReference& ref) const;
253 :
254 : private:
255 : // The subgraph we're layouting.
256 : const BasicBlockSubGraph* sub_graph_;
257 :
258 : // Layout info.
259 : BasicBlockLayoutInfoMap layout_info_;
260 :
261 : // The block graph in which the new blocks are generated.
262 : BlockGraph* const block_graph_;
263 :
264 : // The original block from which the new blocks are derived.
265 : const Block* const original_block_;
266 :
267 : // The set of blocks generated in this context so far.
268 : BlockVector new_blocks_;
269 :
270 : DISALLOW_COPY_AND_ASSIGN(MergeContext);
271 : };
272 :
273 E : bool MergeContext::GenerateBlocks(const BasicBlockSubGraph& subgraph) {
274 E : sub_graph_ = &subgraph;
275 :
276 E : if (!GenerateLayout(subgraph) || !PopulateBlocks(subgraph)) {
277 : // Remove generated blocks (this is safe as they're all disconnected)
278 : // and return false.
279 i : BlockVector::iterator it = new_blocks_.begin();
280 i : for (; it != new_blocks_.end(); ++it) {
281 i : DCHECK((*it)->referrers().empty());
282 i : DCHECK((*it)->references().empty());
283 i : block_graph_->RemoveBlock(*it);
284 i : }
285 i : new_blocks_.clear();
286 :
287 i : sub_graph_ = NULL;
288 i : return false;
289 : }
290 :
291 E : sub_graph_ = NULL;
292 E : return true;
293 E : }
294 :
295 E : void MergeContext::TransferReferrers(const BasicBlockSubGraph* subgraph) const {
296 : // Iterate through the layout info, and update each referenced BB.
297 E : BasicBlockLayoutInfoMap::const_iterator it = layout_info_.begin();
298 E : for (; it != layout_info_.end(); ++it)
299 E : UpdateReferrers(it->second.basic_block);
300 E : }
301 :
302 : void MergeContext::CopySourceRange(const SourceRange& source_range,
303 : Offset new_offset,
304 : Size new_size,
305 E : Block* new_block) {
306 E : DCHECK_LE(0, new_offset);
307 E : DCHECK_NE(0U, new_size);
308 :
309 : // If the range is empty, there's nothing to do.
310 E : if (source_range.size() == 0) {
311 E : return;
312 : }
313 :
314 : // Insert the new source range mapping into the new block.
315 : bool inserted = new_block->source_ranges().Insert(
316 E : Block::DataRange(new_offset, new_size), source_range);
317 E : DCHECK(inserted);
318 E : }
319 :
320 E : bool MergeContext::AssembleSuccessors(const BasicBlockLayoutInfo& info) {
321 E : BasicBlock::Instructions instructions;
322 : BasicBlockAssembler assm(info.start_offset + info.basic_block_size,
323 E : instructions.begin(), &instructions);
324 :
325 : // Copy the successor label, if any, to where it belongs.
326 E : if (info.successor_label.IsValid()) {
327 : info.block->SetLabel(info.start_offset + info.basic_block_size,
328 E : info.successor_label);
329 : }
330 :
331 E : Offset successor_start = info.start_offset + info.basic_block_size;
332 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
333 E : const SuccessorLayoutInfo& successor = info.successors[i];
334 :
335 : // Exit loop early if appropriate.
336 E : if (successor.condition == Successor::kInvalidCondition)
337 E : break;
338 :
339 : // Default to a short reference.
340 E : ValueSize reference_size = core::kSize8Bit;
341 E : if (successor.size != GetShortSuccessorSize(successor.condition))
342 E : reference_size = core::kSize32Bit;
343 :
344 : // Construct the reference we're going to deposit into the instruction
345 : // list first.
346 E : UntypedReference untyped_ref(successor.reference);
347 :
348 : // For debugging, we stomp the correct offset into the re-generated block
349 : // for block-internal references.
350 E : BlockGraph::Reference resolved_ref = ResolveReference(successor.reference);
351 :
352 : // Default to the offset immediately following the successor, which
353 : // will translate to a zero pc-relative offset.
354 E : Offset ref_offset = successor_start + successor.size;
355 E : if (resolved_ref.referenced() == info.block)
356 E : ref_offset = resolved_ref.offset();
357 E : Immediate dest(ref_offset, reference_size, untyped_ref);
358 :
359 : // Assemble the instruction.
360 E : switch (successor.condition) {
361 : case Successor::kConditionAbove:
362 : case Successor::kConditionAboveOrEqual:
363 : case Successor::kConditionBelow:
364 : case Successor::kConditionBelowOrEqual:
365 : case Successor::kConditionEqual:
366 : case Successor::kConditionGreater:
367 : case Successor::kConditionGreaterOrEqual:
368 : case Successor::kConditionLess:
369 : case Successor::kConditionLessOrEqual:
370 : case Successor::kConditionNotEqual:
371 : case Successor::kConditionNotOverflow:
372 : case Successor::kConditionNotParity:
373 : case Successor::kConditionNotSigned:
374 : case Successor::kConditionOverflow:
375 : case Successor::kConditionParity:
376 : case Successor::kConditionSigned:
377 E : assm.j(static_cast<core::ConditionCode>(successor.condition), dest);
378 E : break;
379 :
380 : case Successor::kConditionTrue:
381 E : assm.jmp(dest);
382 E : break;
383 :
384 : default:
385 i : NOTREACHED();
386 i : return false;
387 : }
388 :
389 : // Make sure the assembler produced what we expected.
390 E : DCHECK_EQ(successor.size, instructions.back().size());
391 :
392 : // Walk our start address forwards.
393 E : successor_start += successor.size;
394 :
395 E : if (info.successor_source_range.size() != 0) {
396 E : Instruction& instr = instructions.back();
397 :
398 : // Attribute this instruction to the original successor's source range.
399 E : instr.set_source_range(info.successor_source_range);
400 : }
401 E : }
402 :
403 E : if (!instructions.empty()) {
404 E : Offset start_offset = info.start_offset + info.basic_block_size;
405 E : return CopyInstructions(instructions, start_offset, info.block);
406 : }
407 :
408 E : return true;
409 E : }
410 :
411 : bool MergeContext::InsertNops(Offset offset,
412 : Size bytes,
413 E : Block* new_block) {
414 E : DCHECK(new_block != NULL);
415 :
416 E : uint8* buffer = new_block->GetMutableData();
417 E : DCHECK(buffer != NULL);
418 :
419 E : size_t kMaxNopLength = arraysize(kNops) - 1;
420 E : buffer += offset;
421 E : while (bytes >= kMaxNopLength) {
422 i : ::memcpy(buffer, kNops[kMaxNopLength], kMaxNopLength);
423 i : buffer += kMaxNopLength;
424 i : bytes -= kMaxNopLength;
425 i : }
426 :
427 E : if (bytes > 0) {
428 E : DCHECK_GT(kMaxNopLength, bytes);
429 E : ::memcpy(buffer, kNops[bytes], bytes);
430 : }
431 :
432 E : return true;
433 E : }
434 :
435 : bool MergeContext::CopyInstructions(
436 : const BasicBlock::Instructions& instructions,
437 E : Offset offset, Block* new_block) {
438 E : DCHECK(new_block != NULL);
439 E : DCHECK_EQ(BasicBlock::BASIC_CODE_BLOCK, new_block->type());
440 : // Get the target buffer.
441 E : uint8* buffer = new_block->GetMutableData();
442 E : DCHECK(buffer != NULL);
443 :
444 : // Copy the instruction data and assign each instruction an offset.
445 E : InstructionConstIter it = instructions.begin();
446 E : for (; it != instructions.end(); ++it) {
447 E : const Instruction& instruction = *it;
448 :
449 : // Copy the instruction bytes.
450 : ::memcpy(buffer + offset,
451 : instruction.data(),
452 E : instruction.size());
453 :
454 : // Preserve the label on the instruction, if any.
455 E : if (instruction.has_label())
456 E : new_block->SetLabel(offset, instruction.label());
457 :
458 : // Record the source range.
459 : CopySourceRange(instruction.source_range(),
460 : offset, instruction.size(),
461 E : new_block);
462 :
463 : // Copy references.
464 E : CopyReferences(instruction.references(), offset, new_block);
465 :
466 : // Update the offset/bytes_written.
467 E : offset += instruction.size();
468 E : }
469 :
470 E : return true;
471 E : }
472 :
473 : void MergeContext::CopyReferences(
474 : const BasicBlock::BasicBlockReferenceMap& references,
475 E : Offset offset, Block* new_block) {
476 E : BasicBlock::BasicBlockReferenceMap::const_iterator it = references.begin();
477 E : for (; it != references.end(); ++it) {
478 E : BlockGraph::Reference resolved = ResolveReference(it->second);
479 :
480 E : CHECK(new_block->SetReference(offset + it->first, resolved));
481 E : }
482 E : }
483 :
484 : bool MergeContext::CopyData(const BasicDataBlock* data_block,
485 : Offset offset,
486 E : Block* new_block) {
487 E : DCHECK(data_block != NULL);
488 E : DCHECK_EQ(BasicBlock::BASIC_DATA_BLOCK, data_block->type());
489 :
490 : // Get the target buffer.
491 E : uint8* buffer = new_block->GetMutableData();
492 E : DCHECK(buffer != NULL);
493 :
494 : // Copy the basic-new_block_'s data bytes.
495 E : ::memcpy(buffer + offset, data_block->data(), data_block->size());
496 :
497 : // Record the source range.
498 : CopySourceRange(data_block->source_range(),
499 : offset, data_block->size(),
500 E : new_block);
501 :
502 E : CopyReferences(data_block->references(), offset, new_block);
503 E : return true;
504 E : }
505 :
506 : bool MergeContext::InitializeBlockLayout(const BasicBlockOrdering& order,
507 E : Block* new_block) {
508 : // Populate the initial layout info.
509 E : BasicBlockOrderingConstIter it = order.begin();
510 E : for (; it != order.end(); ++it) {
511 E : const BasicBlock* bb = *it;
512 :
513 : // Propagate BB alignment to the parent block.
514 E : if (bb->alignment() > new_block->alignment())
515 E : new_block->set_alignment(bb->alignment());
516 :
517 : // Create and initialize the layout info for this block.
518 E : DCHECK(layout_info_.find(bb) == layout_info_.end());
519 :
520 E : BasicBlockLayoutInfo& info = layout_info_[bb];
521 E : info.basic_block = bb;
522 E : info.block = new_block;
523 E : info.start_offset = 0;
524 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bb);
525 E : if (code_block != NULL)
526 E : info.basic_block_size = code_block->GetInstructionSize();
527 :
528 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bb);
529 E : if (data_block != NULL)
530 E : info.basic_block_size = data_block->size();
531 :
532 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
533 E : info.successors[i].condition = Successor::kInvalidCondition;
534 E : info.successors[i].size = 0;
535 E : }
536 :
537 : // Find the next basic block, if any.
538 E : BasicBlockOrderingConstIter next_it(it);
539 E : ++next_it;
540 E : const BasicBlock* next_bb = NULL;
541 E : if (next_it != order.end())
542 E : next_bb = *(next_it);
543 :
544 E : if (code_block == NULL)
545 E : continue;
546 :
547 : // Go through and decide how to manifest the successors for the current
548 : // basic block. A basic block has zero, one or two successors, and any
549 : // successor that refers to the next basic block in sequence is elided, as
550 : // it's most efficient for execution to simply fall through. We do this in
551 : // two nearly-identical code blocks, as the handling is only near-identical
552 : // for each of two possible successors.
553 E : DCHECK_GE(2U, code_block->successors().size());
554 E : SuccessorConstIter succ_it = code_block->successors().begin();
555 E : SuccessorConstIter succ_end = code_block->successors().end();
556 :
557 : // Process the first successor, if any.
558 E : size_t manifested_successors = 0;
559 E : if (succ_it != succ_end) {
560 E : const BasicBlock* destination_bb = succ_it->reference().basic_block();
561 :
562 : // Record the source range of the original successor.
563 E : if (succ_it->source_range().size() != 0) {
564 E : DCHECK_EQ(0U, info.successor_source_range.size());
565 E : info.successor_source_range = succ_it->source_range();
566 : }
567 : // Record the label of the original successor.
568 E : if (succ_it->has_label())
569 E : info.successor_label = succ_it->label();
570 :
571 : // Only manifest this successor if it's not referencing the next block.
572 E : if (destination_bb == NULL || destination_bb != next_bb) {
573 : SuccessorLayoutInfo& successor =
574 E : info.successors[manifested_successors++];
575 E : successor.condition = succ_it->condition();
576 E : successor.reference = succ_it->reference();
577 : }
578 :
579 : // Go to the next successor, if any.
580 E : ++succ_it;
581 : }
582 :
583 : // Process the second successor, if any.
584 E : if (succ_it != succ_end) {
585 E : const BasicBlock* destination_bb = succ_it->reference().basic_block();
586 :
587 : // Record the source range of the original successor.
588 E : if (succ_it->source_range().size() != 0) {
589 i : DCHECK_EQ(0U, info.successor_source_range.size());
590 i : info.successor_source_range = succ_it->source_range();
591 : }
592 : // Record the label of the original successor.
593 E : if (succ_it->has_label()) {
594 i : DCHECK(!info.successor_label.IsValid());
595 i : info.successor_label = succ_it->label();
596 : }
597 :
598 : // Only manifest this successor if it's not referencing the next block.
599 E : if (destination_bb == NULL || destination_bb != next_bb) {
600 E : Successor::Condition condition = succ_it->condition();
601 :
602 : // If we've already manifested a successor above, it'll be for the
603 : // complementary condition to ours. While it's correct to manifest it
604 : // as a conditional branch, it's more efficient to manifest as an
605 : // unconditional jump.
606 E : if (manifested_successors != 0) {
607 : DCHECK_EQ(Successor::InvertCondition(info.successors[0].condition),
608 E : succ_it->condition());
609 :
610 E : condition = Successor::kConditionTrue;
611 : }
612 :
613 : SuccessorLayoutInfo& successor =
614 E : info.successors[manifested_successors++];
615 :
616 E : successor.condition = condition;
617 E : successor.reference = succ_it->reference();
618 : }
619 : }
620 E : }
621 :
622 E : return true;
623 E : }
624 :
625 E : bool MergeContext::GenerateBlockLayout(const BasicBlockOrdering& order) {
626 E : BasicBlockOrderingConstIter it = order.begin();
627 :
628 : // Loop over the layout, expanding successors until stable.
629 E : while (true) {
630 E : bool expanded_successor = false;
631 :
632 : // Update the start offset for each of the BBs, respecting the BB alignment
633 : // constraints.
634 E : it = order.begin();
635 E : Offset next_block_start = 0;
636 E : Block* new_block = NULL;
637 E : for (; it != order.end(); ++it) {
638 E : BasicBlockLayoutInfo& info = FindLayoutInfo(*it);
639 : next_block_start = common::AlignUp(next_block_start,
640 E : info.basic_block->alignment());
641 E : info.start_offset = next_block_start;
642 :
643 E : if (new_block == NULL)
644 E : new_block = info.block;
645 E : DCHECK(new_block == info.block);
646 :
647 : next_block_start += info.basic_block_size +
648 : info.successors[0].size +
649 E : info.successors[1].size;
650 E : }
651 :
652 : // See whether there's a need to expand the successor sizes.
653 E : it = order.begin();
654 E : for (; it != order.end(); ++it) {
655 E : const BasicBlock* bb = *it;
656 E : BasicBlockLayoutInfo& info = FindLayoutInfo(bb);
657 :
658 : // Compute the start offset for this block's first successor.
659 E : Offset start_offset = info.start_offset + info.basic_block_size;
660 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
661 E : SuccessorLayoutInfo& successor = info.successors[i];
662 :
663 : // Exit the loop if this (and possibly the subsequent) successor
664 : // is un-manifested.
665 E : if (successor.condition == Successor::kInvalidCondition)
666 E : break;
667 :
668 : // Compute the new size and update the start offset for the next
669 : // successor (if any).
670 : Size new_size =
671 E : ComputeRequiredSuccessorSize(info, start_offset, successor);
672 E : start_offset += new_size;
673 :
674 : // Check whether we're expanding this successor.
675 E : if (new_size != successor.size) {
676 E : DCHECK_LT(successor.size, new_size);
677 E : successor.size = new_size;
678 E : expanded_successor = true;
679 : }
680 E : }
681 E : }
682 :
683 E : if (!expanded_successor) {
684 : // We've achieved a stable layout and we know that next_block_start
685 : // is the size of the new block, so resize it and allocate the data now.
686 E : new_block->set_size(next_block_start);
687 E : new_block->AllocateData(next_block_start);
688 :
689 E : return true;
690 : }
691 E : }
692 E : }
693 :
694 E : bool MergeContext::GenerateLayout(const BasicBlockSubGraph& subgraph) {
695 : // Create each new block and initialize a layout for it.
696 E : BlockDescriptionConstIter it = subgraph.block_descriptions().begin();
697 E : for (; it != subgraph.block_descriptions().end(); ++it) {
698 E : const BlockDescription& description = *it;
699 :
700 : // Skip the block if it's empty.
701 E : if (description.basic_block_order.empty())
702 i : continue;
703 :
704 : Block* new_block = block_graph_->AddBlock(
705 E : description.type, 0, description.name);
706 E : if (new_block == NULL) {
707 i : LOG(ERROR) << "Failed to create block '" << description.name << "'.";
708 i : return false;
709 : }
710 :
711 : // Save this block in the set of newly generated blocks. On failure, this
712 : // list will be used by GenerateBlocks() to clean up after itself.
713 E : new_blocks_.push_back(new_block);
714 :
715 : // Initialize the new block's properties.
716 E : new_block->set_alignment(description.alignment);
717 E : new_block->set_section(description.section);
718 E : new_block->set_attributes(description.attributes);
719 :
720 : // Initialize the layout for this block.
721 E : if (!InitializeBlockLayout(description.basic_block_order, new_block)) {
722 i : LOG(ERROR) << "Failed to initialize layout for basic block '" <<
723 : description.name << "'";
724 i : return false;
725 : }
726 E : }
727 :
728 : // Now generate a layout for each ordering.
729 E : it = subgraph.block_descriptions().begin();
730 E : for (; it != subgraph.block_descriptions().end(); ++it) {
731 E : const BlockDescription& description = *it;
732 :
733 : // Skip the block if it's empty.
734 E : if (description.basic_block_order.empty())
735 i : continue;
736 :
737 : // Generate the layout for this block.
738 E : if (!GenerateBlockLayout(description.basic_block_order)) {
739 i : LOG(ERROR) << "Failed to generate a layout for basic block '" <<
740 : description.name << "'";
741 i : return false;
742 : }
743 E : }
744 :
745 E : return true;
746 E : }
747 :
748 E : bool MergeContext::PopulateBlock(const BasicBlockOrdering& order) {
749 : // Populate the new block with basic blocks.
750 E : BasicBlockOrderingConstIter bb_iter = order.begin();
751 E : BasicBlockOrderingConstIter bb_end = order.end();
752 :
753 E : BlockGraph::Offset prev_offset = 0;
754 :
755 E : for (; bb_iter != bb_end; ++bb_iter) {
756 E : const BasicBlock* bb = *bb_iter;
757 E : const BasicBlockLayoutInfo& info = FindLayoutInfo(bb);
758 :
759 : // Handle any padding for alignment.
760 E : if (info.start_offset > prev_offset) {
761 : if (!InsertNops(prev_offset, info.start_offset - prev_offset,
762 E : info.block)) {
763 i : LOG(ERROR) << "Failed to insert NOPs for '" << bb->name() << "'.";
764 i : return false;
765 : }
766 : }
767 : prev_offset = info.start_offset + info.basic_block_size +
768 E : info.successors[0].size + info.successors[1].size;
769 :
770 : // Handle data basic blocks.
771 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bb);
772 E : if (data_block != NULL) {
773 : // If the basic-block is labeled, copy the label.
774 E : if (data_block->has_label())
775 E : info.block->SetLabel(info.start_offset, data_block->label());
776 :
777 : // Copy its data.
778 E : if (!CopyData(data_block, info.start_offset, info.block)) {
779 i : LOG(ERROR) << "Failed to copy data for '" << bb->name() << "'.";
780 i : return false;
781 : }
782 : }
783 :
784 : // Handle code basic blocks.
785 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bb);
786 E : if (code_block != NULL) {
787 : // Copy the instructions.
788 : if (!CopyInstructions(code_block->instructions(),
789 : info.start_offset,
790 E : info.block)) {
791 i : LOG(ERROR) << "Failed to copy instructions for '" << bb->name() << "'.";
792 i : return false;
793 : }
794 :
795 : // Synthesize the successor instructions and assign each to an offset.
796 E : if (!AssembleSuccessors(info)) {
797 i : LOG(ERROR) << "Failed to create successors for '" << bb->name() << "'.";
798 i : return false;
799 : }
800 : }
801 E : }
802 :
803 E : return true;
804 E : }
805 :
806 E : bool MergeContext::PopulateBlocks(const BasicBlockSubGraph& subgraph) {
807 : // Create each new block and generate a layout for it.
808 E : BlockDescriptionConstIter it = subgraph.block_descriptions().begin();
809 E : for (; it != subgraph.block_descriptions().end(); ++it) {
810 E : const BasicBlockOrdering& order = it->basic_block_order;
811 :
812 : // Skip the block if it's empty.
813 E : if (order.empty())
814 i : continue;
815 :
816 E : if (!PopulateBlock(order))
817 i : return false;
818 E : }
819 :
820 E : return true;
821 E : }
822 :
823 E : void MergeContext::UpdateReferrers(const BasicBlock* bb) const {
824 E : DCHECK(bb != NULL);
825 :
826 : // Find the current location of this basic block.
827 E : BasicBlockLayoutInfoMap::const_iterator layout_it = layout_info_.find(bb);
828 E : DCHECK(layout_it != layout_info_.end());
829 E : const BasicBlockLayoutInfo& info = layout_it->second;
830 E : DCHECK_EQ(bb, info.basic_block);
831 :
832 : // Update all external referrers to point to the new location.
833 E : const BasicBlock::BasicBlockReferrerSet& referrers = bb->referrers();
834 E : BasicBlock::BasicBlockReferrerSet::const_iterator it = referrers.begin();
835 E : for (; it != referrers.end(); ++it) {
836 : // Get a non-const pointer to the referring block. Note that we don't
837 : // modify the set property on referrers as we update the block's references.
838 E : const BasicBlockReferrer& referrer = *it;
839 E : Block* referring_block = const_cast<Block*>(referrer.block());
840 E : BlockGraph::Reference old_ref;
841 E : bool found = referring_block->GetReference(referrer.offset(), &old_ref);
842 E : DCHECK(found);
843 E : DCHECK_EQ(BlockGraph::Reference::kMaximumSize, old_ref.size());
844 :
845 : // The base of the reference is directed to the corresponding BB's
846 : // start address in the new block.
847 : BlockGraph::Reference new_ref(old_ref.type(),
848 : old_ref.size(),
849 : info.block,
850 : info.start_offset,
851 E : info.start_offset);
852 :
853 E : bool is_new = referring_block->SetReference(referrer.offset(), new_ref);
854 E : DCHECK(!is_new); // TODO(rogerm): Is this a valid DCHECK?
855 E : }
856 E : }
857 :
858 E : void MergeContext::RemoveOriginalBlock(BasicBlockSubGraph* subgraph) {
859 E : DCHECK(subgraph != NULL);
860 E : DCHECK_EQ(original_block_, subgraph->original_block());
861 :
862 E : Block* original_block_ = const_cast<Block*>(this->original_block_);
863 E : if (original_block_ == NULL)
864 E : return;
865 :
866 E : DCHECK(!original_block_->HasExternalReferrers());
867 :
868 E : bool removed = original_block_->RemoveAllReferences();
869 E : DCHECK(removed);
870 :
871 E : removed = block_graph_->RemoveBlock(original_block_);
872 E : DCHECK(removed);
873 :
874 E : subgraph->set_original_block(NULL);
875 E : original_block_ = NULL;
876 E : }
877 :
878 E : Size MergeContext::GetShortSuccessorSize(Successor::Condition condition) {
879 E : switch (condition) {
880 : case Successor::kConditionAbove:
881 : case Successor::kConditionAboveOrEqual:
882 : case Successor::kConditionBelow:
883 : case Successor::kConditionBelowOrEqual:
884 : case Successor::kConditionEqual:
885 : case Successor::kConditionGreater:
886 : case Successor::kConditionGreaterOrEqual:
887 : case Successor::kConditionLess:
888 : case Successor::kConditionLessOrEqual:
889 : case Successor::kConditionNotEqual:
890 : case Successor::kConditionNotOverflow:
891 : case Successor::kConditionNotParity:
892 : case Successor::kConditionNotSigned:
893 : case Successor::kConditionOverflow:
894 : case Successor::kConditionParity:
895 : case Successor::kConditionSigned:
896 : // Translates to a conditional branch.
897 E : return core::AssemblerImpl::kShortBranchSize;
898 :
899 : case Successor::kConditionTrue:
900 : // Translates to a jump.
901 E : return core::AssemblerImpl::kShortJumpSize;
902 :
903 : default:
904 i : NOTREACHED() << "Unsupported successor type.";
905 i : return 0;
906 : }
907 E : }
908 :
909 E : Size MergeContext::GetLongSuccessorSize(Successor::Condition condition) {
910 E : switch (condition) {
911 : case Successor::kConditionAbove:
912 : case Successor::kConditionAboveOrEqual:
913 : case Successor::kConditionBelow:
914 : case Successor::kConditionBelowOrEqual:
915 : case Successor::kConditionEqual:
916 : case Successor::kConditionGreater:
917 : case Successor::kConditionGreaterOrEqual:
918 : case Successor::kConditionLess:
919 : case Successor::kConditionLessOrEqual:
920 : case Successor::kConditionNotEqual:
921 : case Successor::kConditionNotOverflow:
922 : case Successor::kConditionNotParity:
923 : case Successor::kConditionNotSigned:
924 : case Successor::kConditionOverflow:
925 : case Successor::kConditionParity:
926 : case Successor::kConditionSigned:
927 : // Translates to a conditional branch.
928 E : return core::AssemblerImpl::kLongBranchSize;
929 :
930 : case Successor::kConditionTrue:
931 : // Translates to a jump.
932 E : return core::AssemblerImpl::kLongJumpSize;
933 :
934 : default:
935 i : NOTREACHED() << "Unsupported successor type.";
936 i : return 0;
937 : }
938 E : }
939 :
940 : Size MergeContext::ComputeRequiredSuccessorSize(
941 : const BasicBlockLayoutInfo& info,
942 : Offset start_offset,
943 E : const SuccessorLayoutInfo& successor) {
944 E : switch (successor.reference.referred_type()) {
945 : case BasicBlockReference::REFERRED_TYPE_BLOCK:
946 E : return GetLongSuccessorSize(successor.condition);
947 :
948 : case BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK: {
949 E : Size short_size = GetShortSuccessorSize(successor.condition);
950 E : const BasicBlock* dest_bb = successor.reference.basic_block();
951 E : DCHECK(dest_bb != NULL);
952 E : const BasicBlockLayoutInfo& dest = FindLayoutInfo(dest_bb);
953 :
954 : // If the destination is within the same destination block,
955 : // let's see if we can use a short reach here.
956 E : if (info.block == dest.block) {
957 : Offset destination_offset =
958 E : dest.start_offset - (start_offset + short_size);
959 :
960 : // Are we in-bounds for a short reference?
961 : if (destination_offset <= std::numeric_limits<int8>::max() &&
962 E : destination_offset >= std::numeric_limits<int8>::min()) {
963 E : return short_size;
964 : }
965 : }
966 :
967 E : return GetLongSuccessorSize(successor.condition);
968 : }
969 :
970 : default:
971 i : NOTREACHED() << "Impossible Successor reference type.";
972 i : return 0;
973 : }
974 E : }
975 :
976 : MergeContext::BasicBlockLayoutInfo& MergeContext::FindLayoutInfo(
977 E : const BasicBlock* bb) {
978 E : BasicBlockLayoutInfoMap::iterator it = layout_info_.find(bb);
979 E : DCHECK(it != layout_info_.end());
980 E : DCHECK_EQ(bb, it->second.basic_block);
981 :
982 E : return it->second;
983 E : }
984 :
985 : const MergeContext::BasicBlockLayoutInfo& MergeContext::FindLayoutInfo(
986 E : const BasicBlock* bb) const {
987 E : BasicBlockLayoutInfoMap::const_iterator it = layout_info_.find(bb);
988 E : DCHECK(it != layout_info_.end());
989 E : DCHECK_EQ(bb, it->second.basic_block);
990 :
991 E : return it->second;
992 E : }
993 :
994 : BlockGraph::Reference MergeContext::ResolveReference(
995 : BlockGraph::ReferenceType type, Size size,
996 E : const BasicBlockReference& ref) const {
997 E : if (ref.referred_type() == BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK) {
998 : // It's a basic block reference, we need to resolve it to a
999 : // block reference.
1000 E : const BasicBlockLayoutInfo& info = FindLayoutInfo(ref.basic_block());
1001 :
1002 : return BlockGraph::Reference(type,
1003 : size,
1004 : info.block,
1005 : info.start_offset,
1006 E : info.start_offset);
1007 i : } else {
1008 E : DCHECK_EQ(BasicBlockReference::REFERRED_TYPE_BLOCK, ref.referred_type());
1009 :
1010 : return BlockGraph::Reference(type,
1011 : size,
1012 : const_cast<Block*>(ref.block()),
1013 : ref.offset(),
1014 E : ref.base());
1015 : }
1016 E : }
1017 :
1018 : BlockGraph::Reference MergeContext::ResolveReference(
1019 E : const BasicBlockReference& ref) const {
1020 E : return ResolveReference(ref.reference_type(), ref.size(), ref);
1021 E : }
1022 :
1023 : } // namespace
1024 :
1025 E : BlockBuilder::BlockBuilder(BlockGraph* bg) : block_graph_(bg) {
1026 E : }
1027 :
1028 E : bool BlockBuilder::Merge(BasicBlockSubGraph* subgraph) {
1029 E : DCHECK(subgraph != NULL);
1030 :
1031 E : MergeContext context(block_graph_, subgraph->original_block());
1032 :
1033 E : if (!context.GenerateBlocks(*subgraph))
1034 i : return false;
1035 :
1036 E : context.TransferReferrers(subgraph);
1037 E : context.RemoveOriginalBlock(subgraph);
1038 :
1039 : // Track the newly created blocks.
1040 E : new_blocks_.reserve(new_blocks_.size() + context.new_blocks().size());
1041 : new_blocks_.insert(new_blocks_.end(),
1042 : context.new_blocks().begin(),
1043 E : context.new_blocks().end());
1044 :
1045 : // And we're done.
1046 E : return true;
1047 E : }
1048 :
1049 : } // namespace block_graph
|