[turbofan] Induction variable decrement bound analysis.

[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

Drive-by fix: Add lower bounds to lower_bounds
zone vector instead of upper_bounds.

BUG=

Committed: https://crrev.com/6e665b094e7cbb6187fb59e3eb135266fa4c2e96
Cr-Commit-Position: refs/heads/master@{#38772}

[Franzi, 2016-08-19 10:45:27]

The CQ bit was checked by franzih@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-19 10:45:29]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Franzi, 2016-08-19 10:49:36]

Description was changed from

==========
[turbofan] Induction variable decrement bound analysis.

This detects loops with integer decrements.

BUG=
==========

to

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

BUG=
==========

[Franzi, 2016-08-19 10:49:59]

The CQ bit was checked by franzih@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-19 10:50:09]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-19 11:13:01]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-19 11:13:01]

Dry run: This issue passed the CQ dry run.

[Franzi, 2016-08-19 11:25:21]

The CQ bit was checked by franzih@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-19 11:25:31]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Franzi, 2016-08-19 11:27:48]

Description was changed from

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

BUG=
==========

to

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

Drive-by fix: Add lower bounds to lower_bounds zone vector instead of
upper_bounds.

BUG=
==========

[Franzi, 2016-08-19 11:28:02]

Description was changed from

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

Drive-by fix: Add lower bounds to lower_bounds zone vector instead of
upper_bounds.

BUG=
==========

to

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

Drive-by fix: Add lower bounds to lower_bounds 
zone vector instead of upper_bounds.

BUG=
==========

[Franzi, 2016-08-19 11:36:25]

The CQ bit was checked by franzih@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-19 11:36:34]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Franzi, 2016-08-19 11:37:08]

franzih@chromium.org changed reviewers:
+ jarin@chromium.org

[Franzi, 2016-08-19 11:37:09]

Hi, 

I tried the induction variable bound analysis for subtraction. Can you have a
look please. 

Thanks, 

Franzi

[commit-bot: I haz the power, 2016-08-19 11:58:46]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-19 11:58:47]

Dry run: This issue passed the CQ dry run.

[Jarin, 2016-08-19 13:08:25]

https://codereview.chromium.org/2260153002/diff/60001/src/compiler/loop-varia...
File src/compiler/loop-variable-optimizer.cc (right):

https://codereview.chromium.org/2260153002/diff/60001/src/compiler/loop-varia...
src/compiler/loop-variable-optimizer.cc:191:
var->second->AddLowerBound(constraint->left(), constraint->kind());
Awesome, thanks for the fix! After a bit of thinking, I believe this is a bad
bug. For example, the program below does not terminate.

function f() {
  for (var i = 5; i < 10; i++) {
    if (i < 0) break;
    if (i === 7) return true;
  }
  return false;
}

f();
f();
%OptimizeFunctionOnNextCall(f);
print(f());

https://codereview.chromium.org/2260153002/diff/60001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/2260153002/diff/60001/src/compiler/typer.cc#n...
src/compiler/typer.cc:657: double max = V8_INFINITY;
Could not you just say here:

double increment_min;
double increment_max;
if (arithmeticType == InductionVariable::ArithmeticType::kAddition) {
  increment_min = increment_type->Min();
  increment_max = increment_type->Max();
} else {
  DCHECK(arithmeticType ==
         InductionVariable::ArithmeticType::kSubtraction);
  increment_min = -increment_type->Max();
  increment_max = -increment_type->Min();
}

And then just use these below rather than special casing for add/subtract below?

[Franzi, 2016-08-19 18:15:57]

The CQ bit was checked by franzih@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-19 18:16:11]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Franzi, 2016-08-19 18:24:29]

The CQ bit was checked by franzih@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-19 18:24:39]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Franzi, 2016-08-19 18:38:51]

Thanks for the feedback. I added some test cases. Did I miss any loop variation
we should have a test for? 

Thanks, 

Franzi

https://codereview.chromium.org/2260153002/diff/60001/src/compiler/loop-varia...
File src/compiler/loop-variable-optimizer.cc (right):

https://codereview.chromium.org/2260153002/diff/60001/src/compiler/loop-varia...
src/compiler/loop-variable-optimizer.cc:191:
var->second->AddLowerBound(constraint->left(), constraint->kind());
On 2016/08/19 13:08:25, Jarin wrote:
> Awesome, thanks for the fix! After a bit of thinking, I believe this is a bad
> bug. For example, the program below does not terminate.
> 
> function f() {
>   for (var i = 5; i < 10; i++) {
>     if (i < 0) break;
>     if (i === 7) return true;
>   }
>   return false;
> }
> 
> f();
> f();
> %OptimizeFunctionOnNextCall(f);
> print(f());

Done.

https://codereview.chromium.org/2260153002/diff/60001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/2260153002/diff/60001/src/compiler/typer.cc#n...
src/compiler/typer.cc:657: double max = V8_INFINITY;
On 2016/08/19 13:08:25, Jarin wrote:
> Could not you just say here:
> 
> double increment_min;
> double increment_max;
> if (arithmeticType == InductionVariable::ArithmeticType::kAddition) {
>   increment_min = increment_type->Min();
>   increment_max = increment_type->Max();
> } else {
>   DCHECK(arithmeticType ==
>          InductionVariable::ArithmeticType::kSubtraction);
>   increment_min = -increment_type->Max();
>   increment_max = -increment_type->Min();
> }
> 
> And then just use these below rather than special casing for add/subtract
below?

Done.

[Franzi, 2016-08-19 18:49:34]

The CQ bit was checked by franzih@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-19 18:49:36]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-19 19:11:05]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-19 19:11:06]

Dry run: This issue passed the CQ dry run.

[Jarin, 2016-08-22 07:27:20]

lgtm once the comments are addressed.

https://codereview.chromium.org/2260153002/diff/160001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/2260153002/diff/160001/src/compiler/typer.cc#...
src/compiler/typer.cc:673: arithmetic_type ==
InductionVariable::ArithmeticType::kSubtraction)) {
How about

if (increment_min >= 0) {

https://codereview.chromium.org/2260153002/diff/160001/src/compiler/typer.cc#...
src/compiler/typer.cc:699: // decreasing sequence (add negative values, or
subtract positive values)
} else if (increment_max <= 0) {

https://codereview.chromium.org/2260153002/diff/160001/test/mjsunit/induction...
File test/mjsunit/induction-variable-turbofan.js (right):

https://codereview.chromium.org/2260153002/diff/160001/test/mjsunit/induction...
test/mjsunit/induction-variable-turbofan.js:26: // OF THIS SOFTWARE, EVEN IF
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Nit: you can use a shorter copyright. E.g., see test/mjsunit/array-push2.js.

https://codereview.chromium.org/2260153002/diff/160001/test/mjsunit/induction...
test/mjsunit/induction-variable-turbofan.js:31: // the corret upper and lower
bounds.
Nit: corret -> correct.

https://codereview.chromium.org/2260153002/diff/160001/test/mjsunit/induction...
test/mjsunit/induction-variable-turbofan.js:43: if (i < 0) break;
Could we change the i < 0 branches to return false? (They should never trigger.)

[Franzi, 2016-08-22 08:56:28]

The CQ bit was checked by franzih@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-08-22 08:56:34]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Franzi, 2016-08-22 09:06:30]

https://codereview.chromium.org/2260153002/diff/160001/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/2260153002/diff/160001/src/compiler/typer.cc#...
src/compiler/typer.cc:673: arithmetic_type ==
InductionVariable::ArithmeticType::kSubtraction)) {
On 2016/08/22 07:27:20, Jarin wrote:
> How about
> 
> if (increment_min >= 0) {

Thanks!

https://codereview.chromium.org/2260153002/diff/160001/src/compiler/typer.cc#...
src/compiler/typer.cc:699: // decreasing sequence (add negative values, or
subtract positive values)
On 2016/08/22 07:27:19, Jarin wrote:
> } else if (increment_max <= 0) {

Done.

https://codereview.chromium.org/2260153002/diff/160001/test/mjsunit/induction...
File test/mjsunit/induction-variable-turbofan.js (right):

https://codereview.chromium.org/2260153002/diff/160001/test/mjsunit/induction...
test/mjsunit/induction-variable-turbofan.js:26: // OF THIS SOFTWARE, EVEN IF
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
On 2016/08/22 07:27:20, Jarin wrote:
> Nit: you can use a shorter copyright. E.g., see test/mjsunit/array-push2.js.

Done.

https://codereview.chromium.org/2260153002/diff/160001/test/mjsunit/induction...
test/mjsunit/induction-variable-turbofan.js:31: // the corret upper and lower
bounds.
On 2016/08/22 07:27:20, Jarin wrote:
> Nit: corret -> correct.

Done.

https://codereview.chromium.org/2260153002/diff/160001/test/mjsunit/induction...
test/mjsunit/induction-variable-turbofan.js:43: if (i < 0) break;
On 2016/08/22 07:27:20, Jarin wrote:
> Could we change the i < 0 branches to return false? (They should never
trigger.)

Done.

[Jarin, 2016-08-22 09:12:25]

Very nice! lgtm.

[commit-bot: I haz the power, 2016-08-22 09:19:15]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-08-22 09:19:16]

Dry run: This issue passed the CQ dry run.

[Franzi, 2016-08-22 09:19:38]

The CQ bit was checked by franzih@chromium.org

[commit-bot: I haz the power, 2016-08-22 09:19:46]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-08-22 09:21:25]

Description was changed from

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

Drive-by fix: Add lower bounds to lower_bounds 
zone vector instead of upper_bounds.

BUG=
==========

to

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

Drive-by fix: Add lower bounds to lower_bounds 
zone vector instead of upper_bounds.

BUG=
==========

[commit-bot: I haz the power, 2016-08-22 09:21:26]

Committed patchset #10 (id:180001)

[commit-bot: I haz the power, 2016-08-22 09:21:55]

Description was changed from

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

Drive-by fix: Add lower bounds to lower_bounds 
zone vector instead of upper_bounds.

BUG=
==========

to

==========
[turbofan] Induction variable bound analysis for decrements.

This detects loops with integer decrements.

Drive-by fix: Add lower bounds to lower_bounds
zone vector instead of upper_bounds.

BUG=

Committed: https://crrev.com/6e665b094e7cbb6187fb59e3eb135266fa4c2e96
Cr-Commit-Position: refs/heads/master@{#38772}
==========

[commit-bot: I haz the power, 2016-08-22 09:21:57]

Patchset 10 (id:??) landed as
https://crrev.com/6e665b094e7cbb6187fb59e3eb135266fa4c2e96
Cr-Commit-Position: refs/heads/master@{#38772}