1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2013 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/hydrogen-check-elimination.h" 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/hydrogen-alias-analysis.h" 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/hydrogen-flow-engine.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define GLOBAL 1 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Only collect stats in debug mode. 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if DEBUG 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define INC_STAT(x) phase_->x++ 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#else 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define INC_STAT(x) 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// For code de-uglification. 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtypedef const UniqueSet<Map>* MapSet; 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochstruct HCheckTableEntry { 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch enum State { 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // We have seen a map check (i.e. an HCheckMaps) for these maps, so we can 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // use this information to eliminate further map checks, elements kind 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // transitions, etc. 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECKED, 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Same as CHECKED, but we also know that these maps are stable. 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECKED_STABLE, 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // These maps are stable, but not checked (i.e. we learned this via field 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // type tracking or from a constant, or they were initially CHECKED_STABLE, 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // but became UNCHECKED_STABLE because of an instruction that changes maps 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // or elements kind), and we need a stability check for them in order to use 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // this information for check elimination (which turns them back to 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // CHECKED_STABLE). 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNCHECKED_STABLE 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const char* State2String(State state) { 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (state) { 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case CHECKED: return "checked"; 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case CHECKED_STABLE: return "checked stable"; 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case UNCHECKED_STABLE: return "unchecked stable"; 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNREACHABLE(); 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return NULL; 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static State StateMerge(State state1, State state2) { 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (state1 == state2) return state1; 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if ((state1 == CHECKED && state2 == CHECKED_STABLE) || 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch (state2 == CHECKED && state1 == CHECKED_STABLE)) { 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return CHECKED; 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) || 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE)); 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return UNCHECKED_STABLE; 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object_; // The object being approximated. NULL => invalid entry. 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* check_; // The last check instruction. 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MapSet maps_; // The set of known maps for the object. 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch State state_; // The state of this entry. 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// The main data structure used during check elimination, which stores a 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// set of known maps for each object. 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass HCheckTable : public ZoneObject { 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const int kMaxTrackedObjects = 16; 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit HCheckTable(HCheckEliminationPhase* phase) 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : phase_(phase), 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch cursor_(0), 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch size_(0) { 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The main processing of instructions. 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTable* Process(HInstruction* instr, Zone* zone) { 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (instr->opcode()) { 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kCheckMaps: { 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceCheckMaps(HCheckMaps::cast(instr)); 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kLoadNamedField: { 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceLoadNamedField(HLoadNamedField::cast(instr)); 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kStoreNamedField: { 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceStoreNamedField(HStoreNamedField::cast(instr)); 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kCompareMap: { 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceCompareMap(HCompareMap::cast(instr)); 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kCompareObjectEqAndBranch: { 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr)); 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kIsStringAndBranch: { 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr)); 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kTransitionElementsKind: { 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceTransitionElementsKind( 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HTransitionElementsKind::cast(instr)); 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kCheckHeapObject: { 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceCheckHeapObject(HCheckHeapObject::cast(instr)); 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kCheckInstanceType: { 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ReduceCheckInstanceType(HCheckInstanceType::cast(instr)); 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch default: { 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If the instruction changes maps uncontrollably, drop everything. 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->CheckChangesFlag(kOsrEntries)) { 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Kill(); 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->CheckChangesFlag(kElementsKind) || 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->CheckChangesFlag(kMaps)) { 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch KillUnstableEntries(); 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Improvements possible: 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // - eliminate redundant HCheckSmi instructions 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // - track which values have been HCheckHeapObject'd 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return this; 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Support for global analysis with HFlowEngine: Merge given state with 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // the other incoming state. 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static HCheckTable* Merge(HCheckTable* succ_state, HBasicBlock* succ_block, 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTable* pred_state, HBasicBlock* pred_block, 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone) { 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (pred_state == NULL || pred_block->IsUnreachable()) { 149b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return succ_state; 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (succ_state == NULL) { 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return pred_state->Copy(succ_block, pred_block, zone); 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return succ_state->Merge(succ_block, pred_state, pred_block, zone); 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Support for global analysis with HFlowEngine: Given state merged with all 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // the other incoming states, prepare it for use. 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static HCheckTable* Finish(HCheckTable* state, HBasicBlock* block, 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone) { 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (state == NULL) { 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch block->MarkUnreachable(); 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (block->IsUnreachable()) { 165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch state = NULL; 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_check_elimination) { 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF("Processing B%d, checkmaps-table:\n", block->block_id()); 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Print(state); 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return state; 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Copy state to successor block. 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) { 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTable* copy = new(zone) HCheckTable(phase_); 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < size_; i++) { 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* old_entry = &entries_[i]; 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(old_entry->maps_->size() > 0); 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* new_entry = ©->entries_[i]; 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new_entry->object_ = old_entry->object_; 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new_entry->maps_ = old_entry->maps_; 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new_entry->state_ = old_entry->state_; 185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Keep the check if the existing check's block dominates the successor. 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (old_entry->check_ != NULL && 187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch old_entry->check_->block()->Dominates(succ)) { 188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new_entry->check_ = old_entry->check_; 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 190b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Leave it NULL till we meet a new check instruction for this object 191b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // in the control flow. 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch new_entry->check_ = NULL; 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch copy->cursor_ = cursor_; 196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch copy->size_ = size_; 197b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Create entries for succ block's phis. 199b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!succ->IsLoopHeader() && succ->phis()->length() > 0) { 200b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int pred_index = succ->PredecessorIndexOf(from_block); 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int phi_index = 0; 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch phi_index < succ->phis()->length(); 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ++phi_index) { 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HPhi* phi = succ->phis()->at(phi_index); 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* phi_operand = phi->OperandAt(pred_index); 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* pred_entry = copy->Find(phi_operand); 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (pred_entry != NULL) { 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Create an entry for a phi in the table. 210b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch copy->Insert(phi, NULL, pred_entry->maps_, pred_entry->state_); 211b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 212b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 213b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 214b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 215b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Branch-sensitive analysis for certain comparisons may add more facts 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // to the state for the successor on the true branch. 217b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool learned = false; 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (succ->predecessors()->length() == 1) { 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HControlInstruction* end = succ->predecessors()->at(0)->end(); 220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_true_branch = end->SuccessorAt(0) == succ; 221b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (end->IsCompareMap()) { 222b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCompareMap* cmp = HCompareMap::cast(end); 223b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object = cmp->value()->ActualValue(); 224b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = copy->Find(object); 225b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (is_true_branch) { 226b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry::State state = cmp->map_is_stable() 227b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ? HCheckTableEntry::CHECKED_STABLE 228b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : HCheckTableEntry::CHECKED; 229b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Learn on the true branch of if(CompareMap(x)). 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry == NULL) { 231b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch copy->Insert(object, cmp, cmp->map(), state); 232b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 233b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_ = new(zone) UniqueSet<Map>(cmp->map(), zone); 234b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->check_ = cmp; 235b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->state_ = state; 236b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 237b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 238b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Learn on the false branch of if(CompareMap(x)). 239b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry != NULL) { 240b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(entry, object, cmp); 241b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<Map>* maps = entry->maps_->Copy(zone); 242b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch maps->Remove(cmp->map()); 243b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_ = maps; 244b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 245b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 246b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 247b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch learned = true; 248b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) { 249b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Learn on the true branch of if(CmpObjectEq(x, y)). 250b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCompareObjectEqAndBranch* cmp = 251b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCompareObjectEqAndBranch::cast(end); 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* left = cmp->left()->ActualValue(); 253b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* right = cmp->right()->ActualValue(); 254b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* le = copy->Find(left); 255b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* re = copy->Find(right); 256b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (le == NULL) { 257b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (re != NULL) { 258b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch copy->Insert(left, NULL, re->maps_, re->state_); 259b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 260b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (re == NULL) { 261b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch copy->Insert(right, NULL, le->maps_, le->state_); 262b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 263b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(le, cmp->left(), cmp); 264b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(re, cmp->right(), cmp); 265b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone); 266b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch le->state_ = re->state_ = HCheckTableEntry::StateMerge( 267b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch le->state_, re->state_); 268b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_); 269b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_); 270b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 271b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch learned = true; 272b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (end->IsIsStringAndBranch()) { 273b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HIsStringAndBranch* cmp = HIsStringAndBranch::cast(end); 274b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object = cmp->value()->ActualValue(); 275b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = copy->Find(object); 276b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (is_true_branch) { 277b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Learn on the true branch of if(IsString(x)). 278b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry == NULL) { 279b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch copy->Insert(object, NULL, string_maps(), 280b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry::CHECKED); 281b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 282b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(entry, object, cmp); 283b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_ = entry->maps_->Intersect(string_maps(), zone); 284b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 285b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 286b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 287b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Learn on the false branch of if(IsString(x)). 288b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry != NULL) { 289b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(entry, object, cmp); 290b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_ = entry->maps_->Subtract(string_maps(), zone); 291b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 292b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 293b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 294b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 295b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Learning on false branches requires storing negative facts. 296b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 297b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 298b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_check_elimination) { 299b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF("B%d checkmaps-table %s from B%d:\n", 300b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch succ->block_id(), 301b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch learned ? "learned" : "copied", 302b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch from_block->block_id()); 303b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Print(copy); 304b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 305b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 306b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return copy; 307b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 308b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 309b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Merge this state with the other incoming state. 310b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, 311b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* pred_block, Zone* zone) { 312b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (that->size_ == 0) { 313b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If the other state is empty, simply reset. 314b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch size_ = 0; 315b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch cursor_ = 0; 316b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 317b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int pred_index = succ->PredecessorIndexOf(pred_block); 318b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool compact = false; 319b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < size_; i++) { 320b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* this_entry = &entries_[i]; 321b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* that_entry; 322b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (this_entry->object_->IsPhi() && 323b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this_entry->object_->block() == succ) { 324b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HPhi* phi = HPhi::cast(this_entry->object_); 325b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* phi_operand = phi->OperandAt(pred_index); 326b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch that_entry = that->Find(phi_operand); 327b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 328b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 329b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch that_entry = that->Find(this_entry->object_); 330b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 331b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 332b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (that_entry == NULL || 333b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch (that_entry->state_ == HCheckTableEntry::CHECKED && 334b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) || 335b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch (this_entry->state_ == HCheckTableEntry::CHECKED && 336b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch that_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE)) { 337b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this_entry->object_ = NULL; 338b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch compact = true; 339b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 340b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this_entry->maps_ = 341b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this_entry->maps_->Union(that_entry->maps_, zone); 342b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this_entry->state_ = HCheckTableEntry::StateMerge( 343b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this_entry->state_, that_entry->state_); 344b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (this_entry->check_ != that_entry->check_) { 345b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this_entry->check_ = NULL; 346b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 347b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(this_entry->maps_->size() > 0); 348b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 349b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 350b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (compact) Compact(); 351b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 352b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 353b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_check_elimination) { 354b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF("B%d checkmaps-table merged with B%d table:\n", 355b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch succ->block_id(), pred_block->block_id()); 356b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Print(this); 357b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return this; 359b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 360b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 361b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceCheckMaps(HCheckMaps* instr) { 362b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object = instr->value()->ActualValue(); 363b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = Find(object); 364b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry != NULL) { 365b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // entry found; 366b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HGraph* graph = instr->block()->graph(); 367b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->maps_->IsSubset(instr->maps())) { 368b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The first check is more strict; the second is redundant. 369b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->check_ != NULL) { 370b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_); 371b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", 372b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->block()->block_id(), entry->check_->id())); 373b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->DeleteAndReplaceWith(entry->check_); 374b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(redundant_); 375b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 376b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_EQ(NULL, entry->check_); 377b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Marking redundant CheckMaps #%d at B%d as stability check\n", 378b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->block()->block_id())); 379b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->set_maps(entry->maps_->Copy(graph->zone())); 380b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->MarkAsStabilityCheck(); 381b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->state_ = HCheckTableEntry::CHECKED_STABLE; 382b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (!instr->IsStabilityCheck()) { 383b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n", 384b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->block()->block_id())); 385b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Mark check as dead but leave it in the graph as a checkpoint for 386b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // subsequent checks. 387b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->SetFlag(HValue::kIsDead); 388b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->check_ = instr; 389b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(removed_); 390b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 391b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 392b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 393b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MapSet intersection = instr->maps()->Intersect( 394b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_, graph->zone()); 395b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (intersection->size() == 0) { 396b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Intersection is empty; probably megamorphic. 397b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(empty_); 398b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->object_ = NULL; 399b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Compact(); 400b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 401b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Update set of maps in the entry. 402b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_ = intersection; 403b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Update state of the entry. 404b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->maps_are_stable() || 405b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 406b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->state_ = HCheckTableEntry::CHECKED_STABLE; 407b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 408b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (intersection->size() != instr->maps()->size()) { 409b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Narrow set of maps in the second check maps instruction. 410b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->check_ != NULL && 411b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->check_->block() == instr->block() && 412b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->check_->IsCheckMaps()) { 413b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // There is a check in the same block so replace it with a more 414b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // strict check and eliminate the second check entirely. 415b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckMaps* check = HCheckMaps::cast(entry->check_); 416b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!check->IsStabilityCheck()); 417b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(), 418b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch check->block()->block_id())); 419b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Update map set and ensure that the check is alive. 420b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch check->set_maps(intersection); 421b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch check->ClearFlag(HValue::kIsDead); 422b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n", 423b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->block()->block_id(), entry->check_->id())); 424b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->DeleteAndReplaceWith(entry->check_); 425b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 426b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(), 427b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->block()->block_id())); 428b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->set_maps(intersection); 429b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->check_ = instr->IsStabilityCheck() ? NULL : instr; 430b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 431b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 432b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_check_elimination) { 433b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Print(this); 434b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 435b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(narrowed_); 436b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 437b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 438b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 439b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // No entry; insert a new one. 440b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry::State state = instr->maps_are_stable() 441b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ? HCheckTableEntry::CHECKED_STABLE 442b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : HCheckTableEntry::CHECKED; 443b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr; 444b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(object, check, instr->maps(), state); 445b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 446b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 447b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 448b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceCheckInstanceType(HCheckInstanceType* instr) { 449b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* value = instr->value()->ActualValue(); 450b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = Find(value); 451b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry == NULL) { 452b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->check() == HCheckInstanceType::IS_STRING) { 453b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED); 454b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 455b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 456b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 457b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>( 458b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_->size(), zone()); 459b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < entry->maps_->size(); ++i) { 460b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstanceType type; 461b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<Map> map = entry->maps_->at(i); 462b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch { 463b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This is safe, because maps don't move and their instance type does 464b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // not change. 465b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AllowHandleDereference allow_deref; 466b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch type = map.handle()->instance_type(); 467b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 468b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->is_interval_check()) { 469b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch InstanceType first_type, last_type; 470b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->GetCheckInterval(&first_type, &last_type); 471b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (first_type <= type && type <= last_type) maps->Add(map, zone()); 472b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 473b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch uint8_t mask, tag; 474b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->GetCheckMaskAndTag(&mask, &tag); 475b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if ((type & mask) == tag) maps->Add(map, zone()); 476b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 477b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 478b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (maps->size() == entry->maps_->size()) { 479b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Removing redundant CheckInstanceType #%d at B%d\n", 480b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->block()->block_id())); 481b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(entry, value, instr); 482b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->DeleteAndReplaceWith(value); 483b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(removed_cit_); 484b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (maps->size() != 0) { 485b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_ = maps; 486b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) { 487b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->state_ = HCheckTableEntry::CHECKED_STABLE; 488b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 489b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 490b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 491b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 492b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceLoadNamedField(HLoadNamedField* instr) { 493b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Reduce a load of the map field when it is known to be a constant. 494b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!instr->access().IsMap()) { 495b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Check if we introduce field maps here. 496b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MapSet maps = instr->maps(); 497b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (maps != NULL) { 498b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_NE(0, maps->size()); 499b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE); 500b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 501b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 502b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 503b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 504b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object = instr->object()->ActualValue(); 505b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = Find(object); 506b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry == NULL || entry->maps_->size() != 1) return; // Not a constant. 507b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 508b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(entry, object, instr); 509b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<Map> map = entry->maps_->at(0); 510b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool map_is_stable = (entry->state_ != HCheckTableEntry::CHECKED); 511b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HConstant* constant = HConstant::CreateAndInsertBefore( 512b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->block()->graph()->zone(), map, map_is_stable, instr); 513b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->DeleteAndReplaceWith(constant); 514b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(loads_); 515b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 516b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 517b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceCheckHeapObject(HCheckHeapObject* instr) { 518b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* value = instr->value()->ActualValue(); 519b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (Find(value) != NULL) { 520b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If the object has known maps, it's definitely a heap object. 521b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->DeleteAndReplaceWith(value); 522b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(removed_cho_); 523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 524b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 525b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 526b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceStoreNamedField(HStoreNamedField* instr) { 527b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object = instr->object()->ActualValue(); 528b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->has_transition()) { 529b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This store transitions the object to a new map. 530b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Kill(object); 531b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HConstant* c_transition = HConstant::cast(instr->transition()); 532b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry::State state = c_transition->HasStableMapValue() 533b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ? HCheckTableEntry::CHECKED_STABLE 534b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : HCheckTableEntry::CHECKED; 535b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(object, NULL, c_transition->MapValue(), state); 536b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else if (instr->access().IsMap()) { 537b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This is a store directly to the map field of the object. 538b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Kill(object); 539b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!instr->value()->IsConstant()) return; 540b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HConstant* c_value = HConstant::cast(instr->value()); 541b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry::State state = c_value->HasStableMapValue() 542b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ? HCheckTableEntry::CHECKED_STABLE 543b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : HCheckTableEntry::CHECKED; 544b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(object, NULL, c_value->MapValue(), state); 545b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 546b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If the instruction changes maps, it should be handled above. 547b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!instr->CheckChangesFlag(kMaps)); 548b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 549b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 550b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 551b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceCompareMap(HCompareMap* instr) { 552b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = Find(instr->value()->ActualValue()); 553b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry == NULL) return; 554b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 555b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(entry, instr->value(), instr); 556b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 557b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int succ; 558b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->maps_->Contains(instr->map())) { 559b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->maps_->size() != 1) { 560b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("CompareMap #%d for #%d at B%d can't be eliminated: " 561b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch "ambiguous set of maps\n", instr->id(), instr->value()->id(), 562b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->block()->block_id())); 563b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 564b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 565b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch succ = 0; 566b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(compares_true_); 567b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 568b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch succ = 1; 569b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(compares_false_); 570b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 571b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 572b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Marking redundant CompareMap #%d for #%d at B%d as %s\n", 573b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->value()->id(), instr->block()->block_id(), 574b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch succ == 0 ? "true" : "false")); 575b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->set_known_successor_index(succ); 576b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 577b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int unreachable_succ = 1 - succ; 578b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 579b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 580b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 581b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) { 582b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* left = instr->left()->ActualValue(); 583b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* le = Find(left); 584b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (le == NULL) return; 585b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* right = instr->right()->ActualValue(); 586b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* re = Find(right); 587b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (re == NULL) return; 588b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 589b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(le, left, instr); 590b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(re, right, instr); 591b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 592b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // TODO(bmeurer): Add a predicate here instead of computing the intersection 593b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MapSet intersection = le->maps_->Intersect(re->maps_, zone()); 594b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (intersection->size() > 0) return; 595b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 596b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n", 597b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->block()->block_id())); 598b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int succ = 1; 599b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->set_known_successor_index(succ); 600b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 601b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int unreachable_succ = 1 - succ; 602b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 603b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 604b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 605b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceIsStringAndBranch(HIsStringAndBranch* instr) { 606b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* value = instr->value()->ActualValue(); 607b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = Find(value); 608b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry == NULL) return; 609b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(entry, value, instr); 610b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int succ; 611b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->maps_->IsSubset(string_maps())) { 612b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n", 613b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->block()->block_id())); 614b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch succ = 0; 615b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 616b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MapSet intersection = entry->maps_->Intersect(string_maps(), zone()); 617b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (intersection->size() > 0) return; 618b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n", 619b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->block()->block_id())); 620b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch succ = 1; 621b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 622b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->set_known_successor_index(succ); 623b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int unreachable_succ = 1 - succ; 624b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->block()->MarkSuccEdgeUnreachable(unreachable_succ); 625b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 626b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 627b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ReduceTransitionElementsKind(HTransitionElementsKind* instr) { 628b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object = instr->object()->ActualValue(); 629b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = Find(object); 630b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Can only learn more about an object that already has a known set of maps. 631b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry == NULL) return; 632b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EnsureChecked(entry, object, instr); 633b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->maps_->Contains(instr->original_map())) { 634b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If the object has the original map, it will be transitioned. 635b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<Map>* maps = entry->maps_->Copy(zone()); 636b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch maps->Remove(instr->original_map()); 637b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch maps->Add(instr->transitioned_map(), zone()); 638b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_ = maps; 639b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 640b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Object does not have the given map, thus the transition is redundant. 641b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->DeleteAndReplaceWith(object); 642b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch INC_STAT(transitions_); 643b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 644b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 645b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 646b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void EnsureChecked(HCheckTableEntry* entry, 647b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* value, 648b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* instr) { 649b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->state_ != HCheckTableEntry::UNCHECKED_STABLE) return; 650b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HGraph* graph = instr->block()->graph(); 651b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckMaps* check = HCheckMaps::CreateAndInsertBefore( 652b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch graph->zone(), value, entry->maps_->Copy(graph->zone()), true, instr); 653b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch check->MarkAsStabilityCheck(); 654b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->state_ = HCheckTableEntry::CHECKED_STABLE; 655b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->check_ = NULL; 656b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 657b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 658b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Kill everything in the table. 659b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Kill() { 660b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch size_ = 0; 661b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch cursor_ = 0; 662b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 663b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 664b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Kill all unstable entries in the table. 665b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void KillUnstableEntries() { 666b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool compact = false; 667b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < size_; ++i) { 668b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = &entries_[i]; 669b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK_NOT_NULL(entry->object_); 670b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->state_ == HCheckTableEntry::CHECKED) { 671b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->object_ = NULL; 672b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch compact = true; 673b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 674b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // All checked stable entries become unchecked stable. 675b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->state_ = HCheckTableEntry::UNCHECKED_STABLE; 676b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->check_ = NULL; 677b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 678b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 679b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (compact) Compact(); 680b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 681b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 682b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Kill everything in the table that may alias {object}. 683b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Kill(HValue* object) { 684b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool compact = false; 685b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < size_; i++) { 686b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = &entries_[i]; 687b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(entry->object_ != NULL); 688b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (phase_->aliasing_->MayAlias(entry->object_, object)) { 689b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->object_ = NULL; 690b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch compact = true; 691b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 692b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 693b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (compact) Compact(); 694b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Find(object) == NULL); 695b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 696b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 697b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Compact() { 698b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // First, compact the array in place. 699b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int max = size_, dest = 0, old_cursor = cursor_; 700b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < max; i++) { 701b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entries_[i].object_ != NULL) { 702b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (dest != i) entries_[dest] = entries_[i]; 703b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch dest++; 704b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 705b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (i < old_cursor) cursor_--; 706b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch size_--; 707b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 708b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 709b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(size_ == dest); 710b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(cursor_ <= size_); 711b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 712b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Preserve the age of the entries by moving the older entries to the end. 713b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (cursor_ == size_) return; // Cursor already points at end. 714b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (cursor_ != 0) { 715b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // | L = oldest | R = newest | | 716b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // ^ cursor ^ size ^ MAX 717b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry tmp_entries[kMaxTrackedObjects]; 718b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int L = cursor_; 719b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int R = size_ - cursor_; 720b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 721b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry)); 722b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry)); 723b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry)); 724b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 725b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 726b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch cursor_ = size_; // Move cursor to end. 727b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 728b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 729b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static void Print(HCheckTable* table) { 730b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (table == NULL) { 731b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF(" unreachable\n"); 732b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 733b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 734b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 735b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < table->size_; i++) { 736b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = &table->entries_[i]; 737b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(entry->object_ != NULL); 738b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF(" checkmaps-table @%d: %s #%d ", i, 739b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->object_->IsPhi() ? "phi" : "object", entry->object_->id()); 740b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (entry->check_ != NULL) { 741b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF("check #%d ", entry->check_->id()); 742b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 743b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MapSet list = entry->maps_; 744b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF("%d %s maps { ", list->size(), 745b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry::State2String(entry->state_)); 746b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int j = 0; j < list->size(); j++) { 747b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (j > 0) PrintF(", "); 748b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF("%" V8PRIxPTR, list->at(j).Hashcode()); 749b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 750b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PrintF(" }\n"); 751b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 752b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 753b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 754b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* Find(HValue* object) { 755b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = size_ - 1; i >= 0; i--) { 756b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Search from most-recently-inserted to least-recently-inserted. 757b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = &entries_[i]; 758b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(entry->object_ != NULL); 759b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry; 760b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 761b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return NULL; 762b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 763b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 764b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Insert(HValue* object, 765b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* check, 766b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<Map> map, 767b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry::State state) { 768b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state); 769b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 770b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 771b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Insert(HValue* object, 772b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* check, 773b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MapSet maps, 774b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry::State state) { 775b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(state != HCheckTableEntry::UNCHECKED_STABLE || check == NULL); 776b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry* entry = &entries_[cursor_++]; 777b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->object_ = object; 778b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->check_ = check; 779b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->maps_ = maps; 780b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch entry->state_ = state; 781b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // If the table becomes full, wrap around and overwrite older entries. 782b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (cursor_ == kMaxTrackedObjects) cursor_ = 0; 783b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (size_ < kMaxTrackedObjects) size_++; 784b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 785b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 786b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone() const { return phase_->zone(); } 787b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MapSet string_maps() const { return phase_->string_maps(); } 788b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 789b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch friend class HCheckMapsEffects; 790b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch friend class HCheckEliminationPhase; 791b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 792b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckEliminationPhase* phase_; 793b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTableEntry entries_[kMaxTrackedObjects]; 794b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int16_t cursor_; // Must be <= kMaxTrackedObjects 795b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int16_t size_; // Must be <= kMaxTrackedObjects 796b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch STATIC_ASSERT(kMaxTrackedObjects < (1 << 15)); 797b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 798b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 799b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 800b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Collects instructions that can cause effects that invalidate information 801b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// needed for check elimination. 802b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass HCheckMapsEffects : public ZoneObject { 803b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 804b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit HCheckMapsEffects(Zone* zone) : objects_(0, zone) { } 805b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 806b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Effects are _not_ disabled. 807b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline bool Disabled() const { return false; } 808b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 809b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Process a possibly side-effecting instruction. 810b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Process(HInstruction* instr, Zone* zone) { 811b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (instr->opcode()) { 812b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kStoreNamedField: { 813b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HStoreNamedField* store = HStoreNamedField::cast(instr); 814b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (store->access().IsMap() || store->has_transition()) { 815b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch objects_.Add(store->object(), zone); 816b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 817b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 818b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 819b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kTransitionElementsKind: { 820b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone); 821b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 822b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 823b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch default: { 824b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags_.Add(instr->ChangesFlags()); 825b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 826b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 827b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 828b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 829b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 830b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Apply these effects to the given check elimination table. 831b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Apply(HCheckTable* table) { 832b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (flags_.Contains(kOsrEntries)) { 833b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Uncontrollable map modifications; kill everything. 834b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch table->Kill(); 835b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 836b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 837b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 838b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Kill all unstable entries. 839b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) { 840b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch table->KillUnstableEntries(); 841b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 842b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 843b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Kill maps for each object contained in these effects. 844b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < objects_.length(); ++i) { 845b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch table->Kill(objects_[i]->ActualValue()); 846b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 847b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 848b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 849b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Union these effects with the other effects. 850b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Union(HCheckMapsEffects* that, Zone* zone) { 851b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags_.Add(that->flags_); 852b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < that->objects_.length(); ++i) { 853b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch objects_.Add(that->objects_[i], zone); 854b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 855b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 856b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 857b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 858b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ZoneList<HValue*> objects_; 859b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GVNFlagSet flags_; 860b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 861b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 862b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 863b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// The main routine of the analysis phase. Use the HFlowEngine for either a 864b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// local or a global analysis. 865b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HCheckEliminationPhase::Run() { 866b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone()); 867b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HCheckTable* table = new(zone()) HCheckTable(this); 868b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 869b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (GLOBAL) { 870b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Perform a global analysis. 871b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table); 872b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 873b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Perform only local analysis. 874b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < graph()->blocks()->length(); i++) { 875b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch table->Kill(); 876b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch engine.AnalyzeOneBlock(graph()->blocks()->at(i), table); 877b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 878b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 879b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 880b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (FLAG_trace_check_elimination) PrintStats(); 881b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 882b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 883b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 884b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Are we eliminated yet? 885b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HCheckEliminationPhase::PrintStats() { 886b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#if DEBUG 887b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_) 888b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#else 889b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch #define PRINT_STAT(x) 890b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 891b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(redundant); 892b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(removed); 893b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(removed_cho); 894b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(removed_cit); 895b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(narrowed); 896b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(loads); 897b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(empty); 898b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(compares_true); 899b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(compares_false); 900b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch PRINT_STAT(transitions); 901b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 902b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 903b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} } // namespace v8::internal 904