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 418631 : HFieldApproximation* Copy(Zone* zone) {
30 418631 : HFieldApproximation* copy = new(zone) HFieldApproximation();
31 418631 : copy->object_ = this->object_;
32 418631 : copy->last_value_ = this->last_value_;
33 418631 : copy->next_ = this->next_ == NULL ? NULL : this->next_->Copy(zone);
34 418631 : 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 2690309 : : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { }
46 :
47 : // The main processing of instructions.
48 23992560 : HLoadEliminationTable* Process(HInstruction* instr, Zone* zone) {
49 23992560 : switch (instr->opcode()) {
50 : case HValue::kLoadNamedField: {
51 : HLoadNamedField* l = HLoadNamedField::cast(instr);
52 284140 : TRACE((" process L%d field %d (o%d)\n",
53 : instr->id(),
54 : FieldOf(l->access()),
55 0 : l->object()->ActualValue()->id()));
56 284140 : HValue* result = load(l);
57 284137 : 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 185851 : 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 185851 : HValue* result = store(s);
72 185851 : if (result == NULL) {
73 : // The store is redundant. Remove it.
74 4391 : TRACE((" remove S%d\n", instr->id()));
75 4391 : instr->DeleteAndReplaceWith(NULL);
76 : }
77 : break;
78 : }
79 : case HValue::kTransitionElementsKind: {
80 : HTransitionElementsKind* t = HTransitionElementsKind::cast(instr);
81 801 : HValue* object = t->object()->ActualValue();
82 801 : KillFieldInternal(object, FieldOf(JSArray::kElementsOffset), NULL);
83 801 : KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
84 801 : break;
85 : }
86 : default: {
87 23521822 : if (instr->CheckChangesFlag(kInobjectFields)) {
88 1811045 : TRACE((" kill-all i%d\n", instr->id()));
89 : Kill();
90 : break;
91 : }
92 21710777 : if (instr->CheckChangesFlag(kMaps)) {
93 0 : TRACE((" kill-maps i%d\n", instr->id()));
94 0 : KillOffset(JSObject::kMapOffset);
95 : }
96 21710781 : 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 21710781 : if (instr->CheckChangesFlag(kElementsPointer)) {
102 2589 : TRACE((" kill-elements i%d\n", instr->id()));
103 2589 : KillOffset(JSObject::kElementsOffset);
104 : }
105 21710781 : if (instr->CheckChangesFlag(kOsrEntries)) {
106 2369 : 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 23992616 : return this;
118 : }
119 :
120 : // Support for global analysis with HFlowEngine: Merge given state with
121 : // the other incoming state.
122 3289242 : 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 3289242 : if (succ_state == NULL) {
129 2406577 : return pred_state->Copy(succ_block, pred_block, zone);
130 : } else {
131 882665 : 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 2406577 : HLoadEliminationTable* Copy(HBasicBlock* succ, HBasicBlock* from_block,
147 : Zone* zone) {
148 : HLoadEliminationTable* copy =
149 2406579 : new(zone) HLoadEliminationTable(zone, aliasing_);
150 6564827 : copy->EnsureFields(fields_.length());
151 6564828 : for (int i = 0; i < fields_.length(); i++) {
152 1751664 : copy->fields_[i] = fields_[i] == NULL ? NULL : fields_[i]->Copy(zone);
153 : }
154 2406582 : if (FLAG_trace_load_elimination) {
155 0 : TRACE((" copy-to B%d\n", succ->block_id()));
156 0 : copy->Print();
157 : }
158 2406582 : return copy;
159 : }
160 :
161 : // Merge this state with the other incoming state.
162 882663 : HLoadEliminationTable* Merge(HBasicBlock* succ, HLoadEliminationTable* that,
163 : HBasicBlock* that_block, Zone* zone) {
164 2256003 : if (that->fields_.length() < fields_.length()) {
165 : // Drop fields not in the other table.
166 : fields_.Rewind(that->fields_.length());
167 : }
168 1338605 : for (int i = 0; i < fields_.length(); i++) {
169 : // Merge the field approximations for like fields.
170 227971 : HFieldApproximation* approx = fields_[i];
171 : HFieldApproximation* prev = NULL;
172 555823 : while (approx != NULL) {
173 : // TODO(titzer): Merging is O(N * M); sort?
174 99881 : HFieldApproximation* other = that->Find(approx->object_, i);
175 99881 : if (other == NULL || !Equal(approx->last_value_, other->last_value_)) {
176 : // Kill an entry that doesn't agree with the other value.
177 34782 : if (prev != NULL) {
178 47 : prev->next_ = approx->next_;
179 : } else {
180 34735 : fields_[i] = approx->next_;
181 : }
182 34782 : approx = approx->next_;
183 34782 : continue;
184 : }
185 : prev = approx;
186 65099 : approx = approx->next_;
187 : }
188 : }
189 882663 : if (FLAG_trace_load_elimination) {
190 0 : TRACE((" merge-to B%d\n", succ->block_id()));
191 0 : Print();
192 : }
193 882663 : 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 284139 : 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 284139 : if (field < 0) return instr;
210 :
211 253899 : HValue* object = instr->object()->ActualValue();
212 253900 : HFieldApproximation* approx = FindOrCreate(object, field);
213 :
214 284110 : if (approx->last_value_ == NULL) {
215 : // Load is not redundant. Fill out a new entry.
216 223684 : approx->last_value_ = instr;
217 223684 : return instr;
218 30213 : } else if (approx->last_value_->block()->EqualToOrDominates(
219 30213 : instr->block())) {
220 : // Eliminate the load. Reuse previously stored value or load instruction.
221 30207 : 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 362271 : HValue* store(HStoreNamedField* instr) {
232 556798 : if (instr->access().IsInobject() &&
233 185851 : !instr->access().existing_inobject_property()) {
234 8391 : TRACE((" skipping non existing property initialization store\n"));
235 8391 : return instr;
236 : }
237 :
238 : int field = FieldOf(instr->access());
239 177460 : if (field < 0) return KillIfMisaligned(instr);
240 :
241 176420 : HValue* object = instr->object()->ActualValue();
242 : HValue* value = instr->value();
243 :
244 176420 : 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 10436 : KillFieldInternal(object, FieldOf(JSObject::kMapOffset), NULL);
248 : } else {
249 : // Kill non-equivalent may-alias entries.
250 165984 : KillFieldInternal(object, field, value);
251 : }
252 176420 : HFieldApproximation* approx = FindOrCreate(object, field);
253 :
254 176420 : 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 172029 : approx->last_value_ = value;
260 172029 : 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 2627 : void KillOffset(int offset) {
271 : int field = FieldOf(offset);
272 2627 : if (field >= 0 && field < fields_.length()) {
273 2597 : fields_[field] = NULL;
274 : }
275 2627 : }
276 :
277 : // Kill all entries aliasing the given store.
278 1257 : void KillStore(HStoreNamedField* s) {
279 : int field = FieldOf(s->access());
280 1257 : if (field >= 0) {
281 1254 : KillFieldInternal(s->object()->ActualValue(), field, s->value());
282 : } else {
283 3 : KillIfMisaligned(s);
284 : }
285 1257 : }
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 99881 : HFieldApproximation* Find(HValue* object, int field) {
309 : // Search for a field approximation for this object.
310 199762 : HFieldApproximation* approx = fields_[field];
311 243206 : while (approx != NULL) {
312 246324 : if (aliasing_->MustAlias(object, approx->object_)) return approx;
313 43444 : approx = approx->next_;
314 : }
315 : return NULL;
316 : }
317 :
318 : // Find or create an entry for the given object and field pair.
319 430316 : HFieldApproximation* FindOrCreate(HValue* object, int field) {
320 430316 : EnsureFields(field + 1);
321 :
322 : // Search for a field approximation for this object.
323 1256340 : HFieldApproximation* approx = fields_[field];
324 : int count = 0;
325 923059 : while (approx != NULL) {
326 194070 : if (aliasing_->MustAlias(object, approx->object_)) return approx;
327 62431 : count++;
328 62431 : approx = approx->next_;
329 : }
330 :
331 395710 : 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 789570 : approx = new(zone_) HFieldApproximation();
337 : }
338 :
339 : // Insert the entry at the head of the list.
340 395712 : approx->object_ = object;
341 395712 : approx->last_value_ = NULL;
342 395712 : approx->next_ = fields_[field];
343 395712 : fields_[field] = approx;
344 :
345 395712 : 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 179276 : void KillFieldInternal(HValue* object, int field, HValue* value) {
351 379862 : if (field >= fields_.length()) return; // Nothing to do.
352 :
353 66843 : HFieldApproximation* approx = fields_[field];
354 : HFieldApproximation* prev = NULL;
355 181833 : while (approx != NULL) {
356 96294 : if (aliasing_->MayAlias(object, approx->object_)) {
357 26312 : if (!Equal(approx->last_value_, value)) {
358 : // Kill an aliasing entry that doesn't agree on the value.
359 21848 : if (prev != NULL) {
360 538 : prev->next_ = approx->next_;
361 : } else {
362 21310 : fields_[field] = approx->next_;
363 : }
364 21848 : approx = approx->next_;
365 21848 : continue;
366 : }
367 : }
368 : prev = approx;
369 26299 : approx = approx->next_;
370 : }
371 : }
372 :
373 327037 : bool Equal(HValue* a, HValue* b) {
374 282450 : if (a == b) return true;
375 261989 : if (a != NULL && b != NULL && a->CheckFlag(HValue::kUseGVN)) {
376 44158 : 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 1852 : HFieldApproximation* approx = fields_[field];
386 : DCHECK(approx != NULL);
387 :
388 : HFieldApproximation* prev = NULL;
389 4638 : while (approx->next_ != NULL) {
390 : prev = approx;
391 : approx = approx->next_;
392 : }
393 926 : 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 462856 : 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 461833 : if (offset >= kMaxTrackedFields * kPointerSize) return -1;
405 456644 : if ((offset % kPointerSize) != 0) return -1; // Ignore misaligned accesses.
406 434198 : return offset / kPointerSize;
407 : }
408 :
409 : // Ensure internal storage for the given number of fields.
410 2836888 : void EnsureFields(int num_fields) {
411 2836888 : if (fields_.length() < num_fields) {
412 493493 : fields_.AddBlock(NULL, num_fields - fields_.length(), zone_);
413 : }
414 2836888 : }
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 107132 : : 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 4047903 : void Process(HInstruction* instr, Zone* zone) {
447 8095806 : if (instr->IsStoreNamedField()) {
448 15814 : stores_.Add(HStoreNamedField::cast(instr), zone_);
449 : } else {
450 : flags_.Add(instr->ChangesFlags());
451 : }
452 4047903 : }
453 :
454 : // Apply these effects to the given load elimination table.
455 51906 : 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 54350 : if (flags_.Contains(kInobjectFields) || flags_.Contains(kOsrEntries)) {
459 : table->Kill();
460 51906 : return;
461 : }
462 4869 : if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) {
463 19 : table->KillOffset(JSObject::kMapOffset);
464 : }
465 4869 : 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 4958 : for (int i = 0; i < stores_.length(); i++) {
471 6215 : table->KillStore(stores_[i]);
472 : }
473 : }
474 :
475 : // Union these effects with the other effects.
476 7568 : void Union(HLoadEliminationEffects* that, Zone* zone) {
477 : flags_.Add(that->flags_);
478 19422 : for (int i = 0; i < that->stores_.length(); i++) {
479 13997 : stores_.Add(that->stores_[i], zone);
480 : }
481 7568 : }
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 283730 : void HLoadEliminationPhase::Run() {
493 : HFlowEngine<HLoadEliminationTable, HLoadEliminationEffects>
494 567460 : 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 283730 : 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 283728 : }
510 :
511 : } // namespace internal
512 : } // namespace v8
|
