LCOV - code coverage report
Current view: top level - src/crankshaft - hydrogen-check-elimination.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 351 396 88.6 %
Date: 2017-04-26 Functions: 24 27 88.9 %

          Line data    Source code
       1             : // Copyright 2013 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/crankshaft/hydrogen-check-elimination.h"
       6             : 
       7             : #include "src/crankshaft/hydrogen-alias-analysis.h"
       8             : #include "src/crankshaft/hydrogen-flow-engine.h"
       9             : #include "src/objects-inl.h"
      10             : 
      11             : #define GLOBAL 1
      12             : 
      13             : // Only collect stats in debug mode.
      14             : #if DEBUG
      15             : #define INC_STAT(x) phase_->x++
      16             : #else
      17             : #define INC_STAT(x)
      18             : #endif
      19             : 
      20             : // For code de-uglification.
      21             : #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
      22             : 
      23             : namespace v8 {
      24             : namespace internal {
      25             : 
      26             : typedef const UniqueSet<Map>* MapSet;
      27             : 
      28             : struct HCheckTableEntry {
      29             :   enum State {
      30             :     // We have seen a map check (i.e. an HCheckMaps) for these maps, so we can
      31             :     // use this information to eliminate further map checks, elements kind
      32             :     // transitions, etc.
      33             :     CHECKED,
      34             :     // Same as CHECKED, but we also know that these maps are stable.
      35             :     CHECKED_STABLE,
      36             :     // These maps are stable, but not checked (i.e. we learned this via field
      37             :     // type tracking or from a constant, or they were initially CHECKED_STABLE,
      38             :     // but became UNCHECKED_STABLE because of an instruction that changes maps
      39             :     // or elements kind), and we need a stability check for them in order to use
      40             :     // this information for check elimination (which turns them back to
      41             :     // CHECKED_STABLE).
      42             :     UNCHECKED_STABLE
      43             :   };
      44             : 
      45           0 :   static const char* State2String(State state) {
      46           0 :     switch (state) {
      47             :       case CHECKED: return "checked";
      48           0 :       case CHECKED_STABLE: return "checked stable";
      49           0 :       case UNCHECKED_STABLE: return "unchecked stable";
      50             :     }
      51           0 :     UNREACHABLE();
      52             :     return NULL;
      53             :   }
      54             : 
      55             :   static State StateMerge(State state1, State state2) {
      56      934121 :     if (state1 == state2) return state1;
      57       18031 :     if ((state1 == CHECKED && state2 == CHECKED_STABLE) ||
      58        7382 :         (state2 == CHECKED && state1 == CHECKED_STABLE)) {
      59             :       return CHECKED;
      60             :     }
      61             :     DCHECK((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) ||
      62             :            (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE));
      63             :     return UNCHECKED_STABLE;
      64             :   }
      65             : 
      66             :   HValue* object_;  // The object being approximated. NULL => invalid entry.
      67             :   HInstruction* check_;  // The last check instruction.
      68             :   MapSet maps_;          // The set of known maps for the object.
      69             :   State state_;          // The state of this entry.
      70             : };
      71             : 
      72             : 
      73             : // The main data structure used during check elimination, which stores a
      74             : // set of known maps for each object.
      75             : class HCheckTable : public ZoneObject {
      76             :  public:
      77             :   static const int kMaxTrackedObjects = 16;
      78             : 
      79             :   explicit HCheckTable(HCheckEliminationPhase* phase)
      80             :     : phase_(phase),
      81             :       cursor_(0),
      82     2166873 :       size_(0) {
      83             :   }
      84             : 
      85             :   // The main processing of instructions.
      86    20917074 :   HCheckTable* Process(HInstruction* instr, Zone* zone) {
      87    20917074 :     switch (instr->opcode()) {
      88             :       case HValue::kCheckMaps: {
      89      203630 :         ReduceCheckMaps(HCheckMaps::cast(instr));
      90      203632 :         break;
      91             :       }
      92             :       case HValue::kLoadNamedField: {
      93      246860 :         ReduceLoadNamedField(HLoadNamedField::cast(instr));
      94      246864 :         break;
      95             :       }
      96             :       case HValue::kStoreNamedField: {
      97      181291 :         ReduceStoreNamedField(HStoreNamedField::cast(instr));
      98      181292 :         break;
      99             :       }
     100             :       case HValue::kCompareMap: {
     101       21996 :         ReduceCompareMap(HCompareMap::cast(instr));
     102       21997 :         break;
     103             :       }
     104             :       case HValue::kCompareObjectEqAndBranch: {
     105       42800 :         ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr));
     106       42800 :         break;
     107             :       }
     108             :       case HValue::kIsStringAndBranch: {
     109         454 :         ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr));
     110         454 :         break;
     111             :       }
     112             :       case HValue::kTransitionElementsKind: {
     113             :         ReduceTransitionElementsKind(
     114         769 :             HTransitionElementsKind::cast(instr));
     115         769 :         break;
     116             :       }
     117             :       case HValue::kCheckHeapObject: {
     118       92252 :         ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
     119       92249 :         break;
     120             :       }
     121             :       case HValue::kCheckInstanceType: {
     122       43573 :         ReduceCheckInstanceType(HCheckInstanceType::cast(instr));
     123       43572 :         break;
     124             :       }
     125             :       default: {
     126             :         // If the instruction changes maps uncontrollably, drop everything.
     127    20083558 :         if (instr->CheckChangesFlag(kOsrEntries)) {
     128             :           Kill();
     129             :           break;
     130             :         }
     131    38812553 :         if (instr->CheckChangesFlag(kElementsKind) ||
     132             :             instr->CheckChangesFlag(kMaps)) {
     133     1350168 :           KillUnstableEntries();
     134             :         }
     135             :       }
     136             :       // Improvements possible:
     137             :       // - eliminate redundant HCheckSmi instructions
     138             :       // - track which values have been HCheckHeapObject'd
     139             :     }
     140             : 
     141    20917186 :     return this;
     142             :   }
     143             : 
     144             :   // Support for global analysis with HFlowEngine: Merge given state with
     145             :   // the other incoming state.
     146     3289221 :   static HCheckTable* Merge(HCheckTable* succ_state, HBasicBlock* succ_block,
     147             :                             HCheckTable* pred_state, HBasicBlock* pred_block,
     148             :                             Zone* zone) {
     149     5697188 :     if (pred_state == NULL || pred_block->IsUnreachable()) {
     150             :       return succ_state;
     151             :     }
     152     2407976 :     if (succ_state == NULL) {
     153     1883137 :       return pred_state->Copy(succ_block, pred_block, zone);
     154             :     } else {
     155      524839 :       return succ_state->Merge(succ_block, pred_state, pred_block, zone);
     156             :     }
     157             :   }
     158             : 
     159             :   // Support for global analysis with HFlowEngine: Given state merged with all
     160             :   // the other incoming states, prepare it for use.
     161     4511651 :   static HCheckTable* Finish(HCheckTable* state, HBasicBlock* block,
     162             :                              Zone* zone) {
     163     4511651 :     if (state == NULL) {
     164      919599 :       block->MarkUnreachable();
     165     3592052 :     } else if (block->IsUnreachable()) {
     166             :       state = NULL;
     167             :     }
     168     4511635 :     if (FLAG_trace_check_elimination) {
     169           0 :       PrintF("Processing B%d, checkmaps-table:\n", block->block_id());
     170           0 :       Print(state);
     171             :     }
     172     4511635 :     return state;
     173             :   }
     174             : 
     175             :  private:
     176             :   // Copy state to successor block.
     177     1883598 :   HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
     178     1883144 :     HCheckTable* copy = new(zone) HCheckTable(phase_);
     179     5320983 :     for (int i = 0; i < size_; i++) {
     180     3437851 :       HCheckTableEntry* old_entry = &entries_[i];
     181             :       DCHECK(old_entry->maps_->size() > 0);
     182     3437851 :       HCheckTableEntry* new_entry = &copy->entries_[i];
     183     3437851 :       new_entry->object_ = old_entry->object_;
     184     3437851 :       new_entry->maps_ = old_entry->maps_;
     185     3437851 :       new_entry->state_ = old_entry->state_;
     186             :       // Keep the check if the existing check's block dominates the successor.
     187     3569788 :       if (old_entry->check_ != NULL &&
     188      131949 :           old_entry->check_->block()->Dominates(succ)) {
     189      119313 :         new_entry->check_ = old_entry->check_;
     190             :       } else {
     191             :         // Leave it NULL till we meet a new check instruction for this object
     192             :         // in the control flow.
     193     3318526 :         new_entry->check_ = NULL;
     194             :       }
     195             :     }
     196     1883132 :     copy->cursor_ = cursor_;
     197     1883132 :     copy->size_ = size_;
     198             : 
     199             :     // Create entries for succ block's phis.
     200     1883132 :     if (!succ->IsLoopHeader() && succ->phis()->length() > 0) {
     201      150158 :       int pred_index = succ->PredecessorIndexOf(from_block);
     202      692934 :       for (int phi_index = 0;
     203      346467 :            phi_index < succ->phis()->length();
     204             :            ++phi_index) {
     205      196309 :         HPhi* phi = succ->phis()->at(phi_index);
     206             :         HValue* phi_operand = phi->OperandAt(pred_index);
     207             : 
     208      196309 :         HCheckTableEntry* pred_entry = copy->Find(phi_operand);
     209      196309 :         if (pred_entry != NULL) {
     210             :           // Create an entry for a phi in the table.
     211        9403 :           copy->Insert(phi, NULL, pred_entry->maps_, pred_entry->state_);
     212             :         }
     213             :       }
     214             :     }
     215             : 
     216             :     // Branch-sensitive analysis for certain comparisons may add more facts
     217             :     // to the state for the successor on the true branch.
     218             :     bool learned = false;
     219     1883132 :     if (succ->predecessors()->length() == 1) {
     220     1483381 :       HControlInstruction* end = succ->predecessors()->at(0)->end();
     221     1483381 :       bool is_true_branch = end->SuccessorAt(0) == succ;
     222     2966769 :       if (end->IsCompareMap()) {
     223       21996 :         HCompareMap* cmp = HCompareMap::cast(end);
     224       43993 :         HValue* object = cmp->value()->ActualValue();
     225       43993 :         HCheckTableEntry* entry = copy->Find(object);
     226       43993 :         if (is_true_branch) {
     227             :           HCheckTableEntry::State state = cmp->map_is_stable()
     228             :               ? HCheckTableEntry::CHECKED_STABLE
     229       21996 :               : HCheckTableEntry::CHECKED;
     230             :           // Learn on the true branch of if(CompareMap(x)).
     231       21996 :           if (entry == NULL) {
     232       15371 :             copy->Insert(object, cmp, cmp->map(), state);
     233             :           } else {
     234        6625 :             entry->maps_ = new(zone) UniqueSet<Map>(cmp->map(), zone);
     235        6625 :             entry->check_ = cmp;
     236        6625 :             entry->state_ = state;
     237             :           }
     238             :         } else {
     239             :           // Learn on the false branch of if(CompareMap(x)).
     240       21997 :           if (entry != NULL) {
     241        6625 :             EnsureChecked(entry, object, cmp);
     242        6625 :             UniqueSet<Map>* maps = entry->maps_->Copy(zone);
     243        6625 :             maps->Remove(cmp->map());
     244        6625 :             entry->maps_ = maps;
     245             :             DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
     246             :           }
     247             :         }
     248             :         learned = true;
     249     2159092 :       } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) {
     250             :         // Learn on the true branch of if(CmpObjectEq(x, y)).
     251             :         HCompareObjectEqAndBranch* cmp =
     252             :           HCompareObjectEqAndBranch::cast(end);
     253       42799 :         HValue* left = cmp->left()->ActualValue();
     254       42801 :         HValue* right = cmp->right()->ActualValue();
     255       42800 :         HCheckTableEntry* le = copy->Find(left);
     256       42801 :         HCheckTableEntry* re = copy->Find(right);
     257       42799 :         if (le == NULL) {
     258       41317 :           if (re != NULL) {
     259          39 :             copy->Insert(left, NULL, re->maps_, re->state_);
     260             :           }
     261        1482 :         } else if (re == NULL) {
     262         827 :           copy->Insert(right, NULL, le->maps_, le->state_);
     263             :         } else {
     264         655 :           EnsureChecked(le, cmp->left(), cmp);
     265         655 :           EnsureChecked(re, cmp->right(), cmp);
     266         655 :           le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone);
     267             :           le->state_ = re->state_ = HCheckTableEntry::StateMerge(
     268        1310 :               le->state_, re->state_);
     269             :           DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_);
     270             :           DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_);
     271             :         }
     272             :         learned = true;
     273     1396594 :       } else if (end->IsIsStringAndBranch()) {
     274             :         HIsStringAndBranch* cmp = HIsStringAndBranch::cast(end);
     275         908 :         HValue* object = cmp->value()->ActualValue();
     276         908 :         HCheckTableEntry* entry = copy->Find(object);
     277         908 :         if (is_true_branch) {
     278             :           // Learn on the true branch of if(IsString(x)).
     279         454 :           if (entry == NULL) {
     280             :             copy->Insert(object, NULL, string_maps(),
     281         448 :                          HCheckTableEntry::CHECKED);
     282             :           } else {
     283           6 :             EnsureChecked(entry, object, cmp);
     284           6 :             entry->maps_ = entry->maps_->Intersect(string_maps(), zone);
     285             :             DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
     286             :           }
     287             :         } else {
     288             :           // Learn on the false branch of if(IsString(x)).
     289         454 :           if (entry != NULL) {
     290           6 :             EnsureChecked(entry, object, cmp);
     291           6 :             entry->maps_ = entry->maps_->Subtract(string_maps(), zone);
     292             :             DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
     293             :           }
     294             :         }
     295             :       }
     296             :       // Learning on false branches requires storing negative facts.
     297             :     }
     298             : 
     299     1883134 :     if (FLAG_trace_check_elimination) {
     300             :       PrintF("B%d checkmaps-table %s from B%d:\n",
     301             :              succ->block_id(),
     302             :              learned ? "learned" : "copied",
     303           0 :              from_block->block_id());
     304           0 :       Print(copy);
     305             :     }
     306             : 
     307     1883134 :     return copy;
     308             :   }
     309             : 
     310             :   // Merge this state with the other incoming state.
     311      524839 :   HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that,
     312           0 :                      HBasicBlock* pred_block, Zone* zone) {
     313      524839 :     if (that->size_ == 0) {
     314             :       // If the other state is empty, simply reset.
     315      252125 :       size_ = 0;
     316      252125 :       cursor_ = 0;
     317             :     } else {
     318      272714 :       int pred_index = succ->PredecessorIndexOf(pred_block);
     319             :       bool compact = false;
     320     1240277 :       for (int i = 0; i < size_; i++) {
     321      967563 :         HCheckTableEntry* this_entry = &entries_[i];
     322             :         HCheckTableEntry* that_entry;
     323     1979754 :         if (this_entry->object_->IsPhi() &&
     324       44631 :             this_entry->object_->block() == succ) {
     325        8185 :           HPhi* phi = HPhi::cast(this_entry->object_);
     326             :           HValue* phi_operand = phi->OperandAt(pred_index);
     327        8185 :           that_entry = that->Find(phi_operand);
     328             : 
     329             :         } else {
     330      959375 :           that_entry = that->Find(this_entry->object_);
     331             :         }
     332             : 
     333     1901046 :         if (that_entry == NULL ||
     334      969297 :             (that_entry->state_ == HCheckTableEntry::CHECKED &&
     335      969281 :              this_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) ||
     336      971260 :             (this_entry->state_ == HCheckTableEntry::CHECKED &&
     337             :              that_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE)) {
     338       34099 :           this_entry->object_ = NULL;
     339       34099 :           compact = true;
     340             :         } else {
     341             :           this_entry->maps_ =
     342      933458 :               this_entry->maps_->Union(that_entry->maps_, zone);
     343             :           this_entry->state_ = HCheckTableEntry::StateMerge(
     344     1866932 :               this_entry->state_, that_entry->state_);
     345      933466 :           if (this_entry->check_ != that_entry->check_) {
     346       12629 :             this_entry->check_ = NULL;
     347             :           }
     348             :           DCHECK(this_entry->maps_->size() > 0);
     349             :         }
     350             :       }
     351      272714 :       if (compact) Compact();
     352             :     }
     353             : 
     354      524839 :     if (FLAG_trace_check_elimination) {
     355             :       PrintF("B%d checkmaps-table merged with B%d table:\n",
     356           0 :              succ->block_id(), pred_block->block_id());
     357           0 :       Print(this);
     358             :     }
     359      524839 :     return this;
     360             :   }
     361             : 
     362      594594 :   void ReduceCheckMaps(HCheckMaps* instr) {
     363      203630 :     HValue* object = instr->value()->ActualValue();
     364      203632 :     HCheckTableEntry* entry = Find(object);
     365      203632 :     if (entry != NULL) {
     366             :       // entry found;
     367       41173 :       HGraph* graph = instr->block()->graph();
     368       25321 :       if (entry->maps_->IsSubset(instr->maps())) {
     369             :         // The first check is more strict; the second is redundant.
     370       24359 :         if (entry->check_ != NULL) {
     371             :           DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
     372        2077 :           TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
     373           0 :               instr->id(), instr->block()->block_id(), entry->check_->id()));
     374        2059 :           instr->DeleteAndReplaceWith(entry->check_);
     375             :           INC_STAT(redundant_);
     376       22300 :         } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
     377             :           DCHECK_NULL(entry->check_);
     378       14874 :           TRACE(("Marking redundant CheckMaps #%d at B%d as stability check\n",
     379           0 :                  instr->id(), instr->block()->block_id()));
     380       14874 :           instr->set_maps(entry->maps_->Copy(graph->zone()));
     381             :           instr->MarkAsStabilityCheck();
     382       14875 :           entry->state_ = HCheckTableEntry::CHECKED_STABLE;
     383        7426 :         } else if (!instr->IsStabilityCheck()) {
     384        6776 :           TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n",
     385           0 :               instr->id(), instr->block()->block_id()));
     386             :           // Mark check as dead but leave it in the graph as a checkpoint for
     387             :           // subsequent checks.
     388             :           instr->SetFlag(HValue::kIsDead);
     389        6776 :           entry->check_ = instr;
     390             :           INC_STAT(removed_);
     391             :         }
     392      203631 :         return;
     393             :       }
     394         960 :       MapSet intersection = instr->maps()->Intersect(
     395         960 :           entry->maps_, graph->zone());
     396         960 :       if (intersection->size() == 0) {
     397             :         // Intersection is empty; probably megamorphic.
     398             :         INC_STAT(empty_);
     399         169 :         entry->object_ = NULL;
     400         169 :         Compact();
     401             :       } else {
     402             :         // Update set of maps in the entry.
     403         791 :         entry->maps_ = intersection;
     404             :         // Update state of the entry.
     405         996 :         if (instr->maps_are_stable() ||
     406         205 :             entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
     407         586 :           entry->state_ = HCheckTableEntry::CHECKED_STABLE;
     408             :         }
     409         791 :         if (intersection->size() != instr->maps()->size()) {
     410             :           // Narrow set of maps in the second check maps instruction.
     411          64 :           if (entry->check_ != NULL &&
     412          33 :               entry->check_->block() == instr->block() &&
     413          10 :               entry->check_->IsCheckMaps()) {
     414             :             // There is a check in the same block so replace it with a more
     415             :             // strict check and eliminate the second check entirely.
     416          10 :             HCheckMaps* check = HCheckMaps::cast(entry->check_);
     417             :             DCHECK(!check->IsStabilityCheck());
     418          10 :             TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(),
     419           0 :                 check->block()->block_id()));
     420             :             // Update map set and ensure that the check is alive.
     421             :             check->set_maps(intersection);
     422             :             check->ClearFlag(HValue::kIsDead);
     423          10 :             TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
     424           0 :                 instr->id(), instr->block()->block_id(), entry->check_->id()));
     425          10 :             instr->DeleteAndReplaceWith(entry->check_);
     426             :           } else {
     427          13 :             TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(),
     428           0 :                 instr->block()->block_id()));
     429             :             instr->set_maps(intersection);
     430          13 :             entry->check_ = instr->IsStabilityCheck() ? NULL : instr;
     431             :           }
     432             : 
     433          23 :           if (FLAG_trace_check_elimination) {
     434           0 :             Print(this);
     435             :           }
     436             :           INC_STAT(narrowed_);
     437             :         }
     438             :       }
     439             :     } else {
     440             :       // No entry; insert a new one.
     441             :       HCheckTableEntry::State state = instr->maps_are_stable()
     442             :           ? HCheckTableEntry::CHECKED_STABLE
     443      178311 :           : HCheckTableEntry::CHECKED;
     444      178311 :       HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr;
     445             :       Insert(object, check, instr->maps(), state);
     446             :     }
     447             :   }
     448             : 
     449      131861 :   void ReduceCheckInstanceType(HCheckInstanceType* instr) {
     450       43572 :     HValue* value = instr->value()->ActualValue();
     451       43573 :     HCheckTableEntry* entry = Find(value);
     452       43572 :     if (entry == NULL) {
     453       43176 :       if (instr->check() == HCheckInstanceType::IS_STRING) {
     454       30597 :         Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED);
     455             :       }
     456       43572 :       return;
     457             :     }
     458         396 :     UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>(
     459       16050 :         entry->maps_->size(), zone());
     460       15654 :     for (int i = 0; i < entry->maps_->size(); ++i) {
     461             :       InstanceType type;
     462        7431 :       Unique<Map> map = entry->maps_->at(i);
     463             :       {
     464             :         // This is safe, because maps don't move and their instance type does
     465             :         // not change.
     466             :         AllowHandleDereference allow_deref;
     467             :         type = map.handle()->instance_type();
     468             :       }
     469        7431 :       if (instr->is_interval_check()) {
     470             :         InstanceType first_type, last_type;
     471          50 :         instr->GetCheckInterval(&first_type, &last_type);
     472         100 :         if (first_type <= type && type <= last_type) maps->Add(map, zone());
     473             :       } else {
     474             :         uint8_t mask, tag;
     475        7381 :         instr->GetCheckMaskAndTag(&mask, &tag);
     476       14020 :         if ((type & mask) == tag) maps->Add(map, zone());
     477             :       }
     478             :     }
     479         396 :     if (maps->size() == entry->maps_->size()) {
     480         343 :       TRACE(("Removing redundant CheckInstanceType #%d at B%d\n",
     481           0 :               instr->id(), instr->block()->block_id()));
     482         343 :       EnsureChecked(entry, value, instr);
     483         343 :       instr->DeleteAndReplaceWith(value);
     484             :       INC_STAT(removed_cit_);
     485          53 :     } else if (maps->size() != 0) {
     486          53 :       entry->maps_ = maps;
     487          53 :       if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
     488           0 :         entry->state_ = HCheckTableEntry::CHECKED_STABLE;
     489             :       }
     490             :     }
     491             :   }
     492             : 
     493      471983 :   void ReduceLoadNamedField(HLoadNamedField* instr) {
     494             :     // Reduce a load of the map field when it is known to be a constant.
     495      246863 :     if (!instr->access().IsMap()) {
     496             :       // Check if we introduce field maps here.
     497             :       MapSet maps = instr->maps();
     498      225120 :       if (maps != NULL) {
     499             :         DCHECK_NE(0, maps->size());
     500             :         Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE);
     501             :       }
     502      246849 :       return;
     503             :     }
     504             : 
     505       21743 :     HValue* object = instr->object()->ActualValue();
     506       21743 :     HCheckTableEntry* entry = Find(object);
     507       21757 :     if (entry == NULL || entry->maps_->size() != 1) return;  // Not a constant.
     508             : 
     509          14 :     EnsureChecked(entry, object, instr);
     510          28 :     Unique<Map> map = entry->maps_->at(0);
     511          14 :     bool map_is_stable = (entry->state_ != HCheckTableEntry::CHECKED);
     512             :     HConstant* constant = HConstant::CreateAndInsertBefore(
     513          14 :         instr->block()->graph()->zone(), map, map_is_stable, instr);
     514          14 :     instr->DeleteAndReplaceWith(constant);
     515             :     INC_STAT(loads_);
     516             :   }
     517             : 
     518       92250 :   void ReduceCheckHeapObject(HCheckHeapObject* instr) {
     519       92250 :     HValue* value = instr->value()->ActualValue();
     520       92251 :     if (Find(value) != NULL) {
     521             :       // If the object has known maps, it's definitely a heap object.
     522         574 :       instr->DeleteAndReplaceWith(value);
     523             :       INC_STAT(removed_cho_);
     524             :     }
     525       92249 :   }
     526             : 
     527      362583 :   void ReduceStoreNamedField(HStoreNamedField* instr) {
     528      181291 :     HValue* object = instr->object()->ActualValue();
     529      181292 :     if (instr->has_transition()) {
     530             :       // This store transitions the object to a new map.
     531       11105 :       Kill(object);
     532       11105 :       HConstant* c_transition = HConstant::cast(instr->transition());
     533             :       HCheckTableEntry::State state = c_transition->HasStableMapValue()
     534             :           ? HCheckTableEntry::CHECKED_STABLE
     535       11105 :           : HCheckTableEntry::CHECKED;
     536       11105 :       Insert(object, NULL, c_transition->MapValue(), state);
     537      170187 :     } else if (instr->access().IsMap()) {
     538             :       // This is a store directly to the map field of the object.
     539       40315 :       Kill(object);
     540      221607 :       if (!instr->value()->IsConstant()) return;
     541       36300 :       HConstant* c_value = HConstant::cast(instr->value());
     542             :       HCheckTableEntry::State state = c_value->HasStableMapValue()
     543             :           ? HCheckTableEntry::CHECKED_STABLE
     544       36300 :           : HCheckTableEntry::CHECKED;
     545       36300 :       Insert(object, NULL, c_value->MapValue(), state);
     546             :     } else {
     547             :       // If the instruction changes maps, it should be handled above.
     548      129872 :       CHECK(!instr->CheckChangesFlag(kMaps));
     549             :     }
     550             :   }
     551             : 
     552       21996 :   void ReduceCompareMap(HCompareMap* instr) {
     553       21996 :     HCheckTableEntry* entry = Find(instr->value()->ActualValue());
     554       21996 :     if (entry == NULL) return;
     555             : 
     556        6624 :     EnsureChecked(entry, instr->value(), instr);
     557             : 
     558             :     int succ;
     559       13250 :     if (entry->maps_->Contains(instr->map())) {
     560        6553 :       if (entry->maps_->size() != 1) {
     561        6625 :         TRACE(("CompareMap #%d for #%d at B%d can't be eliminated: "
     562             :                "ambiguous set of maps\n", instr->id(), instr->value()->id(),
     563           0 :                instr->block()->block_id()));
     564             :         return;
     565             :       }
     566             :       succ = 0;
     567             :       INC_STAT(compares_true_);
     568             :     } else {
     569             :       succ = 1;
     570             :       INC_STAT(compares_false_);
     571             :     }
     572             : 
     573        3267 :     TRACE(("Marking redundant CompareMap #%d for #%d at B%d as %s\n",
     574             :         instr->id(), instr->value()->id(), instr->block()->block_id(),
     575           0 :         succ == 0 ? "true" : "false"));
     576             :     instr->set_known_successor_index(succ);
     577             : 
     578        3267 :     int unreachable_succ = 1 - succ;
     579        3267 :     instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
     580             :   }
     581             : 
     582       43453 :   void ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) {
     583       42799 :     HValue* left = instr->left()->ActualValue();
     584       42800 :     HCheckTableEntry* le = Find(left);
     585       42800 :     if (le == NULL) return;
     586        1482 :     HValue* right = instr->right()->ActualValue();
     587        1482 :     HCheckTableEntry* re = Find(right);
     588        1482 :     if (re == NULL) return;
     589             : 
     590         655 :     EnsureChecked(le, left, instr);
     591         655 :     EnsureChecked(re, right, instr);
     592             : 
     593             :     // TODO(bmeurer): Add a predicate here instead of computing the intersection
     594         655 :     MapSet intersection = le->maps_->Intersect(re->maps_, zone());
     595         655 :     if (intersection->size() > 0) return;
     596             : 
     597           0 :     TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n",
     598           0 :         instr->id(), instr->block()->block_id()));
     599             :     int succ = 1;
     600             :     instr->set_known_successor_index(succ);
     601             : 
     602             :     int unreachable_succ = 1 - succ;
     603           0 :     instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
     604             :   }
     605             : 
     606         460 :   void ReduceIsStringAndBranch(HIsStringAndBranch* instr) {
     607         454 :     HValue* value = instr->value()->ActualValue();
     608         454 :     HCheckTableEntry* entry = Find(value);
     609         454 :     if (entry == NULL) return;
     610           6 :     EnsureChecked(entry, value, instr);
     611             :     int succ;
     612           6 :     if (entry->maps_->IsSubset(string_maps())) {
     613           6 :       TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n",
     614           0 :              instr->id(), instr->block()->block_id()));
     615             :       succ = 0;
     616             :     } else {
     617           6 :       MapSet intersection = entry->maps_->Intersect(string_maps(), zone());
     618           6 :       if (intersection->size() > 0) return;
     619           6 :       TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n",
     620           0 :             instr->id(), instr->block()->block_id()));
     621             :       succ = 1;
     622             :     }
     623             :     instr->set_known_successor_index(succ);
     624           6 :     int unreachable_succ = 1 - succ;
     625           6 :     instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
     626             :   }
     627             : 
     628        1107 :   void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
     629         769 :     HValue* object = instr->object()->ActualValue();
     630         769 :     HCheckTableEntry* entry = Find(object);
     631             :     // Can only learn more about an object that already has a known set of maps.
     632         769 :     if (entry == NULL) {
     633         585 :       Kill(object);
     634        1354 :       return;
     635             :     }
     636         184 :     EnsureChecked(entry, object, instr);
     637         368 :     if (entry->maps_->Contains(instr->original_map())) {
     638             :       // If the object has the original map, it will be transitioned.
     639         169 :       UniqueSet<Map>* maps = entry->maps_->Copy(zone());
     640         169 :       maps->Remove(instr->original_map());
     641         169 :       maps->Add(instr->transitioned_map(), zone());
     642             :       HCheckTableEntry::State state =
     643         169 :           (entry->state_ == HCheckTableEntry::CHECKED_STABLE &&
     644             :            instr->map_is_stable())
     645             :               ? HCheckTableEntry::CHECKED_STABLE
     646         169 :               : HCheckTableEntry::CHECKED;
     647         169 :       Kill(object);
     648             :       Insert(object, NULL, maps, state);
     649             :     } else {
     650             :       // Object does not have the given map, thus the transition is redundant.
     651          15 :       instr->DeleteAndReplaceWith(object);
     652             :       INC_STAT(transitions_);
     653             :     }
     654             :   }
     655             : 
     656       16427 :   void EnsureChecked(HCheckTableEntry* entry,
     657             :                      HValue* value,
     658             :                      HInstruction* instr) {
     659       32854 :     if (entry->state_ != HCheckTableEntry::UNCHECKED_STABLE) return;
     660        1444 :     HGraph* graph = instr->block()->graph();
     661             :     HCheckMaps* check = HCheckMaps::CreateAndInsertBefore(
     662        1444 :         graph->zone(), value, entry->maps_->Copy(graph->zone()), true, instr);
     663             :     check->MarkAsStabilityCheck();
     664         722 :     entry->state_ = HCheckTableEntry::CHECKED_STABLE;
     665         722 :     entry->check_ = NULL;
     666             :   }
     667             : 
     668             :   // Kill everything in the table.
     669             :   void Kill() {
     670        2805 :     size_ = 0;
     671        2805 :     cursor_ = 0;
     672             :   }
     673             : 
     674             :   // Kill all unstable entries in the table.
     675     1378668 :   void KillUnstableEntries() {
     676             :     bool compact = false;
     677     3185306 :     for (int i = 0; i < size_; ++i) {
     678     1806638 :       HCheckTableEntry* entry = &entries_[i];
     679             :       DCHECK_NOT_NULL(entry->object_);
     680     1806638 :       if (entry->state_ == HCheckTableEntry::CHECKED) {
     681       67605 :         entry->object_ = NULL;
     682             :         compact = true;
     683             :       } else {
     684             :         // All checked stable entries become unchecked stable.
     685     1739033 :         entry->state_ = HCheckTableEntry::UNCHECKED_STABLE;
     686     1739033 :         entry->check_ = NULL;
     687             :       }
     688             :     }
     689     1378668 :     if (compact) Compact();
     690     1378667 :   }
     691             : 
     692             :   // Kill everything in the table that may alias {object}.
     693       56178 :   void Kill(HValue* object) {
     694             :     bool compact = false;
     695      215517 :     for (int i = 0; i < size_; i++) {
     696      159339 :       HCheckTableEntry* entry = &entries_[i];
     697             :       DCHECK_NOT_NULL(entry->object_);
     698      318678 :       if (phase_->aliasing_->MayAlias(entry->object_, object)) {
     699       36485 :         entry->object_ = NULL;
     700             :         compact = true;
     701             :       }
     702             :     }
     703       56178 :     if (compact) Compact();
     704             :     DCHECK_NULL(Find(object));
     705       56178 :   }
     706             : 
     707       92567 :   void Compact() {
     708             :     // First, compact the array in place.
     709       92567 :     int max = size_, dest = 0, old_cursor = cursor_;
     710      590938 :     for (int i = 0; i < max; i++) {
     711      498371 :       if (entries_[i].object_ != NULL) {
     712      360007 :         if (dest != i) entries_[dest] = entries_[i];
     713      360007 :         dest++;
     714             :       } else {
     715      138364 :         if (i < old_cursor) cursor_--;
     716      138364 :         size_--;
     717             :       }
     718             :     }
     719             :     DCHECK(size_ == dest);
     720             :     DCHECK(cursor_ <= size_);
     721             : 
     722             :     // Preserve the age of the entries by moving the older entries to the end.
     723      185134 :     if (cursor_ == size_) return;  // Cursor already points at end.
     724        4995 :     if (cursor_ != 0) {
     725             :       // | L = oldest |   R = newest   |       |
     726             :       //              ^ cursor         ^ size  ^ MAX
     727             :       HCheckTableEntry tmp_entries[kMaxTrackedObjects];
     728         702 :       int L = cursor_;
     729         702 :       int R = size_ - cursor_;
     730             : 
     731         702 :       MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry));
     732         702 :       MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry));
     733         702 :       MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry));
     734             :     }
     735             : 
     736        4995 :     cursor_ = size_;  // Move cursor to end.
     737             :   }
     738             : 
     739           0 :   static void Print(HCheckTable* table) {
     740           0 :     if (table == NULL) {
     741           0 :       PrintF("  unreachable\n");
     742           0 :       return;
     743             :     }
     744             : 
     745           0 :     for (int i = 0; i < table->size_; i++) {
     746           0 :       HCheckTableEntry* entry = &table->entries_[i];
     747             :       DCHECK(entry->object_ != NULL);
     748             :       PrintF("  checkmaps-table @%d: %s #%d ", i,
     749           0 :              entry->object_->IsPhi() ? "phi" : "object", entry->object_->id());
     750           0 :       if (entry->check_ != NULL) {
     751           0 :         PrintF("check #%d ", entry->check_->id());
     752             :       }
     753           0 :       MapSet list = entry->maps_;
     754             :       PrintF("%d %s maps { ", list->size(),
     755           0 :              HCheckTableEntry::State2String(entry->state_));
     756           0 :       for (int j = 0; j < list->size(); j++) {
     757           0 :         if (j > 0) PrintF(", ");
     758           0 :         PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
     759             :       }
     760           0 :       PrintF(" }\n");
     761             :     }
     762             :   }
     763             : 
     764     1723022 :   HCheckTableEntry* Find(HValue* object) {
     765     6668926 :     for (int i = size_ - 1; i >= 0; i--) {
     766             :       // Search from most-recently-inserted to least-recently-inserted.
     767     5940832 :       HCheckTableEntry* entry = &entries_[i];
     768             :       DCHECK(entry->object_ != NULL);
     769    11881671 :       if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry;
     770             :     }
     771             :     return NULL;
     772             :   }
     773             : 
     774       62776 :   void Insert(HValue* object,
     775             :               HInstruction* check,
     776             :               Unique<Map> map,
     777       62776 :               HCheckTableEntry::State state) {
     778      125552 :     Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state);
     779       62777 :   }
     780             : 
     781             :   void Insert(HValue* object,
     782             :               HInstruction* check,
     783             :               MapSet maps,
     784             :               HCheckTableEntry::State state) {
     785             :     DCHECK(state != HCheckTableEntry::UNCHECKED_STABLE || check == NULL);
     786      292638 :     HCheckTableEntry* entry = &entries_[cursor_++];
     787      292638 :     entry->object_ = object;
     788      292638 :     entry->check_ = check;
     789      292638 :     entry->maps_ = maps;
     790      292638 :     entry->state_ = state;
     791             :     // If the table becomes full, wrap around and overwrite older entries.
     792      292638 :     if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
     793      292638 :     if (size_ < kMaxTrackedObjects) size_++;
     794             :   }
     795             : 
     796             :   Zone* zone() const { return phase_->zone(); }
     797             :   MapSet string_maps() const { return phase_->string_maps(); }
     798             : 
     799             :   friend class HCheckMapsEffects;
     800             :   friend class HCheckEliminationPhase;
     801             : 
     802             :   HCheckEliminationPhase* phase_;
     803             :   HCheckTableEntry entries_[kMaxTrackedObjects];
     804             :   int16_t cursor_;  // Must be <= kMaxTrackedObjects
     805             :   int16_t size_;    // Must be <= kMaxTrackedObjects
     806             :   STATIC_ASSERT(kMaxTrackedObjects < (1 << 15));
     807             : };
     808             : 
     809             : 
     810             : // Collects instructions that can cause effects that invalidate information
     811             : // needed for check elimination.
     812             : class HCheckMapsEffects : public ZoneObject {
     813             :  public:
     814       52641 :   explicit HCheckMapsEffects(Zone* zone) : objects_(0, zone) { }
     815             : 
     816             :   // Effects are _not_ disabled.
     817             :   inline bool Disabled() const { return false; }
     818             : 
     819             :   // Process a possibly side-effecting instruction.
     820     3055151 :   void Process(HInstruction* instr, Zone* zone) {
     821     3055151 :     switch (instr->opcode()) {
     822             :       case HValue::kStoreNamedField: {
     823       12913 :         HStoreNamedField* store = HStoreNamedField::cast(instr);
     824       28390 :         if (store->access().IsMap() || store->has_transition()) {
     825             :           objects_.Add(store->object(), zone);
     826             :         }
     827             :         break;
     828             :       }
     829             :       case HValue::kTransitionElementsKind: {
     830             :         objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone);
     831          29 :         break;
     832             :       }
     833             :       default: {
     834             :         flags_.Add(instr->ChangesFlags());
     835     3039645 :         break;
     836             :       }
     837             :     }
     838     3055151 :   }
     839             : 
     840             :   // Apply these effects to the given check elimination table.
     841       50778 :   void Apply(HCheckTable* table) {
     842       50778 :     if (flags_.Contains(kOsrEntries)) {
     843             :       // Uncontrollable map modifications; kill everything.
     844             :       table->Kill();
     845       50778 :       return;
     846             :     }
     847             : 
     848             :     // Kill all unstable entries.
     849       72182 :     if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) {
     850       28502 :       table->KillUnstableEntries();
     851             :     }
     852             : 
     853             :     // Kill maps for each object contained in these effects.
     854       58350 :     for (int i = 0; i < objects_.length(); ++i) {
     855       62354 :       table->Kill(objects_[i]->ActualValue());
     856             :     }
     857             :   }
     858             : 
     859             :   // Union these effects with the other effects.
     860        7484 :   void Union(HCheckMapsEffects* that, Zone* zone) {
     861             :     flags_.Add(that->flags_);
     862       15942 :     for (int i = 0; i < that->objects_.length(); ++i) {
     863        8945 :       objects_.Add(that->objects_[i], zone);
     864             :     }
     865        7484 :   }
     866             : 
     867             :  private:
     868             :   ZoneList<HValue*> objects_;
     869             :   GVNFlagSet flags_;
     870             : };
     871             : 
     872             : 
     873             : // The main routine of the analysis phase. Use the HFlowEngine for either a
     874             : // local or a global analysis.
     875      283729 : void HCheckEliminationPhase::Run() {
     876      567458 :   HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone());
     877             :   HCheckTable* table = new(zone()) HCheckTable(this);
     878             : 
     879             :   if (GLOBAL) {
     880             :     // Perform a global analysis.
     881      283729 :     engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
     882             :   } else {
     883             :     // Perform only local analysis.
     884             :     for (int i = 0; i < graph()->blocks()->length(); i++) {
     885             :       table->Kill();
     886             :       engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
     887             :     }
     888             :   }
     889             : 
     890             :   if (FLAG_trace_check_elimination) PrintStats();
     891      283727 : }
     892             : 
     893             : 
     894             : // Are we eliminated yet?
     895           0 : void HCheckEliminationPhase::PrintStats() {
     896             : #if DEBUG
     897             :   #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_)
     898             : #else
     899             :   #define PRINT_STAT(x)
     900             : #endif
     901             :   PRINT_STAT(redundant);
     902             :   PRINT_STAT(removed);
     903             :   PRINT_STAT(removed_cho);
     904             :   PRINT_STAT(removed_cit);
     905             :   PRINT_STAT(narrowed);
     906             :   PRINT_STAT(loads);
     907             :   PRINT_STAT(empty);
     908             :   PRINT_STAT(compares_true);
     909             :   PRINT_STAT(compares_false);
     910             :   PRINT_STAT(transitions);
     911           0 : }
     912             : 
     913             : }  // namespace internal
     914             : }  // namespace v8

Generated by: LCOV version 1.10