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-instructions.h" 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/hydrogen-store-elimination.h" 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define TRACE(x) if (FLAG_trace_store_elimination) PrintF x 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Performs a block-by-block local analysis for removable stores. 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HStoreEliminationPhase::Run() { 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GVNFlagSet flags; // Use GVN flags as an approximation for some instructions. 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.RemoveAll(); 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kArrayElements); 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kArrayLengths); 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kStringLengths); 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kBackingStoreFields); 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kDoubleArrayElements); 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kDoubleFields); 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kElementsPointer); 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kInobjectFields); 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kExternalMemory); 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kStringChars); 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch flags.Add(kTypedArrayElements); 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < graph()->blocks()->length(); i++) { 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unobserved_.Rewind(0); 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HBasicBlock* block = graph()->blocks()->at(i); 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!block->IsReachable()) continue; 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HInstruction* instr = it.Current(); 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->CheckFlag(HValue::kIsDead)) continue; 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // TODO(titzer): eliminate unobserved HStoreKeyed instructions too. 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (instr->opcode()) { 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kStoreNamedField: 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Remove any unobserved stores overwritten by this store. 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ProcessStore(HStoreNamedField::cast(instr)); 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch case HValue::kLoadNamedField: 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Observe any unobserved stores on this object + field. 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ProcessLoad(HLoadNamedField::cast(instr)); 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch default: 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ProcessInstr(instr, flags); 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch break; 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HStoreEliminationPhase::ProcessStore(HStoreNamedField* store) { 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object = store->object()->ActualValue(); 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int i = 0; 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (i < unobserved_.length()) { 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HStoreNamedField* prev = unobserved_.at(i); 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (aliasing_->MustAlias(object, prev->object()->ActualValue()) && 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch prev->CanBeReplacedWith(store)) { 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // This store is guaranteed to overwrite the previous store. 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch prev->DeleteAndReplaceWith(NULL); 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("++ Unobserved store S%d overwritten by S%d\n", 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch prev->id(), store->id())); 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unobserved_.Remove(i); 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // TODO(titzer): remove map word clearing from folded allocations. 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch i++; 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Only non-transitioning stores are removable. 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!store->has_transition()) { 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("-- Might remove store S%d\n", store->id())); 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unobserved_.Add(store, zone()); 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HStoreEliminationPhase::ProcessLoad(HLoadNamedField* load) { 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HValue* object = load->object()->ActualValue(); 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int i = 0; 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch while (i < unobserved_.length()) { 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HStoreNamedField* prev = unobserved_.at(i); 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (aliasing_->MayAlias(object, prev->object()->ActualValue()) && 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch load->access().Equals(prev->access())) { 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("-- Observed store S%d by load L%d\n", prev->id(), load->id())); 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unobserved_.Remove(i); 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch i++; 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid HStoreEliminationPhase::ProcessInstr(HInstruction* instr, 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch GVNFlagSet flags) { 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (unobserved_.length() == 0) return; // Nothing to do. 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->CanDeoptimize()) { 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("-- Observed stores at I%d (%s might deoptimize)\n", 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->Mnemonic())); 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unobserved_.Rewind(0); 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->CheckChangesFlag(kNewSpacePromotion)) { 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("-- Observed stores at I%d (%s might GC)\n", 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->Mnemonic())); 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unobserved_.Rewind(0); 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (instr->DependsOnFlags().ContainsAnyOf(flags)) { 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TRACE(("-- Observed stores at I%d (GVN flags of %s)\n", 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch instr->id(), instr->Mnemonic())); 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch unobserved_.Rewind(0); 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return; 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} } // namespace v8::internal 122