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. This will be a PC-relative reference of size 8 or 32,
346 : // depending on whether the successor has been manifested long or short.
347 : BasicBlockReference ref(BlockGraph::PC_RELATIVE_REF,
348 : reference_size == core::kSize8Bit ? 1 : 4,
349 E : successor.reference);
350 : // For debugging, we stomp the correct offset into the re-generated block
351 : // for block-internal references.
352 E : BlockGraph::Reference resolved_ref = ResolveReference(successor.reference);
353 : // Default to the offset immediately following the successor, which
354 : // will translate to a zero pc-relative offset.
355 E : Offset ref_offset = successor_start + successor.size;
356 E : if (resolved_ref.referenced() == info.block)
357 E : ref_offset = resolved_ref.offset();
358 E : Immediate dest(ref_offset, reference_size, ref);
359 :
360 : // Assemble the instruction.
361 E : switch (successor.condition) {
362 : case Successor::kConditionAbove:
363 : case Successor::kConditionAboveOrEqual:
364 : case Successor::kConditionBelow:
365 : case Successor::kConditionBelowOrEqual:
366 : case Successor::kConditionEqual:
367 : case Successor::kConditionGreater:
368 : case Successor::kConditionGreaterOrEqual:
369 : case Successor::kConditionLess:
370 : case Successor::kConditionLessOrEqual:
371 : case Successor::kConditionNotEqual:
372 : case Successor::kConditionNotOverflow:
373 : case Successor::kConditionNotParity:
374 : case Successor::kConditionNotSigned:
375 : case Successor::kConditionOverflow:
376 : case Successor::kConditionParity:
377 : case Successor::kConditionSigned:
378 E : assm.j(static_cast<core::ConditionCode>(successor.condition), dest);
379 E : break;
380 :
381 : case Successor::kConditionTrue:
382 E : assm.jmp(dest);
383 E : break;
384 :
385 : default:
386 i : NOTREACHED();
387 i : return false;
388 : }
389 :
390 : // Make sure the assembler produced what we expected.
391 E : DCHECK_EQ(successor.size, instructions.back().size());
392 :
393 : // Walk our start address forwards.
394 E : successor_start += successor.size;
395 :
396 E : if (info.successor_source_range.size() != 0) {
397 E : Instruction& instr = instructions.back();
398 :
399 : // Attribute this instruction to the original successor's source range.
400 E : instr.set_source_range(info.successor_source_range);
401 : }
402 E : }
403 :
404 E : if (instructions.size() != 0) {
405 E : Offset start_offset = info.start_offset + info.basic_block_size;
406 E : return CopyInstructions(instructions, start_offset, info.block);
407 : }
408 :
409 E : return true;
410 E : }
411 :
412 : bool MergeContext::InsertNops(Offset offset,
413 : Size bytes,
414 E : Block* new_block) {
415 E : DCHECK(new_block != NULL);
416 :
417 E : uint8* buffer = new_block->GetMutableData();
418 E : DCHECK(buffer != NULL);
419 :
420 E : size_t kMaxNopLength = arraysize(kNops) - 1;
421 E : buffer += offset;
422 E : while (bytes >= kMaxNopLength) {
423 i : ::memcpy(buffer, kNops[kMaxNopLength], kMaxNopLength);
424 i : buffer += kMaxNopLength;
425 i : bytes -= kMaxNopLength;
426 i : }
427 :
428 E : if (bytes > 0) {
429 E : DCHECK_GT(kMaxNopLength, bytes);
430 E : ::memcpy(buffer, kNops[bytes], bytes);
431 : }
432 :
433 E : return true;
434 E : }
435 :
436 : bool MergeContext::CopyInstructions(
437 : const BasicBlock::Instructions& instructions,
438 E : Offset offset, Block* new_block) {
439 E : DCHECK(new_block != NULL);
440 E : DCHECK_EQ(BasicBlock::BASIC_CODE_BLOCK, new_block->type());
441 : // Get the target buffer.
442 E : uint8* buffer = new_block->GetMutableData();
443 E : DCHECK(buffer != NULL);
444 :
445 : // Copy the instruction data and assign each instruction an offset.
446 E : InstructionConstIter it = instructions.begin();
447 E : for (; it != instructions.end(); ++it) {
448 E : const Instruction& instruction = *it;
449 :
450 : // Copy the instruction bytes.
451 : ::memcpy(buffer + offset,
452 : instruction.data(),
453 E : instruction.size());
454 :
455 : // Preserve the label on the instruction, if any.
456 E : if (instruction.has_label())
457 E : new_block->SetLabel(offset, instruction.label());
458 :
459 : // Record the source range.
460 : CopySourceRange(instruction.source_range(),
461 : offset, instruction.size(),
462 E : new_block);
463 :
464 : // Copy references.
465 E : CopyReferences(instruction.references(), offset, new_block);
466 :
467 : // Update the offset/bytes_written.
468 E : offset += instruction.size();
469 E : }
470 :
471 E : return true;
472 E : }
473 :
474 : void MergeContext::CopyReferences(
475 : const BasicBlock::BasicBlockReferenceMap& references,
476 E : Offset offset, Block* new_block) {
477 E : BasicBlock::BasicBlockReferenceMap::const_iterator it = references.begin();
478 E : for (; it != references.end(); ++it) {
479 E : BlockGraph::Reference resolved = ResolveReference(it->second);
480 :
481 E : CHECK(new_block->SetReference(offset + it->first, resolved));
482 E : }
483 E : }
484 :
485 : bool MergeContext::CopyData(const BasicDataBlock* data_block,
486 : Offset offset,
487 E : Block* new_block) {
488 E : DCHECK(data_block != NULL);
489 E : DCHECK_EQ(BasicBlock::BASIC_DATA_BLOCK, data_block->type());
490 :
491 : // Get the target buffer.
492 E : uint8* buffer = new_block->GetMutableData();
493 E : DCHECK(buffer != NULL);
494 :
495 : // Copy the basic-new_block_'s data bytes.
496 E : ::memcpy(buffer + offset, data_block->data(), data_block->size());
497 :
498 : // Record the source range.
499 : CopySourceRange(data_block->source_range(),
500 : offset, data_block->size(),
501 E : new_block);
502 :
503 E : CopyReferences(data_block->references(), offset, new_block);
504 E : return true;
505 E : }
506 :
507 : bool MergeContext::InitializeBlockLayout(const BasicBlockOrdering& order,
508 E : Block* new_block) {
509 : // Populate the initial layout info.
510 E : BasicBlockOrderingConstIter it = order.begin();
511 E : for (; it != order.end(); ++it) {
512 E : const BasicBlock* bb = *it;
513 :
514 : // Propagate BB alignment to the parent block.
515 E : if (bb->alignment() > new_block->alignment())
516 E : new_block->set_alignment(bb->alignment());
517 :
518 : // Create and initialize the layout info for this block.
519 E : DCHECK(layout_info_.find(bb) == layout_info_.end());
520 :
521 E : BasicBlockLayoutInfo& info = layout_info_[bb];
522 E : info.basic_block = bb;
523 E : info.block = new_block;
524 E : info.start_offset = 0;
525 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bb);
526 E : if (code_block != NULL)
527 E : info.basic_block_size = code_block->GetInstructionSize();
528 :
529 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bb);
530 E : if (data_block != NULL)
531 E : info.basic_block_size = data_block->size();
532 :
533 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
534 E : info.successors[i].condition = Successor::kInvalidCondition;
535 E : info.successors[i].size = 0;
536 E : }
537 :
538 : // Find the next basic block, if any.
539 E : BasicBlockOrderingConstIter next_it(it);
540 E : ++next_it;
541 E : const BasicBlock* next_bb = NULL;
542 E : if (next_it != order.end())
543 E : next_bb = *(next_it);
544 :
545 E : if (code_block == NULL)
546 E : continue;
547 :
548 : // Go through and decide how to manifest the successors for the current
549 : // basic block. A basic block has zero, one or two successors, and any
550 : // successor that refers to the next basic block in sequence is elided, as
551 : // it's most efficient for execution to simply fall through. We do this in
552 : // two nearly-identical code blocks, as the handling is only near-identical
553 : // for each of two possible successors.
554 E : DCHECK_GE(2U, code_block->successors().size());
555 E : SuccessorConstIter succ_it = code_block->successors().begin();
556 E : SuccessorConstIter succ_end = code_block->successors().end();
557 :
558 : // Process the first successor, if any.
559 E : size_t manifested_successors = 0;
560 E : if (succ_it != succ_end) {
561 E : const BasicBlock* destination_bb = succ_it->reference().basic_block();
562 :
563 : // Record the source range of the original successor.
564 E : if (succ_it->source_range().size() != 0) {
565 E : DCHECK_EQ(0U, info.successor_source_range.size());
566 E : info.successor_source_range = succ_it->source_range();
567 : }
568 : // Record the label of the original successor.
569 E : if (succ_it->has_label())
570 E : info.successor_label = succ_it->label();
571 :
572 : // Only manifest this successor if it's not referencing the next block.
573 E : if (destination_bb == NULL || destination_bb != next_bb) {
574 : SuccessorLayoutInfo& successor =
575 E : info.successors[manifested_successors++];
576 E : successor.condition = succ_it->condition();
577 E : successor.reference = succ_it->reference();
578 : }
579 :
580 : // Go to the next successor, if any.
581 E : ++succ_it;
582 : }
583 :
584 : // Process the second successor, if any.
585 E : if (succ_it != succ_end) {
586 E : const BasicBlock* destination_bb = succ_it->reference().basic_block();
587 :
588 : // Record the source range of the original successor.
589 E : if (succ_it->source_range().size() != 0) {
590 i : DCHECK_EQ(0U, info.successor_source_range.size());
591 i : info.successor_source_range = succ_it->source_range();
592 : }
593 : // Record the label of the original successor.
594 E : if (succ_it->has_label()) {
595 i : DCHECK_EQ(false, info.successor_label.IsValid());
596 i : info.successor_label = succ_it->label();
597 : }
598 :
599 : // Only manifest this successor if it's not referencing the next block.
600 E : if (destination_bb == NULL || destination_bb != next_bb) {
601 E : Successor::Condition condition = succ_it->condition();
602 :
603 : // If we've already manifested a successor above, it'll be for the
604 : // complementary condition to ours. While it's correct to manifest it
605 : // as a conditional branch, it's more efficient to manifest as an
606 : // unconditional jump.
607 E : if (manifested_successors != 0) {
608 : DCHECK_EQ(Successor::InvertCondition(info.successors[0].condition),
609 E : succ_it->condition());
610 :
611 E : condition = Successor::kConditionTrue;
612 : }
613 :
614 : SuccessorLayoutInfo& successor =
615 E : info.successors[manifested_successors++];
616 :
617 E : successor.condition = condition;
618 E : successor.reference = succ_it->reference();
619 : }
620 : }
621 E : }
622 :
623 E : return true;
624 E : }
625 :
626 E : bool MergeContext::GenerateBlockLayout(const BasicBlockOrdering& order) {
627 E : BasicBlockOrderingConstIter it = order.begin();
628 :
629 : // Loop over the layout, expanding successors until stable.
630 E : while (true) {
631 E : bool expanded_successor = false;
632 :
633 : // Update the start offset for each of the BBs, respecting the BB alignment
634 : // constraints.
635 E : it = order.begin();
636 E : Offset next_block_start = 0;
637 E : Block* new_block = NULL;
638 E : for (; it != order.end(); ++it) {
639 E : BasicBlockLayoutInfo& info = FindLayoutInfo(*it);
640 : next_block_start = common::AlignUp(next_block_start,
641 E : info.basic_block->alignment());
642 E : info.start_offset = next_block_start;
643 :
644 E : if (new_block == NULL)
645 E : new_block = info.block;
646 E : DCHECK(new_block == info.block);
647 :
648 : next_block_start += info.basic_block_size +
649 : info.successors[0].size +
650 E : info.successors[1].size;
651 E : }
652 :
653 : // See whether there's a need to expand the successor sizes.
654 E : it = order.begin();
655 E : for (; it != order.end(); ++it) {
656 E : const BasicBlock* bb = *it;
657 E : BasicBlockLayoutInfo& info = FindLayoutInfo(bb);
658 :
659 : // Compute the start offset for this block's first successor.
660 E : Offset start_offset = info.start_offset + info.basic_block_size;
661 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
662 E : SuccessorLayoutInfo& successor = info.successors[i];
663 :
664 : // Exit the loop if this (and possibly the subsequent) successor
665 : // is un-manifested.
666 E : if (successor.condition == Successor::kInvalidCondition)
667 E : break;
668 :
669 : // Compute the new size and update the start offset for the next
670 : // successor (if any).
671 : Size new_size =
672 E : ComputeRequiredSuccessorSize(info, start_offset, successor);
673 E : start_offset += new_size;
674 :
675 : // Check whether we're expanding this successor.
676 E : if (new_size != successor.size) {
677 E : DCHECK_LT(successor.size, new_size);
678 E : successor.size = new_size;
679 E : expanded_successor = true;
680 : }
681 E : }
682 E : }
683 :
684 E : if (!expanded_successor) {
685 : // We've achieved a stable layout and we know that next_block_start
686 : // is the size of the new block, so resize it and allocate the data now.
687 E : new_block->set_size(next_block_start);
688 E : new_block->AllocateData(next_block_start);
689 :
690 E : return true;
691 : }
692 E : }
693 E : }
694 :
695 E : bool MergeContext::GenerateLayout(const BasicBlockSubGraph& subgraph) {
696 : // Create each new block and initialize a layout for it.
697 E : BlockDescriptionConstIter it = subgraph.block_descriptions().begin();
698 E : for (; it != subgraph.block_descriptions().end(); ++it) {
699 E : const BlockDescription& description = *it;
700 :
701 : // Skip the block if it's empty.
702 E : if (description.basic_block_order.empty())
703 i : continue;
704 :
705 : Block* new_block = block_graph_->AddBlock(
706 E : description.type, 0, description.name);
707 E : if (new_block == NULL) {
708 i : LOG(ERROR) << "Failed to create block '" << description.name << "'.";
709 i : return false;
710 : }
711 :
712 : // Save this block in the set of newly generated blocks. On failure, this
713 : // list will be used by GenerateBlocks() to clean up after itself.
714 E : new_blocks_.push_back(new_block);
715 :
716 : // Initialize the new block's properties.
717 E : new_block->set_alignment(description.alignment);
718 E : new_block->set_section(description.section);
719 E : new_block->set_attributes(description.attributes);
720 :
721 : // Initialize the layout for this block.
722 E : if (!InitializeBlockLayout(description.basic_block_order, new_block)) {
723 i : LOG(ERROR) << "Failed to initialize layout for basic block '" <<
724 : description.name << "'";
725 i : return false;
726 : }
727 E : }
728 :
729 : // Now generate a layout for each ordering.
730 E : it = subgraph.block_descriptions().begin();
731 E : for (; it != subgraph.block_descriptions().end(); ++it) {
732 E : const BlockDescription& description = *it;
733 :
734 : // Skip the block if it's empty.
735 E : if (description.basic_block_order.empty())
736 i : continue;
737 :
738 : // Generate the layout for this block.
739 E : if (!GenerateBlockLayout(description.basic_block_order)) {
740 i : LOG(ERROR) << "Failed to generate a layout for basic block '" <<
741 : description.name << "'";
742 i : return false;
743 : }
744 E : }
745 :
746 E : return true;
747 E : }
748 :
749 E : bool MergeContext::PopulateBlock(const BasicBlockOrdering& order) {
750 : // Populate the new block with basic blocks.
751 E : BasicBlockOrderingConstIter bb_iter = order.begin();
752 E : BasicBlockOrderingConstIter bb_end = order.end();
753 :
754 E : BlockGraph::Offset prev_offset = 0;
755 :
756 E : for (; bb_iter != bb_end; ++bb_iter) {
757 E : const BasicBlock* bb = *bb_iter;
758 E : const BasicBlockLayoutInfo& info = FindLayoutInfo(bb);
759 :
760 : // Handle any padding for alignment.
761 E : if (info.start_offset > prev_offset) {
762 : if (!InsertNops(prev_offset, info.start_offset - prev_offset,
763 E : info.block)) {
764 i : LOG(ERROR) << "Failed to insert NOPs for '" << bb->name() << "'.";
765 i : return false;
766 : }
767 : }
768 : prev_offset = info.start_offset + info.basic_block_size +
769 E : info.successors[0].size + info.successors[1].size;
770 :
771 : // Handle data basic blocks.
772 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bb);
773 E : if (data_block != NULL) {
774 : // If the basic-block is labeled, copy the label.
775 E : if (data_block->has_label())
776 E : info.block->SetLabel(info.start_offset, data_block->label());
777 :
778 : // Copy its data.
779 E : if (!CopyData(data_block, info.start_offset, info.block)) {
780 i : LOG(ERROR) << "Failed to copy data for '" << bb->name() << "'.";
781 i : return false;
782 : }
783 : }
784 :
785 : // Handle code basic blocks.
786 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bb);
787 E : if (code_block != NULL) {
788 : // Copy the instructions.
789 : if (!CopyInstructions(code_block->instructions(),
790 : info.start_offset,
791 E : info.block)) {
792 i : LOG(ERROR) << "Failed to copy instructions for '" << bb->name() << "'.";
793 i : return false;
794 : }
795 :
796 : // Synthesize the successor instructions and assign each to an offset.
797 E : if (!AssembleSuccessors(info)) {
798 i : LOG(ERROR) << "Failed to create successors for '" << bb->name() << "'.";
799 i : return false;
800 : }
801 : }
802 E : }
803 :
804 E : return true;
805 E : }
806 :
807 E : bool MergeContext::PopulateBlocks(const BasicBlockSubGraph& subgraph) {
808 : // Create each new block and generate a layout for it.
809 E : BlockDescriptionConstIter it = subgraph.block_descriptions().begin();
810 E : for (; it != subgraph.block_descriptions().end(); ++it) {
811 E : const BasicBlockOrdering& order = it->basic_block_order;
812 :
813 : // Skip the block if it's empty.
814 E : if (order.empty())
815 i : continue;
816 :
817 E : if (!PopulateBlock(order))
818 i : return false;
819 E : }
820 :
821 E : return true;
822 E : }
823 :
824 E : void MergeContext::UpdateReferrers(const BasicBlock* bb) const {
825 E : DCHECK(bb != NULL);
826 :
827 : // Find the current location of this basic block.
828 E : BasicBlockLayoutInfoMap::const_iterator layout_it = layout_info_.find(bb);
829 E : DCHECK(layout_it != layout_info_.end());
830 E : const BasicBlockLayoutInfo& info = layout_it->second;
831 E : DCHECK_EQ(bb, info.basic_block);
832 :
833 : // Update all external referrers to point to the new location.
834 E : const BasicBlock::BasicBlockReferrerSet& referrers = bb->referrers();
835 E : BasicBlock::BasicBlockReferrerSet::const_iterator it = referrers.begin();
836 E : for (; it != referrers.end(); ++it) {
837 : // Get a non-const pointer to the referring block. Note that we don't
838 : // modify the set property on referrers as we update the block's references.
839 E : const BasicBlockReferrer& referrer = *it;
840 E : Block* referring_block = const_cast<Block*>(referrer.block());
841 E : BlockGraph::Reference old_ref;
842 E : bool found = referring_block->GetReference(referrer.offset(), &old_ref);
843 E : DCHECK(found);
844 E : DCHECK_EQ(BlockGraph::Reference::kMaximumSize, old_ref.size());
845 :
846 : // The base of the reference is directed to the corresponding BB's
847 : // start address in the new block.
848 : BlockGraph::Reference new_ref(old_ref.type(),
849 : old_ref.size(),
850 : info.block,
851 : info.start_offset,
852 E : info.start_offset);
853 :
854 E : bool is_new = referring_block->SetReference(referrer.offset(), new_ref);
855 E : DCHECK(!is_new); // TODO(rogerm): Is this a valid DCHECK?
856 E : }
857 E : }
858 :
859 E : void MergeContext::RemoveOriginalBlock(BasicBlockSubGraph* subgraph) {
860 E : DCHECK(subgraph != NULL);
861 E : DCHECK_EQ(original_block_, subgraph->original_block());
862 :
863 E : Block* original_block_ = const_cast<Block*>(this->original_block_);
864 E : if (original_block_ == NULL)
865 E : return;
866 :
867 E : DCHECK(!original_block_->HasExternalReferrers());
868 :
869 E : bool removed = original_block_->RemoveAllReferences();
870 E : DCHECK(removed);
871 :
872 E : removed = block_graph_->RemoveBlock(original_block_);
873 E : DCHECK(removed);
874 :
875 E : subgraph->set_original_block(NULL);
876 E : original_block_ = NULL;
877 E : }
878 :
879 E : Size MergeContext::GetShortSuccessorSize(Successor::Condition condition) {
880 E : switch (condition) {
881 : case Successor::kConditionAbove:
882 : case Successor::kConditionAboveOrEqual:
883 : case Successor::kConditionBelow:
884 : case Successor::kConditionBelowOrEqual:
885 : case Successor::kConditionEqual:
886 : case Successor::kConditionGreater:
887 : case Successor::kConditionGreaterOrEqual:
888 : case Successor::kConditionLess:
889 : case Successor::kConditionLessOrEqual:
890 : case Successor::kConditionNotEqual:
891 : case Successor::kConditionNotOverflow:
892 : case Successor::kConditionNotParity:
893 : case Successor::kConditionNotSigned:
894 : case Successor::kConditionOverflow:
895 : case Successor::kConditionParity:
896 : case Successor::kConditionSigned:
897 : // Translates to a conditional branch.
898 E : return core::AssemblerImpl::kShortBranchSize;
899 :
900 : case Successor::kConditionTrue:
901 : // Translates to a jump.
902 E : return core::AssemblerImpl::kShortJumpSize;
903 :
904 : default:
905 i : NOTREACHED() << "Unsupported successor type.";
906 i : return 0;
907 : }
908 E : }
909 :
910 E : Size MergeContext::GetLongSuccessorSize(Successor::Condition condition) {
911 E : switch (condition) {
912 : case Successor::kConditionAbove:
913 : case Successor::kConditionAboveOrEqual:
914 : case Successor::kConditionBelow:
915 : case Successor::kConditionBelowOrEqual:
916 : case Successor::kConditionEqual:
917 : case Successor::kConditionGreater:
918 : case Successor::kConditionGreaterOrEqual:
919 : case Successor::kConditionLess:
920 : case Successor::kConditionLessOrEqual:
921 : case Successor::kConditionNotEqual:
922 : case Successor::kConditionNotOverflow:
923 : case Successor::kConditionNotParity:
924 : case Successor::kConditionNotSigned:
925 : case Successor::kConditionOverflow:
926 : case Successor::kConditionParity:
927 : case Successor::kConditionSigned:
928 : // Translates to a conditional branch.
929 E : return core::AssemblerImpl::kLongBranchSize;
930 :
931 : case Successor::kConditionTrue:
932 : // Translates to a jump.
933 E : return core::AssemblerImpl::kLongJumpSize;
934 :
935 : default:
936 i : NOTREACHED() << "Unsupported successor type.";
937 i : return 0;
938 : }
939 E : }
940 :
941 : Size MergeContext::ComputeRequiredSuccessorSize(
942 : const BasicBlockLayoutInfo& info,
943 : Offset start_offset,
944 E : const SuccessorLayoutInfo& successor) {
945 E : switch (successor.reference.referred_type()) {
946 : case BasicBlockReference::REFERRED_TYPE_BLOCK:
947 E : return GetLongSuccessorSize(successor.condition);
948 :
949 : case BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK: {
950 E : Size short_size = GetShortSuccessorSize(successor.condition);
951 E : const BasicBlock* dest_bb = successor.reference.basic_block();
952 E : DCHECK(dest_bb != NULL);
953 E : const BasicBlockLayoutInfo& dest = FindLayoutInfo(dest_bb);
954 :
955 : // If the destination is within the same destination block,
956 : // let's see if we can use a short reach here.
957 E : if (info.block == dest.block) {
958 : Offset destination_offset =
959 E : dest.start_offset - (start_offset + short_size);
960 :
961 : // Are we in-bounds for a short reference?
962 : if (destination_offset <= std::numeric_limits<int8>::max() &&
963 E : destination_offset >= std::numeric_limits<int8>::min()) {
964 E : return short_size;
965 : }
966 : }
967 :
968 E : return GetLongSuccessorSize(successor.condition);
969 : }
970 :
971 : default:
972 i : NOTREACHED() << "Impossible Successor reference type.";
973 i : return 0;
974 : }
975 E : }
976 :
977 : MergeContext::BasicBlockLayoutInfo& MergeContext::FindLayoutInfo(
978 E : const BasicBlock* bb) {
979 E : BasicBlockLayoutInfoMap::iterator it = layout_info_.find(bb);
980 E : DCHECK(it != layout_info_.end());
981 E : DCHECK_EQ(bb, it->second.basic_block);
982 :
983 E : return it->second;
984 E : }
985 :
986 : const MergeContext::BasicBlockLayoutInfo& MergeContext::FindLayoutInfo(
987 E : const BasicBlock* bb) const {
988 E : BasicBlockLayoutInfoMap::const_iterator it = layout_info_.find(bb);
989 E : DCHECK(it != layout_info_.end());
990 E : DCHECK_EQ(bb, it->second.basic_block);
991 :
992 E : return it->second;
993 E : }
994 :
995 : BlockGraph::Reference MergeContext::ResolveReference(
996 : BlockGraph::ReferenceType type, Size size,
997 E : const BasicBlockReference& ref) const {
998 E : if (ref.referred_type() == BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK) {
999 : // It's a basic block reference, we need to resolve it to a
1000 : // block reference.
1001 E : const BasicBlockLayoutInfo& info = FindLayoutInfo(ref.basic_block());
1002 :
1003 : return BlockGraph::Reference(type,
1004 : size,
1005 : info.block,
1006 : info.start_offset,
1007 E : info.start_offset);
1008 i : } else {
1009 E : DCHECK_EQ(BasicBlockReference::REFERRED_TYPE_BLOCK, ref.referred_type());
1010 :
1011 : return BlockGraph::Reference(type,
1012 : size,
1013 : const_cast<Block*>(ref.block()),
1014 : ref.offset(),
1015 E : ref.base());
1016 : }
1017 E : }
1018 :
1019 : BlockGraph::Reference MergeContext::ResolveReference(
1020 E : const BasicBlockReference& ref) const {
1021 E : return ResolveReference(ref.reference_type(), ref.size(), ref);
1022 E : }
1023 :
1024 : } // namespace
1025 :
1026 E : BlockBuilder::BlockBuilder(BlockGraph* bg) : block_graph_(bg) {
1027 E : }
1028 :
1029 E : bool BlockBuilder::Merge(BasicBlockSubGraph* subgraph) {
1030 E : DCHECK(subgraph != NULL);
1031 :
1032 E : MergeContext context(block_graph_, subgraph->original_block());
1033 :
1034 E : if (!context.GenerateBlocks(*subgraph))
1035 i : return false;
1036 :
1037 E : context.TransferReferrers(subgraph);
1038 E : context.RemoveOriginalBlock(subgraph);
1039 :
1040 : // Track the newly created blocks.
1041 E : new_blocks_.reserve(new_blocks_.size() + context.new_blocks().size());
1042 : new_blocks_.insert(new_blocks_.end(),
1043 : context.new_blocks().begin(),
1044 E : context.new_blocks().end());
1045 :
1046 : // And we're done.
1047 E : return true;
1048 E : }
1049 :
1050 : } // namespace block_graph
|