Track side-effect free paths in the graph to allow CSE and LICM for instructions that depend on som…

Track side-effect free paths in the graph to allow CSE and LICM for instructions that depend on some side-effects.

Right now only a single side-effect is important for CSE/LICM purposes: externalization.

But abstractions are in place to introduce others if needed.

R=fschneider@google.com

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

[Vyacheslav Egorov (Google), 2013-04-26 23:25:58]

notice that loads from non-immutable locations are fully excluded from CSE/LICM
and thus stores are marked as having no side-effect.

CSE for loads is fully handled by LoadOptimizer at this point which uses its own
abstraction to track dependencies (Alias/AliasedSet).

[Vyacheslav Egorov (Google), 2013-04-29 08:21:08]

moving to Florian for review.

[Florian Schneider, 2013-04-29 12:11:54]

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/flow_graph.h#newco...
runtime/vm/flow_graph.h:301: // path between these blocks.
This definition is not precise about what the code actually computes:

Assuming no side effects in blocks A, B, C, D and a diamond-shaped graph A->B,
A->C, B->D, C->D

in(A) = {},  out(A) = {A}
in(B) = {A}, out(B) = {A,B}
in(C) = {A}, out(C) = {A,C}
in(D) = {A}, out(D) = {A,D}

There is a path without side effects from B to D, but B is not in in(D) because
{A,B} intersect {A,C} is just {A}.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/flow_graph.h#newco...
runtime/vm/flow_graph.h:302: GrowableArray<BitVector*> live_in_;
Maybe choose a better name for in/out. live_in is already used for live
variables. e.g. freepath_in, freepath_out

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:111: return externalizable ?
EffectSet::All() : EffectSet::None();
Shouldn't the dependencies be EffectSet::kExternalizable?

Right now, there is no difference because it is equals to All().

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:747: // Returns true if the instruction may
have side effects.
Returns set of effects created by this instruction.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2893: 
Extra \n?

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2934: UNREACHABLE();
Maybe add a comment: // Never used in optimizing compiler.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2973: UNREACHABLE();
Maybe add a comment: // Never used in optimizing compiler.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:3052: virtual EffectSet Effects() const {
return EffectSet::None(); }
Add a comment why stores are excluded from side effects here.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:3148: virtual EffectSet Effects() const {
return EffectSet::None(); }
Add a comment why stores are excluded from side effects here.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:3675: virtual EffectSet Effects() const {
return EffectSet::All(); }
It seems this could be ::None() as well.

[srdjan, 2013-04-29 17:16:26]

DBC

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3951: class CSEInstructionMap {
: public ValueObject

https://codereview.chromium.org/14021016/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3960: CSEInstructionMap(const
CSEInstructionMap& other)
explicit

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:110:
unary_checks().HasReceiverClassId(kTwoByteStringCid);
Need to add all typed data arrays as well.

[Vyacheslav Egorov (Google), 2013-04-30 14:01:33]

Thanks for the review. Landing.

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/flow_graph.h#newco...
runtime/vm/flow_graph.h:301: // path between these blocks.
On 2013/04/29 12:11:54, Florian Schneider wrote:
> This definition is not precise about what the code actually computes:
> 
> Assuming no side effects in blocks A, B, C, D and a diamond-shaped graph A->B,
> A->C, B->D, C->D
> 
> in(A) = {},  out(A) = {A}
> in(B) = {A}, out(B) = {A,B}
> in(C) = {A}, out(C) = {A,C}
> in(D) = {A}, out(D) = {A,D}
> 
> There is a path without side effects from B to D, but B is not in in(D)
because
> {A,B} intersect {A,C} is just {A}.

Done.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/flow_graph.h#newco...
runtime/vm/flow_graph.h:302: GrowableArray<BitVector*> live_in_;
On 2013/04/29 12:11:54, Florian Schneider wrote:
> Maybe choose a better name for in/out. live_in is already used for live
> variables. e.g. freepath_in, freepath_out

Renamed to available_at_ and available_after

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3951: class CSEInstructionMap {
On 2013/04/29 17:16:26, srdjan wrote:
> : public ValueObject

Done.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/flow_graph_optimiz...
runtime/vm/flow_graph_optimizer.cc:3960: CSEInstructionMap(const
CSEInstructionMap& other)
On 2013/04/29 17:16:26, srdjan wrote:
> explicit

Done.

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:110:
unary_checks().HasReceiverClassId(kTwoByteStringCid);
On 2013/04/29 17:16:26, srdjan wrote:
> Need to add all typed data arrays as well.

I suggest we add them in a separate CL.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.cc:111: return externalizable ?
EffectSet::All() : EffectSet::None();
On 2013/04/29 12:11:54, Florian Schneider wrote:
> Shouldn't the dependencies be EffectSet::kExternalizable?
> 
> Right now, there is no difference because it is equals to All().

Done.

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

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:747: // Returns true if the instruction may
have side effects.
On 2013/04/29 12:11:54, Florian Schneider wrote:
> Returns set of effects created by this instruction.

Done.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2893: 
On 2013/04/29 12:11:54, Florian Schneider wrote:
> Extra \n?

Done.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2934: UNREACHABLE();
On 2013/04/29 12:11:54, Florian Schneider wrote:
> Maybe add a comment: // Never used in optimizing compiler.

Done.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:2973: UNREACHABLE();
On 2013/04/29 12:11:54, Florian Schneider wrote:
> Maybe add a comment: // Never used in optimizing compiler.

Done.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:3052: virtual EffectSet Effects() const {
return EffectSet::None(); }
On 2013/04/29 12:11:54, Florian Schneider wrote:
> Add a comment why stores are excluded from side effects here.

Done.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:3148: virtual EffectSet Effects() const {
return EffectSet::None(); }
On 2013/04/29 12:11:54, Florian Schneider wrote:
> Add a comment why stores are excluded from side effects here.

Done.

https://codereview.chromium.org/14021016/diff/1/runtime/vm/intermediate_langu...
runtime/vm/intermediate_language.h:3675: virtual EffectSet Effects() const {
return EffectSet::All(); }
On 2013/04/29 12:11:54, Florian Schneider wrote:
> It seems this could be ::None() as well.

Done.

[Florian Schneider, 2013-04-30 14:07:49]

LGTM.

[Vyacheslav Egorov (Google), 2013-04-30 14:25:28]

Committed patchset #3 manually as r22180 (presubmit successful).