LCOV - code coverage report
Current view: top level - src/crankshaft - hydrogen-load-elimination.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 162 190 85.3 %
Date: 2017-04-26 Functions: 19 20 95.0 %

          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-load-elimination.h"
       6             : 
       7             : #include "src/crankshaft/hydrogen-alias-analysis.h"
       8             : #include "src/crankshaft/hydrogen-flow-engine.h"
       9             : #include "src/crankshaft/hydrogen-instructions.h"
      10             : #include "src/objects-inl.h"
      11             : 
      12             : namespace v8 {
      13             : namespace internal {
      14             : 
      15             : #define GLOBAL true
      16             : #define TRACE(x) if (FLAG_trace_load_elimination) PrintF x
      17             : 
      18             : static const int kMaxTrackedFields = 16;
      19             : static const int kMaxTrackedObjects = 5;
      20             : 
      21             : // An element in the field approximation list.
      22             : class HFieldApproximation : public ZoneObject {
      23             :  public:  // Just a data blob.
      24             :   HValue* object_;
      25             :   HValue* last_value_;
      26             :   HFieldApproximation* next_;
      27             : 
      28             :   // Recursively copy the entire linked list of field approximations.
      29      418631 :   HFieldApproximation* Copy(Zone* zone) {
      30      418631 :     HFieldApproximation* copy = new(zone) HFieldApproximation();
      31      418631 :     copy->object_ = this->object_;
      32      418631 :     copy->last_value_ = this->last_value_;
      33      418631 :     copy->next_ = this->next_ == NULL ? NULL : this->next_->Copy(zone);
      34      418631 :     return copy;
      35             :   }
      36             : };
      37             : 
      38             : 
      39             : // The main datastructure used during load/store elimination. Each in-object
      40             : // field is tracked separately. For each field, store a list of known field
      41             : // values for known objects.
      42             : class HLoadEliminationTable : public ZoneObject {
      43             :  public:
      44             :   HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing)
      45     2690309 :     : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { }
      46             : 
      47             :   // The main processing of instructions.
      48    23992560 :   HLoadEliminationTable* Process(HInstruction* instr, Zone* zone) {
      49    23992560 :     switch (instr->opcode()) {
      50             :       case HValue::kLoadNamedField: {
      51             :         HLoadNamedField* l = HLoadNamedField::cast(instr);
      52      284140 :         TRACE((" process L%d field %d (o%d)\n",
      53             :                instr->id(),
      54             :                FieldOf(l->access()),
      55           0 :                l->object()->ActualValue()->id()));
      56      284140 :         HValue* result = load(l);
      57      284137 :         if (result != instr && l->CanBeReplacedWith(result)) {
      58             :           // The load can be replaced with a previous load or a value.
      59           0 :           TRACE(("  replace L%d -> v%d\n", instr->id(), result->id()));
      60           0 :           instr->DeleteAndReplaceWith(result);
      61             :         }
      62             :         break;
      63             :       }
      64             :       case HValue::kStoreNamedField: {
      65             :         HStoreNamedField* s = HStoreNamedField::cast(instr);
      66      185851 :         TRACE((" process S%d field %d (o%d) = v%d\n",
      67             :                instr->id(),
      68             :                FieldOf(s->access()),
      69             :                s->object()->ActualValue()->id(),
      70           0 :                s->value()->id()));
      71      185851 :         HValue* result = store(s);
      72      185851 :         if (result == NULL) {
      73             :           // The store is redundant. Remove it.
      74        4391 :           TRACE(("  remove S%d\n", instr->id()));
      75        4391 :           instr->DeleteAndReplaceWith(NULL);
      76             :         }
      77             :         break;
      78             :       }
      79             :       case HValue::kTransitionElementsKind: {
      80             :         HTransitionElementsKind* t = HTransitionElementsKind::cast(instr);
      81         801 :         HValue* object = t->object()->ActualValue();
      82         801 :         KillFieldInternal(object, FieldOf(JSArray::kElementsOffset), NULL);
      83         801 :         KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
      84         801 :         break;
      85             :       }
      86             :       default: {
      87    23521822 :         if (instr->CheckChangesFlag(kInobjectFields)) {
      88     1811045 :           TRACE((" kill-all i%d\n", instr->id()));
      89             :           Kill();
      90             :           break;
      91             :         }
      92    21710777 :         if (instr->CheckChangesFlag(kMaps)) {
      93           0 :           TRACE((" kill-maps i%d\n", instr->id()));
      94           0 :           KillOffset(JSObject::kMapOffset);
      95             :         }
      96    21710781 :         if (instr->CheckChangesFlag(kElementsKind)) {
      97           0 :           TRACE((" kill-elements-kind i%d\n", instr->id()));
      98           0 :           KillOffset(JSObject::kMapOffset);
      99           0 :           KillOffset(JSObject::kElementsOffset);
     100             :         }
     101    21710781 :         if (instr->CheckChangesFlag(kElementsPointer)) {
     102        2589 :           TRACE((" kill-elements i%d\n", instr->id()));
     103        2589 :           KillOffset(JSObject::kElementsOffset);
     104             :         }
     105    21710781 :         if (instr->CheckChangesFlag(kOsrEntries)) {
     106        2369 :           TRACE((" kill-osr i%d\n", instr->id()));
     107             :           Kill();
     108             :         }
     109             :       }
     110             :       // Improvements possible:
     111             :       // - learn from HCheckMaps for field 0
     112             :       // - remove unobservable stores (write-after-write)
     113             :       // - track cells
     114             :       // - track globals
     115             :       // - track roots
     116             :     }
     117    23992616 :     return this;
     118             :   }
     119             : 
     120             :   // Support for global analysis with HFlowEngine: Merge given state with
     121             :   // the other incoming state.
     122     3289242 :   static HLoadEliminationTable* Merge(HLoadEliminationTable* succ_state,
     123             :                                       HBasicBlock* succ_block,
     124             :                                       HLoadEliminationTable* pred_state,
     125             :                                       HBasicBlock* pred_block,
     126             :                                       Zone* zone) {
     127             :     DCHECK(pred_state != NULL);
     128     3289242 :     if (succ_state == NULL) {
     129     2406577 :       return pred_state->Copy(succ_block, pred_block, zone);
     130             :     } else {
     131      882665 :       return succ_state->Merge(succ_block, pred_state, pred_block, zone);
     132             :     }
     133             :   }
     134             : 
     135             :   // Support for global analysis with HFlowEngine: Given state merged with all
     136             :   // the other incoming states, prepare it for use.
     137             :   static HLoadEliminationTable* Finish(HLoadEliminationTable* state,
     138             :                                        HBasicBlock* block,
     139             :                                        Zone* zone) {
     140             :     DCHECK(state != NULL);
     141             :     return state;
     142             :   }
     143             : 
     144             :  private:
     145             :   // Copy state to successor block.
     146     2406577 :   HLoadEliminationTable* Copy(HBasicBlock* succ, HBasicBlock* from_block,
     147             :                               Zone* zone) {
     148             :     HLoadEliminationTable* copy =
     149     2406579 :         new(zone) HLoadEliminationTable(zone, aliasing_);
     150     6564827 :     copy->EnsureFields(fields_.length());
     151     6564828 :     for (int i = 0; i < fields_.length(); i++) {
     152     1751664 :       copy->fields_[i] = fields_[i] == NULL ? NULL : fields_[i]->Copy(zone);
     153             :     }
     154     2406582 :     if (FLAG_trace_load_elimination) {
     155           0 :       TRACE((" copy-to B%d\n", succ->block_id()));
     156           0 :       copy->Print();
     157             :     }
     158     2406582 :     return copy;
     159             :   }
     160             : 
     161             :   // Merge this state with the other incoming state.
     162      882663 :   HLoadEliminationTable* Merge(HBasicBlock* succ, HLoadEliminationTable* that,
     163             :                                HBasicBlock* that_block, Zone* zone) {
     164     2256003 :     if (that->fields_.length() < fields_.length()) {
     165             :       // Drop fields not in the other table.
     166             :       fields_.Rewind(that->fields_.length());
     167             :     }
     168     1338605 :     for (int i = 0; i < fields_.length(); i++) {
     169             :       // Merge the field approximations for like fields.
     170      227971 :       HFieldApproximation* approx = fields_[i];
     171             :       HFieldApproximation* prev = NULL;
     172      555823 :       while (approx != NULL) {
     173             :         // TODO(titzer): Merging is O(N * M); sort?
     174       99881 :         HFieldApproximation* other = that->Find(approx->object_, i);
     175       99881 :         if (other == NULL || !Equal(approx->last_value_, other->last_value_)) {
     176             :           // Kill an entry that doesn't agree with the other value.
     177       34782 :           if (prev != NULL) {
     178          47 :             prev->next_ = approx->next_;
     179             :           } else {
     180       34735 :             fields_[i] = approx->next_;
     181             :           }
     182       34782 :           approx = approx->next_;
     183       34782 :           continue;
     184             :         }
     185             :         prev = approx;
     186       65099 :         approx = approx->next_;
     187             :       }
     188             :     }
     189      882663 :     if (FLAG_trace_load_elimination) {
     190           0 :       TRACE((" merge-to B%d\n", succ->block_id()));
     191           0 :       Print();
     192             :     }
     193      882663 :     return this;
     194             :   }
     195             : 
     196             :   friend class HLoadEliminationEffects;  // Calls Kill() and others.
     197             :   friend class HLoadEliminationPhase;
     198             : 
     199             :  private:
     200             :   // Process a load instruction, updating internal table state. If a previous
     201             :   // load or store for this object and field exists, return the new value with
     202             :   // which the load should be replaced. Otherwise, return {instr}.
     203      284139 :   HValue* load(HLoadNamedField* instr) {
     204             :     // There must be no loads from non observable in-object properties.
     205             :     DCHECK(!instr->access().IsInobject() ||
     206             :            instr->access().existing_inobject_property());
     207             : 
     208             :     int field = FieldOf(instr->access());
     209      284139 :     if (field < 0) return instr;
     210             : 
     211      253899 :     HValue* object = instr->object()->ActualValue();
     212      253900 :     HFieldApproximation* approx = FindOrCreate(object, field);
     213             : 
     214      284110 :     if (approx->last_value_ == NULL) {
     215             :       // Load is not redundant. Fill out a new entry.
     216      223684 :       approx->last_value_ = instr;
     217      223684 :       return instr;
     218       30213 :     } else if (approx->last_value_->block()->EqualToOrDominates(
     219       30213 :         instr->block())) {
     220             :       // Eliminate the load. Reuse previously stored value or load instruction.
     221       30207 :       return approx->last_value_;
     222             :     } else {
     223             :       return instr;
     224             :     }
     225             :   }
     226             : 
     227             :   // Process a store instruction, updating internal table state. If a previous
     228             :   // store to the same object and field makes this store redundant (e.g. because
     229             :   // the stored values are the same), return NULL indicating that this store
     230             :   // instruction is redundant. Otherwise, return {instr}.
     231      362271 :   HValue* store(HStoreNamedField* instr) {
     232      556798 :     if (instr->access().IsInobject() &&
     233      185851 :         !instr->access().existing_inobject_property()) {
     234        8391 :       TRACE(("  skipping non existing property initialization store\n"));
     235        8391 :       return instr;
     236             :     }
     237             : 
     238             :     int field = FieldOf(instr->access());
     239      177460 :     if (field < 0) return KillIfMisaligned(instr);
     240             : 
     241      176420 :     HValue* object = instr->object()->ActualValue();
     242             :     HValue* value = instr->value();
     243             : 
     244      176420 :     if (instr->has_transition()) {
     245             :       // A transition introduces a new field and alters the map of the object.
     246             :       // Since the field in the object is new, it cannot alias existing entries.
     247       10436 :       KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
     248             :     } else {
     249             :       // Kill non-equivalent may-alias entries.
     250      165984 :       KillFieldInternal(object, field, value);
     251             :     }
     252      176420 :     HFieldApproximation* approx = FindOrCreate(object, field);
     253             : 
     254      176420 :     if (Equal(approx->last_value_, value)) {
     255             :       // The store is redundant because the field already has this value.
     256             :       return NULL;
     257             :     } else {
     258             :       // The store is not redundant. Update the entry.
     259      172029 :       approx->last_value_ = value;
     260      172029 :       return instr;
     261             :     }
     262             :   }
     263             : 
     264             :   // Kill everything in this table.
     265             :   void Kill() {
     266             :     fields_.Rewind(0);
     267             :   }
     268             : 
     269             :   // Kill all entries matching the given offset.
     270        2627 :   void KillOffset(int offset) {
     271             :     int field = FieldOf(offset);
     272        2627 :     if (field >= 0 && field < fields_.length()) {
     273        2597 :       fields_[field] = NULL;
     274             :     }
     275        2627 :   }
     276             : 
     277             :   // Kill all entries aliasing the given store.
     278        1257 :   void KillStore(HStoreNamedField* s) {
     279             :     int field = FieldOf(s->access());
     280        1257 :     if (field >= 0) {
     281        1254 :       KillFieldInternal(s->object()->ActualValue(), field, s->value());
     282             :     } else {
     283           3 :       KillIfMisaligned(s);
     284             :     }
     285        1257 :   }
     286             : 
     287             :   // Kill multiple entries in the case of a misaligned store.
     288        1043 :   HValue* KillIfMisaligned(HStoreNamedField* instr) {
     289             :     HObjectAccess access = instr->access();
     290        1043 :     if (access.IsInobject()) {
     291             :       int offset = access.offset();
     292         285 :       if ((offset % kPointerSize) != 0) {
     293             :         // Kill the field containing the first word of the access.
     294           0 :         HValue* object = instr->object()->ActualValue();
     295           0 :         int field = offset / kPointerSize;
     296           0 :         KillFieldInternal(object, field, NULL);
     297             : 
     298             :         // Kill the next field in case of overlap.
     299           0 :         int size = access.representation().size();
     300           0 :         int next_field = (offset + size - 1) / kPointerSize;
     301           0 :         if (next_field != field) KillFieldInternal(object, next_field, NULL);
     302             :       }
     303             :     }
     304        1043 :     return instr;
     305             :   }
     306             : 
     307             :   // Find an entry for the given object and field pair.
     308       99881 :   HFieldApproximation* Find(HValue* object, int field) {
     309             :     // Search for a field approximation for this object.
     310      199762 :     HFieldApproximation* approx = fields_[field];
     311      243206 :     while (approx != NULL) {
     312      246324 :       if (aliasing_->MustAlias(object, approx->object_)) return approx;
     313       43444 :       approx = approx->next_;
     314             :     }
     315             :     return NULL;
     316             :   }
     317             : 
     318             :   // Find or create an entry for the given object and field pair.
     319      430316 :   HFieldApproximation* FindOrCreate(HValue* object, int field) {
     320      430316 :     EnsureFields(field + 1);
     321             : 
     322             :     // Search for a field approximation for this object.
     323     1256340 :     HFieldApproximation* approx = fields_[field];
     324             :     int count = 0;
     325      923059 :     while (approx != NULL) {
     326      194070 :       if (aliasing_->MustAlias(object, approx->object_)) return approx;
     327       62431 :       count++;
     328       62431 :       approx = approx->next_;
     329             :     }
     330             : 
     331      395710 :     if (count >= kMaxTrackedObjects) {
     332             :       // Pull the last entry off the end and repurpose it for this object.
     333             :       approx = ReuseLastApproximation(field);
     334             :     } else {
     335             :       // Allocate a new entry.
     336      789570 :       approx = new(zone_) HFieldApproximation();
     337             :     }
     338             : 
     339             :     // Insert the entry at the head of the list.
     340      395712 :     approx->object_ = object;
     341      395712 :     approx->last_value_ = NULL;
     342      395712 :     approx->next_ = fields_[field];
     343      395712 :     fields_[field] = approx;
     344             : 
     345      395712 :     return approx;
     346             :   }
     347             : 
     348             :   // Kill all entries for a given field that _may_ alias the given object
     349             :   // and do _not_ have the given value.
     350      179276 :   void KillFieldInternal(HValue* object, int field, HValue* value) {
     351      379862 :     if (field >= fields_.length()) return;  // Nothing to do.
     352             : 
     353       66843 :     HFieldApproximation* approx = fields_[field];
     354             :     HFieldApproximation* prev = NULL;
     355      181833 :     while (approx != NULL) {
     356       96294 :       if (aliasing_->MayAlias(object, approx->object_)) {
     357       26312 :         if (!Equal(approx->last_value_, value)) {
     358             :           // Kill an aliasing entry that doesn't agree on the value.
     359       21848 :           if (prev != NULL) {
     360         538 :             prev->next_ = approx->next_;
     361             :           } else {
     362       21310 :             fields_[field] = approx->next_;
     363             :           }
     364       21848 :           approx = approx->next_;
     365       21848 :           continue;
     366             :         }
     367             :       }
     368             :       prev = approx;
     369       26299 :       approx = approx->next_;
     370             :     }
     371             :   }
     372             : 
     373      327037 :   bool Equal(HValue* a, HValue* b) {
     374      282450 :     if (a == b) return true;
     375      261989 :     if (a != NULL && b != NULL && a->CheckFlag(HValue::kUseGVN)) {
     376       44158 :       return a->Equals(b);
     377             :     }
     378             :     return false;
     379             :   }
     380             : 
     381             :   // Remove the last approximation for a field so that it can be reused.
     382             :   // We reuse the last entry because it was the first inserted and is thus
     383             :   // farthest away from the current instruction.
     384             :   HFieldApproximation* ReuseLastApproximation(int field) {
     385        1852 :     HFieldApproximation* approx = fields_[field];
     386             :     DCHECK(approx != NULL);
     387             : 
     388             :     HFieldApproximation* prev = NULL;
     389        4638 :     while (approx->next_ != NULL) {
     390             :       prev = approx;
     391             :       approx = approx->next_;
     392             :     }
     393         926 :     if (prev != NULL) prev->next_ = NULL;
     394             :     return approx;
     395             :   }
     396             : 
     397             :   // Compute the field index for the given object access; -1 if not tracked.
     398             :   int FieldOf(HObjectAccess access) {
     399      462856 :     return access.IsInobject() ? FieldOf(access.offset()) : -1;
     400             :   }
     401             : 
     402             :   // Compute the field index for the given in-object offset; -1 if not tracked.
     403             :   int FieldOf(int offset) {
     404      461833 :     if (offset >= kMaxTrackedFields * kPointerSize) return -1;
     405      456644 :     if ((offset % kPointerSize) != 0) return -1;  // Ignore misaligned accesses.
     406      434198 :     return offset / kPointerSize;
     407             :   }
     408             : 
     409             :   // Ensure internal storage for the given number of fields.
     410     2836888 :   void EnsureFields(int num_fields) {
     411     2836888 :     if (fields_.length() < num_fields) {
     412      493493 :       fields_.AddBlock(NULL, num_fields - fields_.length(), zone_);
     413             :     }
     414     2836888 :   }
     415             : 
     416             :   // Print this table to stdout.
     417           0 :   void Print() {
     418           0 :     for (int i = 0; i < fields_.length(); i++) {
     419           0 :       PrintF("  field %d: ", i);
     420           0 :       for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) {
     421           0 :         PrintF("[o%d =", a->object_->id());
     422           0 :         if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id());
     423           0 :         PrintF("] ");
     424             :       }
     425           0 :       PrintF("\n");
     426             :     }
     427           0 :   }
     428             : 
     429             :   Zone* zone_;
     430             :   ZoneList<HFieldApproximation*> fields_;
     431             :   HAliasAnalyzer* aliasing_;
     432             : };
     433             : 
     434             : 
     435             : // Support for HFlowEngine: collect store effects within loops.
     436             : class HLoadEliminationEffects : public ZoneObject {
     437             :  public:
     438             :   explicit HLoadEliminationEffects(Zone* zone)
     439      107132 :     : zone_(zone), stores_(5, zone) { }
     440             : 
     441             :   inline bool Disabled() {
     442             :     return false;  // Effects are _not_ disabled.
     443             :   }
     444             : 
     445             :   // Process a possibly side-effecting instruction.
     446     4047903 :   void Process(HInstruction* instr, Zone* zone) {
     447     8095806 :     if (instr->IsStoreNamedField()) {
     448       15814 :       stores_.Add(HStoreNamedField::cast(instr), zone_);
     449             :     } else {
     450             :       flags_.Add(instr->ChangesFlags());
     451             :     }
     452     4047903 :   }
     453             : 
     454             :   // Apply these effects to the given load elimination table.
     455       51906 :   void Apply(HLoadEliminationTable* table) {
     456             :     // Loads must not be hoisted past the OSR entry, therefore we kill
     457             :     // everything if we see an OSR entry.
     458       54350 :     if (flags_.Contains(kInobjectFields) || flags_.Contains(kOsrEntries)) {
     459             :       table->Kill();
     460       51906 :       return;
     461             :     }
     462        4869 :     if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) {
     463          19 :       table->KillOffset(JSObject::kMapOffset);
     464             :     }
     465        4869 :     if (flags_.Contains(kElementsKind) || flags_.Contains(kElementsPointer)) {
     466          19 :       table->KillOffset(JSObject::kElementsOffset);
     467             :     }
     468             : 
     469             :     // Kill non-agreeing fields for each store contained in these effects.
     470        4958 :     for (int i = 0; i < stores_.length(); i++) {
     471        6215 :       table->KillStore(stores_[i]);
     472             :     }
     473             :   }
     474             : 
     475             :   // Union these effects with the other effects.
     476        7568 :   void Union(HLoadEliminationEffects* that, Zone* zone) {
     477             :     flags_.Add(that->flags_);
     478       19422 :     for (int i = 0; i < that->stores_.length(); i++) {
     479       13997 :       stores_.Add(that->stores_[i], zone);
     480             :     }
     481        7568 :   }
     482             : 
     483             :  private:
     484             :   Zone* zone_;
     485             :   GVNFlagSet flags_;
     486             :   ZoneList<HStoreNamedField*> stores_;
     487             : };
     488             : 
     489             : 
     490             : // The main routine of the analysis phase. Use the HFlowEngine for either a
     491             : // local or a global analysis.
     492      283730 : void HLoadEliminationPhase::Run() {
     493             :   HFlowEngine<HLoadEliminationTable, HLoadEliminationEffects>
     494      567460 :     engine(graph(), zone());
     495             :   HAliasAnalyzer aliasing;
     496             :   HLoadEliminationTable* table =
     497             :       new(zone()) HLoadEliminationTable(zone(), &aliasing);
     498             : 
     499             :   if (GLOBAL) {
     500             :     // Perform a global analysis.
     501      283730 :     engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
     502             :   } else {
     503             :     // Perform only local analysis.
     504             :     for (int i = 0; i < graph()->blocks()->length(); i++) {
     505             :       table->Kill();
     506             :       engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
     507             :     }
     508             :   }
     509      283728 : }
     510             : 
     511             : }  // namespace internal
     512             : }  // namespace v8

Generated by: LCOV version 1.10