Second step for computing SSA: renaming.

Second step for computing SSA: renaming.

This CL adds the renaming step to the SSA construction. The renaming pass
initializes a start environment with the initial values of all locals (#null)
 and parameters and removes LoadLocal and StoreLocal instructions from the
 graph.

Right now the renaming does not support functions with parameters yet.
I added a TODO for this. The SSA form for a simple function with an if-statement:

function foo() {
  var v = 0;
  var x;
  if (v == 0) {
    x = 42;
  }
  return x;
}

looks as follows:

 0: [graph]
  #null
  #null
 1: [target]
    t0 <- #0
    t1 <- #null
    t2 <- #0
    t3 <- EqualityCompare(t0 == t2)
    Branch if t3 goto (2, 3)
 2: [target]
    t5 <- #42 goto 4
 3: [target] goto 4
 4: [join]
    t4 <- phi(t1,t5)
    Return t4
Committed: https://code.google.com/p/dart/source/detail?r=8839

[srdjan, 2012-06-18 18:04:38]

LGTM with comments

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder.cc
File vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2561: // TODO(fschneider): Support paramters. All
parameters are initially located
parameters

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2572: ASSERT(var_count ==
parsed_function().stack_local_count());
Why don't you use stack_local_count instead of passing in var_count? If it is
temporary to check sanity, please add a TODO to remove var_count.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2579: ASSERT(normal_entry != NULL);  // Graph entry is
empty.
Maybe change comment to: "Must have entry" or similar.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2603: if (join->phis() != NULL) {
ASSERT(join->phis() != NULL) ?

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2617: while (current != NULL &&
!current->IsBlockEntry()) {
add parenthesis

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2622: load =
current->AsDo()->computation()->AsLoadLocal();
A LoadLocal in a Do has no side effect and can be thrown (optimized) away. Why
not get rid of it?

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2636: if (load != NULL || store != NULL) {
Add parenthesis

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2653: // from the enviroment.
environment

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2684: if (load == NULL && store == NULL) {
parenthesis

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2701: if
(block_entry->last_instruction()->SuccessorCount() == 1 &&
ditto

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder.h
File vm/flow_graph_builder.h (right):

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.h:58: intptr_t var_count);
SHould we move all the SSA building methods and fields into a separate class,
thus stressing the fact that basic IR construction is the same for optimizing
and unoptimizing compiler?

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/intermediate_langua...
File vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1669: void InsertPhi(intptr_t variable_index) { }
Remove?

[Florian Schneider, 2012-06-19 11:26:39]

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder.cc
File vm/flow_graph_builder.cc (right):

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2561: // TODO(fschneider): Support paramters. All
parameters are initially located
On 2012/06/18 18:04:38, srdjan wrote:
> parameters

Done.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2572: ASSERT(var_count ==
parsed_function().stack_local_count());
On 2012/06/18 18:04:38, srdjan wrote:
> Why don't you use stack_local_count instead of passing in var_count? If it is
> temporary to check sanity, please add a TODO to remove var_count.

Yes, in one of the next CLs it will change to:

var_count = local + fixed_params + copied_params

Maybe we should store this value in the builder class instead of passing it
around in all functions?

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2579: ASSERT(normal_entry != NULL);  // Graph entry is
empty.
On 2012/06/18 18:04:38, srdjan wrote:
> Maybe change comment to: "Must have entry" or similar.

Done.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2603: if (join->phis() != NULL) {
On 2012/06/18 18:04:38, srdjan wrote:
> ASSERT(join->phis() != NULL) ? 

Right now I lazily allocate the phis() array when there are phis present: The
non-optimizing compiler will never add any phi-instructions, so the JoinEntry
would always have an empty GrowableArray in this case.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2617: while (current != NULL &&
!current->IsBlockEntry()) {
On 2012/06/18 18:04:38, srdjan wrote:
> add parenthesis

Done.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2622: load =
current->AsDo()->computation()->AsLoadLocal();
On 2012/06/18 18:04:38, srdjan wrote:
> A LoadLocal in a Do has no side effect and can be thrown (optimized) away. Why
> not get rid of it?

Yes. I remove it from the graph below, but better if we already not generate
such a LoadLocal in the first place. I'll add an ASSERT instead.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2636: if (load != NULL || store != NULL) {
On 2012/06/18 18:04:38, srdjan wrote:
> Add parenthesis

Done.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2653: // from the enviroment.
On 2012/06/18 18:04:38, srdjan wrote:
> environment

Done.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2684: if (load == NULL && store == NULL) {
On 2012/06/18 18:04:38, srdjan wrote:
> parenthesis

Done.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.cc:2701: if
(block_entry->last_instruction()->SuccessorCount() == 1 &&
On 2012/06/18 18:04:38, srdjan wrote:
> ditto

Done.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder.h
File vm/flow_graph_builder.h (right):

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/flow_graph_builder....
vm/flow_graph_builder.h:58: intptr_t var_count);
On 2012/06/18 18:04:38, srdjan wrote:
> SHould we move all the SSA building methods and fields into a separate class,
> thus stressing the fact that basic IR construction is the same for optimizing
> and unoptimizing compiler?

Yes, I think that would be good. I'll do it as a separate code-moving-only CL.

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/intermediate_langua...
File vm/intermediate_language.h (right):

https://chromiumcodereview.appspot.com/10544206/diff/1/vm/intermediate_langua...
vm/intermediate_language.h:1669: void InsertPhi(intptr_t variable_index) { }
On 2012/06/18 18:04:38, srdjan wrote:
> Remove?

Oops. Accidental edit.