Refactor load forwarding pass to use a Place abstraction.

Refactor load forwarding pass to use a Place abstraction.

Place describes a location that code can load from or store to.

Start forwarding loads through phis.

Previously load forwarding operated directly on load instructions which complicated certain things e.g. implementation of a hash map had to allow looking up a load instruction by store instruction, forwarding through phis might have required introducing synthetic load instructions to be put into the map.

R=kmillikin@google.com

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

[Kevin Millikin (Google), 2013-06-25 09:18:29]

This is complicated, but it seems right.  LGTM.

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

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:36: DEFINE_FLAG(bool,
trace_load_optimization_verbose, false,
I don't think I want 'verbose' in the name if there is no corresponding
non-verbose flag.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3667: field_(other.field_),
Eeek.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3674: : kind_(kNone), instance_(0),
field_(0), id_(0) {
..., instance_(NULL), field_(NULL), ...

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3695: field_ =
&store_instance_field->field();
This creeps me out.  Isn't it simpler to make the field_ member const Field&?

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3814: return (kind() == Place::kField) &&
field().is_final();
No need for Place:: here.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3870: // Set mapping alias to a list of
places sharing this alias. Additionally
First sentence confusing?  "A map from aliases to a set of places sharing the
alias."

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3878: // BitVector constructor throws if
requested length is 0.
I don't think it does any more, so this can be simplified.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4247: for (intptr_t i = 0; i <
places->length(); i++) {
This needs a bit of comment, especially since it's adding to places while
iterating over it.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4262: if (input->IsPhi()) {
Why only phis?

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4303: if (result != NULL) {
Specifically, it's not clear if these are exactly the phi inputs that were found
in the loop above or if it includes other (non-phi) inputs.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4745: // All blocks were visited. Fuly
Fuly?

https://codereview.chromium.org/17101028/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/17101028/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:943: for (intptr_t from_index = 0;
from_index < phis_->length(); ++from_index) {
Is this better than searching for the phi and replacing it with the last
element, unless it is the last element?

[Florian Schneider, 2013-06-25 09:19:23]

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

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3660: kContext
It would be more natural to have the context just as a normal SSA value. This is
not in the scope of this change, but here it shows how having a dedicated
register for the context makes things more complicated.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3974: class LoadPair {
Could be made a struct with public members from, to.

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

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.h:45: void UnboxPhis();
Unused declaration?

[Vyacheslav Egorov (Google), 2013-06-25 18:02:38]

Thank you for the review. 

Comments addressed, landing.

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

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:36: DEFINE_FLAG(bool,
trace_load_optimization_verbose, false,
On 2013/06/25 09:18:29, kmillikin wrote:
> I don't think I want 'verbose' in the name if there is no corresponding
> non-verbose flag.

Done.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3660: kContext
On 2013/06/25 09:19:24, Florian Schneider wrote:
> It would be more natural to have the context just as a normal SSA value. This
is
> not in the scope of this change, but here it shows how having a dedicated
> register for the context makes things more complicated.

Completely agreed. I began tracking context as a part of load forwarding only
because we did not optimize it in any other way.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3667: field_(other.field_),
On 2013/06/25 09:18:29, kmillikin wrote:
> Eeek.

Added a field called raw_selector_ and started copying that instead to make this
code look a bit more beautiful.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3674: : kind_(kNone), instance_(0),
field_(0), id_(0) {
On 2013/06/25 09:18:29, kmillikin wrote:
> ..., instance_(NULL), field_(NULL), ...

Done.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3695: field_ =
&store_instance_field->field();
On 2013/06/25 09:18:29, kmillikin wrote:
> This creeps me out.  Isn't it simpler to make the field_ member const Field&?

Unions can't have members of reference type.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3814: return (kind() == Place::kField) &&
field().is_final();
On 2013/06/25 09:18:29, kmillikin wrote:
> No need for Place:: here.

Done.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3870: // Set mapping alias to a list of
places sharing this alias. Additionally
On 2013/06/25 09:18:29, kmillikin wrote:
> First sentence confusing?  "A map from aliases to a set of places sharing the
> alias."

Done.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3878: // BitVector constructor throws if
requested length is 0.
On 2013/06/25 09:18:29, kmillikin wrote:
> I don't think it does any more, so this can be simplified.

Done.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3974: class LoadPair {
On 2013/06/25 09:19:24, Florian Schneider wrote:
> Could be made a struct with public members from, to.

I prefer a class.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4247: for (intptr_t i = 0; i <
places->length(); i++) {
On 2013/06/25 09:18:29, kmillikin wrote:
> This needs a bit of comment, especially since it's adding to places while
> iterating over it.

Done.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4262: if (input->IsPhi()) {
On 2013/06/25 09:18:29, kmillikin wrote:
> Why only phis?

The reasoning was: if place was not numbered due to an existing load and store
instruction then numbering it as phi input will give no information, phis are
different: they can have arguments that carry place information.

In some sense it was an optimization. I removed it to simplify the code.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4303: if (result != NULL) {
On 2013/06/25 09:18:29, kmillikin wrote:
> Specifically, it's not clear if these are exactly the phi inputs that were
found
> in the loop above or if it includes other (non-phi) inputs.

I merged phi related parts of these two loops together and moved them to
separate function for easier understanding.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:4745: // All blocks were visited. Fuly
On 2013/06/25 09:18:29, kmillikin wrote:
> Fuly?

Done.

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

https://codereview.chromium.org/17101028/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.h:45: void UnboxPhis();
On 2013/06/25 09:19:24, Florian Schneider wrote:
> Unused declaration?

Done.

https://codereview.chromium.org/17101028/diff/1/runtime/vm/intermediate_langu...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/17101028/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:943: for (intptr_t from_index = 0;
from_index < phis_->length(); ++from_index) {
On 2013/06/25 09:18:29, kmillikin wrote:
> Is this better than searching for the phi and replacing it with the last
> element, unless it is the last element?

Done.

[Vyacheslav Egorov (Google), 2013-06-25 18:50:36]

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