Handle HCheckInstanceType and HIsStringAndBranch in check elimination.

src/hydrogen-check-elimination.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "hydrogen-check-elimination.h"
 
 #include "hydrogen-alias-analysis.h"
 #include "hydrogen-flow-engine.h"
 
 #define GLOBAL 1
@@ skipping 86 matching lines @@
         break;
       }
       case HValue::kCompareMap: {
         ReduceCompareMap(HCompareMap::cast(instr));
         break;
       }
       case HValue::kCompareObjectEqAndBranch: {
         ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr));
         break;
       }
+      case HValue::kIsStringAndBranch: {
+        ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr));
+        break;
+      }
       case HValue::kTransitionElementsKind: {
         ReduceTransitionElementsKind(
             HTransitionElementsKind::cast(instr));
         break;
       }
       case HValue::kCheckHeapObject: {
         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)) {
           Kill();
           break;
         }
         if (instr->CheckChangesFlag(kElementsKind) ||
             instr->CheckChangesFlag(kMaps)) {
           KillUnstableEntries();
         }
       }
       // Improvements possible:
-      // - eliminate redundant HCheckSmi, HCheckInstanceType instructions
+      // - eliminate redundant HCheckSmi instructions
       // - track which values have been HCheckHeapObject'd
     }
 
     return this;
   }
 
   // Support for global analysis with HFlowEngine: Merge given state with
   // the other incoming state.
   static HCheckTable* Merge(HCheckTable* succ_state, HBasicBlock* succ_block,
                             HCheckTable* pred_state, HBasicBlock* pred_block,
@@ skipping 115 matching lines @@
         } else {
           EnsureChecked(le, cmp->left(), cmp);
           EnsureChecked(re, cmp->right(), cmp);
           le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone);
           le->state_ = re->state_ = HCheckTableEntry::StateMerge(
               le->state_, re->state_);
           ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_);
           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.
     }
 
     if (FLAG_trace_check_elimination) {
       PrintF("B%d checkmaps-table %s from B%d:\n",
              succ->block_id(),
              learned ? "learned" : "copied",
              from_block->block_id());
       Print(copy);
@@ skipping 134 matching lines @@
     } else {
       // No entry; insert a new one.
       HCheckTableEntry::State state = instr->maps_are_stable()
           ? HCheckTableEntry::CHECKED_STABLE
           : HCheckTableEntry::CHECKED;
       HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr;
       Insert(object, check, instr->maps(), state);
     }
   }
 
+  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()) {
       // Check if we introduce field maps here.
       MapSet maps = instr->maps();
       if (maps != NULL) {
         ASSERT_NE(0, maps->size());
         Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE);
       }
       return;
@@ skipping 93 matching lines @@
 
     TRACE(("Marking redundant CompareObjectEqAndBranch #%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);
   }
 
+  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);
     // Can only learn more about an object that already has a known set of maps.
     if (entry == NULL) return;
     EnsureChecked(entry, object, instr);
     if (entry->maps_->Contains(instr->original_map())) {
       // If the object has the original map, it will be transitioned.
       UniqueSet<Map>* maps = entry->maps_->Copy(zone());
       maps->Remove(instr->original_map());
@@ skipping 140 matching lines @@
     entry->object_ = object;
     entry->check_ = check;
     entry->maps_ = maps;
     entry->state_ = state;
     // If the table becomes full, wrap around and overwrite older entries.
     if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
     if (size_ < kMaxTrackedObjects) size_++;
   }
 
   Zone* zone() const { return phase_->zone(); }
+  MapSet string_maps() const { return phase_->string_maps(); }
 
   friend class HCheckMapsEffects;
   friend class HCheckEliminationPhase;
 
   HCheckEliminationPhase* phase_;
   HCheckTableEntry entries_[kMaxTrackedObjects];
   int16_t cursor_;  // Must be <= kMaxTrackedObjects
   int16_t size_;    // Must be <= kMaxTrackedObjects
   STATIC_ASSERT(kMaxTrackedObjects < (1 << 15));
 };
@@ skipping 86 matching lines @@
 // Are we eliminated yet?
 void HCheckEliminationPhase::PrintStats() {
 #if DEBUG
   #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_)
 #else
   #define PRINT_STAT(x)
 #endif
   PRINT_STAT(redundant);
   PRINT_STAT(removed);
   PRINT_STAT(removed_cho);
+  PRINT_STAT(removed_cit);
   PRINT_STAT(narrowed);
   PRINT_STAT(loads);
   PRINT_STAT(empty);
   PRINT_STAT(compares_true);
   PRINT_STAT(compares_false);
   PRINT_STAT(transitions);
 }
 
 } }  // namespace v8::internal