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