Don't reference transitioned elements in loop pre header

Don't reference transitioned elements in hoisted instructions.
Test=imaging-desaturate slightly faster

[Zheng Liu, 2012-06-13 10:00:41]

Around ~11% in imaging-desaturate on my machine.


Zheng Liu
zheng.z.liu@intel.com

[danno, 2012-06-14 09:53:59]

In general, this isn't a good idea. AFAICT, you can't be sure that an
HElementsTransition dominates all of the uses of its inputs. It might work for
this benchmark, but I can think of straight-forward situations where this won't
be the case.

Furthermore, some instructions that depend on the input to the
HElementsTransition, like simple property Loads and Stores, may not benefit from
depending on the HTransition. It will prevent them from being hoisted into an
outer loop beyond the inner loop's preheader by doing this. Probably also not
the right thing to do.

What is the motivation of the change? If we are missing GVN opportunities for
selected instructions because they should be treated equivalently regardless
whether they depend on a HElementsTransition or the inputs to the
HElementsTransition, then the Equal method of those affected instructions should
be modified appropriately to handle those cases.

[Zheng Liu, 2012-06-14 13:41:32]

On 2012/06/14 09:53:59, danno wrote:
> In general, this isn't a good idea. AFAICT, you can't be sure that an
> HElementsTransition dominates all of the uses of its inputs. It might work for
> this benchmark, but I can think of straight-forward situations where this
won't
> be the case.
> 
I meant to replace the uses within the pre-header of loop, only for hoisted
instructions.
In current code, I let it start from block start, as I didn't think of cases
where it could be wrong.

> Furthermore, some instructions that depend on the input to the
> HElementsTransition, like simple property Loads and Stores, may not benefit
from
> depending on the HTransition. It will prevent them from being hoisted into an
> outer loop beyond the inner loop's preheader by doing this. 
Yes, the fixup should be served in a seperate loop after one pass of hoist.

> Probably also not
> the right thing to do.
> 
Could you please elaborate it a little?

> What is the motivation of the change? If we are missing GVN opportunities for
> selected instructions because they should be treated equivalently regardless
> whether they depend on a HElementsTransition or the inputs to the
> HElementsTransition, then the Equal method of those affected instructions
should
> be modified appropriately to handle those cases.
It's something like this: (part of a pre-header, all of these are hoised
instructions)
[t235  t237  i295] should be same as [t207  t209  i289]
...
1    t206  TransitionElementsKind t166 [FAST_HOLEY_SMI_ELEMENTS] ->
[FAST_HOLEY_DOUBLE_ELEMENTS]
	 changes[NewSpacePromotion,ElementsKind,ElementsPointer]
1    t207  CheckMaps t166 [0x3d508da1]
1    t209  JSArrayLength t166 t207
2    i289  Change t209 t to i range[-2147483648,2147483647,m0=0]
1    d290  Constant 0x46c93e35 <Number: 0.3>
1    d292  Constant 0x46c93e41 <Number: 0.59>
1    d294  Constant 0x46c93e4d <Number: 0.11>
6    t208  LoadElements t166
1    t235  CheckMaps t166 [0x3d508da1]
1    t237  JSArrayLength t166 t235
2    i295  Change t237 t to i range[-2147483648,2147483647,m0=0]
== END of Block ==

[Zheng Liu, 2012-06-15 02:37:37]

With latest v8, stock imaging-desaturate doesn't generate
TransitionElementsKind.
The effect can be observed by training it to have a TransitionElementsKind.

> Furthermore, some instructions that depend on the input to the
> HElementsTransition, like simple property Loads and Stores, may not benefit
from
> depending on the HTransition. It will prevent them from being hoisted into an
> outer loop beyond the inner loop's preheader by doing this.
Fixed.

[danno, 2012-06-19 15:45:05]

I've thought about this some more, and this approach seems a little too specific
and even a bit hacky, even ignoring the algorithmic complexity. 

If this optimization is worth while (BTW, what is the maximum win), it should
apply to all transitions in all blocks, not just pre-headers. 

It seems to me that are one of two approaches that seems better, but they are
more work:

1) Add a general pass that make sure that all uses of the input to a transition
that are dominated by the transition are canonicalized to the transition. You
might be able to fold this in to the logic in the GVN block processing where
there is special handling of transitions and somehow use the
loop-successor-dominator information so that the additional overhead isn't too
high, but I didn't really do a deep analysis.

2) Tweak the GVN equals check for CheckMaps to treat map checks dominated by
corresponding transition-dependent map check as equal. This is probably a bit
tricky, since there are assumptions about calculating the hash code of a HValues
based on its inputs, and this change would treat HValues with different inputs
as the same.

https://chromiumcodereview.appspot.com/10544133/diff/6001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/10544133/diff/6001/src/hydrogen.cc#new...
src/hydrogen.cc:1826: }
This is potentially a n^2 algorithm with respect to the number of instructions
in the pre header. This is not the right way to do this.