Merged r14169 into 3.17 branch.
Fix worst-case behavior of MergeRemovableSimulates().
BUG=v8:2612
R=jkummerow@chromium.org
Review URL: https://chromiumcodereview.appspot.com/14472003
git-svn-id: http://v8.googlecode.com/svn/branches/3.17@14418 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc
index aef227f..0f42e40 100644
--- a/src/hydrogen-instructions.cc
+++ b/src/hydrogen-instructions.cc
@@ -579,7 +579,7 @@
HValue* operand = OperandAt(i);
if (operand == NULL) continue;
HUseListNode* first = operand->use_list_;
- if (first != NULL && first->value() == this && first->index() == i) {
+ if (first != NULL && first->value()->CheckFlag(kIsDead)) {
operand->use_list_ = first->tail();
}
}
@@ -1749,20 +1749,25 @@
}
-void HSimulate::MergeInto(HSimulate* other) {
- for (int i = 0; i < values_.length(); ++i) {
- HValue* value = values_[i];
- if (HasAssignedIndexAt(i)) {
- other->AddAssignedValue(GetAssignedIndexAt(i), value);
- } else {
- if (other->pop_count_ > 0) {
- other->pop_count_--;
+void HSimulate::MergeWith(ZoneList<HSimulate*>* list) {
+ while (!list->is_empty()) {
+ HSimulate* from = list->RemoveLast();
+ ZoneList<HValue*>* from_values = &from->values_;
+ for (int i = 0; i < from_values->length(); ++i) {
+ if (from->HasAssignedIndexAt(i)) {
+ AddAssignedValue(from->GetAssignedIndexAt(i),
+ from_values->at(i));
} else {
- other->AddPushedValue(value);
+ if (pop_count_ > 0) {
+ pop_count_--;
+ } else {
+ AddPushedValue(from_values->at(i));
+ }
}
}
+ pop_count_ += from->pop_count_;
+ from->DeleteAndReplaceWith(NULL);
}
- other->pop_count_ += pop_count();
}
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index d2b3fc5..ea54621 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -1696,7 +1696,7 @@
return Representation::None();
}
- void MergeInto(HSimulate* other);
+ void MergeWith(ZoneList<HSimulate*>* list);
bool is_candidate_for_removal() { return removable_ == REMOVABLE_SIMULATE; }
DECLARE_CONCRETE_INSTRUCTION(Simulate)
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index 4d9bc9b..ef5de6b 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -2971,10 +2971,11 @@
void HGraph::MergeRemovableSimulates() {
+ ZoneList<HSimulate*> mergelist(2, zone());
for (int i = 0; i < blocks()->length(); ++i) {
HBasicBlock* block = blocks()->at(i);
- // Always reset the folding candidate at the start of a block.
- HSimulate* folding_candidate = NULL;
+ // Make sure the merge list is empty at the start of a block.
+ ASSERT(mergelist.is_empty());
// Nasty heuristic: Never remove the first simulate in a block. This
// just so happens to have a beneficial effect on register allocation.
bool first = true;
@@ -2985,33 +2986,38 @@
// in the outer environment.
// (Before each HEnterInlined, there is a non-foldable HSimulate
// anyway, so we get the barrier in the other direction for free.)
- if (folding_candidate != NULL) {
- folding_candidate->DeleteAndReplaceWith(NULL);
+ // Simply remove all accumulated simulates without merging. This
+ // is safe because simulates after instructions with side effects
+ // are never added to the merge list.
+ while (!mergelist.is_empty()) {
+ mergelist.RemoveLast()->DeleteAndReplaceWith(NULL);
}
- folding_candidate = NULL;
continue;
}
- // If we have an HSimulate and a candidate, perform the folding.
+ // Skip the non-simulates and the first simulate.
if (!current->IsSimulate()) continue;
if (first) {
first = false;
continue;
}
HSimulate* current_simulate = HSimulate::cast(current);
- if (folding_candidate != NULL) {
- folding_candidate->MergeInto(current_simulate);
- folding_candidate->DeleteAndReplaceWith(NULL);
- folding_candidate = NULL;
- }
- // Check if the current simulate is a candidate for folding.
- if (current_simulate->previous()->HasObservableSideEffects() &&
- !current_simulate->next()->IsSimulate()) {
+ if ((current_simulate->previous()->HasObservableSideEffects() &&
+ !current_simulate->next()->IsSimulate()) ||
+ !current_simulate->is_candidate_for_removal()) {
+ // This simulate is not suitable for folding.
+ // Fold the ones accumulated so far.
+ current_simulate->MergeWith(&mergelist);
continue;
+ } else {
+ // Accumulate this simulate for folding later on.
+ mergelist.Add(current_simulate, zone());
}
- if (!current_simulate->is_candidate_for_removal()) {
- continue;
- }
- folding_candidate = current_simulate;
+ }
+
+ if (!mergelist.is_empty()) {
+ // Merge the accumulated simulates at the end of the block.
+ HSimulate* last = mergelist.RemoveLast();
+ last->MergeWith(&mergelist);
}
}
}
diff --git a/src/version.cc b/src/version.cc
index f7fb1ee..f53a8a4 100644
--- a/src/version.cc
+++ b/src/version.cc
@@ -35,7 +35,7 @@
#define MAJOR_VERSION 3
#define MINOR_VERSION 17
#define BUILD_NUMBER 6
-#define PATCH_LEVEL 9
+#define PATCH_LEVEL 10
// Use 1 for candidates and 0 otherwise.
// (Boolean macro values are not supported by all preprocessors.)
#define IS_CANDIDATE_VERSION 0
diff --git a/test/mjsunit/mjsunit.status b/test/mjsunit/mjsunit.status
index 26c8359..2dd43d9 100644
--- a/test/mjsunit/mjsunit.status
+++ b/test/mjsunit/mjsunit.status
@@ -49,6 +49,7 @@
compiler/regress-funcaller: PASS, SKIP if $mode == debug
regress/regress-2318: PASS, SKIP if $mode == debug
regress/regress-create-exception: PASS, SKIP if $mode == debug
+regress/regress-2612: PASS, SKIP if $mode == debug
##############################################################################
# These use a built-in that's only present in debug mode. They take
diff --git a/test/mjsunit/regress/regress-2612.js b/test/mjsunit/regress/regress-2612.js
new file mode 100644
index 0000000..06db077
--- /dev/null
+++ b/test/mjsunit/regress/regress-2612.js
@@ -0,0 +1,76 @@
+// Copyright 2013 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Flags: --allow-natives-syntax --nodead-code-elimination
+// Flags: --nofold-constants --nouse-gvn
+
+// Create a function to get a long series of removable simulates.
+// f() {
+// var _0 = <random>, _1 = <random>, ... _1000 = <random>,
+// _1001 = <random var> + <random var>,
+// _1002 = <random var> + <random var>,
+// ...
+// _99999 = <random var> + <random var>,
+// x = 1;
+// return _0;
+// }
+
+var seed = 1;
+
+function rand() {
+ seed = seed * 171 % 1337 + 17;
+ return (seed % 1000) / 1000;
+}
+
+function randi(max) {
+ seed = seed * 131 % 1773 + 13;
+ return seed % max;
+}
+
+function varname(i) {
+ return "_" + i;
+}
+
+var source = "var ";
+
+for (var i = 0; i < 1000; i++) {
+ source += [varname(i), "=", rand(), ","].join("");
+}
+
+for (var i = 1000; i < 100000; i++) {
+ source += [varname(i), "=",
+ varname(randi(i)), "+",
+ varname(randi(i)), ","].join("");
+}
+
+source += "x=1; return _0;"
+var f = new Function(source);
+
+f();
+%OptimizeFunctionOnNextCall(f);
+f();
+
