Implement global check elimination using the HFlowEngine.

Implement global check elimination using the HFlowEngine.

BUG=
R=mvstanton@chromium.org

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

[mvstanton, 2013-10-31 11:16:13]

Hi Ben,
Looking pretty cool. Some comments around kChangesMaps and stat reporting.
--Michael

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

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:47: static const int kMaxTrackedObjects = 10;
Could this be public static inside the HCheckTable?

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:100: // If the instruction changes maps
uncontrollably, kill the whole town.
LOL! But a more sober comment for checking in, pleez.

Also, should these flags be checked for the instructions in the cases above too?

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:120: new_entry->object_ = old_entry->object_;
Can you explain here why you don't copy the checks as well as object_/maps_?

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:251: Kill(instr->object());
I don't like the combination of action (Kill()) and notice of unexpected state
(UNREACHABLE()). Better to assert that the situation is completely unexpected or
desired.

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:261: if (maps->size() == 1)
INC_STAT(compares_true_);
It looks like this function just serves to update reporting stats, at least
until the TODOs are addressed. Could you put stat collection behind a flag
(instead of implicit with DEBUG), and avoid going deep into code paths if stat
reporting is turned off? So this function would begin with

if (!FLAG_check_elimination_stats) return;
...
// TODO(...

(those TODOs point the way that soon an implementation will make it worthwhile
to come into this function).
The INC_STAT macro will check the flag.

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:333: cursor_ = size_;  // Move cursor to end.
Do performance concerns justify the complexity? How about just use the
tmp_entries every time as a serialization from cursor_ to the oldest entry?

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:398: int16_t cursor_;  // Must be <=
kMaxTrackedObjects
STATIC_ASSERT on sizeof cursor_ and size_ that they hold kMaxTrackedObjects,
since you are already reducing their size.

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:487: #if DEBUG
Same here with a defined flag instead of DEBUG. I guess the flag is already
FLAG_trace_check_elimination.

[titzer, 2013-11-26 13:18:13]

On 2013/10/31 11:16:13, mvstanton wrote:
> Hi Ben,
> Looking pretty cool. Some comments around kChangesMaps and stat reporting.
> --Michael
> 
>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> File src/hydrogen-check-elimination.cc (right):
> 
>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:47: static const int kMaxTrackedObjects =
10;
> Could this be public static inside the HCheckTable?
> 

Done.

>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:100: // If the instruction changes maps
> uncontrollably, kill the whole town.
> LOL! But a more sober comment for checking in, pleez.
> 

Done.

> Also, should these flags be checked for the instructions in the cases above
too?
> 
>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:120: new_entry->object_ =
old_entry->object_;
> Can you explain here why you don't copy the checks as well as object_/maps_?
> 

The idea is that if two checks are in the same block, and the second check is
more strict than the first check, then the first check should be narrowed to the
intersection of the two checks, and the second removed. The code doesn't
currently do this, but if we decide to, then we don't want to narrow the check
from a dominating block because it may be to aggressive.

>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:251: Kill(instr->object());
> I don't like the combination of action (Kill()) and notice of unexpected state
> (UNREACHABLE()). Better to assert that the situation is completely unexpected
or
> desired.
> 

Fixed.

>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:261: if (maps->size() == 1)
> INC_STAT(compares_true_);
> It looks like this function just serves to update reporting stats, at least
> until the TODOs are addressed. Could you put stat collection behind a flag
> (instead of implicit with DEBUG), and avoid going deep into code paths if stat
> reporting is turned off? So this function would begin with
> 
> if (!FLAG_check_elimination_stats) return;
> ...
> // TODO(...
> 

As it is with the macro, it's just a simple increment operation in DEBUG mode
and a no-op in production mode; I think that's probably cheaper and is certainly
simpler than a function call that checks a flag.

> (those TODOs point the way that soon an implementation will make it worthwhile
> to come into this function).
> The INC_STAT macro will check the flag.
> 
>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:333: cursor_ = size_;  // Move cursor to
end.
> Do performance concerns justify the complexity? How about just use the
> tmp_entries every time as a serialization from cursor_ to the oldest entry?

Kills and subsequent compactions happen a lot, so I think it's important not to
do the slow case each time.

>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:398: int16_t cursor_;  // Must be <=
> kMaxTrackedObjects
> STATIC_ASSERT on sizeof cursor_ and size_ that they hold kMaxTrackedObjects,
> since you are already reducing their size.
> 

Where should I put such an assertion? Constructor?

>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:487: #if DEBUG
> Same here with a defined flag instead of DEBUG. I guess the flag is already
> FLAG_trace_check_elimination.

I guess it's not a big savings, but this way the code and the counters aren't
even there in production mode.

[mvstanton, 2013-11-28 07:14:46]

With the static assert, then lgtm.

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

https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
src/hydrogen-check-elimination.cc:398: int16_t cursor_;  // Must be <=
kMaxTrackedObjects
On 2013/10/31 11:16:13, mvstanton wrote:
> STATIC_ASSERT on sizeof cursor_ and size_ that they hold kMaxTrackedObjects,
> since you are already reducing their size.

Ben asked: "where should I put this?"

I think right here next to the declaration, like
STATIC_ASSERT((1 << (sizeof(cursor_) * 8) >= kMaxTrackedObjects);

[titzer, 2013-11-28 13:29:30]

On 2013/11/28 07:14:46, mvstanton wrote:
> With the static assert, then lgtm.
> 
>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> File src/hydrogen-check-elimination.cc (right):
> 
>
https://codereview.chromium.org/46883009/diff/1/src/hydrogen-check-eliminatio...
> src/hydrogen-check-elimination.cc:398: int16_t cursor_;  // Must be <=
> kMaxTrackedObjects
> On 2013/10/31 11:16:13, mvstanton wrote:
> > STATIC_ASSERT on sizeof cursor_ and size_ that they hold kMaxTrackedObjects,
> > since you are already reducing their size.
> 
> Ben asked: "where should I put this?"
> 
> I think right here next to the declaration, like
> STATIC_ASSERT((1 << (sizeof(cursor_) * 8) >= kMaxTrackedObjects);

Done.

[mvstanton, 2013-11-28 13:49:29]

enjoy!
lgtm.

[titzer, 2013-11-28 15:51:01]

Committed patchset #4 manually as r18137 (presubmit successful).