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 : BlockGraph::LabelAttributes new_attr = previous_label.attributes() |
110 E : 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 : : 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 : bool inserted = new_block->source_ranges().Insert(
370 E : 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 : BasicBlockAssembler assm(info.start_offset + info.basic_block_size,
377 E : instructions.begin(), &instructions);
378 :
379 : // Copy the successor label, if any, to where it belongs.
380 E : if (info.successor_label.IsValid()) {
381 : AddOrMergeLabel(info.start_offset + info.basic_block_size,
382 : info.successor_label,
383 E : info.block);
384 : }
385 :
386 E : Offset successor_start = info.start_offset + info.basic_block_size;
387 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
388 E : const SuccessorLayoutInfo& successor = info.successors[i];
389 :
390 : // Exit loop early if appropriate.
391 : if (successor.condition == Successor::kInvalidCondition &&
392 E : successor.successor == NULL) {
393 E : break;
394 : }
395 :
396 : // A pointer to the original successor should always be set for any
397 : // manifested or elided successor.
398 E : DCHECK_NE(reinterpret_cast<Successor*>(NULL), successor.successor);
399 :
400 : // If this represents an elided successor then simply emit tag information
401 : // and continue.
402 E : if (successor.condition == Successor::kInvalidCondition) {
403 : // Update the tag-info map for the successor.
404 : UpdateTagInfoMap(successor.successor->tags(), kSuccessorTag, info.block,
405 E : successor_start, 0, tag_info_map_);
406 : UpdateTagInfoMap(successor.successor->reference().tags(),
407 : kReferenceTag, info.block, successor_start, 0,
408 E : tag_info_map_);
409 E : continue;
410 : }
411 :
412 : // Default to a short reference.
413 E : ValueSize reference_size = assm::kSize8Bit;
414 E : if (successor.size != GetShortSuccessorSize(successor.condition))
415 E : reference_size = assm::kSize32Bit;
416 :
417 : // Construct the reference we're going to deposit into the instruction
418 : // list first.
419 E : UntypedReference untyped_ref(successor.reference);
420 :
421 : // For debugging, we stomp the correct offset into the re-generated block
422 : // for block-internal references.
423 E : BlockGraph::Reference resolved_ref = ResolveReference(successor.reference);
424 :
425 : // Default to the offset immediately following the successor, which
426 : // will translate to a zero pc-relative offset.
427 E : Offset ref_offset = successor_start + successor.size;
428 E : if (resolved_ref.referenced() == info.block)
429 E : ref_offset = resolved_ref.offset();
430 E : auto dest(Immediate(ref_offset, reference_size, untyped_ref));
431 :
432 : // Assemble the instruction.
433 E : switch (successor.condition) {
434 : case Successor::kConditionAbove:
435 : case Successor::kConditionAboveOrEqual:
436 : case Successor::kConditionBelow:
437 : case Successor::kConditionBelowOrEqual:
438 : case Successor::kConditionEqual:
439 : case Successor::kConditionGreater:
440 : case Successor::kConditionGreaterOrEqual:
441 : case Successor::kConditionLess:
442 : case Successor::kConditionLessOrEqual:
443 : case Successor::kConditionNotEqual:
444 : case Successor::kConditionNotOverflow:
445 : case Successor::kConditionNotParity:
446 : case Successor::kConditionNotSigned:
447 : case Successor::kConditionOverflow:
448 : case Successor::kConditionParity:
449 : case Successor::kConditionSigned:
450 E : assm.j(static_cast<assm::ConditionCode>(successor.condition), dest);
451 E : break;
452 :
453 : case Successor::kConditionTrue:
454 E : assm.jmp(dest);
455 E : break;
456 :
457 : default:
458 i : NOTREACHED();
459 i : return false;
460 : }
461 :
462 : // Make sure the assembler produced what we expected.
463 E : DCHECK_EQ(successor.size, instructions.back().size());
464 E : DCHECK_EQ(1u, instructions.back().references().size());
465 :
466 : // Copy the tags that are associated with the successor reference to the
467 : // appropriately sized instruction reference. CopyInstructions will then
468 : // take care of updating the tag info map.
469 : instructions.back().references().begin()->second.tags() =
470 E : successor.reference.tags();
471 :
472 : // Update the tag-info map for the successor.
473 : UpdateTagInfoMap(successor.successor->tags(), kSuccessorTag, info.block,
474 E : successor_start, successor.size, tag_info_map_);
475 :
476 : // Walk our start address forwards.
477 E : successor_start += successor.size;
478 :
479 E : if (info.successor_source_range.size() != 0) {
480 E : Instruction& instr = instructions.back();
481 :
482 : // Attribute this instruction to the original successor's source range.
483 E : instr.set_source_range(info.successor_source_range);
484 : }
485 E : }
486 :
487 E : if (!instructions.empty()) {
488 E : Offset start_offset = info.start_offset + info.basic_block_size;
489 E : return CopyInstructions(instructions, start_offset, info.block);
490 : }
491 :
492 E : return true;
493 E : }
494 :
495 E : bool MergeContext::InsertNops(Offset offset, Size bytes, Block* new_block) {
496 E : DCHECK_NE(reinterpret_cast<Block*>(NULL), new_block);
497 :
498 E : uint8* buffer = new_block->GetMutableData();
499 E : DCHECK_NE(reinterpret_cast<uint8*>(NULL), buffer);
500 :
501 : // Use an assembler to insert a proper NOP sequence.
502 : typedef assm::AssemblerImpl Assembler;
503 E : assm::BufferSerializer serializer(buffer + offset, bytes);
504 E : uint32 start_addr = reinterpret_cast<uint32>(buffer) + offset;
505 E : Assembler assm(start_addr, &serializer);
506 E : assm.nop(bytes);
507 :
508 E : return true;
509 E : }
510 :
511 : bool MergeContext::CopyInstructions(
512 : const BasicBlock::Instructions& instructions,
513 E : Offset offset, Block* new_block) {
514 E : DCHECK_NE(reinterpret_cast<Block*>(NULL), new_block);
515 E : DCHECK_EQ(BasicBlock::BASIC_CODE_BLOCK, new_block->type());
516 : // Get the target buffer.
517 E : uint8* buffer = new_block->GetMutableData();
518 E : DCHECK_NE(reinterpret_cast<uint8*>(NULL), buffer);
519 :
520 : // Copy the instruction data and assign each instruction an offset.
521 E : InstructionConstIter it = instructions.begin();
522 E : for (; it != instructions.end(); ++it) {
523 E : const Instruction& instruction = *it;
524 :
525 : // Update the tag-info map for the instruction.
526 : UpdateTagInfoMap(instruction.tags(), kInstructionTag, new_block,
527 E : offset, instruction.size(), tag_info_map_);
528 :
529 : // Copy the instruction bytes.
530 E : ::memcpy(buffer + offset, instruction.data(), instruction.size());
531 :
532 : // Preserve the label on the instruction, if any.
533 E : if (instruction.has_label())
534 E : AddOrMergeLabel(offset, instruction.label(), new_block);
535 :
536 : // Record the source range.
537 : CopySourceRange(instruction.source_range(),
538 : offset, instruction.size(),
539 E : new_block);
540 :
541 : // Copy references.
542 E : CopyReferences(instruction.references(), offset, new_block);
543 :
544 : // Update the offset/bytes_written.
545 E : offset += instruction.size();
546 E : }
547 :
548 E : return true;
549 E : }
550 :
551 : void MergeContext::CopyReferences(
552 : const BasicBlock::BasicBlockReferenceMap& references,
553 E : Offset offset, Block* new_block) {
554 E : BasicBlock::BasicBlockReferenceMap::const_iterator it = references.begin();
555 E : for (; it != references.end(); ++it) {
556 E : BlockGraph::Reference resolved = ResolveReference(it->second);
557 :
558 E : Offset ref_offset = offset + it->first;
559 E : CHECK(new_block->SetReference(ref_offset, resolved));
560 :
561 : // Update the tag-info map for this reference.
562 : UpdateTagInfoMap(it->second.tags(), kReferenceTag, new_block, ref_offset,
563 E : resolved.size(), tag_info_map_);
564 E : }
565 E : }
566 :
567 : bool MergeContext::CopyData(const BasicDataBlock* data_block,
568 : Offset offset,
569 E : Block* new_block) {
570 E : DCHECK_NE(reinterpret_cast<BasicDataBlock*>(NULL), data_block);
571 E : DCHECK_EQ(BasicBlock::BASIC_DATA_BLOCK, data_block->type());
572 :
573 : // Get the target buffer.
574 E : uint8* buffer = new_block->GetMutableData();
575 E : DCHECK_NE(reinterpret_cast<uint8*>(NULL), buffer);
576 :
577 : // Copy the basic-new_block_'s data bytes.
578 E : ::memcpy(buffer + offset, data_block->data(), data_block->size());
579 :
580 : // Record the source range.
581 : CopySourceRange(data_block->source_range(),
582 : offset, data_block->size(),
583 E : new_block);
584 :
585 E : CopyReferences(data_block->references(), offset, new_block);
586 E : return true;
587 E : }
588 :
589 : bool MergeContext::InitializeBlockLayout(const BasicBlockOrdering& order,
590 E : Block* new_block) {
591 : // Populate the initial layout info.
592 E : BasicBlockOrderingConstIter it = order.begin();
593 E : for (; it != order.end(); ++it) {
594 E : const BasicBlock* bb = *it;
595 :
596 : // Propagate BB alignment to the parent block.
597 E : if (bb->alignment() > new_block->alignment())
598 E : new_block->set_alignment(bb->alignment());
599 :
600 : // Create and initialize the layout info for this block.
601 E : DCHECK(layout_info_.find(bb) == layout_info_.end());
602 :
603 E : BasicBlockLayoutInfo& info = layout_info_[bb];
604 E : info.basic_block = bb;
605 E : info.block = new_block;
606 E : info.start_offset = 0;
607 E : info.basic_block_size = kInvalidSize;
608 :
609 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bb);
610 E : if (code_block != NULL)
611 E : info.basic_block_size = code_block->GetInstructionSize();
612 :
613 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bb);
614 E : if (data_block != NULL)
615 E : info.basic_block_size = data_block->size();
616 :
617 E : const BasicEndBlock* end_block = BasicEndBlock::Cast(bb);
618 E : if (end_block != NULL)
619 E : info.basic_block_size = end_block->size();
620 :
621 : // The size must have been set.
622 E : DCHECK_NE(kInvalidSize, info.basic_block_size);
623 :
624 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
625 E : info.successors[i].condition = Successor::kInvalidCondition;
626 E : info.successors[i].size = 0;
627 E : info.successors[i].successor = NULL;
628 E : }
629 :
630 : // Find the next basic block, if any.
631 E : BasicBlockOrderingConstIter next_it(it);
632 E : ++next_it;
633 E : const BasicBlock* next_bb = NULL;
634 E : if (next_it != order.end())
635 E : next_bb = *(next_it);
636 :
637 E : if (code_block == NULL)
638 E : continue;
639 :
640 : // Go through and decide how to manifest the successors for the current
641 : // basic block. A basic block has zero, one or two successors, and any
642 : // successor that refers to the next basic block in sequence is elided, as
643 : // it's most efficient for execution to simply fall through. We do this in
644 : // two nearly-identical code blocks, as the handling is only near-identical
645 : // for each of two possible successors.
646 E : DCHECK_GE(2U, code_block->successors().size());
647 E : SuccessorConstIter succ_it = code_block->successors().begin();
648 E : SuccessorConstIter succ_end = code_block->successors().end();
649 :
650 : // Process the first successor, if any.
651 E : size_t manifested_successors = 0;
652 E : size_t elided_successors = 0;
653 E : if (succ_it != succ_end) {
654 E : const BasicBlock* destination_bb = succ_it->reference().basic_block();
655 :
656 : // Record the source range of the original successor.
657 E : if (succ_it->source_range().size() != 0) {
658 E : DCHECK_EQ(0U, info.successor_source_range.size());
659 E : info.successor_source_range = succ_it->source_range();
660 : }
661 : // Record the label of the original successor.
662 E : if (succ_it->has_label())
663 E : info.successor_label = succ_it->label();
664 :
665 : // Only manifest this successor if it's not referencing the next block.
666 : SuccessorLayoutInfo& successor =
667 E : info.successors[manifested_successors + elided_successors];
668 E : successor.successor = &(*succ_it);
669 E : if (destination_bb == NULL || destination_bb != next_bb) {
670 E : ++manifested_successors;
671 E : successor.condition = succ_it->condition();
672 E : successor.reference = succ_it->reference();
673 E : } else {
674 E : ++elided_successors;
675 : }
676 :
677 : // Go to the next successor, if any.
678 E : ++succ_it;
679 : }
680 :
681 : // Process the second successor, if any.
682 E : if (succ_it != succ_end) {
683 E : const BasicBlock* destination_bb = succ_it->reference().basic_block();
684 :
685 : // Record the source range of the original successor.
686 E : if (succ_it->source_range().size() != 0) {
687 i : DCHECK_EQ(0U, info.successor_source_range.size());
688 i : info.successor_source_range = succ_it->source_range();
689 : }
690 : // Record the label of the original successor.
691 E : if (succ_it->has_label()) {
692 i : DCHECK(!info.successor_label.IsValid());
693 i : info.successor_label = succ_it->label();
694 : }
695 :
696 : // Only manifest this successor if it's not referencing the next block.
697 : SuccessorLayoutInfo& successor =
698 E : info.successors[manifested_successors + elided_successors];
699 E : successor.successor = &(*succ_it);
700 E : if (destination_bb == NULL || destination_bb != next_bb) {
701 E : Successor::Condition condition = succ_it->condition();
702 :
703 : // If we've already manifested a successor above, it'll be for the
704 : // complementary condition to ours. While it's correct to manifest it
705 : // as a conditional branch, it's more efficient to manifest as an
706 : // unconditional jump.
707 E : if (manifested_successors != 0) {
708 : DCHECK_EQ(Successor::InvertCondition(info.successors[0].condition),
709 E : succ_it->condition());
710 :
711 E : condition = Successor::kConditionTrue;
712 : }
713 :
714 E : ++manifested_successors;
715 :
716 E : successor.condition = condition;
717 E : successor.reference = succ_it->reference();
718 E : } else {
719 E : ++elided_successors;
720 : }
721 : }
722 :
723 : // A basic-block can have at most 2 successors by definition. Since we emit
724 : // a successor layout struct for each one (whether or not its elided), we
725 : // expect there to have been as many successors emitted as there are
726 : // successors in the basic block itself.
727 : DCHECK_GE(arraysize(info.successors),
728 E : manifested_successors + elided_successors);
729 : DCHECK_EQ(code_block->successors().size(),
730 E : manifested_successors + elided_successors);
731 E : }
732 :
733 E : return true;
734 E : }
735 :
736 E : bool MergeContext::GenerateBlockLayout(const BasicBlockOrdering& order) {
737 E : BasicBlockOrderingConstIter it = order.begin();
738 :
739 : // Loop over the layout, expanding successors until stable.
740 E : while (true) {
741 E : bool expanded_successor = false;
742 :
743 : // Update the start offset for each of the BBs, respecting the BB alignment
744 : // constraints.
745 E : it = order.begin();
746 E : Offset next_block_start = 0;
747 E : Block* new_block = NULL;
748 E : for (; it != order.end(); ++it) {
749 E : BasicBlockLayoutInfo& info = FindLayoutInfo(*it);
750 : next_block_start = common::AlignUp(next_block_start,
751 E : info.basic_block->alignment());
752 E : info.start_offset = next_block_start;
753 :
754 E : if (new_block == NULL)
755 E : new_block = info.block;
756 E : DCHECK(new_block == info.block);
757 :
758 : next_block_start += info.basic_block_size +
759 : info.successors[0].size +
760 E : info.successors[1].size;
761 E : }
762 :
763 : // See whether there's a need to expand the successor sizes.
764 E : it = order.begin();
765 E : for (; it != order.end(); ++it) {
766 E : const BasicBlock* bb = *it;
767 E : BasicBlockLayoutInfo& info = FindLayoutInfo(bb);
768 :
769 : // Compute the start offset for this block's first successor.
770 E : Offset start_offset = info.start_offset + info.basic_block_size;
771 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
772 E : SuccessorLayoutInfo& successor = info.successors[i];
773 :
774 : // Exit the loop if this (and possibly the subsequent) successor
775 : // is un-manifested.
776 : if (successor.condition == Successor::kInvalidCondition &&
777 E : successor.successor == NULL) {
778 E : break;
779 : }
780 :
781 : // Skip over elided successors.
782 E : DCHECK_NE(reinterpret_cast<Successor*>(NULL), successor.successor);
783 E : if (successor.condition == Successor::kInvalidCondition)
784 E : continue;
785 :
786 : // Compute the new size and update the start offset for the next
787 : // successor (if any).
788 : Size new_size =
789 E : ComputeRequiredSuccessorSize(info, start_offset, successor);
790 E : start_offset += new_size;
791 :
792 : // Keep the biggest offset used by this jump. A jump may temporarily
793 : // appear shorter when the start offset of this basic block has moved
794 : // but the offset of the target basic block still needs to be updated
795 : // within this iteration.
796 E : new_size = std::max(successor.size, new_size);
797 :
798 : // Check whether we're expanding this successor.
799 E : if (new_size != successor.size) {
800 E : successor.size = new_size;
801 E : expanded_successor = true;
802 : }
803 E : }
804 E : }
805 :
806 E : if (!expanded_successor) {
807 : // We've achieved a stable layout and we know that next_block_start
808 : // is the size of the new block, so resize it and allocate the data now.
809 E : new_block->set_size(next_block_start);
810 E : new_block->AllocateData(next_block_start);
811 :
812 E : return true;
813 : }
814 E : }
815 E : }
816 :
817 E : bool MergeContext::GenerateLayout(const BasicBlockSubGraph& subgraph) {
818 : // Create each new block and initialize a layout for it.
819 E : BlockDescriptionConstIter it = subgraph.block_descriptions().begin();
820 E : for (; it != subgraph.block_descriptions().end(); ++it) {
821 E : const BlockDescription& description = *it;
822 :
823 : // Skip the block if it's empty.
824 E : if (description.basic_block_order.empty())
825 i : continue;
826 :
827 : Block* new_block = block_graph_->AddBlock(
828 E : description.type, 0, description.name);
829 E : if (new_block == NULL) {
830 i : LOG(ERROR) << "Failed to create block '" << description.name << "'.";
831 i : return false;
832 : }
833 :
834 : // Save this block in the set of newly generated blocks. On failure, this
835 : // list will be used by GenerateBlocks() to clean up after itself.
836 E : new_blocks_.push_back(new_block);
837 :
838 : // Initialize the new block's properties.
839 E : new_block->set_alignment(description.alignment);
840 E : new_block->set_padding_before(description.padding_before);
841 E : new_block->set_section(description.section);
842 E : new_block->set_attributes(description.attributes);
843 :
844 : // Initialize the layout for this block.
845 E : if (!InitializeBlockLayout(description.basic_block_order, new_block)) {
846 i : LOG(ERROR) << "Failed to initialize layout for basic block '" <<
847 : description.name << "'";
848 i : return false;
849 : }
850 E : }
851 :
852 : // Now generate a layout for each ordering.
853 E : it = subgraph.block_descriptions().begin();
854 E : for (; it != subgraph.block_descriptions().end(); ++it) {
855 E : const BlockDescription& description = *it;
856 :
857 : // Skip the block if it's empty.
858 E : if (description.basic_block_order.empty())
859 i : continue;
860 :
861 : // Generate the layout for this block.
862 E : if (!GenerateBlockLayout(description.basic_block_order)) {
863 i : LOG(ERROR) << "Failed to generate a layout for basic block '" <<
864 : description.name << "'";
865 i : return false;
866 : }
867 E : }
868 :
869 E : return true;
870 E : }
871 :
872 E : bool MergeContext::PopulateBlock(const BasicBlockOrdering& order) {
873 : // Populate the new block with basic blocks.
874 E : BasicBlockOrderingConstIter bb_iter = order.begin();
875 E : BasicBlockOrderingConstIter bb_end = order.end();
876 :
877 E : BlockGraph::Offset prev_offset = 0;
878 :
879 E : for (; bb_iter != bb_end; ++bb_iter) {
880 E : const BasicBlock* bb = *bb_iter;
881 E : const BasicBlockLayoutInfo& info = FindLayoutInfo(bb);
882 :
883 : // Determine the tag type and size associated with this basic block.
884 E : TaggedObjectType tag_type = kBasicDataBlockTag;
885 E : size_t tag_size = info.basic_block_size;
886 E : if (bb->type() == BasicBlock::BASIC_CODE_BLOCK) {
887 : // We include the size of the successors if its a basic code block.
888 E : tag_type = kBasicCodeBlockTag;
889 E : for (size_t i = 0; i < arraysize(info.successors); ++i) {
890 E : if (info.successors[i].condition != Successor::kInvalidCondition)
891 E : tag_size += info.successors[i].size;
892 E : }
893 : }
894 :
895 : // Update the tag-info map for the basic block.
896 : UpdateTagInfoMap(bb->tags(), tag_type, info.block, info.start_offset,
897 E : tag_size, tag_info_map_);
898 :
899 : // Handle any padding for alignment.
900 E : if (info.start_offset > prev_offset) {
901 : if (!InsertNops(prev_offset, info.start_offset - prev_offset,
902 E : info.block)) {
903 i : LOG(ERROR) << "Failed to insert NOPs for '" << bb->name() << "'.";
904 i : return false;
905 : }
906 : }
907 : prev_offset = info.start_offset + info.basic_block_size +
908 E : info.successors[0].size + info.successors[1].size;
909 :
910 : // Handle data basic blocks.
911 E : const BasicDataBlock* data_block = BasicDataBlock::Cast(bb);
912 E : if (data_block != NULL) {
913 : // If the basic-block is labeled, copy the label.
914 E : if (data_block->has_label())
915 E : AddOrMergeLabel(info.start_offset, data_block->label(), info.block);
916 :
917 : // Copy its data.
918 E : if (!CopyData(data_block, info.start_offset, info.block)) {
919 i : LOG(ERROR) << "Failed to copy data for '" << bb->name() << "'.";
920 i : return false;
921 : }
922 : }
923 :
924 : // Handle code basic blocks.
925 E : const BasicCodeBlock* code_block = BasicCodeBlock::Cast(bb);
926 E : if (code_block != NULL) {
927 : // Copy the instructions.
928 : if (!CopyInstructions(code_block->instructions(),
929 : info.start_offset,
930 E : info.block)) {
931 i : LOG(ERROR) << "Failed to copy instructions for '" << bb->name() << "'.";
932 i : return false;
933 : }
934 :
935 : // Synthesize the successor instructions and assign each to an offset.
936 E : if (!AssembleSuccessors(info)) {
937 i : LOG(ERROR) << "Failed to create successors for '" << bb->name() << "'.";
938 i : return false;
939 : }
940 : }
941 :
942 E : const BasicEndBlock* end_block = BasicEndBlock::Cast(bb);
943 E : if (end_block != NULL) {
944 : // If the end block is labeled, copy the label.
945 E : if (end_block->has_label())
946 E : AddOrMergeLabel(info.start_offset, end_block->label(), info.block);
947 : }
948 :
949 : // We must have handled the basic block as at least one of the fundamental
950 : // types.
951 E : DCHECK(code_block != NULL || data_block != NULL || end_block != NULL);
952 E : }
953 :
954 E : return true;
955 E : }
956 :
957 E : bool MergeContext::PopulateBlocks(const BasicBlockSubGraph& subgraph) {
958 : // Create each new block and generate a layout for it.
959 E : BlockDescriptionConstIter it = subgraph.block_descriptions().begin();
960 E : for (; it != subgraph.block_descriptions().end(); ++it) {
961 E : const BasicBlockOrdering& order = it->basic_block_order;
962 :
963 : // Skip the block if it's empty.
964 E : if (order.empty())
965 i : continue;
966 :
967 E : if (!PopulateBlock(order))
968 i : return false;
969 E : }
970 :
971 E : return true;
972 E : }
973 :
974 E : void MergeContext::UpdateReferrers(const BasicBlock* bb) const {
975 E : DCHECK_NE(reinterpret_cast<BasicBlock*>(NULL), bb);
976 :
977 : // Find the current location of this basic block.
978 E : BasicBlockLayoutInfoMap::const_iterator layout_it = layout_info_.find(bb);
979 E : DCHECK(layout_it != layout_info_.end());
980 E : const BasicBlockLayoutInfo& info = layout_it->second;
981 E : DCHECK_EQ(bb, info.basic_block);
982 :
983 : // Update all external referrers to point to the new location.
984 E : const BasicBlock::BasicBlockReferrerSet& referrers = bb->referrers();
985 E : BasicBlock::BasicBlockReferrerSet::const_iterator it = referrers.begin();
986 E : for (; it != referrers.end(); ++it) {
987 : // Get a non-const pointer to the referring block. Note that we don't
988 : // modify the set property on referrers as we update the block's references.
989 E : const BasicBlockReferrer& referrer = *it;
990 E : Block* referring_block = const_cast<Block*>(referrer.block());
991 E : BlockGraph::Reference old_ref;
992 E : bool found = referring_block->GetReference(referrer.offset(), &old_ref);
993 E : DCHECK(found);
994 :
995 : // The base of the reference is directed to the corresponding BB's
996 : // start address in the new block.
997 : BlockGraph::Reference new_ref(old_ref.type(),
998 : old_ref.size(),
999 : info.block,
1000 : info.start_offset,
1001 E : info.start_offset);
1002 :
1003 E : bool is_new = referring_block->SetReference(referrer.offset(), new_ref);
1004 E : DCHECK(!is_new); // TODO(rogerm): Is this a valid DCHECK?
1005 E : }
1006 E : }
1007 :
1008 E : void MergeContext::RemoveOriginalBlock(BasicBlockSubGraph* subgraph) {
1009 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
1010 E : DCHECK_EQ(original_block_, subgraph->original_block());
1011 :
1012 E : Block* original_block = const_cast<Block*>(this->original_block_);
1013 E : if (original_block == NULL)
1014 E : return;
1015 :
1016 E : DCHECK(!original_block->HasExternalReferrers());
1017 :
1018 E : bool removed = original_block->RemoveAllReferences();
1019 E : DCHECK(removed);
1020 :
1021 E : removed = block_graph_->RemoveBlock(original_block);
1022 E : DCHECK(removed);
1023 :
1024 E : subgraph->set_original_block(NULL);
1025 E : original_block_ = NULL;
1026 E : }
1027 :
1028 E : Size MergeContext::GetShortSuccessorSize(Successor::Condition condition) {
1029 E : switch (condition) {
1030 : case Successor::kConditionAbove:
1031 : case Successor::kConditionAboveOrEqual:
1032 : case Successor::kConditionBelow:
1033 : case Successor::kConditionBelowOrEqual:
1034 : case Successor::kConditionEqual:
1035 : case Successor::kConditionGreater:
1036 : case Successor::kConditionGreaterOrEqual:
1037 : case Successor::kConditionLess:
1038 : case Successor::kConditionLessOrEqual:
1039 : case Successor::kConditionNotEqual:
1040 : case Successor::kConditionNotOverflow:
1041 : case Successor::kConditionNotParity:
1042 : case Successor::kConditionNotSigned:
1043 : case Successor::kConditionOverflow:
1044 : case Successor::kConditionParity:
1045 : case Successor::kConditionSigned:
1046 : // Translates to a conditional branch.
1047 E : return assm::kShortBranchSize;
1048 :
1049 : case Successor::kConditionTrue:
1050 : // Translates to a jump.
1051 E : return assm::kShortJumpSize;
1052 :
1053 : default:
1054 i : NOTREACHED() << "Unsupported successor type.";
1055 i : return 0;
1056 : }
1057 E : }
1058 :
1059 E : Size MergeContext::GetLongSuccessorSize(Successor::Condition condition) {
1060 E : switch (condition) {
1061 : case Successor::kConditionAbove:
1062 : case Successor::kConditionAboveOrEqual:
1063 : case Successor::kConditionBelow:
1064 : case Successor::kConditionBelowOrEqual:
1065 : case Successor::kConditionEqual:
1066 : case Successor::kConditionGreater:
1067 : case Successor::kConditionGreaterOrEqual:
1068 : case Successor::kConditionLess:
1069 : case Successor::kConditionLessOrEqual:
1070 : case Successor::kConditionNotEqual:
1071 : case Successor::kConditionNotOverflow:
1072 : case Successor::kConditionNotParity:
1073 : case Successor::kConditionNotSigned:
1074 : case Successor::kConditionOverflow:
1075 : case Successor::kConditionParity:
1076 : case Successor::kConditionSigned:
1077 : // Translates to a conditional branch.
1078 E : return assm::kLongBranchSize;
1079 :
1080 : case Successor::kConditionTrue:
1081 : // Translates to a jump.
1082 E : return assm::kLongJumpSize;
1083 :
1084 : default:
1085 i : NOTREACHED() << "Unsupported successor type.";
1086 i : return 0;
1087 : }
1088 E : }
1089 :
1090 : Size MergeContext::ComputeRequiredSuccessorSize(
1091 : const BasicBlockLayoutInfo& info,
1092 : Offset start_offset,
1093 E : const SuccessorLayoutInfo& successor) {
1094 E : switch (successor.reference.referred_type()) {
1095 : case BasicBlockReference::REFERRED_TYPE_BLOCK:
1096 E : return GetLongSuccessorSize(successor.condition);
1097 :
1098 : case BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK: {
1099 E : Size short_size = GetShortSuccessorSize(successor.condition);
1100 E : const BasicBlock* dest_bb = successor.reference.basic_block();
1101 E : DCHECK_NE(reinterpret_cast<BasicBlock*>(NULL), dest_bb);
1102 E : const BasicBlockLayoutInfo& dest = FindLayoutInfo(dest_bb);
1103 :
1104 : // If the destination is within the same destination block,
1105 : // let's see if we can use a short reach here.
1106 E : if (info.block == dest.block) {
1107 : Offset destination_offset =
1108 E : dest.start_offset - (start_offset + short_size);
1109 :
1110 : // Are we in-bounds for a short reference?
1111 : if (destination_offset <= std::numeric_limits<int8>::max() &&
1112 E : destination_offset >= std::numeric_limits<int8>::min()) {
1113 E : return short_size;
1114 : }
1115 : }
1116 :
1117 E : return GetLongSuccessorSize(successor.condition);
1118 : }
1119 :
1120 : default:
1121 i : NOTREACHED() << "Impossible Successor reference type.";
1122 i : return 0;
1123 : }
1124 E : }
1125 :
1126 : MergeContext::BasicBlockLayoutInfo& MergeContext::FindLayoutInfo(
1127 E : const BasicBlock* bb) {
1128 E : BasicBlockLayoutInfoMap::iterator it = layout_info_.find(bb);
1129 E : DCHECK(it != layout_info_.end());
1130 E : DCHECK_EQ(bb, it->second.basic_block);
1131 :
1132 E : return it->second;
1133 E : }
1134 :
1135 : const MergeContext::BasicBlockLayoutInfo& MergeContext::FindLayoutInfo(
1136 E : const BasicBlock* bb) const {
1137 E : BasicBlockLayoutInfoMap::const_iterator it = layout_info_.find(bb);
1138 E : DCHECK(it != layout_info_.end());
1139 E : DCHECK_EQ(bb, it->second.basic_block);
1140 :
1141 E : return it->second;
1142 E : }
1143 :
1144 : BlockGraph::Reference MergeContext::ResolveReference(
1145 : BlockGraph::ReferenceType type, Size size,
1146 E : const BasicBlockReference& ref) const {
1147 E : if (ref.referred_type() == BasicBlockReference::REFERRED_TYPE_BASIC_BLOCK) {
1148 : // It's a basic block reference, we need to resolve it to a
1149 : // block reference.
1150 E : const BasicBlockLayoutInfo& info = FindLayoutInfo(ref.basic_block());
1151 :
1152 : return BlockGraph::Reference(type,
1153 : size,
1154 : info.block,
1155 : info.start_offset,
1156 E : info.start_offset);
1157 i : } else {
1158 E : DCHECK_EQ(BasicBlockReference::REFERRED_TYPE_BLOCK, ref.referred_type());
1159 E : DCHECK_NE(ref.block(), original_block_);
1160 :
1161 : return BlockGraph::Reference(type,
1162 : size,
1163 : const_cast<Block*>(ref.block()),
1164 : ref.offset(),
1165 E : ref.base());
1166 : }
1167 E : }
1168 :
1169 : BlockGraph::Reference MergeContext::ResolveReference(
1170 E : const BasicBlockReference& ref) const {
1171 E : return ResolveReference(ref.reference_type(), ref.size(), ref);
1172 E : }
1173 :
1174 : } // namespace
1175 :
1176 E : BlockBuilder::BlockBuilder(BlockGraph* bg) : block_graph_(bg) {
1177 E : }
1178 :
1179 E : bool BlockBuilder::Merge(BasicBlockSubGraph* subgraph) {
1180 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
1181 :
1182 : // Before starting the layout ensure any BasicEndBlocks are at the end of/
1183 : // their respective basic-block orderings.
1184 E : if (!EndBlocksAreWellPlaced(subgraph))
1185 E : return false;
1186 :
1187 : MergeContext context(block_graph_,
1188 : subgraph->original_block(),
1189 E : &tag_info_map_);
1190 :
1191 E : if (!context.GenerateBlocks(*subgraph))
1192 i : return false;
1193 :
1194 E : context.TransferReferrers(subgraph);
1195 E : context.RemoveOriginalBlock(subgraph);
1196 :
1197 : // Track the newly created blocks.
1198 E : new_blocks_.reserve(new_blocks_.size() + context.new_blocks().size());
1199 : new_blocks_.insert(new_blocks_.end(),
1200 : context.new_blocks().begin(),
1201 E : context.new_blocks().end());
1202 :
1203 : // And we're done.
1204 E : return true;
1205 E : }
1206 :
1207 : } // namespace block_graph
|