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