1cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// Copyright 2013 the V8 project authors. All rights reserved. 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// Use of this source code is governed by a BSD-style license that can be 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// found in the LICENSE file. 4cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 5196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/hydrogen-check-elimination.h" 6a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 7196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/hydrogen-alias-analysis.h" 8196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/hydrogen-flow-engine.h" 9cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 10cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#define GLOBAL 1 11cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 12cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// Only collect stats in debug mode. 13cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#if DEBUG 14cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#define INC_STAT(x) phase_->x++ 15cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#else 16cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#define INC_STAT(x) 17cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#endif 18cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 19cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// For code de-uglification. 20cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x 21cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 22cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.orgnamespace v8 { 23cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.orgnamespace internal { 24cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 25af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.orgtypedef const UniqueSet<Map>* MapSet; 26cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 27cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgstruct HCheckTableEntry { 28a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org enum State { 29a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // We have seen a map check (i.e. an HCheckMaps) for these maps, so we can 30a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // use this information to eliminate further map checks, elements kind 31a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // transitions, etc. 32a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org CHECKED, 33a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // Same as CHECKED, but we also know that these maps are stable. 34a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org CHECKED_STABLE, 35a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // These maps are stable, but not checked (i.e. we learned this via field 36a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // type tracking or from a constant, or they were initially CHECKED_STABLE, 37a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // but became UNCHECKED_STABLE because of an instruction that changes maps 38a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // or elements kind), and we need a stability check for them in order to use 39a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // this information for check elimination (which turns them back to 40a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // CHECKED_STABLE). 41a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org UNCHECKED_STABLE 42a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org }; 43a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 44a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org static const char* State2String(State state) { 45a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org switch (state) { 46a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org case CHECKED: return "checked"; 47a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org case CHECKED_STABLE: return "checked stable"; 48a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org case UNCHECKED_STABLE: return "unchecked stable"; 49a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 50a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org UNREACHABLE(); 51a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org return NULL; 52a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 53a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 54a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org static State StateMerge(State state1, State state2) { 55a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (state1 == state2) return state1; 56a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if ((state1 == CHECKED && state2 == CHECKED_STABLE) || 57a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org (state2 == CHECKED && state1 == CHECKED_STABLE)) { 58a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org return CHECKED; 59a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 60e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) || 61a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE)); 62a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org return UNCHECKED_STABLE; 63a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 64a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 65cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HValue* object_; // The object being approximated. NULL => invalid entry. 66f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HInstruction* check_; // The last check instruction. 67f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org MapSet maps_; // The set of known maps for the object. 68a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org State state_; // The state of this entry. 69cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org}; 70cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 71cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 72f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org// The main data structure used during check elimination, which stores a 73cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org// set of known maps for each object. 74cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgclass HCheckTable : public ZoneObject { 75cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org public: 76af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org static const int kMaxTrackedObjects = 16; 77cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 78cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org explicit HCheckTable(HCheckEliminationPhase* phase) 79cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org : phase_(phase), 80cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org cursor_(0), 81cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org size_(0) { 82cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 83cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 84cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // The main processing of instructions. 85cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTable* Process(HInstruction* instr, Zone* zone) { 86cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org switch (instr->opcode()) { 87cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kCheckMaps: { 88cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceCheckMaps(HCheckMaps::cast(instr)); 89cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 90cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 91cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kLoadNamedField: { 92cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceLoadNamedField(HLoadNamedField::cast(instr)); 93cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 94cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 95cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kStoreNamedField: { 96cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceStoreNamedField(HStoreNamedField::cast(instr)); 97cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 98cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 99cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kCompareMap: { 100cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceCompareMap(HCompareMap::cast(instr)); 101cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 102cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 1038545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org case HValue::kCompareObjectEqAndBranch: { 1048545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr)); 1058545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org break; 1068545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org } 1078d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org case HValue::kIsStringAndBranch: { 1088d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr)); 1098d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org break; 1108d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 111cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org case HValue::kTransitionElementsKind: { 112cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org ReduceTransitionElementsKind( 113cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HTransitionElementsKind::cast(instr)); 114cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org break; 115cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 1168a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org case HValue::kCheckHeapObject: { 1178a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org ReduceCheckHeapObject(HCheckHeapObject::cast(instr)); 1188a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org break; 1198a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org } 1208d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org case HValue::kCheckInstanceType: { 1218d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org ReduceCheckInstanceType(HCheckInstanceType::cast(instr)); 1228d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org break; 1238d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 124cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org default: { 125cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // If the instruction changes maps uncontrollably, drop everything. 126a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (instr->CheckChangesFlag(kOsrEntries)) { 127052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org Kill(); 128a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org break; 129a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 130a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (instr->CheckChangesFlag(kElementsKind) || 131a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org instr->CheckChangesFlag(kMaps)) { 132a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org KillUnstableEntries(); 133cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 134cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 135cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Improvements possible: 1368d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org // - eliminate redundant HCheckSmi instructions 1378a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org // - track which values have been HCheckHeapObject'd 138cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 139cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 140cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return this; 141cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 142cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 143f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Support for global analysis with HFlowEngine: Merge given state with 144f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // the other incoming state. 145f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org static HCheckTable* Merge(HCheckTable* succ_state, HBasicBlock* succ_block, 146f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HCheckTable* pred_state, HBasicBlock* pred_block, 147f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org Zone* zone) { 148f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (pred_state == NULL || pred_block->IsUnreachable()) { 149f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org return succ_state; 150f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 151f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (succ_state == NULL) { 152f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org return pred_state->Copy(succ_block, pred_block, zone); 153f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else { 154f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org return succ_state->Merge(succ_block, pred_state, pred_block, zone); 155f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 156f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 157f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 158f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Support for global analysis with HFlowEngine: Given state merged with all 159f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // the other incoming states, prepare it for use. 160f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org static HCheckTable* Finish(HCheckTable* state, HBasicBlock* block, 161f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org Zone* zone) { 162f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (state == NULL) { 163f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org block->MarkUnreachable(); 164f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else if (block->IsUnreachable()) { 165f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org state = NULL; 166f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 167f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (FLAG_trace_check_elimination) { 168f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org PrintF("Processing B%d, checkmaps-table:\n", block->block_id()); 169f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org Print(state); 170f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 171f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org return state; 172f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 173f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 174f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org private: 175f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Copy state to successor block. 17605150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) { 177af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org HCheckTable* copy = new(zone) HCheckTable(phase_); 178cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < size_; i++) { 179cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* old_entry = &entries_[i]; 180e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(old_entry->maps_->size() > 0); 181cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* new_entry = ©->entries_[i]; 182cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org new_entry->object_ = old_entry->object_; 183af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org new_entry->maps_ = old_entry->maps_; 184a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org new_entry->state_ = old_entry->state_; 185f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Keep the check if the existing check's block dominates the successor. 186f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (old_entry->check_ != NULL && 187f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org old_entry->check_->block()->Dominates(succ)) { 188f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org new_entry->check_ = old_entry->check_; 189f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else { 190f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Leave it NULL till we meet a new check instruction for this object 191f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // in the control flow. 192f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org new_entry->check_ = NULL; 193f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 194cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 195ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org copy->cursor_ = cursor_; 196ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org copy->size_ = size_; 197ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org 198f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Create entries for succ block's phis. 199f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (!succ->IsLoopHeader() && succ->phis()->length() > 0) { 200f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org int pred_index = succ->PredecessorIndexOf(from_block); 201f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org for (int phi_index = 0; 202f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org phi_index < succ->phis()->length(); 203f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org ++phi_index) { 204f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HPhi* phi = succ->phis()->at(phi_index); 205f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HValue* phi_operand = phi->OperandAt(pred_index); 206f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 207f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HCheckTableEntry* pred_entry = copy->Find(phi_operand); 208f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (pred_entry != NULL) { 209f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Create an entry for a phi in the table. 210a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org copy->Insert(phi, NULL, pred_entry->maps_, pred_entry->state_); 211f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 212f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 213f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 214f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 215ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org // Branch-sensitive analysis for certain comparisons may add more facts 216ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org // to the state for the successor on the true branch. 21705150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org bool learned = false; 218f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (succ->predecessors()->length() == 1) { 219f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HControlInstruction* end = succ->predecessors()->at(0)->end(); 220f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org bool is_true_branch = end->SuccessorAt(0) == succ; 221ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org if (end->IsCompareMap()) { 222ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org HCompareMap* cmp = HCompareMap::cast(end); 223ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org HValue* object = cmp->value()->ActualValue(); 224ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org HCheckTableEntry* entry = copy->Find(object); 225f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (is_true_branch) { 226a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry::State state = cmp->map_is_stable() 227a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org ? HCheckTableEntry::CHECKED_STABLE 228a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org : HCheckTableEntry::CHECKED; 229f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Learn on the true branch of if(CompareMap(x)). 230f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (entry == NULL) { 231a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org copy->Insert(object, cmp, cmp->map(), state); 232f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else { 233af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org entry->maps_ = new(zone) UniqueSet<Map>(cmp->map(), zone); 234f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org entry->check_ = cmp; 235a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->state_ = state; 236f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 237ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org } else { 238f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Learn on the false branch of if(CompareMap(x)). 239f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (entry != NULL) { 240a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org EnsureChecked(entry, object, cmp); 241af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet<Map>* maps = entry->maps_->Copy(zone); 242af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org maps->Remove(cmp->map()); 243af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org entry->maps_ = maps; 244e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 245f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 246ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org } 24705150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org learned = true; 248f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) { 249ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org // Learn on the true branch of if(CmpObjectEq(x, y)). 250ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org HCompareObjectEqAndBranch* cmp = 251ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org HCompareObjectEqAndBranch::cast(end); 252ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org HValue* left = cmp->left()->ActualValue(); 253ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org HValue* right = cmp->right()->ActualValue(); 254ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org HCheckTableEntry* le = copy->Find(left); 255ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org HCheckTableEntry* re = copy->Find(right); 256ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org if (le == NULL) { 257ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org if (re != NULL) { 258a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org copy->Insert(left, NULL, re->maps_, re->state_); 259ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org } 260ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org } else if (re == NULL) { 261a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org copy->Insert(right, NULL, le->maps_, le->state_); 262ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org } else { 263a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org EnsureChecked(le, cmp->left(), cmp); 264a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org EnsureChecked(re, cmp->right(), cmp); 265af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone); 266a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org le->state_ = re->state_ = HCheckTableEntry::StateMerge( 267a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org le->state_, re->state_); 268e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_); 269e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_); 270ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org } 27105150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org learned = true; 2728d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } else if (end->IsIsStringAndBranch()) { 2738d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org HIsStringAndBranch* cmp = HIsStringAndBranch::cast(end); 2748d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org HValue* object = cmp->value()->ActualValue(); 2758d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org HCheckTableEntry* entry = copy->Find(object); 2768d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (is_true_branch) { 2778d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org // Learn on the true branch of if(IsString(x)). 2788d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (entry == NULL) { 2798d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org copy->Insert(object, NULL, string_maps(), 2808d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org HCheckTableEntry::CHECKED); 2818d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } else { 2828d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org EnsureChecked(entry, object, cmp); 2838d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org entry->maps_ = entry->maps_->Intersect(string_maps(), zone); 284e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 2858d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 2868d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } else { 2878d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org // Learn on the false branch of if(IsString(x)). 2888d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (entry != NULL) { 2898d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org EnsureChecked(entry, object, cmp); 2908d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org entry->maps_ = entry->maps_->Subtract(string_maps(), zone); 291e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 2928d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 2938d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 294ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org } 295ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org // Learning on false branches requires storing negative facts. 296ce9c514a4e015930324b2b45326a478a69535388machenbach@chromium.org } 297ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org 29805150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org if (FLAG_trace_check_elimination) { 29905150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org PrintF("B%d checkmaps-table %s from B%d:\n", 30005150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org succ->block_id(), 30105150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org learned ? "learned" : "copied", 30205150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org from_block->block_id()); 303f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org Print(copy); 30405150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org } 30505150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org 306cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return copy; 307cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 308cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 309f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Merge this state with the other incoming state. 31005150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, 311f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HBasicBlock* pred_block, Zone* zone) { 312f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (that->size_ == 0) { 313f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // If the other state is empty, simply reset. 314f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org size_ = 0; 315f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org cursor_ = 0; 316f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else { 317f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org int pred_index = succ->PredecessorIndexOf(pred_block); 318f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org bool compact = false; 319f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org for (int i = 0; i < size_; i++) { 320f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HCheckTableEntry* this_entry = &entries_[i]; 321f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HCheckTableEntry* that_entry; 322f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (this_entry->object_->IsPhi() && 323f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org this_entry->object_->block() == succ) { 324f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HPhi* phi = HPhi::cast(this_entry->object_); 325f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HValue* phi_operand = phi->OperandAt(pred_index); 326f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org that_entry = that->Find(phi_operand); 327f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 328f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else { 329f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org that_entry = that->Find(this_entry->object_); 330f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 331f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 332a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (that_entry == NULL || 333a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org (that_entry->state_ == HCheckTableEntry::CHECKED && 334a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org this_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) || 335a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org (this_entry->state_ == HCheckTableEntry::CHECKED && 336a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org that_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE)) { 337f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org this_entry->object_ = NULL; 338f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org compact = true; 339f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else { 340f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org this_entry->maps_ = 341af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org this_entry->maps_->Union(that_entry->maps_, zone); 342a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org this_entry->state_ = HCheckTableEntry::StateMerge( 343a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org this_entry->state_, that_entry->state_); 344f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (this_entry->check_ != that_entry->check_) { 345f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org this_entry->check_ = NULL; 34605150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org } 347e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(this_entry->maps_->size() > 0); 34805150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org } 349cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 350f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (compact) Compact(); 351cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 352f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 35305150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org if (FLAG_trace_check_elimination) { 35405150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org PrintF("B%d checkmaps-table merged with B%d table:\n", 355f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org succ->block_id(), pred_block->block_id()); 356f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org Print(this); 35705150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org } 358cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return this; 359cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 360cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 361cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceCheckMaps(HCheckMaps* instr) { 362cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HValue* object = instr->value()->ActualValue(); 363cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = Find(object); 364cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (entry != NULL) { 365cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // entry found; 366a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HGraph* graph = instr->block()->graph(); 367a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (entry->maps_->IsSubset(instr->maps())) { 368cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // The first check is more strict; the second is redundant. 369cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (entry->check_ != NULL) { 370e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 37105150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", 37205150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org instr->id(), instr->block()->block_id(), entry->check_->id())); 373cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org instr->DeleteAndReplaceWith(entry->check_); 374cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(redundant_); 375a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 376e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_EQ(NULL, entry->check_); 377a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org TRACE(("Marking redundant CheckMaps #%d at B%d as stability check\n", 378a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org instr->id(), instr->block()->block_id())); 379a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org instr->set_maps(entry->maps_->Copy(graph->zone())); 380a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org instr->MarkAsStabilityCheck(); 381a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->state_ = HCheckTableEntry::CHECKED_STABLE; 382a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } else if (!instr->IsStabilityCheck()) { 38305150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n", 38405150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org instr->id(), instr->block()->block_id())); 38505150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org // Mark check as dead but leave it in the graph as a checkpoint for 38605150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org // subsequent checks. 38705150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org instr->SetFlag(HValue::kIsDead); 38805150ab746caefd8e734c394ecc7863200ca04cfmachenbach@chromium.org entry->check_ = instr; 389cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(removed_); 390cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 391cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org return; 392cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 393a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org MapSet intersection = instr->maps()->Intersect( 394a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->maps_, graph->zone()); 395f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (intersection->size() == 0) { 396a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // Intersection is empty; probably megamorphic. 397cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(empty_); 398a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->object_ = NULL; 399a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org Compact(); 400cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 401f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Update set of maps in the entry. 402f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org entry->maps_ = intersection; 403a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // Update state of the entry. 404a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (instr->maps_are_stable() || 405a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 406a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->state_ = HCheckTableEntry::CHECKED_STABLE; 407a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 408a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (intersection->size() != instr->maps()->size()) { 409f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Narrow set of maps in the second check maps instruction. 410f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (entry->check_ != NULL && 411f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org entry->check_->block() == instr->block() && 412f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org entry->check_->IsCheckMaps()) { 413f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // There is a check in the same block so replace it with a more 414f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // strict check and eliminate the second check entirely. 415f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HCheckMaps* check = HCheckMaps::cast(entry->check_); 416e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(!check->IsStabilityCheck()); 417f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(), 418f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org check->block()->block_id())); 419f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org // Update map set and ensure that the check is alive. 420af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org check->set_maps(intersection); 421f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org check->ClearFlag(HValue::kIsDead); 422f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", 423f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org instr->id(), instr->block()->block_id(), entry->check_->id())); 424f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org instr->DeleteAndReplaceWith(entry->check_); 425f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } else { 426f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(), 427f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org instr->block()->block_id())); 428af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org instr->set_maps(intersection); 429a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->check_ = instr->IsStabilityCheck() ? NULL : instr; 430f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 431f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 432f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (FLAG_trace_check_elimination) { 433f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org Print(this); 434f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 435f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org INC_STAT(narrowed_); 436f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 437cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 438cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 439cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // No entry; insert a new one. 440a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry::State state = instr->maps_are_stable() 441a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org ? HCheckTableEntry::CHECKED_STABLE 442a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org : HCheckTableEntry::CHECKED; 443a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr; 444a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org Insert(object, check, instr->maps(), state); 445cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 446cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 447cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 4488d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org void ReduceCheckInstanceType(HCheckInstanceType* instr) { 4498d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org HValue* value = instr->value()->ActualValue(); 4508d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org HCheckTableEntry* entry = Find(value); 4518d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (entry == NULL) { 4528d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (instr->check() == HCheckInstanceType::IS_STRING) { 4538d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED); 4548d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 4558d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org return; 4568d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 4578d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>( 4588d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org entry->maps_->size(), zone()); 4598d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org for (int i = 0; i < entry->maps_->size(); ++i) { 4608d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org InstanceType type; 4618d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org Unique<Map> map = entry->maps_->at(i); 4628d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org { 4638d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org // This is safe, because maps don't move and their instance type does 4648d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org // not change. 4658d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org AllowHandleDereference allow_deref; 4668d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org type = map.handle()->instance_type(); 4678d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 4688d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (instr->is_interval_check()) { 4698d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org InstanceType first_type, last_type; 4708d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org instr->GetCheckInterval(&first_type, &last_type); 4718d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (first_type <= type && type <= last_type) maps->Add(map, zone()); 4728d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } else { 4738d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org uint8_t mask, tag; 4748d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org instr->GetCheckMaskAndTag(&mask, &tag); 4758d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if ((type & mask) == tag) maps->Add(map, zone()); 4768d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 4778d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 4788d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (maps->size() == entry->maps_->size()) { 4798d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org TRACE(("Removing redundant CheckInstanceType #%d at B%d\n", 4808d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org instr->id(), instr->block()->block_id())); 4818d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org EnsureChecked(entry, value, instr); 4828d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org instr->DeleteAndReplaceWith(value); 4838d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org INC_STAT(removed_cit_); 4848d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } else if (maps->size() != 0) { 4858d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org entry->maps_ = maps; 4868d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 4878d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org entry->state_ = HCheckTableEntry::CHECKED_STABLE; 4888d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 4898d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 4908d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 4918d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org 492cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceLoadNamedField(HLoadNamedField* instr) { 493cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Reduce a load of the map field when it is known to be a constant. 494af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org if (!instr->access().IsMap()) { 4959fa619507474a4c1c21c6935b3209070bc13a218machenbach@chromium.org // Check if we introduce field maps here. 4965924917d324a643d00a8aefee030bd4acea0de0bmachenbach@chromium.org MapSet maps = instr->maps(); 4975924917d324a643d00a8aefee030bd4acea0de0bmachenbach@chromium.org if (maps != NULL) { 498e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NE(0, maps->size()); 499a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE); 500e9fd6580f52407c94d77bfcb4be04207f2ebb2f1machenbach@chromium.org } 501e9fd6580f52407c94d77bfcb4be04207f2ebb2f1machenbach@chromium.org return; 502e9fd6580f52407c94d77bfcb4be04207f2ebb2f1machenbach@chromium.org } 503cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 504cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HValue* object = instr->object()->ActualValue(); 505a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry* entry = Find(object); 506a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (entry == NULL || entry->maps_->size() != 1) return; // Not a constant. 507cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 508a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org EnsureChecked(entry, object, instr); 509a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org Unique<Map> map = entry->maps_->at(0); 510a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org bool map_is_stable = (entry->state_ != HCheckTableEntry::CHECKED); 511cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HConstant* constant = HConstant::CreateAndInsertBefore( 512a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org instr->block()->graph()->zone(), map, map_is_stable, instr); 513cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org instr->DeleteAndReplaceWith(constant); 514cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(loads_); 515cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 516cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 5178a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org void ReduceCheckHeapObject(HCheckHeapObject* instr) { 518a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HValue* value = instr->value()->ActualValue(); 519a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (Find(value) != NULL) { 5208a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org // If the object has known maps, it's definitely a heap object. 521a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org instr->DeleteAndReplaceWith(value); 5228a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org INC_STAT(removed_cho_); 5238a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org } 5248a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org } 5258a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org 526cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceStoreNamedField(HStoreNamedField* instr) { 527cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org HValue* object = instr->object()->ActualValue(); 528cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (instr->has_transition()) { 529cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // This store transitions the object to a new map. 530cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Kill(object); 531a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HConstant* c_transition = HConstant::cast(instr->transition()); 532a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry::State state = c_transition->HasStableMapValue() 533a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org ? HCheckTableEntry::CHECKED_STABLE 534a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org : HCheckTableEntry::CHECKED; 535a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org Insert(object, NULL, c_transition->MapValue(), state); 536af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org } else if (instr->access().IsMap()) { 537cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // This is a store directly to the map field of the object. 538cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org Kill(object); 539cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (!instr->value()->IsConstant()) return; 540a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HConstant* c_value = HConstant::cast(instr->value()); 541a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry::State state = c_value->HasStableMapValue() 542a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org ? HCheckTableEntry::CHECKED_STABLE 543a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org : HCheckTableEntry::CHECKED; 544a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org Insert(object, NULL, c_value->MapValue(), state); 545cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } else { 546cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // If the instruction changes maps, it should be handled above. 547f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org CHECK(!instr->CheckChangesFlag(kMaps)); 548cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 549cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 550cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 551cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceCompareMap(HCompareMap* instr) { 552a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry* entry = Find(instr->value()->ActualValue()); 553a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (entry == NULL) return; 554a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 555a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org EnsureChecked(entry, instr->value(), instr); 556f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 557f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org int succ; 558a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (entry->maps_->Contains(instr->map())) { 559a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (entry->maps_->size() != 1) { 560f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org TRACE(("CompareMap #%d for #%d at B%d can't be eliminated: " 561f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org "ambiguous set of maps\n", instr->id(), instr->value()->id(), 562f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org instr->block()->block_id())); 563f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org return; 564cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 565f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org succ = 0; 566f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org INC_STAT(compares_true_); 567cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 568f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org succ = 1; 569cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(compares_false_); 570cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 571f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 572f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org TRACE(("Marking redundant CompareMap #%d for #%d at B%d as %s\n", 573f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org instr->id(), instr->value()->id(), instr->block()->block_id(), 574f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org succ == 0 ? "true" : "false")); 575f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org instr->set_known_successor_index(succ); 576f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 577f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org int unreachable_succ = 1 - succ; 578f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 579cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 580cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 5818545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org void ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) { 582a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HValue* left = instr->left()->ActualValue(); 583a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry* le = Find(left); 584a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (le == NULL) return; 585a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HValue* right = instr->right()->ActualValue(); 586a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry* re = Find(right); 587a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (re == NULL) return; 588a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 589a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org EnsureChecked(le, left, instr); 590a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org EnsureChecked(re, right, instr); 591a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 592a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // TODO(bmeurer): Add a predicate here instead of computing the intersection 593a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org MapSet intersection = le->maps_->Intersect(re->maps_, zone()); 5948545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org if (intersection->size() > 0) return; 5958545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org 5968545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n", 5978545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org instr->id(), instr->block()->block_id())); 5988545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org int succ = 1; 5998545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org instr->set_known_successor_index(succ); 6008545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org 6018545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org int unreachable_succ = 1 - succ; 6028545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 6038545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org } 6048545d496a480910c08fd03335583971e4c6ea805machenbach@chromium.org 6058d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org void ReduceIsStringAndBranch(HIsStringAndBranch* instr) { 6068d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org HValue* value = instr->value()->ActualValue(); 6078d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org HCheckTableEntry* entry = Find(value); 6088d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (entry == NULL) return; 6098d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org EnsureChecked(entry, value, instr); 6108d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org int succ; 6118d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (entry->maps_->IsSubset(string_maps())) { 6128d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n", 6138d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org instr->id(), instr->block()->block_id())); 6148d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org succ = 0; 6158d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } else { 6168d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org MapSet intersection = entry->maps_->Intersect(string_maps(), zone()); 6178d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (intersection->size() > 0) return; 6188d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n", 6198d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org instr->id(), instr->block()->block_id())); 6208d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org succ = 1; 6218d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 6228d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org instr->set_known_successor_index(succ); 6238d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org int unreachable_succ = 1 - succ; 6248d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 6258d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 6268d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org 627cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { 628a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HValue* object = instr->object()->ActualValue(); 629a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry* entry = Find(object); 630cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Can only learn more about an object that already has a known set of maps. 631af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org if (entry == NULL) return; 632a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org EnsureChecked(entry, object, instr); 633af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org if (entry->maps_->Contains(instr->original_map())) { 634cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // If the object has the original map, it will be transitioned. 635af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet<Map>* maps = entry->maps_->Copy(zone()); 636cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org maps->Remove(instr->original_map()); 637af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org maps->Add(instr->transitioned_map(), zone()); 638af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org entry->maps_ = maps; 639cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } else { 640cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Object does not have the given map, thus the transition is redundant. 641a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org instr->DeleteAndReplaceWith(object); 642cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org INC_STAT(transitions_); 643cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 644cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 645cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 646a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org void EnsureChecked(HCheckTableEntry* entry, 647a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HValue* value, 648a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HInstruction* instr) { 649a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (entry->state_ != HCheckTableEntry::UNCHECKED_STABLE) return; 650a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HGraph* graph = instr->block()->graph(); 651a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckMaps* check = HCheckMaps::CreateAndInsertBefore( 652a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org graph->zone(), value, entry->maps_->Copy(graph->zone()), true, instr); 653a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org check->MarkAsStabilityCheck(); 654a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->state_ = HCheckTableEntry::CHECKED_STABLE; 655a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->check_ = NULL; 656a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 657a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 658052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org // Kill everything in the table. 659052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org void Kill() { 660cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org size_ = 0; 661cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org cursor_ = 0; 662cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 663cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 664a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // Kill all unstable entries in the table. 665a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org void KillUnstableEntries() { 666a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org bool compact = false; 667a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org for (int i = 0; i < size_; ++i) { 668a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry* entry = &entries_[i]; 669e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NOT_NULL(entry->object_); 670a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (entry->state_ == HCheckTableEntry::CHECKED) { 671a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->object_ = NULL; 672a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org compact = true; 673a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } else { 674a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // All checked stable entries become unchecked stable. 675a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->state_ = HCheckTableEntry::UNCHECKED_STABLE; 676a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->check_ = NULL; 677a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 678a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 679a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (compact) Compact(); 680a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 681a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 682cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Kill everything in the table that may alias {object}. 683cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void Kill(HValue* object) { 684cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org bool compact = false; 685cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < size_; i++) { 686cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = &entries_[i]; 687e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(entry->object_ != NULL); 688cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (phase_->aliasing_->MayAlias(entry->object_, object)) { 689cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org entry->object_ = NULL; 690cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org compact = true; 691cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 692cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 693cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (compact) Compact(); 694e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(Find(object) == NULL); 695cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 696cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 697cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org void Compact() { 698cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // First, compact the array in place. 699cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int max = size_, dest = 0, old_cursor = cursor_; 700cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < max; i++) { 701cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (entries_[i].object_ != NULL) { 702cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (dest != i) entries_[dest] = entries_[i]; 703cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org dest++; 704cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } else { 705cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (i < old_cursor) cursor_--; 706cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org size_--; 707cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 708cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 709e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(size_ == dest); 710e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(cursor_ <= size_); 711cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 712cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Preserve the age of the entries by moving the older entries to the end. 713cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (cursor_ == size_) return; // Cursor already points at end. 714cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (cursor_ != 0) { 715cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // | L = oldest | R = newest | | 716cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // ^ cursor ^ size ^ MAX 717cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry tmp_entries[kMaxTrackedObjects]; 718cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int L = cursor_; 719cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int R = size_ - cursor_; 720cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 721d06b9264b1c886fc80a100e9915cf8ae07fdb4e5machenbach@chromium.org MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry)); 722d06b9264b1c886fc80a100e9915cf8ae07fdb4e5machenbach@chromium.org MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry)); 723d06b9264b1c886fc80a100e9915cf8ae07fdb4e5machenbach@chromium.org MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry)); 724cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 725cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 726cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org cursor_ = size_; // Move cursor to end. 727cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 728cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 729f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org static void Print(HCheckTable* table) { 730f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org if (table == NULL) { 731f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org PrintF(" unreachable\n"); 732f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org return; 733f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org } 734f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org 735f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org for (int i = 0; i < table->size_; i++) { 736f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org HCheckTableEntry* entry = &table->entries_[i]; 737e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(entry->object_ != NULL); 738f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org PrintF(" checkmaps-table @%d: %s #%d ", i, 739f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org entry->object_->IsPhi() ? "phi" : "object", entry->object_->id()); 740cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (entry->check_ != NULL) { 741cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org PrintF("check #%d ", entry->check_->id()); 742cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 743cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org MapSet list = entry->maps_; 744a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org PrintF("%d %s maps { ", list->size(), 745a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry::State2String(entry->state_)); 746cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org for (int j = 0; j < list->size(); j++) { 747cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (j > 0) PrintF(", "); 748cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); 749cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 750cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org PrintF(" }\n"); 751cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 752cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 753cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 754cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* Find(HValue* object) { 755cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = size_ - 1; i >= 0; i--) { 756cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Search from most-recently-inserted to least-recently-inserted. 757cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = &entries_[i]; 758e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(entry->object_ != NULL); 759cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry; 760cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 761cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return NULL; 762cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 763cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 764a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org void Insert(HValue* object, 765a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HInstruction* check, 766a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org Unique<Map> map, 767a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry::State state) { 768a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state); 769cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 770cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 771a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org void Insert(HValue* object, 772a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HInstruction* check, 773a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org MapSet maps, 774a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org HCheckTableEntry::State state) { 775e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(state != HCheckTableEntry::UNCHECKED_STABLE || check == NULL); 776cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry* entry = &entries_[cursor_++]; 777cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org entry->object_ = object; 778cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org entry->check_ = check; 779cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org entry->maps_ = maps; 780a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org entry->state_ = state; 781cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // If the table becomes full, wrap around and overwrite older entries. 782cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (cursor_ == kMaxTrackedObjects) cursor_ = 0; 783cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (size_ < kMaxTrackedObjects) size_++; 784cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 785cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 786af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org Zone* zone() const { return phase_->zone(); } 7878d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org MapSet string_maps() const { return phase_->string_maps(); } 788af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org 789cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org friend class HCheckMapsEffects; 790f5a24546072ecdbbd6372c85c42157e01e913561titzer@chromium.org friend class HCheckEliminationPhase; 791cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 792cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckEliminationPhase* phase_; 793cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTableEntry entries_[kMaxTrackedObjects]; 794cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int16_t cursor_; // Must be <= kMaxTrackedObjects 795cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org int16_t size_; // Must be <= kMaxTrackedObjects 796a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org STATIC_ASSERT(kMaxTrackedObjects < (1 << 15)); 797cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org}; 798cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 799cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 800cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// Collects instructions that can cause effects that invalidate information 801cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// needed for check elimination. 802cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgclass HCheckMapsEffects : public ZoneObject { 803cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org public: 804a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org explicit HCheckMapsEffects(Zone* zone) : objects_(0, zone) { } 805cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 806af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org // Effects are _not_ disabled. 807af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org inline bool Disabled() const { return false; } 808cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 809cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Process a possibly side-effecting instruction. 810cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org void Process(HInstruction* instr, Zone* zone) { 811052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org switch (instr->opcode()) { 812052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org case HValue::kStoreNamedField: { 813af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org HStoreNamedField* store = HStoreNamedField::cast(instr); 8146a4d394882dba70a85567fb90ffd4f428a9eb170machenbach@chromium.org if (store->access().IsMap() || store->has_transition()) { 815af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org objects_.Add(store->object(), zone); 816af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org } 817052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org break; 818052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org } 819af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org case HValue::kTransitionElementsKind: { 820af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone); 821af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org break; 822052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org } 823052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org default: { 824a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org flags_.Add(instr->ChangesFlags()); 825a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org break; 826052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org } 827cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 828cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 829cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 830cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Apply these effects to the given check elimination table. 831cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org void Apply(HCheckTable* table) { 832a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (flags_.Contains(kOsrEntries)) { 833cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Uncontrollable map modifications; kill everything. 834052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org table->Kill(); 835cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org return; 836cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 837cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 838a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org // Kill all unstable entries. 839a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) { 840a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org table->KillUnstableEntries(); 841a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org } 842a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org 843af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org // Kill maps for each object contained in these effects. 844af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org for (int i = 0; i < objects_.length(); ++i) { 845af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org table->Kill(objects_[i]->ActualValue()); 846cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 847cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 848cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 849cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Union these effects with the other effects. 850cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org void Union(HCheckMapsEffects* that, Zone* zone) { 851a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org flags_.Add(that->flags_); 852af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org for (int i = 0; i < that->objects_.length(); ++i) { 853af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org objects_.Add(that->objects_[i], zone); 854cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 855cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 856cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 857cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org private: 858af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org ZoneList<HValue*> objects_; 859a3b66334e4dd35d9d4874d275ef9c4a756f0225cmachenbach@chromium.org GVNFlagSet flags_; 860cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org}; 861cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 862cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 863cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// The main routine of the analysis phase. Use the HFlowEngine for either a 864cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// local or a global analysis. 865cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgvoid HCheckEliminationPhase::Run() { 866cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone()); 867cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org HCheckTable* table = new(zone()) HCheckTable(this); 868cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 869cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (GLOBAL) { 870cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Perform a global analysis. 871cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table); 872cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } else { 873cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org // Perform only local analysis. 874cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org for (int i = 0; i < graph()->blocks()->length(); i++) { 875052c9560e8a41c723726ebe914a93747d8f13285hpayer@chromium.org table->Kill(); 876cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org engine.AnalyzeOneBlock(graph()->blocks()->at(i), table); 877cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org } 878cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 879cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 880cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org if (FLAG_trace_check_elimination) PrintStats(); 881cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org} 882cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 883cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 884cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org// Are we eliminated yet? 885cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.orgvoid HCheckEliminationPhase::PrintStats() { 886cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#if DEBUG 8878a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_) 8888a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org#else 8898a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org #define PRINT_STAT(x) 890cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org#endif 8918a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(redundant); 8928a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(removed); 8938a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(removed_cho); 8948d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org PRINT_STAT(removed_cit); 8958a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(narrowed); 8968a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(loads); 8978a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(empty); 8988a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(compares_true); 8998a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(compares_false); 9008a58f6420f995bb19fff9babb261458d49d90cb1machenbach@chromium.org PRINT_STAT(transitions); 901cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org} 902cc536058448cdb26fedf76ce62f2ce91480f2ae3yangguo@chromium.org 903cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org} } // namespace v8::internal 904