Handle HCheckInstanceType and HIsStringAndBranch in check elimination.

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
index 506a04588995fbd25c858424b1461adf1155b781..27eb2eb501d56336308633aaade1f2686870edf8 100644
--- a/src/hydrogen-check-elimination.cc
+++ b/src/hydrogen-check-elimination.cc
@@ -104,6 +104,10 @@ class HCheckTable : public ZoneObject {
         ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr));
         break;
       }
+      case HValue::kIsStringAndBranch: {
+        ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr));
+        break;
+      }
       case HValue::kTransitionElementsKind: {
         ReduceTransitionElementsKind(
             HTransitionElementsKind::cast(instr));
@@ -113,6 +117,10 @@ class HCheckTable : public ZoneObject {
         ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
         break;
       }
+      case HValue::kCheckInstanceType: {
+        ReduceCheckInstanceType(HCheckInstanceType::cast(instr));
+        break;
+      }
       default: {
         // If the instruction changes maps uncontrollably, drop everything.
         if (instr->CheckChangesFlag(kOsrEntries)) {
@@ -125,7 +133,7 @@ class HCheckTable : public ZoneObject {
         }
       }
       // Improvements possible:
-      // - eliminate redundant HCheckSmi, HCheckInstanceType instructions
+      // - eliminate redundant HCheckSmi instructions
       // - track which values have been HCheckHeapObject'd
     }
 
@@ -261,6 +269,33 @@ class HCheckTable : public ZoneObject {
           ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_);
         }
         learned = true;
+      } else if (end->IsIsStringAndBranch()) {
+        HIsStringAndBranch* cmp = HIsStringAndBranch::cast(end);
+        HValue* object = cmp->value()->ActualValue();
+        HCheckTableEntry* entry = copy->Find(object);
+        if (is_true_branch) {
+          // Learn on the true branch of if(IsString(x)).
+          if (entry == NULL) {
+            copy->Insert(object, NULL, string_maps(),
+                         HCheckTableEntry::CHECKED);
+          } else {
+            EnsureChecked(entry, object, cmp);
+            entry->maps_ = entry->maps_->Intersect(string_maps(), zone);
+            ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
+          }
+        } else {
+          // Learn on the false branch of if(IsString(x)).
+          if (entry != NULL) {
+            EnsureChecked(entry, object, cmp);
+            UniqueSet<Map>* maps = new(zone) UniqueSet<Map>();
+            for (int i = 0; i < entry->maps_->size(); ++i) {
+              Unique<Map> map = entry->maps_->at(i);
+              if (!string_maps()->Contains(map)) maps->Add(map, zone);
+            }

[Igor Sheludko, 2014/05/30 10:00:41]

Suggestion: What about adding Subtract() method to UniqueSet?

[Benedikt Meurer, 2014/05/31 11:15:46]

Done.

+            entry->maps_ = maps;
+            ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
+          }
+        }
       }
       // Learning on false branches requires storing negative facts.
     }
@@ -415,6 +450,37 @@ class HCheckTable : public ZoneObject {
     }
   }
 
+  void ReduceCheckInstanceType(HCheckInstanceType* instr) {
+    HValue* value = instr->value()->ActualValue();
+    HCheckTableEntry* entry = Find(value);
+    if (entry == NULL) return;
+    for (int i = 0; i < entry->maps_->size(); ++i) {
+      InstanceType type;
+      Handle<Map> map = entry->maps_->at(i).handle();
+      {
+        // This is safe, because maps don't move and their instance type does
+        // not change.
+        AllowHandleDereference allow_deref;
+        type = map->instance_type();
+      }
+      if (instr->is_interval_check()) {
+        InstanceType first_type, last_type;
+        instr->GetCheckInterval(&first_type, &last_type);
+        if (type < first_type || last_type < type) return;
+      } else {
+        uint8_t mask, tag;
+        instr->GetCheckMaskAndTag(&mask, &tag);
+        if ((type & mask) != tag) return;
+      }
+    }

[Igor Sheludko, 2014/05/30 10:00:41]

Does it make sense to update set of entry maps if the instruction ensures string
or non-string type even if the instruction itself can't be eliminated?

[Benedikt Meurer, 2014/05/31 11:15:46]

Done.

+    TRACE(("Removing redundant CheckInstanceType #%d at B%d\n",
+            instr->id(), instr->block()->block_id()));
+    EnsureChecked(entry, value, instr);
+    instr->DeleteAndReplaceWith(value);
+    INC_STAT(removed_cit_);
+    return;
+  }
+
   void ReduceLoadNamedField(HLoadNamedField* instr) {
     // Reduce a load of the map field when it is known to be a constant.
     if (!instr->access().IsMap()) {
@@ -528,6 +594,35 @@ class HCheckTable : public ZoneObject {
     instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
   }
 
+  void ReduceIsStringAndBranch(HIsStringAndBranch* instr) {
+    HValue* value = instr->value()->ActualValue();
+    HCheckTableEntry* entry = Find(value);
+    if (entry == NULL) return;
+    EnsureChecked(entry, value, instr);
+    if (entry->maps_->IsSubset(string_maps())) {
+      TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n",
+             instr->id(), instr->block()->block_id()));
+      int succ = 0;
+      instr->set_known_successor_index(succ);
+
+      int unreachable_succ = 1 - succ;
+      instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
+      return;
+    }
+
+    // TODO(bmeurer): Add a predicate here instead of computing the intersection
+    MapSet intersection = entry->maps_->Intersect(string_maps(), zone());
+    if (intersection->size() > 0) return;
+
+    TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n",
+           instr->id(), instr->block()->block_id()));
+    int succ = 1;
+    instr->set_known_successor_index(succ);
+
+    int unreachable_succ = 1 - succ;
+    instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);

[Igor Sheludko, 2014/05/30 10:00:41]

I would suggest to avoid duplication of the three lines above.

[Benedikt Meurer, 2014/05/31 11:15:46]

Done.

+  }
+
   void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
     HValue* object = instr->object()->ActualValue();
     HCheckTableEntry* entry = Find(object);
@@ -688,6 +783,7 @@ class HCheckTable : public ZoneObject {
   }
 
   Zone* zone() const { return phase_->zone(); }
+  MapSet string_maps() const { return phase_->string_maps(); }
 
   friend class HCheckMapsEffects;
   friend class HCheckEliminationPhase;
@@ -794,6 +890,7 @@ void HCheckEliminationPhase::PrintStats() {
   PRINT_STAT(redundant);
   PRINT_STAT(removed);
   PRINT_STAT(removed_cho);
+  PRINT_STAT(removed_cit);
   PRINT_STAT(narrowed);
   PRINT_STAT(loads);
   PRINT_STAT(empty);