dart2js cps: Global value numbering and loop-invariant code motion.

dart2js cps: Global value numbering and loop-invariant code motion.

There is a new pass for doing GVN and LICM.

The 'share interceptors' pass previously GVN'ed and LICM'ed interceptors
but now only constifies them and lets GVN handle the rest.  The pass
has been renamed to optimize_interceptors.

The 'share final fields' pass has been removed since GVN does the same.

A new pass 'remove redundant refinements' removes some refinement nodes
that contribute no information.  These would sometimes block code motion
for no good reason.  This pass is should go away once GVN is able to
hoist expressions across refinement guards.

BUG=
R=sra@google.com

Committed: https://github.com/dart-lang/sdk/commit/84b164a52bf7c7d44a55fef7ff94b7c6ba7aa815

[asgerf, 2015-11-16 15:42:39]

asgerf@google.com changed reviewers:
+ kmillikin@google.com, sra@google.com

[asgerf, 2015-11-16 15:42:39]

https://codereview.chromium.org/1444363002/diff/40001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/loop_effects.dart (right):

https://codereview.chromium.org/1444363002/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/loop_effects.dart:96: 'loop side effects.';
This is similar to the problem of putting unreachable blocks into a dominator
tree. There is no correct place to put it, and putting it in an arbitrary place
can break some assumptions in the client analysis.

[sra1, 2015-11-17 05:41:15]

lgtm.

Can you test some of the edge cases, like hoisting a DAG?

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/gvn.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:142: if (prim.isSafeForElimination &&
currentLoopHeader != null) {
Is there some way to move these 80 lines into their own function?

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:148:
ReferenceVisitor.forEachReference(prim, (Reference ref) {
We should tweak the name a little.
On first reading I thought that this was the references to prim, not the
references to things depended on by prim.

Maybe change the names to allow:

PrimitiveInputReferences.forEach(prim, (Reference ref) { ... });


It would be nice to make this a sync* generator to enable for-in but I don't see
how without duplicating a lot of code.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:209: loop =
loopHierarchy.lowestCommonAncestor(loop, enclosingLoop);
line length

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:248: // The primitive might already be
bound in an outer scope.  Do not reloate
reloate

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:249: // the primitive unless we are lifting
it.
Would this happen if the primitive is referenced at different depths within the
'expression tree' being hoisted?

t1 = a + b;
t2 = t1 + c;
t3 = t1 * t2;

When visiting t1 via t2 it would already have been moved.
If this is correct, maybe describe it in a comment.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:429: target = body.constructor;
should be able to just do

   target = target.constructor;

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:525: /// Combines the hash codes of
[vector] using Jenkin's hash function.
At least say 'modified' Jenkin's, since the Smi masking makes it not exactly the
same.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:529: hash = 0x1fffffff & (hash +
vector[i].hashCode);
Do all the things we put in the vector have fast hashcode funtions?
Maybe use the index of enums to be safe.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:588: // TODO(asgerf): Take fixed lengths
into account?
Yes. For typed arrays V8 should know how to connect the hoisted length to the
indexer's bounds check. For Arrays, we can always re-sink later if we estimate
that the loop will confuse the JS engine.
http://mrale.ph/blog/2014/12/24/array-length-caching.html

A TODO is fine at this point.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:598: // TODO(asgerf): We should add a
GetNativeField instruction.
Maybe called GetProperty

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:661: class ReferenceVisitor extends
DeepRecursiveVisitor {
Maybe we should split DeepRecursiveVisitor into the primitives we are walking
here and the 'deep recursive' part.

The Primitives part could maybe be used here and also mixed-in to
DeepRecursiveVisitor.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:671: static void forEachReference(Node
node, ReferenceCallback callback) {
This is a pretty wild visitor pattern if `node` is not a Primitive.
Perhaps make the `node` parameter have type Primitive to prevent accidents.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/loop_effects.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/loop_effects.dart:96: 'loop side effects.';
On 2015/11/16 15:42:39, asgerf wrote:
> This is similar to the problem of putting unreachable blocks into a dominator
> tree. There is no correct place to put it, and putting it in an arbitrary
place
> can break some assumptions in the client analysis.

Use the proper internal error (possibly as separate CL)

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/loop_hierarchy.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/loop_hierarchy.dart:172: if (loop == null) return
-1;
It would be useful if unnested was 0 (depth can then be used as an index)

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart:161: /// TODO(asgerf):
Handle in seperate constant optimization pass? With some other
separate

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/redundant_refinement.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/redundant_refinement.dart:12: /// But some
opportunities for hoisting are still missed.  Ideally, this pass
Which are still missed?

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/type_mask_system.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/type_mask_system.dart:165: return
inferrer.getGuaranteedTypeOfElement(parameter) ?? dynamicType;
Why are these functions returning null?

[asgerf, 2015-11-17 12:43:43]

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/gvn.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:142: if (prim.isSafeForElimination &&
currentLoopHeader != null) {
On 2015/11/17 05:41:13, sra1 wrote:
> Is there some way to move these 80 lines into their own function?

Done. I'm glad to be rid of the pyramid of doom code and use early returns
instead.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:148:
ReferenceVisitor.forEachReference(prim, (Reference ref) {
On 2015/11/17 05:41:14, sra1 wrote:
> We should tweak the name a little.
> On first reading I thought that this was the references to prim, not the
> references to things depended on by prim.
> 
> Maybe change the names to allow:
> 
> PrimitiveInputReferences.forEach(prim, (Reference ref) { ... });
> 
> 
> It would be nice to make this a sync* generator to enable for-in but I don't
see
> how without duplicating a lot of code.

Changed to InputVisitor.forEach.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:209: loop =
loopHierarchy.lowestCommonAncestor(loop, enclosingLoop);
On 2015/11/17 05:41:14, sra1 wrote:
> line length

Done by extract method

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:248: // The primitive might already be
bound in an outer scope.  Do not reloate
On 2015/11/17 05:41:14, sra1 wrote:
> reloate

Done.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:249: // the primitive unless we are lifting
it.
On 2015/11/17 05:41:14, sra1 wrote:
> Would this happen if the primitive is referenced at different depths within
the
> 'expression tree' being hoisted?
> 
> t1 = a + b;
> t2 = t1 + c;
> t3 = t1 * t2;
> 
> When visiting t1 via t2 it would already have been moved.
> If this is correct, maybe describe it in a comment.

Yes, this is exactly how it happens. I put your example in a comment.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:429: target = body.constructor;
On 2015/11/17 05:41:14, sra1 wrote:
> should be able to just do
> 
>    target = target.constructor;

Type promotion bails out if the block contains an assignment to the promoted
variable :(.  I still can't believe it works like this.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:525: /// Combines the hash codes of
[vector] using Jenkin's hash function.
On 2015/11/17 05:41:14, sra1 wrote:
> At least say 'modified' Jenkin's, since the Smi masking makes it not exactly
the
> same.

Done.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:529: hash = 0x1fffffff & (hash +
vector[i].hashCode);
On 2015/11/17 05:41:14, sra1 wrote:
> Do all the things we put in the vector have fast hashcode funtions?
> Maybe use the index of enums to be safe.

There are: Element, DartType, Primitive, BuiltinOperator, and int.  I've changed
BuiltinOperator to use the index instead.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:588: // TODO(asgerf): Take fixed lengths
into account?
On 2015/11/17 05:41:14, sra1 wrote:
> Yes. For typed arrays V8 should know how to connect the hoisted length to the
> indexer's bounds check. For Arrays, we can always re-sink later if we estimate
> that the loop will confuse the JS engine.
> http://mrale.ph/blog/2014/12/24/array-length-caching.html
> 
> A TODO is fine at this point.

Acknowledged.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:598: // TODO(asgerf): We should add a
GetNativeField instruction.
On 2015/11/17 05:41:14, sra1 wrote:
> Maybe called GetProperty

Acknowledged.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:661: class ReferenceVisitor extends
DeepRecursiveVisitor {
On 2015/11/17 05:41:13, sra1 wrote:
> Maybe we should split DeepRecursiveVisitor into the primitives we are walking
> here and the 'deep recursive' part.
> 
> The Primitives part could maybe be used here and also mixed-in to
> DeepRecursiveVisitor.

The visitors need an overhaul, but I'd rather wait until after the refactoring.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/gvn.dart:671: static void forEachReference(Node
node, ReferenceCallback callback) {
On 2015/11/17 05:41:13, sra1 wrote:
> This is a pretty wild visitor pattern if `node` is not a Primitive.
> Perhaps make the `node` parameter have type Primitive to prevent accidents.
> 

Done.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/loop_effects.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/loop_effects.dart:96: 'loop side effects.';
On 2015/11/17 05:41:14, sra1 wrote:
> On 2015/11/16 15:42:39, asgerf wrote:
> > This is similar to the problem of putting unreachable blocks into a
dominator
> > tree. There is no correct place to put it, and putting it in an arbitrary
> place
> > can break some assumptions in the client analysis.
> 
> Use the proper internal error (possibly as separate CL)

Done.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/loop_hierarchy.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/loop_hierarchy.dart:172: if (loop == null) return
-1;
On 2015/11/17 05:41:14, sra1 wrote:
> It would be useful if unnested was 0 (depth can then be used as an index)

Done. (The first loop had depth 1 so it kind of wrong to begin with).

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/optimize_interceptors.dart:161: /// TODO(asgerf):
Handle in seperate constant optimization pass? With some other
On 2015/11/17 05:41:14, sra1 wrote:
> separate

Done.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/redundant_refinement.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/redundant_refinement.dart:12: /// But some
opportunities for hoisting are still missed.  Ideally, this pass
On 2015/11/17 05:41:15, sra1 wrote:
> Which are still missed?

Added example.

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
File pkg/compiler/lib/src/cps_ir/type_mask_system.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/40001/pkg/compiler/lib...
pkg/compiler/lib/src/cps_ir/type_mask_system.dart:165: return
inferrer.getGuaranteedTypeOfElement(parameter) ?? dynamicType;
On 2015/11/17 05:41:15, sra1 wrote:
> Why are these functions returning null?

I can't reproduce it anymore so I've reverted the null checks.

[sra1, 2015-11-18 23:33:15]

lgtm with test for hoisting a DAG.

[sra1, 2015-11-23 22:35:07]

https://chromiumcodereview.appspot.com/1444363002/diff/160001/tests/compiler/...
File tests/compiler/dart2js/js_backend_cps_ir_gvn_test.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/160001/tests/compiler/...
tests/compiler/dart2js/js_backend_cps_ir_gvn_test.dart:16: // Everything can be
hoisted out, except the bounds check and sum += z.
Nice

https://chromiumcodereview.appspot.com/1444363002/diff/160001/tests/compiler/...
tests/compiler/dart2js/js_backend_cps_ir_gvn_test.dart:18: var b = x.left.right;
Indentation is inconsistent

[asgerf, 2015-11-24 10:05:59]

https://chromiumcodereview.appspot.com/1444363002/diff/160001/tests/compiler/...
File tests/compiler/dart2js/js_backend_cps_ir_gvn_test.dart (right):

https://chromiumcodereview.appspot.com/1444363002/diff/160001/tests/compiler/...
tests/compiler/dart2js/js_backend_cps_ir_gvn_test.dart:16: // Everything can be
hoisted out, except the bounds check and sum += z.
On 2015/11/23 22:35:07, sra1 wrote:
> Nice

Acknowledged.

https://chromiumcodereview.appspot.com/1444363002/diff/160001/tests/compiler/...
tests/compiler/dart2js/js_backend_cps_ir_gvn_test.dart:18: var b = x.left.right;
On 2015/11/23 22:35:07, sra1 wrote:
> Indentation is inconsistent

Done.

[asgerf, 2015-11-24 11:45:38]

Committed patchset #13 (id:240001) manually as
84b164a52bf7c7d44a55fef7ff94b7c6ba7aa815 (presubmit successful).