Lattice-based representation inference, powered by left/right specific type feedback for BinaryOps …

Lattice-based representation inference, powered by left/right specific type feedback for BinaryOps and comparisons

Committed: https://code.google.com/p/v8/source/detail?r=12961

[Jakob Kummerow, 2012-09-14 12:45:09]

The platform independent stuff and the ia32 port are ready for review. Please
take a look.

High-level overview: This CL contains the following things (which unfortunately
are closely related, so it's hard to split up):

1.) Keep track of type feedback for left/right inputs separately in BinaryOp ICs
and Compare ICs. One side-effect is that the CompareStub got folded into the
ICCompareStub.
2.) Feed this fine grained type feedback into Hydrogen, where HValues store it
as observed_input_representation. Use it to infer appropriate representations
for HValues based on what we've seen in the full code.
3.) Invert the working direction of the representation inference algorithm to
match what we're doing elsewhere: start with the most specific type, become more
generic as required (fixed-point iteration over the lattice None -> Int32 ->
Double -> Tagged). Since this is partly dependent on the type of HInstruction,
the code has been moved from HInferRepresentation to HValue, so that subclasses
can override it.

[Jakob Kummerow, 2012-10-18 12:12:08]

Platform-independent parts are ready for review. Please take a look.

To reduce the amount of duplicated changes, I moved the definition of
BinaryOpStub as well as platform-independent implementation to code-stubs.h/cc.

[danno, 2012-11-06 11:42:59]

First round of comments

http://codereview.chromium.org/10837165/diff/28001/src/arm/code-stubs-arm.cc
File src/arm/code-stubs-arm.cc (right):

http://codereview.chromium.org/10837165/diff/28001/src/arm/code-stubs-arm.cc#...
src/arm/code-stubs-arm.cc:2485: void
BinaryOpStub_GenerateHeapResultAllocation(MacroAssembler* masm,
Make into a real class method without the "_"

http://codereview.chromium.org/10837165/diff/28001/src/arm/lithium-arm.cc
File src/arm/lithium-arm.cc (right):

http://codereview.chromium.org/10837165/diff/28001/src/arm/lithium-arm.cc#new...
src/arm/lithium-arm.cc:2165: for (int i = instr->values()->length() - 1; i >= 0;
--i) {
Add a comment describing why the order is reversed.

http://codereview.chromium.org/10837165/diff/28001/src/code-stubs.h
File src/code-stubs.h (right):

http://codereview.chromium.org/10837165/diff/28001/src/code-stubs.h#newcode518
src/code-stubs.h:518: *result_type=
nit: space after type

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:132: if (new_rep.IsInteger32() &&
!IsConvertibleToInteger()) {
Add a comment

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2636: 
nit: two lines

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen-instructions....
src/hydrogen-instructions.h:804: void
AddDependantsToWorklist(HInferRepresentation* hinfer);
h_infer

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen-instructions....
src/hydrogen-instructions.h:1129: virtual Representation
observed_input_representation(int index) {
put in .cc file

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen-instructions....
src/hydrogen-instructions.h:1351: HSimulate(BailoutId ast_id, int pop_count,
Zone* zone, bool optional)
removable

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen-instructions....
src/hydrogen-instructions.h:2995: SetAllSideEffects();
Probably not necessary

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen.cc
File src/hydrogen.cc (right):

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen.cc#newcode2362
src/hydrogen.cc:2362: // With representations figured out, we can now remove
HSimulates
Make this a new method

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen.cc#newcode2574
src/hydrogen.cc:2574: Representation input_representation =
Comment would be nice.

http://codereview.chromium.org/10837165/diff/28001/src/hydrogen.cc#newcode2998
src/hydrogen.cc:2998: if (instr->HasObservableSideEffects())
owner()->AddSimulate(ast_id, true);
Create an enum for this

http://codereview.chromium.org/10837165/diff/28001/src/objects-inl.h
File src/objects-inl.h (right):

http://codereview.chromium.org/10837165/diff/28001/src/objects-inl.h#newcode4598
src/objects-inl.h:4598: }
nit: whitespace between

http://codereview.chromium.org/10837165/diff/28001/src/objects-inl.h#newcode4611
src/objects-inl.h:4611: kind() == BINARY_OP_IC);
one line

[Jakob Kummerow, 2012-11-06 12:44:05]

Feedback addressed.

Also in this patch set: a few fixes that had crept in due to rebasing.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/arm/code-stubs...
File src/arm/code-stubs-arm.cc (right):

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/arm/code-stubs...
src/arm/code-stubs-arm.cc:2485: void
BinaryOpStub_GenerateHeapResultAllocation(MacroAssembler* masm,
On 2012/11/06 11:42:59, danno wrote:
> Make into a real class method without the "_"

As discussed offline, that would not be as beautiful/simple as we initially
thought because of platform-dependent signatures (e.g. different numbers of
labels and scratch registers being passed in). So I'm leaving it as it is.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/arm/lithium-ar...
File src/arm/lithium-arm.cc (right):

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/arm/lithium-ar...
src/arm/lithium-arm.cc:2165: for (int i = instr->values()->length() - 1; i >= 0;
--i) {
On 2012/11/06 11:42:59, danno wrote:
> Add a comment describing why the order is reversed.

The comment is in hydrogen.cc, in HBasicBlock::CreateSimulate().

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/code-stubs.h
File src/code-stubs.h (right):

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/code-stubs.h#n...
src/code-stubs.h:518: *result_type=
On 2012/11/06 11:42:59, danno wrote:
> nit: space after type

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen-instr...
File src/hydrogen-instructions.cc (right):

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen-instr...
src/hydrogen-instructions.cc:132: if (new_rep.IsInteger32() &&
!IsConvertibleToInteger()) {
On 2012/11/06 11:42:59, danno wrote:
> Add a comment

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen-instr...
src/hydrogen-instructions.cc:2636: 
On 2012/11/06 11:42:59, danno wrote:
> nit: two lines

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen-instr...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen-instr...
src/hydrogen-instructions.h:804: void
AddDependantsToWorklist(HInferRepresentation* hinfer);
On 2012/11/06 11:42:59, danno wrote:
> h_infer

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen-instr...
src/hydrogen-instructions.h:1129: virtual Representation
observed_input_representation(int index) {
On 2012/11/06 11:42:59, danno wrote:
> put in .cc file

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen-instr...
src/hydrogen-instructions.h:1351: HSimulate(BailoutId ast_id, int pop_count,
Zone* zone, bool optional)
On 2012/11/06 11:42:59, danno wrote:
> removable

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen-instr...
src/hydrogen-instructions.h:2995: SetAllSideEffects();
On 2012/11/06 11:42:59, danno wrote:
> Probably not necessary

No, it is in fact necessary, because HBinaryOperation does not set it, because
some other classes derive from it that do not have side effects.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen.cc#ne...
src/hydrogen.cc:2362: // With representations figured out, we can now remove
HSimulates
On 2012/11/06 11:42:59, danno wrote:
> Make this a new method

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen.cc#ne...
src/hydrogen.cc:2574: Representation input_representation =
On 2012/11/06 11:42:59, danno wrote:
> Comment would be nice.

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/hydrogen.cc#ne...
src/hydrogen.cc:2998: if (instr->HasObservableSideEffects())
owner()->AddSimulate(ast_id, true);
On 2012/11/06 11:42:59, danno wrote:
> Create an enum for this

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/objects-inl.h
File src/objects-inl.h (right):

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/objects-inl.h#...
src/objects-inl.h:4598: }
On 2012/11/06 11:42:59, danno wrote:
> nit: whitespace between

Done.

https://chromiumcodereview.appspot.com/10837165/diff/28001/src/objects-inl.h#...
src/objects-inl.h:4611: kind() == BINARY_OP_IC);
On 2012/11/06 11:42:59, danno wrote:
> one line

Done.

[danno, 2012-11-14 10:38:22]

lgtm with nits

http://codereview.chromium.org/10837165/diff/30002/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

http://codereview.chromium.org/10837165/diff/30002/src/hydrogen-instructions....
src/hydrogen-instructions.h:1335: REMOVABLE,
make this REMOVABLE_SIMULATE?

http://codereview.chromium.org/10837165/diff/33002/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

http://codereview.chromium.org/10837165/diff/33002/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2632: Representation HPhi::AllNonPhiUsesObserved()
{
Add comment with what you described during the code review

http://codereview.chromium.org/10837165/diff/33002/src/ic.cc
File src/ic.cc (right):

http://codereview.chromium.org/10837165/diff/33002/src/ic.cc#newcode2429
src/ic.cc:2429: if (old_type == BinaryOpIC::UNINITIALIZED) return new_type;
remove above?

[Jakob Kummerow, 2012-11-14 15:53:23]

https://chromiumcodereview.appspot.com/10837165/diff/30002/src/hydrogen-instr...
File src/hydrogen-instructions.h (right):

https://chromiumcodereview.appspot.com/10837165/diff/30002/src/hydrogen-instr...
src/hydrogen-instructions.h:1335: REMOVABLE,
On 2012/11/14 10:38:22, danno wrote:
> make this REMOVABLE_SIMULATE?

Done.

https://chromiumcodereview.appspot.com/10837165/diff/33002/src/hydrogen-instr...
File src/hydrogen-instructions.cc (right):

https://chromiumcodereview.appspot.com/10837165/diff/33002/src/hydrogen-instr...
src/hydrogen-instructions.cc:2632: Representation HPhi::AllNonPhiUsesObserved()
{
On 2012/11/14 10:38:22, danno wrote:
> Add comment with what you described during the code review

Done.

https://chromiumcodereview.appspot.com/10837165/diff/33002/src/ic.cc
File src/ic.cc (right):

https://chromiumcodereview.appspot.com/10837165/diff/33002/src/ic.cc#newcode2429
src/ic.cc:2429: if (old_type == BinaryOpIC::UNINITIALIZED) return new_type;
On 2012/11/14 10:38:22, danno wrote:
> remove above?

Done.