src/v8/src/hydrogen-check-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-check-elimination.h"
  29 #include "hydrogen-alias-analysis.h"
  30 #include "hydrogen-flow-engine.h"
  31
  32 #define GLOBAL 1
  33
  34 // Only collect stats in debug mode.
  35 #if DEBUG
  36 #define INC_STAT(x) phase_->x++
  37 #else
  38 #define INC_STAT(x)
  39 #endif
  40
  41 // For code de-uglification.
  42 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
  43
  44 namespace v8 {
  45 namespace internal {
  46
  47 typedef UniqueSet<Map>* MapSet;
  48
  49 struct HCheckTableEntry {
  50   HValue* object_;  // The object being approximated. NULL => invalid entry.
  51   HValue* check_;   // The last check instruction.
  52   MapSet maps_;     // The set of known maps for the object.
  53 };
  54
  55
  56 // The main datastructure used during check elimination, which stores a
  57 // set of known maps for each object.
  58 class HCheckTable : public ZoneObject {
  59  public:
  60   static const int kMaxTrackedObjects = 10;
  61
  62   explicit HCheckTable(HCheckEliminationPhase* phase)
  63     : phase_(phase),
  64       cursor_(0),
  65       size_(0) {
  66   }
  67
  68   // The main processing of instructions.
  69   HCheckTable* Process(HInstruction* instr, Zone* zone) {
  70     switch (instr->opcode()) {
  71       case HValue::kCheckMaps: {
  72         ReduceCheckMaps(HCheckMaps::cast(instr));
  73         break;
  74       }
  75       case HValue::kCheckValue: {
  76         ReduceCheckValue(HCheckValue::cast(instr));
  77         break;
  78       }
  79       case HValue::kLoadNamedField: {
  80         ReduceLoadNamedField(HLoadNamedField::cast(instr));
  81         break;
  82       }
  83       case HValue::kStoreNamedField: {
  84         ReduceStoreNamedField(HStoreNamedField::cast(instr));
  85         break;
  86       }
  87       case HValue::kCompareMap: {
  88         ReduceCompareMap(HCompareMap::cast(instr));
  89         break;
  90       }
  91       case HValue::kTransitionElementsKind: {
  92         ReduceTransitionElementsKind(
  93             HTransitionElementsKind::cast(instr));
  94         break;
  95       }
  96       case HValue::kCheckMapValue: {
  97         ReduceCheckMapValue(HCheckMapValue::cast(instr));
  98         break;
  99       }
 100       case HValue::kCheckHeapObject: {
 101         ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
 102         break;
 103       }
 104       default: {
 105         // If the instruction changes maps uncontrollably, drop everything.
 106         if (instr->CheckGVNFlag(kChangesMaps) ||
 107             instr->CheckGVNFlag(kChangesOsrEntries)) {
 108           Kill();
 109         }
 110       }
 111       // Improvements possible:
 112       // - eliminate redundant HCheckSmi, HCheckInstanceType instructions
 113       // - track which values have been HCheckHeapObject'd
 114     }
 115
 116     return this;
 117   }
 118
 119   // Global analysis: Copy state to successor block.
 120   HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
 121     HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_);
 122     for (int i = 0; i < size_; i++) {
 123       HCheckTableEntry* old_entry = &entries_[i];
 124       HCheckTableEntry* new_entry = &copy->entries_[i];
 125       // TODO(titzer): keep the check if this block dominates the successor?
 126       new_entry->object_ = old_entry->object_;
 127       new_entry->check_ = NULL;
 128       new_entry->maps_ = old_entry->maps_->Copy(phase_->zone());
 129     }
 130     copy->cursor_ = cursor_;
 131     copy->size_ = size_;
 132
 133     // Branch-sensitive analysis for certain comparisons may add more facts
 134     // to the state for the successor on the true branch.
 135     bool learned = false;
 136     HControlInstruction* end = succ->predecessors()->at(0)->end();
 137     if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) {
 138       if (end->IsCompareMap()) {
 139         // Learn on the true branch of if(CompareMap(x)).
 140         HCompareMap* cmp = HCompareMap::cast(end);
 141         HValue* object = cmp->value()->ActualValue();
 142         HCheckTableEntry* entry = copy->Find(object);
 143         if (entry == NULL) {
 144           copy->Insert(object, cmp->map());
 145         } else {
 146           MapSet list = new(phase_->zone()) UniqueSet<Map>();
 147           list->Add(cmp->map(), phase_->zone());
 148           entry->maps_ = list;
 149         }
 150         learned = true;
 151       } else if (end->IsCompareObjectEqAndBranch()) {
 152         // Learn on the true branch of if(CmpObjectEq(x, y)).
 153         HCompareObjectEqAndBranch* cmp =
 154           HCompareObjectEqAndBranch::cast(end);
 155         HValue* left = cmp->left()->ActualValue();
 156         HValue* right = cmp->right()->ActualValue();
 157         HCheckTableEntry* le = copy->Find(left);
 158         HCheckTableEntry* re = copy->Find(right);
 159         if (le == NULL) {
 160           if (re != NULL) {
 161             copy->Insert(left, NULL, re->maps_->Copy(zone));
 162           }
 163         } else if (re == NULL) {
 164           copy->Insert(right, NULL, le->maps_->Copy(zone));
 165         } else {
 166           MapSet intersect = le->maps_->Intersect(re->maps_, zone);
 167           le->maps_ = intersect;
 168           re->maps_ = intersect->Copy(zone);
 169         }
 170         learned = true;
 171       }
 172       // Learning on false branches requires storing negative facts.
 173     }
 174
 175     if (FLAG_trace_check_elimination) {
 176       PrintF("B%d checkmaps-table %s from B%d:\n",
 177              succ->block_id(),
 178              learned ? "learned" : "copied",
 179              from_block->block_id());
 180       copy->Print();
 181     }
 182
 183     return copy;
 184   }
 185
 186   // Global analysis: Merge this state with the other incoming state.
 187   HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that,
 188                      HBasicBlock* that_block, Zone* zone) {
 189     if (that_block->IsReachable()) {
 190       if (that->size_ == 0) {
 191         // If the other state is empty, simply reset.
 192         size_ = 0;
 193         cursor_ = 0;
 194       } else {
 195         bool compact = false;
 196         for (int i = 0; i < size_; i++) {
 197           HCheckTableEntry* this_entry = &entries_[i];
 198           HCheckTableEntry* that_entry = that->Find(this_entry->object_);
 199           if (that_entry == NULL) {
 200             this_entry->object_ = NULL;
 201             compact = true;
 202           } else {
 203             this_entry->maps_ =
 204                 this_entry->maps_->Union(that_entry->maps_, phase_->zone());
 205             if (this_entry->check_ != that_entry->check_) {
 206               this_entry->check_ = NULL;
 207             }
 208             ASSERT(this_entry->maps_->size() > 0);
 209           }
 210         }
 211         if (compact) Compact();
 212       }
 213     }
 214     if (FLAG_trace_check_elimination) {
 215       PrintF("B%d checkmaps-table merged with B%d table:\n",
 216              succ->block_id(), that_block->block_id());
 217       Print();
 218     }
 219     return this;
 220   }
 221
 222   void ReduceCheckMaps(HCheckMaps* instr) {
 223     HValue* object = instr->value()->ActualValue();
 224     HCheckTableEntry* entry = Find(object);
 225     if (entry != NULL) {
 226       // entry found;
 227       MapSet a = entry->maps_;
 228       MapSet i = instr->map_set().Copy(phase_->zone());
 229       if (a->IsSubset(i)) {
 230         // The first check is more strict; the second is redundant.
 231         if (entry->check_ != NULL) {
 232           TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
 233               instr->id(), instr->block()->block_id(), entry->check_->id()));
 234           instr->DeleteAndReplaceWith(entry->check_);
 235           INC_STAT(redundant_);
 236         } else {
 237           TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n",
 238               instr->id(), instr->block()->block_id()));
 239           // Mark check as dead but leave it in the graph as a checkpoint for
 240           // subsequent checks.
 241           instr->SetFlag(HValue::kIsDead);
 242           entry->check_ = instr;
 243           INC_STAT(removed_);
 244         }
 245         return;
 246       }
 247       i = i->Intersect(a, phase_->zone());
 248       if (i->size() == 0) {
 249         // Intersection is empty; probably megamorphic, which is likely to
 250         // deopt anyway, so just leave things as they are.
 251         INC_STAT(empty_);
 252       } else {
 253         // TODO(titzer): replace the first check with a more strict check
 254         INC_STAT(narrowed_);
 255       }
 256     } else {
 257       // No entry; insert a new one.
 258       Insert(object, instr, instr->map_set().Copy(phase_->zone()));
 259     }
 260   }
 261
 262   void ReduceCheckValue(HCheckValue* instr) {
 263     // Canonicalize HCheckValues; they might have their values load-eliminated.
 264     HValue* value = instr->Canonicalize();
 265     if (value == NULL) {
 266       instr->DeleteAndReplaceWith(instr->value());
 267       INC_STAT(removed_);
 268     } else if (value != instr) {
 269       instr->DeleteAndReplaceWith(value);
 270       INC_STAT(redundant_);
 271     }
 272   }
 273
 274   void ReduceLoadNamedField(HLoadNamedField* instr) {
 275     // Reduce a load of the map field when it is known to be a constant.
 276     if (!IsMapAccess(instr->access())) return;
 277
 278     HValue* object = instr->object()->ActualValue();
 279     MapSet maps = FindMaps(object);
 280     if (maps == NULL || maps->size() != 1) return;  // Not a constant.
 281
 282     Unique<Map> map = maps->at(0);
 283     HConstant* constant = HConstant::CreateAndInsertBefore(
 284         instr->block()->graph()->zone(), map, true, instr);
 285     instr->DeleteAndReplaceWith(constant);
 286     INC_STAT(loads_);
 287   }
 288
 289   void ReduceCheckMapValue(HCheckMapValue* instr) {
 290     if (!instr->map()->IsConstant()) return;  // Nothing to learn.
 291
 292     HValue* object = instr->value()->ActualValue();
 293     // Match a HCheckMapValue(object, HConstant(map))
 294     Unique<Map> map = MapConstant(instr->map());
 295     MapSet maps = FindMaps(object);
 296     if (maps != NULL) {
 297       if (maps->Contains(map)) {
 298         if (maps->size() == 1) {
 299           // Object is known to have exactly this map.
 300           instr->DeleteAndReplaceWith(NULL);
 301           INC_STAT(removed_);
 302         } else {
 303           // Only one map survives the check.
 304           maps->Clear();
 305           maps->Add(map, phase_->zone());
 306         }
 307       }
 308     } else {
 309       // No prior information.
 310       Insert(object, map);
 311     }
 312   }
 313
 314   void ReduceCheckHeapObject(HCheckHeapObject* instr) {
 315     if (FindMaps(instr->value()->ActualValue()) != NULL) {
 316       // If the object has known maps, it's definitely a heap object.
 317       instr->DeleteAndReplaceWith(instr->value());
 318       INC_STAT(removed_cho_);
 319     }
 320   }
 321
 322   void ReduceStoreNamedField(HStoreNamedField* instr) {
 323     HValue* object = instr->object()->ActualValue();
 324     if (instr->has_transition()) {
 325       // This store transitions the object to a new map.
 326       Kill(object);
 327       Insert(object, MapConstant(instr->transition()));
 328     } else if (IsMapAccess(instr->access())) {
 329       // This is a store directly to the map field of the object.
 330       Kill(object);
 331       if (!instr->value()->IsConstant()) return;
 332       Insert(object, MapConstant(instr->value()));
 333     } else {
 334       // If the instruction changes maps, it should be handled above.
 335       CHECK(!instr->CheckGVNFlag(kChangesMaps));
 336     }
 337   }
 338
 339   void ReduceCompareMap(HCompareMap* instr) {
 340     MapSet maps = FindMaps(instr->value()->ActualValue());
 341     if (maps == NULL) return;
 342     if (maps->Contains(instr->map())) {
 343       if (maps->size() == 1) {
 344         TRACE(("Marking redundant CompareMap #%d at B%d as true\n",
 345             instr->id(), instr->block()->block_id()));
 346         instr->set_known_successor_index(0);
 347         INC_STAT(compares_true_);
 348       }
 349     } else {
 350       TRACE(("Marking redundant CompareMap #%d at B%d as false\n",
 351           instr->id(), instr->block()->block_id()));
 352       instr->set_known_successor_index(1);
 353       INC_STAT(compares_false_);
 354     }
 355   }
 356
 357   void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
 358     MapSet maps = FindMaps(instr->object()->ActualValue());
 359     // Can only learn more about an object that already has a known set of maps.
 360     if (maps == NULL) return;
 361     if (maps->Contains(instr->original_map())) {
 362       // If the object has the original map, it will be transitioned.
 363       maps->Remove(instr->original_map());
 364       maps->Add(instr->transitioned_map(), phase_->zone());
 365     } else {
 366       // Object does not have the given map, thus the transition is redundant.
 367       instr->DeleteAndReplaceWith(instr->object());
 368       INC_STAT(transitions_);
 369     }
 370   }
 371
 372   // Kill everything in the table.
 373   void Kill() {
 374     size_ = 0;
 375     cursor_ = 0;
 376   }
 377
 378   // Kill everything in the table that may alias {object}.
 379   void Kill(HValue* object) {
 380     bool compact = false;
 381     for (int i = 0; i < size_; i++) {
 382       HCheckTableEntry* entry = &entries_[i];
 383       ASSERT(entry->object_ != NULL);
 384       if (phase_->aliasing_->MayAlias(entry->object_, object)) {
 385         entry->object_ = NULL;
 386         compact = true;
 387       }
 388     }
 389     if (compact) Compact();
 390     ASSERT(Find(object) == NULL);
 391   }
 392
 393   void Compact() {
 394     // First, compact the array in place.
 395     int max = size_, dest = 0, old_cursor = cursor_;
 396     for (int i = 0; i < max; i++) {
 397       if (entries_[i].object_ != NULL) {
 398         if (dest != i) entries_[dest] = entries_[i];
 399         dest++;
 400       } else {
 401         if (i < old_cursor) cursor_--;
 402         size_--;
 403       }
 404     }
 405     ASSERT(size_ == dest);
 406     ASSERT(cursor_ <= size_);
 407
 408     // Preserve the age of the entries by moving the older entries to the end.
 409     if (cursor_ == size_) return;  // Cursor already points at end.
 410     if (cursor_ != 0) {
 411       // | L = oldest |   R = newest   |       |
 412       //              ^ cursor         ^ size  ^ MAX
 413       HCheckTableEntry tmp_entries[kMaxTrackedObjects];
 414       int L = cursor_;
 415       int R = size_ - cursor_;
 416
 417       OS::MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry));
 418       OS::MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry));
 419       OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry));
 420     }
 421
 422     cursor_ = size_;  // Move cursor to end.
 423   }
 424
 425   void Print() {
 426     for (int i = 0; i < size_; i++) {
 427       HCheckTableEntry* entry = &entries_[i];
 428       ASSERT(entry->object_ != NULL);
 429       PrintF("  checkmaps-table @%d: object #%d ", i, entry->object_->id());
 430       if (entry->check_ != NULL) {
 431         PrintF("check #%d ", entry->check_->id());
 432       }
 433       MapSet list = entry->maps_;
 434       PrintF("%d maps { ", list->size());
 435       for (int j = 0; j < list->size(); j++) {
 436         if (j > 0) PrintF(", ");
 437         PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
 438       }
 439       PrintF(" }\n");
 440     }
 441   }
 442
 443  private:
 444   HCheckTableEntry* Find(HValue* object) {
 445     for (int i = size_ - 1; i >= 0; i--) {
 446       // Search from most-recently-inserted to least-recently-inserted.
 447       HCheckTableEntry* entry = &entries_[i];
 448       ASSERT(entry->object_ != NULL);
 449       if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry;
 450     }
 451     return NULL;
 452   }
 453
 454   MapSet FindMaps(HValue* object) {
 455     HCheckTableEntry* entry = Find(object);
 456     return entry == NULL ? NULL : entry->maps_;
 457   }
 458
 459   void Insert(HValue* object, Unique<Map> map) {
 460     MapSet list = new(phase_->zone()) UniqueSet<Map>();
 461     list->Add(map, phase_->zone());
 462     Insert(object, NULL, list);
 463   }
 464
 465   void Insert(HValue* object, HCheckMaps* check, MapSet maps) {
 466     HCheckTableEntry* entry = &entries_[cursor_++];
 467     entry->object_ = object;
 468     entry->check_ = check;
 469     entry->maps_ = maps;
 470     // If the table becomes full, wrap around and overwrite older entries.
 471     if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
 472     if (size_ < kMaxTrackedObjects) size_++;
 473   }
 474
 475   bool IsMapAccess(HObjectAccess access) {
 476     return access.IsInobject() && access.offset() == JSObject::kMapOffset;
 477   }
 478
 479   Unique<Map> MapConstant(HValue* value) {
 480     return Unique<Map>::cast(HConstant::cast(value)->GetUnique());
 481   }
 482
 483   friend class HCheckMapsEffects;
 484
 485   HCheckEliminationPhase* phase_;
 486   HCheckTableEntry entries_[kMaxTrackedObjects];
 487   int16_t cursor_;  // Must be <= kMaxTrackedObjects
 488   int16_t size_;    // Must be <= kMaxTrackedObjects
 489   // TODO(titzer): STATIC_ASSERT kMaxTrackedObjects < max(cursor_)
 490 };
 491
 492
 493 // Collects instructions that can cause effects that invalidate information
 494 // needed for check elimination.
 495 class HCheckMapsEffects : public ZoneObject {
 496  public:
 497   explicit HCheckMapsEffects(Zone* zone)
 498     : maps_stored_(false),
 499       stores_(5, zone) { }
 500
 501   inline bool Disabled() {
 502     return false;  // Effects are _not_ disabled.
 503   }
 504
 505   // Process a possibly side-effecting instruction.
 506   void Process(HInstruction* instr, Zone* zone) {
 507     switch (instr->opcode()) {
 508       case HValue::kStoreNamedField: {
 509         stores_.Add(HStoreNamedField::cast(instr), zone);
 510         break;
 511       }
 512       case HValue::kOsrEntry: {
 513         // Kill everything. Loads must not be hoisted past the OSR entry.
 514         maps_stored_ = true;
 515       }
 516       default: {
 517         maps_stored_ |= (instr->CheckGVNFlag(kChangesMaps) |
 518                          instr->CheckGVNFlag(kChangesElementsKind));
 519       }
 520     }
 521   }
 522
 523   // Apply these effects to the given check elimination table.
 524   void Apply(HCheckTable* table) {
 525     if (maps_stored_) {
 526       // Uncontrollable map modifications; kill everything.
 527       table->Kill();
 528       return;
 529     }
 530
 531     // Kill maps for each store contained in these effects.
 532     for (int i = 0; i < stores_.length(); i++) {
 533       HStoreNamedField* s = stores_[i];
 534       if (table->IsMapAccess(s->access()) || s->has_transition()) {
 535         table->Kill(s->object()->ActualValue());
 536       }
 537     }
 538   }
 539
 540   // Union these effects with the other effects.
 541   void Union(HCheckMapsEffects* that, Zone* zone) {
 542     maps_stored_ |= that->maps_stored_;
 543     for (int i = 0; i < that->stores_.length(); i++) {
 544       stores_.Add(that->stores_[i], zone);
 545     }
 546   }
 547
 548  private:
 549   bool maps_stored_ : 1;
 550   ZoneList<HStoreNamedField*> stores_;
 551 };
 552
 553
 554 // The main routine of the analysis phase. Use the HFlowEngine for either a
 555 // local or a global analysis.
 556 void HCheckEliminationPhase::Run() {
 557   HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone());
 558   HCheckTable* table = new(zone()) HCheckTable(this);
 559
 560   if (GLOBAL) {
 561     // Perform a global analysis.
 562     engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
 563   } else {
 564     // Perform only local analysis.
 565     for (int i = 0; i < graph()->blocks()->length(); i++) {
 566       table->Kill();
 567       engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
 568     }
 569   }
 570
 571   if (FLAG_trace_check_elimination) PrintStats();
 572 }
 573
 574
 575 // Are we eliminated yet?
 576 void HCheckEliminationPhase::PrintStats() {
 577 #if DEBUG
 578   #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_)
 579 #else
 580   #define PRINT_STAT(x)
 581 #endif
 582   PRINT_STAT(redundant);
 583   PRINT_STAT(removed);
 584   PRINT_STAT(removed_cho);
 585   PRINT_STAT(narrowed);
 586   PRINT_STAT(loads);
 587   PRINT_STAT(empty);
 588   PRINT_STAT(compares_true);
 589   PRINT_STAT(compares_false);
 590   PRINT_STAT(transitions);
 591 }
 592
 593 } }  // namespace v8::internal