Improve GVN handling of ElementTransitions.

test/mjsunit/elements-transition-hoisting.js

Index: test/mjsunit/elements-transition-hoisting.js
diff --git a/test/mjsunit/elements-transition-hoisting.js b/test/mjsunit/elements-transition-hoisting.js
new file mode 100644
index 0000000000000000000000000000000000000000..f6e36cd60a55c75c15cb34367bdf2b7b3fe3e0d1
--- /dev/null
+++ b/test/mjsunit/elements-transition-hoisting.js
@@ -0,0 +1,182 @@
+// 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
+
+// Ensure that ElementsKind transitions in various situations are hoisted (or
+// not hoisted) correctly, don't change the semantics programs and don't trigger
+// deopt through hoisting in important situations.
+
+support_smi_only_arrays = %HasFastSmiOnlyElements(new Array(1,2,3,4,5,6));
+
+if (support_smi_only_arrays) {
+  print("Tests include smi-only arrays.");
+} else {
+  print("Tests do NOT include smi-only arrays.");
+}
+
+if (support_smi_only_arrays) {
+  // Make sure that multiple stores to an object array get hoisted in a way that
+  // doesn't generate a deopt in simple cases.
+  function testDoubleConversion4(a) {
+    var object = new Object();
+    a[0] = 0;
+    do {
+      // In non CS code, the array should have FAST_SMI_ONLY_ELEMENTS at this
+      // point, but when the code gets optimized, the double transition should

[fschneider, 2012/02/01 10:54:14]

s/double//

[danno, 2012/02/01 16:53:15]

Done.

+      // get hoisted out and the array should be of type FAST_OBJECT
+      assertTrue(((2 != %GetOptimizationStatus(testDoubleConversion4) &&
+                   %HasFastElements(a)) || %HasFastSmiOnlyElements(a)));
+      a[0] = object;
+      result = a[0] == object;
+    } while (false);

[fschneider, 2012/02/01 10:54:14]

do { } while(false) may be optimized away by the compiler. Not sure if we
currently do it, but in the future it will definitely be.

[danno, 2012/02/01 16:53:15]

Done.

+    // Check outside of loop to prevent call in loop

[fschneider, 2012/02/01 10:54:14]

This comment does not make sense: there is already a call to assertTrue,
%HasFastElements, etc. inside the loop.

[danno, 2012/02/01 16:53:15]

Done.

+    assertTrue(result);
+  }
+
+  testDoubleConversion4(new Array(5));
+  %OptimizeFunctionOnNextCall(testDoubleConversion4);
+  testDoubleConversion4(new Array(5));
+  testDoubleConversion4(new Array(5));
+  assertTrue(2 != %GetOptimizationStatus(testDoubleConversion4));
+
+  // Make sure that non-element related map checks still get hoisted in a way
+  // that doesn't generate a deopt in simple cases.
+  function testExactMapHoisting(a) {
+    var object = new Object();
+    a.foo = 0;
+    a[0] = 0;
+    a[1] = 1;
+    do {
+      // In non CS code, the array should have FAST_SMI_ONLY_ELEMENTS at this
+      // point, but when the code gets optimized, the double transition should

[fschneider, 2012/02/01 10:54:14]

s/double//

[danno, 2012/02/01 16:53:15]

Done.

+      // get hoisted out and the array should be of type FAST_OBJECT
+      assertTrue(((2 != %GetOptimizationStatus(testExactMapHoisting) &&
+                   %HasFastElements(a)) || %HasFastSmiOnlyElements(a)));
+      a.foo = object; // This map check should be hoistable
+      a[1] = object;
+      result = a.foo == object && a[1] == object;
+    } while (false);
+    // Check outside of loop to prevent call in loop
+    assertTrue(result);
+  }
+
+  testExactMapHoisting(new Array(5));
+  %OptimizeFunctionOnNextCall(testExactMapHoisting);
+  testExactMapHoisting(new Array(5));
+  testExactMapHoisting(new Array(5));
+  assertTrue(2 != %GetOptimizationStatus(testExactMapHoisting));
+
+  // Make sure that non-element related map checks still get hoisted if all
+  // known element transitions have been done by the time the map check is done.
+  // Make sure it's done in a way that doesn't deopt later.
+  function testExactMapHoisting2(a) {
+    var object = new Object();
+    a.foo = 0;
+    a[0] = 0;
+    a[1] = 1;
+    do {
+      // In non CS code, the array should have FAST_SMI_ONLY_ELEMENTS at this
+      // point, but when the code gets optimized, the double transition should
+      // get hoisted out and the array should be of type FAST_DOUBLE_ELEMENTS
+      assertTrue(((2 != %GetOptimizationStatus(testExactMapHoisting2) &&
+                   %HasFastDoubleElements(a)) || %HasFastSmiOnlyElements(a)));
+      a[1] = 2.5;
+      a.foo = object; // This map check should be hoistable

[fschneider, 2012/02/01 10:54:14]

There are calls inside the loop, so this map check won't be hoisted.

[danno, 2012/02/01 16:53:15]

Done.

+      result = a.foo == object && a[1] == 2.5;
+    } while (false);
+    // Check outside of loop to prevent call in loop
+    assertTrue(result);
+  }
+
+  testExactMapHoisting2(new Array(5));
+  %OptimizeFunctionOnNextCall(testExactMapHoisting2);
+  testExactMapHoisting2(new Array(5));
+  testExactMapHoisting2(new Array(5));
+  assertTrue(2 != %GetOptimizationStatus(testExactMapHoisting2));
+
+  // Make sure that non-element related map checks still get hoisted if all
+  // known element transitions have been done by the time the map check is done.
+  // Make sure it's done in a way that doesn't deopt later.
+  function testExactMapHoisting3(a) {
+    var object = new Object();
+    a.foo = 0;
+    a[0] = 0;
+    a[1] = 1;
+    do {
+      // In non CS code, the array should have FAST_SMI_ONLY_ELEMENTS at this
+      // point, but when the code gets optimized, the double transition should
+      // get hoisted out and the array should be of type FAST_DOUBLE_ELEMENTS
+      assertTrue(((2 != %GetOptimizationStatus(testExactMapHoisting3) &&
+                   %HasFastDoubleElements(a)) || %HasFastSmiOnlyElements(a)));
+      a[1] = 2.5;
+      a.foo = object; // This map check should NOT be hoistable because it
+      // includes a check for the FAST_ELEMENTS map as well as the
+      // FAST_DOUBLE_ELEMENTS map.
+      result = a.foo == object && a[1] == 2.5;
+    } while (false);
+    // Check outside of loop to prevent call in loop
+    assertTrue(result);
+  }
+
+  var add_transition = new Array(5);
+  add_transition.foo = 0;
+  add_transition[0] = new Object(); // For FAST_ELEMENT transition to be created
+  testExactMapHoisting3(new Array(5));
+  %OptimizeFunctionOnNextCall(testExactMapHoisting3);
+  testExactMapHoisting3(new Array(5));
+  testExactMapHoisting3(new Array(5));
+  assertTrue(2 != %GetOptimizationStatus(testExactMapHoisting3));
+
+  function testDominatingTransitionHoisting1(a) {
+    var object = new Object();
+    a.foo = 0;
+    a[0] = 0;
+    do {
+      // Transitions shouldn't be hoisted that are not guaranteed to dominate
+      // all blocks after them with higher id numbers.
+      assertTrue(%HasFastSmiOnlyElements(a));
+      if (new Date() != true) {
+        a[1] = 2.5;
+      }
+      // The following FAST_DOUBLE_ELEMENTS -> FAST_ELEMENT transition can't be
+      // hoisted because of the FAST_SMI_ONLY_ELEMENTS -> FAST_DOUBLE_ELEMENTS
+      // transition in the if immediately above.
+      assertTrue(%HasFastDoubleElements(a));
+      a[0] = object;
+      result = a[0] == object && a[1] == 2.5;
+    } while (false);
+    // Check outside of loop to prevent call in loop
+    assertTrue(result);
+  }
+
+  testDominatingTransitionHoisting1(new Array(5));
+  %OptimizeFunctionOnNextCall(testDominatingTransitionHoisting1);
+  testDominatingTransitionHoisting1(new Array(5));
+  testDominatingTransitionHoisting1(new Array(5));
+  assertTrue(2 != %GetOptimizationStatus(testDominatingTransitionHoisting1));
+}