Make IL instructions a doubly-linked list within basic blocks.

Make IL instructions a doubly-linked list within basic blocks.

In order to be able to efficiently iterate backwards over instructions
and removing or replacing instructions in the graph we want them to
be a double-linked list inside basic blocks. The list has the following

1. Block entry instructions do not have a previous instruction.
2. The last instruction in a block may or may not have a next instruction:
   - Branches have a NULL-successor.
   - Normal block exits have a block entry instructions as successor.

This CL also makes the accessor for previous and next instruction in this
list non-virtual. This avoidis the current code duplication there.
Committed: https://code.google.com/p/dart/source/detail?r=9297

[srdjan, 2012-06-25 15:57:16]

LGTM

I am worried about inconsistent state when removing instructions and would like
as many safeguard as possible. Please also add a check in UseVal::definition(),
making sure that nobody accesses a removed instruction via UseVal (assert that
Definition was not removed before returning it).

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/flow_graph_build...
File vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/flow_graph_build...
vm/flow_graph_builder.cc:83: }
I like it a lot that we factor out the knowledge of how the IL nodes are
connected.

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
File vm/intermediate_language.cc (right):

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.cc:534: void Instruction::SetSuccessor(Instruction*
instr) {
The two methods are (at least now) very simple setter and could be renamed to
set_successor, set_previous and moved into  header file. Or are there plans to
make them more complex?

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.cc:558: if (next != NULL && !next->IsBlockEntry()) {
Add parenthesis. Quick question: when is it possible to remove the last
instruction (next == NULL)? I.e., should (next != NULL) be an assert or is it
possible?

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.cc:560: }
Set successor and previous of this instruction to NULL

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
File vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.h:1763: Instruction* StraightLineSuccessor() const {
return successor_; }
Since it is a very simple setter now, maybe rename it to successor?

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.h:1766: Instruction* Previous() const { return
previous_; }
s/Previous/previous/

[Vyacheslav Egorov (Google), 2012-06-25 16:02:44]

lgtm with Srdjan's comments addressed.

[Florian Schneider, 2012-07-02 09:20:42]

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
File vm/intermediate_language.cc (right):

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.cc:534: void Instruction::SetSuccessor(Instruction*
instr) {
On 2012/06/25 15:57:16, srdjan wrote:
> The two methods are (at least now) very simple setter and could be renamed to
> set_successor, set_previous and moved into  header file. Or are there plans to
> make them more complex?

Done.

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.cc:558: if (next != NULL && !next->IsBlockEntry()) {
On 2012/06/25 15:57:16, srdjan wrote:
> Add parenthesis. Quick question: when is it possible to remove the last
> instruction (next == NULL)? I.e., should (next != NULL) be an assert or is it
> possible?


It can happen. But this just made me realize that we need to do more here:

The last instruction currently acts as an implicit Goto-instruction. So we need
to update the last_instruction of the block_entry if we want to remove it.

This would mean I need to find the entry corresponding to the current block from
every instruction. Maybe it would be nicer to have an explicit Goto-instruction
instead?

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.cc:560: }
On 2012/06/25 15:57:16, srdjan wrote:
> Set successor and previous of this instruction to NULL

Done.

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
File vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.h:1763: Instruction* StraightLineSuccessor() const {
return successor_; }
On 2012/06/25 15:57:16, srdjan wrote:
> Since it is a very simple setter now, maybe rename it to successor?

Done.

https://chromiumcodereview.appspot.com/10665022/diff/4001/vm/intermediate_lan...
vm/intermediate_language.h:1766: Instruction* Previous() const { return
previous_; }
On 2012/06/25 15:57:16, srdjan wrote:
> s/Previous/previous/

Done.