Introduce Goto instructions to the flow graph.

Introduce Goto instructions to the flow graph.

Goto is a control instruction with a single successor.

Before: basic blocks ended with an exit (return, throw, or rethrow), a
branch to a pair of target entries, or else they fell through to the
next block entry.

Now: basic blocks end with an exit, a branch, or an explicit goto to a
join entry.

R=vegorov@google.com,srdjan@google.com
BUG=
TEST=

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

[Kevin Millikin (Google), 2012-07-12 11:51:28]

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_builder.cc:991: TargetEntryInstr** previous_false_address
= NULL;
I refactored this code to wire up the case comparisons as soon as they became
available.

[srdjan, 2012-07-12 16:42:26]

LGTM

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_builder.h (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_builder.h:126: // open.
Adapt comment to changed AddInstruction.

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_builder.h:130: void Goto(JoinEntryInstr* join);
IMO, s/Goto/AppendGotoTo/ makes it more reable at call site

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_compiler.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_compiler.cc:157: return (current_index <
block_order().length() - 1) &&
Add parenthesis

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/il_print...
File runtime/vm/il_printer.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/il_print...
runtime/vm/il_printer.cc:382: (ssa_temp_index() != -1) ? ssa_temp_index() :
temp_index(),
Maybe introduce HasSSATemp(), since there are many places where we check.

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
File runtime/vm/intermediate_language.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.cc:607: void Instruction::Goto(JoinEntryInstr*
entry) {
IMO, renaming it to AppendGoto will make the call sites more readable.
Can a Goto be appended to any instruction, i..e, do you need asserts to restrict
appending?

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.cc:1032:
compiler->frame_register_allocator()->Spill();
It looks strange to do spilling inside EmitNativeCode. Shouldn't this be handled
by register allocator?

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
File runtime/vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.h:1766: // TODO(fschneider): Also add Throw and
ReThrow to the list of instructions
parenthesis

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.h:2292: class GotoInstr : public
InstructionWithInputs {
Why is a goto InstructionWithInputs and not just Instruction? Please add
comment.

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.h:2308: JoinEntryInstr* successor_;
DISALLOW_...

[Vyacheslav Egorov (Google), 2012-07-13 14:41:42]

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
File runtime/vm/intermediate_language.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.cc:1032:
compiler->frame_register_allocator()->Spill();
On 2012/07/12 16:42:26, srdjan wrote:
> It looks strange to do spilling inside EmitNativeCode. Shouldn't this be
handled
> by register allocator?

I agree with Srdjan. This way we have discrepancy between the way we handle
Branch (in the register allocator) and Goto (here).

[Kevin Millikin (Google), 2012-07-13 15:34:59]

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
File runtime/vm/flow_graph_builder.h (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/flow_gra...
runtime/vm/flow_graph_builder.h:130: void Goto(JoinEntryInstr* join);
On 2012/07/12 16:42:26, srdjan wrote:
> IMO, s/Goto/AppendGotoTo/ makes it more reable at call site

I see your point.  Goto is what happens at runtime, not an effect on the graph.

On the other hand, "AppendGotoTo" is ambiguous (is is a goto to the join, or is
it appended to the join?).  And we're doing a bit more than just adding a single
instruction.

So I'm happy to have it changed to a better name, but I've left it as "Goto" for
now.

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/il_print...
File runtime/vm/il_printer.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/il_print...
runtime/vm/il_printer.cc:382: (ssa_temp_index() != -1) ? ssa_temp_index() :
temp_index(),
On 2012/07/12 16:42:26, srdjan wrote:
> Maybe introduce HasSSATemp(), since there are many places where we check.

Hmm.  There are a few places where we use it to tell whether we've done the SSA
translation or not, and a few places where we use it to tell if a value has uses
after the translation.

Testing for the index seems indirect in both cases, even with a predicate for
it.

I'll probably make a separate change to clean it up.  I prefer calling it a
'virtual register index' anyway.

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
File runtime/vm/intermediate_language.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.cc:607: void Instruction::Goto(JoinEntryInstr*
entry) {
On 2012/07/12 16:42:26, srdjan wrote:
> IMO, renaming it to AppendGoto will make the call sites more readable.
> Can a Goto be appended to any instruction, i..e, do you need asserts to
restrict
> appending?

It's kind of messy right now.  There are asserts in set_next that cover the
disallowed cases.

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.cc:1032:
compiler->frame_register_allocator()->Spill();
On 2012/07/12 16:42:26, srdjan wrote:
> It looks strange to do spilling inside EmitNativeCode. Shouldn't this be
handled
> by register allocator?

I think so.  Right now, it's hardcoded into the compiler.  I just moved this
from the driver loop to the native code for Goto (since we didn't have goto
before).

Leaving it in the driver loop requires an explicit check for IsGoto(), which
seems like it should get rolled into one of the virtual functions on the
instruction.

It seems redundant to me anyway, since we also spill at basic block entries. 
I'll sort that out in another change.

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
File runtime/vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.h:2292: class GotoInstr : public
InstructionWithInputs {
On 2012/07/12 16:42:26, srdjan wrote:
> Why is a goto InstructionWithInputs and not just Instruction? Please add
> comment.

Well, it's an instruction with inputs that happens to have zero of them :)

InstructionWithInputs seems like the wrong name or else the wrong abstraction. 
There's a handful of virtual functions related to the register allocator and
code generator (already, and there will probably become more) that assume that
they will only be called on InstructionWithInputs.  

*Avoiding* to call them requires checking the instruction type in the driver
loop (with a virtual method) rather than just making the virtual method safe to
call in the first place.

I'll add a comment, but it still needs more some cleanup.

[Kevin Millikin (Google), 2012-07-13 15:41:32]

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
File runtime/vm/intermediate_language.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.cc:1032:
compiler->frame_register_allocator()->Spill();
On 2012/07/13 14:41:42, Vyacheslav Egorov (Google) wrote:
> On 2012/07/12 16:42:26, srdjan wrote:
> > It looks strange to do spilling inside EmitNativeCode. Shouldn't this be
> handled
> > by register allocator?
> 
> I agree with Srdjan. This way we have discrepancy between the way we handle
> Branch (in the register allocator) and Goto (here).

I agree with you both that this is fishy.  It was already that way and I just
moved it around.

It was previously hardcoded in the compiler's VisitBlocks loop, at the end of
every basic block that ended with Goto just before the (hardcoded) jmp.

I can move it back there, or leave it here.

[srdjan, 2012-07-13 23:18:33]

Still LGTM once the allocation/spilling at Goto has been agreed upon.

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
File runtime/vm/intermediate_language.cc (right):

https://chromiumcodereview.appspot.com/10735071/diff/4001/runtime/vm/intermed...
runtime/vm/intermediate_language.cc:1032:
compiler->frame_register_allocator()->Spill();
On 2012/07/13 15:41:32, kmillikin wrote:
> On 2012/07/13 14:41:42, Vyacheslav Egorov (Google) wrote:
> > On 2012/07/12 16:42:26, srdjan wrote:
> > > It looks strange to do spilling inside EmitNativeCode. Shouldn't this be
> > handled
> > > by register allocator?
> > 
> > I agree with Srdjan. This way we have discrepancy between the way we handle
> > Branch (in the register allocator) and Goto (here).
> 
> I agree with you both that this is fishy.  It was already that way and I just
> moved it around.
> 
> It was previously hardcoded in the compiler's VisitBlocks loop, at the end of
> every basic block that ended with Goto just before the (hardcoded) jmp.
> 
> I can move it back there, or leave it here.

I am fine with a solution that you and Slava agree with.

[Kevin Millikin (Google), 2012-07-16 12:34:32]

Comments incorporated.  Slava, I had to change the live range computation in
flow_graph_allocator.cc to account for Goto.  The instruction indices are a bit
subtle, could you take a quick look?

[Vyacheslav Egorov (Google), 2012-07-16 12:42:55]

http://codereview.chromium.org/10735071/diff/15001/runtime/vm/flow_graph_allo...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10735071/diff/15001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:394: GotoInstr* goto_instr =
current->AsGoto();
I suggest you just don't give goto a position in NumberInstructions.

http://codereview.chromium.org/10735071/diff/15001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:436: pos -= 3;  // The beginning of the
previous instruction.
I don't get where -3 comes from. we now have -6 in total here. which is 3
instructions in total, but it's only goto an last instruction, so it should be
-4 tops. (ParallelMove should have no position, and I suggest goto should have
none as well, then pos should be just -2).

http://codereview.chromium.org/10735071/diff/15001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:604: ASSERT(!previous->IsParallelMove());  //
Why??
ParallelMove should be created only once. (verification of an edge split form:
join can't have a predecessor with multiple-successors).

[Kevin Millikin (Google), 2012-07-16 13:47:48]

I've uploaded an attempt to fix the instruction numbering and make it agree in
both places.

http://codereview.chromium.org/10735071/diff/15001/runtime/vm/flow_graph_allo...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10735071/diff/15001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:436: pos -= 3;  // The beginning of the
previous instruction.
On 2012/07/16 12:42:55, Vyacheslav Egorov (Google) wrote:
> I don't get where -3 comes from. we now have -6 in total here. which is 3
> instructions in total, but it's only goto an last instruction, so it should be
> -4 tops. (ParallelMove should have no position, and I suggest goto should have
> none as well, then pos should be just -2).

I was counting both the goto and the parallel move.

I missed the way that NumberInstructions assigned numbers to some but not all
instructions.  Obviously this this code that recreates the instruction numbers
needs to account for that.

I'll change it to not number those two classes of instructions, but I think that
makes the situation worse, not better.  I would say we should either (1) just
read the number off the instruction and not try to recompute the same number
here or (2) make the numbering completely uniform for all instructions even if
it leaks integers.

http://codereview.chromium.org/10735071/diff/15001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:604: ASSERT(!previous->IsParallelMove());  //
Why??
On 2012/07/16 12:42:55, Vyacheslav Egorov (Google) wrote:
> ParallelMove should be created only once. (verification of an edge split form:
> join can't have a predecessor with multiple-successors).

It seems like an indirect way to assert that.  It would probably be nicer to
just make it impossible (i.e., have a dedicated parallel move for phi resolution
that lies outside the instruction stream and so always at the end of the block).

It's already impossible to have the violation, because the only instructions
with multiple successors are GraphEntry and Branch, and those successors have
type TargetEntryInstr*.

[Kevin Millikin (Google), 2012-07-16 13:49:17]

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:586: // We do not assign an instruction
number to the block entry.
Ooops, this comment described the situation before.  I've changed it to be
numbered with the block's start position so I'll scrap the comment.

[Vyacheslav Egorov (Google), 2012-07-16 14:16:41]

positions LGTM

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:575: // for phi resolution.
there is a comment in the header file. you can copy it to here

[srdjan, 2012-07-16 16:50:44]

some comments

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:397: // If we have a parallel move here then
the successor block must be a
must start with a join with phis

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:442: current = current->previous();
According to the comment this should this be 'current =
parallel_move->previous()'  and inside 'if (parallel_move ! = NULL)', no?

[Kevin Millikin (Google), 2012-07-18 09:47:11]

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
File runtime/vm/flow_graph_allocator.cc (right):

http://codereview.chromium.org/10735071/diff/19001/runtime/vm/flow_graph_allo...
runtime/vm/flow_graph_allocator.cc:442: current = current->previous();
On 2012/07/16 16:50:45, srdjan wrote:
> According to the comment this should this be 'current =
> parallel_move->previous()'  and inside 'if (parallel_move ! = NULL)', no?

Yes.  It's hard to see on the codereview tool, but this is inside parallel_move
!= NULL already and in that case parallel_move == current->AsParallelMove().