1cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// Copyright 2013 the V8 project authors. All rights reserved. 2cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// Redistribution and use in source and binary forms, with or without 3cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// modification, are permitted provided that the following conditions are 4cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// met: 5cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// 6cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// * Redistributions of source code must retain the above copyright 7cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// notice, this list of conditions and the following disclaimer. 8cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// * Redistributions in binary form must reproduce the above 9cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// copyright notice, this list of conditions and the following 10cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// disclaimer in the documentation and/or other materials provided 11cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// with the distribution. 12cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// * Neither the name of Google Inc. nor the names of its 13cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// contributors may be used to endorse or promote products derived 14cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// from this software without specific prior written permission. 15cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// 16cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 28cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org#include "hydrogen-check-elimination.h" 29cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org#include "hydrogen-alias-analysis.h" 30cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#include "hydrogen-flow-engine.h" 31cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 32cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#define GLOBAL 1 33cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 34cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// Only collect stats in debug mode. 35cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#if DEBUG 36cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#define INC_STAT(x) phase_->x++ 37cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#else 38cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#define INC_STAT(x) 39cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#endif 40cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 41cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// For code de-uglification. 42cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x 43cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 44cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.orgnamespace v8 { 45cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.orgnamespace internal { 46cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 47cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.orgtypedef UniqueSet<Map>* MapSet; 48cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 49cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgstruct HCheckTableEntry { 50cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HValue* object_; // The object being approximated. NULL => invalid entry. 51cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HValue* check_; // The last check instruction. 52cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org MapSet maps_; // The set of known maps for the object. 53cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org}; 54cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 55cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 56cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// The main datastructure used during check elimination, which stores a 57cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// set of known maps for each object. 58cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgclass HCheckTable : public ZoneObject { 59cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org public: 60cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org static const int kMaxTrackedObjects = 10; 61cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 62cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org explicit HCheckTable(HCheckEliminationPhase* phase) 63cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org : phase_(phase), 64cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org cursor_(0), 65cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org size_(0) { 66cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 67cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 68cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // The main processing of instructions. 69cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTable* Process(HInstruction* instr, Zone* zone) { 70cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org switch (instr->opcode()) { 71cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kCheckMaps: { 72cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceCheckMaps(HCheckMaps::cast(instr)); 73cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 74cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 75cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kCheckValue: { 76cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceCheckValue(HCheckValue::cast(instr)); 77cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 78cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 79cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kLoadNamedField: { 80cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceLoadNamedField(HLoadNamedField::cast(instr)); 81cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 82cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 83cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kStoreNamedField: { 84cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceStoreNamedField(HStoreNamedField::cast(instr)); 85cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 86cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 87cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kCompareMap: { 88cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceCompareMap(HCompareMap::cast(instr)); 89cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 90cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 91cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kTransitionElementsKind: { 92cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceTransitionElementsKind( 93cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HTransitionElementsKind::cast(instr)); 94cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 95cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 96cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kCheckMapValue: { 97cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceCheckMapValue(HCheckMapValue::cast(instr)); 98cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 99cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 1008a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org case HValue::kCheckHeapObject: { 1018a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org ReduceCheckHeapObject(HCheckHeapObject::cast(instr)); 1028a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org break; 1038a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org } 104cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org default: { 105cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // If the instruction changes maps uncontrollably, drop everything. 106cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (instr->CheckGVNFlag(kChangesMaps) || 107cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org instr->CheckGVNFlag(kChangesOsrEntries)) { 108cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org Kill(); 109cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 110cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 111cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Improvements possible: 1128a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org // - eliminate redundant HCheckSmi, HCheckInstanceType instructions 1138a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org // - track which values have been HCheckHeapObject'd 114cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 115cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 116cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return this; 117cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 118cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 119cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Global analysis: Copy state to successor block. 120cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTable* Copy(HBasicBlock* succ, Zone* zone) { 121cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_); 122cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < size_; i++) { 123cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* old_entry = &entries_[i]; 124cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* new_entry = ©->entries_[i]; 125cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // TODO(titzer): keep the check if this block dominates the successor? 126cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org new_entry->object_ = old_entry->object_; 127cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org new_entry->check_ = NULL; 128cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org new_entry->maps_ = old_entry->maps_->Copy(phase_->zone()); 129cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 130ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org if (succ->predecessors()->length() == 1) { 131ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org HControlInstruction* end = succ->predecessors()->at(0)->end(); 132ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org if (end->IsCompareMap() && end->SuccessorAt(0) == succ) { 133ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org // Learn on the true branch of if(CompareMap(x)). 134ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org HCompareMap* cmp = HCompareMap::cast(end); 135ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org HValue* object = cmp->value()->ActualValue(); 136ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org HCheckTableEntry* entry = copy->Find(object); 137ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org if (entry == NULL) { 138ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org copy->Insert(object, cmp->map()); 139ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org } else { 140ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org MapSet list = new(phase_->zone()) UniqueSet<Map>(); 141ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org list->Add(cmp->map(), phase_->zone()); 142ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org entry->maps_ = list; 143ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org } 144ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org } 145ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org // TODO(titzer): is it worthwhile to learn on false branch too? 146ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org } 147cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return copy; 148cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 149cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 150cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Global analysis: Merge this state with the other incoming state. 151cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, Zone* zone) { 152cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (that->size_ == 0) { 153cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // If the other state is empty, simply reset. 154cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org size_ = 0; 155cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org cursor_ = 0; 156cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return this; 157cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 158cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org bool compact = false; 159cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < size_; i++) { 160cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* this_entry = &entries_[i]; 161cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* that_entry = that->Find(this_entry->object_); 162cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (that_entry == NULL) { 163cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org this_entry->object_ = NULL; 164cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org compact = true; 165cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } else { 166cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org this_entry->maps_ = this_entry->maps_->Union( 167cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org that_entry->maps_, phase_->zone()); 168cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (this_entry->check_ != that_entry->check_) this_entry->check_ = NULL; 169cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ASSERT(this_entry->maps_->size() > 0); 170cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 171cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 172cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (compact) Compact(); 173cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return this; 174cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 175cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 176cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceCheckMaps(HCheckMaps* instr) { 177cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HValue* object = instr->value()->ActualValue(); 178cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = Find(object); 179cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (entry != NULL) { 180cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // entry found; 181cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org MapSet a = entry->maps_; 182cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org MapSet i = instr->map_set().Copy(phase_->zone()); 183cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (a->IsSubset(i)) { 184cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // The first check is more strict; the second is redundant. 185cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (entry->check_ != NULL) { 186cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org instr->DeleteAndReplaceWith(entry->check_); 187cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(redundant_); 188cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 189cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org instr->DeleteAndReplaceWith(instr->value()); 190cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(removed_); 191cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 192cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org return; 193cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 194cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org i = i->Intersect(a, phase_->zone()); 195cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (i->size() == 0) { 196cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Intersection is empty; probably megamorphic, which is likely to 197cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // deopt anyway, so just leave things as they are. 198cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(empty_); 199cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 200cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // TODO(titzer): replace the first check with a more strict check 201cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(narrowed_); 202cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 203cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 204cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // No entry; insert a new one. 205cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org Insert(object, instr, instr->map_set().Copy(phase_->zone())); 206cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 207cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 208cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 209cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceCheckValue(HCheckValue* instr) { 210cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Canonicalize HCheckValues; they might have their values load-eliminated. 211cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HValue* value = instr->Canonicalize(); 212cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (value == NULL) { 213cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org instr->DeleteAndReplaceWith(instr->value()); 214cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(removed_); 215cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else if (value != instr) { 216cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org instr->DeleteAndReplaceWith(value); 217cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(redundant_); 218cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 219cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 220cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 221cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceLoadNamedField(HLoadNamedField* instr) { 222cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Reduce a load of the map field when it is known to be a constant. 223cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (!IsMapAccess(instr->access())) return; 224cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 225cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HValue* object = instr->object()->ActualValue(); 226cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org MapSet maps = FindMaps(object); 227cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (maps == NULL || maps->size() != 1) return; // Not a constant. 228cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 229cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Unique<Map> map = maps->at(0); 230cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HConstant* constant = HConstant::CreateAndInsertBefore( 231cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org instr->block()->graph()->zone(), map, true, instr); 232cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org instr->DeleteAndReplaceWith(constant); 233cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(loads_); 234cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 235cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 236cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceCheckMapValue(HCheckMapValue* instr) { 237cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (!instr->map()->IsConstant()) return; // Nothing to learn. 238cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 239cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HValue* object = instr->value()->ActualValue(); 240cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Match a HCheckMapValue(object, HConstant(map)) 241cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Unique<Map> map = MapConstant(instr->map()); 242cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org MapSet maps = FindMaps(object); 243cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (maps != NULL) { 244cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (maps->Contains(map)) { 245cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (maps->size() == 1) { 246cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Object is known to have exactly this map. 247cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org instr->DeleteAndReplaceWith(NULL); 248cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(removed_); 249cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 250cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Only one map survives the check. 251cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org maps->Clear(); 252cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org maps->Add(map, phase_->zone()); 253cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 254cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 255cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 256cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // No prior information. 257cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Insert(object, map); 258cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 259cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 260cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 2618a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org void ReduceCheckHeapObject(HCheckHeapObject* instr) { 2628a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org if (FindMaps(instr->value()->ActualValue()) != NULL) { 2638a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org // If the object has known maps, it's definitely a heap object. 2648a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org instr->DeleteAndReplaceWith(instr->value()); 2658a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org INC_STAT(removed_cho_); 2668a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org } 2678a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org } 2688a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org 269cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceStoreNamedField(HStoreNamedField* instr) { 270cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HValue* object = instr->object()->ActualValue(); 271cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (instr->has_transition()) { 272cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // This store transitions the object to a new map. 273cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Kill(object); 274cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Insert(object, MapConstant(instr->transition())); 275cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else if (IsMapAccess(instr->access())) { 276cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // This is a store directly to the map field of the object. 277cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Kill(object); 278cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (!instr->value()->IsConstant()) return; 279cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Insert(object, MapConstant(instr->value())); 280cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } else { 281cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // If the instruction changes maps, it should be handled above. 282cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org CHECK(!instr->CheckGVNFlag(kChangesMaps)); 283cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 284cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 285cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 286cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceCompareMap(HCompareMap* instr) { 287cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org MapSet maps = FindMaps(instr->value()->ActualValue()); 288cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (maps == NULL) return; 289cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (maps->Contains(instr->map())) { 290cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (maps->size() == 1) { 291cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // TODO(titzer): replace with goto true branch 292cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(compares_true_); 293cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 294cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 295cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // TODO(titzer): replace with goto false branch 296cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(compares_false_); 297cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 298cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 299cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 300cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { 301cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org MapSet maps = FindMaps(instr->object()->ActualValue()); 302cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Can only learn more about an object that already has a known set of maps. 303cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (maps == NULL) return; 304cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (maps->Contains(instr->original_map())) { 305cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // If the object has the original map, it will be transitioned. 306cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org maps->Remove(instr->original_map()); 307cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org maps->Add(instr->transitioned_map(), phase_->zone()); 308cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 309cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Object does not have the given map, thus the transition is redundant. 310cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org instr->DeleteAndReplaceWith(instr->object()); 311cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(transitions_); 312cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 313cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 314cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 315cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Kill everything in the table. 316cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void Kill() { 317cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org size_ = 0; 318cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org cursor_ = 0; 319cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 320cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 321cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Kill everything in the table that may alias {object}. 322cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void Kill(HValue* object) { 323cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org bool compact = false; 324cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < size_; i++) { 325cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = &entries_[i]; 326cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ASSERT(entry->object_ != NULL); 327cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (phase_->aliasing_->MayAlias(entry->object_, object)) { 328cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org entry->object_ = NULL; 329cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org compact = true; 330cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 331cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 332cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (compact) Compact(); 333cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ASSERT(Find(object) == NULL); 334cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 335cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 336cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org void Compact() { 337cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // First, compact the array in place. 338cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int max = size_, dest = 0, old_cursor = cursor_; 339cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < max; i++) { 340cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (entries_[i].object_ != NULL) { 341cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (dest != i) entries_[dest] = entries_[i]; 342cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org dest++; 343cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } else { 344cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (i < old_cursor) cursor_--; 345cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org size_--; 346cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 347cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 348cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ASSERT(size_ == dest); 349cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ASSERT(cursor_ <= size_); 350cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 351cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Preserve the age of the entries by moving the older entries to the end. 352cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (cursor_ == size_) return; // Cursor already points at end. 353cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (cursor_ != 0) { 354cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // | L = oldest | R = newest | | 355cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // ^ cursor ^ size ^ MAX 356cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry tmp_entries[kMaxTrackedObjects]; 357cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int L = cursor_; 358cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int R = size_ - cursor_; 359cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 360cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org OS::MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry)); 361cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org OS::MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry)); 362cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry)); 363cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 364cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 365cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org cursor_ = size_; // Move cursor to end. 366cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 367cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 368cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void Print() { 369cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < size_; i++) { 370cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = &entries_[i]; 371cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ASSERT(entry->object_ != NULL); 372cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org PrintF(" checkmaps-table @%d: object #%d ", i, entry->object_->id()); 373cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (entry->check_ != NULL) { 374cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org PrintF("check #%d ", entry->check_->id()); 375cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 376cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org MapSet list = entry->maps_; 377cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org PrintF("%d maps { ", list->size()); 378cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org for (int j = 0; j < list->size(); j++) { 379cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (j > 0) PrintF(", "); 380cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); 381cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 382cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org PrintF(" }\n"); 383cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 384cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 385cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 386cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org private: 387cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* Find(HValue* object) { 388cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = size_ - 1; i >= 0; i--) { 389cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Search from most-recently-inserted to least-recently-inserted. 390cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = &entries_[i]; 391cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ASSERT(entry->object_ != NULL); 392cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry; 393cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 394cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return NULL; 395cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 396cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 397cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org MapSet FindMaps(HValue* object) { 398cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = Find(object); 399cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return entry == NULL ? NULL : entry->maps_; 400cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 401cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 402cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void Insert(HValue* object, Unique<Map> map) { 403cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org MapSet list = new(phase_->zone()) UniqueSet<Map>(); 404cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org list->Add(map, phase_->zone()); 405cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Insert(object, NULL, list); 406cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 407cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 408cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void Insert(HValue* object, HCheckMaps* check, MapSet maps) { 409cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = &entries_[cursor_++]; 410cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org entry->object_ = object; 411cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org entry->check_ = check; 412cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org entry->maps_ = maps; 413cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // If the table becomes full, wrap around and overwrite older entries. 414cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (cursor_ == kMaxTrackedObjects) cursor_ = 0; 415cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (size_ < kMaxTrackedObjects) size_++; 416cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 417cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 418cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org bool IsMapAccess(HObjectAccess access) { 419cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org return access.IsInobject() && access.offset() == JSObject::kMapOffset; 420cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 421cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 422cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Unique<Map> MapConstant(HValue* value) { 423cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org return Unique<Map>::cast(HConstant::cast(value)->GetUnique()); 424cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 425cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 426cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org friend class HCheckMapsEffects; 427cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 428cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckEliminationPhase* phase_; 429cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry entries_[kMaxTrackedObjects]; 430cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int16_t cursor_; // Must be <= kMaxTrackedObjects 431cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int16_t size_; // Must be <= kMaxTrackedObjects 432cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // TODO(titzer): STATIC_ASSERT kMaxTrackedObjects < max(cursor_) 433cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org}; 434cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 435cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 436cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// Collects instructions that can cause effects that invalidate information 437cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// needed for check elimination. 438cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgclass HCheckMapsEffects : public ZoneObject { 439cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org public: 440cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org explicit HCheckMapsEffects(Zone* zone) 441cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org : maps_stored_(false), 442cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org stores_(5, zone) { } 443cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 444cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org inline bool Disabled() { 445cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return false; // Effects are _not_ disabled. 446cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 447cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 448cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Process a possibly side-effecting instruction. 449cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org void Process(HInstruction* instr, Zone* zone) { 450cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org switch (instr->opcode()) { 451cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org case HValue::kStoreNamedField: { 452cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org stores_.Add(HStoreNamedField::cast(instr), zone); 453cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org break; 454cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 455cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kOsrEntry: { 456cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Kill everything. Loads must not be hoisted past the OSR entry. 457cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org maps_stored_ = true; 458cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 459cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org default: { 460cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org maps_stored_ |= (instr->CheckGVNFlag(kChangesMaps) | 461cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org instr->CheckGVNFlag(kChangesElementsKind)); 462cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 463cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 464cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 465cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 466cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Apply these effects to the given check elimination table. 467cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org void Apply(HCheckTable* table) { 468cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (maps_stored_) { 469cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Uncontrollable map modifications; kill everything. 470cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org table->Kill(); 471cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return; 472cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 473cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 474cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Kill maps for each store contained in these effects. 475cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < stores_.length(); i++) { 476cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HStoreNamedField* s = stores_[i]; 477cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (table->IsMapAccess(s->access()) || s->has_transition()) { 478cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org table->Kill(s->object()->ActualValue()); 479cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 480cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 481cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 482cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 483cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Union these effects with the other effects. 484cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org void Union(HCheckMapsEffects* that, Zone* zone) { 485cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org maps_stored_ |= that->maps_stored_; 486cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < that->stores_.length(); i++) { 487cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org stores_.Add(that->stores_[i], zone); 488cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 489cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 490cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 491cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org private: 492cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org bool maps_stored_ : 1; 493cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ZoneList<HStoreNamedField*> stores_; 494cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org}; 495cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 496cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 497cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// The main routine of the analysis phase. Use the HFlowEngine for either a 498cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// local or a global analysis. 499cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgvoid HCheckEliminationPhase::Run() { 500cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone()); 501cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTable* table = new(zone()) HCheckTable(this); 502cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 503cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (GLOBAL) { 504cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Perform a global analysis. 505cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table); 506cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } else { 507cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Perform only local analysis. 508cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < graph()->blocks()->length(); i++) { 509cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org table->Kill(); 510cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org engine.AnalyzeOneBlock(graph()->blocks()->at(i), table); 511cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 512cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 513cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 514cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (FLAG_trace_check_elimination) PrintStats(); 515cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org} 516cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 517cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 518cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// Are we eliminated yet? 519cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgvoid HCheckEliminationPhase::PrintStats() { 520cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#if DEBUG 5218a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_) 5228a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org#else 5238a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org #define PRINT_STAT(x) 524cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#endif 5258a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(redundant); 5268a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(removed); 5278a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(removed_cho); 5288a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(narrowed); 5298a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(loads); 5308a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(empty); 5318a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(compares_true); 5328a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(compares_false); 5338a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(transitions); 534cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org} 535cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 536cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org} } // namespace v8::internal 537