cps-ir: Merge variables based on set-based liveness and graph coloring.

cps-ir: Merge variables based on set-based liveness and graph coloring.

RegisterAllocator and CopyPropagator have been removed.

Variables are merged after StatementRewriter.

This simplifies CPS->Tree translation is a little bit since the mapping
to variables is one-to-one.

The StatementRewriter has a more SSA-like input, but has to be more
aggressive when looking for a redex. It now looks through a chain of
phi-assignments to check if two statements can be combined, whereas
before it would only combine two identical jumps.

I haven't been able to measure a significant slowdown, though I'm sure
it is at least a little bit slower.

R=kmillikin@google.com

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

[asgerf, 2015-03-19 14:39:18]

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

[Kevin Millikin (Google), 2015-03-20 11:12:04]

Some small comments, I'm still reviewing the variable merger file.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart (right):

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart:401: reduced =
visitStatement(reduced);
I like tail calls, just return visitStatement(reduced);.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart:563: if (s is
Break && t is Break && s.target == t.target) {
I sort of prefer a top-level structure dispatching solely on the type of s like
so:

if (s is Break) {
  if (t is! Break || s.target != t.target) return null;
  --t.target.useCount;
  return s;
} else if (s is Continue) {
  // ...
} else if (s is Return) // ...

or similar.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart (right):

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:49: final
Map<cps_ir.Primitive, Variable> primitive2variable =
I don't really like this naming convention.  At the use site you normally want
to read this like a function from the key to the value.  There you normally
already know the type of the key so putting it in the name is redundant.  And
you'd rather know the interpretation of the value, not just its type.

As a concrete suggestion: primitive2varible => variables (or treeVariables) and
mutable2variable => mutableVariables (or mutableTreeVariables) though I'm not
sure if that's the best we can come up with.

[Kevin Millikin (Google), 2015-03-26 14:35:55]

I think the algorithm looks good.  I have a lot of suggestions for more
comments, though.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart (right):

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:48: /// Each
block consists of a sequence of reads or a sequence of writes.
Flesh out this comment a bit to say explicitly that these are basic blocks but
not maximal basic blocks.  Also, indicate why we've chosen to do it that way,
which is what the reader will probably wonder.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:50: /// List of
predecessors in the control-flow graph.s
There's an extra 's'.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:63: /// Variables
being read or written in this block.
I'd mention either "Sequence of variables" or "in this block, in order" or the
like to distinguish it from a set.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:66: ///
Auxilliary fields used by the liveness analysis.
One 'l' in auxiliary.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:68: Set<Variable>
liveBefore = new Set<Variable>();
Consider liveIn and liveOut, which are fairly standard.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:79: class
BlockGraphBuilder extends RecursiveVisitor {
The blank line after class isn't necessary.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:81: Map<Label,
Block> jumpTarget = <Label, Block>{};
I'd make most of these private names, except for the public api ('blocks'). 
Especially state like currentBlock.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:106: /// Starts a
new branch after the end of [block].
Not necessary a branch (at least, not a non-trivial one).  I'd just say "Starts
a new block..." in the comment.  I'm not sure I'd change the function's name,
because I can't think of anything much better.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:115: void
read(Variable v) {
Go ahead and spell out 'variable', here and below.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:120:
currentBlock.isRead = true;
true is the default and we do rely on that a bit below, so perhaps it's clearer
to just assert it.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:133: if
(!currentBlock.variables.isEmpty) {
This needs a short comment to explain that this code is because the default for
blocks is isRead, so we are handling the first variable use in a fresh block.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:202: Block
tryBlock = newBlock(catchBlock: catchBlock);
The three lines starting here are branchFrom with a catch block.  I suggest
making branchFrom (optionally) take a catch block.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:207:
node.catchParameters.forEach(finalWrite);
Is this necessary or defensive?  It seems like since the catch parameters are
mutable, we could have phi-assignments to them, and we'd want to try to coalesce
them.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:256: List<Block>
worklist = new List<Block>.from(blocks);
Comment that blocks are initially in AST order and that visiting them in reverse
with a LIFO stack is probably a good order.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:260:
Set<Variable> live = new Set<Variable>.from(block.liveAfter);
This is potentially expensive, it's making an iterable from block.liveAfter,
creating a new LinkedHashSet, and then adding each element from the iterable to
the new set.  Comment that a specialized set implementation would be faster to
copy.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:263:
live.addAll(block.variables);
I think it is worth pointing out that our blocks are either reads or writes, so
in terms of liveness analysis, they either have an empty kill set (for reads) or
an empty gen set, and that the list of variables in the block is the gen set
(for reads) or the kill set.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:274: if
(block.liveBefore.length < live.length) {
Comment that this is a monotone analysis: the liveIn and liveOut sets start
empty and only grow, so we can use the length to detect changes.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:278: for (Block
pred in block.predecessors) {
Spell out predecessor.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:279: int size =
pred.liveAfter.length;
size ==> length, or originalLength or the like.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:290: int size =
pred.liveAfter.length;
Use 'length' in the name, not 'size'.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:292: if (size <
pred.liveAfter.length) {
The analogous comparison in the loop above has size on the right, so it should
be on the right here too.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:298:
pred.variables.removeWhere(block.liveBefore.contains);
block.liveBefore is the same as live, isn't it?  I think you should just use one
or the other and not mix them.

There should also be a comment here that points out that we are removing
variables from a write block, that is from a kill set, so the liveIn set can
only grow (the analysis is still monotone).

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:303: if
(!pred.inWorklist && changed) {
Probably cheaper to check changed before !pred.inWorklist, and it will parallel
the analogous check in the loop above.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:325:
Map<Variable, Set<Variable>> edges = new Map<Variable, Set<Variable>>();
edges ==> interferences

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:333: for
(Variable x in block.liveAfter) {
x ==> variable

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:366: for
(Variable v2 in edges[v1]) {
I don't have a feel for how big the sets of interferences are and so how often
we have to choose new colors.

Does it make sense to have an early exit like:

Set<Variable> potential = new Set<Variable>.from(register);
if (potential.isNotEmpty) {
  for (Variable v2 in edges[v1]) {
    v2 = subst[v2];
    if (v2 != null) {
      potential.remove(v2);
    }
    if (potential.isEmpty) break;
  }
}

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:385: class
SubstVariables extends RecursiveVisitor {
I'm not sure what Subst is supposed to be.  The verb 'substitute'?  That's a
good sign we should spell it out.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:391: Variable
replaceRead(Variable v) {
v ==> variable, w ==> other.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:393: if (w ==
null) return v;
This is the case for final assignments, or does it arise some other way?  It
needs a comment.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:408: for (int
i=0; i < parameters.length; i++) {
'i = 0'.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:433: for (int
i=0; i<node.arguments.length; i++) {
'i = 0', 'i < node.arguments.length'.

And '++i' :)

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:472: Statement
visitBreak(Break node) => node;
I usually make all the 'related' method bodies have a parallel style, so

Statement visitBreak(Break node) {
  return node;
}

[asgerf, 2015-03-27 15:18:28]

I went ahead and switched to interleaved blocks and gen/kill sets. 

I don't like implementing it like A and then documenting it as if it was B.

Sorry for the review overhead.

The most non-standard thing now is probably the way the gen set is only added to
liveIn at the first iteration. But at least we don't need to copy sets any more
(yay).

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart (right):

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:48: /// Each
block consists of a sequence of reads or a sequence of writes.
On 2015/03/26 14:35:54, kmillikin wrote:
> Flesh out this comment a bit to say explicitly that these are basic blocks but
> not maximal basic blocks.  Also, indicate why we've chosen to do it that way,
> which is what the reader will probably wonder.

Changed to basic blocks with interleaved operations.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:50: /// List of
predecessors in the control-flow graph.s
On 2015/03/26 14:35:53, kmillikin wrote:
> There's an extra 's'.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:63: /// Variables
being read or written in this block.
On 2015/03/26 14:35:53, kmillikin wrote:
> I'd mention either "Sequence of variables" or "in this block, in order" or the
> like to distinguish it from a set.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:66: ///
Auxilliary fields used by the liveness analysis.
On 2015/03/26 14:35:54, kmillikin wrote:
> One 'l' in auxiliary.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:68: Set<Variable>
liveBefore = new Set<Variable>();
On 2015/03/26 14:35:54, kmillikin wrote:
> Consider liveIn and liveOut, which are fairly standard.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:79: class
BlockGraphBuilder extends RecursiveVisitor {
On 2015/03/26 14:35:55, kmillikin wrote:
> The blank line after class isn't necessary.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:81: Map<Label,
Block> jumpTarget = <Label, Block>{};
On 2015/03/26 14:35:53, kmillikin wrote:
> I'd make most of these private names, except for the public api ('blocks'). 
> Especially state like currentBlock.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:106: /// Starts a
new branch after the end of [block].
On 2015/03/26 14:35:53, kmillikin wrote:
> Not necessary a branch (at least, not a non-trivial one).  I'd just say
"Starts
> a new block..." in the comment.  I'm not sure I'd change the function's name,
> because I can't think of anything much better.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:115: void
read(Variable v) {
On 2015/03/26 14:35:54, kmillikin wrote:
> Go ahead and spell out 'variable', here and below.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:120:
currentBlock.isRead = true;
On 2015/03/26 14:35:53, kmillikin wrote:
> true is the default and we do rely on that a bit below, so perhaps it's
clearer
> to just assert it.

Not relevant anymore.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:133: if
(!currentBlock.variables.isEmpty) {
On 2015/03/26 14:35:54, kmillikin wrote:
> This needs a short comment to explain that this code is because the default
for
> blocks is isRead, so we are handling the first variable use in a fresh block.

Not relevant anymore.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:202: Block
tryBlock = newBlock(catchBlock: catchBlock);
On 2015/03/26 14:35:53, kmillikin wrote:
> The three lines starting here are branchFrom with a catch block.  I suggest
> making branchFrom (optionally) take a catch block.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:207:
node.catchParameters.forEach(finalWrite);
On 2015/03/26 14:35:53, kmillikin wrote:
> Is this necessary or defensive?  It seems like since the catch parameters are
> mutable, we could have phi-assignments to them, and we'd want to try to
coalesce
> them.

Both. Something smarter could be done, but it's not so simple.

A catch parameter can't be hoisted to the top of the function, so if we merge it
with a variable that is used both inside and outside the catch body, the two
uses will be end up referring to different variables. This is the case for both
JS and Dart.

Since we only merge variables that originated from the same source variable,
this seem unlikely to happen, but I'm not convinced that it can't. For example:

try { 
    return foo();
} catch (e) {
    if (e is! SmartException) e = new SmartException(e);
    e.beSmart();
}

Since the code after catch is only reachable from the catch, it's not hard to
imagine that a CPS rewrite might shuffle the code around a little, so it looks
like this:

var e2;
try {
    return foo();
} catch (e) {
    if (e is! SmartException) {
        e2 = new SmartException(e);
    } else {
        e2 = e;
    }
}
e2.beSmart();

We can't merge e and e2 in this case. Not even in JavaScript, where catch blocks
also their own scope.

Since catch parameters are probably almost never assigned to, this seems like an
acceptable loss.

I've clarified with a comment.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:256: List<Block>
worklist = new List<Block>.from(blocks);
On 2015/03/26 14:35:53, kmillikin wrote:
> Comment that blocks are initially in AST order and that visiting them in
reverse
> with a LIFO stack is probably a good order.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:260:
Set<Variable> live = new Set<Variable>.from(block.liveAfter);
On 2015/03/26 14:35:53, kmillikin wrote:
> This is potentially expensive, it's making an iterable from block.liveAfter,
> creating a new LinkedHashSet, and then adding each element from the iterable
to
> the new set.  Comment that a specialized set implementation would be faster to
> copy.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:263:
live.addAll(block.variables);
On 2015/03/26 14:35:54, kmillikin wrote:
> I think it is worth pointing out that our blocks are either reads or writes,
so
> in terms of liveness analysis, they either have an empty kill set (for reads)
or
> an empty gen set, and that the list of variables in the block is the gen set
> (for reads) or the kill set.

Not relevant anymore.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:274: if
(block.liveBefore.length < live.length) {
On 2015/03/26 14:35:54, kmillikin wrote:
> Comment that this is a monotone analysis: the liveIn and liveOut sets start
> empty and only grow, so we can use the length to detect changes.

I agree, but there is now an explicit changed flag.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:278: for (Block
pred in block.predecessors) {
On 2015/03/26 14:35:53, kmillikin wrote:
> Spell out predecessor.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:279: int size =
pred.liveAfter.length;
On 2015/03/26 14:35:54, kmillikin wrote:
> size ==> length, or originalLength or the like.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:290: int size =
pred.liveAfter.length;
On 2015/03/26 14:35:54, kmillikin wrote:
> Use 'length' in the name, not 'size'.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:298:
pred.variables.removeWhere(block.liveBefore.contains);
On 2015/03/26 14:35:55, kmillikin wrote:
> block.liveBefore is the same as live, isn't it?  I think you should just use
one
> or the other and not mix them.
> 
> There should also be a comment here that points out that we are removing
> variables from a write block, that is from a kill set, so the liveIn set can
> only grow (the analysis is still monotone).

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:303: if
(!pred.inWorklist && changed) {
On 2015/03/26 14:35:54, kmillikin wrote:
> Probably cheaper to check changed before !pred.inWorklist, and it will
parallel
> the analogous check in the loop above.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:325:
Map<Variable, Set<Variable>> edges = new Map<Variable, Set<Variable>>();
On 2015/03/26 14:35:55, kmillikin wrote:
> edges ==> interferences

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:333: for
(Variable x in block.liveAfter) {
On 2015/03/26 14:35:53, kmillikin wrote:
> x ==> variable

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:366: for
(Variable v2 in edges[v1]) {
On 2015/03/26 14:35:54, kmillikin wrote:
> I don't have a feel for how big the sets of interferences are and so how often
> we have to choose new colors.
> 
> Does it make sense to have an early exit like:
> 
> Set<Variable> potential = new Set<Variable>.from(register);
> if (potential.isNotEmpty) {
>   for (Variable v2 in edges[v1]) {
>     v2 = subst[v2];
>     if (v2 != null) {
>       potential.remove(v2);
>     }
>     if (potential.isEmpty) break;
>   }
> }

When compiling swarm, it's empty about 90% of the time. So it might pay off to
treat that case specially.

I rewrote it a little bit to also avoid building a set from the empty list.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:385: class
SubstVariables extends RecursiveVisitor {
On 2015/03/26 14:35:53, kmillikin wrote:
> I'm not sure what Subst is supposed to be.  The verb 'substitute'?  That's a
> good sign we should spell it out.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:391: Variable
replaceRead(Variable v) {
On 2015/03/26 14:35:54, kmillikin wrote:
> v ==> variable, w ==> other.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:393: if (w ==
null) return v;
On 2015/03/26 14:35:54, kmillikin wrote:
> This is the case for final assignments, or does it arise some other way?  It
> needs a comment.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:408: for (int
i=0; i < parameters.length; i++) {
On 2015/03/26 14:35:54, kmillikin wrote:
> 'i = 0'.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:433: for (int
i=0; i<node.arguments.length; i++) {
On 2015/03/26 14:35:54, kmillikin wrote:
> 'i = 0', 'i < node.arguments.length'.
> 
> And '++i' :)

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:472: Statement
visitBreak(Break node) => node;
On 2015/03/26 14:35:54, kmillikin wrote:
> I usually make all the 'related' method bodies have a parallel style, so
> 
> Statement visitBreak(Break node) {
>   return node;
> }

Done.

[asgerf, 2015-03-31 11:50:39]

PTAL.

Following our offline discussion about reprocessing expressions: I fixed it in
the upcoming CL for assignment expressions because it has better infrastructure
for it. Unfortunately, that CL is based on this one, so I've just left it as a
TODO in here.

[asgerf, 2015-03-31 12:14:19]

(Missed a few comments in my first pass)

Please see previous message.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart (right):

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart:401: reduced =
visitStatement(reduced);
On 2015/03/20 11:12:03, kmillikin wrote:
> I like tail calls, just return visitStatement(reduced);.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart:563: if (s is
Break && t is Break && s.target == t.target) {
On 2015/03/20 11:12:03, kmillikin wrote:
> I sort of prefer a top-level structure dispatching solely on the type of s
like
> so:
> 
> if (s is Break) {
>   if (t is! Break || s.target != t.target) return null;
>   --t.target.useCount;
>   return s;
> } else if (s is Continue) {
>   // ...
> } else if (s is Return) // ...
> 
> or similar.

Doesn't really work for me.

I try to write it in a style that makes Dart's type promotion work and without
too many nested ifs and redundant variable redeclarations.

"if (t is! Break) return" will not promote the type of t, for instance.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart (right):

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:292: if (size <
pred.liveAfter.length) {
On 2015/03/26 14:35:54, kmillikin wrote:
> The analogous comparison in the loop above has size on the right, so it should
> be on the right here too.

Done.

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart (right):

https://codereview.chromium.org/1007103003/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:49: final
Map<cps_ir.Primitive, Variable> primitive2variable =
On 2015/03/20 11:12:03, kmillikin wrote:
> I don't really like this naming convention.  At the use site you normally want
> to read this like a function from the key to the value.  There you normally
> already know the type of the key so putting it in the name is redundant.  And
> you'd rather know the interpretation of the value, not just its type.
> 
> As a concrete suggestion: primitive2varible => variables (or treeVariables)
and
> mutable2variable => mutableVariables (or mutableTreeVariables) though I'm not
> sure if that's the best we can come up with.

I don't think of it as the type of the key. We map variables in the input
language to variables in the output language, but since we have two kinds of
input variables (primitives and mutables), we need two maps and it seems natural
to name them accordingly.

We could also have a single map:

    Map<cps.Definition, Variable> variables;

That would work for me.

[Kevin Millikin (Google), 2015-04-07 14:03:00]

Very much nicer.  LGTM and STV.

https://codereview.chromium.org/1007103003/diff/80001/pkg/compiler/lib/src/tr...
File pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart (right):

https://codereview.chromium.org/1007103003/diff/80001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:82: void
addRead(Variable variable) {
I guess there should be a comment here reminding us that we visit read/writes in
a block in a forward order --- then this code is 'obviously' correct.

[asgerf, 2015-04-08 10:59:39]

Committed patchset #7 (id:120001) manually as 44962 (presubmit successful).