Fix LoadOptimizer's handling of load/stores with constant indices for TypedData.

Fix LoadOptimizer's handling of load/stores with constant indices for TypedData.

LoadOptimizer computes KILL sets in assumption that place X[C] can alias place X[K] if and only if K == C. This however does not hold for TypedData where X[0] can alias X[1] if we are reading 32bit value at X[0] and 8bit value at X[1]. The only thing that TypedData guarantees is that all accesses are done with byte offsets aligned by the size of the data type.

This change incorporates TypeData elements aliasing rules into LoadOptimizer:

- Place hierarchy was extended with constant index places for TypedData X[C|S]:
  - C is a byte offset to the element being read instead of an unscaled index that was used before;
  - S size of the element being read.

- KILL set computation ensures the following aliasing rule:

      X[C|S] aliases X[RoundDown(C, S')|S'] for all sizes S' > S

R=fschneider@google.com
BUG=http://dartbug.com/22120

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

[Florian Schneider, 2015-01-26 13:30:40]

LGTM with the added test coverage.

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

https://codereview.chromium.org/868283002/diff/1/runtime/vm/flow_graph_optimi...
runtime/vm/flow_graph_optimizer.cc:5098: //     offset is always aligned by the
data type size. We write these accesses
Do you mean data type size of the underlying array or size of the access?

Because it seems possible to write e.g. an int32 from offset 1 of an
Float32Array: Can you add a test like this? (on ARM it will fail due to
unaligned access due to another issue)

  var x = new Float32List(2);
  var y = x.buffer.asByteData();
  y.setFloat32(0, 1.5);
  y.setInt32(1, 0);
  return y.getFloat32(0);


Maybe clarify that the start of the view is aligned and the check below ensures
that constant indices are aligned.

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
File tests/language/vm/load_to_load_forwarding_vm_test.dart (right):

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
tests/language/vm/load_to_load_forwarding_vm_test.dart:492: f64[0] = 1.0;  //
lower 32bits are all 0s
Comment: Should not be forwarded.

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
tests/language/vm/load_to_load_forwarding_vm_test.dart:500: f64[1] = 1.0;
Comment: Should be forwarded.

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
tests/language/vm/load_to_load_forwarding_vm_test.dart:508: f64[0] = 1.0;
Comment: Should be forwarded, [0,7] and [14], [15] don't overlap.

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
tests/language/vm/load_to_load_forwarding_vm_test.dart:517: f64[0] = 2.0;  //
Not aliased: should be forwarded.
This should not be forwarded, since f64[0] writes [0,7] and [0],[1] overlap.

[Vyacheslav Egorov (Google), 2015-01-26 14:57:16]

All done. Added separate test (marked as Crashing on ARM&MIPS)

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

https://codereview.chromium.org/868283002/diff/1/runtime/vm/flow_graph_optimi...
runtime/vm/flow_graph_optimizer.cc:5098: //     offset is always aligned by the
data type size. We write these accesses
On 2015/01/26 13:30:39, Florian Schneider wrote:
> Do you mean data type size of the underlying array or size of the access?
> 
> Because it seems possible to write e.g. an int32 from offset 1 of an
> Float32Array: Can you add a test like this? (on ARM it will fail due to
> unaligned access due to another issue)
> 
>   var x = new Float32List(2);
>   var y = x.buffer.asByteData();
>   y.setFloat32(0, 1.5);
>   y.setInt32(1, 0);
>   return y.getFloat32(0);
> 
> 
> Maybe clarify that the start of the view is aligned and the check below
ensures
> that constant indices are aligned.

I was talking about element size (access size). I have amended the comment as
discussed.

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
File tests/language/vm/load_to_load_forwarding_vm_test.dart (right):

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
tests/language/vm/load_to_load_forwarding_vm_test.dart:492: f64[0] = 1.0;  //
lower 32bits are all 0s
On 2015/01/26 13:30:39, Florian Schneider wrote:
> Comment: Should not be forwarded.

Done.

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
tests/language/vm/load_to_load_forwarding_vm_test.dart:500: f64[1] = 1.0;
On 2015/01/26 13:30:39, Florian Schneider wrote:
> Comment: Should be forwarded.

Should *not* be forwarded.

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
tests/language/vm/load_to_load_forwarding_vm_test.dart:508: f64[0] = 1.0;
On 2015/01/26 13:30:39, Florian Schneider wrote:
> Comment: Should be forwarded, [0,7] and [14], [15] don't overlap.

note: view starts at 8 - means f64[0] is bytes 8-15. should not be forwarded.

https://codereview.chromium.org/868283002/diff/1/tests/language/vm/load_to_lo...
tests/language/vm/load_to_load_forwarding_vm_test.dart:517: f64[0] = 2.0;  //
Not aliased: should be forwarded.
On 2015/01/26 13:30:39, Florian Schneider wrote:
> This should not be forwarded, since f64[0] writes [0,7] and [0],[1] overlap.

note: view starts at 8 like about. should *be* forwarded.

[Florian Schneider, 2015-01-26 15:09:12]

LGTM. Thanks!

[Vyacheslav Egorov (Google), 2015-01-26 15:14:44]

Committed patchset #2 (id:20001) manually as 43137 (presubmit successful).