Revision: 21672
Author: [email protected]
Date: Wed Jun 4 11:52:17 2014 UTC
Log: Extend bounds check elimination to constant keys.
[email protected]
BUG=v8:3367
LOG=N
Review URL: https://codereview.chromium.org/310333004
http://code.google.com/p/v8/source/detail?r=21672
Added:
/branches/bleeding_edge/test/mjsunit/bounds-checks-elimination.js
Modified:
/branches/bleeding_edge/src/hydrogen-bce.cc
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/bounds-checks-elimination.js Wed
Jun 4 11:52:17 2014 UTC
@@ -0,0 +1,123 @@
+// Copyright 2014 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Flags: --allow-natives-syntax --array-bounds-checks-elimination
+
+var a = []
+for (var i = 0; i < 9; i++) a[i] = i + 1;
+
+function test(f, arg1, arg2, expected) {
+ assertEquals(expected, f(arg1));
+ f(arg2);
+ %OptimizeFunctionOnNextCall(f);
+ assertEquals(expected, f(arg1));
+}
+
+test(function f0() {
+ return a[7] * a[6] * a[5] * a[4] * a[3] * a[2] * a[1] * a[0];
+}, 0, 1, 40320);
+
+test(function f1() {
+ return a[7] * a[6] * a[5] * a[4] * a[10] * a[2] * a[1] * a[0];
+}, 0, 1, NaN);
+
+test(function f2() {
+ return a[0] * a[1] * a[2] * a[3] * a[4] * a[5] * a[6] * a[7];
+}, 0, 1, 40320);
+
+test(function f3() {
+ return a[3] * a[0] * a[6] * a[7] * a[5] * a[1] * a[4] * a[2];
+}, 0, 1, 40320);
+
+test(function f4(b) {
+ return a[b+3] * a[0] * a[b+6] * a[7] * a[b+5] * a[1] * a[b+4] * a[2];
+}, 0, 1, 40320);
+
+test(function f5(b) {
+ return a[b+1] * a[0] * a[b+4] * a[7] * a[b+3] * a[1] * a[b+2] * a[2];
+}, 2, 3, 40320);
+
+test(function f6(b) {
+ var c;
+ if (b) c = a[3] * a[0] * a[6] * a[7];
+ return c * a[5] * a[1] * a[4] * a[2];
+}, true, false, 40320);
+
+test(function f7(b) {
+ var c = a[7];
+ if (b) c *= a[3] * a[0] * a[6];
+ return c * a[5] * a[1] * a[4] * a[2];
+}, true, false, 40320);
+
+test(function f8(b) {
+ var c = a[7];
+ if (b) c *= a[3] * a[0] * a[6];
+ return c * a[5] * a[10] * a[4] * a[2];
+}, true, false, NaN);
+
+test(function f9(b) {
+ var c = a[1];
+ if (b) {
+ c *= a[3] * a[0] * a[6];
+ } else {
+ c = a[6] * a[5] * a[4];
+ }
+ return c * a[5] * a[7] * a[4] * a[2];
+}, true, false, 40320);
+
+test(function fa(b) {
+ var c = a[1];
+ if (b) {
+ c = a[6] * a[b+5] * a[4];
+ } else {
+ c *= a[b+3] * a[0] * a[b+6];
+ }
+ return c * a[5] * a[b+7] * a[4] * a[2];
+}, 0, 1, 40320);
+
+test(function fb(b) {
+ var c = a[b-3];
+ if (b != 4) {
+ c = a[6] * a[b+1] * a[4];
+ } else {
+ c *= a[b-1] * a[0] * a[b+2];
+ }
+ return c * a[5] * a[b+3] * a[4] * a[b-2];
+}, 4, 3, 40320);
+
+test(function fc(b) {
+ var c = a[b-3];
+ if (b != 4) {
+ c = a[6] * a[b+1] * a[4];
+ } else {
+ c *= a[b-1] * a[0] * a[b+2];
+ }
+ return c * a[5] * a[b+3] * a[4] * a[b-2];
+}, 6, 3, NaN);
+
+test(function fd(b) {
+ var c = a[b-3];
+ if (b != 4) {
+ c = a[6] * a[b+1] * a[4];
+ } else {
+ c *= a[b-1] * a[0] * a[b+2];
+ }
+ return c * a[5] * a[b+3] * a[4] * a[b-2];
+}, 1, 4, NaN);
+
+test(function fe(b) {
+ var c = 1;
+ for (var i = 1; i < b-1; i++) {
+ c *= a[i-1] * a[i] * a[i+1];
+ }
+ return c;
+}, 8, 4, (40320 / 8 / 7) * (40320 / 8) * (40320 / 2));
+
+test(function ff(b) {
+ var c = 0;
+ for (var i = 0; i < b; i++) {
+ c += a[3] * a[0] * a[6] * a[7] * a[5] * a[1] * a[4] * a[2];
+ }
+ return c;
+}, 100, 4, 40320 * 100);
=======================================
--- /branches/bleeding_edge/src/hydrogen-bce.cc Tue Jun 3 08:12:43 2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-bce.cc Wed Jun 4 11:52:17 2014 UTC
@@ -54,6 +54,9 @@
constant = HConstant::cast(index->right());
index_base = index->left();
}
+ } else if (check->index()->IsConstant()) {
+ index_base = check->block()->graph()->GetConstant0();
+ constant = HConstant::cast(check->index());
}
if (constant != NULL && constant->HasInteger32Value()) {
@@ -222,41 +225,56 @@
void MoveIndexIfNecessary(HValue* index_raw,
HBoundsCheck* insert_before,
HInstruction* end_of_scan_range) {
- if (!index_raw->IsAdd() && !index_raw->IsSub()) {
- // index_raw can be HAdd(index_base, offset), HSub(index_base,
offset),
- // or index_base directly. In the latter case, no need to move
anything.
- return;
- }
- HArithmeticBinaryOperation* index =
- HArithmeticBinaryOperation::cast(index_raw);
- HValue* left_input = index->left();
- HValue* right_input = index->right();
- bool must_move_index = false;
- bool must_move_left_input = false;
- bool must_move_right_input = false;
- for (HInstruction* cursor = end_of_scan_range; cursor !=
insert_before;) {
- if (cursor == left_input) must_move_left_input = true;
- if (cursor == right_input) must_move_right_input = true;
- if (cursor == index) must_move_index = true;
- if (cursor->previous() == NULL) {
- cursor = cursor->block()->dominator()->end();
- } else {
- cursor = cursor->previous();
+ // index_raw can be HAdd(index_base, offset), HSub(index_base, offset),
+ // HConstant(offset) or index_base directly.
+ // In the latter case, no need to move anything.
+ if (index_raw->IsAdd() || index_raw->IsSub()) {
+ HArithmeticBinaryOperation* index =
+ HArithmeticBinaryOperation::cast(index_raw);
+ HValue* left_input = index->left();
+ HValue* right_input = index->right();
+ bool must_move_index = false;
+ bool must_move_left_input = false;
+ bool must_move_right_input = false;
+ for (HInstruction* cursor = end_of_scan_range; cursor !=
insert_before;) {
+ if (cursor == left_input) must_move_left_input = true;
+ if (cursor == right_input) must_move_right_input = true;
+ if (cursor == index) must_move_index = true;
+ if (cursor->previous() == NULL) {
+ cursor = cursor->block()->dominator()->end();
+ } else {
+ cursor = cursor->previous();
+ }
}
- }
- if (must_move_index) {
- index->Unlink();
- index->InsertBefore(insert_before);
- }
- // The BCE algorithm only selects mergeable bounds checks that share
- // the same "index_base", so we'll only ever have to move constants.
- if (must_move_left_input) {
- HConstant::cast(left_input)->Unlink();
- HConstant::cast(left_input)->InsertBefore(index);
- }
- if (must_move_right_input) {
- HConstant::cast(right_input)->Unlink();
- HConstant::cast(right_input)->InsertBefore(index);
+ if (must_move_index) {
+ index->Unlink();
+ index->InsertBefore(insert_before);
+ }
+ // The BCE algorithm only selects mergeable bounds checks that share
+ // the same "index_base", so we'll only ever have to move constants.
+ if (must_move_left_input) {
+ HConstant::cast(left_input)->Unlink();
+ HConstant::cast(left_input)->InsertBefore(index);
+ }
+ if (must_move_right_input) {
+ HConstant::cast(right_input)->Unlink();
+ HConstant::cast(right_input)->InsertBefore(index);
+ }
+ } else if (index_raw->IsConstant()) {
+ HConstant* index = HConstant::cast(index_raw);
+ bool must_move = false;
+ for (HInstruction* cursor = end_of_scan_range; cursor !=
insert_before;) {
+ if (cursor == index) must_move = true;
+ if (cursor->previous() == NULL) {
+ cursor = cursor->block()->dominator()->end();
+ } else {
+ cursor = cursor->previous();
+ }
+ }
+ if (must_move) {
+ index->Unlink();
+ index->InsertBefore(insert_before);
+ }
}
}
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
