Line data Source code
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-load-elimination.h"
6 :
7 : #include "src/crankshaft/hydrogen-alias-analysis.h"
8 : #include "src/crankshaft/hydrogen-flow-engine.h"
9 : #include "src/crankshaft/hydrogen-instructions.h"
10 : #include "src/objects-inl.h"
11 :
12 : namespace v8 {
13 : namespace internal {
14 :
15 : #define GLOBAL true
16 : #define TRACE(x) if (FLAG_trace_load_elimination) PrintF x
17 :
18 : static const int kMaxTrackedFields = 16;
19 : static const int kMaxTrackedObjects = 5;
20 :
21 : // An element in the field approximation list.
22 : class HFieldApproximation : public ZoneObject {
23 : public: // Just a data blob.
24 : HValue* object_;
25 : HValue* last_value_;
26 : HFieldApproximation* next_;
27 :
28 : // Recursively copy the entire linked list of field approximations.
29 404331 : HFieldApproximation* Copy(Zone* zone) {
30 404331 : HFieldApproximation* copy = new(zone) HFieldApproximation();
31 404331 : copy->object_ = this->object_;
32 404331 : copy->last_value_ = this->last_value_;
33 404331 : copy->next_ = this->next_ == NULL ? NULL : this->next_->Copy(zone);
34 404331 : return copy;
35 : }
36 : };
37 :
38 :
39 : // The main datastructure used during load/store elimination. Each in-object
40 : // field is tracked separately. For each field, store a list of known field
41 : // values for known objects.
42 : class HLoadEliminationTable : public ZoneObject {
43 : public:
44 : HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing)
45 2678229 : : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { }
46 :
47 : // The main processing of instructions.
48 23944770 : HLoadEliminationTable* Process(HInstruction* instr, Zone* zone) {
49 23944770 : switch (instr->opcode()) {
50 : case HValue::kLoadNamedField: {
51 : HLoadNamedField* l = HLoadNamedField::cast(instr);
52 282205 : TRACE((" process L%d field %d (o%d)\n",
53 : instr->id(),
54 : FieldOf(l->access()),
55 0 : l->object()->ActualValue()->id()));
56 282205 : HValue* result = load(l);
57 282205 : if (result != instr && l->CanBeReplacedWith(result)) {
58 : // The load can be replaced with a previous load or a value.
59 0 : TRACE((" replace L%d -> v%d\n", instr->id(), result->id()));
60 0 : instr->DeleteAndReplaceWith(result);
61 : }
62 : break;
63 : }
64 : case HValue::kStoreNamedField: {
65 : HStoreNamedField* s = HStoreNamedField::cast(instr);
66 184161 : TRACE((" process S%d field %d (o%d) = v%d\n",
67 : instr->id(),
68 : FieldOf(s->access()),
69 : s->object()->ActualValue()->id(),
70 0 : s->value()->id()));
71 184161 : HValue* result = store(s);
72 184161 : if (result == NULL) {
73 : // The store is redundant. Remove it.
74 4369 : TRACE((" remove S%d\n", instr->id()));
75 4369 : instr->DeleteAndReplaceWith(NULL);
76 : }
77 : break;
78 : }
79 : case HValue::kTransitionElementsKind: {
80 : HTransitionElementsKind* t = HTransitionElementsKind::cast(instr);
81 803 : HValue* object = t->object()->ActualValue();
82 803 : KillFieldInternal(object, FieldOf(JSArray::kElementsOffset), NULL);
83 803 : KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
84 803 : break;
85 : }
86 : default: {
87 23477633 : if (instr->CheckChangesFlag(kInobjectFields)) {
88 1812734 : TRACE((" kill-all i%d\n", instr->id()));
89 : Kill();
90 : break;
91 : }
92 21664899 : if (instr->CheckChangesFlag(kMaps)) {
93 0 : TRACE((" kill-maps i%d\n", instr->id()));
94 0 : KillOffset(JSObject::kMapOffset);
95 : }
96 21664900 : if (instr->CheckChangesFlag(kElementsKind)) {
97 0 : TRACE((" kill-elements-kind i%d\n", instr->id()));
98 0 : KillOffset(JSObject::kMapOffset);
99 0 : KillOffset(JSObject::kElementsOffset);
100 : }
101 21664900 : if (instr->CheckChangesFlag(kElementsPointer)) {
102 2578 : TRACE((" kill-elements i%d\n", instr->id()));
103 2578 : KillOffset(JSObject::kElementsOffset);
104 : }
105 21664900 : if (instr->CheckChangesFlag(kOsrEntries)) {
106 2365 : TRACE((" kill-osr i%d\n", instr->id()));
107 : Kill();
108 : }
109 : }
110 : // Improvements possible:
111 : // - learn from HCheckMaps for field 0
112 : // - remove unobservable stores (write-after-write)
113 : // - track cells
114 : // - track globals
115 : // - track roots
116 : }
117 23944803 : return this;
118 : }
119 :
120 : // Support for global analysis with HFlowEngine: Merge given state with
121 : // the other incoming state.
122 3273841 : static HLoadEliminationTable* Merge(HLoadEliminationTable* succ_state,
123 : HBasicBlock* succ_block,
124 : HLoadEliminationTable* pred_state,
125 : HBasicBlock* pred_block,
126 : Zone* zone) {
127 : DCHECK(pred_state != NULL);
128 3273841 : if (succ_state == NULL) {
129 2395032 : return pred_state->Copy(succ_block, pred_block, zone);
130 : } else {
131 878809 : return succ_state->Merge(succ_block, pred_state, pred_block, zone);
132 : }
133 : }
134 :
135 : // Support for global analysis with HFlowEngine: Given state merged with all
136 : // the other incoming states, prepare it for use.
137 : static HLoadEliminationTable* Finish(HLoadEliminationTable* state,
138 : HBasicBlock* block,
139 : Zone* zone) {
140 : DCHECK(state != NULL);
141 : return state;
142 : }
143 :
144 : private:
145 : // Copy state to successor block.
146 2395032 : HLoadEliminationTable* Copy(HBasicBlock* succ, HBasicBlock* from_block,
147 : Zone* zone) {
148 : HLoadEliminationTable* copy =
149 2395032 : new(zone) HLoadEliminationTable(zone, aliasing_);
150 6477653 : copy->EnsureFields(fields_.length());
151 6477654 : for (int i = 0; i < fields_.length(); i++) {
152 1687590 : copy->fields_[i] = fields_[i] == NULL ? NULL : fields_[i]->Copy(zone);
153 : }
154 2395032 : if (FLAG_trace_load_elimination) {
155 0 : TRACE((" copy-to B%d\n", succ->block_id()));
156 0 : copy->Print();
157 : }
158 2395032 : return copy;
159 : }
160 :
161 : // Merge this state with the other incoming state.
162 878809 : HLoadEliminationTable* Merge(HBasicBlock* succ, HLoadEliminationTable* that,
163 : HBasicBlock* that_block, Zone* zone) {
164 2228352 : if (that->fields_.length() < fields_.length()) {
165 : // Drop fields not in the other table.
166 : fields_.Rewind(that->fields_.length());
167 : }
168 1315349 : for (int i = 0; i < fields_.length(); i++) {
169 : // Merge the field approximations for like fields.
170 218270 : HFieldApproximation* approx = fields_[i];
171 : HFieldApproximation* prev = NULL;
172 532304 : while (approx != NULL) {
173 : // TODO(titzer): Merging is O(N * M); sort?
174 95764 : HFieldApproximation* other = that->Find(approx->object_, i);
175 95764 : if (other == NULL || !Equal(approx->last_value_, other->last_value_)) {
176 : // Kill an entry that doesn't agree with the other value.
177 34238 : if (prev != NULL) {
178 44 : prev->next_ = approx->next_;
179 : } else {
180 34194 : fields_[i] = approx->next_;
181 : }
182 34238 : approx = approx->next_;
183 34238 : continue;
184 : }
185 : prev = approx;
186 61526 : approx = approx->next_;
187 : }
188 : }
189 878809 : if (FLAG_trace_load_elimination) {
190 0 : TRACE((" merge-to B%d\n", succ->block_id()));
191 0 : Print();
192 : }
193 878809 : return this;
194 : }
195 :
196 : friend class HLoadEliminationEffects; // Calls Kill() and others.
197 : friend class HLoadEliminationPhase;
198 :
199 : private:
200 : // Process a load instruction, updating internal table state. If a previous
201 : // load or store for this object and field exists, return the new value with
202 : // which the load should be replaced. Otherwise, return {instr}.
203 282205 : HValue* load(HLoadNamedField* instr) {
204 : // There must be no loads from non observable in-object properties.
205 : DCHECK(!instr->access().IsInobject() ||
206 : instr->access().existing_inobject_property());
207 :
208 : int field = FieldOf(instr->access());
209 282205 : if (field < 0) return instr;
210 :
211 252074 : HValue* object = instr->object()->ActualValue();
212 252074 : HFieldApproximation* approx = FindOrCreate(object, field);
213 :
214 282139 : if (approx->last_value_ == NULL) {
215 : // Load is not redundant. Fill out a new entry.
216 222011 : approx->last_value_ = instr;
217 222011 : return instr;
218 30064 : } else if (approx->last_value_->block()->EqualToOrDominates(
219 30064 : instr->block())) {
220 : // Eliminate the load. Reuse previously stored value or load instruction.
221 30058 : return approx->last_value_;
222 : } else {
223 : return instr;
224 : }
225 : }
226 :
227 : // Process a store instruction, updating internal table state. If a previous
228 : // store to the same object and field makes this store redundant (e.g. because
229 : // the stored values are the same), return NULL indicating that this store
230 : // instruction is redundant. Otherwise, return {instr}.
231 359107 : HValue* store(HStoreNamedField* instr) {
232 551728 : if (instr->access().IsInobject() &&
233 184161 : !instr->access().existing_inobject_property()) {
234 8175 : TRACE((" skipping non existing property initialization store\n"));
235 8175 : return instr;
236 : }
237 :
238 : int field = FieldOf(instr->access());
239 175986 : if (field < 0) return KillIfMisaligned(instr);
240 :
241 174946 : HValue* object = instr->object()->ActualValue();
242 : HValue* value = instr->value();
243 :
244 174946 : if (instr->has_transition()) {
245 : // A transition introduces a new field and alters the map of the object.
246 : // Since the field in the object is new, it cannot alias existing entries.
247 9997 : KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
248 : } else {
249 : // Kill non-equivalent may-alias entries.
250 164949 : KillFieldInternal(object, field, value);
251 : }
252 174946 : HFieldApproximation* approx = FindOrCreate(object, field);
253 :
254 174946 : if (Equal(approx->last_value_, value)) {
255 : // The store is redundant because the field already has this value.
256 : return NULL;
257 : } else {
258 : // The store is not redundant. Update the entry.
259 170577 : approx->last_value_ = value;
260 170577 : return instr;
261 : }
262 : }
263 :
264 : // Kill everything in this table.
265 : void Kill() {
266 : fields_.Rewind(0);
267 : }
268 :
269 : // Kill all entries matching the given offset.
270 2616 : void KillOffset(int offset) {
271 : int field = FieldOf(offset);
272 2616 : if (field >= 0 && field < fields_.length()) {
273 2586 : fields_[field] = NULL;
274 : }
275 2616 : }
276 :
277 : // Kill all entries aliasing the given store.
278 1139 : void KillStore(HStoreNamedField* s) {
279 : int field = FieldOf(s->access());
280 1139 : if (field >= 0) {
281 1136 : KillFieldInternal(s->object()->ActualValue(), field, s->value());
282 : } else {
283 3 : KillIfMisaligned(s);
284 : }
285 1139 : }
286 :
287 : // Kill multiple entries in the case of a misaligned store.
288 1043 : HValue* KillIfMisaligned(HStoreNamedField* instr) {
289 : HObjectAccess access = instr->access();
290 1043 : if (access.IsInobject()) {
291 : int offset = access.offset();
292 285 : if ((offset % kPointerSize) != 0) {
293 : // Kill the field containing the first word of the access.
294 0 : HValue* object = instr->object()->ActualValue();
295 0 : int field = offset / kPointerSize;
296 0 : KillFieldInternal(object, field, NULL);
297 :
298 : // Kill the next field in case of overlap.
299 0 : int size = access.representation().size();
300 0 : int next_field = (offset + size - 1) / kPointerSize;
301 0 : if (next_field != field) KillFieldInternal(object, next_field, NULL);
302 : }
303 : }
304 1043 : return instr;
305 : }
306 :
307 : // Find an entry for the given object and field pair.
308 95764 : HFieldApproximation* Find(HValue* object, int field) {
309 : // Search for a field approximation for this object.
310 191528 : HFieldApproximation* approx = fields_[field];
311 232923 : while (approx != NULL) {
312 234970 : if (aliasing_->MustAlias(object, approx->object_)) return approx;
313 41395 : approx = approx->next_;
314 : }
315 : return NULL;
316 : }
317 :
318 : // Find or create an entry for the given object and field pair.
319 427020 : HFieldApproximation* FindOrCreate(HValue* object, int field) {
320 427020 : EnsureFields(field + 1);
321 :
322 : // Search for a field approximation for this object.
323 1246632 : HFieldApproximation* approx = fields_[field];
324 : int count = 0;
325 915729 : while (approx != NULL) {
326 192236 : if (aliasing_->MustAlias(object, approx->object_)) return approx;
327 61685 : count++;
328 61685 : approx = approx->next_;
329 : }
330 :
331 392589 : if (count >= kMaxTrackedObjects) {
332 : // Pull the last entry off the end and repurpose it for this object.
333 : approx = ReuseLastApproximation(field);
334 : } else {
335 : // Allocate a new entry.
336 783321 : approx = new(zone_) HFieldApproximation();
337 : }
338 :
339 : // Insert the entry at the head of the list.
340 392588 : approx->object_ = object;
341 392588 : approx->last_value_ = NULL;
342 392588 : approx->next_ = fields_[field];
343 392588 : fields_[field] = approx;
344 :
345 392588 : return approx;
346 : }
347 :
348 : // Kill all entries for a given field that _may_ alias the given object
349 : // and do _not_ have the given value.
350 177688 : void KillFieldInternal(HValue* object, int field, HValue* value) {
351 376555 : if (field >= fields_.length()) return; // Nothing to do.
352 :
353 66098 : HFieldApproximation* approx = fields_[field];
354 : HFieldApproximation* prev = NULL;
355 180140 : while (approx != NULL) {
356 95888 : if (aliasing_->MayAlias(object, approx->object_)) {
357 26144 : if (!Equal(approx->last_value_, value)) {
358 : // Kill an aliasing entry that doesn't agree on the value.
359 21706 : if (prev != NULL) {
360 527 : prev->next_ = approx->next_;
361 : } else {
362 21179 : fields_[field] = approx->next_;
363 : }
364 21706 : approx = approx->next_;
365 21706 : continue;
366 : }
367 : }
368 : prev = approx;
369 26238 : approx = approx->next_;
370 : }
371 : }
372 :
373 321572 : bool Equal(HValue* a, HValue* b) {
374 277180 : if (a == b) return true;
375 260101 : if (a != NULL && b != NULL && a->CheckFlag(HValue::kUseGVN)) {
376 43994 : return a->Equals(b);
377 : }
378 : return false;
379 : }
380 :
381 : // Remove the last approximation for a field so that it can be reused.
382 : // We reuse the last entry because it was the first inserted and is thus
383 : // farthest away from the current instruction.
384 : HFieldApproximation* ReuseLastApproximation(int field) {
385 1856 : HFieldApproximation* approx = fields_[field];
386 : DCHECK(approx != NULL);
387 :
388 : HFieldApproximation* prev = NULL;
389 4640 : while (approx->next_ != NULL) {
390 : prev = approx;
391 : approx = approx->next_;
392 : }
393 928 : if (prev != NULL) prev->next_ = NULL;
394 : return approx;
395 : }
396 :
397 : // Compute the field index for the given object access; -1 if not tracked.
398 : int FieldOf(HObjectAccess access) {
399 459330 : return access.IsInobject() ? FieldOf(access.offset()) : -1;
400 : }
401 :
402 : // Compute the field index for the given in-object offset; -1 if not tracked.
403 : int FieldOf(int offset) {
404 458347 : if (offset >= kMaxTrackedFields * kPointerSize) return -1;
405 453168 : if ((offset % kPointerSize) != 0) return -1; // Ignore misaligned accesses.
406 430772 : return offset / kPointerSize;
407 : }
408 :
409 : // Ensure internal storage for the given number of fields.
410 2822050 : void EnsureFields(int num_fields) {
411 2822050 : if (fields_.length() < num_fields) {
412 485280 : fields_.AddBlock(NULL, num_fields - fields_.length(), zone_);
413 : }
414 2822051 : }
415 :
416 : // Print this table to stdout.
417 0 : void Print() {
418 0 : for (int i = 0; i < fields_.length(); i++) {
419 0 : PrintF(" field %d: ", i);
420 0 : for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) {
421 0 : PrintF("[o%d =", a->object_->id());
422 0 : if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id());
423 0 : PrintF("] ");
424 : }
425 0 : PrintF("\n");
426 : }
427 0 : }
428 :
429 : Zone* zone_;
430 : ZoneList<HFieldApproximation*> fields_;
431 : HAliasAnalyzer* aliasing_;
432 : };
433 :
434 :
435 : // Support for HFlowEngine: collect store effects within loops.
436 : class HLoadEliminationEffects : public ZoneObject {
437 : public:
438 : explicit HLoadEliminationEffects(Zone* zone)
439 106872 : : zone_(zone), stores_(5, zone) { }
440 :
441 : inline bool Disabled() {
442 : return false; // Effects are _not_ disabled.
443 : }
444 :
445 : // Process a possibly side-effecting instruction.
446 4046843 : void Process(HInstruction* instr, Zone* zone) {
447 8093686 : if (instr->IsStoreNamedField()) {
448 15229 : stores_.Add(HStoreNamedField::cast(instr), zone_);
449 : } else {
450 : flags_.Add(instr->ChangesFlags());
451 : }
452 4046843 : }
453 :
454 : // Apply these effects to the given load elimination table.
455 51775 : void Apply(HLoadEliminationTable* table) {
456 : // Loads must not be hoisted past the OSR entry, therefore we kill
457 : // everything if we see an OSR entry.
458 54187 : if (flags_.Contains(kInobjectFields) || flags_.Contains(kOsrEntries)) {
459 : table->Kill();
460 51775 : return;
461 : }
462 4805 : if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) {
463 19 : table->KillOffset(JSObject::kMapOffset);
464 : }
465 4805 : if (flags_.Contains(kElementsKind) || flags_.Contains(kElementsPointer)) {
466 19 : table->KillOffset(JSObject::kElementsOffset);
467 : }
468 :
469 : // Kill non-agreeing fields for each store contained in these effects.
470 4690 : for (int i = 0; i < stores_.length(); i++) {
471 5829 : table->KillStore(stores_[i]);
472 : }
473 : }
474 :
475 : // Union these effects with the other effects.
476 7570 : void Union(HLoadEliminationEffects* that, Zone* zone) {
477 : flags_.Add(that->flags_);
478 19352 : for (int i = 0; i < that->stores_.length(); i++) {
479 13888 : stores_.Add(that->stores_[i], zone);
480 : }
481 7570 : }
482 :
483 : private:
484 : Zone* zone_;
485 : GVNFlagSet flags_;
486 : ZoneList<HStoreNamedField*> stores_;
487 : };
488 :
489 :
490 : // The main routine of the analysis phase. Use the HFlowEngine for either a
491 : // local or a global analysis.
492 283196 : void HLoadEliminationPhase::Run() {
493 : HFlowEngine<HLoadEliminationTable, HLoadEliminationEffects>
494 566393 : engine(graph(), zone());
495 : HAliasAnalyzer aliasing;
496 : HLoadEliminationTable* table =
497 : new(zone()) HLoadEliminationTable(zone(), &aliasing);
498 :
499 : if (GLOBAL) {
500 : // Perform a global analysis.
501 283197 : engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
502 : } else {
503 : // Perform only local analysis.
504 : for (int i = 0; i < graph()->blocks()->length(); i++) {
505 : table->Kill();
506 : engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
507 : }
508 : }
509 283197 : }
510 :
511 : } // namespace internal
512 : } // namespace v8
|
