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-check-elimination.h"
6 :
7 : #include "src/crankshaft/hydrogen-alias-analysis.h"
8 : #include "src/crankshaft/hydrogen-flow-engine.h"
9 : #include "src/objects-inl.h"
10 :
11 : #define GLOBAL 1
12 :
13 : // Only collect stats in debug mode.
14 : #if DEBUG
15 : #define INC_STAT(x) phase_->x++
16 : #else
17 : #define INC_STAT(x)
18 : #endif
19 :
20 : // For code de-uglification.
21 : #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
22 :
23 : namespace v8 {
24 : namespace internal {
25 :
26 : typedef const UniqueSet<Map>* MapSet;
27 :
28 : struct HCheckTableEntry {
29 : enum State {
30 : // We have seen a map check (i.e. an HCheckMaps) for these maps, so we can
31 : // use this information to eliminate further map checks, elements kind
32 : // transitions, etc.
33 : CHECKED,
34 : // Same as CHECKED, but we also know that these maps are stable.
35 : CHECKED_STABLE,
36 : // These maps are stable, but not checked (i.e. we learned this via field
37 : // type tracking or from a constant, or they were initially CHECKED_STABLE,
38 : // but became UNCHECKED_STABLE because of an instruction that changes maps
39 : // or elements kind), and we need a stability check for them in order to use
40 : // this information for check elimination (which turns them back to
41 : // CHECKED_STABLE).
42 : UNCHECKED_STABLE
43 : };
44 :
45 0 : static const char* State2String(State state) {
46 0 : switch (state) {
47 : case CHECKED: return "checked";
48 0 : case CHECKED_STABLE: return "checked stable";
49 0 : case UNCHECKED_STABLE: return "unchecked stable";
50 : }
51 0 : UNREACHABLE();
52 : return NULL;
53 : }
54 :
55 : static State StateMerge(State state1, State state2) {
56 934121 : if (state1 == state2) return state1;
57 18031 : if ((state1 == CHECKED && state2 == CHECKED_STABLE) ||
58 7382 : (state2 == CHECKED && state1 == CHECKED_STABLE)) {
59 : return CHECKED;
60 : }
61 : DCHECK((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) ||
62 : (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE));
63 : return UNCHECKED_STABLE;
64 : }
65 :
66 : HValue* object_; // The object being approximated. NULL => invalid entry.
67 : HInstruction* check_; // The last check instruction.
68 : MapSet maps_; // The set of known maps for the object.
69 : State state_; // The state of this entry.
70 : };
71 :
72 :
73 : // The main data structure used during check elimination, which stores a
74 : // set of known maps for each object.
75 : class HCheckTable : public ZoneObject {
76 : public:
77 : static const int kMaxTrackedObjects = 16;
78 :
79 : explicit HCheckTable(HCheckEliminationPhase* phase)
80 : : phase_(phase),
81 : cursor_(0),
82 2166873 : size_(0) {
83 : }
84 :
85 : // The main processing of instructions.
86 20917074 : HCheckTable* Process(HInstruction* instr, Zone* zone) {
87 20917074 : switch (instr->opcode()) {
88 : case HValue::kCheckMaps: {
89 203630 : ReduceCheckMaps(HCheckMaps::cast(instr));
90 203632 : break;
91 : }
92 : case HValue::kLoadNamedField: {
93 246860 : ReduceLoadNamedField(HLoadNamedField::cast(instr));
94 246864 : break;
95 : }
96 : case HValue::kStoreNamedField: {
97 181291 : ReduceStoreNamedField(HStoreNamedField::cast(instr));
98 181292 : break;
99 : }
100 : case HValue::kCompareMap: {
101 21996 : ReduceCompareMap(HCompareMap::cast(instr));
102 21997 : break;
103 : }
104 : case HValue::kCompareObjectEqAndBranch: {
105 42800 : ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch::cast(instr));
106 42800 : break;
107 : }
108 : case HValue::kIsStringAndBranch: {
109 454 : ReduceIsStringAndBranch(HIsStringAndBranch::cast(instr));
110 454 : break;
111 : }
112 : case HValue::kTransitionElementsKind: {
113 : ReduceTransitionElementsKind(
114 769 : HTransitionElementsKind::cast(instr));
115 769 : break;
116 : }
117 : case HValue::kCheckHeapObject: {
118 92252 : ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
119 92249 : break;
120 : }
121 : case HValue::kCheckInstanceType: {
122 43573 : ReduceCheckInstanceType(HCheckInstanceType::cast(instr));
123 43572 : break;
124 : }
125 : default: {
126 : // If the instruction changes maps uncontrollably, drop everything.
127 20083558 : if (instr->CheckChangesFlag(kOsrEntries)) {
128 : Kill();
129 : break;
130 : }
131 38812553 : if (instr->CheckChangesFlag(kElementsKind) ||
132 : instr->CheckChangesFlag(kMaps)) {
133 1350168 : KillUnstableEntries();
134 : }
135 : }
136 : // Improvements possible:
137 : // - eliminate redundant HCheckSmi instructions
138 : // - track which values have been HCheckHeapObject'd
139 : }
140 :
141 20917186 : return this;
142 : }
143 :
144 : // Support for global analysis with HFlowEngine: Merge given state with
145 : // the other incoming state.
146 3289221 : static HCheckTable* Merge(HCheckTable* succ_state, HBasicBlock* succ_block,
147 : HCheckTable* pred_state, HBasicBlock* pred_block,
148 : Zone* zone) {
149 5697188 : if (pred_state == NULL || pred_block->IsUnreachable()) {
150 : return succ_state;
151 : }
152 2407976 : if (succ_state == NULL) {
153 1883137 : return pred_state->Copy(succ_block, pred_block, zone);
154 : } else {
155 524839 : return succ_state->Merge(succ_block, pred_state, pred_block, zone);
156 : }
157 : }
158 :
159 : // Support for global analysis with HFlowEngine: Given state merged with all
160 : // the other incoming states, prepare it for use.
161 4511651 : static HCheckTable* Finish(HCheckTable* state, HBasicBlock* block,
162 : Zone* zone) {
163 4511651 : if (state == NULL) {
164 919599 : block->MarkUnreachable();
165 3592052 : } else if (block->IsUnreachable()) {
166 : state = NULL;
167 : }
168 4511635 : if (FLAG_trace_check_elimination) {
169 0 : PrintF("Processing B%d, checkmaps-table:\n", block->block_id());
170 0 : Print(state);
171 : }
172 4511635 : return state;
173 : }
174 :
175 : private:
176 : // Copy state to successor block.
177 1883598 : HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
178 1883144 : HCheckTable* copy = new(zone) HCheckTable(phase_);
179 5320983 : for (int i = 0; i < size_; i++) {
180 3437851 : HCheckTableEntry* old_entry = &entries_[i];
181 : DCHECK(old_entry->maps_->size() > 0);
182 3437851 : HCheckTableEntry* new_entry = ©->entries_[i];
183 3437851 : new_entry->object_ = old_entry->object_;
184 3437851 : new_entry->maps_ = old_entry->maps_;
185 3437851 : new_entry->state_ = old_entry->state_;
186 : // Keep the check if the existing check's block dominates the successor.
187 3569788 : if (old_entry->check_ != NULL &&
188 131949 : old_entry->check_->block()->Dominates(succ)) {
189 119313 : new_entry->check_ = old_entry->check_;
190 : } else {
191 : // Leave it NULL till we meet a new check instruction for this object
192 : // in the control flow.
193 3318526 : new_entry->check_ = NULL;
194 : }
195 : }
196 1883132 : copy->cursor_ = cursor_;
197 1883132 : copy->size_ = size_;
198 :
199 : // Create entries for succ block's phis.
200 1883132 : if (!succ->IsLoopHeader() && succ->phis()->length() > 0) {
201 150158 : int pred_index = succ->PredecessorIndexOf(from_block);
202 692934 : for (int phi_index = 0;
203 346467 : phi_index < succ->phis()->length();
204 : ++phi_index) {
205 196309 : HPhi* phi = succ->phis()->at(phi_index);
206 : HValue* phi_operand = phi->OperandAt(pred_index);
207 :
208 196309 : HCheckTableEntry* pred_entry = copy->Find(phi_operand);
209 196309 : if (pred_entry != NULL) {
210 : // Create an entry for a phi in the table.
211 9403 : copy->Insert(phi, NULL, pred_entry->maps_, pred_entry->state_);
212 : }
213 : }
214 : }
215 :
216 : // Branch-sensitive analysis for certain comparisons may add more facts
217 : // to the state for the successor on the true branch.
218 : bool learned = false;
219 1883132 : if (succ->predecessors()->length() == 1) {
220 1483381 : HControlInstruction* end = succ->predecessors()->at(0)->end();
221 1483381 : bool is_true_branch = end->SuccessorAt(0) == succ;
222 2966769 : if (end->IsCompareMap()) {
223 21996 : HCompareMap* cmp = HCompareMap::cast(end);
224 43993 : HValue* object = cmp->value()->ActualValue();
225 43993 : HCheckTableEntry* entry = copy->Find(object);
226 43993 : if (is_true_branch) {
227 : HCheckTableEntry::State state = cmp->map_is_stable()
228 : ? HCheckTableEntry::CHECKED_STABLE
229 21996 : : HCheckTableEntry::CHECKED;
230 : // Learn on the true branch of if(CompareMap(x)).
231 21996 : if (entry == NULL) {
232 15371 : copy->Insert(object, cmp, cmp->map(), state);
233 : } else {
234 6625 : entry->maps_ = new(zone) UniqueSet<Map>(cmp->map(), zone);
235 6625 : entry->check_ = cmp;
236 6625 : entry->state_ = state;
237 : }
238 : } else {
239 : // Learn on the false branch of if(CompareMap(x)).
240 21997 : if (entry != NULL) {
241 6625 : EnsureChecked(entry, object, cmp);
242 6625 : UniqueSet<Map>* maps = entry->maps_->Copy(zone);
243 6625 : maps->Remove(cmp->map());
244 6625 : entry->maps_ = maps;
245 : DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
246 : }
247 : }
248 : learned = true;
249 2159092 : } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) {
250 : // Learn on the true branch of if(CmpObjectEq(x, y)).
251 : HCompareObjectEqAndBranch* cmp =
252 : HCompareObjectEqAndBranch::cast(end);
253 42799 : HValue* left = cmp->left()->ActualValue();
254 42801 : HValue* right = cmp->right()->ActualValue();
255 42800 : HCheckTableEntry* le = copy->Find(left);
256 42801 : HCheckTableEntry* re = copy->Find(right);
257 42799 : if (le == NULL) {
258 41317 : if (re != NULL) {
259 39 : copy->Insert(left, NULL, re->maps_, re->state_);
260 : }
261 1482 : } else if (re == NULL) {
262 827 : copy->Insert(right, NULL, le->maps_, le->state_);
263 : } else {
264 655 : EnsureChecked(le, cmp->left(), cmp);
265 655 : EnsureChecked(re, cmp->right(), cmp);
266 655 : le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone);
267 : le->state_ = re->state_ = HCheckTableEntry::StateMerge(
268 1310 : le->state_, re->state_);
269 : DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_);
270 : DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_);
271 : }
272 : learned = true;
273 1396594 : } else if (end->IsIsStringAndBranch()) {
274 : HIsStringAndBranch* cmp = HIsStringAndBranch::cast(end);
275 908 : HValue* object = cmp->value()->ActualValue();
276 908 : HCheckTableEntry* entry = copy->Find(object);
277 908 : if (is_true_branch) {
278 : // Learn on the true branch of if(IsString(x)).
279 454 : if (entry == NULL) {
280 : copy->Insert(object, NULL, string_maps(),
281 448 : HCheckTableEntry::CHECKED);
282 : } else {
283 6 : EnsureChecked(entry, object, cmp);
284 6 : entry->maps_ = entry->maps_->Intersect(string_maps(), zone);
285 : DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
286 : }
287 : } else {
288 : // Learn on the false branch of if(IsString(x)).
289 454 : if (entry != NULL) {
290 6 : EnsureChecked(entry, object, cmp);
291 6 : entry->maps_ = entry->maps_->Subtract(string_maps(), zone);
292 : DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
293 : }
294 : }
295 : }
296 : // Learning on false branches requires storing negative facts.
297 : }
298 :
299 1883134 : if (FLAG_trace_check_elimination) {
300 : PrintF("B%d checkmaps-table %s from B%d:\n",
301 : succ->block_id(),
302 : learned ? "learned" : "copied",
303 0 : from_block->block_id());
304 0 : Print(copy);
305 : }
306 :
307 1883134 : return copy;
308 : }
309 :
310 : // Merge this state with the other incoming state.
311 524839 : HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that,
312 0 : HBasicBlock* pred_block, Zone* zone) {
313 524839 : if (that->size_ == 0) {
314 : // If the other state is empty, simply reset.
315 252125 : size_ = 0;
316 252125 : cursor_ = 0;
317 : } else {
318 272714 : int pred_index = succ->PredecessorIndexOf(pred_block);
319 : bool compact = false;
320 1240277 : for (int i = 0; i < size_; i++) {
321 967563 : HCheckTableEntry* this_entry = &entries_[i];
322 : HCheckTableEntry* that_entry;
323 1979754 : if (this_entry->object_->IsPhi() &&
324 44631 : this_entry->object_->block() == succ) {
325 8185 : HPhi* phi = HPhi::cast(this_entry->object_);
326 : HValue* phi_operand = phi->OperandAt(pred_index);
327 8185 : that_entry = that->Find(phi_operand);
328 :
329 : } else {
330 959375 : that_entry = that->Find(this_entry->object_);
331 : }
332 :
333 1901046 : if (that_entry == NULL ||
334 969297 : (that_entry->state_ == HCheckTableEntry::CHECKED &&
335 969281 : this_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) ||
336 971260 : (this_entry->state_ == HCheckTableEntry::CHECKED &&
337 : that_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE)) {
338 34099 : this_entry->object_ = NULL;
339 34099 : compact = true;
340 : } else {
341 : this_entry->maps_ =
342 933458 : this_entry->maps_->Union(that_entry->maps_, zone);
343 : this_entry->state_ = HCheckTableEntry::StateMerge(
344 1866932 : this_entry->state_, that_entry->state_);
345 933466 : if (this_entry->check_ != that_entry->check_) {
346 12629 : this_entry->check_ = NULL;
347 : }
348 : DCHECK(this_entry->maps_->size() > 0);
349 : }
350 : }
351 272714 : if (compact) Compact();
352 : }
353 :
354 524839 : if (FLAG_trace_check_elimination) {
355 : PrintF("B%d checkmaps-table merged with B%d table:\n",
356 0 : succ->block_id(), pred_block->block_id());
357 0 : Print(this);
358 : }
359 524839 : return this;
360 : }
361 :
362 594594 : void ReduceCheckMaps(HCheckMaps* instr) {
363 203630 : HValue* object = instr->value()->ActualValue();
364 203632 : HCheckTableEntry* entry = Find(object);
365 203632 : if (entry != NULL) {
366 : // entry found;
367 41173 : HGraph* graph = instr->block()->graph();
368 25321 : if (entry->maps_->IsSubset(instr->maps())) {
369 : // The first check is more strict; the second is redundant.
370 24359 : if (entry->check_ != NULL) {
371 : DCHECK_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
372 2077 : TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
373 0 : instr->id(), instr->block()->block_id(), entry->check_->id()));
374 2059 : instr->DeleteAndReplaceWith(entry->check_);
375 : INC_STAT(redundant_);
376 22300 : } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
377 : DCHECK_NULL(entry->check_);
378 14874 : TRACE(("Marking redundant CheckMaps #%d at B%d as stability check\n",
379 0 : instr->id(), instr->block()->block_id()));
380 14874 : instr->set_maps(entry->maps_->Copy(graph->zone()));
381 : instr->MarkAsStabilityCheck();
382 14875 : entry->state_ = HCheckTableEntry::CHECKED_STABLE;
383 7426 : } else if (!instr->IsStabilityCheck()) {
384 6776 : TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n",
385 0 : instr->id(), instr->block()->block_id()));
386 : // Mark check as dead but leave it in the graph as a checkpoint for
387 : // subsequent checks.
388 : instr->SetFlag(HValue::kIsDead);
389 6776 : entry->check_ = instr;
390 : INC_STAT(removed_);
391 : }
392 203631 : return;
393 : }
394 960 : MapSet intersection = instr->maps()->Intersect(
395 960 : entry->maps_, graph->zone());
396 960 : if (intersection->size() == 0) {
397 : // Intersection is empty; probably megamorphic.
398 : INC_STAT(empty_);
399 169 : entry->object_ = NULL;
400 169 : Compact();
401 : } else {
402 : // Update set of maps in the entry.
403 791 : entry->maps_ = intersection;
404 : // Update state of the entry.
405 996 : if (instr->maps_are_stable() ||
406 205 : entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
407 586 : entry->state_ = HCheckTableEntry::CHECKED_STABLE;
408 : }
409 791 : if (intersection->size() != instr->maps()->size()) {
410 : // Narrow set of maps in the second check maps instruction.
411 64 : if (entry->check_ != NULL &&
412 33 : entry->check_->block() == instr->block() &&
413 10 : entry->check_->IsCheckMaps()) {
414 : // There is a check in the same block so replace it with a more
415 : // strict check and eliminate the second check entirely.
416 10 : HCheckMaps* check = HCheckMaps::cast(entry->check_);
417 : DCHECK(!check->IsStabilityCheck());
418 10 : TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(),
419 0 : check->block()->block_id()));
420 : // Update map set and ensure that the check is alive.
421 : check->set_maps(intersection);
422 : check->ClearFlag(HValue::kIsDead);
423 10 : TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
424 0 : instr->id(), instr->block()->block_id(), entry->check_->id()));
425 10 : instr->DeleteAndReplaceWith(entry->check_);
426 : } else {
427 13 : TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(),
428 0 : instr->block()->block_id()));
429 : instr->set_maps(intersection);
430 13 : entry->check_ = instr->IsStabilityCheck() ? NULL : instr;
431 : }
432 :
433 23 : if (FLAG_trace_check_elimination) {
434 0 : Print(this);
435 : }
436 : INC_STAT(narrowed_);
437 : }
438 : }
439 : } else {
440 : // No entry; insert a new one.
441 : HCheckTableEntry::State state = instr->maps_are_stable()
442 : ? HCheckTableEntry::CHECKED_STABLE
443 178311 : : HCheckTableEntry::CHECKED;
444 178311 : HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr;
445 : Insert(object, check, instr->maps(), state);
446 : }
447 : }
448 :
449 131861 : void ReduceCheckInstanceType(HCheckInstanceType* instr) {
450 43572 : HValue* value = instr->value()->ActualValue();
451 43573 : HCheckTableEntry* entry = Find(value);
452 43572 : if (entry == NULL) {
453 43176 : if (instr->check() == HCheckInstanceType::IS_STRING) {
454 30597 : Insert(value, NULL, string_maps(), HCheckTableEntry::CHECKED);
455 : }
456 43572 : return;
457 : }
458 396 : UniqueSet<Map>* maps = new(zone()) UniqueSet<Map>(
459 16050 : entry->maps_->size(), zone());
460 15654 : for (int i = 0; i < entry->maps_->size(); ++i) {
461 : InstanceType type;
462 7431 : Unique<Map> map = entry->maps_->at(i);
463 : {
464 : // This is safe, because maps don't move and their instance type does
465 : // not change.
466 : AllowHandleDereference allow_deref;
467 : type = map.handle()->instance_type();
468 : }
469 7431 : if (instr->is_interval_check()) {
470 : InstanceType first_type, last_type;
471 50 : instr->GetCheckInterval(&first_type, &last_type);
472 100 : if (first_type <= type && type <= last_type) maps->Add(map, zone());
473 : } else {
474 : uint8_t mask, tag;
475 7381 : instr->GetCheckMaskAndTag(&mask, &tag);
476 14020 : if ((type & mask) == tag) maps->Add(map, zone());
477 : }
478 : }
479 396 : if (maps->size() == entry->maps_->size()) {
480 343 : TRACE(("Removing redundant CheckInstanceType #%d at B%d\n",
481 0 : instr->id(), instr->block()->block_id()));
482 343 : EnsureChecked(entry, value, instr);
483 343 : instr->DeleteAndReplaceWith(value);
484 : INC_STAT(removed_cit_);
485 53 : } else if (maps->size() != 0) {
486 53 : entry->maps_ = maps;
487 53 : if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
488 0 : entry->state_ = HCheckTableEntry::CHECKED_STABLE;
489 : }
490 : }
491 : }
492 :
493 471983 : void ReduceLoadNamedField(HLoadNamedField* instr) {
494 : // Reduce a load of the map field when it is known to be a constant.
495 246863 : if (!instr->access().IsMap()) {
496 : // Check if we introduce field maps here.
497 : MapSet maps = instr->maps();
498 225120 : if (maps != NULL) {
499 : DCHECK_NE(0, maps->size());
500 : Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE);
501 : }
502 246849 : return;
503 : }
504 :
505 21743 : HValue* object = instr->object()->ActualValue();
506 21743 : HCheckTableEntry* entry = Find(object);
507 21757 : if (entry == NULL || entry->maps_->size() != 1) return; // Not a constant.
508 :
509 14 : EnsureChecked(entry, object, instr);
510 28 : Unique<Map> map = entry->maps_->at(0);
511 14 : bool map_is_stable = (entry->state_ != HCheckTableEntry::CHECKED);
512 : HConstant* constant = HConstant::CreateAndInsertBefore(
513 14 : instr->block()->graph()->zone(), map, map_is_stable, instr);
514 14 : instr->DeleteAndReplaceWith(constant);
515 : INC_STAT(loads_);
516 : }
517 :
518 92250 : void ReduceCheckHeapObject(HCheckHeapObject* instr) {
519 92250 : HValue* value = instr->value()->ActualValue();
520 92251 : if (Find(value) != NULL) {
521 : // If the object has known maps, it's definitely a heap object.
522 574 : instr->DeleteAndReplaceWith(value);
523 : INC_STAT(removed_cho_);
524 : }
525 92249 : }
526 :
527 362583 : void ReduceStoreNamedField(HStoreNamedField* instr) {
528 181291 : HValue* object = instr->object()->ActualValue();
529 181292 : if (instr->has_transition()) {
530 : // This store transitions the object to a new map.
531 11105 : Kill(object);
532 11105 : HConstant* c_transition = HConstant::cast(instr->transition());
533 : HCheckTableEntry::State state = c_transition->HasStableMapValue()
534 : ? HCheckTableEntry::CHECKED_STABLE
535 11105 : : HCheckTableEntry::CHECKED;
536 11105 : Insert(object, NULL, c_transition->MapValue(), state);
537 170187 : } else if (instr->access().IsMap()) {
538 : // This is a store directly to the map field of the object.
539 40315 : Kill(object);
540 221607 : if (!instr->value()->IsConstant()) return;
541 36300 : HConstant* c_value = HConstant::cast(instr->value());
542 : HCheckTableEntry::State state = c_value->HasStableMapValue()
543 : ? HCheckTableEntry::CHECKED_STABLE
544 36300 : : HCheckTableEntry::CHECKED;
545 36300 : Insert(object, NULL, c_value->MapValue(), state);
546 : } else {
547 : // If the instruction changes maps, it should be handled above.
548 129872 : CHECK(!instr->CheckChangesFlag(kMaps));
549 : }
550 : }
551 :
552 21996 : void ReduceCompareMap(HCompareMap* instr) {
553 21996 : HCheckTableEntry* entry = Find(instr->value()->ActualValue());
554 21996 : if (entry == NULL) return;
555 :
556 6624 : EnsureChecked(entry, instr->value(), instr);
557 :
558 : int succ;
559 13250 : if (entry->maps_->Contains(instr->map())) {
560 6553 : if (entry->maps_->size() != 1) {
561 6625 : TRACE(("CompareMap #%d for #%d at B%d can't be eliminated: "
562 : "ambiguous set of maps\n", instr->id(), instr->value()->id(),
563 0 : instr->block()->block_id()));
564 : return;
565 : }
566 : succ = 0;
567 : INC_STAT(compares_true_);
568 : } else {
569 : succ = 1;
570 : INC_STAT(compares_false_);
571 : }
572 :
573 3267 : TRACE(("Marking redundant CompareMap #%d for #%d at B%d as %s\n",
574 : instr->id(), instr->value()->id(), instr->block()->block_id(),
575 0 : succ == 0 ? "true" : "false"));
576 : instr->set_known_successor_index(succ);
577 :
578 3267 : int unreachable_succ = 1 - succ;
579 3267 : instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
580 : }
581 :
582 43453 : void ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) {
583 42799 : HValue* left = instr->left()->ActualValue();
584 42800 : HCheckTableEntry* le = Find(left);
585 42800 : if (le == NULL) return;
586 1482 : HValue* right = instr->right()->ActualValue();
587 1482 : HCheckTableEntry* re = Find(right);
588 1482 : if (re == NULL) return;
589 :
590 655 : EnsureChecked(le, left, instr);
591 655 : EnsureChecked(re, right, instr);
592 :
593 : // TODO(bmeurer): Add a predicate here instead of computing the intersection
594 655 : MapSet intersection = le->maps_->Intersect(re->maps_, zone());
595 655 : if (intersection->size() > 0) return;
596 :
597 0 : TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n",
598 0 : instr->id(), instr->block()->block_id()));
599 : int succ = 1;
600 : instr->set_known_successor_index(succ);
601 :
602 : int unreachable_succ = 1 - succ;
603 0 : instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
604 : }
605 :
606 460 : void ReduceIsStringAndBranch(HIsStringAndBranch* instr) {
607 454 : HValue* value = instr->value()->ActualValue();
608 454 : HCheckTableEntry* entry = Find(value);
609 454 : if (entry == NULL) return;
610 6 : EnsureChecked(entry, value, instr);
611 : int succ;
612 6 : if (entry->maps_->IsSubset(string_maps())) {
613 6 : TRACE(("Marking redundant IsStringAndBranch #%d at B%d as true\n",
614 0 : instr->id(), instr->block()->block_id()));
615 : succ = 0;
616 : } else {
617 6 : MapSet intersection = entry->maps_->Intersect(string_maps(), zone());
618 6 : if (intersection->size() > 0) return;
619 6 : TRACE(("Marking redundant IsStringAndBranch #%d at B%d as false\n",
620 0 : instr->id(), instr->block()->block_id()));
621 : succ = 1;
622 : }
623 : instr->set_known_successor_index(succ);
624 6 : int unreachable_succ = 1 - succ;
625 6 : instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
626 : }
627 :
628 1107 : void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
629 769 : HValue* object = instr->object()->ActualValue();
630 769 : HCheckTableEntry* entry = Find(object);
631 : // Can only learn more about an object that already has a known set of maps.
632 769 : if (entry == NULL) {
633 585 : Kill(object);
634 1354 : return;
635 : }
636 184 : EnsureChecked(entry, object, instr);
637 368 : if (entry->maps_->Contains(instr->original_map())) {
638 : // If the object has the original map, it will be transitioned.
639 169 : UniqueSet<Map>* maps = entry->maps_->Copy(zone());
640 169 : maps->Remove(instr->original_map());
641 169 : maps->Add(instr->transitioned_map(), zone());
642 : HCheckTableEntry::State state =
643 169 : (entry->state_ == HCheckTableEntry::CHECKED_STABLE &&
644 : instr->map_is_stable())
645 : ? HCheckTableEntry::CHECKED_STABLE
646 169 : : HCheckTableEntry::CHECKED;
647 169 : Kill(object);
648 : Insert(object, NULL, maps, state);
649 : } else {
650 : // Object does not have the given map, thus the transition is redundant.
651 15 : instr->DeleteAndReplaceWith(object);
652 : INC_STAT(transitions_);
653 : }
654 : }
655 :
656 16427 : void EnsureChecked(HCheckTableEntry* entry,
657 : HValue* value,
658 : HInstruction* instr) {
659 32854 : if (entry->state_ != HCheckTableEntry::UNCHECKED_STABLE) return;
660 1444 : HGraph* graph = instr->block()->graph();
661 : HCheckMaps* check = HCheckMaps::CreateAndInsertBefore(
662 1444 : graph->zone(), value, entry->maps_->Copy(graph->zone()), true, instr);
663 : check->MarkAsStabilityCheck();
664 722 : entry->state_ = HCheckTableEntry::CHECKED_STABLE;
665 722 : entry->check_ = NULL;
666 : }
667 :
668 : // Kill everything in the table.
669 : void Kill() {
670 2805 : size_ = 0;
671 2805 : cursor_ = 0;
672 : }
673 :
674 : // Kill all unstable entries in the table.
675 1378668 : void KillUnstableEntries() {
676 : bool compact = false;
677 3185306 : for (int i = 0; i < size_; ++i) {
678 1806638 : HCheckTableEntry* entry = &entries_[i];
679 : DCHECK_NOT_NULL(entry->object_);
680 1806638 : if (entry->state_ == HCheckTableEntry::CHECKED) {
681 67605 : entry->object_ = NULL;
682 : compact = true;
683 : } else {
684 : // All checked stable entries become unchecked stable.
685 1739033 : entry->state_ = HCheckTableEntry::UNCHECKED_STABLE;
686 1739033 : entry->check_ = NULL;
687 : }
688 : }
689 1378668 : if (compact) Compact();
690 1378667 : }
691 :
692 : // Kill everything in the table that may alias {object}.
693 56178 : void Kill(HValue* object) {
694 : bool compact = false;
695 215517 : for (int i = 0; i < size_; i++) {
696 159339 : HCheckTableEntry* entry = &entries_[i];
697 : DCHECK_NOT_NULL(entry->object_);
698 318678 : if (phase_->aliasing_->MayAlias(entry->object_, object)) {
699 36485 : entry->object_ = NULL;
700 : compact = true;
701 : }
702 : }
703 56178 : if (compact) Compact();
704 : DCHECK_NULL(Find(object));
705 56178 : }
706 :
707 92567 : void Compact() {
708 : // First, compact the array in place.
709 92567 : int max = size_, dest = 0, old_cursor = cursor_;
710 590938 : for (int i = 0; i < max; i++) {
711 498371 : if (entries_[i].object_ != NULL) {
712 360007 : if (dest != i) entries_[dest] = entries_[i];
713 360007 : dest++;
714 : } else {
715 138364 : if (i < old_cursor) cursor_--;
716 138364 : size_--;
717 : }
718 : }
719 : DCHECK(size_ == dest);
720 : DCHECK(cursor_ <= size_);
721 :
722 : // Preserve the age of the entries by moving the older entries to the end.
723 185134 : if (cursor_ == size_) return; // Cursor already points at end.
724 4995 : if (cursor_ != 0) {
725 : // | L = oldest | R = newest | |
726 : // ^ cursor ^ size ^ MAX
727 : HCheckTableEntry tmp_entries[kMaxTrackedObjects];
728 702 : int L = cursor_;
729 702 : int R = size_ - cursor_;
730 :
731 702 : MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry));
732 702 : MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry));
733 702 : MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry));
734 : }
735 :
736 4995 : cursor_ = size_; // Move cursor to end.
737 : }
738 :
739 0 : static void Print(HCheckTable* table) {
740 0 : if (table == NULL) {
741 0 : PrintF(" unreachable\n");
742 0 : return;
743 : }
744 :
745 0 : for (int i = 0; i < table->size_; i++) {
746 0 : HCheckTableEntry* entry = &table->entries_[i];
747 : DCHECK(entry->object_ != NULL);
748 : PrintF(" checkmaps-table @%d: %s #%d ", i,
749 0 : entry->object_->IsPhi() ? "phi" : "object", entry->object_->id());
750 0 : if (entry->check_ != NULL) {
751 0 : PrintF("check #%d ", entry->check_->id());
752 : }
753 0 : MapSet list = entry->maps_;
754 : PrintF("%d %s maps { ", list->size(),
755 0 : HCheckTableEntry::State2String(entry->state_));
756 0 : for (int j = 0; j < list->size(); j++) {
757 0 : if (j > 0) PrintF(", ");
758 0 : PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
759 : }
760 0 : PrintF(" }\n");
761 : }
762 : }
763 :
764 1723022 : HCheckTableEntry* Find(HValue* object) {
765 6668926 : for (int i = size_ - 1; i >= 0; i--) {
766 : // Search from most-recently-inserted to least-recently-inserted.
767 5940832 : HCheckTableEntry* entry = &entries_[i];
768 : DCHECK(entry->object_ != NULL);
769 11881671 : if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry;
770 : }
771 : return NULL;
772 : }
773 :
774 62776 : void Insert(HValue* object,
775 : HInstruction* check,
776 : Unique<Map> map,
777 62776 : HCheckTableEntry::State state) {
778 125552 : Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state);
779 62777 : }
780 :
781 : void Insert(HValue* object,
782 : HInstruction* check,
783 : MapSet maps,
784 : HCheckTableEntry::State state) {
785 : DCHECK(state != HCheckTableEntry::UNCHECKED_STABLE || check == NULL);
786 292638 : HCheckTableEntry* entry = &entries_[cursor_++];
787 292638 : entry->object_ = object;
788 292638 : entry->check_ = check;
789 292638 : entry->maps_ = maps;
790 292638 : entry->state_ = state;
791 : // If the table becomes full, wrap around and overwrite older entries.
792 292638 : if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
793 292638 : if (size_ < kMaxTrackedObjects) size_++;
794 : }
795 :
796 : Zone* zone() const { return phase_->zone(); }
797 : MapSet string_maps() const { return phase_->string_maps(); }
798 :
799 : friend class HCheckMapsEffects;
800 : friend class HCheckEliminationPhase;
801 :
802 : HCheckEliminationPhase* phase_;
803 : HCheckTableEntry entries_[kMaxTrackedObjects];
804 : int16_t cursor_; // Must be <= kMaxTrackedObjects
805 : int16_t size_; // Must be <= kMaxTrackedObjects
806 : STATIC_ASSERT(kMaxTrackedObjects < (1 << 15));
807 : };
808 :
809 :
810 : // Collects instructions that can cause effects that invalidate information
811 : // needed for check elimination.
812 : class HCheckMapsEffects : public ZoneObject {
813 : public:
814 52641 : explicit HCheckMapsEffects(Zone* zone) : objects_(0, zone) { }
815 :
816 : // Effects are _not_ disabled.
817 : inline bool Disabled() const { return false; }
818 :
819 : // Process a possibly side-effecting instruction.
820 3055151 : void Process(HInstruction* instr, Zone* zone) {
821 3055151 : switch (instr->opcode()) {
822 : case HValue::kStoreNamedField: {
823 12913 : HStoreNamedField* store = HStoreNamedField::cast(instr);
824 28390 : if (store->access().IsMap() || store->has_transition()) {
825 : objects_.Add(store->object(), zone);
826 : }
827 : break;
828 : }
829 : case HValue::kTransitionElementsKind: {
830 : objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone);
831 29 : break;
832 : }
833 : default: {
834 : flags_.Add(instr->ChangesFlags());
835 3039645 : break;
836 : }
837 : }
838 3055151 : }
839 :
840 : // Apply these effects to the given check elimination table.
841 50778 : void Apply(HCheckTable* table) {
842 50778 : if (flags_.Contains(kOsrEntries)) {
843 : // Uncontrollable map modifications; kill everything.
844 : table->Kill();
845 50778 : return;
846 : }
847 :
848 : // Kill all unstable entries.
849 72182 : if (flags_.Contains(kElementsKind) || flags_.Contains(kMaps)) {
850 28502 : table->KillUnstableEntries();
851 : }
852 :
853 : // Kill maps for each object contained in these effects.
854 58350 : for (int i = 0; i < objects_.length(); ++i) {
855 62354 : table->Kill(objects_[i]->ActualValue());
856 : }
857 : }
858 :
859 : // Union these effects with the other effects.
860 7484 : void Union(HCheckMapsEffects* that, Zone* zone) {
861 : flags_.Add(that->flags_);
862 15942 : for (int i = 0; i < that->objects_.length(); ++i) {
863 8945 : objects_.Add(that->objects_[i], zone);
864 : }
865 7484 : }
866 :
867 : private:
868 : ZoneList<HValue*> objects_;
869 : GVNFlagSet flags_;
870 : };
871 :
872 :
873 : // The main routine of the analysis phase. Use the HFlowEngine for either a
874 : // local or a global analysis.
875 283729 : void HCheckEliminationPhase::Run() {
876 567458 : HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone());
877 : HCheckTable* table = new(zone()) HCheckTable(this);
878 :
879 : if (GLOBAL) {
880 : // Perform a global analysis.
881 283729 : engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
882 : } else {
883 : // Perform only local analysis.
884 : for (int i = 0; i < graph()->blocks()->length(); i++) {
885 : table->Kill();
886 : engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
887 : }
888 : }
889 :
890 : if (FLAG_trace_check_elimination) PrintStats();
891 283727 : }
892 :
893 :
894 : // Are we eliminated yet?
895 0 : void HCheckEliminationPhase::PrintStats() {
896 : #if DEBUG
897 : #define PRINT_STAT(x) if (x##_ > 0) PrintF(" %-16s = %2d\n", #x, x##_)
898 : #else
899 : #define PRINT_STAT(x)
900 : #endif
901 : PRINT_STAT(redundant);
902 : PRINT_STAT(removed);
903 : PRINT_STAT(removed_cho);
904 : PRINT_STAT(removed_cit);
905 : PRINT_STAT(narrowed);
906 : PRINT_STAT(loads);
907 : PRINT_STAT(empty);
908 : PRINT_STAT(compares_true);
909 : PRINT_STAT(compares_false);
910 : PRINT_STAT(transitions);
911 0 : }
912 :
913 : } // namespace internal
914 : } // namespace v8
|
