Revision: 9847
Author: [email protected]
Date: Mon Oct 31 07:15:10 2011
Log: Add and use ElementsKind side effect
Also partition side effects into observable and not observable, with only
observable requiring Simulates and non-observable changes able to
participate in GVN and code hoisting.
BUG=none
TEST=none
Review URL: http://codereview.chromium.org/8380017
http://code.google.com/p/v8/source/detail?r=9847
Added:
/branches/bleeding_edge/test/mjsunit/elements-kind-depends.js
Modified:
/branches/bleeding_edge/src/arm/lithium-arm.cc
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/src/ia32/lithium-ia32.cc
/branches/bleeding_edge/src/x64/lithium-x64.cc
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/elements-kind-depends.js Mon Oct
31 07:15:10 2011
@@ -0,0 +1,74 @@
+// Copyright 2011 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 --smi-only-arrays
+
+function burn() {
+ var a = new Array(3);
+ a[0] = 10;
+ a[1] = 15.5;
+ a[2] = 20;
+ return a;
+}
+
+function check(a) {
+ assertEquals(10, a[0]);
+ assertEquals(15.5, a[1]);
+ assertEquals(20, a[2]);
+}
+
+var b;
+for (var i = 0; i < 3; ++i) {
+ b = burn();
+ check(b); // all OK
+}
+%OptimizeFunctionOnNextCall(burn);
+b = burn();
+check(b); // fails
+
+
+function loop_test(x) {
+ for (i=0;i<3;i++) {
+ x[i] = (i+1) * 0.5;
+ }
+}
+
+function check2(b) {
+ assertEquals(0.5, b[0]);
+ assertEquals(1.0, b[1]);
+ assertEquals(1.5, b[2]);
+}
+
+for (var i = 0; i < 3; ++i) {
+ b = [0,1,2];
+ loop_test(b);
+ check2(b);
+}
+%OptimizeFunctionOnNextCall(loop_test);
+b = [0,1,2];
+loop_test(b);
+check2(b);
=======================================
--- /branches/bleeding_edge/src/arm/lithium-arm.cc Mon Oct 31 06:06:26 2011
+++ /branches/bleeding_edge/src/arm/lithium-arm.cc Mon Oct 31 07:15:10 2011
@@ -750,7 +750,7 @@
instr->MarkAsCall();
instr = AssignPointerMap(instr);
- if (hinstr->HasSideEffects()) {
+ if (hinstr->HasObservableSideEffects()) {
ASSERT(hinstr->next()->IsSimulate());
HSimulate* sim = HSimulate::cast(hinstr->next());
instr = SetInstructionPendingDeoptimizationEnvironment(
@@ -762,7 +762,8 @@
// Thus we still need to attach environment to this call even if
// call sequence can not deoptimize eagerly.
bool needs_environment =
- (can_deoptimize == CAN_DEOPTIMIZE_EAGERLY) |
| !hinstr->HasSideEffects();
+ (can_deoptimize == CAN_DEOPTIMIZE_EAGERLY) ||
+ !hinstr->HasObservableSideEffects();
if (needs_environment && !instr->HasEnvironment()) {
instr = AssignEnvironment(instr);
}
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Mon Oct 31
06:06:26 2011
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Mon Oct 31
07:15:10 2011
@@ -564,7 +564,7 @@
// followed by a simulate instruction, we need to insert after the
// simulate instruction instead.
HInstruction* next = previous->next_;
- if (previous->HasSideEffects() && next != NULL) {
+ if (previous->HasObservableSideEffects() && next != NULL) {
ASSERT(next->IsSimulate());
previous = next;
next = previous->next_;
@@ -604,7 +604,7 @@
// Verify that instructions that may have side-effects are followed
// by a simulate instruction.
- if (HasSideEffects() && !IsOsrEntry()) {
+ if (HasObservableSideEffects() && !IsOsrEntry()) {
ASSERT(next()->IsSimulate());
}
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Mon Oct 31 06:06:26
2011
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Mon Oct 31 07:15:10
2011
@@ -181,6 +181,7 @@
V(Calls) \
V(InobjectFields) \
V(BackingStoreFields) \
+ V(ElementsKind) \
V(ArrayElements) \
V(DoubleArrayElements) \
V(SpecializedArrayElements) \
@@ -619,8 +620,14 @@
void SetAllSideEffects() { flags_ |= AllSideEffects(); }
void ClearAllSideEffects() { flags_ &= ~AllSideEffects(); }
bool HasSideEffects() const { return (flags_ & AllSideEffects()) != 0; }
+ bool HasObservableSideEffects() const {
+ return (flags_ & ObservableSideEffects()) != 0;
+ }
int ChangesFlags() const { return flags_ & ChangesFlagsMask(); }
+ int ObservableChangesFlags() const {
+ return flags_ & ChangesFlagsMask() & ObservableSideEffects();
+ }
Range* range() const { return range_; }
bool HasRange() const { return range_ != NULL; }
@@ -699,6 +706,12 @@
static int AllSideEffects() {
return ChangesFlagsMask() & ~(1 << kChangesOsrEntries);
}
+
+ // A flag mask of all side effects that can make observable changes in
+ // an executing program (i.e. are not safe to repeat, move or remove);
+ static int ObservableSideEffects() {
+ return ChangesFlagsMask() & ~(1 << kChangesElementsKind);
+ }
// Remove the matching use from the use list if present. Returns the
// removed list node or NULL.
@@ -1737,7 +1750,7 @@
explicit HElementsKind(HValue* value) : HUnaryOperation(value) {
set_representation(Representation::Integer32());
SetFlag(kUseGVN);
- SetFlag(kDependsOnMaps);
+ SetFlag(kDependsOnElementsKind);
}
virtual Representation RequiredInputRepresentation(int index) {
@@ -1864,6 +1877,7 @@
set_representation(Representation::Tagged());
SetFlag(kUseGVN);
SetFlag(kDependsOnMaps);
+ SetFlag(kDependsOnElementsKind);
}
virtual Representation RequiredInputRepresentation(int index) {
@@ -3886,7 +3900,7 @@
transitioned_map_(transitioned_map) {
SetOperandAt(0, object);
SetFlag(kUseGVN);
- SetFlag(kDependsOnMaps);
+ SetFlag(kChangesElementsKind);
set_representation(Representation::Tagged());
}
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Mon Oct 31 06:06:26 2011
+++ /branches/bleeding_edge/src/hydrogen.cc Mon Oct 31 07:15:10 2011
@@ -1346,6 +1346,7 @@
explicit HGlobalValueNumberer(HGraph* graph, CompilationInfo* info)
: graph_(graph),
info_(info),
+ removed_side_effects_(false),
block_side_effects_(graph->blocks()->length()),
loop_side_effects_(graph->blocks()->length()),
visited_on_paths_(graph->zone(), graph->blocks()->length()) {
@@ -1357,7 +1358,8 @@
ASSERT(!info_->isolate()->heap()->allow_allocation(true));
}
- void Analyze();
+ // Returns true if values with side effects are removed.
+ bool Analyze();
private:
int CollectSideEffectsOnPathsToDominatedBlock(HBasicBlock* dominator,
@@ -1377,6 +1379,7 @@
HGraph* graph_;
CompilationInfo* info_;
+ bool removed_side_effects_;
// A map of block IDs to their side effects.
ZoneList<int> block_side_effects_;
@@ -1390,13 +1393,14 @@
};
-void HGlobalValueNumberer::Analyze() {
+bool HGlobalValueNumberer::Analyze() {
ComputeBlockSideEffects();
if (FLAG_loop_invariant_code_motion) {
LoopInvariantCodeMotion();
}
HValueMap* map = new(zone()) HValueMap();
AnalyzeBlock(graph_->entry_block(), map);
+ return removed_side_effects_;
}
@@ -1530,11 +1534,12 @@
HInstruction* next = instr->next();
int flags = instr->ChangesFlags();
if (flags != 0) {
- ASSERT(!instr->CheckFlag(HValue::kUseGVN));
// Clear all instructions in the map that are affected by side
effects.
map->Kill(flags);
TraceGVN("Instruction %d kills\n", instr->id());
- } else if (instr->CheckFlag(HValue::kUseGVN)) {
+ }
+ if (instr->CheckFlag(HValue::kUseGVN)) {
+ ASSERT(!instr->HasObservableSideEffects());
HValue* other = map->Lookup(instr);
if (other != NULL) {
ASSERT(instr->Equals(other) && other->Equals(instr));
@@ -1543,6 +1548,7 @@
instr->Mnemonic(),
other->id(),
other->Mnemonic());
+ if (instr->HasSideEffects()) removed_side_effects_ = true;
instr->DeleteAndReplaceWith(other);
} else {
map->Add(instr);
@@ -2108,12 +2114,12 @@
void EffectContext::ReturnInstruction(HInstruction* instr, int ast_id) {
ASSERT(!instr->IsControlInstruction());
owner()->AddInstruction(instr);
- if (instr->HasSideEffects()) owner()->AddSimulate(ast_id);
+ if (instr->HasObservableSideEffects()) owner()->AddSimulate(ast_id);
}
void EffectContext::ReturnControl(HControlInstruction* instr, int ast_id) {
- ASSERT(!instr->HasSideEffects());
+ ASSERT(!instr->HasObservableSideEffects());
HBasicBlock* empty_true = owner()->graph()->CreateBasicBlock();
HBasicBlock* empty_false = owner()->graph()->CreateBasicBlock();
instr->SetSuccessorAt(0, empty_true);
@@ -2131,12 +2137,12 @@
}
owner()->AddInstruction(instr);
owner()->Push(instr);
- if (instr->HasSideEffects()) owner()->AddSimulate(ast_id);
+ if (instr->HasObservableSideEffects()) owner()->AddSimulate(ast_id);
}
void ValueContext::ReturnControl(HControlInstruction* instr, int ast_id) {
- ASSERT(!instr->HasSideEffects());
+ ASSERT(!instr->HasObservableSideEffects());
if (!arguments_allowed() && instr->CheckFlag(HValue::kIsArguments)) {
return owner()->Bailout("bad value context for arguments object
value");
}
@@ -2161,7 +2167,7 @@
builder->AddInstruction(instr);
// We expect a simulate after every expression with side effects, though
// this one isn't actually needed (and wouldn't work if it were
targeted).
- if (instr->HasSideEffects()) {
+ if (instr->HasObservableSideEffects()) {
builder->Push(instr);
builder->AddSimulate(ast_id);
builder->Pop();
@@ -2171,7 +2177,7 @@
void TestContext::ReturnControl(HControlInstruction* instr, int ast_id) {
- ASSERT(!instr->HasSideEffects());
+ ASSERT(!instr->HasObservableSideEffects());
HBasicBlock* empty_true = owner()->graph()->CreateBasicBlock();
HBasicBlock* empty_false = owner()->graph()->CreateBasicBlock();
instr->SetSuccessorAt(0, empty_true);
@@ -2373,7 +2379,13 @@
if (FLAG_use_gvn) {
HPhase phase("Global value numbering", graph());
HGlobalValueNumberer gvn(graph(), info());
- gvn.Analyze();
+ bool removed_side_effects = gvn.Analyze();
+ // Trigger a second analysis pass to further eliminate duplicate
values that
+ // could only be discovered by removing side-effect-generating
instructions
+ // during the first pass.
+ if (FLAG_smi_only_arrays && removed_side_effects) {
+ gvn.Analyze();
+ }
}
if (FLAG_use_range) {
@@ -3546,7 +3558,7 @@
// The HSimulate for the store should not see the stored value in
// effect contexts (it is not materialized at expr->id() in the
// unoptimized code).
- if (instr->HasSideEffects()) {
+ if (instr->HasObservableSideEffects()) {
if (ast_context()->IsEffect()) {
AddSimulate(expr->id());
} else {
@@ -3619,7 +3631,7 @@
Push(value);
instr->set_position(expr->position());
AddInstruction(instr);
- if (instr->HasSideEffects()) AddSimulate(expr->AssignmentId());
+ if (instr->HasObservableSideEffects()) AddSimulate(expr->AssignmentId());
return ast_context()->ReturnValue(Pop());
}
@@ -3640,7 +3652,7 @@
new(zone()) HStoreGlobalCell(value, cell,
lookup.GetPropertyDetails());
instr->set_position(position);
AddInstruction(instr);
- if (instr->HasSideEffects()) AddSimulate(ast_id);
+ if (instr->HasObservableSideEffects()) AddSimulate(ast_id);
} else {
HValue* context = environment()->LookupContext();
HGlobalObject* global_object = new(zone()) HGlobalObject(context);
@@ -3653,8 +3665,8 @@
function_strict_mode_flag());
instr->set_position(position);
AddInstruction(instr);
- ASSERT(instr->HasSideEffects());
- if (instr->HasSideEffects()) AddSimulate(ast_id);
+ ASSERT(instr->HasObservableSideEffects());
+ if (instr->HasObservableSideEffects()) AddSimulate(ast_id);
}
}
@@ -3711,7 +3723,9 @@
HStoreContextSlot* instr =
new(zone()) HStoreContextSlot(context, var->index(), Top());
AddInstruction(instr);
- if (instr->HasSideEffects()) AddSimulate(expr->AssignmentId());
+ if (instr->HasObservableSideEffects()) {
+ AddSimulate(expr->AssignmentId());
+ }
break;
}
@@ -3737,7 +3751,7 @@
load = BuildLoadNamedGeneric(obj, prop);
}
PushAndAdd(load);
- if (load->HasSideEffects()) AddSimulate(expr->CompoundLoadId());
+ if (load->HasObservableSideEffects())
AddSimulate(expr->CompoundLoadId());
CHECK_ALIVE(VisitForValue(expr->value()));
HValue* right = Pop();
@@ -3745,14 +3759,14 @@
HInstruction* instr = BuildBinaryOperation(operation, left, right);
PushAndAdd(instr);
- if (instr->HasSideEffects()) AddSimulate(operation->id());
+ if (instr->HasObservableSideEffects()) AddSimulate(operation->id());
HInstruction* store = BuildStoreNamed(obj, instr, prop);
AddInstruction(store);
// Drop the simulated receiver and value. Return the value.
Drop(2);
Push(instr);
- if (store->HasSideEffects()) AddSimulate(expr->AssignmentId());
+ if (store->HasObservableSideEffects())
AddSimulate(expr->AssignmentId());
return ast_context()->ReturnValue(Pop());
} else {
@@ -3777,7 +3791,7 @@
HInstruction* instr = BuildBinaryOperation(operation, left, right);
PushAndAdd(instr);
- if (instr->HasSideEffects()) AddSimulate(operation->id());
+ if (instr->HasObservableSideEffects()) AddSimulate(operation->id());
expr->RecordTypeFeedback(oracle());
HandleKeyedElementAccess(obj, key, instr, expr, expr->AssignmentId(),
@@ -3875,7 +3889,9 @@
HStoreContextSlot* instr =
new(zone()) HStoreContextSlot(context, var->index(), Top());
AddInstruction(instr);
- if (instr->HasSideEffects()) AddSimulate(expr->AssignmentId());
+ if (instr->HasObservableSideEffects()) {
+ AddSimulate(expr->AssignmentId());
+ }
return ast_context()->ReturnValue(Pop());
}
@@ -4148,7 +4164,7 @@
if (num_untransitionable_maps == 1) {
HInstruction* instr = AddInstruction(BuildMonomorphicElementAccess(
object, key, val, untransitionable_map, is_store));
- *has_side_effects |= instr->HasSideEffects();
+ *has_side_effects |= instr->HasObservableSideEffects();
instr->set_position(position);
return is_store ? NULL : instr;
}
@@ -4235,7 +4251,7 @@
Push(access);
}
- *has_side_effects |= access->HasSideEffects();
+ *has_side_effects |= access->HasObservableSideEffects();
if (position != -1) {
access->set_position(position);
}
@@ -4256,7 +4272,7 @@
access = AddInstruction(BuildExternalArrayElementAccess(
external_elements, checked_key, val, elements_kind, is_store));
}
- *has_side_effects |= access->HasSideEffects();
+ *has_side_effects |= access->HasObservableSideEffects();
access->set_position(position);
if (!is_store) {
Push(access);
@@ -4301,7 +4317,7 @@
}
instr->set_position(position);
AddInstruction(instr);
- *has_side_effects = instr->HasSideEffects();
+ *has_side_effects = instr->HasObservableSideEffects();
return instr;
}
@@ -4900,7 +4916,7 @@
AddInstruction(square_root);
// MathPowHalf doesn't have side effects so there's no need for
// an environment simulation here.
- ASSERT(!square_root->HasSideEffects());
+ ASSERT(!square_root->HasObservableSideEffects());
result = new(zone()) HDiv(context, double_one, square_root);
} else if (exponent == 2.0) {
result = new(zone()) HMul(context, left, left);
@@ -5484,7 +5500,9 @@
HStoreContextSlot* instr =
new(zone()) HStoreContextSlot(context, var->index(), after);
AddInstruction(instr);
- if (instr->HasSideEffects()) AddSimulate(expr->AssignmentId());
+ if (instr->HasObservableSideEffects()) {
+ AddSimulate(expr->AssignmentId());
+ }
break;
}
@@ -5513,7 +5531,7 @@
load = BuildLoadNamedGeneric(obj, prop);
}
PushAndAdd(load);
- if (load->HasSideEffects()) AddSimulate(expr->CountId());
+ if (load->HasObservableSideEffects()) AddSimulate(expr->CountId());
after = BuildIncrement(returns_original_input, expr);
input = Pop();
@@ -5526,7 +5544,7 @@
// necessary.
environment()->SetExpressionStackAt(0, after);
if (returns_original_input) environment()->SetExpressionStackAt(1,
input);
- if (store->HasSideEffects()) AddSimulate(expr->AssignmentId());
+ if (store->HasObservableSideEffects())
AddSimulate(expr->AssignmentId());
} else {
// Keyed property.
@@ -6076,7 +6094,7 @@
HStoreContextSlot* store =
new HStoreContextSlot(context, var->index(), value);
AddInstruction(store);
- if (store->HasSideEffects()) AddSimulate(proxy->id());
+ if (store->HasObservableSideEffects()) AddSimulate(proxy->id());
} else {
environment()->Bind(var, value);
}
=======================================
--- /branches/bleeding_edge/src/ia32/lithium-ia32.cc Mon Oct 31 06:06:26
2011
+++ /branches/bleeding_edge/src/ia32/lithium-ia32.cc Mon Oct 31 07:15:10
2011
@@ -750,7 +750,7 @@
instr->MarkAsCall();
instr = AssignPointerMap(instr);
- if (hinstr->HasSideEffects()) {
+ if (hinstr->HasObservableSideEffects()) {
ASSERT(hinstr->next()->IsSimulate());
HSimulate* sim = HSimulate::cast(hinstr->next());
instr = SetInstructionPendingDeoptimizationEnvironment(
@@ -762,7 +762,8 @@
// Thus we still need to attach environment to this call even if
// call sequence can not deoptimize eagerly.
bool needs_environment =
- (can_deoptimize == CAN_DEOPTIMIZE_EAGERLY) |
| !hinstr->HasSideEffects();
+ (can_deoptimize == CAN_DEOPTIMIZE_EAGERLY) ||
+ !hinstr->HasObservableSideEffects();
if (needs_environment && !instr->HasEnvironment()) {
instr = AssignEnvironment(instr);
}
=======================================
--- /branches/bleeding_edge/src/x64/lithium-x64.cc Mon Oct 31 06:06:26 2011
+++ /branches/bleeding_edge/src/x64/lithium-x64.cc Mon Oct 31 07:15:10 2011
@@ -745,7 +745,7 @@
instr->MarkAsCall();
instr = AssignPointerMap(instr);
- if (hinstr->HasSideEffects()) {
+ if (hinstr->HasObservableSideEffects()) {
ASSERT(hinstr->next()->IsSimulate());
HSimulate* sim = HSimulate::cast(hinstr->next());
instr = SetInstructionPendingDeoptimizationEnvironment(
@@ -757,7 +757,8 @@
// Thus we still need to attach environment to this call even if
// call sequence can not deoptimize eagerly.
bool needs_environment =
- (can_deoptimize == CAN_DEOPTIMIZE_EAGERLY) |
| !hinstr->HasSideEffects();
+ (can_deoptimize == CAN_DEOPTIMIZE_EAGERLY) ||
+ !hinstr->HasObservableSideEffects();
if (needs_environment && !instr->HasEnvironment()) {
instr = AssignEnvironment(instr);
}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
