Support allocation sinking for compound objects.

Support allocation sinking for compound objects.

- Improve escape/alias analysis:
-- Storing an object into a field of another object does not mean that this object escapes (or has aliases) as long as that object does not have any loads from the same place;
-- Places like X.f and Y.f don't alias if X and Y are two different allocation instructions even if X and Y themselves potentially have aliases;
-- Improve precision of alias analysis for indexed properties;

- Support dematerialization and rematerialization of objects that are referenced by other dematerialized objects.
-- Use fix-point algorithm to collect candidates for allocation sinking;
-- Support aborting unsuccessful allocation sinking.

R=fschneider@google.com, johnmccutchan@google.com

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

[Vyacheslav Egorov (Google), 2014-07-16 12:24:02]

PTAL

[Florian Schneider, 2014-07-16 15:02:03]

LGTM with test coverage added with objects pointing to each other (A->B->C,
A->B->A, A->B->C->A)

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:5688: // Separating allocation results from
other objects is improves precision of the
Something is missing in this comment.

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:6544: // Set of ids of places that can be
affected by side-effects other then
s/then/than/

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:10175: //
ASSERT(materializations_[i]->input_use_list() == NULL);
Remove obsolete ASSERT?

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:10219: // Given the deoptimization exit find
firt materialization that was inserted
s/firt/first/

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:10220: // at it.
s/at/before/ ?

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/hash_map.h
File runtime/vm/hash_map.h (right):

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/hash_map.h#ne...
runtime/vm/hash_map.h:29: intptr_t size() const { return count_; }
this seems unused?

[Vyacheslav Egorov (Google), 2014-07-17 17:03:48]

PTAL

I addressed comments and added more tests.

John & Srdjan, could you take a look as Florian is on vacation now.

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:5688: // Separating allocation results from
other objects is improves precision of the
On 2014/07/16 15:02:03, Florian Schneider wrote:
> Something is missing in this comment.

Done.

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:10175: //
ASSERT(materializations_[i]->input_use_list() == NULL);
On 2014/07/16 15:02:03, Florian Schneider wrote:
> Remove obsolete ASSERT?

Done.

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:10219: // Given the deoptimization exit find
firt materialization that was inserted
On 2014/07/16 15:02:02, Florian Schneider wrote:
> s/firt/first/

Done.

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:10220: // at it.
On 2014/07/16 15:02:02, Florian Schneider wrote:
> s/at/before/ ?

Done.

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/hash_map.h
File runtime/vm/hash_map.h (right):

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/hash_map.h#ne...
runtime/vm/hash_map.h:29: intptr_t size() const { return count_; }
On 2014/07/16 15:02:03, Florian Schneider wrote:
> this seems unused?

Done.

[srdjan, 2014-07-17 23:08:15]

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/compiler.cc#n...
runtime/vm/compiler.cc:483: optimizer.Canonicalize();
Why another canonicalization?

https://codereview.chromium.org/395943003/diff/40001/runtime/vm/deferred_obje...
File runtime/vm/deferred_objects.h (right):

https://codereview.chromium.org/395943003/diff/40001/runtime/vm/deferred_obje...
runtime/vm/deferred_objects.h:175: // Allocate the object but keep it's fields
null-initialized. Actual field
s/it's/its/

https://codereview.chromium.org/395943003/diff/40001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/395943003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.h:1766: class AliasIdentity {
: public ValueObject ?

https://codereview.chromium.org/395943003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.h:1804: intptr_t value_;
const

[Vyacheslav Egorov (Google), 2014-07-18 11:25:08]

Addressed Srdjan's comments.

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/compiler.cc
File runtime/vm/compiler.cc (right):

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/compiler.cc#n...
runtime/vm/compiler.cc:483: optimizer.Canonicalize();
On 2014/07/17 23:08:14, srdjan wrote:
> Why another canonicalization?

When writing tests I noticed that we often arrive to the following IR right
before allocation sinking:

v1 <- AllocateObject(...)
...
CheckClass(v1, ...)

I run one more canonicalization to remove this CheckClass instruction.

Ideally our Canonicalize just needs to run every time we rewire uses, otherwise
we constantly miss optimization opportunities.

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/395943003/diff/20001/runtime/vm/flow_graph_op...
runtime/vm/flow_graph_optimizer.cc:6544: // Set of ids of places that can be
affected by side-effects other then
On 2014/07/16 15:02:03, Florian Schneider wrote:
> s/then/than/

Done.

https://codereview.chromium.org/395943003/diff/40001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/395943003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.h:1766: class AliasIdentity {
On 2014/07/17 23:08:15, srdjan wrote:
> : public ValueObject ?

Done.

https://codereview.chromium.org/395943003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.h:1804: intptr_t value_;
On 2014/07/17 23:08:15, srdjan wrote:
> const

It can't be const because we have fields of this type that we change once it is
computed (see SetIdentity).

[Vyacheslav Egorov (Google), 2014-07-18 13:21:47]

I also improved tests/language/vm/load_to_load_forwarding_vm_test.dart by
generating test cases automatically to have it cover interesting combinations.

[Cutch, 2014-07-18 18:10:33]

lgtm

[Vyacheslav Egorov (Google), 2014-07-18 18:35:24]

Committed patchset #5 manually as r38404 (presubmit successful).