Line data Source code
1 : // Copyright 2012 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/lithium-allocator.h"
6 :
7 : #include "src/crankshaft/hydrogen.h"
8 : #include "src/crankshaft/lithium-allocator-inl.h"
9 : #include "src/crankshaft/lithium-inl.h"
10 : #include "src/objects-inl.h"
11 : #include "src/register-configuration.h"
12 : #include "src/string-stream.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 :
17 : const auto GetRegConfig = RegisterConfiguration::Crankshaft;
18 :
19 : static inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) {
20 48546066 : return a.Value() < b.Value() ? a : b;
21 : }
22 :
23 :
24 : static inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) {
25 28420655 : return a.Value() > b.Value() ? a : b;
26 : }
27 :
28 :
29 39644933 : UsePosition::UsePosition(LifetimePosition pos,
30 : LOperand* operand,
31 : LOperand* hint)
32 : : operand_(operand),
33 : hint_(hint),
34 : pos_(pos),
35 : next_(NULL),
36 : requires_reg_(false),
37 39644933 : register_beneficial_(true) {
38 78832907 : if (operand_ != NULL && operand_->IsUnallocated()) {
39 : LUnallocated* unalloc = LUnallocated::cast(operand_);
40 68994333 : requires_reg_ = unalloc->HasRegisterPolicy() ||
41 39188898 : unalloc->HasDoubleRegisterPolicy();
42 39188898 : register_beneficial_ = !unalloc->HasAnyPolicy();
43 : }
44 : DCHECK(pos_.IsValid());
45 39644933 : }
46 :
47 :
48 0 : bool UsePosition::HasHint() const {
49 90255189 : return hint_ != NULL && !hint_->IsUnallocated();
50 : }
51 :
52 :
53 0 : bool UsePosition::RequiresRegister() const {
54 15621658 : return requires_reg_;
55 : }
56 :
57 :
58 0 : bool UsePosition::RegisterIsBeneficial() const {
59 5335521 : return register_beneficial_;
60 : }
61 :
62 :
63 1679137 : void UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
64 : DCHECK(Contains(pos) && pos.Value() != start().Value());
65 1679137 : UseInterval* after = new(zone) UseInterval(pos, end_);
66 1679137 : after->next_ = next_;
67 1679137 : next_ = after;
68 1679137 : end_ = pos;
69 1679137 : }
70 :
71 :
72 : #ifdef DEBUG
73 :
74 :
75 : void LiveRange::Verify() const {
76 : UsePosition* cur = first_pos_;
77 : while (cur != NULL) {
78 : DCHECK(Start().Value() <= cur->pos().Value() &&
79 : cur->pos().Value() <= End().Value());
80 : cur = cur->next();
81 : }
82 : }
83 :
84 :
85 : bool LiveRange::HasOverlap(UseInterval* target) const {
86 : UseInterval* current_interval = first_interval_;
87 : while (current_interval != NULL) {
88 : // Intervals overlap if the start of one is contained in the other.
89 : if (current_interval->Contains(target->start()) ||
90 : target->Contains(current_interval->start())) {
91 : return true;
92 : }
93 : current_interval = current_interval->next();
94 : }
95 : return false;
96 : }
97 :
98 :
99 : #endif
100 :
101 :
102 15277670 : LiveRange::LiveRange(int id, Zone* zone)
103 : : id_(id),
104 : spilled_(false),
105 : kind_(UNALLOCATED_REGISTERS),
106 : assigned_register_(kInvalidAssignment),
107 : last_interval_(NULL),
108 : first_interval_(NULL),
109 : first_pos_(NULL),
110 : parent_(NULL),
111 : next_(NULL),
112 : current_interval_(NULL),
113 : last_processed_use_(NULL),
114 : current_hint_operand_(NULL),
115 : spill_operand_(new (zone) LOperand()),
116 30555022 : spill_start_index_(kMaxInt) {}
117 :
118 :
119 0 : void LiveRange::set_assigned_register(int reg, Zone* zone) {
120 : DCHECK(!HasRegisterAssigned() && !IsSpilled());
121 13395414 : assigned_register_ = reg;
122 13395414 : ConvertOperands(zone);
123 0 : }
124 :
125 :
126 0 : void LiveRange::MakeSpilled(Zone* zone) {
127 : DCHECK(!IsSpilled());
128 : DCHECK(TopLevel()->HasAllocatedSpillOperand());
129 1642594 : spilled_ = true;
130 1642594 : assigned_register_ = kInvalidAssignment;
131 1642594 : ConvertOperands(zone);
132 0 : }
133 :
134 :
135 0 : bool LiveRange::HasAllocatedSpillOperand() const {
136 : DCHECK(spill_operand_ != NULL);
137 26332767 : return !spill_operand_->IsIgnored();
138 : }
139 :
140 :
141 0 : void LiveRange::SetSpillOperand(LOperand* operand) {
142 : DCHECK(!operand->IsUnallocated());
143 : DCHECK(spill_operand_ != NULL);
144 : DCHECK(spill_operand_->IsIgnored());
145 1252443 : spill_operand_->ConvertTo(operand->kind(), operand->index());
146 0 : }
147 :
148 :
149 1992412 : UsePosition* LiveRange::NextUsePosition(LifetimePosition start) {
150 4891342 : UsePosition* use_pos = last_processed_use_;
151 3176863 : if (use_pos == NULL) use_pos = first_pos();
152 4891342 : while (use_pos != NULL && use_pos->pos().Value() < start.Value()) {
153 : use_pos = use_pos->next();
154 : }
155 3176863 : last_processed_use_ = use_pos;
156 0 : return use_pos;
157 : }
158 :
159 :
160 1157909 : UsePosition* LiveRange::NextUsePositionRegisterIsBeneficial(
161 : LifetimePosition start) {
162 4626696 : UsePosition* pos = NextUsePosition(start);
163 12239015 : while (pos != NULL && !pos->RegisterIsBeneficial()) {
164 : pos = pos->next();
165 : }
166 1157909 : return pos;
167 : }
168 :
169 :
170 0 : UsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial(
171 15081 : LifetimePosition start) {
172 39020 : UsePosition* pos = first_pos();
173 : UsePosition* prev = NULL;
174 54101 : while (pos != NULL && pos->pos().Value() < start.Value()) {
175 39020 : if (pos->RegisterIsBeneficial()) prev = pos;
176 : pos = pos->next();
177 : }
178 0 : return prev;
179 : }
180 :
181 :
182 2018954 : UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) {
183 14658243 : UsePosition* pos = NextUsePosition(start);
184 34317809 : while (pos != NULL && !pos->RequiresRegister()) {
185 : pos = pos->next();
186 : }
187 2018954 : return pos;
188 : }
189 :
190 :
191 764260 : bool LiveRange::CanBeSpilled(LifetimePosition pos) {
192 : // We cannot spill a live range that has a use requiring a register
193 : // at the current or the immediate next position.
194 764260 : UsePosition* use_pos = NextRegisterPosition(pos);
195 764260 : if (use_pos == NULL) return true;
196 : return
197 565837 : use_pos->pos().Value() > pos.NextInstruction().InstructionEnd().Value();
198 : }
199 :
200 :
201 33279628 : LOperand* LiveRange::CreateAssignedOperand(Zone* zone) {
202 : LOperand* op = NULL;
203 16639814 : if (HasRegisterAssigned()) {
204 : DCHECK(!IsSpilled());
205 14305181 : switch (Kind()) {
206 : case GENERAL_REGISTERS:
207 9957810 : op = LRegister::Create(assigned_register(), zone);
208 9957815 : break;
209 : case DOUBLE_REGISTERS:
210 4347371 : op = LDoubleRegister::Create(assigned_register(), zone);
211 4347375 : break;
212 : default:
213 0 : UNREACHABLE();
214 : }
215 2334633 : } else if (IsSpilled()) {
216 : DCHECK(!HasRegisterAssigned());
217 2334633 : op = TopLevel()->GetSpillOperand();
218 : DCHECK(!op->IsUnallocated());
219 : } else {
220 : LUnallocated* unalloc = new(zone) LUnallocated(LUnallocated::NONE);
221 0 : unalloc->set_virtual_register(id_);
222 : op = unalloc;
223 : }
224 16639823 : return op;
225 : }
226 :
227 :
228 0 : UseInterval* LiveRange::FirstSearchIntervalForPosition(
229 : LifetimePosition position) const {
230 230935985 : if (current_interval_ == NULL) return first_interval_;
231 218096437 : if (current_interval_->start().Value() > position.Value()) {
232 153400 : current_interval_ = NULL;
233 0 : return first_interval_;
234 : }
235 : return current_interval_;
236 : }
237 :
238 :
239 0 : void LiveRange::AdvanceLastProcessedMarker(
240 : UseInterval* to_start_of, LifetimePosition but_not_past) const {
241 399900526 : if (to_start_of == NULL) return;
242 399902085 : if (to_start_of->start().Value() > but_not_past.Value()) return;
243 : LifetimePosition start =
244 158885136 : current_interval_ == NULL ? LifetimePosition::Invalid()
245 158885136 : : current_interval_->start();
246 158885136 : if (to_start_of->start().Value() > start.Value()) {
247 30616617 : current_interval_ = to_start_of;
248 : }
249 : }
250 :
251 :
252 1679262 : void LiveRange::SplitAt(LifetimePosition position,
253 : LiveRange* result,
254 : Zone* zone) {
255 : DCHECK(Start().Value() < position.Value());
256 : DCHECK(result->IsEmpty());
257 : // Find the last interval that ends before the position. If the
258 : // position is contained in one of the intervals in the chain, we
259 : // split that interval and use the first part.
260 299997 : UseInterval* current = FirstSearchIntervalForPosition(position);
261 :
262 : // If the split position coincides with the beginning of a use interval
263 : // we need to split use positons in a special way.
264 : bool split_at_start = false;
265 :
266 1679262 : if (current->start().Value() == position.Value()) {
267 : // When splitting at start we need to locate the previous use interval.
268 0 : current = first_interval_;
269 : }
270 :
271 1979144 : while (current != NULL) {
272 1979130 : if (current->Contains(position)) {
273 1679133 : current->SplitAt(position, zone);
274 1679129 : break;
275 : }
276 : UseInterval* next = current->next();
277 299997 : if (next->start().Value() >= position.Value()) {
278 115 : split_at_start = (next->start().Value() == position.Value());
279 115 : break;
280 : }
281 : current = next;
282 : }
283 :
284 : // Partition original use intervals to the two live ranges.
285 1679258 : UseInterval* before = current;
286 : UseInterval* after = before->next();
287 1679258 : result->last_interval_ = (last_interval_ == before)
288 : ? after // Only interval in the range after split.
289 1679258 : : last_interval_; // Last interval of the original range.
290 1679258 : result->first_interval_ = after;
291 1679258 : last_interval_ = before;
292 :
293 : // Find the last use position before the split and the first use
294 : // position after it.
295 9738080 : UsePosition* use_after = first_pos_;
296 : UsePosition* use_before = NULL;
297 1679258 : if (split_at_start) {
298 : // The split position coincides with the beginning of a use interval (the
299 : // end of a lifetime hole). Use at this position should be attributed to
300 : // the split child because split child owns use interval covering it.
301 16 : while (use_after != NULL && use_after->pos().Value() < position.Value()) {
302 : use_before = use_after;
303 : use_after = use_after->next();
304 : }
305 : } else {
306 9738064 : while (use_after != NULL && use_after->pos().Value() <= position.Value()) {
307 : use_before = use_after;
308 : use_after = use_after->next();
309 : }
310 : }
311 :
312 : // Partition original use positions to the two live ranges.
313 1679258 : if (use_before != NULL) {
314 1602755 : use_before->next_ = NULL;
315 : } else {
316 76503 : first_pos_ = NULL;
317 : }
318 1679258 : result->first_pos_ = use_after;
319 :
320 : // Discard cached iteration state. It might be pointing
321 : // to the use that no longer belongs to this live range.
322 1679258 : last_processed_use_ = NULL;
323 1679258 : current_interval_ = NULL;
324 :
325 : // Link the new live range in the chain before any of the other
326 : // ranges linked from the range before the split.
327 1679258 : result->parent_ = (parent_ == NULL) ? this : parent_;
328 1679258 : result->kind_ = result->parent_->kind_;
329 1679258 : result->next_ = next_;
330 1679258 : next_ = result;
331 :
332 : #ifdef DEBUG
333 : Verify();
334 : result->Verify();
335 : #endif
336 1679258 : }
337 :
338 :
339 : // This implements an ordering on live ranges so that they are ordered by their
340 : // start positions. This is needed for the correctness of the register
341 : // allocation algorithm. If two live ranges start at the same offset then there
342 : // is a tie breaker based on where the value is first used. This part of the
343 : // ordering is merely a heuristic.
344 2860484 : bool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const {
345 : LifetimePosition start = Start();
346 : LifetimePosition other_start = other->Start();
347 94697848 : if (start.Value() == other_start.Value()) {
348 : UsePosition* pos = first_pos();
349 1433335 : if (pos == NULL) return false;
350 : UsePosition* other_pos = other->first_pos();
351 1427149 : if (other_pos == NULL) return true;
352 1422892 : return pos->pos().Value() < other_pos->pos().Value();
353 : }
354 93264513 : return start.Value() < other_start.Value();
355 : }
356 :
357 :
358 0 : void LiveRange::ShortenTo(LifetimePosition start) {
359 15454792 : LAllocator::TraceAlloc("Shorten live range %d to [%d\n", id_, start.Value());
360 : DCHECK(first_interval_ != NULL);
361 : DCHECK(first_interval_->start().Value() <= start.Value());
362 : DCHECK(start.Value() < first_interval_->end().Value());
363 15454785 : first_interval_->set_start(start);
364 0 : }
365 :
366 :
367 409965 : void LiveRange::EnsureInterval(LifetimePosition start,
368 : LifetimePosition end,
369 : Zone* zone) {
370 : LAllocator::TraceAlloc("Ensure live range %d in interval [%d %d[\n",
371 : id_,
372 : start.Value(),
373 409965 : end.Value());
374 : LifetimePosition new_end = end;
375 1564502 : while (first_interval_ != NULL &&
376 : first_interval_->start().Value() <= end.Value()) {
377 744572 : if (first_interval_->end().Value() > end.Value()) {
378 : new_end = first_interval_->end();
379 : }
380 744572 : first_interval_ = first_interval_->next();
381 : }
382 :
383 : UseInterval* new_interval = new(zone) UseInterval(start, new_end);
384 409965 : new_interval->next_ = first_interval_;
385 409965 : first_interval_ = new_interval;
386 409965 : if (new_interval->next() == NULL) {
387 213576 : last_interval_ = new_interval;
388 : }
389 409965 : }
390 :
391 :
392 109000501 : void LiveRange::AddUseInterval(LifetimePosition start,
393 : LifetimePosition end,
394 : Zone* zone) {
395 : LAllocator::TraceAlloc("Add to live range %d interval [%d %d[\n",
396 : id_,
397 : start.Value(),
398 109000501 : end.Value());
399 109009414 : if (first_interval_ == NULL) {
400 : UseInterval* interval = new(zone) UseInterval(start, end);
401 13358682 : first_interval_ = interval;
402 13358682 : last_interval_ = interval;
403 : } else {
404 95650739 : if (end.Value() == first_interval_->start().Value()) {
405 : first_interval_->set_start(start);
406 70442382 : } else if (end.Value() < first_interval_->start().Value()) {
407 : UseInterval* interval = new(zone) UseInterval(start, end);
408 42505362 : interval->set_next(first_interval_);
409 42505362 : first_interval_ = interval;
410 : } else {
411 : // Order of instruction's processing (see ProcessInstructions) guarantees
412 : // that each new use interval either precedes or intersects with
413 : // last added interval.
414 : DCHECK(start.Value() < first_interval_->end().Value());
415 27936944 : first_interval_->start_ = Min(start, first_interval_->start_);
416 27936944 : first_interval_->end_ = Max(end, first_interval_->end_);
417 : }
418 : }
419 109009345 : }
420 :
421 :
422 39644264 : void LiveRange::AddUsePosition(LifetimePosition pos,
423 : LOperand* operand,
424 : LOperand* hint,
425 : Zone* zone) {
426 : LAllocator::TraceAlloc("Add to live range %d use position %d\n",
427 : id_,
428 39644264 : pos.Value());
429 79290100 : UsePosition* use_pos = new(zone) UsePosition(pos, operand, hint);
430 : UsePosition* prev_hint = NULL;
431 : UsePosition* prev = NULL;
432 39977413 : UsePosition* current = first_pos_;
433 79623580 : while (current != NULL && current->pos().Value() < pos.Value()) {
434 331246 : prev_hint = current->HasHint() ? current : prev_hint;
435 : prev = current;
436 : current = current->next();
437 : }
438 :
439 39646167 : if (prev == NULL) {
440 : use_pos->set_next(first_pos_);
441 39314916 : first_pos_ = use_pos;
442 : } else {
443 331251 : use_pos->next_ = prev->next_;
444 331251 : prev->next_ = use_pos;
445 : }
446 :
447 79292266 : if (prev_hint == NULL && use_pos->HasHint()) {
448 7829803 : current_hint_operand_ = hint;
449 : }
450 39646167 : }
451 :
452 :
453 30074842 : void LiveRange::ConvertOperands(Zone* zone) {
454 15037439 : LOperand* op = CreateAssignedOperand(zone);
455 79360714 : UsePosition* use_pos = first_pos();
456 69755163 : while (use_pos != NULL) {
457 : DCHECK(Start().Value() <= use_pos->pos().Value() &&
458 : use_pos->pos().Value() <= End().Value());
459 :
460 39680357 : if (use_pos->HasOperand()) {
461 : DCHECK(op->IsRegister() || op->IsDoubleRegister() ||
462 : !use_pos->RequiresRegister());
463 : use_pos->operand()->ConvertTo(op->kind(), op->index());
464 : }
465 : use_pos = use_pos->next();
466 : }
467 15037403 : }
468 :
469 :
470 272435806 : bool LiveRange::CanCover(LifetimePosition position) const {
471 277478138 : if (IsEmpty()) return false;
472 549914058 : return Start().Value() <= position.Value() &&
473 : position.Value() < End().Value();
474 : }
475 :
476 :
477 163536316 : bool LiveRange::Covers(LifetimePosition position) {
478 163536316 : if (!CanCover(position)) return false;
479 : UseInterval* start_search = FirstSearchIntervalForPosition(position);
480 262640510 : for (UseInterval* interval = start_search;
481 : interval != NULL;
482 : interval = interval->next()) {
483 : DCHECK(interval->next() == NULL ||
484 : interval->next()->start().Value() >= interval->start().Value());
485 : AdvanceLastProcessedMarker(interval, position);
486 262633613 : if (interval->Contains(position)) return true;
487 230208418 : if (interval->start().Value() > position.Value()) return false;
488 : }
489 : return false;
490 : }
491 :
492 :
493 817241387 : LifetimePosition LiveRange::FirstIntersection(LiveRange* other) {
494 41241089 : UseInterval* b = other->first_interval();
495 93074737 : if (b == NULL) return LifetimePosition::Invalid();
496 : LifetimePosition advance_last_processed_up_to = b->start();
497 199675595 : UseInterval* a = FirstSearchIntervalForPosition(b->start());
498 364657476 : while (a != NULL && b != NULL) {
499 262304895 : if (a->start().Value() > other->End().Value()) break;
500 262186671 : if (b->start().Value() > End().Value()) break;
501 261473663 : LifetimePosition cur_intersection = a->Intersect(b);
502 261479014 : if (cur_intersection.IsValid()) {
503 20562330 : return cur_intersection;
504 : }
505 240916684 : if (a->start().Value() < b->start().Value()) {
506 : a = a->next();
507 399350679 : if (a == NULL || a->start().Value() > other->End().Value()) break;
508 : AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
509 : } else {
510 : b = b->next();
511 : }
512 : }
513 : return LifetimePosition::Invalid();
514 : }
515 :
516 283725 : LAllocator::LAllocator(int num_values, HGraph* graph)
517 : : zone_(graph->isolate()->allocator(), ZONE_NAME),
518 : chunk_(NULL),
519 : live_in_sets_(graph->blocks()->length(), zone()),
520 : live_ranges_(num_values * 2, zone()),
521 : fixed_live_ranges_(NULL),
522 : fixed_double_live_ranges_(NULL),
523 : unhandled_live_ranges_(num_values * 2, zone()),
524 : active_live_ranges_(8, zone()),
525 : inactive_live_ranges_(8, zone()),
526 : reusable_slots_(8, zone()),
527 : next_virtual_register_(num_values),
528 : first_artificial_register_(num_values),
529 : mode_(UNALLOCATED_REGISTERS),
530 : num_registers_(-1),
531 : graph_(graph),
532 : has_osr_entry_(false),
533 851184 : allocation_ok_(true) {}
534 :
535 283726 : void LAllocator::InitializeLivenessAnalysis() {
536 : // Initialize the live_in sets for each block to NULL.
537 283726 : int block_count = graph_->blocks()->length();
538 283726 : live_in_sets_.Initialize(block_count, zone());
539 283729 : live_in_sets_.AddBlock(NULL, block_count, zone());
540 283729 : }
541 :
542 :
543 9023269 : BitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) {
544 : // Compute live out for the given block, except not including backward
545 : // successor edges.
546 14507608 : BitVector* live_out = new(zone()) BitVector(next_virtual_register_, zone());
547 :
548 : // Process all successor blocks.
549 9622212 : for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
550 : // Add values live on entry to the successor. Note the successor's
551 : // live_in will not be computed yet for backwards edges.
552 5110562 : HBasicBlock* successor = it.Current();
553 10221124 : BitVector* live_in = live_in_sets_[successor->block_id()];
554 5110562 : if (live_in != NULL) live_out->Union(*live_in);
555 :
556 : // All phi input operands corresponding to this successor edge are live
557 : // out from this block.
558 5110562 : int index = successor->PredecessorIndexOf(block);
559 : const ZoneList<HPhi*>* phis = successor->phis();
560 11453290 : for (int i = 0; i < phis->length(); ++i) {
561 6342720 : HPhi* phi = phis->at(i);
562 616074 : if (!phi->OperandAt(index)->IsConstant()) {
563 433733 : live_out->Add(phi->OperandAt(index)->id());
564 : }
565 : }
566 : }
567 :
568 4511643 : return live_out;
569 : }
570 :
571 :
572 9023280 : void LAllocator::AddInitialIntervals(HBasicBlock* block,
573 : BitVector* live_out) {
574 : // Add an interval that includes the entire block to the live range for
575 : // each live_out value.
576 : LifetimePosition start = LifetimePosition::FromInstructionIndex(
577 4511640 : block->first_instruction_index());
578 : LifetimePosition end = LifetimePosition::FromInstructionIndex(
579 4511640 : block->last_instruction_index()).NextInstruction();
580 : BitVector::Iterator iterator(live_out);
581 61779646 : while (!iterator.Done()) {
582 26378153 : int operand_index = iterator.Current();
583 26378153 : LiveRange* range = LiveRangeFor(operand_index);
584 26378146 : range->AddUseInterval(start, end, zone());
585 26378094 : iterator.Advance();
586 : }
587 4511670 : }
588 :
589 :
590 0 : int LAllocator::FixedDoubleLiveRangeID(int index) {
591 3922441 : return -index - 1 - Register::kNumRegisters;
592 : }
593 :
594 :
595 7895814 : LOperand* LAllocator::AllocateFixed(LUnallocated* operand,
596 : int pos,
597 6701451 : bool is_tagged) {
598 7895814 : TraceAlloc("Allocating fixed reg for op %d\n", operand->virtual_register());
599 : DCHECK(operand->HasFixedPolicy());
600 7895837 : if (operand->HasFixedSlotPolicy()) {
601 : operand->ConvertTo(LOperand::STACK_SLOT, operand->fixed_slot_index());
602 7458913 : } else if (operand->HasFixedRegisterPolicy()) {
603 : int reg_index = operand->fixed_register_index();
604 : operand->ConvertTo(LOperand::REGISTER, reg_index);
605 65826 : } else if (operand->HasFixedDoubleRegisterPolicy()) {
606 : int reg_index = operand->fixed_register_index();
607 : operand->ConvertTo(LOperand::DOUBLE_REGISTER, reg_index);
608 : } else {
609 0 : UNREACHABLE();
610 : }
611 7895837 : if (is_tagged) {
612 6701450 : TraceAlloc("Fixed reg is tagged at %d\n", pos);
613 : LInstruction* instr = InstructionAt(pos);
614 6701451 : if (instr->HasPointerMap()) {
615 8869674 : instr->pointer_map()->RecordPointer(operand, chunk()->zone());
616 : }
617 : }
618 7895838 : return operand;
619 : }
620 :
621 :
622 36714261 : LiveRange* LAllocator::FixedLiveRangeFor(int index) {
623 : DCHECK(index < Register::kNumRegisters);
624 70204638 : LiveRange* result = fixed_live_ranges_[index];
625 33490406 : if (result == NULL) {
626 9671585 : result = new(zone()) LiveRange(FixedLiveRangeID(index), chunk()->zone());
627 : DCHECK(result->IsFixed());
628 3223797 : result->kind_ = GENERAL_REGISTERS;
629 3223797 : SetLiveRangeAssignedRegister(result, index);
630 3223826 : fixed_live_ranges_[index] = result;
631 : }
632 33490377 : return result;
633 : }
634 :
635 :
636 29327462 : LiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) {
637 : DCHECK(index < DoubleRegister::kMaxNumRegisters);
638 54732461 : LiveRange* result = fixed_double_live_ranges_[index];
639 25405021 : if (result == NULL) {
640 : result = new(zone()) LiveRange(FixedDoubleLiveRangeID(index),
641 11767325 : chunk()->zone());
642 : DCHECK(result->IsFixed());
643 3922393 : result->kind_ = DOUBLE_REGISTERS;
644 3922393 : SetLiveRangeAssignedRegister(result, index);
645 3922419 : fixed_double_live_ranges_[index] = result;
646 : }
647 25404999 : return result;
648 : }
649 :
650 :
651 100598186 : LiveRange* LAllocator::LiveRangeFor(int index) {
652 193069254 : if (index >= live_ranges_.length()) {
653 3979548 : live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1, zone());
654 : }
655 92471196 : LiveRange* result = live_ranges_[index];
656 92471196 : if (result == NULL) {
657 24395139 : result = new(zone()) LiveRange(index, chunk()->zone());
658 8131583 : live_ranges_[index] = result;
659 : }
660 92471068 : return result;
661 : }
662 :
663 :
664 1025470 : LGap* LAllocator::GetLastGap(HBasicBlock* block) {
665 : int last_instruction = block->last_instruction_index();
666 512735 : int index = chunk_->NearestGapPos(last_instruction);
667 512735 : return GapAt(index);
668 : }
669 :
670 :
671 8928157 : HPhi* LAllocator::LookupPhi(LOperand* operand) const {
672 8928157 : if (!operand->IsUnallocated()) return NULL;
673 : int index = LUnallocated::cast(operand)->virtual_register();
674 3006381 : HValue* instr = graph_->LookupValue(index);
675 5879317 : if (instr != NULL && instr->IsPhi()) {
676 616076 : return HPhi::cast(instr);
677 : }
678 : return NULL;
679 : }
680 :
681 :
682 54909619 : LiveRange* LAllocator::LiveRangeFor(LOperand* operand) {
683 54909619 : if (operand->IsUnallocated()) {
684 39187615 : return LiveRangeFor(LUnallocated::cast(operand)->virtual_register());
685 15722004 : } else if (operand->IsRegister()) {
686 14546655 : return FixedLiveRangeFor(operand->index());
687 1175349 : } else if (operand->IsDoubleRegister()) {
688 131626 : return FixedDoubleLiveRangeFor(operand->index());
689 : } else {
690 : return NULL;
691 : }
692 : }
693 :
694 :
695 16348242 : void LAllocator::Define(LifetimePosition position,
696 : LOperand* operand,
697 : LOperand* hint) {
698 16348242 : LiveRange* range = LiveRangeFor(operand);
699 32696735 : if (range == NULL) return;
700 :
701 15911451 : if (range->IsEmpty() || range->Start().Value() > position.Value()) {
702 : // Can happen if there is a definition without use.
703 913318 : range->AddUseInterval(position, position.NextInstruction(), zone());
704 456659 : range->AddUsePosition(position.NextInstruction(), NULL, NULL, zone());
705 : } else {
706 : range->ShortenTo(position);
707 : }
708 :
709 15911578 : if (operand->IsUnallocated()) {
710 : LUnallocated* unalloc_operand = LUnallocated::cast(operand);
711 8452629 : range->AddUsePosition(position, unalloc_operand, hint, zone());
712 : }
713 : }
714 :
715 :
716 38561620 : void LAllocator::Use(LifetimePosition block_start,
717 : LifetimePosition position,
718 : LOperand* operand,
719 : LOperand* hint) {
720 38561620 : LiveRange* range = LiveRangeFor(operand);
721 77124589 : if (range == NULL) return;
722 37955403 : if (operand->IsUnallocated()) {
723 : LUnallocated* unalloc_operand = LUnallocated::cast(operand);
724 30736567 : range->AddUsePosition(position, unalloc_operand, hint, zone());
725 : }
726 37956449 : range->AddUseInterval(block_start, position, zone());
727 : }
728 :
729 :
730 6405393 : void LAllocator::AddConstraintsGapMove(int index,
731 : LOperand* from,
732 19216181 : LOperand* to) {
733 : LGap* gap = GapAt(index);
734 : LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START,
735 12810794 : chunk()->zone());
736 6405391 : if (from->IsUnallocated()) {
737 : const ZoneList<LMoveOperands>* move_operands = move->move_operands();
738 23459497 : for (int i = 0; i < move_operands->length(); ++i) {
739 23459872 : LMoveOperands cur = move_operands->at(i);
740 : LOperand* cur_to = cur.destination();
741 8527428 : if (cur_to->IsUnallocated()) {
742 27327 : if (LUnallocated::cast(cur_to)->virtual_register() ==
743 : LUnallocated::cast(from)->virtual_register()) {
744 375 : move->AddMove(cur.source(), to, chunk()->zone());
745 6405390 : return;
746 : }
747 : }
748 : }
749 : }
750 6405016 : move->AddMove(from, to, chunk()->zone());
751 : }
752 :
753 :
754 124677897 : void LAllocator::MeetRegisterConstraints(HBasicBlock* block) {
755 : int start = block->first_instruction_index();
756 : int end = block->last_instruction_index();
757 4511648 : if (start == -1) return;
758 44615744 : for (int i = start; i <= end; ++i) {
759 44615543 : if (IsGapAt(i)) {
760 : LInstruction* instr = NULL;
761 : LInstruction* prev_instr = NULL;
762 26819269 : if (i < end) instr = InstructionAt(i + 1);
763 26819269 : if (i > start) prev_instr = InstructionAt(i - 1);
764 26819269 : MeetConstraintsBetween(prev_instr, instr, i);
765 26819683 : if (!AllocationOk()) return;
766 : }
767 : }
768 : }
769 :
770 :
771 26819558 : void LAllocator::MeetConstraintsBetween(LInstruction* first,
772 : LInstruction* second,
773 30558463 : int gap_index) {
774 : // Handle fixed temporaries.
775 26819558 : if (first != NULL) {
776 44798481 : for (TempIterator it(first); !it.Done(); it.Advance()) {
777 181289 : LUnallocated* temp = LUnallocated::cast(it.Current());
778 181289 : if (temp->HasFixedPolicy()) {
779 67298 : AllocateFixed(temp, gap_index - 1, false);
780 : }
781 : }
782 : }
783 :
784 : // Handle fixed output operand.
785 26819686 : if (first != NULL && first->Output() != NULL) {
786 7776595 : LUnallocated* first_output = LUnallocated::cast(first->Output());
787 15116442 : LiveRange* range = LiveRangeFor(first_output->virtual_register());
788 : bool assigned = false;
789 7776662 : if (first_output->HasFixedPolicy()) {
790 : LUnallocated* output_copy = first_output->CopyUnconstrained(
791 3813466 : chunk()->zone());
792 1906737 : bool is_tagged = HasTaggedValue(first_output->virtual_register());
793 1906739 : AllocateFixed(first_output, gap_index, is_tagged);
794 :
795 : // This value is produced on the stack, we never need to spill it.
796 1906743 : if (first_output->IsStackSlot()) {
797 : range->SetSpillOperand(first_output);
798 436929 : range->SetSpillStartIndex(gap_index - 1);
799 : assigned = true;
800 : }
801 1906743 : chunk_->AddGapMove(gap_index, first_output, output_copy);
802 : }
803 :
804 7777555 : if (!assigned) {
805 : range->SetSpillStartIndex(gap_index);
806 :
807 : // This move to spill operand is not a real use. Liveness analysis
808 : // and splitting of live ranges do not account for it.
809 : // Thus it should be inserted to a lifetime position corresponding to
810 : // the instruction end.
811 : LGap* gap = GapAt(gap_index);
812 : LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE,
813 14679544 : chunk()->zone());
814 : move->AddMove(first_output, range->GetSpillOperand(),
815 7339792 : chunk()->zone());
816 : }
817 : }
818 :
819 : // Handle fixed input operands of second instruction.
820 26820622 : if (second != NULL) {
821 111906134 : for (UseIterator it(second); !it.Done(); it.Advance()) {
822 29529819 : LUnallocated* cur_input = LUnallocated::cast(it.Current());
823 29530205 : if (cur_input->HasFixedPolicy()) {
824 : LUnallocated* input_copy = cur_input->CopyUnconstrained(
825 11843622 : chunk()->zone());
826 5921807 : bool is_tagged = HasTaggedValue(cur_input->virtual_register());
827 5921812 : AllocateFixed(cur_input, gap_index + 1, is_tagged);
828 5921814 : AddConstraintsGapMove(gap_index, input_copy, cur_input);
829 23608394 : } else if (cur_input->HasWritableRegisterPolicy()) {
830 : // The live range of writable input registers always goes until the end
831 : // of the instruction.
832 : DCHECK(!cur_input->IsUsedAtStart());
833 :
834 : LUnallocated* input_copy = cur_input->CopyUnconstrained(
835 266888 : chunk()->zone());
836 : int vreg = GetVirtualRegister();
837 26953705 : if (!AllocationOk()) return;
838 133444 : cur_input->set_virtual_register(vreg);
839 :
840 133444 : if (RequiredRegisterKind(input_copy->virtual_register()) ==
841 : DOUBLE_REGISTERS) {
842 : double_artificial_registers_.Add(
843 : cur_input->virtual_register() - first_artificial_register_,
844 570 : zone());
845 : }
846 :
847 133444 : AddConstraintsGapMove(gap_index, input_copy, cur_input);
848 : }
849 : }
850 : }
851 :
852 : // Handle "output same as input" for second instruction.
853 26820425 : if (second != NULL && second->Output() != NULL) {
854 7776643 : LUnallocated* second_output = LUnallocated::cast(second->Output());
855 7776607 : if (second_output->HasSameAsInputPolicy()) {
856 : LUnallocated* cur_input = LUnallocated::cast(second->FirstInput());
857 : int output_vreg = second_output->virtual_register();
858 : int input_vreg = cur_input->virtual_register();
859 :
860 : LUnallocated* input_copy = cur_input->CopyUnconstrained(
861 700280 : chunk()->zone());
862 : cur_input->set_virtual_register(second_output->virtual_register());
863 350140 : AddConstraintsGapMove(gap_index, input_copy, cur_input);
864 :
865 350139 : if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) {
866 93568 : int index = gap_index + 1;
867 : LInstruction* instr = InstructionAt(index);
868 93568 : if (instr->HasPointerMap()) {
869 0 : instr->pointer_map()->RecordPointer(input_copy, chunk()->zone());
870 : }
871 : } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) {
872 : // The input is assumed to immediately have a tagged representation,
873 : // before the pointer map can be used. I.e. the pointer map at the
874 : // instruction will include the output operand (whose value at the
875 : // beginning of the instruction is equal to the input operand). If
876 : // this is not desired, then the pointer map at this instruction needs
877 : // to be adjusted manually.
878 : }
879 : }
880 : }
881 : }
882 :
883 :
884 179373607 : void LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) {
885 : int block_start = block->first_instruction_index();
886 : int index = block->last_instruction_index();
887 :
888 : LifetimePosition block_start_position =
889 4511614 : LifetimePosition::FromInstructionIndex(block_start);
890 :
891 53637099 : while (index >= block_start) {
892 : LifetimePosition curr_position =
893 : LifetimePosition::FromInstructionIndex(index);
894 :
895 44614094 : if (IsGapAt(index)) {
896 : // We have a gap at this position.
897 : LGap* gap = GapAt(index);
898 : LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START,
899 53638860 : chunk()->zone());
900 : const ZoneList<LMoveOperands>* move_operands = move->move_operands();
901 72097246 : for (int i = 0; i < move_operands->length(); ++i) {
902 54206078 : LMoveOperands* cur = &move_operands->at(i);
903 9229295 : if (cur->IsIgnored()) continue;
904 : LOperand* from = cur->source();
905 : LOperand* to = cur->destination();
906 8928160 : HPhi* phi = LookupPhi(to);
907 : LOperand* hint = to;
908 8928235 : if (phi != NULL) {
909 : // This is a phi resolving move.
910 1232152 : if (!phi->block()->IsLoopHeader()) {
911 413165 : hint = LiveRangeFor(phi->id())->current_hint_operand();
912 : }
913 : } else {
914 8312159 : if (to->IsUnallocated()) {
915 2390321 : if (live->Contains(LUnallocated::cast(to)->virtual_register())) {
916 2150453 : Define(curr_position, to, from);
917 : live->Remove(LUnallocated::cast(to)->virtual_register());
918 : } else {
919 : cur->Eliminate();
920 : continue;
921 : }
922 : } else {
923 5921838 : Define(curr_position, to, from);
924 : }
925 : }
926 8688385 : Use(block_start_position, curr_position, from, hint);
927 8688345 : if (from->IsUnallocated()) {
928 : live->Add(LUnallocated::cast(from)->virtual_register());
929 : }
930 : }
931 : } else {
932 : DCHECK(!IsGapAt(index));
933 : LInstruction* instr = InstructionAt(index);
934 :
935 17794646 : if (instr != NULL) {
936 17797365 : LOperand* output = instr->Output();
937 17797124 : if (output != NULL) {
938 7776651 : if (output->IsUnallocated()) {
939 : live->Remove(LUnallocated::cast(output)->virtual_register());
940 : }
941 7776651 : Define(curr_position, output, NULL);
942 : }
943 :
944 17797385 : if (instr->ClobbersRegisters()) {
945 27121476 : for (int i = 0; i < Register::kNumRegisters; ++i) {
946 54242994 : if (GetRegConfig()->IsAllocatableGeneralCode(i)) {
947 53909281 : if (output == NULL || !output->IsRegister() ||
948 : output->index() != i) {
949 18944228 : LiveRange* range = FixedLiveRangeFor(i);
950 : range->AddUseInterval(curr_position,
951 37888420 : curr_position.InstructionEnd(), zone());
952 : }
953 : }
954 : }
955 : }
956 :
957 35594760 : if (instr->ClobbersDoubleRegisters(isolate())) {
958 26962059 : for (int i = 0; i < DoubleRegister::kMaxNumRegisters; ++i) {
959 53924060 : if (GetRegConfig()->IsAllocatableDoubleCode(i)) {
960 46187507 : if (output == NULL || !output->IsDoubleRegister() ||
961 : output->index() != i) {
962 25273399 : LiveRange* range = FixedDoubleLiveRangeFor(i);
963 : range->AddUseInterval(curr_position,
964 50546686 : curr_position.InstructionEnd(), zone());
965 : }
966 : }
967 : }
968 : }
969 :
970 94947318 : for (UseIterator it(instr); !it.Done(); it.Advance()) {
971 29675944 : LOperand* input = it.Current();
972 :
973 : LifetimePosition use_pos;
974 53430969 : if (input->IsUnallocated() &&
975 : LUnallocated::cast(input)->IsUsedAtStart()) {
976 2083704 : use_pos = curr_position;
977 : } else {
978 27592706 : use_pos = curr_position.InstructionEnd();
979 : }
980 :
981 29676410 : Use(block_start_position, use_pos, input, NULL);
982 29676756 : if (input->IsUnallocated()) {
983 : live->Add(LUnallocated::cast(input)->virtual_register());
984 : }
985 : }
986 :
987 35792938 : for (TempIterator it(instr); !it.Done(); it.Advance()) {
988 198385 : LOperand* temp = it.Current();
989 198385 : if (instr->ClobbersTemps()) {
990 0 : if (temp->IsRegister()) continue;
991 0 : if (temp->IsUnallocated()) {
992 : LUnallocated* temp_unalloc = LUnallocated::cast(temp);
993 0 : if (temp_unalloc->HasFixedPolicy()) {
994 : continue;
995 : }
996 : }
997 : }
998 198385 : Use(block_start_position, curr_position.InstructionEnd(), temp, NULL);
999 198383 : Define(curr_position, temp, NULL);
1000 :
1001 198386 : if (temp->IsUnallocated()) {
1002 : LUnallocated* temp_unalloc = LUnallocated::cast(temp);
1003 131088 : if (temp_unalloc->HasDoubleRegisterPolicy()) {
1004 : double_artificial_registers_.Add(
1005 : temp_unalloc->virtual_register() - first_artificial_register_,
1006 0 : zone());
1007 : }
1008 : }
1009 : }
1010 : }
1011 : }
1012 :
1013 44613871 : index = index - 1;
1014 : }
1015 4511592 : }
1016 :
1017 :
1018 6176281 : void LAllocator::ResolvePhis(HBasicBlock* block) {
1019 : const ZoneList<HPhi*>* phis = block->phis();
1020 9625688 : for (int i = 0; i < phis->length(); ++i) {
1021 5113990 : HPhi* phi = phis->at(i);
1022 : LUnallocated* phi_operand =
1023 301146 : new (chunk()->zone()) LUnallocated(LUnallocated::NONE);
1024 1204584 : phi_operand->set_virtual_register(phi->id());
1025 1834450 : for (int j = 0; j < phi->OperandCount(); ++j) {
1026 446212 : HValue* op = phi->OperandAt(j);
1027 : LOperand* operand = NULL;
1028 616079 : if (op->IsConstant() && op->EmitAtUses()) {
1029 : HConstant* constant = HConstant::cast(op);
1030 169867 : operand = chunk_->DefineConstantOperand(constant);
1031 : } else {
1032 : DCHECK(!op->EmitAtUses());
1033 : LUnallocated* unalloc =
1034 446212 : new(chunk()->zone()) LUnallocated(LUnallocated::ANY);
1035 446212 : unalloc->set_virtual_register(op->id());
1036 : operand = unalloc;
1037 : }
1038 1232158 : HBasicBlock* cur_block = block->predecessors()->at(j);
1039 : // The gap move must be added without any special processing as in
1040 : // the AddConstraintsGapMove.
1041 : chunk_->AddGapMove(cur_block->last_instruction_index() - 1,
1042 : operand,
1043 616079 : phi_operand);
1044 :
1045 : // We are going to insert a move before the branch instruction.
1046 : // Some branch instructions (e.g. loops' back edges)
1047 : // can potentially cause a GC so they have a pointer map.
1048 : // By inserting a move we essentially create a copy of a
1049 : // value which is invisible to PopulatePointerMaps(), because we store
1050 : // it into a location different from the operand of a live range
1051 : // covering a branch instruction.
1052 : // Thus we need to manually record a pointer.
1053 : LInstruction* branch =
1054 : InstructionAt(cur_block->last_instruction_index());
1055 616079 : if (branch->HasPointerMap()) {
1056 0 : if (phi->representation().IsTagged() && !phi->type().IsSmi()) {
1057 0 : branch->pointer_map()->RecordPointer(phi_operand, chunk()->zone());
1058 0 : } else if (!phi->representation().IsDouble()) {
1059 0 : branch->pointer_map()->RecordUntagged(phi_operand, chunk()->zone());
1060 : }
1061 : }
1062 : }
1063 :
1064 602292 : LiveRange* live_range = LiveRangeFor(phi->id());
1065 301146 : LLabel* label = chunk_->GetLabel(phi->block()->block_id());
1066 : label->GetOrCreateParallelMove(LGap::START, chunk()->zone())->
1067 602292 : AddMove(phi_operand, live_range->GetSpillOperand(), chunk()->zone());
1068 301146 : live_range->SetSpillStartIndex(phi->block()->first_instruction_index());
1069 : }
1070 4511698 : }
1071 :
1072 :
1073 1702363 : bool LAllocator::Allocate(LChunk* chunk) {
1074 : DCHECK(chunk_ == NULL);
1075 283726 : chunk_ = static_cast<LPlatformChunk*>(chunk);
1076 : assigned_registers_ =
1077 283727 : new (chunk->zone()) BitVector(Register::kNumRegisters, chunk->zone());
1078 : assigned_double_registers_ = new (chunk->zone())
1079 283729 : BitVector(DoubleRegister::kMaxNumRegisters, chunk->zone());
1080 283729 : MeetRegisterConstraints();
1081 283728 : if (!AllocationOk()) return false;
1082 283728 : ResolvePhis();
1083 283730 : BuildLiveRanges();
1084 283730 : AllocateGeneralRegisters();
1085 283728 : if (!AllocationOk()) return false;
1086 283728 : AllocateDoubleRegisters();
1087 283728 : if (!AllocationOk()) return false;
1088 283728 : PopulatePointerMaps();
1089 283729 : ConnectRanges();
1090 283727 : ResolveControlFlow();
1091 283730 : return true;
1092 : }
1093 :
1094 :
1095 4795381 : void LAllocator::MeetRegisterConstraints() {
1096 283727 : LAllocatorPhase phase("L_Register constraints", this);
1097 283730 : const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1098 9590768 : for (int i = 0; i < blocks->length(); ++i) {
1099 9307039 : HBasicBlock* block = blocks->at(i);
1100 4511655 : MeetRegisterConstraints(block);
1101 4511654 : if (!AllocationOk()) return;
1102 283729 : }
1103 : }
1104 :
1105 :
1106 283726 : void LAllocator::ResolvePhis() {
1107 283726 : LAllocatorPhase phase("L_Resolve phis", this);
1108 :
1109 : // Process the blocks in reverse order.
1110 283731 : const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1111 4795437 : for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) {
1112 4511707 : HBasicBlock* block = blocks->at(block_id);
1113 4511707 : ResolvePhis(block);
1114 283730 : }
1115 283730 : }
1116 :
1117 :
1118 16345138 : void LAllocator::ResolveControlFlow(LiveRange* range,
1119 16391505 : HBasicBlock* block,
1120 17386738 : HBasicBlock* pred) {
1121 : LifetimePosition pred_end =
1122 : LifetimePosition::FromInstructionIndex(pred->last_instruction_index());
1123 : LifetimePosition cur_start =
1124 : LifetimePosition::FromInstructionIndex(block->first_instruction_index());
1125 : LiveRange* pred_cover = NULL;
1126 16345138 : LiveRange* cur_cover = NULL;
1127 56970911 : LiveRange* cur_range = range;
1128 89661187 : while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) {
1129 56970911 : if (cur_range->CanCover(cur_start)) {
1130 : DCHECK(cur_cover == NULL);
1131 : cur_cover = cur_range;
1132 : }
1133 56970911 : if (cur_range->CanCover(pred_end)) {
1134 : DCHECK(pred_cover == NULL);
1135 : pred_cover = cur_range;
1136 : }
1137 : cur_range = cur_range->next();
1138 : }
1139 :
1140 32690276 : if (cur_cover->IsSpilled()) return;
1141 : DCHECK(pred_cover != NULL && cur_cover != NULL);
1142 3043363 : if (pred_cover != cur_cover) {
1143 525684 : LOperand* pred_op = pred_cover->CreateAssignedOperand(chunk()->zone());
1144 525684 : LOperand* cur_op = cur_cover->CreateAssignedOperand(chunk()->zone());
1145 262842 : if (!pred_op->Equals(cur_op)) {
1146 : LGap* gap = NULL;
1147 257958 : if (block->predecessors()->length() == 1) {
1148 : gap = GapAt(block->first_instruction_index());
1149 : } else {
1150 : DCHECK(pred->end()->SecondSuccessor() == NULL);
1151 211591 : gap = GetLastGap(pred);
1152 :
1153 : // We are going to insert a move before the branch instruction.
1154 : // Some branch instructions (e.g. loops' back edges)
1155 : // can potentially cause a GC so they have a pointer map.
1156 : // By inserting a move we essentially create a copy of a
1157 : // value which is invisible to PopulatePointerMaps(), because we store
1158 : // it into a location different from the operand of a live range
1159 : // covering a branch instruction.
1160 : // Thus we need to manually record a pointer.
1161 : LInstruction* branch = InstructionAt(pred->last_instruction_index());
1162 211591 : if (branch->HasPointerMap()) {
1163 0 : if (HasTaggedValue(range->id())) {
1164 0 : branch->pointer_map()->RecordPointer(cur_op, chunk()->zone());
1165 0 : } else if (!cur_op->IsDoubleStackSlot() &&
1166 : !cur_op->IsDoubleRegister()) {
1167 0 : branch->pointer_map()->RemovePointer(cur_op);
1168 : }
1169 : }
1170 : }
1171 : gap->GetOrCreateParallelMove(
1172 : LGap::START, chunk()->zone())->AddMove(pred_op, cur_op,
1173 515916 : chunk()->zone());
1174 : }
1175 : }
1176 : }
1177 :
1178 :
1179 1797094 : LParallelMove* LAllocator::GetConnectingParallelMove(LifetimePosition pos) {
1180 : int index = pos.InstructionIndex();
1181 449338 : if (IsGapAt(index)) {
1182 : LGap* gap = GapAt(index);
1183 : return gap->GetOrCreateParallelMove(
1184 898160 : pos.IsInstructionStart() ? LGap::START : LGap::END, chunk()->zone());
1185 : }
1186 262 : int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1);
1187 : return GapAt(gap_pos)->GetOrCreateParallelMove(
1188 786 : (gap_pos < index) ? LGap::AFTER : LGap::BEFORE, chunk()->zone());
1189 : }
1190 :
1191 :
1192 2097674 : HBasicBlock* LAllocator::GetBlock(LifetimePosition pos) {
1193 2097673 : LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex()));
1194 1048838 : return gap->block();
1195 : }
1196 :
1197 :
1198 1631750 : void LAllocator::ConnectRanges() {
1199 283727 : LAllocatorPhase phase("L_Connect ranges", this);
1200 34799648 : for (int i = 0; i < live_ranges()->length(); ++i) {
1201 49579010 : LiveRange* first_range = live_ranges()->at(i);
1202 42647821 : if (first_range == NULL || first_range->parent() != NULL) continue;
1203 :
1204 3358493 : LiveRange* second_range = first_range->next();
1205 14584544 : while (second_range != NULL) {
1206 : LifetimePosition pos = second_range->Start();
1207 :
1208 1679253 : if (!second_range->IsSpilled()) {
1209 : // Add gap move if the two live ranges touch and there is no block
1210 : // boundary.
1211 478537 : if (first_range->End().Value() == pos.Value()) {
1212 : bool should_insert = true;
1213 478434 : if (IsBlockBoundary(pos)) {
1214 29080 : should_insert = CanEagerlyResolveControlFlow(GetBlock(pos));
1215 : }
1216 478421 : if (should_insert) {
1217 449341 : LParallelMove* move = GetConnectingParallelMove(pos);
1218 : LOperand* prev_operand = first_range->CreateAssignedOperand(
1219 898682 : chunk()->zone());
1220 : LOperand* cur_operand = second_range->CreateAssignedOperand(
1221 898682 : chunk()->zone());
1222 : move->AddMove(prev_operand, cur_operand,
1223 449341 : chunk()->zone());
1224 : }
1225 : }
1226 : }
1227 :
1228 : first_range = second_range;
1229 : second_range = second_range->next();
1230 : }
1231 283728 : }
1232 283728 : }
1233 :
1234 :
1235 3782323 : bool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const {
1236 4257034 : if (block->predecessors()->length() != 1) return false;
1237 7564646 : return block->predecessors()->first()->block_id() == block->block_id() - 1;
1238 : }
1239 :
1240 :
1241 283725 : void LAllocator::ResolveControlFlow() {
1242 283725 : LAllocatorPhase phase("L_Resolve control flow", this);
1243 283730 : const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1244 9023366 : for (int block_id = 1; block_id < blocks->length(); ++block_id) {
1245 10165729 : HBasicBlock* block = blocks->at(block_id);
1246 7029816 : if (CanEagerlyResolveControlFlow(block)) continue;
1247 2852184 : BitVector* live = live_in_sets_[block->block_id()];
1248 : BitVector::Iterator iterator(live);
1249 23186778 : while (!iterator.Done()) {
1250 10167298 : int operand_index = iterator.Current();
1251 26512376 : for (int i = 0; i < block->predecessors()->length(); ++i) {
1252 16345089 : HBasicBlock* cur = block->predecessors()->at(i);
1253 16345089 : LiveRange* cur_range = LiveRangeFor(operand_index);
1254 16345100 : ResolveControlFlow(cur_range, block, cur);
1255 : }
1256 10167287 : iterator.Advance();
1257 : }
1258 283729 : }
1259 283730 : }
1260 :
1261 :
1262 584870 : void LAllocator::BuildLiveRanges() {
1263 283726 : LAllocatorPhase phase("L_Build live ranges", this);
1264 283729 : InitializeLivenessAnalysis();
1265 : // Process the blocks in reverse order.
1266 283746 : const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1267 4795345 : for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) {
1268 4932592 : HBasicBlock* block = blocks->at(block_id);
1269 4812748 : BitVector* live = ComputeLiveOut(block);
1270 : // Initially consider all live_out values live for the entire block. We
1271 : // will shorten these intervals if necessary.
1272 4511647 : AddInitialIntervals(block, live);
1273 :
1274 : // Process the instructions in reverse order, generating and killing
1275 : // live values.
1276 4511668 : ProcessInstructions(block, live);
1277 : // All phi output operands are killed by this block.
1278 : const ZoneList<HPhi*>* phis = block->phis();
1279 9625486 : for (int i = 0; i < phis->length(); ++i) {
1280 : // The live range interval already ends at the first instruction of the
1281 : // block.
1282 5113887 : HPhi* phi = phis->at(i);
1283 1199547 : live->Remove(phi->id());
1284 :
1285 : LOperand* hint = NULL;
1286 : LOperand* phi_operand = NULL;
1287 301144 : LGap* gap = GetLastGap(phi->block()->predecessors()->at(0));
1288 : LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START,
1289 602288 : chunk()->zone());
1290 597259 : for (int j = 0; j < move->move_operands()->length(); ++j) {
1291 597259 : LOperand* to = move->move_operands()->at(j).destination();
1292 1194518 : if (to->IsUnallocated() &&
1293 : LUnallocated::cast(to)->virtual_register() == phi->id()) {
1294 301144 : hint = move->move_operands()->at(j).source();
1295 : phi_operand = to;
1296 301144 : break;
1297 : }
1298 : }
1299 : DCHECK(hint != NULL);
1300 :
1301 : LifetimePosition block_start = LifetimePosition::FromInstructionIndex(
1302 301144 : block->first_instruction_index());
1303 301144 : Define(block_start, phi_operand, hint);
1304 : }
1305 :
1306 : // Now live is live_in for this block except not including values live
1307 : // out on backward successor edges.
1308 9992885 : live_in_sets_[block_id] = live;
1309 :
1310 : // If this block is a loop header go back and patch up the necessary
1311 : // predecessor blocks.
1312 4511599 : if (block->IsLoopHeader()) {
1313 : // TODO(kmillikin): Need to be able to get the last block of the loop
1314 : // in the loop information. Add a live range stretching from the first
1315 : // loop instruction to the last for each value live on entry to the
1316 : // header.
1317 1149453 : HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge();
1318 : BitVector::Iterator iterator(live);
1319 : LifetimePosition start = LifetimePosition::FromInstructionIndex(
1320 59922 : block->first_instruction_index());
1321 : LifetimePosition end = LifetimePosition::FromInstructionIndex(
1322 59922 : back_edge->last_instruction_index()).NextInstruction();
1323 999696 : while (!iterator.Done()) {
1324 409965 : int operand_index = iterator.Current();
1325 409965 : LiveRange* range = LiveRangeFor(operand_index);
1326 409965 : range->EnsureInterval(start, end, zone());
1327 409965 : iterator.Advance();
1328 : }
1329 :
1330 2059218 : for (int i = block->block_id() + 1; i <= back_edge->block_id(); ++i) {
1331 969687 : live_in_sets_[i]->Union(*live);
1332 : }
1333 : }
1334 :
1335 : #ifdef DEBUG
1336 : if (block_id == 0) {
1337 : BitVector::Iterator iterator(live);
1338 : bool found = false;
1339 : while (!iterator.Done()) {
1340 : found = true;
1341 : int operand_index = iterator.Current();
1342 : {
1343 : AllowHandleDereference allow_deref;
1344 : PrintF("Function: %s\n", chunk_->info()->GetDebugName().get());
1345 : }
1346 : PrintF("Value %d used before first definition!\n", operand_index);
1347 : LiveRange* range = LiveRangeFor(operand_index);
1348 : PrintF("First use is at %d\n", range->first_pos()->pos().Value());
1349 : iterator.Advance();
1350 : }
1351 : DCHECK(!found);
1352 : }
1353 : #endif
1354 : }
1355 :
1356 64768571 : for (int i = 0; i < live_ranges_.length(); ++i) {
1357 97011008 : if (live_ranges_[i] != NULL) {
1358 6452539 : live_ranges_[i]->kind_ = RequiredRegisterKind(live_ranges_[i]->id());
1359 : }
1360 283730 : }
1361 283730 : }
1362 :
1363 :
1364 : bool LAllocator::SafePointsAreInOrder() const {
1365 : const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps();
1366 : int safe_point = 0;
1367 : for (int i = 0; i < pointer_maps->length(); ++i) {
1368 : LPointerMap* map = pointer_maps->at(i);
1369 : if (safe_point > map->lithium_position()) return false;
1370 : safe_point = map->lithium_position();
1371 : }
1372 : return true;
1373 : }
1374 :
1375 :
1376 9449844 : void LAllocator::PopulatePointerMaps() {
1377 283727 : LAllocatorPhase phase("L_Populate pointer maps", this);
1378 283758 : const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps();
1379 :
1380 : DCHECK(SafePointsAreInOrder());
1381 :
1382 : // Iterate over all safe point positions and record a pointer
1383 : // for all spilled live ranges at this point.
1384 : int first_safe_point_index = 0;
1385 : int last_range_start = 0;
1386 34799152 : for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) {
1387 75539153 : LiveRange* range = live_ranges()->at(range_idx);
1388 34515423 : if (range == NULL) continue;
1389 : // Iterate over the first parts of multi-part live ranges.
1390 8131845 : if (range->parent() != NULL) continue;
1391 : // Skip non-pointer values.
1392 6452709 : if (!HasTaggedValue(range->id())) continue;
1393 : // Skip empty live ranges.
1394 4360396 : if (range->IsEmpty()) continue;
1395 :
1396 : // Find the extent of the range and its children.
1397 : int start = range->Start().InstructionIndex();
1398 : int end = 0;
1399 9683118 : for (LiveRange* cur = range; cur != NULL; cur = cur->next()) {
1400 : LifetimePosition this_end = cur->End();
1401 5562338 : if (this_end.InstructionIndex() > end) end = this_end.InstructionIndex();
1402 : DCHECK(cur->Start().InstructionIndex() >= start);
1403 : }
1404 :
1405 : // Most of the ranges are in order, but not all. Keep an eye on when
1406 : // they step backwards and reset the first_safe_point_index so we don't
1407 : // miss any safe points.
1408 4120780 : if (start < last_range_start) {
1409 : first_safe_point_index = 0;
1410 : }
1411 : last_range_start = start;
1412 :
1413 : // Step across all the safe points that are before the start of this range,
1414 : // recording how far we step in order to save doing this for the next range.
1415 27447439 : while (first_safe_point_index < pointer_maps->length()) {
1416 66908141 : LPointerMap* map = pointer_maps->at(first_safe_point_index);
1417 : int safe_point = map->lithium_position();
1418 22868825 : if (safe_point >= start) break;
1419 19205879 : first_safe_point_index++;
1420 : }
1421 :
1422 : // Step through the safe points to see whether they are in the range.
1423 37304534 : for (int safe_point_index = first_safe_point_index;
1424 : safe_point_index < pointer_maps->length();
1425 : ++safe_point_index) {
1426 19195051 : LPointerMap* map = pointer_maps->at(safe_point_index);
1427 : int safe_point = map->lithium_position();
1428 :
1429 : // The safe points are sorted so we can stop searching here.
1430 19195051 : if (safe_point - 1 > end) break;
1431 :
1432 : // Advance to the next active range that covers the current
1433 : // safe point position.
1434 : LifetimePosition safe_point_pos =
1435 16591801 : LifetimePosition::FromInstructionIndex(safe_point);
1436 39284971 : LiveRange* cur = range;
1437 63383283 : while (cur != NULL && !cur->Covers(safe_point_pos)) {
1438 : cur = cur->next();
1439 : }
1440 24276018 : if (cur == NULL) continue;
1441 :
1442 : // Check if the live range is spilled and the safe point is after
1443 : // the spill position.
1444 17724795 : if (range->HasAllocatedSpillOperand() &&
1445 : safe_point >= range->spill_start_index()) {
1446 : TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n",
1447 8811108 : range->id(), range->spill_start_index(), safe_point);
1448 17622210 : map->RecordPointer(range->GetSpillOperand(), chunk()->zone());
1449 : }
1450 :
1451 8907784 : if (!cur->IsSpilled()) {
1452 : TraceAlloc("Pointer in register for range %d (start at %d) "
1453 : "at safe point %d\n",
1454 177506 : cur->id(), cur->Start().Value(), safe_point);
1455 355012 : LOperand* operand = cur->CreateAssignedOperand(chunk()->zone());
1456 : DCHECK(!operand->IsStackSlot());
1457 355012 : map->RecordPointer(operand, chunk()->zone());
1458 : }
1459 : }
1460 283729 : }
1461 283729 : }
1462 :
1463 :
1464 283730 : void LAllocator::AllocateGeneralRegisters() {
1465 283730 : LAllocatorPhase phase("L_Allocate general registers", this);
1466 283728 : num_registers_ = GetRegConfig()->num_allocatable_general_registers();
1467 283728 : allocatable_register_codes_ = GetRegConfig()->allocatable_general_codes();
1468 283728 : mode_ = GENERAL_REGISTERS;
1469 283728 : AllocateRegisters();
1470 283728 : }
1471 :
1472 :
1473 283727 : void LAllocator::AllocateDoubleRegisters() {
1474 283727 : LAllocatorPhase phase("L_Allocate double registers", this);
1475 283726 : num_registers_ = GetRegConfig()->num_allocatable_double_registers();
1476 283728 : allocatable_register_codes_ = GetRegConfig()->allocatable_double_codes();
1477 283726 : mode_ = DOUBLE_REGISTERS;
1478 283726 : AllocateRegisters();
1479 283728 : }
1480 :
1481 :
1482 15951353 : void LAllocator::AllocateRegisters() {
1483 : DCHECK(unhandled_live_ranges_.is_empty());
1484 :
1485 134446052 : for (int i = 0; i < live_ranges_.length(); ++i) {
1486 200534162 : if (live_ranges_[i] != NULL) {
1487 14482631 : if (live_ranges_[i]->Kind() == mode_) {
1488 6452504 : AddToUnhandledUnsorted(live_ranges_[i]);
1489 : }
1490 : }
1491 : }
1492 567458 : SortUnhandled();
1493 : DCHECK(UnhandledIsSorted());
1494 :
1495 : DCHECK(reusable_slots_.is_empty());
1496 : DCHECK(active_live_ranges_.is_empty());
1497 : DCHECK(inactive_live_ranges_.is_empty());
1498 :
1499 567459 : if (mode_ == DOUBLE_REGISTERS) {
1500 9362936 : for (int i = 0; i < fixed_double_live_ranges_.length(); ++i) {
1501 9362940 : LiveRange* current = fixed_double_live_ranges_.at(i);
1502 4539607 : if (current != NULL) {
1503 3922451 : AddToInactive(current);
1504 : }
1505 : }
1506 : } else {
1507 : DCHECK(mode_ == GENERAL_REGISTERS);
1508 9362851 : for (int i = 0; i < fixed_live_ranges_.length(); ++i) {
1509 9362854 : LiveRange* current = fixed_live_ranges_.at(i);
1510 4539564 : if (current != NULL) {
1511 3223839 : AddToInactive(current);
1512 : }
1513 : }
1514 : }
1515 :
1516 8410266 : while (!unhandled_live_ranges_.is_empty()) {
1517 : DCHECK(UnhandledIsSorted());
1518 31938714 : LiveRange* current = unhandled_live_ranges_.RemoveLast();
1519 : DCHECK(UnhandledIsSorted());
1520 : LifetimePosition position = current->Start();
1521 : #ifdef DEBUG
1522 : allocation_finger_ = position;
1523 : #endif
1524 : TraceAlloc("Processing interval %d start=%d\n",
1525 : current->id(),
1526 7842816 : position.Value());
1527 :
1528 7843279 : if (current->HasAllocatedSpillOperand()) {
1529 436924 : TraceAlloc("Live range %d already has a spill operand\n", current->id());
1530 : LifetimePosition next_pos = position;
1531 436925 : if (IsGapAt(next_pos.InstructionIndex())) {
1532 : next_pos = next_pos.NextInstruction();
1533 : }
1534 436925 : UsePosition* pos = current->NextUsePositionRegisterIsBeneficial(next_pos);
1535 : // If the range already has a spill operand and it doesn't need a
1536 : // register immediately, split it and spill the first part of the range.
1537 436928 : if (pos == NULL) {
1538 301802 : Spill(current);
1539 301803 : continue;
1540 135126 : } else if (pos->pos().Value() >
1541 : current->Start().NextInstruction().Value()) {
1542 : // Do not spill live range eagerly if use position that can benefit from
1543 : // the register is too close to the start of live range.
1544 : SpillBetween(current, current->Start(), pos->pos());
1545 135127 : if (!AllocationOk()) return;
1546 : DCHECK(UnhandledIsSorted());
1547 : continue;
1548 : }
1549 : }
1550 :
1551 65883289 : for (int i = 0; i < active_live_ranges_.length(); ++i) {
1552 65883229 : LiveRange* cur_active = active_live_ranges_.at(i);
1553 29238407 : if (cur_active->End().Value() <= position.Value()) {
1554 6941513 : ActiveToHandled(cur_active);
1555 6941586 : --i; // The live range was removed from the list of active live ranges.
1556 22296894 : } else if (!cur_active->Covers(position)) {
1557 9357876 : ActiveToInactive(cur_active);
1558 9357905 : --i; // The live range was removed from the list of active live ranges.
1559 : }
1560 : }
1561 :
1562 215933409 : for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
1563 215933765 : LiveRange* cur_inactive = inactive_live_ranges_.at(i);
1564 104263853 : if (cur_inactive->End().Value() <= position.Value()) {
1565 2139088 : InactiveToHandled(cur_inactive);
1566 2139275 : --i; // Live range was removed from the list of inactive live ranges.
1567 102124765 : } else if (cur_inactive->Covers(position)) {
1568 10580443 : InactiveToActive(cur_inactive);
1569 10580473 : --i; // Live range was removed from the list of inactive live ranges.
1570 : }
1571 : }
1572 :
1573 : DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled());
1574 :
1575 7406059 : bool result = TryAllocateFreeReg(current);
1576 7405959 : if (!AllocationOk()) return;
1577 :
1578 7405961 : if (!result) AllocateBlockedReg(current);
1579 7405897 : if (!AllocationOk()) return;
1580 :
1581 7405897 : if (current->HasRegisterAssigned()) {
1582 6249345 : AddToActive(current);
1583 : }
1584 : }
1585 :
1586 : reusable_slots_.Rewind(0);
1587 : active_live_ranges_.Rewind(0);
1588 : inactive_live_ranges_.Rewind(0);
1589 : }
1590 :
1591 :
1592 11178075 : const char* LAllocator::RegisterName(int allocation_index) {
1593 11178075 : if (mode_ == GENERAL_REGISTERS) {
1594 21589384 : return GetRegConfig()->GetGeneralRegisterName(allocation_index);
1595 : } else {
1596 766768 : return GetRegConfig()->GetDoubleRegisterName(allocation_index);
1597 : }
1598 : }
1599 :
1600 :
1601 262599230 : void LAllocator::TraceAlloc(const char* msg, ...) {
1602 262599230 : if (FLAG_trace_alloc) {
1603 : va_list arguments;
1604 0 : va_start(arguments, msg);
1605 0 : base::OS::VPrint(msg, arguments);
1606 0 : va_end(arguments);
1607 : }
1608 262599230 : }
1609 :
1610 :
1611 14729419 : bool LAllocator::HasTaggedValue(int virtual_register) const {
1612 14729419 : HValue* value = graph_->LookupValue(virtual_register);
1613 14729419 : if (value == NULL) return false;
1614 26031777 : return value->representation().IsTagged() && !value->type().IsSmi();
1615 : }
1616 :
1617 :
1618 6585980 : RegisterKind LAllocator::RequiredRegisterKind(int virtual_register) const {
1619 6585980 : if (virtual_register < first_artificial_register_) {
1620 6321448 : HValue* value = graph_->LookupValue(virtual_register);
1621 6321448 : if (value != NULL && value->representation().IsDouble()) {
1622 : return DOUBLE_REGISTERS;
1623 : }
1624 264532 : } else if (double_artificial_registers_.Contains(
1625 264532 : virtual_register - first_artificial_register_)) {
1626 : return DOUBLE_REGISTERS;
1627 : }
1628 :
1629 : return GENERAL_REGISTERS;
1630 : }
1631 :
1632 :
1633 6249352 : void LAllocator::AddToActive(LiveRange* range) {
1634 6249352 : TraceAlloc("Add live range %d to active\n", range->id());
1635 6249368 : active_live_ranges_.Add(range, zone());
1636 6249371 : }
1637 :
1638 :
1639 7146213 : void LAllocator::AddToInactive(LiveRange* range) {
1640 7146213 : TraceAlloc("Add live range %d to inactive\n", range->id());
1641 7146214 : inactive_live_ranges_.Add(range, zone());
1642 7146202 : }
1643 :
1644 :
1645 1630274 : void LAllocator::AddToUnhandledSorted(LiveRange* range) {
1646 4890793 : if (range == NULL || range->IsEmpty()) return;
1647 : DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
1648 : DCHECK(allocation_finger_.Value() <= range->Start().Value());
1649 19101487 : for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) {
1650 19093809 : LiveRange* cur_range = unhandled_live_ranges_.at(i);
1651 19093809 : if (range->ShouldBeAllocatedBefore(cur_range)) {
1652 3245132 : TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1);
1653 1622593 : unhandled_live_ranges_.InsertAt(i + 1, range, zone());
1654 : DCHECK(UnhandledIsSorted());
1655 : return;
1656 : }
1657 : }
1658 7678 : TraceAlloc("Add live range %d to unhandled at start\n", range->id());
1659 7678 : unhandled_live_ranges_.InsertAt(0, range, zone());
1660 : DCHECK(UnhandledIsSorted());
1661 : }
1662 :
1663 :
1664 6452493 : void LAllocator::AddToUnhandledUnsorted(LiveRange* range) {
1665 19357467 : if (range == NULL || range->IsEmpty()) return;
1666 : DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
1667 6212632 : TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id());
1668 6212625 : unhandled_live_ranges_.Add(range, zone());
1669 : }
1670 :
1671 :
1672 45604834 : static int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) {
1673 : DCHECK(!(*a)->ShouldBeAllocatedBefore(*b) ||
1674 : !(*b)->ShouldBeAllocatedBefore(*a));
1675 91559415 : if ((*a)->ShouldBeAllocatedBefore(*b)) return 1;
1676 29999205 : if ((*b)->ShouldBeAllocatedBefore(*a)) return -1;
1677 349747 : return (*a)->id() - (*b)->id();
1678 : }
1679 :
1680 :
1681 : // Sort the unhandled live ranges so that the ranges to be processed first are
1682 : // at the end of the array list. This is convenient for the register allocation
1683 : // algorithm because it is efficient to remove elements from the end.
1684 567458 : void LAllocator::SortUnhandled() {
1685 567458 : TraceAlloc("Sort unhandled\n");
1686 : unhandled_live_ranges_.Sort(&UnhandledSortHelper);
1687 567454 : }
1688 :
1689 :
1690 0 : bool LAllocator::UnhandledIsSorted() {
1691 0 : int len = unhandled_live_ranges_.length();
1692 0 : for (int i = 1; i < len; i++) {
1693 0 : LiveRange* a = unhandled_live_ranges_.at(i - 1);
1694 0 : LiveRange* b = unhandled_live_ranges_.at(i);
1695 0 : if (a->Start().Value() < b->Start().Value()) return false;
1696 : }
1697 : return true;
1698 : }
1699 :
1700 :
1701 9130675 : void LAllocator::FreeSpillSlot(LiveRange* range) {
1702 : // Check that we are the last range.
1703 9130675 : if (range->next() != NULL) return;
1704 :
1705 7939065 : if (!range->TopLevel()->HasAllocatedSpillOperand()) return;
1706 :
1707 93278 : int index = range->TopLevel()->GetSpillOperand()->index();
1708 93278 : if (index >= 0) {
1709 58311 : reusable_slots_.Add(range, zone());
1710 : }
1711 : }
1712 :
1713 :
1714 815508 : LOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) {
1715 815508 : if (reusable_slots_.is_empty()) return NULL;
1716 38160 : if (reusable_slots_.first()->End().Value() >
1717 : range->TopLevel()->Start().Value()) {
1718 : return NULL;
1719 : }
1720 17146 : LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand();
1721 17146 : reusable_slots_.Remove(0);
1722 17146 : return result;
1723 : }
1724 :
1725 :
1726 6991311 : void LAllocator::ActiveToHandled(LiveRange* range) {
1727 : DCHECK(active_live_ranges_.Contains(range));
1728 6991311 : active_live_ranges_.RemoveElement(range);
1729 6991323 : TraceAlloc("Moving live range %d from active to handled\n", range->id());
1730 6991317 : FreeSpillSlot(range);
1731 6991324 : }
1732 :
1733 :
1734 9357880 : void LAllocator::ActiveToInactive(LiveRange* range) {
1735 : DCHECK(active_live_ranges_.Contains(range));
1736 9357880 : active_live_ranges_.RemoveElement(range);
1737 9357904 : inactive_live_ranges_.Add(range, zone());
1738 9357905 : TraceAlloc("Moving live range %d from active to inactive\n", range->id());
1739 9357905 : }
1740 :
1741 :
1742 2139409 : void LAllocator::InactiveToHandled(LiveRange* range) {
1743 : DCHECK(inactive_live_ranges_.Contains(range));
1744 2139409 : inactive_live_ranges_.RemoveElement(range);
1745 2139411 : TraceAlloc("Moving live range %d from inactive to handled\n", range->id());
1746 2139408 : FreeSpillSlot(range);
1747 2139411 : }
1748 :
1749 :
1750 10580423 : void LAllocator::InactiveToActive(LiveRange* range) {
1751 : DCHECK(inactive_live_ranges_.Contains(range));
1752 10580423 : inactive_live_ranges_.RemoveElement(range);
1753 10580483 : active_live_ranges_.Add(range, zone());
1754 10580488 : TraceAlloc("Moving live range %d from inactive to active\n", range->id());
1755 10580472 : }
1756 :
1757 :
1758 35234228 : bool LAllocator::TryAllocateFreeReg(LiveRange* current) {
1759 : DCHECK(DoubleRegister::kMaxNumRegisters >= Register::kNumRegisters);
1760 :
1761 125903290 : LifetimePosition free_until_pos[DoubleRegister::kMaxNumRegisters];
1762 :
1763 118496912 : for (int i = 0; i < DoubleRegister::kMaxNumRegisters; i++) {
1764 118496912 : free_until_pos[i] = LifetimePosition::MaxPosition();
1765 : }
1766 :
1767 54446580 : for (int i = 0; i < active_live_ranges_.length(); ++i) {
1768 54446580 : LiveRange* cur_active = active_live_ranges_.at(i);
1769 : free_until_pos[cur_active->assigned_register()] =
1770 23520197 : LifetimePosition::FromInstructionIndex(0);
1771 : }
1772 :
1773 190498200 : for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
1774 210059262 : LiveRange* cur_inactive = inactive_live_ranges_.at(i);
1775 : DCHECK(cur_inactive->End().Value() > current->Start().Value());
1776 : LifetimePosition next_intersection =
1777 91546162 : cur_inactive->FirstIntersection(current);
1778 163531107 : if (!next_intersection.IsValid()) continue;
1779 : int cur_reg = cur_inactive->assigned_register();
1780 19560907 : free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection);
1781 : }
1782 :
1783 7406031 : LOperand* hint = current->FirstHint();
1784 12599329 : if (hint != NULL && (hint->IsRegister() || hint->IsDoubleRegister())) {
1785 : int register_index = hint->index();
1786 : TraceAlloc(
1787 : "Found reg hint %s (free until [%d) for live range %d (end %d[).\n",
1788 : RegisterName(register_index),
1789 : free_until_pos[register_index].Value(),
1790 : current->id(),
1791 9857562 : current->End().Value());
1792 :
1793 : // The desired register is free until the end of the current live range.
1794 4928772 : if (free_until_pos[register_index].Value() >= current->End().Value()) {
1795 : TraceAlloc("Assigning preferred reg %s to live range %d\n",
1796 : RegisterName(register_index),
1797 2981267 : current->id());
1798 2981268 : SetLiveRangeAssignedRegister(current, register_index);
1799 2981266 : return true;
1800 : }
1801 : }
1802 :
1803 : // Find the register which stays free for the longest time.
1804 4424797 : int reg = allocatable_register_codes_[0];
1805 108161032 : for (int i = 1; i < RegisterCount(); ++i) {
1806 49655719 : int code = allocatable_register_codes_[i];
1807 148967157 : if (free_until_pos[code].Value() > free_until_pos[reg].Value()) {
1808 : reg = code;
1809 : }
1810 : }
1811 :
1812 4424797 : LifetimePosition pos = free_until_pos[reg];
1813 :
1814 4424797 : if (pos.Value() <= current->Start().Value()) {
1815 : // All registers are blocked.
1816 : return false;
1817 : }
1818 :
1819 3219142 : if (pos.Value() < current->End().Value()) {
1820 : // Register reg is available at the range start but becomes blocked before
1821 : // the range end. Split current at position where it becomes blocked.
1822 1144904 : LiveRange* tail = SplitRangeAt(current, pos);
1823 1144904 : if (!AllocationOk()) return false;
1824 1144903 : AddToUnhandledSorted(tail);
1825 : }
1826 :
1827 :
1828 : // Register reg is available at the range start and is free until
1829 : // the range end.
1830 : DCHECK(pos.Value() >= current->End().Value());
1831 : TraceAlloc("Assigning free reg %s to live range %d\n",
1832 : RegisterName(reg),
1833 3219145 : current->id());
1834 3219135 : SetLiveRangeAssignedRegister(current, reg);
1835 :
1836 3219128 : return true;
1837 : }
1838 :
1839 :
1840 1305367 : void LAllocator::AllocateBlockedReg(LiveRange* current) {
1841 1205667 : UsePosition* register_use = current->NextRegisterPosition(current->Start());
1842 1205665 : if (register_use == NULL) {
1843 : // There is no use in the current live range that requires a register.
1844 : // We can just spill it.
1845 842065 : Spill(current);
1846 842068 : return;
1847 : }
1848 :
1849 :
1850 5817600 : LifetimePosition use_pos[DoubleRegister::kMaxNumRegisters];
1851 5817600 : LifetimePosition block_pos[DoubleRegister::kMaxNumRegisters];
1852 :
1853 5817568 : for (int i = 0; i < DoubleRegister::kMaxNumRegisters; i++) {
1854 5817568 : use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition();
1855 : }
1856 :
1857 9380036 : for (int i = 0; i < active_live_ranges_.length(); ++i) {
1858 14074555 : LiveRange* range = active_live_ranges_[i];
1859 : int cur_reg = range->assigned_register();
1860 5272480 : if (range->IsFixed() || !range->CanBeSpilled(current->Start())) {
1861 : block_pos[cur_reg] = use_pos[cur_reg] =
1862 3787236 : LifetimePosition::FromInstructionIndex(0);
1863 : } else {
1864 : UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial(
1865 720982 : current->Start());
1866 720982 : if (next_use == NULL) {
1867 186299 : use_pos[cur_reg] = range->End();
1868 : } else {
1869 534683 : use_pos[cur_reg] = next_use->pos();
1870 : }
1871 : }
1872 : }
1873 :
1874 3427795 : for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
1875 4427599 : LiveRange* range = inactive_live_ranges_.at(i);
1876 : DCHECK(range->End().Value() > current->Start().Value());
1877 1532098 : LifetimePosition next_intersection = range->FirstIntersection(current);
1878 2064392 : if (!next_intersection.IsValid()) continue;
1879 : int cur_reg = range->assigned_register();
1880 999804 : if (range->IsFixed()) {
1881 48410 : block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection);
1882 48410 : use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]);
1883 : } else {
1884 951394 : use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection);
1885 : }
1886 : }
1887 :
1888 363599 : int reg = allocatable_register_codes_[0];
1889 9016430 : for (int i = 1; i < RegisterCount(); ++i) {
1890 4144616 : int code = allocatable_register_codes_[i];
1891 12433848 : if (use_pos[code].Value() > use_pos[reg].Value()) {
1892 : reg = code;
1893 : }
1894 : }
1895 :
1896 363599 : LifetimePosition pos = use_pos[reg];
1897 :
1898 363599 : if (pos.Value() < register_use->pos().Value()) {
1899 : // All registers are blocked before the first use that requires a register.
1900 : // Spill starting part of live range up to that use.
1901 : SpillBetween(current, current->Start(), register_use->pos());
1902 : return;
1903 : }
1904 :
1905 98038 : if (block_pos[reg].Value() < current->End().Value()) {
1906 : // Register becomes blocked before the current range end. Split before that
1907 : // position.
1908 : LiveRange* tail = SplitBetween(current,
1909 : current->Start(),
1910 1662 : block_pos[reg].InstructionStart());
1911 1662 : if (!AllocationOk()) return;
1912 1662 : AddToUnhandledSorted(tail);
1913 : }
1914 :
1915 : // Register reg is not blocked for the whole range.
1916 : DCHECK(block_pos[reg].Value() >= current->End().Value());
1917 : TraceAlloc("Assigning blocked reg %s to live range %d\n",
1918 : RegisterName(reg),
1919 49019 : current->id());
1920 49018 : SetLiveRangeAssignedRegister(current, reg);
1921 :
1922 : // This register was not free. Thus we need to find and spill
1923 : // parts of active and inactive live regions that use the same register
1924 : // at the same lifetime positions as current.
1925 49017 : SplitAndSpillIntersecting(current);
1926 : }
1927 :
1928 :
1929 49019 : LifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range,
1930 : LifetimePosition pos) {
1931 96135 : HBasicBlock* block = GetBlock(pos.InstructionStart());
1932 31766 : HBasicBlock* loop_header =
1933 49018 : block->IsLoopHeader() ? block : block->parent_loop_header();
1934 :
1935 49018 : if (loop_header == NULL) return pos;
1936 :
1937 : UsePosition* prev_use =
1938 : range->PreviousUsePositionRegisterIsBeneficial(pos);
1939 :
1940 30964 : while (loop_header != NULL) {
1941 : // We are going to spill live range inside the loop.
1942 : // If possible try to move spilling position backwards to loop header.
1943 : // This will reduce number of memory moves on the back edge.
1944 : LifetimePosition loop_start = LifetimePosition::FromInstructionIndex(
1945 : loop_header->first_instruction_index());
1946 :
1947 15883 : if (range->Covers(loop_start)) {
1948 5175 : if (prev_use == NULL || prev_use->pos().Value() < loop_start.Value()) {
1949 : // No register beneficial use inside the loop before the pos.
1950 : pos = loop_start;
1951 : }
1952 : }
1953 :
1954 : // Try hoisting out to an outer loop.
1955 : loop_header = loop_header->parent_loop_header();
1956 : }
1957 :
1958 15081 : return pos;
1959 : }
1960 :
1961 :
1962 98025 : void LAllocator::SplitAndSpillIntersecting(LiveRange* current) {
1963 : DCHECK(current->HasRegisterAssigned());
1964 : int reg = current->assigned_register();
1965 : LifetimePosition split_pos = current->Start();
1966 1427986 : for (int i = 0; i < active_live_ranges_.length(); ++i) {
1967 2043941 : LiveRange* range = active_live_ranges_[i];
1968 664974 : if (range->assigned_register() == reg) {
1969 49006 : UsePosition* next_pos = range->NextRegisterPosition(current->Start());
1970 49018 : LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos);
1971 49019 : if (next_pos == NULL) {
1972 15013 : SpillAfter(range, spill_pos);
1973 : } else {
1974 : // When spilling between spill_pos and next_pos ensure that the range
1975 : // remains spilled at least until the start of the current live range.
1976 : // This guarantees that we will not introduce new unhandled ranges that
1977 : // start before the current range as this violates allocation invariant
1978 : // and will lead to an inconsistent state of active and inactive
1979 : // live-ranges: ranges are allocated in order of their start positions,
1980 : // ranges are retired from active/inactive when the start of the
1981 : // current live-range is larger than their end.
1982 34006 : SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos());
1983 : }
1984 49018 : if (!AllocationOk()) return;
1985 49018 : ActiveToHandled(range);
1986 49019 : --i;
1987 : }
1988 : }
1989 :
1990 209655 : for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
1991 305340 : LiveRange* range = inactive_live_ranges_[i];
1992 : DCHECK(range->End().Value() > current->Start().Value());
1993 95684 : if (range->assigned_register() == reg && !range->IsFixed()) {
1994 388 : LifetimePosition next_intersection = range->FirstIntersection(current);
1995 387 : if (next_intersection.IsValid()) {
1996 1 : UsePosition* next_pos = range->NextRegisterPosition(current->Start());
1997 1 : if (next_pos == NULL) {
1998 0 : SpillAfter(range, split_pos);
1999 : } else {
2000 : next_intersection = Min(next_intersection, next_pos->pos());
2001 : SpillBetween(range, split_pos, next_intersection);
2002 : }
2003 1 : if (!AllocationOk()) return;
2004 1 : InactiveToHandled(range);
2005 1 : --i;
2006 : }
2007 : }
2008 : }
2009 : }
2010 :
2011 :
2012 508930 : bool LAllocator::IsBlockBoundary(LifetimePosition pos) {
2013 508930 : return pos.IsInstructionStart() &&
2014 478422 : InstructionAt(pos.InstructionIndex())->IsLabel();
2015 : }
2016 :
2017 :
2018 3808224 : LiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) {
2019 : DCHECK(!range->IsFixed());
2020 2128980 : TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value());
2021 :
2022 2128970 : if (pos.Value() <= range->Start().Value()) return range;
2023 :
2024 : // We can't properly connect liveranges if split occured at the end
2025 : // of control instruction.
2026 : DCHECK(pos.IsInstructionStart() ||
2027 : !chunk_->instructions()->at(pos.InstructionIndex())->IsControl());
2028 :
2029 : int vreg = GetVirtualRegister();
2030 1679244 : if (!AllocationOk()) return NULL;
2031 1679247 : LiveRange* result = LiveRangeFor(vreg);
2032 1679247 : range->SplitAt(pos, result, zone());
2033 1679255 : return result;
2034 : }
2035 :
2036 :
2037 970744 : LiveRange* LAllocator::SplitBetween(LiveRange* range,
2038 : LifetimePosition start,
2039 : LifetimePosition end) {
2040 : DCHECK(!range->IsFixed());
2041 : TraceAlloc("Splitting live range %d in position between [%d, %d]\n",
2042 : range->id(),
2043 : start.Value(),
2044 485372 : end.Value());
2045 :
2046 485370 : LifetimePosition split_pos = FindOptimalSplitPos(start, end);
2047 : DCHECK(split_pos.Value() >= start.Value());
2048 485370 : return SplitRangeAt(range, split_pos);
2049 : }
2050 :
2051 :
2052 485369 : LifetimePosition LAllocator::FindOptimalSplitPos(LifetimePosition start,
2053 : LifetimePosition end) {
2054 : int start_instr = start.InstructionIndex();
2055 : int end_instr = end.InstructionIndex();
2056 : DCHECK(start_instr <= end_instr);
2057 :
2058 : // We have no choice
2059 485369 : if (start_instr == end_instr) return end;
2060 :
2061 573930 : HBasicBlock* start_block = GetBlock(start);
2062 485371 : HBasicBlock* end_block = GetBlock(end);
2063 :
2064 485369 : if (end_block == start_block) {
2065 : // The interval is split in the same basic block. Split at the latest
2066 : // possible position.
2067 147197 : return end;
2068 : }
2069 :
2070 407910 : HBasicBlock* block = end_block;
2071 : // Find header of outermost loop.
2072 459665 : while (block->parent_loop_header() != NULL &&
2073 88561 : block->parent_loop_header()->block_id() > start_block->block_id()) {
2074 : block = block->parent_loop_header();
2075 : }
2076 :
2077 : // We did not find any suitable outer loop. Split at the latest possible
2078 : // position unless end_block is a loop header itself.
2079 643850 : if (block == end_block && !end_block->IsLoopHeader()) return end;
2080 :
2081 : return LifetimePosition::FromInstructionIndex(
2082 : block->first_instruction_index());
2083 : }
2084 :
2085 :
2086 30026 : void LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
2087 15013 : LiveRange* second_part = SplitRangeAt(range, pos);
2088 30026 : if (!AllocationOk()) return;
2089 15013 : Spill(second_part);
2090 : }
2091 :
2092 :
2093 0 : void LAllocator::SpillBetween(LiveRange* range,
2094 : LifetimePosition start,
2095 : LifetimePosition end) {
2096 449707 : SpillBetweenUntil(range, start, start, end);
2097 0 : }
2098 :
2099 :
2100 483709 : void LAllocator::SpillBetweenUntil(LiveRange* range,
2101 : LifetimePosition start,
2102 : LifetimePosition until,
2103 967424 : LifetimePosition end) {
2104 483709 : CHECK(start.Value() < end.Value());
2105 483709 : LiveRange* second_part = SplitRangeAt(range, start);
2106 483711 : if (!AllocationOk()) return;
2107 :
2108 483712 : if (second_part->Start().Value() < end.Value()) {
2109 : // The split result intersects with [start, end[.
2110 : // Split it at position between ]start+1, end[, spill the middle part
2111 : // and put the rest to unhandled.
2112 : LiveRange* third_part = SplitBetween(
2113 : second_part,
2114 : Max(second_part->Start().InstructionEnd(), until),
2115 483711 : end.PrevInstruction().InstructionEnd());
2116 483713 : if (!AllocationOk()) return;
2117 :
2118 : DCHECK(third_part != second_part);
2119 :
2120 483714 : Spill(second_part);
2121 483713 : AddToUnhandledSorted(third_part);
2122 : } else {
2123 : // The split result does not intersect with [start, end[.
2124 : // Nothing to spill. Just put it to unhandled as whole.
2125 1 : AddToUnhandledSorted(second_part);
2126 : }
2127 : }
2128 :
2129 :
2130 4083544 : void LAllocator::Spill(LiveRange* range) {
2131 : DCHECK(!range->IsSpilled());
2132 1642588 : TraceAlloc("Spilling live range %d\n", range->id());
2133 : LiveRange* first = range->TopLevel();
2134 :
2135 1642591 : if (!first->HasAllocatedSpillOperand()) {
2136 815511 : LOperand* op = TryReuseSpillSlot(range);
2137 1613869 : if (op == NULL) op = chunk_->GetNextSpillSlot(range->Kind());
2138 : first->SetSpillOperand(op);
2139 : }
2140 1642594 : range->MakeSpilled(chunk()->zone());
2141 1642594 : }
2142 :
2143 :
2144 0 : int LAllocator::RegisterCount() const {
2145 58588731 : return num_registers_;
2146 : }
2147 :
2148 :
2149 : #ifdef DEBUG
2150 :
2151 :
2152 : void LAllocator::Verify() const {
2153 : for (int i = 0; i < live_ranges()->length(); ++i) {
2154 : LiveRange* current = live_ranges()->at(i);
2155 : if (current != NULL) current->Verify();
2156 : }
2157 : }
2158 :
2159 :
2160 : #endif
2161 :
2162 :
2163 2269789 : LAllocatorPhase::LAllocatorPhase(const char* name, LAllocator* allocator)
2164 : : CompilationPhase(name, allocator->graph()->info()),
2165 2269789 : allocator_(allocator) {
2166 2269793 : if (FLAG_hydrogen_stats) {
2167 : allocator_zone_start_allocation_size_ =
2168 0 : allocator->zone()->allocation_size();
2169 : }
2170 2269793 : }
2171 :
2172 :
2173 4539624 : LAllocatorPhase::~LAllocatorPhase() {
2174 2269811 : if (FLAG_hydrogen_stats) {
2175 0 : size_t size = allocator_->zone()->allocation_size() -
2176 0 : allocator_zone_start_allocation_size_;
2177 0 : isolate()->GetHStatistics()->SaveTiming(name(), base::TimeDelta(), size);
2178 : }
2179 :
2180 2269811 : if (ShouldProduceTraceOutput()) {
2181 0 : isolate()->GetHTracer()->TraceLithium(name(), allocator_->chunk());
2182 0 : isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_);
2183 : }
2184 :
2185 : #ifdef DEBUG
2186 : if (allocator_ != NULL) allocator_->Verify();
2187 : #endif
2188 2269808 : }
2189 :
2190 :
2191 : } // namespace internal
2192 : } // namespace v8
|
