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 48445551 : return a.Value() < b.Value() ? a : b;
21 : }
22 :
23 :
24 : static inline LifetimePosition Max(LifetimePosition a, LifetimePosition b) {
25 28348846 : return a.Value() > b.Value() ? a : b;
26 : }
27 :
28 :
29 39554334 : 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 39554334 : register_beneficial_(true) {
38 78650762 : if (operand_ != NULL && operand_->IsUnallocated()) {
39 : LUnallocated* unalloc = LUnallocated::cast(operand_);
40 68821300 : requires_reg_ = unalloc->HasRegisterPolicy() ||
41 39097076 : unalloc->HasDoubleRegisterPolicy();
42 39097076 : register_beneficial_ = !unalloc->HasAnyPolicy();
43 : }
44 : DCHECK(pos_.IsValid());
45 39554334 : }
46 :
47 :
48 0 : bool UsePosition::HasHint() const {
49 90082747 : return hint_ != NULL && !hint_->IsUnallocated();
50 : }
51 :
52 :
53 0 : bool UsePosition::RequiresRegister() const {
54 15646398 : return requires_reg_;
55 : }
56 :
57 :
58 0 : bool UsePosition::RegisterIsBeneficial() const {
59 5372172 : return register_beneficial_;
60 : }
61 :
62 :
63 1684141 : void UseInterval::SplitAt(LifetimePosition pos, Zone* zone) {
64 : DCHECK(Contains(pos) && pos.Value() != start().Value());
65 1684141 : UseInterval* after = new(zone) UseInterval(pos, end_);
66 1684139 : after->next_ = next_;
67 1684139 : next_ = after;
68 1684139 : end_ = pos;
69 1684139 : }
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 15258261 : 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 30516211 : spill_start_index_(kMaxInt) {}
117 :
118 :
119 0 : void LiveRange::set_assigned_register(int reg, Zone* zone) {
120 : DCHECK(!HasRegisterAssigned() && !IsSpilled());
121 13375334 : assigned_register_ = reg;
122 13375334 : ConvertOperands(zone);
123 0 : }
124 :
125 :
126 0 : void LiveRange::MakeSpilled(Zone* zone) {
127 : DCHECK(!IsSpilled());
128 : DCHECK(TopLevel()->HasAllocatedSpillOperand());
129 1643609 : spilled_ = true;
130 1643609 : assigned_register_ = kInvalidAssignment;
131 1643609 : ConvertOperands(zone);
132 0 : }
133 :
134 :
135 0 : bool LiveRange::HasAllocatedSpillOperand() const {
136 : DCHECK(spill_operand_ != NULL);
137 26288774 : 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 1250777 : spill_operand_->ConvertTo(operand->kind(), operand->index());
146 0 : }
147 :
148 :
149 1996216 : UsePosition* LiveRange::NextUsePosition(LifetimePosition start) {
150 5020665 : UsePosition* use_pos = last_processed_use_;
151 3301613 : if (use_pos == NULL) use_pos = first_pos();
152 5020665 : while (use_pos != NULL && use_pos->pos().Value() < start.Value()) {
153 : use_pos = use_pos->next();
154 : }
155 3301613 : last_processed_use_ = use_pos;
156 0 : return use_pos;
157 : }
158 :
159 :
160 1213888 : UsePosition* LiveRange::NextUsePositionRegisterIsBeneficial(
161 : LifetimePosition start) {
162 4607551 : UsePosition* pos = NextUsePosition(start);
163 12368441 : while (pos != NULL && !pos->RegisterIsBeneficial()) {
164 : pos = pos->next();
165 : }
166 1213888 : return pos;
167 : }
168 :
169 :
170 0 : UsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial(
171 15134 : LifetimePosition start) {
172 39058 : UsePosition* pos = first_pos();
173 : UsePosition* prev = NULL;
174 54192 : while (pos != NULL && pos->pos().Value() < start.Value()) {
175 39058 : if (pos->RegisterIsBeneficial()) prev = pos;
176 : pos = pos->next();
177 : }
178 0 : return prev;
179 : }
180 :
181 :
182 2087725 : UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) {
183 14614148 : UsePosition* pos = NextUsePosition(start);
184 34435996 : while (pos != NULL && !pos->RequiresRegister()) {
185 : pos = pos->next();
186 : }
187 2087725 : return pos;
188 : }
189 :
190 :
191 826726 : 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 826726 : UsePosition* use_pos = NextRegisterPosition(pos);
195 826726 : if (use_pos == NULL) return true;
196 : return
197 627108 : use_pos->pos().Value() > pos.NextInstruction().InstructionEnd().Value();
198 : }
199 :
200 :
201 33246564 : LOperand* LiveRange::CreateAssignedOperand(Zone* zone) {
202 : LOperand* op = NULL;
203 16623282 : if (HasRegisterAssigned()) {
204 : DCHECK(!IsSpilled());
205 14285185 : switch (Kind()) {
206 : case GENERAL_REGISTERS:
207 9933262 : op = LRegister::Create(assigned_register(), zone);
208 9933297 : break;
209 : case DOUBLE_REGISTERS:
210 4351923 : op = LDoubleRegister::Create(assigned_register(), zone);
211 4351944 : break;
212 : default:
213 0 : UNREACHABLE();
214 : }
215 2338097 : } else if (IsSpilled()) {
216 : DCHECK(!HasRegisterAssigned());
217 2338097 : 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 16623338 : return op;
225 : }
226 :
227 :
228 0 : UseInterval* LiveRange::FirstSearchIntervalForPosition(
229 : LifetimePosition position) const {
230 230683503 : if (current_interval_ == NULL) return first_interval_;
231 217860531 : if (current_interval_->start().Value() > position.Value()) {
232 153009 : 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 399589976 : if (to_start_of == NULL) return;
242 399596798 : if (to_start_of->start().Value() > but_not_past.Value()) return;
243 : LifetimePosition start =
244 158721712 : current_interval_ == NULL ? LifetimePosition::Invalid()
245 158721712 : : current_interval_->start();
246 158721712 : if (to_start_of->start().Value() > start.Value()) {
247 30562800 : current_interval_ = to_start_of;
248 : }
249 : }
250 :
251 :
252 1684259 : 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 297208 : 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 1684259 : 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 1981351 : while (current != NULL) {
272 1981344 : if (current->Contains(position)) {
273 1684136 : current->SplitAt(position, zone);
274 1684134 : break;
275 : }
276 : UseInterval* next = current->next();
277 297208 : if (next->start().Value() >= position.Value()) {
278 116 : split_at_start = (next->start().Value() == position.Value());
279 116 : break;
280 : }
281 : current = next;
282 : }
283 :
284 : // Partition original use intervals to the two live ranges.
285 1684257 : UseInterval* before = current;
286 : UseInterval* after = before->next();
287 1684257 : result->last_interval_ = (last_interval_ == before)
288 : ? after // Only interval in the range after split.
289 1684257 : : last_interval_; // Last interval of the original range.
290 1684257 : result->first_interval_ = after;
291 1684257 : last_interval_ = before;
292 :
293 : // Find the last use position before the split and the first use
294 : // position after it.
295 9715057 : UsePosition* use_after = first_pos_;
296 : UsePosition* use_before = NULL;
297 1684257 : 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 19 : 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 9715038 : 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 1684257 : if (use_before != NULL) {
314 1603661 : use_before->next_ = NULL;
315 : } else {
316 80596 : first_pos_ = NULL;
317 : }
318 1684257 : 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 1684257 : last_processed_use_ = NULL;
323 1684257 : 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 1684257 : result->parent_ = (parent_ == NULL) ? this : parent_;
328 1684257 : result->kind_ = result->parent_->kind_;
329 1684257 : result->next_ = next_;
330 1684257 : next_ = result;
331 :
332 : #ifdef DEBUG
333 : Verify();
334 : result->Verify();
335 : #endif
336 1684257 : }
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 2863735 : bool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const {
345 : LifetimePosition start = Start();
346 : LifetimePosition other_start = other->Start();
347 95920002 : if (start.Value() == other_start.Value()) {
348 : UsePosition* pos = first_pos();
349 1435027 : if (pos == NULL) return false;
350 : UsePosition* other_pos = other->first_pos();
351 1428708 : if (other_pos == NULL) return true;
352 1424393 : return pos->pos().Value() < other_pos->pos().Value();
353 : }
354 94484975 : return start.Value() < other_start.Value();
355 : }
356 :
357 :
358 0 : void LiveRange::ShortenTo(LifetimePosition start) {
359 15431800 : 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 15431803 : first_interval_->set_start(start);
364 0 : }
365 :
366 :
367 409092 : 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 409092 : end.Value());
374 : LifetimePosition new_end = end;
375 1561426 : while (first_interval_ != NULL &&
376 : first_interval_->start().Value() <= end.Value()) {
377 743242 : if (first_interval_->end().Value() > end.Value()) {
378 : new_end = first_interval_->end();
379 : }
380 743242 : first_interval_ = first_interval_->next();
381 : }
382 :
383 : UseInterval* new_interval = new(zone) UseInterval(start, new_end);
384 409092 : new_interval->next_ = first_interval_;
385 409092 : first_interval_ = new_interval;
386 409092 : if (new_interval->next() == NULL) {
387 213499 : last_interval_ = new_interval;
388 : }
389 409092 : }
390 :
391 :
392 108769382 : 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 108769382 : end.Value());
399 108777195 : if (first_interval_ == NULL) {
400 : UseInterval* interval = new(zone) UseInterval(start, end);
401 13334663 : first_interval_ = interval;
402 13334663 : last_interval_ = interval;
403 : } else {
404 95442489 : if (end.Value() == first_interval_->start().Value()) {
405 : first_interval_->set_start(start);
406 70289593 : } else if (end.Value() < first_interval_->start().Value()) {
407 : UseInterval* interval = new(zone) UseInterval(start, end);
408 42427265 : interval->set_next(first_interval_);
409 42427265 : 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 27862235 : first_interval_->start_ = Min(start, first_interval_->start_);
416 27862235 : first_interval_->end_ = Max(end, first_interval_->end_);
417 : }
418 : }
419 108777059 : }
420 :
421 :
422 39553748 : 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 39553748 : pos.Value());
429 79108876 : UsePosition* use_pos = new(zone) UsePosition(pos, operand, hint);
430 : UsePosition* prev_hint = NULL;
431 : UsePosition* prev = NULL;
432 39885267 : UsePosition* current = first_pos_;
433 79440404 : while (current != NULL && current->pos().Value() < pos.Value()) {
434 330130 : prev_hint = current->HasHint() ? current : prev_hint;
435 : prev = current;
436 : current = current->next();
437 : }
438 :
439 39555137 : if (prev == NULL) {
440 : use_pos->set_next(first_pos_);
441 39225007 : first_pos_ = use_pos;
442 : } else {
443 330130 : use_pos->next_ = prev->next_;
444 330130 : prev->next_ = use_pos;
445 : }
446 :
447 79110228 : if (prev_hint == NULL && use_pos->HasHint()) {
448 7816260 : current_hint_operand_ = hint;
449 : }
450 39555137 : }
451 :
452 :
453 30036770 : void LiveRange::ConvertOperands(Zone* zone) {
454 15018360 : LOperand* op = CreateAssignedOperand(zone);
455 79258154 : UsePosition* use_pos = first_pos();
456 69665897 : while (use_pos != NULL) {
457 : DCHECK(Start().Value() <= use_pos->pos().Value() &&
458 : use_pos->pos().Value() <= End().Value());
459 :
460 39629077 : 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 15018410 : }
468 :
469 :
470 271973258 : bool LiveRange::CanCover(LifetimePosition position) const {
471 277005479 : if (IsEmpty()) return false;
472 548978872 : return Start().Value() <= position.Value() &&
473 : position.Value() < End().Value();
474 : }
475 :
476 :
477 163370379 : bool LiveRange::Covers(LifetimePosition position) {
478 163370379 : if (!CanCover(position)) return false;
479 : UseInterval* start_search = FirstSearchIntervalForPosition(position);
480 262329861 : 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 262308479 : if (interval->Contains(position)) return true;
487 229857077 : if (interval->start().Value() > position.Value()) return false;
488 : }
489 : return false;
490 : }
491 :
492 :
493 816711961 : LifetimePosition LiveRange::FirstIntersection(LiveRange* other) {
494 41201796 : UseInterval* b = other->first_interval();
495 92932056 : if (b == NULL) return LifetimePosition::Invalid();
496 : LifetimePosition advance_last_processed_up_to = b->start();
497 199591952 : UseInterval* a = FirstSearchIntervalForPosition(b->start());
498 364347405 : while (a != NULL && b != NULL) {
499 262153287 : if (a->start().Value() > other->End().Value()) break;
500 262035170 : if (b->start().Value() > End().Value()) break;
501 261323584 : LifetimePosition cur_intersection = a->Intersect(b);
502 261330522 : if (cur_intersection.IsValid()) {
503 20536774 : return cur_intersection;
504 : }
505 240793748 : if (a->start().Value() < b->start().Value()) {
506 : a = a->next();
507 399183400 : 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 283190 : 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 849580 : allocation_ok_(true) {}
534 :
535 283196 : void LAllocator::InitializeLivenessAnalysis() {
536 : // Initialize the live_in sets for each block to NULL.
537 283196 : int block_count = graph_->blocks()->length();
538 283196 : live_in_sets_.Initialize(block_count, zone());
539 283197 : live_in_sets_.AddBlock(NULL, block_count, zone());
540 283194 : }
541 :
542 :
543 8987079 : BitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) {
544 : // Compute live out for the given block, except not including backward
545 : // successor edges.
546 14447963 : BitVector* live_out = new(zone()) BitVector(next_virtual_register_, zone());
547 :
548 : // Process all successor blocks.
549 9582688 : 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 5089151 : HBasicBlock* successor = it.Current();
553 10178302 : BitVector* live_in = live_in_sets_[successor->block_id()];
554 5089151 : 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 5089151 : int index = successor->PredecessorIndexOf(block);
559 : const ZoneList<HPhi*>* phis = successor->phis();
560 11405248 : for (int i = 0; i < phis->length(); ++i) {
561 6316092 : HPhi* phi = phis->at(i);
562 613467 : if (!phi->OperandAt(index)->IsConstant()) {
563 431484 : live_out->Add(phi->OperandAt(index)->id());
564 : }
565 : }
566 : }
567 :
568 4493534 : return live_out;
569 : }
570 :
571 :
572 8987070 : 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 4493535 : block->first_instruction_index());
578 : LifetimePosition end = LifetimePosition::FromInstructionIndex(
579 4493535 : block->last_instruction_index()).NextInstruction();
580 : BitVector::Iterator iterator(live_out);
581 61617606 : while (!iterator.Done()) {
582 26315240 : int operand_index = iterator.Current();
583 26315240 : LiveRange* range = LiveRangeFor(operand_index);
584 26315241 : range->AddUseInterval(start, end, zone());
585 26315205 : iterator.Advance();
586 : }
587 4493563 : }
588 :
589 :
590 0 : int LAllocator::FixedDoubleLiveRangeID(int index) {
591 3915173 : return -index - 1 - Register::kNumRegisters;
592 : }
593 :
594 :
595 7882269 : LOperand* LAllocator::AllocateFixed(LUnallocated* operand,
596 : int pos,
597 6689656 : bool is_tagged) {
598 7882269 : TraceAlloc("Allocating fixed reg for op %d\n", operand->virtual_register());
599 : DCHECK(operand->HasFixedPolicy());
600 7882290 : if (operand->HasFixedSlotPolicy()) {
601 : operand->ConvertTo(LOperand::STACK_SLOT, operand->fixed_slot_index());
602 7446483 : } else if (operand->HasFixedRegisterPolicy()) {
603 : int reg_index = operand->fixed_register_index();
604 : operand->ConvertTo(LOperand::REGISTER, reg_index);
605 65844 : } 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 7882290 : if (is_tagged) {
612 6689652 : TraceAlloc("Fixed reg is tagged at %d\n", pos);
613 : LInstruction* instr = InstructionAt(pos);
614 6689656 : if (instr->HasPointerMap()) {
615 8854642 : instr->pointer_map()->RecordPointer(operand, chunk()->zone());
616 : }
617 : }
618 7882290 : return operand;
619 : }
620 :
621 :
622 36651000 : LiveRange* LAllocator::FixedLiveRangeFor(int index) {
623 : DCHECK(index < Register::kNumRegisters);
624 70084176 : LiveRange* result = fixed_live_ranges_[index];
625 33433182 : if (result == NULL) {
626 9653459 : result = new(zone()) LiveRange(FixedLiveRangeID(index), chunk()->zone());
627 : DCHECK(result->IsFixed());
628 3217779 : result->kind_ = GENERAL_REGISTERS;
629 3217779 : SetLiveRangeAssignedRegister(result, index);
630 3217812 : fixed_live_ranges_[index] = result;
631 : }
632 33433176 : return result;
633 : }
634 :
635 :
636 29276960 : LiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) {
637 : DCHECK(index < DoubleRegister::kMaxNumRegisters);
638 54638719 : LiveRange* result = fixed_double_live_ranges_[index];
639 25361787 : if (result == NULL) {
640 : result = new(zone()) LiveRange(FixedDoubleLiveRangeID(index),
641 11745528 : chunk()->zone());
642 : DCHECK(result->IsFixed());
643 3915110 : result->kind_ = DOUBLE_REGISTERS;
644 3915110 : SetLiveRangeAssignedRegister(result, index);
645 3915145 : fixed_double_live_ranges_[index] = result;
646 : }
647 25361759 : return result;
648 : }
649 :
650 :
651 100366669 : LiveRange* LAllocator::LiveRangeFor(int index) {
652 192613008 : if (index >= live_ranges_.length()) {
653 3982162 : live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1, zone());
654 : }
655 92246437 : LiveRange* result = live_ranges_[index];
656 92246437 : if (result == NULL) {
657 24376880 : result = new(zone()) LiveRange(index, chunk()->zone());
658 8125529 : live_ranges_[index] = result;
659 : }
660 92246339 : return result;
661 : }
662 :
663 :
664 1023117 : LGap* LAllocator::GetLastGap(HBasicBlock* block) {
665 : int last_instruction = block->last_instruction_index();
666 511558 : int index = chunk_->NearestGapPos(last_instruction);
667 511559 : return GapAt(index);
668 : }
669 :
670 :
671 8913559 : HPhi* LAllocator::LookupPhi(LOperand* operand) const {
672 8913559 : if (!operand->IsUnallocated()) return NULL;
673 : int index = LUnallocated::cast(operand)->virtual_register();
674 3001381 : HValue* instr = graph_->LookupValue(index);
675 5870270 : if (instr != NULL && instr->IsPhi()) {
676 613468 : return HPhi::cast(instr);
677 : }
678 : return NULL;
679 : }
680 :
681 :
682 54790985 : LiveRange* LAllocator::LiveRangeFor(LOperand* operand) {
683 54790985 : if (operand->IsUnallocated()) {
684 39096153 : return LiveRangeFor(LUnallocated::cast(operand)->virtual_register());
685 15694832 : } else if (operand->IsRegister()) {
686 14522054 : return FixedLiveRangeFor(operand->index());
687 1172778 : } else if (operand->IsDoubleRegister()) {
688 131661 : return FixedDoubleLiveRangeFor(operand->index());
689 : } else {
690 : return NULL;
691 : }
692 : }
693 :
694 :
695 16325042 : void LAllocator::Define(LifetimePosition position,
696 : LOperand* operand,
697 : LOperand* hint) {
698 16325042 : LiveRange* range = LiveRangeFor(operand);
699 32650362 : if (range == NULL) return;
700 :
701 15889360 : if (range->IsEmpty() || range->Start().Value() > position.Value()) {
702 : // Can happen if there is a definition without use.
703 915120 : range->AddUseInterval(position, position.NextInstruction(), zone());
704 457560 : range->AddUsePosition(position.NextInstruction(), NULL, NULL, zone());
705 : } else {
706 : range->ShortenTo(position);
707 : }
708 :
709 15889487 : if (operand->IsUnallocated()) {
710 : LUnallocated* unalloc_operand = LUnallocated::cast(operand);
711 8443020 : range->AddUsePosition(position, unalloc_operand, hint, zone());
712 : }
713 : }
714 :
715 :
716 38466188 : void LAllocator::Use(LifetimePosition block_start,
717 : LifetimePosition position,
718 : LOperand* operand,
719 : LOperand* hint) {
720 38466188 : LiveRange* range = LiveRangeFor(operand);
721 76933183 : if (range == NULL) return;
722 37861227 : if (operand->IsUnallocated()) {
723 : LUnallocated* unalloc_operand = LUnallocated::cast(operand);
724 30654373 : range->AddUsePosition(position, unalloc_operand, hint, zone());
725 : }
726 37862034 : range->AddUseInterval(block_start, position, zone());
727 : }
728 :
729 :
730 6397180 : void LAllocator::AddConstraintsGapMove(int index,
731 : LOperand* from,
732 19191542 : LOperand* to) {
733 : LGap* gap = GapAt(index);
734 : LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START,
735 12794368 : chunk()->zone());
736 6397178 : if (from->IsUnallocated()) {
737 : const ZoneList<LMoveOperands>* move_operands = move->move_operands();
738 23425825 : for (int i = 0; i < move_operands->length(); ++i) {
739 23426199 : LMoveOperands cur = move_operands->at(i);
740 : LOperand* cur_to = cur.destination();
741 8514698 : if (cur_to->IsUnallocated()) {
742 27329 : if (LUnallocated::cast(cur_to)->virtual_register() ==
743 : LUnallocated::cast(from)->virtual_register()) {
744 374 : move->AddMove(cur.source(), to, chunk()->zone());
745 6397174 : return;
746 : }
747 : }
748 : }
749 : }
750 6396804 : move->AddMove(from, to, chunk()->zone());
751 : }
752 :
753 :
754 124321993 : void LAllocator::MeetRegisterConstraints(HBasicBlock* block) {
755 : int start = block->first_instruction_index();
756 : int end = block->last_instruction_index();
757 4493549 : if (start == -1) return;
758 44494580 : for (int i = start; i <= end; ++i) {
759 44494403 : if (IsGapAt(i)) {
760 : LInstruction* instr = NULL;
761 : LInstruction* prev_instr = NULL;
762 26740604 : if (i < end) instr = InstructionAt(i + 1);
763 26740604 : if (i > start) prev_instr = InstructionAt(i - 1);
764 26740604 : MeetConstraintsBetween(prev_instr, instr, i);
765 26740956 : if (!AllocationOk()) return;
766 : }
767 : }
768 : }
769 :
770 :
771 26740766 : void LAllocator::MeetConstraintsBetween(LInstruction* first,
772 : LInstruction* second,
773 30521742 : int gap_index) {
774 : // Handle fixed temporaries.
775 26740766 : if (first != NULL) {
776 44675461 : for (TempIterator it(first); !it.Done(); it.Advance()) {
777 179996 : LUnallocated* temp = LUnallocated::cast(it.Current());
778 179996 : if (temp->HasFixedPolicy()) {
779 67049 : AllocateFixed(temp, gap_index - 1, false);
780 : }
781 : }
782 : }
783 :
784 : // Handle fixed output operand.
785 26740899 : if (first != NULL && first->Output() != NULL) {
786 7767595 : LUnallocated* first_output = LUnallocated::cast(first->Output());
787 15099439 : LiveRange* range = LiveRangeFor(first_output->virtual_register());
788 : bool assigned = false;
789 7767617 : if (first_output->HasFixedPolicy()) {
790 : LUnallocated* output_copy = first_output->CopyUnconstrained(
791 3805994 : chunk()->zone());
792 1903002 : bool is_tagged = HasTaggedValue(first_output->virtual_register());
793 1903004 : AllocateFixed(first_output, gap_index, is_tagged);
794 :
795 : // This value is produced on the stack, we never need to spill it.
796 1903003 : if (first_output->IsStackSlot()) {
797 : range->SetSpillOperand(first_output);
798 435810 : range->SetSpillStartIndex(gap_index - 1);
799 : assigned = true;
800 : }
801 1903003 : chunk_->AddGapMove(gap_index, first_output, output_copy);
802 : }
803 :
804 7768311 : 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 14663660 : chunk()->zone());
814 : move->AddMove(first_output, range->GetSpillOperand(),
815 7331827 : chunk()->zone());
816 : }
817 : }
818 :
819 : // Handle fixed input operands of second instruction.
820 26741610 : if (second != NULL) {
821 111592665 : for (UseIterator it(second); !it.Done(); it.Advance()) {
822 29450357 : LUnallocated* cur_input = LUnallocated::cast(it.Current());
823 29450712 : if (cur_input->HasFixedPolicy()) {
824 : LUnallocated* input_copy = cur_input->CopyUnconstrained(
825 11824508 : chunk()->zone());
826 5912252 : bool is_tagged = HasTaggedValue(cur_input->virtual_register());
827 5912252 : AllocateFixed(cur_input, gap_index + 1, is_tagged);
828 5912259 : AddConstraintsGapMove(gap_index, input_copy, cur_input);
829 23538458 : } 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 264972 : chunk()->zone());
836 : int vreg = GetVirtualRegister();
837 26873870 : if (!AllocationOk()) return;
838 132486 : cur_input->set_virtual_register(vreg);
839 :
840 132486 : 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 132486 : AddConstraintsGapMove(gap_index, input_copy, cur_input);
848 : }
849 : }
850 : }
851 :
852 : // Handle "output same as input" for second instruction.
853 26741500 : if (second != NULL && second->Output() != NULL) {
854 7767620 : LUnallocated* second_output = LUnallocated::cast(second->Output());
855 7767589 : 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 704886 : chunk()->zone());
862 : cur_input->set_virtual_register(second_output->virtual_register());
863 352442 : AddConstraintsGapMove(gap_index, input_copy, cur_input);
864 :
865 352443 : if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) {
866 93594 : int index = gap_index + 1;
867 : LInstruction* instr = InstructionAt(index);
868 93594 : 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 178901209 : 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 4493665 : LifetimePosition::FromInstructionIndex(block_start);
890 :
891 53480258 : while (index >= block_start) {
892 : LifetimePosition curr_position =
893 : LifetimePosition::FromInstructionIndex(index);
894 :
895 44493154 : if (IsGapAt(index)) {
896 : // We have a gap at this position.
897 : LGap* gap = GapAt(index);
898 : LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START,
899 53481502 : chunk()->zone());
900 : const ZoneList<LMoveOperands>* move_operands = move->move_operands();
901 71908154 : for (int i = 0; i < move_operands->length(); ++i) {
902 54081153 : LMoveOperands* cur = &move_operands->at(i);
903 9213509 : if (cur->IsIgnored()) continue;
904 : LOperand* from = cur->source();
905 : LOperand* to = cur->destination();
906 8913567 : HPhi* phi = LookupPhi(to);
907 : LOperand* hint = to;
908 8913632 : if (phi != NULL) {
909 : // This is a phi resolving move.
910 1226936 : if (!phi->block()->IsLoopHeader()) {
911 410972 : hint = LiveRangeFor(phi->id())->current_hint_operand();
912 : }
913 : } else {
914 8300164 : if (to->IsUnallocated()) {
915 2387918 : if (live->Contains(LUnallocated::cast(to)->virtual_register())) {
916 2148449 : Define(curr_position, to, from);
917 : live->Remove(LUnallocated::cast(to)->virtual_register());
918 : } else {
919 : cur->Eliminate();
920 : continue;
921 : }
922 : } else {
923 5912246 : Define(curr_position, to, from);
924 : }
925 : }
926 8674179 : Use(block_start_position, curr_position, from, hint);
927 8674132 : 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 17752372 : if (instr != NULL) {
936 17754464 : LOperand* output = instr->Output();
937 17754284 : if (output != NULL) {
938 7767566 : if (output->IsUnallocated()) {
939 : live->Remove(LUnallocated::cast(output)->virtual_register());
940 : }
941 7767566 : Define(curr_position, output, NULL);
942 : }
943 :
944 17754497 : if (instr->ClobbersRegisters()) {
945 27074879 : for (int i = 0; i < Register::kNumRegisters; ++i) {
946 54149851 : if (GetRegConfig()->IsAllocatableGeneralCode(i)) {
947 53817753 : if (output == NULL || !output->IsRegister() ||
948 : output->index() != i) {
949 18911669 : LiveRange* range = FixedLiveRangeFor(i);
950 : range->AddUseInterval(curr_position,
951 37823332 : curr_position.InstructionEnd(), zone());
952 : }
953 : }
954 : }
955 : }
956 :
957 35508916 : if (instr->ClobbersDoubleRegisters(isolate())) {
958 26915909 : for (int i = 0; i < DoubleRegister::kMaxNumRegisters; ++i) {
959 53831729 : if (GetRegConfig()->IsAllocatableDoubleCode(i)) {
960 46109263 : if (output == NULL || !output->IsDoubleRegister() ||
961 : output->index() != i) {
962 25230127 : LiveRange* range = FixedDoubleLiveRangeFor(i);
963 : range->AddUseInterval(curr_position,
964 50460150 : curr_position.InstructionEnd(), zone());
965 : }
966 : }
967 : }
968 : }
969 :
970 94700938 : for (UseIterator it(instr); !it.Done(); it.Advance()) {
971 29595654 : LOperand* input = it.Current();
972 :
973 : LifetimePosition use_pos;
974 53279853 : if (input->IsUnallocated() &&
975 : LUnallocated::cast(input)->IsUsedAtStart()) {
976 2086568 : use_pos = curr_position;
977 : } else {
978 27509479 : use_pos = curr_position.InstructionEnd();
979 : }
980 :
981 29596047 : Use(block_start_position, use_pos, input, NULL);
982 29596352 : if (input->IsUnallocated()) {
983 : live->Add(LUnallocated::cast(input)->virtual_register());
984 : }
985 : }
986 :
987 35705996 : for (TempIterator it(instr); !it.Done(); it.Advance()) {
988 197064 : LOperand* temp = it.Current();
989 197065 : 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 197065 : Use(block_start_position, curr_position.InstructionEnd(), temp, NULL);
999 197062 : Define(curr_position, temp, NULL);
1000 :
1001 197065 : if (temp->IsUnallocated()) {
1002 : LUnallocated* temp_unalloc = LUnallocated::cast(temp);
1003 130016 : 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 44492928 : index = index - 1;
1014 : }
1015 4493527 : }
1016 :
1017 :
1018 6150916 : void LAllocator::ResolvePhis(HBasicBlock* block) {
1019 : const ZoneList<HPhi*>* phis = block->phis();
1020 9587056 : for (int i = 0; i < phis->length(); ++i) {
1021 5093478 : HPhi* phi = phis->at(i);
1022 : LUnallocated* phi_operand =
1023 299950 : new (chunk()->zone()) LUnallocated(LUnallocated::NONE);
1024 1199803 : phi_operand->set_virtual_register(phi->id());
1025 1826840 : for (int j = 0; j < phi->OperandCount(); ++j) {
1026 443968 : HValue* op = phi->OperandAt(j);
1027 : LOperand* operand = NULL;
1028 613471 : if (op->IsConstant() && op->EmitAtUses()) {
1029 : HConstant* constant = HConstant::cast(op);
1030 169502 : operand = chunk_->DefineConstantOperand(constant);
1031 : } else {
1032 : DCHECK(!op->EmitAtUses());
1033 : LUnallocated* unalloc =
1034 443969 : new(chunk()->zone()) LUnallocated(LUnallocated::ANY);
1035 443968 : unalloc->set_virtual_register(op->id());
1036 : operand = unalloc;
1037 : }
1038 1226939 : 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 613470 : 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 613469 : 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 599902 : LiveRange* live_range = LiveRangeFor(phi->id());
1065 299950 : LLabel* label = chunk_->GetLabel(phi->block()->block_id());
1066 : label->GetOrCreateParallelMove(LGap::START, chunk()->zone())->
1067 599902 : AddMove(phi_operand, live_range->GetSpillOperand(), chunk()->zone());
1068 299951 : live_range->SetSpillStartIndex(phi->block()->first_instruction_index());
1069 : }
1070 4493578 : }
1071 :
1072 :
1073 1699168 : bool LAllocator::Allocate(LChunk* chunk) {
1074 : DCHECK(chunk_ == NULL);
1075 283194 : chunk_ = static_cast<LPlatformChunk*>(chunk);
1076 : assigned_registers_ =
1077 283194 : new (chunk->zone()) BitVector(Register::kNumRegisters, chunk->zone());
1078 : assigned_double_registers_ = new (chunk->zone())
1079 283195 : BitVector(DoubleRegister::kMaxNumRegisters, chunk->zone());
1080 283196 : MeetRegisterConstraints();
1081 283195 : if (!AllocationOk()) return false;
1082 283195 : ResolvePhis();
1083 283197 : BuildLiveRanges();
1084 283196 : AllocateGeneralRegisters();
1085 283195 : if (!AllocationOk()) return false;
1086 283194 : AllocateDoubleRegisters();
1087 283196 : if (!AllocationOk()) return false;
1088 283196 : PopulatePointerMaps();
1089 283195 : ConnectRanges();
1090 283196 : ResolveControlFlow();
1091 283196 : return true;
1092 : }
1093 :
1094 :
1095 4776749 : void LAllocator::MeetRegisterConstraints() {
1096 283196 : LAllocatorPhase phase("L_Register constraints", this);
1097 283199 : const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1098 9553504 : for (int i = 0; i < blocks->length(); ++i) {
1099 9270307 : HBasicBlock* block = blocks->at(i);
1100 4493555 : MeetRegisterConstraints(block);
1101 4493553 : if (!AllocationOk()) return;
1102 283197 : }
1103 : }
1104 :
1105 :
1106 283194 : void LAllocator::ResolvePhis() {
1107 283194 : LAllocatorPhase phase("L_Resolve phis", this);
1108 :
1109 : // Process the blocks in reverse order.
1110 283196 : const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1111 4776777 : for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) {
1112 4493580 : HBasicBlock* block = blocks->at(block_id);
1113 4493580 : ResolvePhis(block);
1114 283197 : }
1115 283197 : }
1116 :
1117 :
1118 16285529 : void LAllocator::ResolveControlFlow(LiveRange* range,
1119 16331326 : HBasicBlock* block,
1120 17324585 : 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 16285529 : LiveRange* cur_cover = NULL;
1127 56817550 : LiveRange* cur_range = range;
1128 89388608 : while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) {
1129 56817550 : if (cur_range->CanCover(cur_start)) {
1130 : DCHECK(cur_cover == NULL);
1131 : cur_cover = cur_range;
1132 : }
1133 56817550 : 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 32571059 : if (cur_cover->IsSpilled()) return;
1141 : DCHECK(pred_cover != NULL && cur_cover != NULL);
1142 3022426 : if (pred_cover != cur_cover) {
1143 524246 : LOperand* pred_op = pred_cover->CreateAssignedOperand(chunk()->zone());
1144 524246 : LOperand* cur_op = cur_cover->CreateAssignedOperand(chunk()->zone());
1145 262123 : if (!pred_op->Equals(cur_op)) {
1146 : LGap* gap = NULL;
1147 257404 : if (block->predecessors()->length() == 1) {
1148 : gap = GapAt(block->first_instruction_index());
1149 : } else {
1150 : DCHECK(pred->end()->SecondSuccessor() == NULL);
1151 211607 : 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 211608 : 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 514810 : chunk()->zone());
1174 : }
1175 : }
1176 : }
1177 :
1178 :
1179 1808846 : LParallelMove* LAllocator::GetConnectingParallelMove(LifetimePosition pos) {
1180 : int index = pos.InstructionIndex();
1181 452278 : if (IsGapAt(index)) {
1182 : LGap* gap = GapAt(index);
1183 : return gap->GetOrCreateParallelMove(
1184 904032 : pos.IsInstructionStart() ? LGap::START : LGap::END, chunk()->zone());
1185 : }
1186 263 : int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1);
1187 : return GapAt(gap_pos)->GetOrCreateParallelMove(
1188 789 : (gap_pos < index) ? LGap::AFTER : LGap::BEFORE, chunk()->zone());
1189 : }
1190 :
1191 :
1192 2117571 : HBasicBlock* LAllocator::GetBlock(LifetimePosition pos) {
1193 2117576 : LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex()));
1194 1058790 : return gap->block();
1195 : }
1196 :
1197 :
1198 1640037 : void LAllocator::ConnectRanges() {
1199 283194 : LAllocatorPhase phase("L_Connect ranges", this);
1200 34727490 : for (int i = 0; i < live_ranges()->length(); ++i) {
1201 49493030 : LiveRange* first_range = live_ranges()->at(i);
1202 42570064 : if (first_range == NULL || first_range->parent() != NULL) continue;
1203 :
1204 3368501 : LiveRange* second_range = first_range->next();
1205 14567288 : while (second_range != NULL) {
1206 : LifetimePosition pos = second_range->Start();
1207 :
1208 1684259 : if (!second_range->IsSpilled()) {
1209 : // Add gap move if the two live ranges touch and there is no block
1210 : // boundary.
1211 481443 : if (first_range->End().Value() == pos.Value()) {
1212 : bool should_insert = true;
1213 481342 : if (IsBlockBoundary(pos)) {
1214 29044 : should_insert = CanEagerlyResolveControlFlow(GetBlock(pos));
1215 : }
1216 481325 : if (should_insert) {
1217 452280 : LParallelMove* move = GetConnectingParallelMove(pos);
1218 : LOperand* prev_operand = first_range->CreateAssignedOperand(
1219 904562 : chunk()->zone());
1220 : LOperand* cur_operand = second_range->CreateAssignedOperand(
1221 904562 : chunk()->zone());
1222 : move->AddMove(prev_operand, cur_operand,
1223 452281 : chunk()->zone());
1224 : }
1225 : }
1226 : }
1227 :
1228 : first_range = second_range;
1229 : second_range = second_range->next();
1230 : }
1231 283196 : }
1232 283196 : }
1233 :
1234 :
1235 3766781 : bool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const {
1236 4239428 : if (block->predecessors()->length() != 1) return false;
1237 7533562 : return block->predecessors()->first()->block_id() == block->block_id() - 1;
1238 : }
1239 :
1240 :
1241 283192 : void LAllocator::ResolveControlFlow() {
1242 283192 : LAllocatorPhase phase("L_Resolve control flow", this);
1243 283199 : const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1244 8987158 : for (int block_id = 1; block_id < blocks->length(); ++block_id) {
1245 10123277 : HBasicBlock* block = blocks->at(block_id);
1246 7001451 : if (CanEagerlyResolveControlFlow(block)) continue;
1247 2838630 : BitVector* live = live_in_sets_[block->block_id()];
1248 : BitVector::Iterator iterator(live);
1249 23091550 : while (!iterator.Done()) {
1250 10126463 : int operand_index = iterator.Current();
1251 26411989 : for (int i = 0; i < block->predecessors()->length(); ++i) {
1252 16285526 : HBasicBlock* cur = block->predecessors()->at(i);
1253 16285526 : LiveRange* cur_range = LiveRangeFor(operand_index);
1254 16285528 : ResolveControlFlow(cur_range, block, cur);
1255 : }
1256 10126463 : iterator.Advance();
1257 : }
1258 283196 : }
1259 283196 : }
1260 :
1261 :
1262 583147 : void LAllocator::BuildLiveRanges() {
1263 283196 : LAllocatorPhase phase("L_Build live ranges", this);
1264 283196 : InitializeLivenessAnalysis();
1265 : // Process the blocks in reverse order.
1266 283223 : const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1267 4776748 : for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) {
1268 4912968 : HBasicBlock* block = blocks->at(block_id);
1269 4793482 : 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 4493537 : AddInitialIntervals(block, live);
1273 :
1274 : // Process the instructions in reverse order, generating and killing
1275 : // live values.
1276 4493564 : ProcessInstructions(block, live);
1277 : // All phi output operands are killed by this block.
1278 : const ZoneList<HPhi*>* phis = block->phis();
1279 9586952 : for (int i = 0; i < phis->length(); ++i) {
1280 : // The live range interval already ends at the first instruction of the
1281 : // block.
1282 5093427 : HPhi* phi = phis->at(i);
1283 1196025 : live->Remove(phi->id());
1284 :
1285 : LOperand* hint = NULL;
1286 : LOperand* phi_operand = NULL;
1287 299951 : LGap* gap = GetLastGap(phi->block()->predecessors()->at(0));
1288 : LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START,
1289 599902 : chunk()->zone());
1290 596123 : for (int j = 0; j < move->move_operands()->length(); ++j) {
1291 596123 : LOperand* to = move->move_operands()->at(j).destination();
1292 1192246 : if (to->IsUnallocated() &&
1293 : LUnallocated::cast(to)->virtual_register() == phi->id()) {
1294 299951 : hint = move->move_operands()->at(j).source();
1295 : phi_operand = to;
1296 299951 : break;
1297 : }
1298 : }
1299 : DCHECK(hint != NULL);
1300 :
1301 : LifetimePosition block_start = LifetimePosition::FromInstructionIndex(
1302 299951 : block->first_instruction_index());
1303 299951 : 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 9954993 : 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 4493525 : 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 1147172 : HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge();
1318 : BitVector::Iterator iterator(live);
1319 : LifetimePosition start = LifetimePosition::FromInstructionIndex(
1320 59743 : block->first_instruction_index());
1321 : LifetimePosition end = LifetimePosition::FromInstructionIndex(
1322 59743 : back_edge->last_instruction_index()).NextInstruction();
1323 997413 : while (!iterator.Done()) {
1324 409092 : int operand_index = iterator.Current();
1325 409092 : LiveRange* range = LiveRangeFor(operand_index);
1326 409092 : range->EnsureInterval(start, end, zone());
1327 409092 : iterator.Advance();
1328 : }
1329 :
1330 2055372 : for (int i = block->block_id() + 1; i <= back_edge->block_id(); ++i) {
1331 967943 : 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 64619073 : for (int i = 0; i < live_ranges_.length(); ++i) {
1357 96787043 : if (live_ranges_[i] != NULL) {
1358 6441518 : live_ranges_[i]->kind_ = RequiredRegisterKind(live_ranges_[i]->id());
1359 : }
1360 283196 : }
1361 283195 : }
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 9425883 : void LAllocator::PopulatePointerMaps() {
1377 283196 : LAllocatorPhase phase("L_Populate pointer maps", this);
1378 283196 : 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 34727302 : for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) {
1387 75391508 : LiveRange* range = live_ranges()->at(range_idx);
1388 34444105 : if (range == NULL) continue;
1389 : // Iterate over the first parts of multi-part live ranges.
1390 8125755 : if (range->parent() != NULL) continue;
1391 : // Skip non-pointer values.
1392 6441568 : if (!HasTaggedValue(range->id())) continue;
1393 : // Skip empty live ranges.
1394 4348267 : 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 9656168 : for (LiveRange* cur = range; cur != NULL; cur = cur->next()) {
1400 : LifetimePosition this_end = cur->End();
1401 5547106 : 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 4109062 : 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 27398631 : while (first_safe_point_index < pointer_maps->length()) {
1416 66797153 : LPointerMap* map = pointer_maps->at(first_safe_point_index);
1417 : int safe_point = map->lithium_position();
1418 22832938 : if (safe_point >= start) break;
1419 19180507 : first_safe_point_index++;
1420 : }
1421 :
1422 : // Step through the safe points to see whether they are in the range.
1423 37240230 : for (int safe_point_index = first_safe_point_index;
1424 : safe_point_index < pointer_maps->length();
1425 : ++safe_point_index) {
1426 19160308 : 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 19160308 : 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 16565526 : LifetimePosition::FromInstructionIndex(safe_point);
1436 39216033 : LiveRange* cur = range;
1437 63284348 : while (cur != NULL && !cur->Covers(safe_point_pos)) {
1438 : cur = cur->next();
1439 : }
1440 24244111 : if (cur == NULL) continue;
1441 :
1442 : // Check if the live range is spilled and the safe point is after
1443 : // the spill position.
1444 17684391 : 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 8791419 : range->id(), range->spill_start_index(), safe_point);
1448 17582830 : map->RecordPointer(range->GetSpillOperand(), chunk()->zone());
1449 : }
1450 :
1451 8887101 : if (!cur->IsSpilled()) {
1452 : TraceAlloc("Pointer in register for range %d (start at %d) "
1453 : "at safe point %d\n",
1454 175636 : cur->id(), cur->Start().Value(), safe_point);
1455 351272 : LOperand* operand = cur->CreateAssignedOperand(chunk()->zone());
1456 : DCHECK(!operand->IsStackSlot());
1457 351272 : map->RecordPointer(operand, chunk()->zone());
1458 : }
1459 : }
1460 283197 : }
1461 283195 : }
1462 :
1463 :
1464 283195 : void LAllocator::AllocateGeneralRegisters() {
1465 283195 : LAllocatorPhase phase("L_Allocate general registers", this);
1466 283195 : num_registers_ = GetRegConfig()->num_allocatable_general_registers();
1467 283196 : allocatable_register_codes_ = GetRegConfig()->allocatable_general_codes();
1468 283197 : mode_ = GENERAL_REGISTERS;
1469 283197 : AllocateRegisters();
1470 283195 : }
1471 :
1472 :
1473 283194 : void LAllocator::AllocateDoubleRegisters() {
1474 283194 : LAllocatorPhase phase("L_Allocate double registers", this);
1475 283196 : num_registers_ = GetRegConfig()->num_allocatable_double_registers();
1476 283195 : allocatable_register_codes_ = GetRegConfig()->allocatable_double_codes();
1477 283195 : mode_ = DOUBLE_REGISTERS;
1478 283195 : AllocateRegisters();
1479 283196 : }
1480 :
1481 :
1482 15931256 : void LAllocator::AllocateRegisters() {
1483 : DCHECK(unhandled_live_ranges_.is_empty());
1484 :
1485 134136392 : for (int i = 0; i < live_ranges_.length(); ++i) {
1486 200071806 : if (live_ranges_[i] != NULL) {
1487 14457177 : if (live_ranges_[i]->Kind() == mode_) {
1488 6441473 : AddToUnhandledUnsorted(live_ranges_[i]);
1489 : }
1490 : }
1491 : }
1492 566391 : 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 566402 : if (mode_ == DOUBLE_REGISTERS) {
1500 9345398 : for (int i = 0; i < fixed_double_live_ranges_.length(); ++i) {
1501 9345401 : LiveRange* current = fixed_double_live_ranges_.at(i);
1502 4531105 : if (current != NULL) {
1503 3915197 : AddToInactive(current);
1504 : }
1505 : }
1506 : } else {
1507 : DCHECK(mode_ == GENERAL_REGISTERS);
1508 9345402 : for (int i = 0; i < fixed_live_ranges_.length(); ++i) {
1509 9345405 : LiveRange* current = fixed_live_ranges_.at(i);
1510 4531100 : if (current != NULL) {
1511 3217845 : AddToInactive(current);
1512 : }
1513 : }
1514 : }
1515 :
1516 8399315 : while (!unhandled_live_ranges_.is_empty()) {
1517 : DCHECK(UnhandledIsSorted());
1518 31898101 : 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 7832928 : position.Value());
1527 :
1528 7833512 : if (current->HasAllocatedSpillOperand()) {
1529 435812 : TraceAlloc("Live range %d already has a spill operand\n", current->id());
1530 : LifetimePosition next_pos = position;
1531 435810 : if (IsGapAt(next_pos.InstructionIndex())) {
1532 : next_pos = next_pos.NextInstruction();
1533 : }
1534 435810 : 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 435812 : if (pos == NULL) {
1538 301156 : Spill(current);
1539 301156 : continue;
1540 134656 : } 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 134655 : if (!AllocationOk()) return;
1546 : DCHECK(UnhandledIsSorted());
1547 : continue;
1548 : }
1549 : }
1550 :
1551 65979554 : for (int i = 0; i < active_live_ranges_.length(); ++i) {
1552 65979429 : LiveRange* cur_active = active_live_ranges_.at(i);
1553 29290802 : if (cur_active->End().Value() <= position.Value()) {
1554 6928791 : ActiveToHandled(cur_active);
1555 6928889 : --i; // The live range was removed from the list of active live ranges.
1556 22362011 : } else if (!cur_active->Covers(position)) {
1557 9341377 : ActiveToInactive(cur_active);
1558 9341403 : --i; // The live range was removed from the list of active live ranges.
1559 : }
1560 : }
1561 :
1562 215590095 : for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
1563 215590639 : LiveRange* cur_inactive = inactive_live_ranges_.at(i);
1564 104096679 : if (cur_inactive->End().Value() <= position.Value()) {
1565 2134861 : InactiveToHandled(cur_inactive);
1566 2135055 : --i; // Live range was removed from the list of inactive live ranges.
1567 101961818 : } else if (cur_inactive->Covers(position)) {
1568 10561063 : InactiveToActive(cur_inactive);
1569 10561097 : --i; // Live range was removed from the list of inactive live ranges.
1570 : }
1571 : }
1572 :
1573 : DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled());
1574 :
1575 7397281 : bool result = TryAllocateFreeReg(current);
1576 7397173 : if (!AllocationOk()) return;
1577 :
1578 7397177 : if (!result) AllocateBlockedReg(current);
1579 7397122 : if (!AllocationOk()) return;
1580 :
1581 7397122 : if (current->HasRegisterAssigned()) {
1582 6242612 : 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 11163485 : const char* LAllocator::RegisterName(int allocation_index) {
1593 11163485 : if (mode_ == GENERAL_REGISTERS) {
1594 21546025 : return GetRegConfig()->GetGeneralRegisterName(allocation_index);
1595 : } else {
1596 780946 : return GetRegConfig()->GetDoubleRegisterName(allocation_index);
1597 : }
1598 : }
1599 :
1600 :
1601 262101707 : void LAllocator::TraceAlloc(const char* msg, ...) {
1602 262101707 : 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 262101707 : }
1609 :
1610 :
1611 14707410 : bool LAllocator::HasTaggedValue(int virtual_register) const {
1612 14707410 : HValue* value = graph_->LookupValue(virtual_register);
1613 14707410 : if (value == NULL) return false;
1614 25987372 : return value->representation().IsTagged() && !value->type().IsSmi();
1615 : }
1616 :
1617 :
1618 6573984 : RegisterKind LAllocator::RequiredRegisterKind(int virtual_register) const {
1619 6573984 : if (virtual_register < first_artificial_register_) {
1620 6311482 : HValue* value = graph_->LookupValue(virtual_register);
1621 6311482 : if (value != NULL && value->representation().IsDouble()) {
1622 : return DOUBLE_REGISTERS;
1623 : }
1624 262502 : } else if (double_artificial_registers_.Contains(
1625 262502 : virtual_register - first_artificial_register_)) {
1626 : return DOUBLE_REGISTERS;
1627 : }
1628 :
1629 : return GENERAL_REGISTERS;
1630 : }
1631 :
1632 :
1633 6242618 : void LAllocator::AddToActive(LiveRange* range) {
1634 6242618 : TraceAlloc("Add live range %d to active\n", range->id());
1635 6242638 : active_live_ranges_.Add(range, zone());
1636 6242628 : }
1637 :
1638 :
1639 7133005 : void LAllocator::AddToInactive(LiveRange* range) {
1640 7133005 : TraceAlloc("Add live range %d to inactive\n", range->id());
1641 7132999 : inactive_live_ranges_.Add(range, zone());
1642 7133005 : }
1643 :
1644 :
1645 1631105 : void LAllocator::AddToUnhandledSorted(LiveRange* range) {
1646 4893270 : if (range == NULL || range->IsEmpty()) return;
1647 : DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
1648 : DCHECK(allocation_finger_.Value() <= range->Start().Value());
1649 20398058 : for (int i = unhandled_live_ranges_.length() - 1; i >= 0; --i) {
1650 20390390 : LiveRange* cur_range = unhandled_live_ranges_.at(i);
1651 20390390 : if (range->ShouldBeAllocatedBefore(cur_range)) {
1652 3246782 : TraceAlloc("Add live range %d to unhandled at %d\n", range->id(), i + 1);
1653 1623436 : unhandled_live_ranges_.InsertAt(i + 1, range, zone());
1654 : DCHECK(UnhandledIsSorted());
1655 : return;
1656 : }
1657 : }
1658 7668 : TraceAlloc("Add live range %d to unhandled at start\n", range->id());
1659 7668 : unhandled_live_ranges_.InsertAt(0, range, zone());
1660 : DCHECK(UnhandledIsSorted());
1661 : }
1662 :
1663 :
1664 6441469 : void LAllocator::AddToUnhandledUnsorted(LiveRange* range) {
1665 19324398 : if (range == NULL || range->IsEmpty()) return;
1666 : DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled());
1667 6202008 : TraceAlloc("Add live range %d to unhandled unsorted at end\n", range->id());
1668 6201998 : unhandled_live_ranges_.Add(range, zone());
1669 : }
1670 :
1671 :
1672 45555863 : static int UnhandledSortHelper(LiveRange* const* a, LiveRange* const* b) {
1673 : DCHECK(!(*a)->ShouldBeAllocatedBefore(*b) ||
1674 : !(*b)->ShouldBeAllocatedBefore(*a));
1675 91461168 : if ((*a)->ShouldBeAllocatedBefore(*b)) return 1;
1676 29973749 : if ((*b)->ShouldBeAllocatedBefore(*a)) return -1;
1677 349442 : 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 566390 : void LAllocator::SortUnhandled() {
1685 566390 : TraceAlloc("Sort unhandled\n");
1686 : unhandled_live_ranges_.Sort(&UnhandledSortHelper);
1687 566391 : }
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 9118104 : void LAllocator::FreeSpillSlot(LiveRange* range) {
1702 : // Check that we are the last range.
1703 9118104 : if (range->next() != NULL) return;
1704 :
1705 7924508 : if (!range->TopLevel()->HasAllocatedSpillOperand()) return;
1706 :
1707 93577 : int index = range->TopLevel()->GetSpillOperand()->index();
1708 93577 : if (index >= 0) {
1709 58738 : reusable_slots_.Add(range, zone());
1710 : }
1711 : }
1712 :
1713 :
1714 814968 : LOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) {
1715 814968 : if (reusable_slots_.is_empty()) return NULL;
1716 38418 : if (reusable_slots_.first()->End().Value() >
1717 : range->TopLevel()->Start().Value()) {
1718 : return NULL;
1719 : }
1720 17264 : LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand();
1721 17264 : reusable_slots_.Remove(0);
1722 17264 : return result;
1723 : }
1724 :
1725 :
1726 6982696 : void LAllocator::ActiveToHandled(LiveRange* range) {
1727 : DCHECK(active_live_ranges_.Contains(range));
1728 6982696 : active_live_ranges_.RemoveElement(range);
1729 6982722 : TraceAlloc("Moving live range %d from active to handled\n", range->id());
1730 6982719 : FreeSpillSlot(range);
1731 6982716 : }
1732 :
1733 :
1734 9341370 : void LAllocator::ActiveToInactive(LiveRange* range) {
1735 : DCHECK(active_live_ranges_.Contains(range));
1736 9341370 : active_live_ranges_.RemoveElement(range);
1737 9341408 : inactive_live_ranges_.Add(range, zone());
1738 9341414 : TraceAlloc("Moving live range %d from active to inactive\n", range->id());
1739 9341401 : }
1740 :
1741 :
1742 2135429 : void LAllocator::InactiveToHandled(LiveRange* range) {
1743 : DCHECK(inactive_live_ranges_.Contains(range));
1744 2135429 : inactive_live_ranges_.RemoveElement(range);
1745 2135429 : TraceAlloc("Moving live range %d from inactive to handled\n", range->id());
1746 2135427 : FreeSpillSlot(range);
1747 2135429 : }
1748 :
1749 :
1750 10561050 : void LAllocator::InactiveToActive(LiveRange* range) {
1751 : DCHECK(inactive_live_ranges_.Contains(range));
1752 10561050 : inactive_live_ranges_.RemoveElement(range);
1753 10561096 : active_live_ranges_.Add(range, zone());
1754 10561093 : TraceAlloc("Moving live range %d from inactive to active\n", range->id());
1755 10561092 : }
1756 :
1757 :
1758 35182202 : bool LAllocator::TryAllocateFreeReg(LiveRange* current) {
1759 : DCHECK(DoubleRegister::kMaxNumRegisters >= Register::kNumRegisters);
1760 :
1761 125753988 : LifetimePosition free_until_pos[DoubleRegister::kMaxNumRegisters];
1762 :
1763 118356560 : for (int i = 0; i < DoubleRegister::kMaxNumRegisters; i++) {
1764 118356560 : free_until_pos[i] = LifetimePosition::MaxPosition();
1765 : }
1766 :
1767 54561818 : for (int i = 0; i < active_live_ranges_.length(); ++i) {
1768 54561818 : LiveRange* cur_active = active_live_ranges_.at(i);
1769 : free_until_pos[cur_active->assigned_register()] =
1770 23582211 : LifetimePosition::FromInstructionIndex(0);
1771 : }
1772 :
1773 190201700 : for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
1774 209736615 : LiveRange* cur_inactive = inactive_live_ranges_.at(i);
1775 : DCHECK(cur_inactive->End().Value() > current->Start().Value());
1776 : LifetimePosition next_intersection =
1777 91402296 : cur_inactive->FirstIntersection(current);
1778 163269533 : if (!next_intersection.IsValid()) continue;
1779 : int cur_reg = cur_inactive->assigned_register();
1780 19534771 : free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection);
1781 : }
1782 :
1783 7397252 : LOperand* hint = current->FirstHint();
1784 12582497 : 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 9841944 : current->End().Value());
1792 :
1793 : // The desired register is free until the end of the current live range.
1794 4920959 : 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 2976201 : current->id());
1798 2976202 : SetLiveRangeAssignedRegister(current, register_index);
1799 2976200 : return true;
1800 : }
1801 : }
1802 :
1803 : // Find the register which stays free for the longest time.
1804 4421073 : int reg = allocatable_register_codes_[0];
1805 108114792 : for (int i = 1; i < RegisterCount(); ++i) {
1806 49636323 : int code = allocatable_register_codes_[i];
1807 148908969 : if (free_until_pos[code].Value() > free_until_pos[reg].Value()) {
1808 : reg = code;
1809 : }
1810 : }
1811 :
1812 4421073 : LifetimePosition pos = free_until_pos[reg];
1813 :
1814 4421073 : if (pos.Value() <= current->Start().Value()) {
1815 : // All registers are blocked.
1816 : return false;
1817 : }
1818 :
1819 3213298 : 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 1142829 : LiveRange* tail = SplitRangeAt(current, pos);
1823 1142829 : if (!AllocationOk()) return false;
1824 1142828 : 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 3213295 : current->id());
1834 3213289 : SetLiveRangeAssignedRegister(current, reg);
1835 :
1836 3213285 : return true;
1837 : }
1838 :
1839 :
1840 1315851 : void LAllocator::AllocateBlockedReg(LiveRange* current) {
1841 1207798 : UsePosition* register_use = current->NextRegisterPosition(current->Start());
1842 1207801 : 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 840737 : Spill(current);
1846 840743 : return;
1847 : }
1848 :
1849 :
1850 5872992 : LifetimePosition use_pos[DoubleRegister::kMaxNumRegisters];
1851 5872992 : LifetimePosition block_pos[DoubleRegister::kMaxNumRegisters];
1852 :
1853 5872976 : for (int i = 0; i < DoubleRegister::kMaxNumRegisters; i++) {
1854 5872976 : use_pos[i] = block_pos[i] = LifetimePosition::MaxPosition();
1855 : }
1856 :
1857 9491738 : for (int i = 0; i < active_live_ranges_.length(); ++i) {
1858 14241252 : LiveRange* range = active_live_ranges_[i];
1859 : int cur_reg = range->assigned_register();
1860 5389069 : if (range->IsFixed() || !range->CanBeSpilled(current->Start())) {
1861 : block_pos[cur_reg] = use_pos[cur_reg] =
1862 3784261 : LifetimePosition::FromInstructionIndex(0);
1863 : } else {
1864 : UsePosition* next_use = range->NextUsePositionRegisterIsBeneficial(
1865 778076 : current->Start());
1866 778076 : if (next_use == NULL) {
1867 187171 : use_pos[cur_reg] = range->End();
1868 : } else {
1869 590905 : use_pos[cur_reg] = next_use->pos();
1870 : }
1871 : }
1872 : }
1873 :
1874 3435817 : for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
1875 4435757 : LiveRange* range = inactive_live_ranges_.at(i);
1876 : DCHECK(range->End().Value() > current->Start().Value());
1877 1534378 : LifetimePosition next_intersection = range->FirstIntersection(current);
1878 2068816 : if (!next_intersection.IsValid()) continue;
1879 : int cur_reg = range->assigned_register();
1880 999940 : if (range->IsFixed()) {
1881 48604 : block_pos[cur_reg] = Min(block_pos[cur_reg], next_intersection);
1882 48604 : use_pos[cur_reg] = Min(block_pos[cur_reg], use_pos[cur_reg]);
1883 : } else {
1884 951336 : use_pos[cur_reg] = Min(use_pos[cur_reg], next_intersection);
1885 : }
1886 : }
1887 :
1888 367061 : int reg = allocatable_register_codes_[0];
1889 9124574 : for (int i = 1; i < RegisterCount(); ++i) {
1890 4195226 : int code = allocatable_register_codes_[i];
1891 12585678 : if (use_pos[code].Value() > use_pos[reg].Value()) {
1892 : reg = code;
1893 : }
1894 : }
1895 :
1896 367061 : LifetimePosition pos = use_pos[reg];
1897 :
1898 367061 : 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 106386 : 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 1667 : block_pos[reg].InstructionStart());
1911 1667 : if (!AllocationOk()) return;
1912 1667 : 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 53193 : current->id());
1920 53193 : 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 53193 : SplitAndSpillIntersecting(current);
1926 : }
1927 :
1928 :
1929 53193 : LifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range,
1930 : LifetimePosition pos) {
1931 104480 : HBasicBlock* block = GetBlock(pos.InstructionStart());
1932 31862 : HBasicBlock* loop_header =
1933 53193 : block->IsLoopHeader() ? block : block->parent_loop_header();
1934 :
1935 53193 : if (loop_header == NULL) return pos;
1936 :
1937 : UsePosition* prev_use =
1938 : range->PreviousUsePositionRegisterIsBeneficial(pos);
1939 :
1940 31065 : 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 15931 : if (range->Covers(loop_start)) {
1948 5164 : 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 15134 : return pos;
1959 : }
1960 :
1961 :
1962 106387 : void LAllocator::SplitAndSpillIntersecting(LiveRange* current) {
1963 : DCHECK(current->HasRegisterAssigned());
1964 : int reg = current->assigned_register();
1965 : LifetimePosition split_pos = current->Start();
1966 1561038 : for (int i = 0; i < active_live_ranges_.length(); ++i) {
1967 2235171 : LiveRange* range = active_live_ranges_[i];
1968 727326 : if (range->assigned_register() == reg) {
1969 53193 : UsePosition* next_pos = range->NextRegisterPosition(current->Start());
1970 53193 : LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos);
1971 53193 : if (next_pos == NULL) {
1972 15107 : 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 38086 : SpillBetweenUntil(range, spill_pos, current->Start(), next_pos->pos());
1983 : }
1984 53193 : if (!AllocationOk()) return;
1985 53193 : ActiveToHandled(range);
1986 53193 : --i;
1987 : }
1988 : }
1989 :
1990 216501 : for (int i = 0; i < inactive_live_ranges_.length(); ++i) {
1991 313623 : LiveRange* range = inactive_live_ranges_[i];
1992 : DCHECK(range->End().Value() > current->Start().Value());
1993 97122 : if (range->assigned_register() == reg && !range->IsFixed()) {
1994 394 : LifetimePosition next_intersection = range->FirstIntersection(current);
1995 394 : 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 511800 : bool LAllocator::IsBlockBoundary(LifetimePosition pos) {
2013 511799 : return pos.IsInstructionStart() &&
2014 481323 : InstructionAt(pos.InstructionIndex())->IsLabel();
2015 : }
2016 :
2017 :
2018 3817067 : LiveRange* LAllocator::SplitRangeAt(LiveRange* range, LifetimePosition pos) {
2019 : DCHECK(!range->IsFixed());
2020 2132809 : TraceAlloc("Splitting live range %d at %d\n", range->id(), pos.Value());
2021 :
2022 2132805 : 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 1684258 : if (!AllocationOk()) return NULL;
2031 1684260 : LiveRange* result = LiveRangeFor(vreg);
2032 1684254 : range->SplitAt(pos, result, zone());
2033 1684259 : return result;
2034 : }
2035 :
2036 :
2037 976550 : 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 488275 : end.Value());
2045 :
2046 488274 : LifetimePosition split_pos = FindOptimalSplitPos(start, end);
2047 : DCHECK(split_pos.Value() >= start.Value());
2048 488276 : return SplitRangeAt(range, split_pos);
2049 : }
2050 :
2051 :
2052 488274 : 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 488274 : if (start_instr == end_instr) return end;
2060 :
2061 576852 : HBasicBlock* start_block = GetBlock(start);
2062 488278 : HBasicBlock* end_block = GetBlock(end);
2063 :
2064 488276 : if (end_block == start_block) {
2065 : // The interval is split in the same basic block. Split at the latest
2066 : // possible position.
2067 151069 : return end;
2068 : }
2069 :
2070 406887 : HBasicBlock* block = end_block;
2071 : // Find header of outermost loop.
2072 458692 : while (block->parent_loop_header() != NULL &&
2073 88578 : 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 641948 : if (block == end_block && !end_block->IsLoopHeader()) return end;
2080 :
2081 : return LifetimePosition::FromInstructionIndex(
2082 : block->first_instruction_index());
2083 : }
2084 :
2085 :
2086 30214 : void LAllocator::SpillAfter(LiveRange* range, LifetimePosition pos) {
2087 15107 : LiveRange* second_part = SplitRangeAt(range, pos);
2088 30214 : if (!AllocationOk()) return;
2089 15107 : Spill(second_part);
2090 : }
2091 :
2092 :
2093 0 : void LAllocator::SpillBetween(LiveRange* range,
2094 : LifetimePosition start,
2095 : LifetimePosition end) {
2096 448525 : SpillBetweenUntil(range, start, start, end);
2097 0 : }
2098 :
2099 :
2100 486610 : void LAllocator::SpillBetweenUntil(LiveRange* range,
2101 : LifetimePosition start,
2102 : LifetimePosition until,
2103 973221 : LifetimePosition end) {
2104 486610 : CHECK(start.Value() < end.Value());
2105 486610 : LiveRange* second_part = SplitRangeAt(range, start);
2106 486611 : if (!AllocationOk()) return;
2107 :
2108 486612 : 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 486611 : end.PrevInstruction().InstructionEnd());
2116 486610 : if (!AllocationOk()) return;
2117 :
2118 : DCHECK(third_part != second_part);
2119 :
2120 486610 : Spill(second_part);
2121 486612 : 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 4084919 : void LAllocator::Spill(LiveRange* range) {
2131 : DCHECK(!range->IsSpilled());
2132 1643606 : TraceAlloc("Spilling live range %d\n", range->id());
2133 : LiveRange* first = range->TopLevel();
2134 :
2135 1643609 : if (!first->HasAllocatedSpillOperand()) {
2136 814967 : LOperand* op = TryReuseSpillSlot(range);
2137 1612673 : if (op == NULL) op = chunk_->GetNextSpillSlot(range->Kind());
2138 : first->SetSpillOperand(op);
2139 : }
2140 1643609 : range->MakeSpilled(chunk()->zone());
2141 1643611 : }
2142 :
2143 :
2144 0 : int LAllocator::RegisterCount() const {
2145 58619683 : 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 2265516 : LAllocatorPhase::LAllocatorPhase(const char* name, LAllocator* allocator)
2164 : : CompilationPhase(name, allocator->graph()->info()),
2165 2265516 : allocator_(allocator) {
2166 2265519 : if (FLAG_hydrogen_stats) {
2167 : allocator_zone_start_allocation_size_ =
2168 0 : allocator->zone()->allocation_size();
2169 : }
2170 2265519 : }
2171 :
2172 :
2173 4531085 : LAllocatorPhase::~LAllocatorPhase() {
2174 2265545 : 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 2265545 : 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 2265536 : }
2189 :
2190 :
2191 : } // namespace internal
2192 : } // namespace v8
|
