Revision: 10731
Author: [email protected]
Date: Thu Feb 16 07:37:52 2012
Log: Relax TransitionElementsKind DependsOn/Changes dependencies.
Ensure that GVN eliminates all transitions that are dominated by an
equivalent transition, even if there is a DependsOn-changing instruction in
between.
[email protected]
Review URL: https://chromiumcodereview.appspot.com/9365057
http://code.google.com/p/v8/source/detail?r=10731
Modified:
/branches/bleeding_edge/src/hydrogen-instructions.h
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/test/mjsunit/elements-transition-hoisting.js
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Tue Feb 14 06:14:51
2012
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Thu Feb 16 07:37:52
2012
@@ -4191,17 +4191,8 @@
transitioned_map_(transitioned_map) {
SetOperandAt(0, object);
SetFlag(kUseGVN);
- SetGVNFlag(kDependsOnMaps);
SetGVNFlag(kChangesElementsKind);
- if (original_map->has_fast_double_elements()) {
- SetGVNFlag(kChangesElementsPointer);
- SetGVNFlag(kDependsOnElementsPointer);
- SetGVNFlag(kDependsOnDoubleArrayElements);
- } else if (transitioned_map->has_fast_double_elements()) {
- SetGVNFlag(kChangesElementsPointer);
- SetGVNFlag(kDependsOnElementsPointer);
- SetGVNFlag(kDependsOnArrayElements);
- }
+ SetGVNFlag(kChangesElementsPointer);
set_representation(Representation::Tagged());
}
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Tue Feb 14 06:40:58 2012
+++ /branches/bleeding_edge/src/hydrogen.cc Thu Feb 16 07:37:52 2012
@@ -1431,7 +1431,8 @@
void ProcessLoopBlock(HBasicBlock* block,
HBasicBlock* before_loop,
GVNFlagSet loop_kills,
- GVNFlagSet* accumulated_first_time_depends);
+ GVNFlagSet* accumulated_first_time_depends,
+ GVNFlagSet* accumulated_first_time_changes);
bool AllowCodeMotion();
bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
@@ -1512,10 +1513,12 @@
side_effects.ToIntegral());
GVNFlagSet accumulated_first_time_depends;
+ GVNFlagSet accumulated_first_time_changes;
HBasicBlock* last = block->loop_information()->GetLastBackEdge();
for (int j = block->block_id(); j <= last->block_id(); ++j) {
ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects,
- &accumulated_first_time_depends);
+ &accumulated_first_time_depends,
+ &accumulated_first_time_changes);
}
}
}
@@ -1526,7 +1529,8 @@
HBasicBlock* block,
HBasicBlock* loop_header,
GVNFlagSet loop_kills,
- GVNFlagSet* accumulated_first_time_depends) {
+ GVNFlagSet* first_time_depends,
+ GVNFlagSet* first_time_changes) {
HBasicBlock* pre_header = loop_header->predecessors()->at(0);
GVNFlagSet depends_flags =
HValue::ConvertChangesToDependsFlags(loop_kills);
TraceGVN("Loop invariant motion for B%d depends_flags=0x%x\n",
@@ -1544,28 +1548,47 @@
instr->gvn_flags().ToIntegral(),
depends_flags.ToIntegral());
bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags);
- if (!can_hoist && instr->IsTransitionElementsKind()) {
- // It's only possible to hoist one time side effects if there are
no
- // dependencies on their changes from the loop header to the
current
- // instruction.
- GVNFlagSet converted_changes =
- HValue::ConvertChangesToDependsFlags(instr->ChangesFlags());
- TraceGVN("Checking dependencies on one-time instruction %d (%s) "
- "converted changes 0x%X, accumulated depends 0x%X\n",
+ if (instr->IsTransitionElementsKind()) {
+ // It's possible to hoist transitions out of a loop as long as the
+ // hoisting wouldn't move the transition past a DependsOn of one
of it's
+ // changes or any instructions that might change an objects map or
+ // elements contents.
+ GVNFlagSet changes = instr->ChangesFlags();
+ GVNFlagSet hoist_depends_blockers =
+ HValue::ConvertChangesToDependsFlags(changes);
+ // In addition to not hoisting transitions above other
instructions that
+ // change dependencies that the transition changes, it must not be
+ // hoisted above map changes and stores to an elements backing
store
+ // that the transition might change.
+ GVNFlagSet hoist_change_blockers = changes;
+ hoist_change_blockers.Add(kChangesMaps);
+ HTransitionElementsKind* trans =
HTransitionElementsKind::cast(instr);
+ if (trans->original_map()->has_fast_double_elements()) {
+ hoist_change_blockers.Add(kChangesDoubleArrayElements);
+ }
+ if (trans->transitioned_map()->has_fast_double_elements()) {
+ hoist_change_blockers.Add(kChangesArrayElements);
+ }
+ TraceGVN("Checking dependencies on HTransitionElementsKind %d
(%s) "
+ "hoist depends blockers 0x%X, hoist change blockers
0x%X, "
+ "accumulated depends 0x%X, accumulated changes 0x%X\n",
instr->id(),
instr->Mnemonic(),
- converted_changes.ToIntegral(),
- accumulated_first_time_depends->ToIntegral());
- // It's possible to hoist one-time side effects from the current
loop
- // loop only if they dominate all of the successor blocks in the
same
- // loop and there are not any instructions that have
Changes/DependsOn
- // that intervene between it and the beginning of the loop header.
+ hoist_depends_blockers.ToIntegral(),
+ hoist_change_blockers.ToIntegral(),
+ first_time_depends->ToIntegral(),
+ first_time_changes->ToIntegral());
+ // It's possible to hoist transition from the current loop loop
only if
+ // they dominate all of the successor blocks in the same loop and
there
+ // are not any instructions that have Changes/DependsOn that
intervene
+ // between it and the beginning of the loop header.
bool in_nested_loop = block != loop_header &&
((block->parent_loop_header() != loop_header) ||
block->IsLoopHeader());
can_hoist = !in_nested_loop &&
block->IsLoopSuccessorDominator() &&
- !accumulated_first_time_depends->ContainsAnyOf(converted_changes);
+ !first_time_depends->ContainsAnyOf(hoist_depends_blockers) &&
+ !first_time_changes->ContainsAnyOf(hoist_change_blockers);
}
if (can_hoist) {
@@ -1589,10 +1612,8 @@
if (!hoisted) {
// If an instruction is not hoisted, we have to account for its side
// effects when hoisting later HTransitionElementsKind instructions.
- accumulated_first_time_depends->Add(instr->DependsOnFlags());
- GVNFlagSet converted_changes =
- HValue::ConvertChangesToDependsFlags(instr->SideEffectFlags());
- accumulated_first_time_depends->Add(converted_changes);
+ first_time_depends->Add(instr->DependsOnFlags());
+ first_time_changes->Add(instr->ChangesFlags());
}
instr = next;
}
@@ -4454,7 +4475,7 @@
Handle<Map> map = maps->at(i);
ASSERT(map->IsMap());
if (!transition_target.at(i).is_null()) {
- object = AddInstruction(new(zone()) HTransitionElementsKind(
+ AddInstruction(new(zone()) HTransitionElementsKind(
object, map, transition_target.at(i)));
} else {
type_todo[map->elements_kind()] = true;
=======================================
--- /branches/bleeding_edge/test/mjsunit/elements-transition-hoisting.js
Thu Feb 9 06:55:32 2012
+++ /branches/bleeding_edge/test/mjsunit/elements-transition-hoisting.js
Thu Feb 16 07:37:52 2012
@@ -170,4 +170,42 @@
testHoistingWithSideEffect(new Array(5));
testHoistingWithSideEffect(new Array(5));
assertTrue(2 != %GetOptimizationStatus(testHoistingWithSideEffect));
-}
+
+ function testStraightLineDupeElinination(a,b,c,d,e,f) {
+ var count = 3;
+ do {
+ assertTrue(true);
+ a[0] = b;
+ a[1] = c;
+ a[2] = d;
+ assertTrue(true);
+ a[3] = e; // TransitionElementsKind should be eliminated despite
call.
+ a[4] = f;
+ } while (--count > 3);
+ }
+
+ testStraightLineDupeElinination(new Array(0, 0, 0, 0, 0),0,0,0,0,.5);
+ testStraightLineDupeElinination(new Array(0, 0, 0, 0, 0),0,0,0,.5,0);
+ testStraightLineDupeElinination(new Array(0, 0, 0, 0, 0),0,0,.5,0,0);
+ testStraightLineDupeElinination(new Array(0, 0, 0, 0, 0),0,.5,0,0,0);
+ testStraightLineDupeElinination(new Array(0, 0, 0, 0, 0),.5,0,0,0,0);
+ testStraightLineDupeElinination(new Array(.1,.1,.1,.1,.1),0,0,0,0,.5);
+ testStraightLineDupeElinination(new Array(.1,.1,.1,.1,.1),0,0,0,.5,0);
+ testStraightLineDupeElinination(new Array(.1,.1,.1,.1,.1),0,0,.5,0,0);
+ testStraightLineDupeElinination(new Array(.1,.1,.1,.1,.1),0,.5,0,0,0);
+ testStraightLineDupeElinination(new Array(.1,.1,.1,.1,.1),.5,0,0,0,0);
+ testStraightLineDupeElinination(new Array(5),.5,0,0,0,0);
+ testStraightLineDupeElinination(new Array(5),0,.5,0,0,0);
+ testStraightLineDupeElinination(new Array(5),0,0,.5,0,0);
+ testStraightLineDupeElinination(new Array(5),0,0,0,.5,0);
+ testStraightLineDupeElinination(new Array(5),0,0,0,0,.5);
+ testStraightLineDupeElinination(new Array(5),.5,0,0,0,0);
+ testStraightLineDupeElinination(new Array(5),0,.5,0,0,0);
+ testStraightLineDupeElinination(new Array(5),0,0,.5,0,0);
+ testStraightLineDupeElinination(new Array(5),0,0,0,.5,0);
+ testStraightLineDupeElinination(new Array(5),0,0,0,0,.5);
+ %OptimizeFunctionOnNextCall(testStraightLineDupeElinination);
+ testStraightLineDupeElinination(new Array(5));
+ testStraightLineDupeElinination(new Array(5));
+ assertTrue(2 != %GetOptimizationStatus(testStraightLineDupeElinination));
+}
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
