1 : // Copyright 2012 Google Inc.
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 <map>
24 : #include <utility>
25 : #include <vector>
26 :
27 : #include "syzygy/block_graph/basic_block.h"
28 : #include "syzygy/block_graph/basic_block_subgraph.h"
29 : #include "syzygy/block_graph/block_graph.h"
30 : #include "syzygy/core/assembler.h"
31 :
32 : namespace block_graph {
33 :
34 : namespace {
35 :
36 : // A bunch of handy typedefs for some verbose types.
37 : typedef BlockGraph::Block Block;
38 : typedef BlockGraph::Offset Offset;
39 : typedef BlockGraph::Size Size;
40 : typedef BasicBlockSubGraph::BlockDescription BlockDescription;
41 : typedef BasicBlockSubGraph::BlockDescriptionList BlockDescriptionList;
42 : typedef BasicBlockSubGraph::BasicBlockOrdering BasicBlockOrdering;
43 : typedef BasicBlockOrdering::const_iterator BasicBlockOrderingConstIter;
44 : typedef BlockDescriptionList::const_iterator BlockDescriptionConstIter;
45 : typedef BasicBlock::Instructions::const_iterator InstructionConstIter;
46 : typedef BasicBlock::Successors::const_iterator SuccessorConstIter;
47 :
48 : // A helper class to track the location to which a block element (a basic-block,
49 : // instruction, or successor reference) has been mapped.
50 : class LocationMap {
51 : public:
52 : // Remember the location of the given @p obj in the current context.
53 : // @param obj The object to remember.
54 : // @param b The block in which @p obj was placed.
55 : // @param n The offset in @p b at which @p obj was placed.
56 : // Returns false if the @p obj has already been assigned a location.
57 E : bool Add(const void* obj, Block* b, Offset n) {
58 E : DCHECK(obj != NULL);
59 E : DCHECK(b != NULL);
60 E : DCHECK_LE(0, n);
61 E : return map_.insert(std::make_pair(obj, std::make_pair(b, n))).second;
62 E : }
63 :
64 : // Find the location of the given @p object in the current context.
65 : // @param obj The object to find.
66 : // @param b The block in which @p object was place is returned here.
67 : // @param n The offset in @p b at which @p obj was placed is returned here.
68 : // Returns false if the object is not found.
69 E : bool Find(const void* obj, Block** b, Offset* n) const {
70 E : DCHECK(obj != NULL);
71 E : DCHECK(b != NULL);
72 E : DCHECK(n != NULL);
73 E : Map::const_iterator loc_iter = map_.find(obj);
74 E : if (loc_iter == map_.end())
75 E : return false;
76 E : *b = loc_iter->second.first;
77 E : *n = loc_iter->second.second;
78 E : return true;
79 E : }
80 :
81 : // Returns the final block reference corresponding to a basic-block reference.
82 E : BlockGraph::Reference Resolve(const BasicBlockReference& bb_ref) const {
83 E : if (bb_ref.block() != NULL) {
84 : return BlockGraph::Reference(bb_ref.reference_type(), bb_ref.size(),
85 : const_cast<Block*>(bb_ref.block()),
86 : bb_ref.offset(),
87 E : bb_ref.base());
88 : }
89 :
90 E : DCHECK(bb_ref.basic_block() != NULL);
91 E : DCHECK_EQ(0, bb_ref.base());
92 :
93 E : Block* block = NULL;
94 E : Offset base = 0;
95 E : bool found = Find(bb_ref.basic_block(), &block, &base);
96 E : DCHECK(found);
97 :
98 : return BlockGraph::Reference(bb_ref.reference_type(), bb_ref.size(), block,
99 E : base + bb_ref.offset(), base);
100 E : }
101 :
102 : private:
103 : // The underlying data structures.
104 : typedef std::pair<Block*, Offset> Location;
105 : typedef std::map<const void*, Location> Map;
106 : Map map_;
107 : };
108 :
109 : // A utility structure to package up the context in which a new block is
110 : // generated. This reduces the amount of context parameters being passed
111 : // around from call to call.
112 : // TODO(rogerm): Make the calls that take MergeContext members functions
113 : // as soon as it is convenient to do so.
114 : struct MergeContext {
115 : // Initialize a MergeContext with the block graph and original block.
116 E : MergeContext(BlockGraph* bg, const Block* ob)
117 : : block_graph(bg), original_block(ob), new_block(NULL), offset(0) {
118 E : DCHECK(bg != NULL);
119 E : }
120 :
121 : // The mapped locations of the block elements.
122 : LocationMap locations;
123 :
124 : // The block graph in which the new blocks are generated.
125 : BlockGraph* const block_graph;
126 :
127 : // The original block from which the new blocks are derived.
128 : const Block* original_block;
129 :
130 : // The set of blocks generated in this context.
131 : BlockVector new_blocks;
132 :
133 : // The current new block being generated.
134 : Block* new_block;
135 :
136 : // The current write offset into the new block.
137 : Offset offset;
138 : };
139 :
140 : // Serializes instruction bytes to a target buffer.
141 : // TODO(siggi, rogerm): Reconsider this approach when there's a BlockAssembler.
142 : class Serializer : public core::AssemblerImpl::InstructionSerializer {
143 : public:
144 E : explicit Serializer(uint8* buffer) : buffer_(buffer) {
145 E : DCHECK(buffer != NULL);
146 E : }
147 :
148 : virtual void AppendInstruction(uint32 location,
149 : const uint8* bytes,
150 : size_t num_bytes,
151 : const size_t* /* ref_locations */,
152 : const void* const* /* refs */,
153 E : size_t /* num_refs */) OVERRIDE {
154 E : DCHECK(bytes != NULL);
155 E : ::memcpy(buffer_ + location, bytes, num_bytes);
156 E : }
157 :
158 : protected:
159 : uint8* const buffer_;
160 : };
161 :
162 : // Update the new working block with the source range for the bytes in the
163 : // range [new_offset, new_offset + new_size).
164 : // @param original_offset The offset in the original block corresponding to
165 : // the bytes in the new block. This may be BlockGraphh::kNoOffset, if
166 : // the source range in question is for synthesized bytes (for example,
167 : // a flow-through successor that will be synthesized as a branch).
168 : // @param original_size The number of bytes in the original range.
169 : // @param new_offset The offset in the new block where the original bytes
170 : // will now live.
171 : // @param new_size The number of bytes the new range occupies.
172 : // @param ctx The merge context.
173 : void UpdateSourceRange(Offset original_offset,
174 : Size original_size,
175 : Offset new_offset,
176 : Size new_size,
177 E : MergeContext* ctx) {
178 E : DCHECK_LE(0, new_offset);
179 E : DCHECK_NE(0U, new_size);
180 E : DCHECK(ctx != NULL);
181 E : DCHECK(ctx->new_block != NULL);
182 :
183 : // If the entire block is synthesized or just this new byte range is
184 : // synthesized, there's nothing to do.
185 E : if (ctx->original_block == NULL || original_offset == BasicBlock::kNoOffset) {
186 E : return;
187 : }
188 :
189 : // Find the source range for the original bytes. We may not have source
190 : // data for bytes that were synthesized in other transformations.
191 : // TODO(rogerm): During decomposition the basic-block decomposer should
192 : // incorporate the source ranges for each subgraph element (data/padding
193 : // basic-blocks, instructions and successors) into each element itself.
194 : const Block::SourceRanges::RangePair* range_pair =
195 : ctx->original_block->source_ranges().FindRangePair(original_offset,
196 E : original_size);
197 E : if (range_pair == NULL)
198 E : return;
199 :
200 E : core::RelativeAddress source_addr;
201 E : Size source_size = 0;
202 :
203 : if (original_offset != range_pair->first.start() ||
204 E : original_size != range_pair->first.size()) {
205 : // It must be that the mapping is one-to-one, that is, the source and
206 : // destination ranges must be the same size.
207 E : CHECK_EQ(range_pair->first.size(), range_pair->second.size());
208 E : Offset source_offset = original_offset - range_pair->first.start();
209 E : source_addr = range_pair->second.start() + source_offset;
210 E : source_size = original_size;
211 E : } else {
212 : // Otherwise, we must have that the range_pair matches exactly the original
213 : // offset and size, in which case we want to use the whole of the second
214 : // part of the pair.
215 E : CHECK_EQ(original_offset, range_pair->first.start());
216 E : CHECK_EQ(original_size, range_pair->first.size());
217 E : source_addr = range_pair->second.start();
218 E : source_size = range_pair->second.size();
219 : }
220 :
221 : // Insert the new source range mapping into the new block.
222 : bool inserted = ctx->new_block->source_ranges().Insert(
223 : Block::DataRange(new_offset, new_size),
224 E : Block::SourceRange(source_addr, source_size));
225 E : DCHECK(inserted);
226 E : }
227 :
228 : // Synthesize the instruction(s) to implement the given @p successor.
229 : // @param successor The successor to synthesize.
230 : // @param condition The condition to synthesize (overrides that of successor).
231 : // @param ctx The merge context describing where the instructions should be
232 : // synthesized.
233 : bool SynthesizeSuccessor(const Successor& successor,
234 : Successor::Condition condition,
235 E : MergeContext* ctx) {
236 E : DCHECK_LT(Successor::kInvalidCondition, condition);
237 E : DCHECK(ctx != NULL);
238 E : DCHECK(ctx->new_block != NULL);
239 :
240 : // We use a temporary target location when assembling only to satisfy the
241 : // assembler interface. We will actually synthesize references that will
242 : // be responsible for filling in the correct values.
243 : // TODO(siggi, rogerm): Revisit once the BlockAssembler becomes available.
244 E : static const core::ImmediateImpl kTempTarget(0, core::kSize32Bit);
245 : static const size_t k32BitsInBytes = 4;
246 :
247 : // Create the assembler.
248 E : Serializer serializer(ctx->new_block->GetMutableData());
249 E : core::AssemblerImpl asm_(ctx->offset, &serializer);
250 :
251 : // Synthesize the instruction(s) corresponding to the condition.
252 E : if (condition <= Successor::kMaxConditionalBranch) {
253 E : asm_.j(static_cast<core::ConditionCode>(condition), kTempTarget);
254 E : } else {
255 E : switch (condition) {
256 : case Successor::kConditionTrue:
257 E : asm_.jmp(kTempTarget);
258 E : break;
259 : case Successor::kCounterIsZero:
260 i : asm_.jecxz(kTempTarget);
261 i : break;
262 : case Successor::kLoopTrue:
263 i : asm_.loop(kTempTarget);
264 i : break;
265 : case Successor::kLoopIfEqual:
266 i : asm_.loope(kTempTarget);
267 i : break;
268 : case Successor::kLoopIfNotEqual:
269 i : asm_.loopne(kTempTarget);
270 i : break;
271 : case Successor::kInverseCounterIsZero:
272 : case Successor::kInverseLoopTrue:
273 : case Successor::kInverseLoopIfEqual:
274 : case Successor::kInverseLoopIfNotEqual:
275 i : LOG(ERROR) << "Synthesis of inverse loop and counter branches is "
276 : << "not supported yet.";
277 i : return false;
278 :
279 : default:
280 i : NOTREACHED();
281 i : return false;
282 : }
283 : }
284 :
285 : // Remember where the reference for this successor has been placed. In each
286 : // of the above synthesized cases, it is the last thing written to the buffer.
287 E : Offset ref_offset = asm_.location() - k32BitsInBytes;
288 E : bool inserted = ctx->locations.Add(&successor, ctx->new_block, ref_offset);
289 E : DCHECK(inserted);
290 :
291 : // Calculate the number of bytes written.
292 E : size_t bytes_written = asm_.location() - ctx->offset;
293 :
294 : // Update the source range.
295 : UpdateSourceRange(successor.instruction_offset(),
296 : successor.instruction_size(),
297 : ctx->offset, // This is where we started writing.
298 : bytes_written,
299 E : ctx);
300 :
301 : // Update the write location.
302 E : ctx->offset = asm_.location();
303 :
304 : // And we're done.
305 E : return true;
306 E : }
307 :
308 : // Generate the byte sequence for the given @p successors. This function
309 : // handles the elision of successors that would naturally flow through to
310 : // the @p next_bb_in_ordering.
311 : // @param successors The successors to synthesize.
312 : // @param next_bb_in_ordering The next basic block in the basic block ordering.
313 : // If a successor refers to the next basic-block in the ordering it does
314 : // not have to be synthesized into a branch instruction as control flow
315 : // will naturally continue into it.
316 : // @param ctx The merge context describing where the successors should be
317 : // synthesized.
318 : bool SynthesizeSuccessors(const BasicBlock::Successors& successors,
319 : const BasicBlock* next_bb_in_ordering,
320 E : MergeContext* ctx) {
321 E : DCHECK(ctx != NULL);
322 :
323 E : size_t num_successors = successors.size();
324 E : DCHECK_GE(2U, num_successors);
325 :
326 : // If there are no successors then we have nothing to do.
327 E : if (num_successors == 0)
328 E : return true;
329 :
330 : // If a successor is labeled, preserve it. Note that we expect at most one
331 : // successor to be labeled. We apply the label before synthesis because it
332 : // is possible that the labeled successor may be elided if control flow is
333 : // straightened.
334 E : if (successors.front().has_label()) {
335 E : ctx->new_block->SetLabel(ctx->offset, successors.front().label());
336 E : } else if (num_successors == 2 && successors.back().has_label()) {
337 i : ctx->new_block->SetLabel(ctx->offset, successors.back().label());
338 : }
339 :
340 : // Track whether we have already generated a successor. We can use this to
341 : // optimize the branch not taken case in the event both successors are
342 : // generated (the next_bb_in_ordering does not match any of the successors).
343 : // Since we have at most 2 successors (and they'll have inverse conditions
344 : // if there are two) then the second successor (if generated) can be modified
345 : // to be an unconditional branch. Note that if we generalize to an arbitrary
346 : // set of successors this optimization must be removed.
347 E : bool branch_has_already_been_generated = false;
348 :
349 : // If there is no next_bb_in_ordering or the first successor does not refer
350 : // to next_bb_in_ordering, then we must generate the instruction for it, as
351 : // it cannot be a fall-through or branch-not-taken successor.
352 E : const Successor& successor_a = successors.front();
353 : if (next_bb_in_ordering == NULL ||
354 E : successor_a.reference().basic_block() != next_bb_in_ordering) {
355 E : if (!SynthesizeSuccessor(successor_a, successor_a.condition(), ctx))
356 i : return false;
357 E : branch_has_already_been_generated = true;
358 : }
359 :
360 : // If there is only one successor, then we have nothing further to do.
361 E : if (num_successors == 1) {
362 E : DCHECK_EQ(Successor::kConditionTrue, successor_a.condition());
363 E : return true;
364 : }
365 :
366 : // If there is no next_bb_in_ordering or the second successor does not refer
367 : // to next_bb_in_ordering, then we must generate the instruction for it, as
368 : // it cannot be the branch-not-taken fall-through successor.
369 E : const Successor& successor_b = successors.back();
370 : DCHECK_EQ(successor_a.condition(),
371 E : Successor::InvertCondition(successor_b.condition()));
372 : if (next_bb_in_ordering == NULL ||
373 E : successor_b.reference().basic_block() != next_bb_in_ordering) {
374 E : Successor::Condition condition = successor_b.condition();
375 E : if (branch_has_already_been_generated)
376 E : condition = Successor::kConditionTrue;
377 E : if (!SynthesizeSuccessor(successor_b, condition, ctx))
378 i : return false;
379 : }
380 :
381 E : return true;
382 E : }
383 :
384 : // Copy the given @p instructions to the current working block.
385 : // @param instructions The instructions to copy.
386 : // @param ctx The merge context describing where the instructions should be
387 : // copied.
388 : bool CopyInstructions(const BasicBlock::Instructions& instructions,
389 E : MergeContext* ctx) {
390 E : DCHECK(ctx != NULL);
391 E : DCHECK_EQ(BasicBlock::BASIC_CODE_BLOCK, ctx->new_block->type());
392 : // Get the target buffer.
393 E : uint8* buffer = ctx->new_block->GetMutableData();
394 E : DCHECK(buffer != NULL);
395 :
396 : // Copy the instruction data and assign each instruction an offset.
397 E : InstructionConstIter it = instructions.begin();
398 E : for (; it != instructions.end(); ++it) {
399 E : const Instruction& instruction = *it;
400 E : Offset offset = ctx->offset;
401 :
402 : // Remember where this instruction begins.
403 E : bool inserted = ctx->locations.Add(&instruction, ctx->new_block, offset);
404 E : DCHECK(inserted);
405 :
406 : // Copy the instruction bytes.
407 : ::memcpy(buffer + offset,
408 : instruction.data(),
409 E : instruction.size());
410 :
411 : // Preserve the label on the instruction, if any.
412 E : if (instruction.has_label())
413 E : ctx->new_block->SetLabel(ctx->offset, instruction.label());
414 :
415 : // Update the offset/bytes_written.
416 E : ctx->offset += instruction.size();
417 :
418 : // Record the source range.
419 : UpdateSourceRange(instruction.offset(), instruction.size(),
420 E : offset, instruction.size(), ctx);
421 E : }
422 :
423 E : return true;
424 E : }
425 :
426 : // Copy the data (or padding bytes) in @p basic_block into new working block.
427 : // @param basic_block The basic_block to copy.
428 : // @param ctx The merge context describing where the data should be copied.
429 E : bool CopyData(const BasicBlock* basic_block, MergeContext* ctx) {
430 E : DCHECK(basic_block != NULL);
431 : DCHECK(basic_block->type() == BasicBlock::BASIC_DATA_BLOCK ||
432 E : basic_block->type() == BasicBlock::BASIC_PADDING_BLOCK);
433 E : DCHECK(ctx != NULL);
434 :
435 : // Get the target buffer.
436 E : uint8* buffer = ctx->new_block->GetMutableData();
437 E : DCHECK(buffer != NULL);
438 :
439 : // Copy the basic-new_block's data bytes.
440 E : Offset offset = ctx->offset;
441 E : ::memcpy(buffer + ctx->offset, basic_block->data(), basic_block->size());
442 E : ctx->offset += basic_block->size();
443 :
444 : // Record the source range.
445 : UpdateSourceRange(basic_block->offset(), basic_block->size(),
446 E : offset, basic_block->size(), ctx);
447 :
448 E : return true;
449 E : }
450 :
451 : // Generate a new block based on the given block @p description.
452 : // @param description Defines the block properties and basic blocks to use
453 : // when creating the @p new_block.
454 : // @param ctx The merge context into which the new block will be generated.
455 E : bool GenerateBlock(const BlockDescription& description, MergeContext* ctx) {
456 E : DCHECK(ctx != NULL);
457 :
458 : // Remember the max size of the described block.
459 E : size_t max_size = description.GetMaxSize();
460 :
461 : // Allocate a new block for this description.
462 E : ctx->offset = 0;
463 : ctx->new_block = ctx->block_graph->AddBlock(
464 E : description.type, max_size, description.name);
465 E : if (ctx->new_block == NULL) {
466 i : LOG(ERROR) << "Failed to create block '" << description.name << "'.";
467 i : return false;
468 : }
469 :
470 : // Save this block in the set of newly generated blocks. On failure, this
471 : // list will be used by GenerateBlocks() to clean up after itself.
472 E : ctx->new_blocks.push_back(ctx->new_block);
473 :
474 : // Allocate the data buffer for the new block.
475 E : if (ctx->new_block->AllocateData(max_size) == NULL) {
476 i : LOG(ERROR) << "Failed to allocate block data '" << description.name << "'.";
477 i : return false;
478 : }
479 :
480 : // Initialize the new block's properties.
481 E : ctx->new_block->set_alignment(description.alignment);
482 E : ctx->new_block->set_section(description.section);
483 E : ctx->new_block->set_attributes(description.attributes);
484 :
485 : // Populate the new block with basic blocks.
486 E : BasicBlockOrderingConstIter bb_iter = description.basic_block_order.begin();
487 E : BasicBlockOrderingConstIter bb_end = description.basic_block_order.end();
488 E : for (; bb_iter != bb_end; ++bb_iter) {
489 E : const BasicBlock* bb = *bb_iter;
490 :
491 : // Remember where this basic block begins.
492 E : bool inserted = ctx->locations.Add(bb, ctx->new_block, ctx->offset);
493 E : DCHECK(inserted);
494 :
495 : // If the basic-block is labeled, copy the label.
496 E : if (bb->has_label())
497 E : ctx->new_block->SetLabel(ctx->offset, bb->label());
498 :
499 : // Copy the contents of the basic block into the new block.
500 E : if (bb->type() != BasicBlock::BASIC_CODE_BLOCK) {
501 : // If it's not a code basic-block then all we need to do is copy its data.
502 E : if (!CopyData(bb, ctx)) {
503 i : LOG(ERROR) << "Failed to copy data for '" << bb->name() << "'.";
504 i : return false;
505 : }
506 E : } else {
507 : // Copy the instructions.
508 E : if (!CopyInstructions(bb->instructions(), ctx)) {
509 i : LOG(ERROR) << "Failed to copy instructions for '" << bb->name() << "'.";
510 i : return false;
511 : }
512 :
513 : // Calculate the next basic block in the ordering.
514 E : BasicBlockOrderingConstIter next_bb_iter = bb_iter;
515 E : ++next_bb_iter;
516 E : const BasicBlock* next_bb = NULL;
517 E : if (next_bb_iter != bb_end)
518 E : next_bb = *next_bb_iter;
519 :
520 : // Synthesize the successor instructions and assign each to an offset.
521 E : if (!SynthesizeSuccessors(bb->successors(), next_bb, ctx)) {
522 i : LOG(ERROR) << "Failed to create successors for '" << bb->name() << "'.";
523 i : return false;
524 : }
525 E : }
526 E : }
527 :
528 E : DCHECK_LT(0, ctx->offset);
529 E : DCHECK_LE(static_cast<BlockGraph::Size>(ctx->offset), max_size);
530 :
531 : // Truncate the block to the number of bytes actually written.
532 E : ctx->new_block->ResizeData(ctx->offset);
533 E : ctx->new_block->set_size(ctx->offset);
534 :
535 : // Reset the current working block.
536 E : ctx->new_block = NULL;
537 E : ctx->offset = 0;
538 :
539 : // And we're done.
540 E : return true;
541 E : }
542 :
543 : // Generate all of the blocks described in @p subgraph.
544 : // @param subgraph Defines the block properties and basic blocks to use
545 : // for each of the blocks to be created.
546 : // @param ctx The merge context into which the new blocks will be generated.
547 E : bool GenerateBlocks(const BasicBlockSubGraph* subgraph, MergeContext* ctx) {
548 E : DCHECK(subgraph != NULL);
549 E : DCHECK(ctx != NULL);
550 :
551 : // Create a new block for each block description and remember the association.
552 E : BlockDescriptionConstIter bd_iter = subgraph->block_descriptions().begin();
553 E : for (; bd_iter != subgraph->block_descriptions().end(); ++bd_iter) {
554 E : const BlockDescription& description = *bd_iter;
555 :
556 : // Skip the block if it's empty.
557 E : if (description.basic_block_order.empty())
558 i : continue;
559 :
560 E : if (!GenerateBlock(description, ctx)) {
561 : // Remove generated blocks (this is safe as they're all disconnected)
562 : // and return false.
563 i : BlockVector::iterator it = ctx->new_blocks.begin();
564 i : for (; it != ctx->new_blocks.end(); ++it) {
565 i : DCHECK((*it)->referrers().empty());
566 i : DCHECK((*it)->references().empty());
567 i : ctx->block_graph->RemoveBlock(*it);
568 i : }
569 i : ctx->new_blocks.clear();
570 i : ctx->new_block = NULL;
571 i : ctx->offset = 0;
572 i : return false;
573 : }
574 E : }
575 :
576 E : return true;
577 E : }
578 :
579 : // Transfer all external referrers that refer to @p bb to point to
580 : // bb's new location instead of to the original block.
581 : // @param ctx The merge context.
582 : // @param bb The basic block.
583 E : void UpdateReferrers(const MergeContext& ctx, const BasicBlock* bb) {
584 E : DCHECK(bb != NULL);
585 :
586 : // Find the current location of this basic block.
587 E : Block* new_block = NULL;
588 E : Offset new_base = 0;
589 E : bool found = ctx.locations.Find(bb, &new_block, &new_base);
590 E : DCHECK(found);
591 :
592 : // Update all external referrers to point to the new location.
593 E : const BasicBlock::BasicBlockReferrerSet& referrers = bb->referrers();
594 E : BasicBlock::BasicBlockReferrerSet::const_iterator it = referrers.begin();
595 E : for (; it != referrers.end(); ++it) {
596 : // Get a non-const pointer to the referring block. Note that we don't
597 : // modify the set property on referrers as we update the block's references.
598 E : const BasicBlockReferrer& referrer = *it;
599 E : Block* referring_block = const_cast<Block*>(referrer.block());
600 :
601 : // We only care about references from other blocks.
602 E : if (referring_block == NULL)
603 E : continue;
604 :
605 E : BlockGraph::Reference old_ref;
606 E : bool found = referring_block->GetReference(referrer.offset(), &old_ref);
607 E : DCHECK(found);
608 E : DCHECK_EQ(BlockGraph::Reference::kMaximumSize, old_ref.size());
609 :
610 : BlockGraph::Reference new_ref(old_ref.type(),
611 : old_ref.size(),
612 : new_block,
613 : old_ref.offset(),
614 E : new_base);
615 :
616 E : bool is_new = referring_block->SetReference(referrer.offset(), new_ref);
617 E : DCHECK(!is_new); // TODO(rogerm): Is this a valid DCHECK?
618 E : }
619 E : }
620 :
621 : // Resolves all of @p object's references (where object is a basic-block,
622 : // or instruction) to point to their final locations in the block graph.
623 : // @param ctx The merge context.
624 : // @param object The referring object.
625 : // @param references The references made from object.
626 : void UpdateReferences(const MergeContext& ctx,
627 : const void* object,
628 E : const BasicBlock::BasicBlockReferenceMap& references) {
629 E : DCHECK(object != NULL);
630 :
631 : // Find the location of the object in the new block_graph.
632 E : Block* block = NULL;
633 E : Offset offset = 0;
634 E : bool found = ctx.locations.Find(object, &block, &offset);
635 E : DCHECK(found);
636 :
637 : // Transfer all of this basic-block's references to the new block.
638 E : BasicBlock::BasicBlockReferenceMap::const_iterator it = references.begin();
639 E : for (; it != references.end(); ++it) {
640 : bool inserted = block->SetReference(offset + it->first,
641 E : ctx.locations.Resolve(it->second));
642 E : DCHECK(inserted);
643 E : }
644 E : }
645 :
646 : // Update all of references in the given basic-block's instructions to
647 : // point to their final locations in the block graph.
648 : // @param ctx The merge context.
649 : // @param basic_block The basic block.
650 : void UpdateInstructionReferences(const MergeContext& ctx,
651 E : const BasicBlock* basic_block) {
652 E : DCHECK(basic_block != NULL);
653 E : DCHECK_EQ(BasicBlock::BASIC_CODE_BLOCK, basic_block->type());
654 E : InstructionConstIter inst_iter = basic_block->instructions().begin();
655 E : for (; inst_iter != basic_block->instructions().end(); ++inst_iter)
656 E : UpdateReferences(ctx, &(*inst_iter), inst_iter->references());
657 E : }
658 :
659 : // Update all of references for the given basic-block's successors to
660 : // point to their final locations in the block graph.
661 : // @param ctx The merge context.
662 : // @param basic_block The basic block.
663 : void UpdateSuccessorReferences(const MergeContext& ctx,
664 E : const BasicBlock* basic_block) {
665 E : DCHECK(basic_block != NULL);
666 E : DCHECK_EQ(BasicBlock::BASIC_CODE_BLOCK, basic_block->type());
667 E : SuccessorConstIter succ_iter = basic_block->successors().begin();
668 E : for (; succ_iter != basic_block->successors().end(); ++succ_iter) {
669 E : Block* block = NULL;
670 E : Offset offset = 0;
671 E : bool found = ctx.locations.Find(&(*succ_iter), &block, &offset);
672 E : if (!found)
673 E : continue; // This successor didn't generate any instructions.
674 :
675 : // Note that for successors, the (block, offset) points directly to
676 : // the location at which the target reference should live (as opposed
677 : // to the start of the instruction sequence).
678 : bool inserted = block->SetReference(
679 E : offset, ctx.locations.Resolve(succ_iter->reference()));
680 E : DCHECK(inserted);
681 E : }
682 E : }
683 :
684 : // A wrapper function to resolve all of the references in the merged subgraph
685 : // to point to their final locations in the block graph.
686 : // @param ctx The merge context.
687 : // @param subgraph The subgraph.
688 : void TransferReferences(const MergeContext& ctx,
689 E : const BasicBlockSubGraph* subgraph) {
690 : // Transfer references to and from the original source block to the
691 : // corresponding new block.
692 E : BlockDescriptionConstIter bd_iter = subgraph->block_descriptions().begin();
693 E : for (; bd_iter != subgraph->block_descriptions().end(); ++bd_iter) {
694 E : const BlockDescription& description = *bd_iter;
695 E : const BasicBlockOrdering& basic_block_order = description.basic_block_order;
696 :
697 : // Skip the block description if it's empty.
698 E : if (basic_block_order.empty())
699 i : continue;
700 :
701 E : BasicBlockOrderingConstIter bb_iter = basic_block_order.begin();
702 E : for (; bb_iter != basic_block_order.end(); ++bb_iter) {
703 E : const BasicBlock* basic_block = *bb_iter;
704 : // All referrers are stored at the basic block level.
705 E : UpdateReferrers(ctx, basic_block);
706 :
707 : // Either this is a basic code block, which stores all of its outbound
708 : // references at the instruction and successor levels, or it's a basic
709 : // data or padding block (which includes unreachable code) and stores
710 : // all of its references at the basic block level.
711 E : if (basic_block->type() == BasicBlock::BASIC_CODE_BLOCK) {
712 E : DCHECK_EQ(0U, basic_block->references().size());
713 E : UpdateInstructionReferences(ctx, basic_block);
714 E : UpdateSuccessorReferences(ctx, basic_block);
715 E : } else {
716 E : UpdateReferences(ctx, basic_block, basic_block->references());
717 : }
718 E : }
719 E : }
720 E : }
721 :
722 : // A clean-up function to remove the original block from which @p subgraph
723 : // is derived (if any) from the block graph. This must only be performed
724 : // after having updated the block graph with the new blocks and transfered
725 : // all references to the new block(s).
726 : // @param subgraph The subgraph.
727 : // @param ctx The merge context.
728 E : void RemoveOriginalBlock(BasicBlockSubGraph* subgraph, MergeContext* ctx) {
729 E : DCHECK(subgraph != NULL);
730 E : DCHECK(ctx != NULL);
731 E : DCHECK_EQ(ctx->original_block, subgraph->original_block());
732 :
733 E : Block* original_block = const_cast<Block*>(ctx->original_block);
734 E : if (original_block == NULL)
735 i : return;
736 :
737 E : DCHECK(!original_block->HasExternalReferrers());
738 :
739 E : bool removed = original_block->RemoveAllReferences();
740 E : DCHECK(removed);
741 :
742 E : removed = ctx->block_graph->RemoveBlock(original_block);
743 E : DCHECK(removed);
744 :
745 E : subgraph->set_original_block(NULL);
746 E : ctx->original_block = NULL;
747 E : }
748 :
749 : } // namespace
750 :
751 E : BlockBuilder::BlockBuilder(BlockGraph* bg) : block_graph_(bg) {
752 E : }
753 :
754 E : bool BlockBuilder::Merge(BasicBlockSubGraph* subgraph) {
755 E : DCHECK(subgraph != NULL);
756 :
757 E : MergeContext context(block_graph_, subgraph->original_block());
758 :
759 E : if (!GenerateBlocks(subgraph, &context))
760 i : return false;
761 :
762 E : TransferReferences(context, subgraph);
763 E : RemoveOriginalBlock(subgraph, &context);
764 :
765 : // Track the newly created blocks.
766 E : new_blocks_.reserve(new_blocks_.size() + context.new_blocks.size());
767 : new_blocks_.insert(
768 E : new_blocks_.end(), context.new_blocks.begin(), context.new_blocks.end());
769 :
770 : // And we're done.
771 E : return true;
772 E : }
773 :
774 : } // namespace pe
|