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