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);
+            entry->maps_ = entry->maps_->Subtract(string_maps(), zone);
+            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) {
+      if (instr->check() == HCheckInstanceType::IS_STRING) {
+        Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED);
+      }
+      return;
+    }
+    UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>(
+        entry->maps_->size(), zone());
+    for (int i = 0; i < entry->maps_->size(); ++i) {
+      InstanceType type;
+      Unique<Map> map = entry->maps_->at(i);
+      {
+        // This is safe, because maps don't move and their instance type does
+        // not change.
+        AllowHandleDereference allow_deref;
+        type = map.handle()->instance_type();
+      }
+      if (instr->is_interval_check()) {
+        InstanceType first_type, last_type;
+        instr->GetCheckInterval(&first_type, &last_type);
+        if (first_type <= type && type <= last_type) maps->Add(map, zone());
+      } else {
+        uint8_t mask, tag;
+        instr->GetCheckMaskAndTag(&mask, &tag);
+        if ((type & mask) == tag) maps->Add(map, zone());
+      }
+    }
+    if (maps->size() == entry->maps_->size()) {
+      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_);
+    } else if (maps->size() != 0) {
+      entry->maps_ = maps;
+      if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
+        entry->state_ = HCheckTableEntry::CHECKED_STABLE;
+      }
+    }
+  }
+
   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);
+    int succ;
+    if (entry->maps_->IsSubset(string_maps())) {
+      TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n",
+             instr->id(), instr->block()->block_id()));
+      succ = 0;
+    } else {
+      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()));
+      succ = 1;
+    }
+    instr->set_known_successor_index(succ);
+    int unreachable_succ = 1 - succ;
+    instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
+  }
+
   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