Work around buggy break in List.sort and optimize constant folding of negative values.

Work around buggy break in List.sort and optimize constant folding of negative values.

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

[floitsch, 2012-02-29 20:28:10]

LGTM.

[ngeoffray, 2012-02-29 20:36:26]

DBC

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
dart/frog/leg/ssa/builder.dart:1309:
stack.add(graph.addNewLiteralInt(-operand.value));
Why is that not done in the constant folder instead?

[ahe, 2012-02-29 20:41:24]

Hi Florian and Nicolas,

Thank you for taking a look.

Cheers,
Peter

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
dart/frog/leg/ssa/builder.dart:1309:
stack.add(graph.addNewLiteralInt(-operand.value));
On 2012/02/29 20:36:26, ngeoffray wrote:
> Why is that not done in the constant folder instead?

Because it is really slow at doing it.

[kasperl, 2012-03-01 06:13:00]

LGTM but:

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
dart/frog/leg/ssa/builder.dart:1305: case "-":
This could possible be dealt with in a faster way by not visiting the
node.receiver when it is a literal (thus not creating the initial HLiteral node
at all). That way we also don't have to use 'is double' and 'is int' to
distinguish. Feel free to throw in a TODO(kasperl) so I don't forget about this.

[ahe, 2012-03-01 06:54:15]

Hi Kasper,

Thank you for taking a look. I have added a TODO for you.

Cheers,
Peter

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
dart/frog/leg/ssa/builder.dart:1305: case "-":
On 2012/03/01 06:13:00, kasperl wrote:
> This could possible be dealt with in a faster way by not visiting the
> node.receiver when it is a literal (thus not creating the initial HLiteral
node
> at all). That way we also don't have to use 'is double' and 'is int' to
> distinguish. Feel free to throw in a TODO(kasperl) so I don't forget about
this.

Done.

[ngeoffray, 2012-03-01 08:15:51]

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
dart/frog/leg/ssa/builder.dart:1309:
stack.add(graph.addNewLiteralInt(-operand.value));
On 2012/02/29 20:41:24, ahe wrote:
> On 2012/02/29 20:36:26, ngeoffray wrote:
> > Why is that not done in the constant folder instead?
> 
> Because it is really slow at doing it.

Why is that?

[floitsch, 2012-03-01 10:32:18]

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9536020/diff/1/dart/frog/leg/ssa/build...
dart/frog/leg/ssa/builder.dart:1309:
stack.add(graph.addNewLiteralInt(-operand.value));
On 2012/03/01 08:15:51, ngeoffray wrote:
> On 2012/02/29 20:41:24, ahe wrote:
> > On 2012/02/29 20:36:26, ngeoffray wrote:
> > > Why is that not done in the constant folder instead?
> > 
> > Because it is really slow at doing it.
> 
> Why is that?

The problem is not really the constant folding, but then replacing the
instruction with the folded one.
Currently we know in which instruction we are used, but not exactly at which
position. For arrays, which have hundreds of inputs, finding the old instruction
to replace it with the new folded one, boils down to doing a linear search.
The worst case is basically an array like: [-1, -2, -3....].
Then each input is replaced and searched for in a linear way yielding n^2
behavior.
This CL is a short-term fix, but we (kasper and I) have discussed better ways to
replace it.