Implement local check elimination on basic blocks.

src/hydrogen-check-elimination.cc

Index: src/hydrogen-check-elimination.cc
diff --git a/src/hydrogen-check-elimination.cc b/src/hydrogen-check-elimination.cc
new file mode 100644
index 0000000000000000000000000000000000000000..63ea5a7e6aa0049b4710de62adc73547d118166e
--- /dev/null
+++ b/src/hydrogen-check-elimination.cc
@@ -0,0 +1,340 @@
+// 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-check-elimination.h"
+#include "hydrogen-alias-analysis.h"
+
+namespace v8 {
+namespace internal {
+
+static const int kMaxTrackedObjects = 10;
+typedef UniqueSet<Map>* MapSet;
+
+// The main datastructure used during check elimination, which stores a
+// set of known maps for each object.
+class HCheckTable {
+ public:
+  explicit HCheckTable(Zone* zone) : zone_(zone) {
+    Kill();
+    redundant_ = 0;
+    narrowed_ = 0;
+    empty_ = 0;
+    removed_ = 0;
+    compares_true_ = 0;
+    compares_false_ = 0;
+    transitions_ = 0;
+  }
+
+  void ReduceCheckMaps(HCheckMaps* instr) {
+    HValue* object = instr->ActualValue();

[Michael Starzinger, 2013/09/26 09:09:56]

Even though HCheckMaps serves as an informative definition of it's target
object, this should always make sure to use the target object. I think the
following is safer:

HValue* object = instr->value()->ActualValue();

+    int index = Find(object);
+    if (index >= 0) {
+      // entry found;
+      MapSet a = known_maps_[index];
+      MapSet i = instr->map_set().Copy(zone_);
+      if (a->IsSubset(i)) {
+        // The first check is more strict; the second is redundant.
+        if (checks_[index] != NULL) {
+          instr->DeleteAndReplaceWith(checks_[index]);
+          redundant_++;
+        } else {
+          instr->DeleteAndReplaceWith(instr->value());
+          removed_++;
+        }
+        return;
+      }
+      i = i->Intersect(a, zone_);
+      if (i->size() == 0) {
+        // Intersection is empty; probably megamorphic, which is likely to
+        // deopt anyway, so just leave things as they are.
+        empty_++;
+      } else {
+        // TODO(titzer): replace the first check with a more strict check.
+        narrowed_++;
+      }
+    } else {
+      // No entry; insert a new one.
+      Insert(object, instr, instr->map_set().Copy(zone_));
+    }
+  }
+
+  void ReduceCheckValue(HCheckValue* instr) {
+    HValue* value = instr->value();
+    if (value->IsLoadNamedField()) {
+      HLoadNamedField* load = HLoadNamedField::cast(value);
+      // Match a HCheckValue(HLoadNamedField[field = map](object))
+      if (IsMapAccess(load->access())) {
+        MapSet maps = FindMaps(load->object()->ActualValue());
+        if (maps == NULL) return;
+        if (maps->size() == 1 && maps->Contains(instr->object())) {
+          // The check is redundant because it's a load of the map,
+          // and the map is known to be exactly the given constant.

[Michael Starzinger, 2013/09/26 09:09:56]

Technically this only holds if the load has happened before any subsequent
map-changes to the object. We might get lucky because we don't generate
map-loads which are used over longer live-ranges. This seems fragile.

+          instr->DeleteAndReplaceWith(NULL);
+          removed_++;
+        }
+      }
+    }
+  }
+
+  void ReduceCheckMapValue(HCheckMapValue* instr) {
+    if (!instr->map()->IsConstant()) return;  // Nothing to learn.
+
+    HValue* object = instr->value()->ActualValue();
+    // Match a HCheckMapValue(object, HConstant(map))
+    Unique<Map> map = MapConstant(instr->map());
+    MapSet maps = FindMaps(object);
+    if (maps != NULL) {
+      if (maps->Contains(map)) {
+        if (maps->size() == 1) {
+          // Object is known to have exactly this map.
+          instr->DeleteAndReplaceWith(NULL);
+          removed_++;
+        } else {
+          // Only one map survives the check.
+          maps->Clear();
+          maps->Add(map, zone_);
+        }
+      }
+    } else {
+      // No prior information.
+      Insert(object, map);
+    }
+  }
+
+  void ReduceStoreNamedField(HStoreNamedField* instr) {
+    HValue* object = instr->object()->ActualValue();
+    if (instr->has_transition()) {
+      // This store transitions the object to a new map.
+      Kill(object);
+      Insert(object, MapConstant(instr->transition()));
+    } else if (IsMapAccess(instr->access())) {
+      // This is a store directly to the map field of the object.
+      Kill(object);
+      if (!instr->value()->IsConstant()) return;
+      Insert(object, MapConstant(instr->value()));
+    } else if (instr->CheckGVNFlag(kChangesMaps)) {
+      // This store indirectly changes the map of the object.
+      Kill(instr->object());
+      UNREACHABLE();
+    }
+  }
+
+  void ReduceCompareMap(HCompareMap* instr) {
+    MapSet maps = FindMaps(instr->value()->ActualValue());
+    if (maps == NULL) return;
+    if (maps->Contains(instr->map())) {
+      // TODO(titzer): replace with goto true branch
+      if (maps->size() == 1) compares_true_++;
+    } else {
+      // TODO(titzer): replace with goto false branch
+      compares_false_++;
+    }
+  }
+
+  void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
+    MapSet maps = FindMaps(instr->object()->ActualValue());
+    // Can only learn more about an object that already has a known set of maps.
+    if (maps == NULL) return;
+    if (maps->Contains(instr->original_map())) {
+      // If the object has the original map, it will be transitioned.
+      maps->Remove(instr->original_map());
+      maps->Add(instr->transitioned_map(), zone_);
+    } else {
+      // Object does not have the given map, thus the transition is redundant.
+      instr->DeleteAndReplaceWith(instr->object());
+      transitions_++;
+    }
+  }
+
+  // Kill everything in the table.
+  void Kill() {
+    memset(objects_, 0, sizeof(objects_));
+  }
+
+  // Kill everything in the table that may alias {object}.
+  void Kill(HValue* object) {
+    for (int i = 0; i < kMaxTrackedObjects; i++) {
+      if (objects_[i] == NULL) continue;
+      if (aliasing_.MayAlias(objects_[i], object)) objects_[i] = NULL;
+    }
+  }
+
+  void Print() {
+    for (int i = 0; i < kMaxTrackedObjects; i++) {
+      if (objects_[i] == NULL) continue;
+      PrintF("  checkmaps-table @%d: object #%d ", i, objects_[i]->id());
+      if (checks_[i] != NULL) {
+        PrintF("check #%d ", checks_[i]->id());
+      }
+      MapSet list = known_maps_[i];
+      PrintF("%d maps { ", list->size());
+      for (int j = 0; j < list->size(); j++) {
+        if (j > 0) PrintF(", ");
+        PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
+      }
+      PrintF(" }\n");
+    }
+  }
+
+  void PrintStats() {
+    if (redundant_ > 0)      PrintF("  redundant   = %2d\n", redundant_);
+    if (removed_ > 0)        PrintF("  removed     = %2d\n", removed_);
+    if (narrowed_ > 0)       PrintF("  narrowed    = %2d\n", narrowed_);
+    if (empty_ > 0)          PrintF("  empty       = %2d\n", empty_);
+    if (compares_true_ > 0)  PrintF("  cmp_true    = %2d\n", compares_true_);
+    if (compares_false_ > 0) PrintF("  cmp_false   = %2d\n", compares_false_);
+    if (transitions_ > 0)    PrintF("  transitions = %2d\n", transitions_);
+  }
+
+ private:
+  int Find(HValue* object) {
+    for (int i = 0; i < kMaxTrackedObjects; i++) {
+      if (objects_[i] == NULL) continue;
+      if (aliasing_.MustAlias(objects_[i], object)) return i;
+    }
+    return -1;
+  }
+
+  MapSet FindMaps(HValue* object) {
+    int index = Find(object);
+    if (index < 0) return NULL;
+    return known_maps_[index];
+  }
+
+  int Insert(HValue* object, Unique<Map> map) {
+    MapSet list = new(zone_) UniqueSet<Map>();
+    list->Add(map, zone_);
+    return Insert(object, NULL, list);
+  }
+
+  int Insert(HValue* object, HCheckMaps* check, MapSet maps) {
+    for (int i = 0; i < kMaxTrackedObjects; i++) {

[Michael Starzinger, 2013/09/26 09:09:56]

Can we ASSERT(Find(object) < 0) here?

+      if (objects_[i] == NULL) {
+        objects_[i] = object;
+        checks_[i] = check;
+        known_maps_[i] = maps;
+        return i;
+      }
+    }
+    return -1;
+  }
+
+  bool IsMapAccess(HObjectAccess access) {
+    return access.IsInobject() && access.offset() == JSObject::kMapOffset;
+  }
+
+  Unique<Map> MapConstant(HValue* value) {
+    return HConstant::cast(value)->GetCastedUnique<Map>();
+  }
+
+  Zone* zone_;
+  HValue* objects_[kMaxTrackedObjects];
+  HValue* checks_[kMaxTrackedObjects];
+  MapSet known_maps_[kMaxTrackedObjects];
+  HAliasAnalyzer aliasing_;
+  int redundant_;
+  int removed_;
+  int narrowed_;
+  int empty_;
+  int compares_true_;
+  int compares_false_;
+  int transitions_;
+};
+
+
+void HCheckEliminationPhase::Run() {
+  for (int i = 0; i < graph()->blocks()->length(); i++) {
+    EliminateLocalChecks(graph()->blocks()->at(i));
+  }
+}
+
+
+// For code de-uglification.
+#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
+
+
+// Eliminate checks local to a block.
+void HCheckEliminationPhase::EliminateLocalChecks(HBasicBlock* block) {
+  HCheckTable table(zone());
+  TRACE(("-- check-elim B%d ------------------------------------------------\n",
+         block->block_id()));
+
+  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+    bool changed = false;
+    HInstruction* instr = it.Current();
+
+    switch (instr->opcode()) {
+      case HValue::kCheckMaps: {
+        table.ReduceCheckMaps(HCheckMaps::cast(instr));
+        changed = true;
+        break;
+      }
+      case HValue::kCheckValue: {
+        table.ReduceCheckValue(HCheckValue::cast(instr));
+        changed = true;
+        break;
+      }
+      case HValue::kStoreNamedField: {
+        table.ReduceStoreNamedField(HStoreNamedField::cast(instr));
+        changed = true;
+        break;
+      }
+      case HValue::kCompareMap: {
+        table.ReduceCompareMap(HCompareMap::cast(instr));
+        changed = true;
+        break;
+      }
+      case HValue::kTransitionElementsKind: {
+        table.ReduceTransitionElementsKind(
+            HTransitionElementsKind::cast(instr));
+        changed = true;
+        break;
+      }
+      case HValue::kCheckMapValue: {
+        table.ReduceCheckMapValue(HCheckMapValue::cast(instr));
+        changed = true;
+        break;
+      }
+      default: {
+        // If the instruction changes maps uncontrollably, kill the whole town.
+        if (instr->CheckGVNFlag(kChangesMaps)) {
+          table.Kill();
+          changed = true;
+        }
+      }
+      // Improvements possible:
+      // - eliminate HCheckSmi and HCheckHeapObject
+    }
+
+    if (changed && FLAG_trace_check_elimination) table.Print();
+  }
+
+  if (FLAG_trace_check_elimination) table.PrintStats();
+}
+
+
+} }  // namespace v8::internal