Remove half of the checks for comparing two Obejcts

Remove half of the checks for comparing two Obejcts

BUG=

[danno, 2013-12-04 16:10:19]

Ben, can you take a look?

Weiliang, did you consider my other suggestion to only check the map once
explicitly? This can be done both for the IsClass case and the non-IsClass case,
since the equality guarantees one check suffices.

[titzer, 2013-12-04 16:31:59]

NOT LGTM.

https://codereview.chromium.org/104843002/diff/1/src/hydrogen-check-eliminati...
File src/hydrogen-check-elimination.cc (right):

https://codereview.chromium.org/104843002/diff/1/src/hydrogen-check-eliminati...
src/hydrogen-check-elimination.cc:292:
removed->DeleteAndReplaceWith(removed->ActualValue());
This transformation is completely incorrect. First, you haven't even checked
whether the two CheckMaps refer to the same object. Second, you haven't checked
the relationship between the CheckMaps either (does one entail another?). Third,
an object's map can change in between these instructions. Fourth, removing the
check heap object in between is only legal if the CheckMaps refer to the the
same object. Fourth, I have no idea why you choose to match this pattern at the
CompareObjectEqAndBranch instruction.

But, you did bring one optimization opportunity to mind. We can remove some
CheckHeapObject instructions for objects whose maps may no longer be known, but
they are still known to be heap objects.

[Weiliang, 2013-12-05 08:01:49]

On 2013/12/04 16:10:19, danno wrote:
> Ben, can you take a look?
> 
> Weiliang, did you consider my other suggestion to only check the map once
> explicitly? This can be done both for the IsClass case and the non-IsClass
case,
> since the equality guarantees one check suffices.

Hi Danno, 
I have followed your suggestion to only check the map once. But I does not do it
when building IR graph but just leave it to check_elimination pass when we have
more info to make the correct decision.

[Weiliang, 2013-12-05 08:34:37]

On 2013/12/04 16:31:59, titzer wrote:
> NOT LGTM.
> 
>
https://codereview.chromium.org/104843002/diff/1/src/hydrogen-check-eliminati...
> File src/hydrogen-check-elimination.cc (right):
> 
>
https://codereview.chromium.org/104843002/diff/1/src/hydrogen-check-eliminati...
> src/hydrogen-check-elimination.cc:292:
> removed->DeleteAndReplaceWith(removed->ActualValue());
> This transformation is completely incorrect. First, you haven't even checked
> whether the two CheckMaps refer to the same object. Second, you haven't
checked
> the relationship between the CheckMaps either (does one entail another?).
Third,
> an object's map can change in between these instructions. Fourth, removing the
> check heap object in between is only legal if the CheckMaps refer to the the
> same object. Fourth, I have no idea why you choose to match this pattern at
the
> CompareObjectEqAndBranch instruction.
> 
> But, you did bring one optimization opportunity to mind. We can remove some
> CheckHeapObject instructions for objects whose maps may no longer be known,
but
> they are still known to be heap objects.

Hi Ben, 
The pattern of CompareObjectEqAndBranch is as below for object "==" operation
  t13 CheckHeapObject t4
  t14 CheckMaps t4
  t15 CheckHeapObject t3
  t16 CheckMaps t3
  v17 CompareObjectEqAndBranch t16 t14

As Danno said, we don't need to check both. One check for either left or right
is enough. What I do is to match this pattern and remove one redundant check to
improve the performance. When CompareObjectEqAndBranch appears in the loop, I
hope to keep loop invariant object's map check and remove the other, so that the
remaining map check could be hoisted out of loop. That could bring the biggest
performance improvement. 

The patch set 2 is a refined implementation based on your comments. Could you
please have a look again?

Thanks
-Weiliang

[titzer, 2013-12-05 09:57:47]

On 2013/12/05 08:34:37, Weiliang wrote:
> On 2013/12/04 16:31:59, titzer wrote:
> > NOT LGTM.
> > 
> >
>
https://codereview.chromium.org/104843002/diff/1/src/hydrogen-check-eliminati...
> > File src/hydrogen-check-elimination.cc (right):
> > 
> >
>
https://codereview.chromium.org/104843002/diff/1/src/hydrogen-check-eliminati...
> > src/hydrogen-check-elimination.cc:292:
> > removed->DeleteAndReplaceWith(removed->ActualValue());
> > This transformation is completely incorrect. First, you haven't even checked
> > whether the two CheckMaps refer to the same object. Second, you haven't
> checked
> > the relationship between the CheckMaps either (does one entail another?).
> Third,
> > an object's map can change in between these instructions. Fourth, removing
the
> > check heap object in between is only legal if the CheckMaps refer to the the
> > same object. Fourth, I have no idea why you choose to match this pattern at
> the
> > CompareObjectEqAndBranch instruction.
> > 
> > But, you did bring one optimization opportunity to mind. We can remove some
> > CheckHeapObject instructions for objects whose maps may no longer be known,
> but
> > they are still known to be heap objects.
> 
> Hi Ben, 
> The pattern of CompareObjectEqAndBranch is as below for object "==" operation
>   t13 CheckHeapObject t4
>   t14 CheckMaps t4
>   t15 CheckHeapObject t3
>   t16 CheckMaps t3
>   v17 CompareObjectEqAndBranch t16 t14
> 

> As Danno said, we don't need to check both. One check for either left or right
> is enough. What I do is to match this pattern and remove one redundant check
to
> improve the performance. When CompareObjectEqAndBranch appears in the loop, I
> hope to keep loop invariant object's map check and remove the other, so that
the
> remaining map check could be hoisted out of loop. That could bring the biggest
> performance improvement. 
> 

Given our discussion here, I think the best place for this optimization is in
the graph builder, to avoid introducing the CheckMaps for the comparison. The
problem is that the local pattern matching that you are trying to apply here is
working on a graph that doesn't capture the _reason_ that the HCheckMaps have
been inserted. Since you are doing this after GVN, the chances of removing a
semantically meaningful check are greatly increased.

> The patch set 2 is a refined implementation based on your comments. Could you
> please have a look again?

I had a look, and upon further reflection I don't think this is going to work
here. Please do this optimization in the graph builder. You don't have the
dominance relation to determine which of the checks is better to leave out, but
you can maybe use the creation order. It's not guaranteed, but I am pretty sure
that the higher dominating instruction will have a lower ID (by accident) just
because of the order in which we process the AST nodes. The higher dominating
node is more likely to be pulled out of any loops.