New array bounds check elimination pass (focused on induction variables and bitwise operations).

New array bounds check elimination pass (focused on induction variables and bitwise operations).

R=titzer@chromium.org

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

[titzer, 2013-06-24 14:03:29]

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1953: InductionVariableData*
InductionVariableData::New(HPhi* phi) {
This method really isn't a "new" or constructor method, since it can return
NULL. It needs a more descriptive name.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1977: HValue** context) {
Returning potentially four different values via pointer is getting a little
awkward here. I think a little data object, either created in the caller or the
callee, would be cleaner.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:2171: HValue* phi_operand) {
I think this code would be cleaner if all the match failures fall through to a
single case at the end which returns 0. The name "FindIncrement" or maybe
"MatchIncrement" might be better.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:2208: HValue*
InductionVariableData::DiscardOsrValue(HValue* v) {
"DiscardOsrValue" implies something is being deleted or removed. Maybe
"IgnoreOsrValue".

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:2232: bool
InductionVariableData::ValidateToken(Token::Value token) {
Validate the token how? This is not clear.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:3054: class InductionVariableData;
It seems like the only reason that all this code lives in this header file is so
that you can hang it directly off the HPhi instruction. I think we can avoid
that entanglement if we have a side table (essentially HashMap<Phi,
InductionVariableData> in the array bounds check elimination class (which should
be in its own file).

https://codereview.chromium.org/17568015/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/17568015/diff/1/src/hydrogen.cc#newcode4378
src/hydrogen.cc:4378: class InductionVariableBlocksTable BASE_EMBEDDED {
Highly recommend moving this class and related functionality into a new file
specifically for doing bounds check elimination.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/17568015/diff/1/src/hydrogen.h#newcode268
src/hydrogen.h:268: bool IsNestedInThisLoop(HBasicBlock* other_block) {
This method overloading is just for convenience; I think it's better just to
have one version and inline this one into its caller(s). Or, you could inline
the other version into this method and remove the current_loop() method.

https://codereview.chromium.org/17568015/diff/1/src/ia32/lithium-codegen-ia32.cc
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/17568015/diff/1/src/ia32/lithium-codegen-ia32...
src/ia32/lithium-codegen-ia32.cc:4382: void LCodeGen::ApplyCheckIf(Condition cc,
LBoundsCheck* check) {
Is this a remnant of debugging code? What does this do?

[Massi, 2013-07-01 13:10:48]

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1953: InductionVariableData*
InductionVariableData::New(HPhi* phi) {
On 2013/06/24 14:03:30, titzer wrote:
> This method really isn't a "new" or constructor method, since it can return
> NULL. It needs a more descriptive name.

Done (renamed as "ExaminePhi").

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:1977: HValue** context) {
On 2013/06/24 14:03:30, titzer wrote:
> Returning potentially four different values via pointer is getting a little
> awkward here. I think a little data object, either created in the caller or
the
> callee, would be cleaner.

Done.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:2171: HValue* phi_operand) {
On 2013/06/24 14:03:30, titzer wrote:
> I think this code would be cleaner if all the match failures fall through to a
> single case at the end which returns 0. The name "FindIncrement" or maybe
> "MatchIncrement" might be better.

Done.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:2208: HValue*
InductionVariableData::DiscardOsrValue(HValue* v) {
On 2013/06/24 14:03:30, titzer wrote:
> "DiscardOsrValue" implies something is being deleted or removed. Maybe
> "IgnoreOsrValue".

Done.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.cc#...
src/hydrogen-instructions.cc:2232: bool
InductionVariableData::ValidateToken(Token::Value token) {
On 2013/06/24 14:03:30, titzer wrote:
> Validate the token how? This is not clear.

Renamed, and added comment.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/17568015/diff/1/src/hydrogen-instructions.h#n...
src/hydrogen-instructions.h:3054: class InductionVariableData;
On 2013/06/24 14:03:30, titzer wrote:
> It seems like the only reason that all this code lives in this header file is
so
> that you can hang it directly off the HPhi instruction. I think we can avoid
> that entanglement if we have a side table (essentially HashMap<Phi,
> InductionVariableData> in the array bounds check elimination class (which
should
> be in its own file).

As discussed off line with danno, we can keep the reference in HPhi (having
induction variable info can will be useful elsewhere, for instance for
prefetching in indexed loads).

https://codereview.chromium.org/17568015/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/17568015/diff/1/src/hydrogen.cc#newcode4378
src/hydrogen.cc:4378: class InductionVariableBlocksTable BASE_EMBEDDED {
On 2013/06/24 14:03:30, titzer wrote:
> Highly recommend moving this class and related functionality into a new file
> specifically for doing bounds check elimination.

Done.

https://codereview.chromium.org/17568015/diff/1/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/17568015/diff/1/src/hydrogen.h#newcode268
src/hydrogen.h:268: bool IsNestedInThisLoop(HBasicBlock* other_block) {
On 2013/06/24 14:03:30, titzer wrote:
> This method overloading is just for convenience; I think it's better just to
> have one version and inline this one into its caller(s). Or, you could inline
> the other version into this method and remove the current_loop() method.

Removed and inlined.

[titzer, 2013-07-02 13:45:05]

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
File src/bounds-check-elimination.cc (right):

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:1: // Copyright 2013 the V8 project authors. All
rights reserved.
Please name this file with a "hydrogen-" prefix.
"hydrogen-bounds-check-elimination.cc" might be unwieldy, so perhaps
"hydrogen-bce.cc" will be OK.

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:35: class Element {
I find it hard to understand why this class serves both as a table of induction
variable information and also the state needed to iterate over the blocks in the
correct order. The dominator traversal here is unlike others, e.g. the one in
GVN, and I find that it obscures the underlying algorithm here. And there is
zero documentation.

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:39: HBasicBlock* block() { return block_; }
Why do you have accessors for all this state in the table? Why is any other
class using the internals?

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:107: Element()
At the very least the constructor should accept the block as a parameter.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:1986: while (true) {
I do not understand why this pattern matching is a loop. It can only iterate
from the ADD or SUB cases, both of which check that the masks are both 0--but
that seems redundant because all the other cases return. Then you have a
sentinel to indicate that you have matched an offset with an ADD or SUB in order
to force the OR case to abort.

Basically, I cannot figure which patterns this code matches or is supposed to
match. In most situations pattern matching is best done recursively and I would
advocate strongly to do so here. Also, a comment would help a lot--including a
grammar of which patterns would be matched, for example, would save the reader a
ton of work decoding this.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2093:
added_constant()->InsertBefore(constant_insertion_point);
Just move this code up into the if and save two lines. You will also then have a
redundant branch on added_index != NULL which you can then fold together.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2101: new_index->ClearAllSideEffects();
What side effects might the new index have that you are clearing? Some weird
JS-iness?

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2103: added_index_ = HBitwise::cast(new_index);
There are several assignments of private variables directly and then also getter
uses. Suggest just going with a direct private access for consistency.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2119: BitwiseDecompositionResult decomposition;
Probably better to initialize this struct at the declaration site (either with a
constructor or explicitly here), rather than in the decompose method.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2174: int32_t
InductionVariableData::ComputeIncrement(HPhi* phi,
Comments documenting this method.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2180: if (operation->left() == phi) {
You can further shorten these branches with &&.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen.h#newcode470
src/hydrogen.h:470: void CollectInductionVariableData(HBasicBlock* bb,
I think you can move two of these methods to live in the
InductionVariableBlocksTable class and thus remove them from HGraph.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen.h#newcode475
src/hydrogen.h:475: void NewJoke();
Was ist das?

[Massi, 2013-07-08 11:55:07]

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
File src/bounds-check-elimination.cc (right):

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:1: // Copyright 2013 the V8 project authors. All
rights reserved.
On 2013/07/02 13:45:06, titzer wrote:
> Please name this file with a "hydrogen-" prefix.
> "hydrogen-bounds-check-elimination.cc" might be unwieldy, so perhaps
> "hydrogen-bce.cc" will be OK.

hydrogen-bounds-check-removal.cc is just as long as other names...

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:35: class Element {
On 2013/07/02 13:45:06, titzer wrote:
> I find it hard to understand why this class serves both as a table of
induction
> variable information and also the state needed to iterate over the blocks in
the
> correct order. The dominator traversal here is unlike others, e.g. the one in
> GVN, and I find that it obscures the underlying algorithm here. And there is
> zero documentation.

Added comments.

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:39: HBasicBlock* block() { return block_; }
On 2013/07/02 13:45:06, titzer wrote:
> Why do you have accessors for all this state in the table? Why is any other
> class using the internals?

Removed unneeded accessors.

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:107: Element()
On 2013/07/02 13:45:06, titzer wrote:
> At the very least the constructor should accept the block as a parameter.

I don't think I can do it because this is the element of an array, so I need a
parameterless constructor.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:1986: while (true) {
On 2013/07/02 13:45:06, titzer wrote:
> I do not understand why this pattern matching is a loop. It can only iterate
> from the ADD or SUB cases, both of which check that the masks are both 0--but
> that seems redundant because all the other cases return. Then you have a
> sentinel to indicate that you have matched an offset with an ADD or SUB in
order
> to force the OR case to abort.
> 
> Basically, I cannot figure which patterns this code matches or is supposed to
> match. In most situations pattern matching is best done recursively and I
would
> advocate strongly to do so here. Also, a comment would help a lot--including a
> grammar of which patterns would be matched, for example, would save the reader
a
> ton of work decoding this.

Added a comment.
I still think that having the loop is simpler because to implement it
recursively I'd have to pass along "has_offset" and "current" as additional
arguments, which would mean having an "internal" recursive version of the method
or something similar.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2093:
added_constant()->InsertBefore(constant_insertion_point);
On 2013/07/02 13:45:06, titzer wrote:
> Just move this code up into the if and save two lines. You will also then have
a
> redundant branch on added_index != NULL which you can then fold together.

I tried that, with the ternary ?:, but added_index() and first_check_in_block()
have different types, therefore writing the ternary expression would have
required casts... I just did not find the expression with those casts readable
at all :-(
But yes, I can invoke "InsertBefore" in each if branch :-)

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2101: new_index->ClearAllSideEffects();
On 2013/07/02 13:45:06, titzer wrote:
> What side effects might the new index have that you are clearing? Some weird
> JS-iness?

IIRC calling "toNumber()", which in our case is guaranteed not to happen.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2103: added_index_ = HBitwise::cast(new_index);
On 2013/07/02 13:45:06, titzer wrote:
> There are several assignments of private variables directly and then also
getter
> uses. Suggest just going with a direct private access for consistency.

The logic was to use the private variable for writing and the getter for
reading, I added a setter for writing.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2119: BitwiseDecompositionResult decomposition;
On 2013/07/02 13:45:06, titzer wrote:
> Probably better to initialize this struct at the declaration site (either with
a
> constructor or explicitly here), rather than in the decompose method.

Added parameterless constructor, even if I still think that it is
InductionVariableData::DecomposeBitwise that produces the result therefore it
should be the one with the responsibility to initialize it.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2174: int32_t
InductionVariableData::ComputeIncrement(HPhi* phi,
On 2013/07/02 13:45:06, titzer wrote:
> Comments documenting this method.

Done.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen-instructions....
src/hydrogen-instructions.cc:2180: if (operation->left() == phi) {
On 2013/07/02 13:45:06, titzer wrote:
> You can further shorten these branches with &&.

Done.

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/17568015/diff/8001/src/hydrogen.h#newcode475
src/hydrogen.h:475: void NewJoke();
On 2013/07/02 13:45:06, titzer wrote:
> Was ist das?

Debugging leftover :-)

[titzer, 2013-07-10 16:34:18]

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
File src/bounds-check-elimination.cc (right):

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:1: // Copyright 2013 the V8 project authors. All
rights reserved.
On 2013/07/08 11:55:07, Massi wrote:
> On 2013/07/02 13:45:06, titzer wrote:
> > Please name this file with a "hydrogen-" prefix.
> > "hydrogen-bounds-check-elimination.cc" might be unwieldy, so perhaps
> > "hydrogen-bce.cc" will be OK.
> 
> hydrogen-bounds-check-removal.cc is just as long as other names...

Ok.

https://codereview.chromium.org/17568015/diff/8001/src/bounds-check-eliminati...
src/bounds-check-elimination.cc:265: ZoneList<Element> elements_;
I think you could get away with a plain-old C array for these elements, since it
is only allocated once and never grows.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-bounds-check...
File src/hydrogen-bounds-check-removal.cc (right):

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:101: */
It is still not clear to me what order the code visits the blocks, and how
exactly that is accomplished. Will need in-person discussion for this.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:180: &failure, unsafe);
It might actually be clearer to inline this PerformStep method and then refactor
its pieces into different configurations.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:293: void
CollectInductionVariableData(HBasicBlock* bb);
It's OK IMO to go ahead and pull up these other methods into the class
definition.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:1986: result->base = value;
Thanks for the comment; now that I understand the patterns you would like to
match, I don't think you even need a recursive method. You can first just try to
match the outer |/& operation, and if it succeeds, then try to match the inner
+/- on the non-constant side, and if it fails, try to match the +/- on the whole
thing. It would be far more clear than a loop that does not loop.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2241: bool
InductionVariableData::TokenCanRepresentLoopGuard(Token::Value token) {
With the name change I see now more clearly what you meant. I actually think you
want to compute whether a given {InductionVariable, Token, limit} is false
leading out of a loop, since that is what is interesting below?

In other words, I am not sure if breaking this operation out into its own method
is worthwhile.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2256: HBasicBlock* out_branch) {
This is kind of a strange name for this method. I think it should be inlined
(with a comment) into the second of the two methods which I suggest making the
below method into.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2269: HInstruction* end = predecessor->last();
This method could benefit from being split up into one that matches the
branching pattern from which we derive information (namely the given block is
entered from a predecessor that has a branch on an induction variable) and a
method that consumes that branching pattern and updates either the induction
variable data or the additional limit.

You could have a little datastructure that represents basically the triple

{InductionVariableData induction_variable, Token token, Instruction limit).

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2288: if (is_else_branch) {
Please just negate the token above, and don't use an intermediate is_else_branch
boolean variable.

[Massi, 2013-07-11 11:15:22]

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-bounds-check...
File src/hydrogen-bounds-check-removal.cc (right):

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:101: */
On 2013/07/10 16:34:18, titzer wrote:
> It is still not clear to me what order the code visits the blocks, and how
> exactly that is accomplished. Will need in-person discussion for this.

Done.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:180: &failure, unsafe);
On 2013/07/10 16:34:18, titzer wrote:
> It might actually be clearer to inline this PerformStep method and then
refactor
> its pieces into different configurations.

Done.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:293: void
CollectInductionVariableData(HBasicBlock* bb);
On 2013/07/10 16:34:18, titzer wrote:
> It's OK IMO to go ahead and pull up these other methods into the class
> definition.

Done.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:1986: result->base = value;
On 2013/07/10 16:34:18, titzer wrote:
> Thanks for the comment; now that I understand the patterns you would like to
> match, I don't think you even need a recursive method. You can first just try
to
> match the outer |/& operation, and if it succeeds, then try to match the inner
> +/- on the non-constant side, and if it fails, try to match the +/- on the
whole
> thing. It would be far more clear than a loop that does not loop.

Done.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2241: bool
InductionVariableData::TokenCanRepresentLoopGuard(Token::Value token) {
On 2013/07/10 16:34:18, titzer wrote:
> With the name change I see now more clearly what you meant. I actually think
you
> want to compute whether a given {InductionVariable, Token, limit} is false
> leading out of a loop, since that is what is interesting below?
> 
> In other words, I am not sure if breaking this operation out into its own
method
> is worthwhile.

Inlined it into CheckIfBranchIsLoopGuard.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2256: HBasicBlock* out_branch) {
On 2013/07/10 16:34:18, titzer wrote:
> This is kind of a strange name for this method. I think it should be inlined
> (with a comment) into the second of the two methods which I suggest making the
> below method into.

After the off line discussion I ended up not inlining it (but it now contains
the code of CheckIfBranchIsLoopGuard).

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2269: HInstruction* end = predecessor->last();
On 2013/07/10 16:34:18, titzer wrote:
> This method could benefit from being split up into one that matches the
> branching pattern from which we derive information (namely the given block is
> entered from a predecessor that has a branch on an induction variable) and a
> method that consumes that branching pattern and updates either the induction
> variable data or the additional limit.
> 
> You could have a little datastructure that represents basically the triple
> 
> {InductionVariableData induction_variable, Token token, Instruction limit).
> 

Done.

https://codereview.chromium.org/17568015/diff/21001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2288: if (is_else_branch) {
On 2013/07/10 16:34:18, titzer wrote:
> Please just negate the token above, and don't use an intermediate
is_else_branch
> boolean variable.

Done.

[titzer, 2013-07-11 16:39:10]

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:1979: * (base - constant_offset) &
constant_and_mask
Why do we not also want to match "base + constant_offset" and "base -
constant_offset"?

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2003: if (bitwise->right()->IsInteger32Constant())
{
If you get the mask first, before matching AND or OR, then you don't need
mask_location, and probably also don't need allow_offset.

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2239: HBasicBlock* current_branch,
If I understand this code correctly now, this is the "true" target of a
hypothetical branch comparing the induction variable with "token" against some
limit. If that's true, I suggest "true_target" and "false_target" for the basic
block parameter names.

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3201: void
UpdateAdditionalLimit(InductionVariableLimitUpdate* update) {
Also put this into the .cc file please.

And why are we swapping and not copying?

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3230: bool lower_limit_is_non_negative_constant() {
hacker_style is supposedly only for accessors.

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3244: int32_t ComputeUpperLimit(int32_t and_mask,
int32_t or_mask) {
Put this one in the .cc file.

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen.cc#newcode4453
src/hydrogen.cc:4453: if (FLAG_abcd_ivars) {
Indentation

https://codereview.chromium.org/17568015/diff/31001/src/ia32/lithium-codegen-...
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/17568015/diff/31001/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.cc:4382: void LCodeGen::ApplyCheckIf(Condition cc,
LBoundsCheck* check) {
I guess you were just using this for debugging on ia32, since the other
platforms don't have something similar, so perhaps you can take this out now.

[Massi, 2013-07-12 08:20:24]

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:1979: * (base - constant_offset) &
constant_and_mask
On 2013/07/11 16:39:10, titzer wrote:
> Why do we not also want to match "base + constant_offset" and "base -
> constant_offset"?

Because collapsing those patterns is the job of the other array bounds
elimination pass.
Of course we could also handle hoisting of "base + constant" patterns but I did
not think that the added complexity was worth it (at that point we would end up
with the "all encompassing" idef based approach).

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2003: if (bitwise->right()->IsInteger32Constant())
{
On 2013/07/11 16:39:10, titzer wrote:
> If you get the mask first, before matching AND or OR, then you don't need
> mask_location, and probably also don't need allow_offset.

True about mask, but we still want to allow those offsets in the "bitwise and"
case.
To be fair we could allow *anything* in the bitwise and case (the constant
operand is an upper limit anyway) but I did not want to go that far.

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3201: void
UpdateAdditionalLimit(InductionVariableLimitUpdate* update) {
On 2013/07/11 16:39:10, titzer wrote:
> Also put this into the .cc file please.
> 
> And why are we swapping and not copying?

Done.
We are swapping because of the need for backtracking, see added comment.

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3230: bool lower_limit_is_non_negative_constant() {
On 2013/07/11 16:39:10, titzer wrote:
> hacker_style is supposedly only for accessors.

Done.

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen-instructions...
src/hydrogen-instructions.h:3244: int32_t ComputeUpperLimit(int32_t and_mask,
int32_t or_mask) {
On 2013/07/11 16:39:10, titzer wrote:
> Put this one in the .cc file.

Done.

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/17568015/diff/31001/src/hydrogen.cc#newcode4453
src/hydrogen.cc:4453: if (FLAG_abcd_ivars) {
On 2013/07/11 16:39:10, titzer wrote:
> Indentation

Done.

https://codereview.chromium.org/17568015/diff/31001/src/ia32/lithium-codegen-...
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/17568015/diff/31001/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.cc:4382: void LCodeGen::ApplyCheckIf(Condition cc,
LBoundsCheck* check) {
On 2013/07/11 16:39:10, titzer wrote:
> I guess you were just using this for debugging on ia32, since the other
> platforms don't have something similar, so perhaps you can take this out now.

This needs to stay because it is a sort of "safety net": with this, whenever we
run tests with --debug_code we also fully check the bounds check elimination.
As long as we test on ia32 IMHO it is not really necessary to port this to other
archs (but of course we could do it).

[titzer, 2013-07-18 12:22:57]

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
File src/hydrogen-bounds-check-removal.cc (right):

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:48: * InitializeLoop() sets up the table
for a given loop.
These comments are probably better located on their respective methods.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:117: bool* unsafe) {
This is much more readable, good. I think we can do this iteratively (and more
cleanly) using an iterator. Essentially, the iterator would yield one block at a
time, and would have its own internal stack to keep track of the DFS. As we
discussed in person, I don't think that intertwining the state needed to
maintain the traversal within the InductionVariableBlocksTable is readable, and
I think the iterator is the solution.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:208: bool
LoopPathsAreCheckedIteratively(bool* unsafe) {
When you convert this method to use an iterator, please don't pass in a bool*
for unsafe, but instead you can return one of 3 values.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:309: bool failure =
!LoopPathsAreChecked(&unsafe);
If this method just returns a value, then you don't need this weird condition
and pointer.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:1979: * (base - constant_offset) &
constant_and_mask
I don't understand why we don't match (base + constant) as well.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2002: if (bitwise->right()->IsInteger32Constant())
{
As per previous comments, please don't use a pointer here, when you can change
the order of comparisons and get rid of it.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2251: if (result >= MAX_LIMIT) {
Can use a ternary here.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (left):

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.h:6611: 
Whitespace change

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.h:42: 
unnecessary whitespace change

https://codereview.chromium.org/17568015/diff/44001/src/ia32/lithium-codegen-...
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/17568015/diff/44001/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.cc:4382: void LCodeGen::ApplyCheckIf(Condition cc,
LBoundsCheck* check) {
If the debug code is valuable enough to have on ia32, then it's valuable enough
to have on all platforms. Please make all platforms the same (even though I
normally am against code duplication).

https://codereview.chromium.org/17568015/diff/44001/src/v8-counters.h
File src/v8-counters.h (right):

https://codereview.chromium.org/17568015/diff/44001/src/v8-counters.h#newcode241
src/v8-counters.h:241: SC(bounds_checks_covered, V8.BoundsChecksCovered)        
          \
I don't know what covered and induced are supposed to mean. Do you mean added
and eliminated?

[titzer, 2013-07-22 13:03:10]

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
File src/hydrogen-bounds-check-removal.cc (right):

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:101: if (!next->is_in_loop()) {
This code is now redundant with CheckLoopPaths(Block*).

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:163: enum PathCheckResult {
How about HOISTABLE, OPTIMISTICALLY_HOISTABLE, and NOT_HOISTABLE?

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:180: PathCheckResult CheckLoopPaths() {
CheckHoistability?

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:316: if (data->increment() <= 0) continue;
Haven't we already done a whole lot of work to deal with induction variables
that are counting down?

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:371: PathCheckResult
CheckLoopPaths(HBasicBlock* block) {
Much improved.

[Massi, 2013-07-23 07:57:50]

There are only two things on the todo list (for now):
- rewrite CheckHoistability in a non recursive way
- fix the counters for eliminated checks

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
File src/hydrogen-bounds-check-removal.cc (right):

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:48: * InitializeLoop() sets up the table
for a given loop.
On 2013/07/18 12:22:58, titzer wrote:
> These comments are probably better located on their respective methods.

Done.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:117: bool* unsafe) {
On 2013/07/18 12:22:58, titzer wrote:
> This is much more readable, good. I think we can do this iteratively (and more
> cleanly) using an iterator. Essentially, the iterator would yield one block at
a
> time, and would have its own internal stack to keep track of the DFS. As we
> discussed in person, I don't think that intertwining the state needed to
> maintain the traversal within the InductionVariableBlocksTable is readable,
and
> I think the iterator is the solution.

We are going towards a solution where we iterate the dominator tree (or anyway
test dominance relations).

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:208: bool
LoopPathsAreCheckedIteratively(bool* unsafe) {
On 2013/07/18 12:22:58, titzer wrote:
> When you convert this method to use an iterator, please don't pass in a bool*
> for unsafe, but instead you can return one of 3 values.

Done.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:309: bool failure =
!LoopPathsAreChecked(&unsafe);
On 2013/07/18 12:22:58, titzer wrote:
> If this method just returns a value, then you don't need this weird condition
> and pointer.

Done.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions.cc
File src/hydrogen-instructions.cc (right):

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:1979: * (base - constant_offset) &
constant_and_mask
On 2013/07/18 12:22:58, titzer wrote:
> I don't understand why we don't match (base + constant) as well.

Because the old bounds check elimination phase already handles "collapsing"
them, and handling them here (hoisting them) would complicate the code further.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2002: if (bitwise->right()->IsInteger32Constant())
{
On 2013/07/18 12:22:58, titzer wrote:
> As per previous comments, please don't use a pointer here, when you can change
> the order of comparisons and get rid of it.

Done.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.cc:2251: if (result >= MAX_LIMIT) {
On 2013/07/18 12:22:58, titzer wrote:
> Can use a ternary here.

Done.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (left):

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.h:6611: 
On 2013/07/18 12:22:58, titzer wrote:
> Whitespace change

Done.

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions.h
File src/hydrogen-instructions.h (right):

https://codereview.chromium.org/17568015/diff/44001/src/hydrogen-instructions...
src/hydrogen-instructions.h:42: 
On 2013/07/18 12:22:58, titzer wrote:
> unnecessary whitespace change

Done.

https://codereview.chromium.org/17568015/diff/44001/src/ia32/lithium-codegen-...
File src/ia32/lithium-codegen-ia32.cc (right):

https://codereview.chromium.org/17568015/diff/44001/src/ia32/lithium-codegen-...
src/ia32/lithium-codegen-ia32.cc:4382: void LCodeGen::ApplyCheckIf(Condition cc,
LBoundsCheck* check) {
On 2013/07/18 12:22:58, titzer wrote:
> If the debug code is valuable enough to have on ia32, then it's valuable
enough
> to have on all platforms. Please make all platforms the same (even though I
> normally am against code duplication).

Done.

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
File src/hydrogen-bounds-check-removal.cc (right):

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:101: if (!next->is_in_loop()) {
On 2013/07/22 13:03:10, titzer wrote:
> This code is now redundant with CheckLoopPaths(Block*).

Done.

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:163: enum PathCheckResult {
On 2013/07/22 13:03:10, titzer wrote:
> How about HOISTABLE, OPTIMISTICALLY_HOISTABLE, and NOT_HOISTABLE?

Done.

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:180: PathCheckResult CheckLoopPaths() {
On 2013/07/22 13:03:10, titzer wrote:
> CheckHoistability?

Done.

https://codereview.chromium.org/17568015/diff/55001/src/hydrogen-bounds-check...
src/hydrogen-bounds-check-removal.cc:316: if (data->increment() <= 0) continue;
On 2013/07/22 13:03:10, titzer wrote:
> Haven't we already done a whole lot of work to deal with induction variables
> that are counting down?

It depends what we call "a whole lot of work".
What we do is handle both HAdd and HSub when we detect the induction variable,
and flip the sign of the increment in case of HSub.

And note the "for now" in the comment: I just did not want to complicate the
code further, for now.
Handling decreasing induction would need dealing with a single "base upper
bound" (the induction base), and then trying to see if the lower bound is >= 0.

The complication is that further branches would influence the lower bound but
bit masks would still change the upper bound.

This is slightly different from what we do here (test that the single lower
bound is a non negative constant and deal with the potentially different upper
bounds, both because of masks and additional branches), and for now I decided
not to write that code.

[Massi, 2013-07-23 11:53:23]

Addressed all current comments.

[titzer, 2013-07-24 09:33:17]

LGTM

https://codereview.chromium.org/17568015/diff/67001/src/flag-definitions.h
File src/flag-definitions.h (right):

https://codereview.chromium.org/17568015/diff/67001/src/flag-definitions.h#ne...
src/flag-definitions.h:257: DEFINE_bool(abcd_ivars, true, "eliminate bounds
checks on induction variables")
Probably should get it in disabled by default, first.

[Massi, 2013-07-25 06:37:36]

Committed patchset #14 manually as r15866 (presubmit successful).