Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(254)

Side by Side Diff: src/hydrogen-load-elimination.cc

Issue 24117004: Implement local load/store elimination on basic blocks. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Indentation. Created 7 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/hydrogen-load-elimination.h ('k') | test/mjsunit/compiler/load-elimination.js » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright 2013 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28 #include "hydrogen-alias-analysis.h"
29 #include "hydrogen-load-elimination.h"
30 #include "hydrogen-instructions.h"
31
32 namespace v8 {
33 namespace internal {
34
35 static const int kMaxTrackedFields = 16;
36 static const int kMaxTrackedObjects = 5;
37
38 // An element in the field approximation list.
39 class HFieldApproximation : public ZoneObject {
40 public: // Just a data blob.
41 HValue* object_;
42 HLoadNamedField* last_load_;
43 HValue* last_value_;
44 HFieldApproximation* next_;
45 };
46
47
48 // The main datastructure used during load/store elimination. Each in-object
49 // field is tracked separately. For each field, store a list of known field
50 // values for known objects.
51 class HLoadEliminationTable BASE_EMBEDDED {
52 public:
53 HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing)
54 : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { }
55
56 // Process a load instruction, updating internal table state. If a previous
57 // load or store for this object and field exists, return the new value with
58 // which the load should be replaced. Otherwise, return {instr}.
59 HValue* load(HLoadNamedField* instr) {
60 int field = FieldOf(instr->access());
61 if (field < 0) return instr;
62
63 HValue* object = instr->object()->ActualValue();
64 HFieldApproximation* approx = FindOrCreate(object, field);
65
66 if (approx->last_value_ == NULL) {
67 // Load is not redundant. Fill out a new entry.
68 approx->last_load_ = instr;
69 approx->last_value_ = instr;
70 return instr;
71 } else {
72 // Eliminate the load. Reuse previously stored value or load instruction.
73 return approx->last_value_;
74 }
75 }
76
77 // Process a store instruction, updating internal table state. If a previous
78 // store to the same object and field makes this store redundant (e.g. because
79 // the stored values are the same), return NULL indicating that this store
80 // instruction is redundant. Otherwise, return {instr}.
81 HValue* store(HStoreNamedField* instr) {
82 int field = FieldOf(instr->access());
83 if (field < 0) return instr;
84
85 HValue* object = instr->object()->ActualValue();
86 HValue* value = instr->value();
87
88 // Kill non-equivalent may-alias entries.
89 KillFieldInternal(object, field, value);
90 if (instr->has_transition()) {
91 // A transition store alters the map of the object.
92 // TODO(titzer): remember the new map (a constant) for the object.
93 KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
94 }
95 HFieldApproximation* approx = FindOrCreate(object, field);
96
97 if (Equal(approx->last_value_, value)) {
98 // The store is redundant because the field already has this value.
99 return NULL;
100 } else {
101 // The store is not redundant. Update the entry.
102 approx->last_load_ = NULL;
103 approx->last_value_ = value;
104 return instr;
105 }
106 }
107
108 // Kill everything in this table.
109 void Kill() {
110 fields_.Rewind(0);
111 }
112
113 // Kill all entries matching the given offset.
114 void KillOffset(int offset) {
115 int field = FieldOf(offset);
116 if (field >= 0 && field < fields_.length()) {
117 fields_[field] = NULL;
118 }
119 }
120
121 // Compute the field index for the given object access; -1 if not tracked.
122 int FieldOf(HObjectAccess access) {
123 // Only track kMaxTrackedFields in-object fields.
124 if (!access.IsInobject()) return -1;
125 return FieldOf(access.offset());
126 }
127
128 // Print this table to stdout.
129 void Print() {
130 for (int i = 0; i < fields_.length(); i++) {
131 PrintF(" field %d: ", i);
132 for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) {
133 PrintF("[o%d =", a->object_->id());
134 if (a->last_load_ != NULL) PrintF(" L%d", a->last_load_->id());
135 if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id());
136 PrintF("] ");
137 }
138 PrintF("\n");
139 }
140 }
141
142 private:
143 // Find or create an entry for the given object and field pair.
144 HFieldApproximation* FindOrCreate(HValue* object, int field) {
145 EnsureFields(field + 1);
146
147 // Search for a field approximation for this object.
148 HFieldApproximation* approx = fields_[field];
149 int count = 0;
150 while (approx != NULL) {
151 if (aliasing_->MustAlias(object, approx->object_)) return approx;
152 count++;
153 approx = approx->next_;
154 }
155
156 if (count >= kMaxTrackedObjects) {
157 // Pull the last entry off the end and repurpose it for this object.
158 approx = ReuseLastApproximation(field);
159 } else {
160 // Allocate a new entry.
161 approx = new(zone_) HFieldApproximation();
162 }
163
164 // Insert the entry at the head of the list.
165 approx->object_ = object;
166 approx->last_load_ = NULL;
167 approx->last_value_ = NULL;
168 approx->next_ = fields_[field];
169 fields_[field] = approx;
170
171 return approx;
172 }
173
174 // Kill all entries for a given field that _may_ alias the given object
175 // and do _not_ have the given value.
176 void KillFieldInternal(HValue* object, int field, HValue* value) {
177 if (field >= fields_.length()) return; // Nothing to do.
178
179 HFieldApproximation* approx = fields_[field];
180 HFieldApproximation* prev = NULL;
181 while (approx != NULL) {
182 if (aliasing_->MayAlias(object, approx->object_)) {
183 if (!Equal(approx->last_value_, value)) {
184 // Kill an aliasing entry that doesn't agree on the value.
185 if (prev != NULL) {
186 prev->next_ = approx->next_;
187 } else {
188 fields_[field] = approx->next_;
189 }
190 approx = approx->next_;
191 continue;
192 }
193 }
194 prev = approx;
195 approx = approx->next_;
196 }
197 }
198
199 bool Equal(HValue* a, HValue* b) {
200 if (a == b) return true;
201 if (a != NULL && b != NULL) return a->Equals(b);
202 return false;
203 }
204
205 // Remove the last approximation for a field so that it can be reused.
206 // We reuse the last entry because it was the first inserted and is thus
207 // farthest away from the current instruction.
208 HFieldApproximation* ReuseLastApproximation(int field) {
209 HFieldApproximation* approx = fields_[field];
210 ASSERT(approx != NULL);
211
212 HFieldApproximation* prev = NULL;
213 while (approx->next_ != NULL) {
214 prev = approx;
215 approx = approx->next_;
216 }
217 if (prev != NULL) prev->next_ = NULL;
218 return approx;
219 }
220
221 // Ensure internal storage for the given number of fields.
222 void EnsureFields(int num_fields) {
223 while (fields_.length() < num_fields) fields_.Add(NULL, zone_);
224 }
225
226 // Compute the field index for the given in-object offset.
227 int FieldOf(int offset) {
228 if (offset >= kMaxTrackedFields * kPointerSize) return -1;
229 ASSERT((offset % kPointerSize) == 0); // Assume aligned accesses.
230 return offset / kPointerSize;
231 }
232
233 Zone* zone_;
234 ZoneList<HFieldApproximation*> fields_;
235 HAliasAnalyzer* aliasing_;
236 };
237
238
239 void HLoadEliminationPhase::Run() {
240 for (int i = 0; i < graph()->blocks()->length(); i++) {
241 HBasicBlock* block = graph()->blocks()->at(i);
242 EliminateLoads(block);
243 }
244 }
245
246
247 // For code de-uglification.
248 #define TRACE(x) if (FLAG_trace_load_elimination) PrintF x
249
250
251 // Eliminate loads and stores local to a block.
252 void HLoadEliminationPhase::EliminateLoads(HBasicBlock* block) {
253 HAliasAnalyzer aliasing;
254 HLoadEliminationTable table(zone(), &aliasing);
255
256 TRACE(("-- load-elim B%d -------------------------------------------------\n",
257 block->block_id()));
258
259 for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
260 bool changed = false;
261 HInstruction* instr = it.Current();
262
263 switch (instr->opcode()) {
264 case HValue::kLoadNamedField: {
265 HLoadNamedField* load = HLoadNamedField::cast(instr);
266 TRACE((" process L%d field %d (o%d)\n",
267 instr->id(),
268 table.FieldOf(load->access()),
269 load->object()->ActualValue()->id()));
270 HValue* result = table.load(load);
271 if (result != instr) {
272 // The load can be replaced with a previous load or a value.
273 TRACE((" replace L%d -> v%d\n", instr->id(), result->id()));
274 instr->DeleteAndReplaceWith(result);
275 }
276 changed = true;
277 break;
278 }
279 case HValue::kStoreNamedField: {
280 HStoreNamedField* store = HStoreNamedField::cast(instr);
281 TRACE((" process S%d field %d (o%d) = v%d\n",
282 instr->id(),
283 table.FieldOf(store->access()),
284 store->object()->ActualValue()->id(),
285 store->value()->id()));
286 HValue* result = table.store(store);
287 if (result == NULL) {
288 // The store is redundant. Remove it.
289 TRACE((" remove S%d\n", instr->id()));
290 instr->DeleteAndReplaceWith(NULL);
291 }
292 changed = true;
293 break;
294 }
295 default: {
296 if (instr->CheckGVNFlag(kChangesInobjectFields)) {
297 TRACE((" kill-all i%d\n", instr->id()));
298 table.Kill();
299 continue;
300 }
301 if (instr->CheckGVNFlag(kChangesMaps)) {
302 TRACE((" kill-maps i%d\n", instr->id()));
303 table.KillOffset(JSObject::kMapOffset);
304 }
305 if (instr->CheckGVNFlag(kChangesElementsKind)) {
306 TRACE((" kill-elements-kind i%d\n", instr->id()));
307 table.KillOffset(JSObject::kMapOffset);
308 table.KillOffset(JSObject::kElementsOffset);
309 }
310 if (instr->CheckGVNFlag(kChangesElementsPointer)) {
311 TRACE((" kill-elements i%d\n", instr->id()));
312 table.KillOffset(JSObject::kElementsOffset);
313 }
314 }
315 // Improvements possible:
316 // - learn from HCheckMaps for field 0
317 // - remove unobservable stores (write-after-write)
318 }
319
320 if (changed && FLAG_trace_load_elimination) {
321 table.Print();
322 }
323 }
324 }
325
326
327 } } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/hydrogen-load-elimination.h ('k') | test/mjsunit/compiler/load-elimination.js » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698