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