From 61a5a413d7da0def33100a737fbaec3f57043cbd Mon Sep 17 00:00:00 2001 From: "yangguo@chromium.org" Date: Wed, 4 Jun 2014 11:52:17 +0000 Subject: [PATCH] Extend bounds check elimination to constant keys. R=jkummerow@chromium.org BUG=v8:3367 LOG=N Review URL: https://codereview.chromium.org/310333004 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@21672 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/hydrogen-bce.cc | 86 ++++++++++++--------- test/mjsunit/bounds-checks-elimination.js | 123 ++++++++++++++++++++++++++++++ 2 files changed, 175 insertions(+), 34 deletions(-) create mode 100644 test/mjsunit/bounds-checks-elimination.js diff --git a/src/hydrogen-bce.cc b/src/hydrogen-bce.cc index 65c2b14..c72a8c5 100644 --- a/src/hydrogen-bce.cc +++ b/src/hydrogen-bce.cc @@ -54,6 +54,9 @@ class BoundsCheckKey : public ZoneObject { 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 @@ class BoundsCheckBbData: public ZoneObject { 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); + } + } 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); } - } - 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); } } diff --git a/test/mjsunit/bounds-checks-elimination.js b/test/mjsunit/bounds-checks-elimination.js new file mode 100644 index 0000000..4ea7f17 --- /dev/null +++ b/test/mjsunit/bounds-checks-elimination.js @@ -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); -- 2.7.4