First implementation of store elimination.

src/hydrogen-store-elimination.cc

Index: src/hydrogen-store-elimination.cc
diff --git a/src/hydrogen-store-elimination.cc b/src/hydrogen-store-elimination.cc
new file mode 100644
index 0000000000000000000000000000000000000000..ea12dd8154d1142a5f477b99eca5c2593520d611
--- /dev/null
+++ b/src/hydrogen-store-elimination.cc
@@ -0,0 +1,230 @@
+// 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.
+
+#include "hydrogen-store-elimination.h"
+#include "hydrogen-instructions.h"
+
+namespace v8 {
+namespace internal {
+
+#define TRACE(x) if (FLAG_trace_store_elimination) PrintF x
+
+// Performs a block-by-block local analysis for removable stores.
+void HStoreEliminationPhase::Run() {
+  GVNFlagSet flags;  // Use GVN flags as an approximation for some instructions.
+  flags.RemoveAll();
+
+  flags.Add(kDependsOnArrayElements);
+  flags.Add(kDependsOnArrayLengths);
+  flags.Add(kDependsOnStringLengths);
+  flags.Add(kDependsOnBackingStoreFields);
+  flags.Add(kDependsOnDoubleArrayElements);
+  flags.Add(kDependsOnDoubleFields);
+  flags.Add(kDependsOnElementsPointer);
+  flags.Add(kDependsOnInobjectFields);
+  flags.Add(kDependsOnExternalMemory);
+
+  for (int i = 0; i < graph()->blocks()->length(); i++) {
+    unobserved_.Rewind(0);
+    HBasicBlock* block = graph()->blocks()->at(i);
+    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+      HInstruction* instr = it.Current();
+
+      switch (instr->opcode()) {
+        case HValue::kStoreNamedField:

[Hannes Payer (out of office), 2014/01/16 15:25:21]

Can we also have that for keyed stores? Leave a TODO?

+          // Remove any unobserved stores overwritten by this store.
+          ProcessStore(HStoreNamedField::cast(instr));
+          break;
+        case HValue::kLoadNamedField:
+          // Observe any unobserved stores on this object + field.
+          ProcessLoad(HLoadNamedField::cast(instr));
+          break;
+        default:
+          ProcessInstr(instr, flags);
+          break;
+      }
+    }
+  }
+}
+
+
+void HStoreEliminationPhase::ProcessStore(HStoreNamedField* store) {
+  HValue* object = store->object()->ActualValue();
+  int i = 0;
+  while (i < unobserved_.length()) {
+    HStoreNamedField* prev = unobserved_.at(i);
+    if (aliasing_->MustAlias(object, prev->object()->ActualValue()) &&
+        store->access().Equals(prev->access())) {
+      // This store is guaranteed to overwrite the previous store.
+      prev->DeleteAndReplaceWith(NULL);
+      TRACE(("++ Unobserved store S%d overwritten by S%d\n",
+             prev->id(), store->id()));
+      unobserved_.Remove(i);
+    } else {
+      // TODO(titzer): remove map word clearing from folded allocations.
+      i++;
+    }
+  }
+  // Only non-transitioning stores are removable.
+  if (!store->has_transition()) {
+    TRACE(("-- Might remove store S%d\n", store->id()));
+    unobserved_.Add(store, zone());
+  }
+}
+
+
+void HStoreEliminationPhase::ProcessLoad(HLoadNamedField* load) {
+  HValue* object = load->object()->ActualValue();
+  int i = 0;
+  while (i < unobserved_.length()) {
+    HStoreNamedField* prev = unobserved_.at(i);
+    if (aliasing_->MayAlias(object, prev->object()->ActualValue()) &&
+        load->access().Equals(prev->access())) {
+      TRACE(("-- Observed store S%d by load L%d\n", prev->id(), load->id()));
+      unobserved_.Remove(i);
+    } else {
+      i++;
+    }
+  }
+}
+
+
+static bool CanDeoptimize(HInstruction* instr) {

[Hannes Payer (out of office), 2014/01/16 15:25:21]

This function looks pretty fragile, is there a more consistent way to check
that? Moreover, does it really belong here? I guess it should live in
HInstruction.

+  // TODO(titzer): most binops can allocate?
+  switch (instr->opcode()) {
+    case HValue::kAccessArgumentsAt:
+    case HValue::kAdd:
+    case HValue::kApplyArguments:
+    case HValue::kArgumentsElements:
+    case HValue::kArgumentsLength:
+    case HValue::kArgumentsObject:
+      // TODO(titzer): non-tagged inputs    case HValue::kBitwise:

[Hannes Payer (out of office), 2014/01/16 15:25:21]

that looks broken

+    case HValue::kBoundsCheckBaseIndexInformation:
+    case HValue::kCapturedObject:
+      // TODO(titzer): non-tagged inputs    case HValue::kChange:
+    case HValue::kClampToUint8:
+      // TODO(titzer): non-tagged inputs    case HValue::kCompareGeneric:
+    case HValue::kConstant:
+    case HValue::kContext:
+    case HValue::kDateField:
+    case HValue::kDebugBreak:
+    case HValue::kDeclareGlobals:
+    case HValue::kDiv:
+    case HValue::kDummyUse:
+    case HValue::kElementsKind:
+    case HValue::kEnterInlined:
+    case HValue::kEnvironmentMarker:
+    case HValue::kForceRepresentation:
+    case HValue::kForInCacheArray:
+    case HValue::kForInPrepareMap:
+    case HValue::kFunctionLiteral:
+    case HValue::kGetCachedArrayIndex:
+    case HValue::kGlobalObject:
+    case HValue::kGlobalReceiver:
+    case HValue::kGoto:
+    case HValue::kInnerAllocatedObject:
+    case HValue::kInstanceOf:
+    case HValue::kInstanceOfKnownGlobal:
+    case HValue::kInvokeFunction:
+    case HValue::kLeaveInlined:
+    case HValue::kLoadContextSlot:
+    case HValue::kLoadExternalArrayPointer:
+    case HValue::kLoadFieldByIndex:
+    case HValue::kLoadFunctionPrototype:
+    case HValue::kLoadGlobalCell:
+    case HValue::kLoadGlobalGeneric:
+    case HValue::kLoadKeyed:
+    case HValue::kLoadKeyedGeneric:
+    case HValue::kLoadNamedField:
+    case HValue::kLoadNamedGeneric:
+    case HValue::kLoadRoot:
+    case HValue::kMapEnumLength:
+    case HValue::kMathFloorOfDiv:
+    case HValue::kMathMinMax:
+    case HValue::kMod:
+    case HValue::kMul:
+    case HValue::kOsrEntry:
+    case HValue::kOuterContext:
+    case HValue::kParameter:
+    case HValue::kPower:
+    case HValue::kPushArgument:
+    case HValue::kRor:
+    case HValue::kSar:
+    case HValue::kSeqStringGetChar:
+    case HValue::kSeqStringSetChar:
+    case HValue::kShl:
+    case HValue::kShr:
+    case HValue::kSimulate:
+    case HValue::kStackCheck:
+    case HValue::kStoreCodeEntry:
+    case HValue::kStoreContextSlot:
+    case HValue::kStoreGlobalCell:
+    case HValue::kStoreGlobalGeneric:
+    case HValue::kStoreKeyed:
+    case HValue::kStoreKeyedGeneric:
+    case HValue::kStoreNamedField:
+    case HValue::kStoreNamedGeneric:
+    case HValue::kStringAdd:
+    case HValue::kStringCharCodeAt:
+    case HValue::kStringCharFromCode:
+    case HValue::kSub:
+    case HValue::kThisFunction:
+    case HValue::kToFastProperties:
+    case HValue::kTransitionElementsKind:
+    case HValue::kTrapAllocationMemento:
+    case HValue::kTypeof:
+    case HValue::kUnaryMathOperation:
+    case HValue::kUseConst:
+    case HValue::kWrapReceiver:
+      return false;
+    default:
+      return true;
+  }
+}
+
+
+void HStoreEliminationPhase::ProcessInstr(HInstruction* instr,
+    GVNFlagSet flags) {
+  if (unobserved_.length() == 0) return;  // Nothing to do.
+  if (CanDeoptimize(instr)) {
+    TRACE(("-- Observed stores at I%d (might deoptimize)\n", instr->id()));
+    unobserved_.Rewind(0);
+    return;
+  }
+  if (instr->CheckGVNFlag(kChangesNewSpacePromotion)) {
+    TRACE(("-- Observed stores at I%d (might GC)\n", instr->id()));
+    unobserved_.Rewind(0);
+    return;
+  }
+  if (instr->gvn_flags().ContainsAnyOf(flags)) {
+    TRACE(("-- Observed stores at I%d (GVN flags)\n", instr->id()));
+    unobserved_.Rewind(0);
+    return;
+  }
+}
+
+} }  // namespace v8::internal