Avoid rediscovering blocks on each call to FlowGraph::InlineCall.

Avoid rediscovering blocks on each call to FlowGraph::InlineCall.


R=kmillikin@google.com

Committed: https://code.google.com/p/dart/source/detail?r=13922

[zerny-google, 2012-10-12 11:52:05]

Looks like this removed DiscoverBlocks from the top of perf (was at 0.67% when
pref'ing dart2js).

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:766: while (i != new_pred_index) {
I'll rewrite this to a for loop again (still using += step for the increment).

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:782: while (use_idx != new_pred_index) {
I'll rewrite this to a for loop again (still using += step for the increment).

[Kevin Millikin (Google), 2012-10-22 09:10:37]

Good job on getting rid of the block discovery overhead.  Here's my initial
round of comments.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:730: // Helper to reorder predecessors and phis after
splitting a block.  For each
Comment needs some updating---it's no longer called just for blocks that have
been split (e.g., at the call sites where old_block is callee_entry, where the
block callee_entry has actually been merged into caller_entry).

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:735: void
FlowGraph::ReorderPredecessors(BlockEntryInstr* old_block,
I find the naming and emphasis (on reordering) a bit confusing.  It's true that
it reorders even for the degenerate case of successors with one predecessor, but
I'd prefer to focus on the replacing.

It seems better to think of it as, for each successor of old_block, replacing
old_block as a predecessor with new_block.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:738: BranchInstr* branch =
old_block->last_instruction()->AsBranch();
It doesn't make a huge difference, but this code could be more generic.  Instead
of specifically mentioning instructions Branch and Goto, it could just be
structured after SuccessorCount: 0, more than 1, or 1.  Everything else should
still work.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:756: // Find the new predecessor index
It seems like we could do the search and move in the same pass.  Start at old
pred_index, and bubble elements up or down (depending on whether the block ID
has decreased or increased) until we find the sorted position.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:758: intptr_t new_pred_index = -1;
Is it simpler to understand this if you shift the index so it's a usual for loop
(update at the end)?

intptr_t new_pred_index = 0;
for (; new_pred_index < pred_count - 1; ++new_pred_index) {
  if (join->predecessors_[new_pred_index]->block_id() > new_block_id) break;
}

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:772: if ((join->phis() == NULL) || (pred_index ==
new_pred_index)) return;
Can't you can skip the reordering of the predecessors as well, in the case that
pred_index == new_pred_index.  So, move that check earlier.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:861: // The caller block is split and the predecessors
might need reordering.
'the predecessors' is unclear.  "The caller block has been split and the
predecessors of its successors may need to be reordered." or "The caller block
has been split and its successors may need their predecessors reordered."?

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:862: // The caller entry becomes the block of the
callee entry block.
I don't think I understand this comment at all :)  The caller entry block has
been split at the point of the call and so its original successors now have
exit_block as a replacement predecessor; and the callee entry block has been
merged into the (split) caller entry block and so its successors now have
caller_entry as a replacement predecessor.

It should work to reorder the two calls to ReorderPredecessors, which matches
the way I think of the order of effects (the original block has to be split
before the callee_entry can be merged into it).

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:883:
exit_block->set_last_instruction(caller_entry->last_instruction());
It seems like this could also be moved into ReorderPredecessors if the order of
the two calls were swapped.

[zerny-google, 2012-10-22 13:21:30]

Thanks for the review. This CL should address your comments and I have a
question regarding naming of "ReplaceBlock".

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:730: // Helper to reorder predecessors and phis after
splitting a block.  For each
On 2012/10/22 09:10:37, kmillikin wrote:
> Comment needs some updating---it's no longer called just for blocks that have
> been split (e.g., at the call sites where old_block is callee_entry, where the
> block callee_entry has actually been merged into caller_entry).

Done.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:735: void
FlowGraph::ReorderPredecessors(BlockEntryInstr* old_block,
On 2012/10/22 09:10:37, kmillikin wrote:
> I find the naming and emphasis (on reordering) a bit confusing.  It's true
that
> it reorders even for the degenerate case of successors with one predecessor,
but
> I'd prefer to focus on the replacing.
> 
> It seems better to think of it as, for each successor of old_block, replacing
> old_block as a predecessor with new_block.

I renamed it to ReplaceBlock, but that is not entirely accurate either because
old_block may still appear in the graph. The code replaces the block associated
with the exiting/last instruction, so maybe ReplaceBlockOfLastInstruction or
ReplaceLastInstructionBlock?

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:738: BranchInstr* branch =
old_block->last_instruction()->AsBranch();
On 2012/10/22 09:10:37, kmillikin wrote:
> It doesn't make a huge difference, but this code could be more generic. 
Instead
> of specifically mentioning instructions Branch and Goto, it could just be
> structured after SuccessorCount: 0, more than 1, or 1.  Everything else should
> still work.

Done.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:756: // Find the new predecessor index
On 2012/10/22 09:10:37, kmillikin wrote:
> It seems like we could do the search and move in the same pass.  Start at old
> pred_index, and bubble elements up or down (depending on whether the block ID
> has decreased or increased) until we find the sorted position.

Done.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:758: intptr_t new_pred_index = -1;
On 2012/10/22 09:10:37, kmillikin wrote:
> Is it simpler to understand this if you shift the index so it's a usual for
loop
> (update at the end)?
> 
> intptr_t new_pred_index = 0;
> for (; new_pred_index < pred_count - 1; ++new_pred_index) {
>   if (join->predecessors_[new_pred_index]->block_id() > new_block_id) break;
> }

No longer an issue with the new "find predecessor index".

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:772: if ((join->phis() == NULL) || (pred_index ==
new_pred_index)) return;
On 2012/10/22 09:10:37, kmillikin wrote:
> Can't you can skip the reordering of the predecessors as well, in the case
that
> pred_index == new_pred_index.  So, move that check earlier.

No, we still need to write the new_block at the new_index even if
new_index==old_index.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:861: // The caller block is split and the predecessors
might need reordering.
On 2012/10/22 09:10:37, kmillikin wrote:
> 'the predecessors' is unclear.  "The caller block has been split and the
> predecessors of its successors may need to be reordered." or "The caller block
> has been split and its successors may need their predecessors reordered."?

Done.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:862: // The caller entry becomes the block of the
callee entry block.
On 2012/10/22 09:10:37, kmillikin wrote:
> I don't think I understand this comment at all :)  The caller entry block has
> been split at the point of the call and so its original successors now have
> exit_block as a replacement predecessor; and the callee entry block has been
> merged into the (split) caller entry block and so its successors now have
> caller_entry as a replacement predecessor.
> 
> It should work to reorder the two calls to ReorderPredecessors, which matches
> the way I think of the order of effects (the original block has to be split
> before the callee_entry can be merged into it).

Done.

http://codereview.chromium.org/11092102/diff/2001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:883:
exit_block->set_last_instruction(caller_entry->last_instruction());
On 2012/10/22 09:10:37, kmillikin wrote:
> It seems like this could also be moved into ReorderPredecessors if the order
of
> the two calls were swapped.

Done.

[Kevin Millikin (Google), 2012-10-22 14:13:10]

LGTM with the bugfix noted below.

http://codereview.chromium.org/11092102/diff/7001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

http://codereview.chromium.org/11092102/diff/7001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:733: void FlowGraph::ReplaceBlock(BlockEntryInstr*
old_block,
I suggest ReplacePredecessor.  It replaces old_block with new_block as a
predecessor in all (original) successors of old_block.

http://codereview.chromium.org/11092102/diff/7001/runtime/vm/flow_graph.cc#ne...
runtime/vm/flow_graph.cc:767: if (join->predecessors_[new_index +
step]->block_id() > new_id) break;
Split this loop so that the comparison works for both iteration directions.

[srdjan, 2012-10-24 15:10:23]

dbc

https://codereview.chromium.org/11092102/diff/14001/runtime/vm/flow_graph.cc
File runtime/vm/flow_graph.cc (right):

https://codereview.chromium.org/11092102/diff/14001/runtime/vm/flow_graph.cc#...
runtime/vm/flow_graph.cc:751: intptr_t pred_count = join->PredecessorCount();
const intptr_t old_index (and pred_count). The code is easier to understand that
way.

https://codereview.chromium.org/11092102/diff/14001/runtime/vm/flow_graph.cc#...
runtime/vm/flow_graph.cc:755: intptr_t new_id = new_block->block_id();
ditto for newid

https://codereview.chromium.org/11092102/diff/14001/runtime/vm/flow_graph.cc#...
runtime/vm/flow_graph.cc:757: if (old_block->block_id() < new_id) {
Add a comment that you expect the blocks to be sorted by id in the list of
predecessors_ (where are we checking/doing that?)