Compute local variable liveness before translation to SSA.

Compute local variable liveness before translation to SSA.

Use it to remove dead values from deoptimization environments.

R=kmillikin@google.com
BUG=

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

[Vyacheslav Egorov (Google), 2013-03-21 22:48:27]

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4438: jump->SetEnvironment(branch->env());
This change revealed serious flaw in the way we restructure graph that slipped
past reviews before. 

We when we insert goto's into the graph we forget to attach the environment to
them... But we *must* do that goto can become a deoptimization target.

It is very fragile part of the system. Fix in this place extinguished immediate
fire but we need to review all places where we generate gotos and branches and
ensure that they get proper environment.

[Kevin Millikin (Google), 2013-03-22 11:57:52]

LGTM.

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

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph.cc#newc...
runtime/vm/flow_graph.cc:318: kill->Intersect(GetLiveOutSet(block));
It seems to me that you could either use a fresh bitvector for each element of
assigned_vars_ and not mutate kill_, or else mutate kill_ and then just return
it.

There doesn't seem much point to doing it this way, though.

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph.cc#newc...
runtime/vm/flow_graph.cc:675: (current->IsBranch() &&
This still seems kind of fiddly.

Could we just make every control instruction that has successors have a deopt
environment?

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph.h
File runtime/vm/flow_graph.h (right):

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph.h#newco...
runtime/vm/flow_graph.h:262: // Live-out sets for each block.  They contain
indices of SSA values
This comment and the ones below should not mention SSA values.  Just say
"indexes of variables".

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph_optimiz...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4438: jump->SetEnvironment(branch->env());
I wouldn't say it's a flaw in the way we restructure the graph, but a flaw in
the way we record deoptimization environments.

Off the top of my head, there are two more occurrences in this file just below
for branch propagation, and occurrences also for inlining exits.

As we try to do more complicated things with changing the graph structure, this
will get harder and harder.

[Vyacheslav Egorov (Google), 2013-03-22 12:16:15]

Thanks!

Landing.

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

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph.cc#newc...
runtime/vm/flow_graph.cc:318: kill->Intersect(GetLiveOutSet(block));
On 2013/03/22 11:57:52, kmillikin wrote:
> It seems to me that you could either use a fresh bitvector for each element of
> assigned_vars_ and not mutate kill_, or else mutate kill_ and then just return
> it.
> 
> There doesn't seem much point to doing it this way, though.

kill_ is in postorder while assigned_vars_ are in preorder. I will add a comment
about that.

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph.cc#newc...
runtime/vm/flow_graph.cc:675: (current->IsBranch() &&
On 2013/03/22 11:57:52, kmillikin wrote:
> This still seems kind of fiddly.
> 
> Could we just make every control instruction that has successors have a deopt
> environment?

Discussed offline. Will postpone it to another change.

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph.h
File runtime/vm/flow_graph.h (right):

https://codereview.chromium.org/12638040/diff/1/runtime/vm/flow_graph.h#newco...
runtime/vm/flow_graph.h:262: // Live-out sets for each block.  They contain
indices of SSA values
On 2013/03/22 11:57:52, kmillikin wrote:
> This comment and the ones below should not mention SSA values.  Just say
> "indexes of variables".

Done.

[Vyacheslav Egorov (Google), 2013-03-22 12:33:59]

Committed patchset #2 manually as r20377 (presubmit successful).