src/v8/src/hydrogen-load-elimination.cc

   1 // Copyright 2013 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include "hydrogen-alias-analysis.h"
  29 #include "hydrogen-load-elimination.h"
  30 #include "hydrogen-instructions.h"
  31 #include "hydrogen-flow-engine.h"
  32
  33 namespace v8 {
  34 namespace internal {
  35
  36 #define GLOBAL true
  37 #define TRACE(x) if (FLAG_trace_load_elimination) PrintF x
  38
  39 static const int kMaxTrackedFields = 16;
  40 static const int kMaxTrackedObjects = 5;
  41
  42 // An element in the field approximation list.
  43 class HFieldApproximation : public ZoneObject {
  44  public:  // Just a data blob.
  45   HValue* object_;
  46   HValue* last_value_;
  47   HFieldApproximation* next_;
  48
  49   // Recursively copy the entire linked list of field approximations.
  50   HFieldApproximation* Copy(Zone* zone) {
  51     if (this == NULL) return NULL;
  52     HFieldApproximation* copy = new(zone) HFieldApproximation();
  53     copy->object_ = this->object_;
  54     copy->last_value_ = this->last_value_;
  55     copy->next_ = this->next_->Copy(zone);
  56     return copy;
  57   }
  58 };
  59
  60
  61 // The main datastructure used during load/store elimination. Each in-object
  62 // field is tracked separately. For each field, store a list of known field
  63 // values for known objects.
  64 class HLoadEliminationTable : public ZoneObject {
  65  public:
  66   HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing)
  67     : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { }
  68
  69   // The main processing of instructions.
  70   HLoadEliminationTable* Process(HInstruction* instr, Zone* zone) {
  71     switch (instr->opcode()) {
  72       case HValue::kLoadNamedField: {
  73         HLoadNamedField* l = HLoadNamedField::cast(instr);
  74         TRACE((" process L%d field %d (o%d)\n",
  75                instr->id(),
  76                FieldOf(l->access()),
  77                l->object()->ActualValue()->id()));
  78         HValue* result = load(l);
  79         if (result != instr &&
  80             result->type().Equals(instr->type()) &&
  81             result->representation().Equals(instr->representation())) {
  82           // The load can be replaced with a previous load or a value.
  83           TRACE(("  replace L%d -> v%d\n", instr->id(), result->id()));
  84           instr->DeleteAndReplaceWith(result);
  85         }
  86         break;
  87       }
  88       case HValue::kStoreNamedField: {
  89         HStoreNamedField* s = HStoreNamedField::cast(instr);
  90         TRACE((" process S%d field %d (o%d) = v%d\n",
  91                instr->id(),
  92                FieldOf(s->access()),
  93                s->object()->ActualValue()->id(),
  94                s->value()->id()));
  95         HValue* result = store(s);
  96         if (result == NULL) {
  97           // The store is redundant. Remove it.
  98           TRACE(("  remove S%d\n", instr->id()));
  99           instr->DeleteAndReplaceWith(NULL);
 100         }
 101         break;
 102       }
 103       default: {
 104         if (instr->CheckGVNFlag(kChangesInobjectFields)) {
 105           TRACE((" kill-all i%d\n", instr->id()));
 106           Kill();
 107           break;
 108         }
 109         if (instr->CheckGVNFlag(kChangesMaps)) {
 110           TRACE((" kill-maps i%d\n", instr->id()));
 111           KillOffset(JSObject::kMapOffset);
 112         }
 113         if (instr->CheckGVNFlag(kChangesElementsKind)) {
 114           TRACE((" kill-elements-kind i%d\n", instr->id()));
 115           KillOffset(JSObject::kMapOffset);
 116           KillOffset(JSObject::kElementsOffset);
 117         }
 118         if (instr->CheckGVNFlag(kChangesElementsPointer)) {
 119           TRACE((" kill-elements i%d\n", instr->id()));
 120           KillOffset(JSObject::kElementsOffset);
 121         }
 122         if (instr->CheckGVNFlag(kChangesOsrEntries)) {
 123           TRACE((" kill-osr i%d\n", instr->id()));
 124           Kill();
 125         }
 126       }
 127       // Improvements possible:
 128       // - learn from HCheckMaps for field 0
 129       // - remove unobservable stores (write-after-write)
 130       // - track cells
 131       // - track globals
 132       // - track roots
 133     }
 134     return this;
 135   }
 136
 137   // Support for global analysis with HFlowEngine: Copy state to successor
 138   // block.
 139   HLoadEliminationTable* Copy(HBasicBlock* succ, HBasicBlock* from_block,
 140                               Zone* zone) {
 141     HLoadEliminationTable* copy =
 142         new(zone) HLoadEliminationTable(zone, aliasing_);
 143     copy->EnsureFields(fields_.length());
 144     for (int i = 0; i < fields_.length(); i++) {
 145       copy->fields_[i] = fields_[i]->Copy(zone);
 146     }
 147     if (FLAG_trace_load_elimination) {
 148       TRACE((" copy-to B%d\n", succ->block_id()));
 149       copy->Print();
 150     }
 151     return copy;
 152   }
 153
 154   // Support for global analysis with HFlowEngine: Merge this state with
 155   // the other incoming state.
 156   HLoadEliminationTable* Merge(HBasicBlock* succ, HLoadEliminationTable* that,
 157                                HBasicBlock* that_block, Zone* zone) {
 158     if (that->fields_.length() < fields_.length()) {
 159       // Drop fields not in the other table.
 160       fields_.Rewind(that->fields_.length());
 161     }
 162     for (int i = 0; i < fields_.length(); i++) {
 163       // Merge the field approximations for like fields.
 164       HFieldApproximation* approx = fields_[i];
 165       HFieldApproximation* prev = NULL;
 166       while (approx != NULL) {
 167         // TODO(titzer): Merging is O(N * M); sort?
 168         HFieldApproximation* other = that->Find(approx->object_, i);
 169         if (other == NULL || !Equal(approx->last_value_, other->last_value_)) {
 170           // Kill an entry that doesn't agree with the other value.
 171           if (prev != NULL) {
 172             prev->next_ = approx->next_;
 173           } else {
 174             fields_[i] = approx->next_;
 175           }
 176           approx = approx->next_;
 177           continue;
 178         }
 179         prev = approx;
 180         approx = approx->next_;
 181       }
 182     }
 183     if (FLAG_trace_load_elimination) {
 184       TRACE((" merge-to B%d\n", succ->block_id()));
 185       Print();
 186     }
 187     return this;
 188   }
 189
 190   friend class HLoadEliminationEffects;  // Calls Kill() and others.
 191   friend class HLoadEliminationPhase;
 192
 193  private:
 194   // Process a load instruction, updating internal table state. If a previous
 195   // load or store for this object and field exists, return the new value with
 196   // which the load should be replaced. Otherwise, return {instr}.
 197   HValue* load(HLoadNamedField* instr) {
 198     // There must be no loads from non observable in-object properties.
 199     ASSERT(!instr->access().IsInobject() ||
 200            instr->access().existing_inobject_property());
 201
 202     int field = FieldOf(instr->access());
 203     if (field < 0) return instr;
 204
 205     HValue* object = instr->object()->ActualValue();
 206     HFieldApproximation* approx = FindOrCreate(object, field);
 207
 208     if (approx->last_value_ == NULL) {
 209       // Load is not redundant. Fill out a new entry.
 210       approx->last_value_ = instr;
 211       return instr;
 212     } else if (approx->last_value_->block()->EqualToOrDominates(
 213         instr->block())) {
 214       // Eliminate the load. Reuse previously stored value or load instruction.
 215       return approx->last_value_;
 216     } else {
 217       return instr;
 218     }
 219   }
 220
 221   // Process a store instruction, updating internal table state. If a previous
 222   // store to the same object and field makes this store redundant (e.g. because
 223   // the stored values are the same), return NULL indicating that this store
 224   // instruction is redundant. Otherwise, return {instr}.
 225   HValue* store(HStoreNamedField* instr) {
 226     if (instr->access().IsInobject() &&
 227         !instr->access().existing_inobject_property()) {
 228       TRACE(("  skipping non existing property initialization store\n"));
 229       return instr;
 230     }
 231
 232     int field = FieldOf(instr->access());
 233     if (field < 0) return KillIfMisaligned(instr);
 234
 235     HValue* object = instr->object()->ActualValue();
 236     HValue* value = instr->value();
 237
 238     if (instr->has_transition()) {
 239       // A transition introduces a new field and alters the map of the object.
 240       // Since the field in the object is new, it cannot alias existing entries.
 241       // TODO(titzer): introduce a constant for the new map and remember it.
 242       KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
 243     } else {
 244       // Kill non-equivalent may-alias entries.
 245       KillFieldInternal(object, field, value);
 246     }
 247     HFieldApproximation* approx = FindOrCreate(object, field);
 248
 249     if (Equal(approx->last_value_, value)) {
 250       // The store is redundant because the field already has this value.
 251       return NULL;
 252     } else {
 253       // The store is not redundant. Update the entry.
 254       approx->last_value_ = value;
 255       return instr;
 256     }
 257   }
 258
 259   // Kill everything in this table.
 260   void Kill() {
 261     fields_.Rewind(0);
 262   }
 263
 264   // Kill all entries matching the given offset.
 265   void KillOffset(int offset) {
 266     int field = FieldOf(offset);
 267     if (field >= 0 && field < fields_.length()) {
 268       fields_[field] = NULL;
 269     }
 270   }
 271
 272   // Kill all entries aliasing the given store.
 273   void KillStore(HStoreNamedField* s) {
 274     int field = FieldOf(s->access());
 275     if (field >= 0) {
 276       KillFieldInternal(s->object()->ActualValue(), field, s->value());
 277     } else {
 278       KillIfMisaligned(s);
 279     }
 280   }
 281
 282   // Kill multiple entries in the case of a misaligned store.
 283   HValue* KillIfMisaligned(HStoreNamedField* instr) {
 284     HObjectAccess access = instr->access();
 285     if (access.IsInobject()) {
 286       int offset = access.offset();
 287       if ((offset % kPointerSize) != 0) {
 288         // Kill the field containing the first word of the access.
 289         HValue* object = instr->object()->ActualValue();
 290         int field = offset / kPointerSize;
 291         KillFieldInternal(object, field, NULL);
 292
 293         // Kill the next field in case of overlap.
 294         int size = access.representation().size();
 295         int next_field = (offset + size - 1) / kPointerSize;
 296         if (next_field != field) KillFieldInternal(object, next_field, NULL);
 297       }
 298     }
 299     return instr;
 300   }
 301
 302   // Find an entry for the given object and field pair.
 303   HFieldApproximation* Find(HValue* object, int field) {
 304     // Search for a field approximation for this object.
 305     HFieldApproximation* approx = fields_[field];
 306     while (approx != NULL) {
 307       if (aliasing_->MustAlias(object, approx->object_)) return approx;
 308       approx = approx->next_;
 309     }
 310     return NULL;
 311   }
 312
 313   // Find or create an entry for the given object and field pair.
 314   HFieldApproximation* FindOrCreate(HValue* object, int field) {
 315     EnsureFields(field + 1);
 316
 317     // Search for a field approximation for this object.
 318     HFieldApproximation* approx = fields_[field];
 319     int count = 0;
 320     while (approx != NULL) {
 321       if (aliasing_->MustAlias(object, approx->object_)) return approx;
 322       count++;
 323       approx = approx->next_;
 324     }
 325
 326     if (count >= kMaxTrackedObjects) {
 327       // Pull the last entry off the end and repurpose it for this object.
 328       approx = ReuseLastApproximation(field);
 329     } else {
 330       // Allocate a new entry.
 331       approx = new(zone_) HFieldApproximation();
 332     }
 333
 334     // Insert the entry at the head of the list.
 335     approx->object_ = object;
 336     approx->last_value_ = NULL;
 337     approx->next_ = fields_[field];
 338     fields_[field] = approx;
 339
 340     return approx;
 341   }
 342
 343   // Kill all entries for a given field that _may_ alias the given object
 344   // and do _not_ have the given value.
 345   void KillFieldInternal(HValue* object, int field, HValue* value) {
 346     if (field >= fields_.length()) return;  // Nothing to do.
 347
 348     HFieldApproximation* approx = fields_[field];
 349     HFieldApproximation* prev = NULL;
 350     while (approx != NULL) {
 351       if (aliasing_->MayAlias(object, approx->object_)) {
 352         if (!Equal(approx->last_value_, value)) {
 353           // Kill an aliasing entry that doesn't agree on the value.
 354           if (prev != NULL) {
 355             prev->next_ = approx->next_;
 356           } else {
 357             fields_[field] = approx->next_;
 358           }
 359           approx = approx->next_;
 360           continue;
 361         }
 362       }
 363       prev = approx;
 364       approx = approx->next_;
 365     }
 366   }
 367
 368   bool Equal(HValue* a, HValue* b) {
 369     if (a == b) return true;
 370     if (a != NULL && b != NULL && a->CheckFlag(HValue::kUseGVN)) {
 371       return a->Equals(b);
 372     }
 373     return false;
 374   }
 375
 376   // Remove the last approximation for a field so that it can be reused.
 377   // We reuse the last entry because it was the first inserted and is thus
 378   // farthest away from the current instruction.
 379   HFieldApproximation* ReuseLastApproximation(int field) {
 380     HFieldApproximation* approx = fields_[field];
 381     ASSERT(approx != NULL);
 382
 383     HFieldApproximation* prev = NULL;
 384     while (approx->next_ != NULL) {
 385       prev = approx;
 386       approx = approx->next_;
 387     }
 388     if (prev != NULL) prev->next_ = NULL;
 389     return approx;
 390   }
 391
 392   // Compute the field index for the given object access; -1 if not tracked.
 393   int FieldOf(HObjectAccess access) {
 394     return access.IsInobject() ? FieldOf(access.offset()) : -1;
 395   }
 396
 397   // Compute the field index for the given in-object offset; -1 if not tracked.
 398   int FieldOf(int offset) {
 399     if (offset >= kMaxTrackedFields * kPointerSize) return -1;
 400     // TODO(titzer): track misaligned loads in a separate list?
 401     if ((offset % kPointerSize) != 0) return -1;  // Ignore misaligned accesses.
 402     return offset / kPointerSize;
 403   }
 404
 405   // Ensure internal storage for the given number of fields.
 406   void EnsureFields(int num_fields) {
 407     if (fields_.length() < num_fields) {
 408       fields_.AddBlock(NULL, num_fields - fields_.length(), zone_);
 409     }
 410   }
 411
 412   // Print this table to stdout.
 413   void Print() {
 414     for (int i = 0; i < fields_.length(); i++) {
 415       PrintF("  field %d: ", i);
 416       for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) {
 417         PrintF("[o%d =", a->object_->id());
 418         if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id());
 419         PrintF("] ");
 420       }
 421       PrintF("\n");
 422     }
 423   }
 424
 425   Zone* zone_;
 426   ZoneList<HFieldApproximation*> fields_;
 427   HAliasAnalyzer* aliasing_;
 428 };
 429
 430
 431 // Support for HFlowEngine: collect store effects within loops.
 432 class HLoadEliminationEffects : public ZoneObject {
 433  public:
 434   explicit HLoadEliminationEffects(Zone* zone)
 435     : zone_(zone),
 436       maps_stored_(false),
 437       fields_stored_(false),
 438       elements_stored_(false),
 439       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   void Process(HInstruction* instr, Zone* zone) {
 447     switch (instr->opcode()) {
 448       case HValue::kStoreNamedField: {
 449         stores_.Add(HStoreNamedField::cast(instr), zone_);
 450         break;
 451       }
 452       case HValue::kOsrEntry: {
 453         // Kill everything. Loads must not be hoisted past the OSR entry.
 454         maps_stored_ = true;
 455         fields_stored_ = true;
 456         elements_stored_ = true;
 457       }
 458       default: {
 459         fields_stored_ |= instr->CheckGVNFlag(kChangesInobjectFields);
 460         maps_stored_ |= instr->CheckGVNFlag(kChangesMaps);
 461         maps_stored_ |= instr->CheckGVNFlag(kChangesElementsKind);
 462         elements_stored_ |= instr->CheckGVNFlag(kChangesElementsKind);
 463         elements_stored_ |= instr->CheckGVNFlag(kChangesElementsPointer);
 464       }
 465     }
 466   }
 467
 468   // Apply these effects to the given load elimination table.
 469   void Apply(HLoadEliminationTable* table) {
 470     if (fields_stored_) {
 471       table->Kill();
 472       return;
 473     }
 474     if (maps_stored_) {
 475       table->KillOffset(JSObject::kMapOffset);
 476     }
 477     if (elements_stored_) {
 478       table->KillOffset(JSObject::kElementsOffset);
 479     }
 480
 481     // Kill non-agreeing fields for each store contained in these effects.
 482     for (int i = 0; i < stores_.length(); i++) {
 483       table->KillStore(stores_[i]);
 484     }
 485   }
 486
 487   // Union these effects with the other effects.
 488   void Union(HLoadEliminationEffects* that, Zone* zone) {
 489     maps_stored_ |= that->maps_stored_;
 490     fields_stored_ |= that->fields_stored_;
 491     elements_stored_ |= that->elements_stored_;
 492     for (int i = 0; i < that->stores_.length(); i++) {
 493       stores_.Add(that->stores_[i], zone);
 494     }
 495   }
 496
 497  private:
 498   Zone* zone_;
 499   bool maps_stored_ : 1;
 500   bool fields_stored_ : 1;
 501   bool elements_stored_ : 1;
 502   ZoneList<HStoreNamedField*> stores_;
 503 };
 504
 505
 506 // The main routine of the analysis phase. Use the HFlowEngine for either a
 507 // local or a global analysis.
 508 void HLoadEliminationPhase::Run() {
 509   HFlowEngine<HLoadEliminationTable, HLoadEliminationEffects>
 510     engine(graph(), zone());
 511   HAliasAnalyzer aliasing;
 512   HLoadEliminationTable* table =
 513       new(zone()) HLoadEliminationTable(zone(), &aliasing);
 514
 515   if (GLOBAL) {
 516     // Perform a global analysis.
 517     engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
 518   } else {
 519     // Perform only local analysis.
 520     for (int i = 0; i < graph()->blocks()->length(); i++) {
 521       table->Kill();
 522       engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
 523     }
 524   }
 525 }
 526
 527 } }  // namespace v8::internal