1// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/compiler/backend/linearscan.h"
6
7#include "vm/bit_vector.h"
8#include "vm/compiler/backend/flow_graph.h"
9#include "vm/compiler/backend/flow_graph_compiler.h"
10#include "vm/compiler/backend/il.h"
11#include "vm/compiler/backend/il_printer.h"
12#include "vm/compiler/backend/loops.h"
13#include "vm/log.h"
14#include "vm/parser.h"
15#include "vm/stack_frame.h"
16
17namespace dart {
18
19#if !defined(PRODUCT)
20#define INCLUDE_LINEAR_SCAN_TRACING_CODE
21#endif
22
23#if defined(INCLUDE_LINEAR_SCAN_TRACING_CODE)
24#define TRACE_ALLOC(statement) \
25 do { \
26 if (FLAG_trace_ssa_allocator && CompilerState::ShouldTrace()) statement; \
27 } while (0)
28#else
29#define TRACE_ALLOC(statement)
30#endif
31
32static const intptr_t kNoVirtualRegister = -1;
33static const intptr_t kTempVirtualRegister = -2;
34static const intptr_t kIllegalPosition = -1;
35static const intptr_t kMaxPosition = 0x7FFFFFFF;
36static const intptr_t kPairVirtualRegisterOffset = 1;
37
38// Definitions which have pair representations
39// (kPairOfTagged) use two virtual register names.
40// At SSA index allocation time each definition reserves two SSA indexes,
41// the second index is only used for pairs. This function maps from the first
42// SSA index to the second.
43static intptr_t ToSecondPairVreg(intptr_t vreg) {
44 // Map vreg to its pair vreg.
45 ASSERT((vreg == kNoVirtualRegister) || vreg >= 0);
46 return (vreg == kNoVirtualRegister) ? kNoVirtualRegister
47 : (vreg + kPairVirtualRegisterOffset);
48}
49
50static intptr_t MinPosition(intptr_t a, intptr_t b) {
51 return (a < b) ? a : b;
52}
53
54static bool IsInstructionStartPosition(intptr_t pos) {
55 return (pos & 1) == 0;
56}
57
58static bool IsInstructionEndPosition(intptr_t pos) {
59 return (pos & 1) == 1;
60}
61
62static intptr_t ToInstructionStart(intptr_t pos) {
63 return (pos & ~1);
64}
65
66static intptr_t ToInstructionEnd(intptr_t pos) {
67 return (pos | 1);
68}
69
70// Additional information on loops during register allocation.
71struct ExtraLoopInfo : public ZoneAllocated {
72 ExtraLoopInfo(intptr_t s, intptr_t e)
73 : start(s), end(e), backedge_interference(nullptr) {}
74 intptr_t start;
75 intptr_t end;
76 BitVector* backedge_interference;
77};
78
79// Returns extra loop information.
80static ExtraLoopInfo* ComputeExtraLoopInfo(Zone* zone, LoopInfo* loop_info) {
81 intptr_t start = loop_info->header()->start_pos();
82 intptr_t end = start;
83 for (auto back_edge : loop_info->back_edges()) {
84 intptr_t end_pos = back_edge->end_pos();
85 if (end_pos > end) {
86 end = end_pos;
87 }
88 }
89 return new (zone) ExtraLoopInfo(start, end);
90}
91
92FlowGraphAllocator::FlowGraphAllocator(const FlowGraph& flow_graph,
93 bool intrinsic_mode)
94 : flow_graph_(flow_graph),
95 reaching_defs_(flow_graph),
96 value_representations_(flow_graph.max_virtual_register_number()),
97 block_order_(flow_graph.reverse_postorder()),
98 postorder_(flow_graph.postorder()),
99 instructions_(),
100 block_entries_(),
101 extra_loop_info_(),
102 liveness_(flow_graph),
103 vreg_count_(flow_graph.max_virtual_register_number()),
104 live_ranges_(flow_graph.max_virtual_register_number()),
105 unallocated_cpu_(),
106 unallocated_xmm_(),
107 cpu_regs_(),
108 fpu_regs_(),
109 blocked_cpu_registers_(),
110 blocked_fpu_registers_(),
111 spilled_(),
112 safepoints_(),
113 register_kind_(),
114 number_of_registers_(0),
115 registers_(),
116 blocked_registers_(),
117 unallocated_(),
118 spill_slots_(),
119 quad_spill_slots_(),
120 untagged_spill_slots_(),
121 cpu_spill_slot_count_(0),
122 intrinsic_mode_(intrinsic_mode) {
123 for (intptr_t i = 0; i < vreg_count_; i++) {
124 live_ranges_.Add(NULL);
125 }
126 for (intptr_t i = 0; i < vreg_count_; i++) {
127 value_representations_.Add(kNoRepresentation);
128 }
129
130 // All registers are marked as "not blocked" (array initialized to false).
131 // Mark the unavailable ones as "blocked" (true).
132 for (intptr_t i = 0; i < kNumberOfCpuRegisters; i++) {
133 if ((kDartAvailableCpuRegs & (1 << i)) == 0) {
134 blocked_cpu_registers_[i] = true;
135 }
136 }
137
138 // FpuTMP is used as scratch by optimized code and parallel move resolver.
139 blocked_fpu_registers_[FpuTMP] = true;
140
141 // Block additional registers needed preserved when generating intrinsics.
142 // TODO(fschneider): Handle saving and restoring these registers when
143 // generating intrinsic code.
144 if (intrinsic_mode) {
145 blocked_cpu_registers_[ARGS_DESC_REG] = true;
146
147#if !defined(TARGET_ARCH_IA32)
148 // Need to preserve CODE_REG to be able to store the PC marker
149 // and load the pool pointer.
150 blocked_cpu_registers_[CODE_REG] = true;
151#endif
152 }
153}
154
155static void DeepLiveness(MaterializeObjectInstr* mat, BitVector* live_in) {
156 if (mat->was_visited_for_liveness()) {
157 return;
158 }
159 mat->mark_visited_for_liveness();
160
161 for (intptr_t i = 0; i < mat->InputCount(); i++) {
162 if (!mat->InputAt(i)->BindsToConstant()) {
163 Definition* defn = mat->InputAt(i)->definition();
164 MaterializeObjectInstr* inner_mat = defn->AsMaterializeObject();
165 if (inner_mat != NULL) {
166 DeepLiveness(inner_mat, live_in);
167 } else {
168 intptr_t idx = defn->ssa_temp_index();
169 live_in->Add(idx);
170 }
171 }
172 }
173}
174
175void SSALivenessAnalysis::ComputeInitialSets() {
176 const intptr_t block_count = postorder_.length();
177 for (intptr_t i = 0; i < block_count; i++) {
178 BlockEntryInstr* block = postorder_[i];
179
180 BitVector* kill = kill_[i];
181 BitVector* live_in = live_in_[i];
182
183 // Iterate backwards starting at the last instruction.
184 for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) {
185 Instruction* current = it.Current();
186
187 // Initialize location summary for instruction.
188 current->InitializeLocationSummary(zone(), true); // opt
189
190 LocationSummary* locs = current->locs();
191#if defined(DEBUG)
192 locs->DiscoverWritableInputs();
193#endif
194
195 // Handle definitions.
196 Definition* current_def = current->AsDefinition();
197 if ((current_def != NULL) && current_def->HasSSATemp()) {
198 kill->Add(current_def->ssa_temp_index());
199 live_in->Remove(current_def->ssa_temp_index());
200 if (current_def->HasPairRepresentation()) {
201 kill->Add(ToSecondPairVreg(current_def->ssa_temp_index()));
202 live_in->Remove(ToSecondPairVreg(current_def->ssa_temp_index()));
203 }
204 }
205
206 // Handle uses.
207 ASSERT(locs->input_count() == current->InputCount());
208 for (intptr_t j = 0; j < current->InputCount(); j++) {
209 Value* input = current->InputAt(j);
210
211 ASSERT(!locs->in(j).IsConstant() || input->BindsToConstant());
212 if (locs->in(j).IsConstant()) continue;
213
214 live_in->Add(input->definition()->ssa_temp_index());
215 if (input->definition()->HasPairRepresentation()) {
216 live_in->Add(ToSecondPairVreg(input->definition()->ssa_temp_index()));
217 }
218 }
219
220 // Add non-argument uses from the deoptimization environment (pushed
221 // arguments are not allocated by the register allocator).
222 if (current->env() != NULL) {
223 for (Environment::DeepIterator env_it(current->env()); !env_it.Done();
224 env_it.Advance()) {
225 Definition* defn = env_it.CurrentValue()->definition();
226 if (defn->IsMaterializeObject()) {
227 // MaterializeObject instruction is not in the graph.
228 // Treat its inputs as part of the environment.
229 DeepLiveness(defn->AsMaterializeObject(), live_in);
230 } else if (!defn->IsPushArgument() && !defn->IsConstant()) {
231 live_in->Add(defn->ssa_temp_index());
232 if (defn->HasPairRepresentation()) {
233 live_in->Add(ToSecondPairVreg(defn->ssa_temp_index()));
234 }
235 }
236 }
237 }
238 }
239
240 // Handle phis.
241 if (block->IsJoinEntry()) {
242 JoinEntryInstr* join = block->AsJoinEntry();
243 for (PhiIterator it(join); !it.Done(); it.Advance()) {
244 PhiInstr* phi = it.Current();
245 ASSERT(phi != NULL);
246 kill->Add(phi->ssa_temp_index());
247 live_in->Remove(phi->ssa_temp_index());
248 if (phi->HasPairRepresentation()) {
249 kill->Add(ToSecondPairVreg(phi->ssa_temp_index()));
250 live_in->Remove(ToSecondPairVreg(phi->ssa_temp_index()));
251 }
252
253 // If a phi input is not defined by the corresponding predecessor it
254 // must be marked live-in for that predecessor.
255 for (intptr_t k = 0; k < phi->InputCount(); k++) {
256 Value* val = phi->InputAt(k);
257 if (val->BindsToConstant()) continue;
258
259 BlockEntryInstr* pred = block->PredecessorAt(k);
260 const intptr_t use = val->definition()->ssa_temp_index();
261 if (!kill_[pred->postorder_number()]->Contains(use)) {
262 live_in_[pred->postorder_number()]->Add(use);
263 }
264 if (phi->HasPairRepresentation()) {
265 const intptr_t second_use = ToSecondPairVreg(use);
266 if (!kill_[pred->postorder_number()]->Contains(second_use)) {
267 live_in_[pred->postorder_number()]->Add(second_use);
268 }
269 }
270 }
271 }
272 } else if (auto entry = block->AsBlockEntryWithInitialDefs()) {
273 // Process initial definitions, i.e. parameters and special parameters.
274 for (intptr_t i = 0; i < entry->initial_definitions()->length(); i++) {
275 Definition* def = (*entry->initial_definitions())[i];
276 const intptr_t vreg = def->ssa_temp_index();
277 kill_[entry->postorder_number()]->Add(vreg);
278 live_in_[entry->postorder_number()]->Remove(vreg);
279 if (def->HasPairRepresentation()) {
280 kill_[entry->postorder_number()]->Add(ToSecondPairVreg((vreg)));
281 live_in_[entry->postorder_number()]->Remove(ToSecondPairVreg(vreg));
282 }
283 }
284 }
285 }
286}
287
288UsePosition* LiveRange::AddUse(intptr_t pos, Location* location_slot) {
289 ASSERT(location_slot != NULL);
290 ASSERT((first_use_interval_->start_ <= pos) &&
291 (pos <= first_use_interval_->end_));
292 if (uses_ != NULL) {
293 if ((uses_->pos() == pos) && (uses_->location_slot() == location_slot)) {
294 return uses_;
295 } else if (uses_->pos() < pos) {
296 // If an instruction at position P is using the same value both as
297 // a fixed register input and a non-fixed input (in this order) we will
298 // add uses both at position P-1 and *then* P which will make
299 // uses_ unsorted unless we account for it here.
300 UsePosition* insert_after = uses_;
301 while ((insert_after->next() != NULL) &&
302 (insert_after->next()->pos() < pos)) {
303 insert_after = insert_after->next();
304 }
305
306 UsePosition* insert_before = insert_after->next();
307 while (insert_before != NULL && (insert_before->pos() == pos)) {
308 if (insert_before->location_slot() == location_slot) {
309 return insert_before;
310 }
311 insert_before = insert_before->next();
312 }
313
314 insert_after->set_next(
315 new UsePosition(pos, insert_after->next(), location_slot));
316 return insert_after->next();
317 }
318 }
319 uses_ = new UsePosition(pos, uses_, location_slot);
320 return uses_;
321}
322
323void LiveRange::AddSafepoint(intptr_t pos, LocationSummary* locs) {
324 ASSERT(IsInstructionStartPosition(pos));
325 SafepointPosition* safepoint =
326 new SafepointPosition(ToInstructionEnd(pos), locs);
327
328 if (first_safepoint_ == NULL) {
329 ASSERT(last_safepoint_ == NULL);
330 first_safepoint_ = last_safepoint_ = safepoint;
331 } else {
332 ASSERT(last_safepoint_ != NULL);
333 // We assume that safepoints list is sorted by position and that
334 // safepoints are added in this order.
335 ASSERT(last_safepoint_->pos() < pos);
336 last_safepoint_->set_next(safepoint);
337 last_safepoint_ = safepoint;
338 }
339}
340
341void LiveRange::AddHintedUse(intptr_t pos,
342 Location* location_slot,
343 Location* hint) {
344 ASSERT(hint != NULL);
345 AddUse(pos, location_slot)->set_hint(hint);
346}
347
348void LiveRange::AddUseInterval(intptr_t start, intptr_t end) {
349 ASSERT(start < end);
350
351 // Live ranges are being build by visiting instructions in post-order.
352 // This implies that use intervals will be prepended in a monotonically
353 // decreasing order.
354 if (first_use_interval() != NULL) {
355 // If the first use interval and the use interval we are adding
356 // touch then we can just extend the first interval to cover their
357 // union.
358 if (start > first_use_interval()->start()) {
359 // The only case when we can add intervals with start greater than
360 // start of an already created interval is BlockLocation.
361 ASSERT(vreg() == kNoVirtualRegister);
362 ASSERT(end <= first_use_interval()->end());
363 return;
364 } else if (start == first_use_interval()->start()) {
365 // Grow first interval if necessary.
366 if (end <= first_use_interval()->end()) return;
367 first_use_interval_->end_ = end;
368 return;
369 } else if (end == first_use_interval()->start()) {
370 first_use_interval()->start_ = start;
371 return;
372 }
373
374 ASSERT(end < first_use_interval()->start());
375 }
376
377 first_use_interval_ = new UseInterval(start, end, first_use_interval_);
378 if (last_use_interval_ == NULL) {
379 ASSERT(first_use_interval_->next() == NULL);
380 last_use_interval_ = first_use_interval_;
381 }
382}
383
384void LiveRange::DefineAt(intptr_t pos) {
385 // Live ranges are being build by visiting instructions in post-order.
386 // This implies that use intervals will be prepended in a monotonically
387 // decreasing order.
388 // When we encounter a use of a value inside a block we optimistically
389 // expand the first use interval to cover the block from the start
390 // to the last use in the block and then we shrink it if we encounter
391 // definition of the value inside the same block.
392 if (first_use_interval_ == NULL) {
393 // Definition without a use.
394 first_use_interval_ = new UseInterval(pos, pos + 1, NULL);
395 last_use_interval_ = first_use_interval_;
396 } else {
397 // Shrink the first use interval. It was optimistically expanded to
398 // cover the block from the start to the last use in the block.
399 ASSERT(first_use_interval_->start_ <= pos);
400 first_use_interval_->start_ = pos;
401 }
402}
403
404LiveRange* FlowGraphAllocator::GetLiveRange(intptr_t vreg) {
405 if (live_ranges_[vreg] == NULL) {
406 Representation rep = value_representations_[vreg];
407 ASSERT(rep != kNoRepresentation);
408 live_ranges_[vreg] = new LiveRange(vreg, rep);
409 }
410 return live_ranges_[vreg];
411}
412
413LiveRange* FlowGraphAllocator::MakeLiveRangeForTemporary() {
414 // Representation does not matter for temps.
415 Representation ignored = kNoRepresentation;
416 LiveRange* range = new LiveRange(kTempVirtualRegister, ignored);
417#if defined(DEBUG)
418 temporaries_.Add(range);
419#endif
420 return range;
421}
422
423void FlowGraphAllocator::BlockRegisterLocation(Location loc,
424 intptr_t from,
425 intptr_t to,
426 bool* blocked_registers,
427 LiveRange** blocking_ranges) {
428 if (blocked_registers[loc.register_code()]) {
429 return;
430 }
431
432 if (blocking_ranges[loc.register_code()] == NULL) {
433 Representation ignored = kNoRepresentation;
434 LiveRange* range = new LiveRange(kNoVirtualRegister, ignored);
435 blocking_ranges[loc.register_code()] = range;
436 range->set_assigned_location(loc);
437#if defined(DEBUG)
438 temporaries_.Add(range);
439#endif
440 }
441
442 blocking_ranges[loc.register_code()]->AddUseInterval(from, to);
443}
444
445// Block location from the start of the instruction to its end.
446void FlowGraphAllocator::BlockLocation(Location loc,
447 intptr_t from,
448 intptr_t to) {
449 if (loc.IsRegister()) {
450 BlockRegisterLocation(loc, from, to, blocked_cpu_registers_, cpu_regs_);
451 } else if (loc.IsFpuRegister()) {
452 BlockRegisterLocation(loc, from, to, blocked_fpu_registers_, fpu_regs_);
453 } else {
454 UNREACHABLE();
455 }
456}
457
458void LiveRange::Print() {
459 if (first_use_interval() == NULL) {
460 return;
461 }
462
463 THR_Print(" live range v%" Pd " [%" Pd ", %" Pd ") in ", vreg(), Start(),
464 End());
465 assigned_location().Print();
466 if (spill_slot_.HasStackIndex()) {
467 const intptr_t stack_slot =
468 -compiler::target::frame_layout.VariableIndexForFrameSlot(
469 spill_slot_.stack_index());
470 THR_Print(" allocated spill slot: %" Pd "", stack_slot);
471 }
472 THR_Print("\n");
473
474 SafepointPosition* safepoint = first_safepoint();
475 while (safepoint != NULL) {
476 THR_Print(" Safepoint [%" Pd "]: ", safepoint->pos());
477 safepoint->locs()->stack_bitmap()->Print();
478 THR_Print("\n");
479 safepoint = safepoint->next();
480 }
481
482 UsePosition* use_pos = uses_;
483 for (UseInterval* interval = first_use_interval_; interval != NULL;
484 interval = interval->next()) {
485 THR_Print(" use interval [%" Pd ", %" Pd ")\n", interval->start(),
486 interval->end());
487 while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) {
488 THR_Print(" use at %" Pd "", use_pos->pos());
489 if (use_pos->location_slot() != NULL) {
490 THR_Print(" as ");
491 use_pos->location_slot()->Print();
492 }
493 THR_Print("\n");
494 use_pos = use_pos->next();
495 }
496 }
497
498 if (next_sibling() != NULL) {
499 next_sibling()->Print();
500 }
501}
502
503void FlowGraphAllocator::PrintLiveRanges() {
504#if defined(DEBUG)
505 for (intptr_t i = 0; i < temporaries_.length(); i++) {
506 temporaries_[i]->Print();
507 }
508#endif
509
510 for (intptr_t i = 0; i < live_ranges_.length(); i++) {
511 if (live_ranges_[i] != NULL) {
512 live_ranges_[i]->Print();
513 }
514 }
515}
516
517// Returns true if all uses of the given range inside the
518// given loop boundary have Any allocation policy.
519static bool HasOnlyUnconstrainedUsesInLoop(LiveRange* range,
520 intptr_t boundary) {
521 UsePosition* use = range->first_use();
522 while ((use != NULL) && (use->pos() < boundary)) {
523 if (!use->location_slot()->Equals(Location::Any())) {
524 return false;
525 }
526 use = use->next();
527 }
528 return true;
529}
530
531// Returns true if all uses of the given range have Any allocation policy.
532static bool HasOnlyUnconstrainedUses(LiveRange* range) {
533 UsePosition* use = range->first_use();
534 while (use != NULL) {
535 if (!use->location_slot()->Equals(Location::Any())) {
536 return false;
537 }
538 use = use->next();
539 }
540 return true;
541}
542
543void FlowGraphAllocator::BuildLiveRanges() {
544 const intptr_t block_count = postorder_.length();
545 ASSERT(postorder_.Last()->IsGraphEntry());
546 BitVector* current_interference_set = NULL;
547 Zone* zone = flow_graph_.zone();
548 for (intptr_t i = 0; i < (block_count - 1); i++) {
549 BlockEntryInstr* block = postorder_[i];
550 ASSERT(BlockEntryAt(block->start_pos()) == block);
551
552 // For every SSA value that is live out of this block, create an interval
553 // that covers the whole block. It will be shortened if we encounter a
554 // definition of this value in this block.
555 for (BitVector::Iterator it(liveness_.GetLiveOutSetAt(i)); !it.Done();
556 it.Advance()) {
557 LiveRange* range = GetLiveRange(it.Current());
558 range->AddUseInterval(block->start_pos(), block->end_pos());
559 }
560
561 LoopInfo* loop_info = block->loop_info();
562 if ((loop_info != nullptr) && (loop_info->IsBackEdge(block))) {
563 BitVector* backedge_interference =
564 extra_loop_info_[loop_info->id()]->backedge_interference;
565 if (backedge_interference != nullptr) {
566 // Restore interference for subsequent backedge a loop
567 // (perhaps inner loop's header reset set in the meanwhile).
568 current_interference_set = backedge_interference;
569 } else {
570 // All values flowing into the loop header are live at the
571 // back edge and can interfere with phi moves.
572 current_interference_set = new (zone)
573 BitVector(zone, flow_graph_.max_virtual_register_number());
574 current_interference_set->AddAll(
575 liveness_.GetLiveInSet(loop_info->header()));
576 extra_loop_info_[loop_info->id()]->backedge_interference =
577 current_interference_set;
578 }
579 }
580
581 // Connect outgoing phi-moves that were created in NumberInstructions
582 // and find last instruction that contributes to liveness.
583 Instruction* current =
584 ConnectOutgoingPhiMoves(block, current_interference_set);
585
586 // Now process all instructions in reverse order.
587 while (current != block) {
588 // Skip parallel moves that we insert while processing instructions.
589 if (!current->IsParallelMove()) {
590 ProcessOneInstruction(block, current, current_interference_set);
591 }
592 current = current->previous();
593 }
594
595 // Check if any values live into the loop can be spilled for free.
596 if (block->IsLoopHeader()) {
597 ASSERT(loop_info != nullptr);
598 current_interference_set = nullptr;
599 for (BitVector::Iterator it(liveness_.GetLiveInSetAt(i)); !it.Done();
600 it.Advance()) {
601 LiveRange* range = GetLiveRange(it.Current());
602 intptr_t loop_end = extra_loop_info_[loop_info->id()]->end;
603 if (HasOnlyUnconstrainedUsesInLoop(range, loop_end)) {
604 range->MarkHasOnlyUnconstrainedUsesInLoop(loop_info->id());
605 }
606 }
607 }
608
609 if (auto join_entry = block->AsJoinEntry()) {
610 ConnectIncomingPhiMoves(join_entry);
611 } else if (auto catch_entry = block->AsCatchBlockEntry()) {
612 // Process initial definitions.
613 ProcessEnvironmentUses(catch_entry, catch_entry); // For lazy deopt
614 for (intptr_t i = 0; i < catch_entry->initial_definitions()->length();
615 i++) {
616 Definition* defn = (*catch_entry->initial_definitions())[i];
617 LiveRange* range = GetLiveRange(defn->ssa_temp_index());
618 range->DefineAt(catch_entry->start_pos()); // Defined at block entry.
619 ProcessInitialDefinition(defn, range, catch_entry);
620 }
621 } else if (auto entry = block->AsBlockEntryWithInitialDefs()) {
622 ASSERT(block->IsFunctionEntry() || block->IsOsrEntry());
623 auto& initial_definitions = *entry->initial_definitions();
624 for (intptr_t i = 0; i < initial_definitions.length(); i++) {
625 Definition* defn = initial_definitions[i];
626 if (defn->HasPairRepresentation()) {
627 // The lower bits are pushed after the higher bits
628 LiveRange* range =
629 GetLiveRange(ToSecondPairVreg(defn->ssa_temp_index()));
630 range->AddUseInterval(entry->start_pos(), entry->start_pos() + 2);
631 range->DefineAt(entry->start_pos());
632 ProcessInitialDefinition(defn, range, entry,
633 /*second_location_for_definition=*/true);
634 }
635 LiveRange* range = GetLiveRange(defn->ssa_temp_index());
636 range->AddUseInterval(entry->start_pos(), entry->start_pos() + 2);
637 range->DefineAt(entry->start_pos());
638 ProcessInitialDefinition(defn, range, entry);
639 }
640 }
641 }
642
643 // Process incoming parameters and constants. Do this after all other
644 // instructions so that safepoints for all calls have already been found.
645 GraphEntryInstr* graph_entry = flow_graph_.graph_entry();
646 for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) {
647 Definition* defn = (*graph_entry->initial_definitions())[i];
648 ASSERT(!defn->HasPairRepresentation());
649 LiveRange* range = GetLiveRange(defn->ssa_temp_index());
650 range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos());
651 range->DefineAt(graph_entry->start_pos());
652 ProcessInitialDefinition(defn, range, graph_entry);
653 }
654}
655
656void FlowGraphAllocator::SplitInitialDefinitionAt(LiveRange* range,
657 intptr_t pos) {
658 if (range->End() > pos) {
659 LiveRange* tail = range->SplitAt(pos);
660 CompleteRange(tail, Location::kRegister);
661 }
662}
663
664void FlowGraphAllocator::ProcessInitialDefinition(
665 Definition* defn,
666 LiveRange* range,
667 BlockEntryInstr* block,
668 bool second_location_for_definition) {
669 // Save the range end because it may change below.
670 const intptr_t range_end = range->End();
671
672 // TODO(31956): Clean up this code and factor common functionality out.
673 // Consider also making a separate [ProcessInitialDefinition] for
674 // [CatchBlockEntry]'s.
675 if (block->IsCatchBlockEntry()) {
676 if (SpecialParameterInstr* param = defn->AsSpecialParameter()) {
677 Location loc;
678 switch (param->kind()) {
679 case SpecialParameterInstr::kException:
680 loc = LocationExceptionLocation();
681 break;
682 case SpecialParameterInstr::kStackTrace:
683 loc = LocationStackTraceLocation();
684 break;
685 default:
686 UNREACHABLE();
687 }
688 range->set_assigned_location(loc);
689 AssignSafepoints(defn, range);
690 range->finger()->Initialize(range);
691 SplitInitialDefinitionAt(range, GetLifetimePosition(block) + 1);
692 ConvertAllUses(range);
693
694 // We have exception/stacktrace in a register and need to
695 // ensure this register is not available for register allocation during
696 // the [CatchBlockEntry] to ensure it's not overwritten.
697 if (loc.IsRegister()) {
698 BlockLocation(loc, GetLifetimePosition(block),
699 GetLifetimePosition(block) + 1);
700 }
701 return;
702 }
703 }
704
705 if (defn->IsParameter()) {
706 // Only function entries may have unboxed parameters, possibly making the
707 // parameters size different from the number of parameters on 32-bit
708 // architectures.
709 const intptr_t parameters_size = block->IsFunctionEntry()
710 ? flow_graph_.direct_parameters_size()
711 : flow_graph_.num_direct_parameters();
712 ParameterInstr* param = defn->AsParameter();
713 intptr_t slot_index =
714 param->param_offset() + (second_location_for_definition ? -1 : 0);
715 ASSERT(slot_index >= 0);
716 if (param->base_reg() == FPREG) {
717 // Slot index for the rightmost fixed parameter is -1.
718 slot_index -= parameters_size;
719 } else {
720 // Slot index for a "frameless" parameter is reversed.
721 ASSERT(param->base_reg() == SPREG);
722 ASSERT(slot_index < parameters_size);
723 slot_index = parameters_size - 1 - slot_index;
724 }
725
726 if (param->base_reg() == FPREG) {
727 slot_index =
728 compiler::target::frame_layout.FrameSlotForVariableIndex(-slot_index);
729 } else {
730 ASSERT(param->base_reg() == SPREG);
731 slot_index += compiler::target::frame_layout.last_param_from_entry_sp;
732 }
733
734 if (param->representation() == kUnboxedInt64 ||
735 param->representation() == kTagged) {
736 const auto location = Location::StackSlot(slot_index, param->base_reg());
737 range->set_assigned_location(location);
738 range->set_spill_slot(location);
739 } else {
740 ASSERT(param->representation() == kUnboxedDouble);
741 const auto location =
742 Location::DoubleStackSlot(slot_index, param->base_reg());
743 range->set_assigned_location(location);
744 range->set_spill_slot(location);
745 }
746 } else if (defn->IsSpecialParameter()) {
747 SpecialParameterInstr* param = defn->AsSpecialParameter();
748 ASSERT(param->kind() == SpecialParameterInstr::kArgDescriptor);
749 Location loc;
750 loc = Location::RegisterLocation(ARGS_DESC_REG);
751 range->set_assigned_location(loc);
752 if (loc.IsRegister()) {
753 AssignSafepoints(defn, range);
754 if (range->End() > (GetLifetimePosition(block) + 2)) {
755 SplitInitialDefinitionAt(range, GetLifetimePosition(block) + 2);
756 }
757 ConvertAllUses(range);
758 BlockLocation(loc, GetLifetimePosition(block),
759 GetLifetimePosition(block) + 2);
760 return;
761 }
762 } else {
763 ConstantInstr* constant = defn->AsConstant();
764 ASSERT(constant != NULL);
765 range->set_assigned_location(Location::Constant(constant));
766 range->set_spill_slot(Location::Constant(constant));
767 }
768 AssignSafepoints(defn, range);
769 range->finger()->Initialize(range);
770 UsePosition* use =
771 range->finger()->FirstRegisterBeneficialUse(block->start_pos());
772 if (use != NULL) {
773 LiveRange* tail = SplitBetween(range, block->start_pos(), use->pos());
774 CompleteRange(tail, defn->RegisterKindForResult());
775 }
776 ConvertAllUses(range);
777 Location spill_slot = range->spill_slot();
778 if (spill_slot.IsStackSlot() && spill_slot.base_reg() == FPREG &&
779 spill_slot.stack_index() <=
780 compiler::target::frame_layout.first_local_from_fp) {
781 // On entry to the function, range is stored on the stack above the FP in
782 // the same space which is used for spill slots. Update spill slot state to
783 // reflect that and prevent register allocator from reusing this space as a
784 // spill slot.
785 spill_slots_.Add(range_end);
786 quad_spill_slots_.Add(false);
787 untagged_spill_slots_.Add(false);
788 // Note, all incoming parameters are assumed to be tagged.
789 MarkAsObjectAtSafepoints(range);
790 } else if (defn->IsConstant() && block->IsCatchBlockEntry()) {
791 // Constants at catch block entries consume spill slots.
792 spill_slots_.Add(range_end);
793 quad_spill_slots_.Add(false);
794 untagged_spill_slots_.Add(false);
795 }
796}
797
798static Location::Kind RegisterKindFromPolicy(Location loc) {
799 if (loc.policy() == Location::kRequiresFpuRegister) {
800 return Location::kFpuRegister;
801 } else {
802 return Location::kRegister;
803 }
804}
805
806//
807// When describing shape of live ranges in comments below we are going to use
808// the following notation:
809//
810// B block entry
811// g g' start and end of goto instruction
812// i i' start and end of any other instruction
813// j j' start and end of any other instruction
814
815// - body of a use interval
816// [ start of a use interval
817// ) end of a use interval
818// * use
819//
820// For example diagram
821//
822// i i'
823// value --*--)
824//
825// can be read as: use interval for value starts somewhere before instruction
826// and extends until currently processed instruction, there is a use of value
827// at the start of the instruction.
828//
829
830Instruction* FlowGraphAllocator::ConnectOutgoingPhiMoves(
831 BlockEntryInstr* block,
832 BitVector* interfere_at_backedge) {
833 Instruction* last = block->last_instruction();
834
835 GotoInstr* goto_instr = last->AsGoto();
836 if (goto_instr == NULL) return last;
837
838 // If we have a parallel move here then the successor block must be a
839 // join with phis. The phi inputs contribute uses to each predecessor
840 // block (and the phi outputs contribute definitions in the successor
841 // block).
842 if (!goto_instr->HasParallelMove()) return goto_instr->previous();
843 ParallelMoveInstr* parallel_move = goto_instr->parallel_move();
844
845 // All uses are recorded at the position of parallel move preceding goto.
846 const intptr_t pos = GetLifetimePosition(goto_instr);
847
848 JoinEntryInstr* join = goto_instr->successor();
849 ASSERT(join != NULL);
850
851 // Search for the index of the current block in the predecessors of
852 // the join.
853 const intptr_t pred_index = join->IndexOfPredecessor(block);
854
855 // Record the corresponding phi input use for each phi.
856 intptr_t move_index = 0;
857 for (PhiIterator it(join); !it.Done(); it.Advance()) {
858 PhiInstr* phi = it.Current();
859 Value* val = phi->InputAt(pred_index);
860 MoveOperands* move = parallel_move->MoveOperandsAt(move_index++);
861
862 ConstantInstr* constant = val->definition()->AsConstant();
863 if (constant != NULL) {
864 move->set_src(Location::Constant(constant));
865 continue;
866 }
867
868 // Expected shape of live ranges:
869 //
870 // g g'
871 // value --*
872 //
873 intptr_t vreg = val->definition()->ssa_temp_index();
874 LiveRange* range = GetLiveRange(vreg);
875 if (interfere_at_backedge != NULL) interfere_at_backedge->Add(vreg);
876
877 range->AddUseInterval(block->start_pos(), pos);
878 range->AddHintedUse(
879 pos, move->src_slot(),
880 GetLiveRange(phi->ssa_temp_index())->assigned_location_slot());
881 move->set_src(Location::PrefersRegister());
882
883 if (val->definition()->HasPairRepresentation()) {
884 move = parallel_move->MoveOperandsAt(move_index++);
885 vreg = ToSecondPairVreg(vreg);
886 range = GetLiveRange(vreg);
887 if (interfere_at_backedge != NULL) {
888 interfere_at_backedge->Add(vreg);
889 }
890 range->AddUseInterval(block->start_pos(), pos);
891 range->AddHintedUse(pos, move->src_slot(),
892 GetLiveRange(ToSecondPairVreg(phi->ssa_temp_index()))
893 ->assigned_location_slot());
894 move->set_src(Location::PrefersRegister());
895 }
896 }
897
898 // Begin backward iteration with the instruction before the parallel
899 // move.
900 return goto_instr->previous();
901}
902
903void FlowGraphAllocator::ConnectIncomingPhiMoves(JoinEntryInstr* join) {
904 // For join blocks we need to add destinations of phi resolution moves
905 // to phi's live range so that register allocator will fill them with moves.
906
907 // All uses are recorded at the start position in the block.
908 const intptr_t pos = join->start_pos();
909 const bool is_loop_header = join->IsLoopHeader();
910
911 intptr_t move_idx = 0;
912 for (PhiIterator it(join); !it.Done(); it.Advance()) {
913 PhiInstr* phi = it.Current();
914 ASSERT(phi != NULL);
915 const intptr_t vreg = phi->ssa_temp_index();
916 ASSERT(vreg >= 0);
917 const bool is_pair_phi = phi->HasPairRepresentation();
918
919 // Expected shape of live range:
920 //
921 // B
922 // phi [--------
923 //
924 LiveRange* range = GetLiveRange(vreg);
925 range->DefineAt(pos); // Shorten live range.
926 if (is_loop_header) range->mark_loop_phi();
927
928 if (is_pair_phi) {
929 LiveRange* second_range = GetLiveRange(ToSecondPairVreg(vreg));
930 second_range->DefineAt(pos); // Shorten live range.
931 if (is_loop_header) second_range->mark_loop_phi();
932 }
933
934 for (intptr_t pred_idx = 0; pred_idx < phi->InputCount(); pred_idx++) {
935 BlockEntryInstr* pred = join->PredecessorAt(pred_idx);
936 GotoInstr* goto_instr = pred->last_instruction()->AsGoto();
937 ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove()));
938 MoveOperands* move =
939 goto_instr->parallel_move()->MoveOperandsAt(move_idx);
940 move->set_dest(Location::PrefersRegister());
941 range->AddUse(pos, move->dest_slot());
942 if (is_pair_phi) {
943 LiveRange* second_range = GetLiveRange(ToSecondPairVreg(vreg));
944 MoveOperands* second_move =
945 goto_instr->parallel_move()->MoveOperandsAt(move_idx + 1);
946 second_move->set_dest(Location::PrefersRegister());
947 second_range->AddUse(pos, second_move->dest_slot());
948 }
949 }
950
951 // All phi resolution moves are connected. Phi's live range is
952 // complete.
953 AssignSafepoints(phi, range);
954 CompleteRange(range, phi->RegisterKindForResult());
955 if (is_pair_phi) {
956 LiveRange* second_range = GetLiveRange(ToSecondPairVreg(vreg));
957 AssignSafepoints(phi, second_range);
958 CompleteRange(second_range, phi->RegisterKindForResult());
959 }
960
961 move_idx += is_pair_phi ? 2 : 1;
962 }
963}
964
965void FlowGraphAllocator::ProcessEnvironmentUses(BlockEntryInstr* block,
966 Instruction* current) {
967 ASSERT(current->env() != NULL);
968 Environment* env = current->env();
969 while (env != NULL) {
970 // Any value mentioned in the deoptimization environment should survive
971 // until the end of instruction but it does not need to be in the register.
972 // Expected shape of live range:
973 //
974 // i i'
975 // value -----*
976 //
977
978 if (env->Length() == 0) {
979 env = env->outer();
980 continue;
981 }
982
983 const intptr_t block_start_pos = block->start_pos();
984 const intptr_t use_pos = GetLifetimePosition(current) + 1;
985
986 Location* locations = flow_graph_.zone()->Alloc<Location>(env->Length());
987
988 for (intptr_t i = 0; i < env->Length(); ++i) {
989 Value* value = env->ValueAt(i);
990 Definition* def = value->definition();
991 if (def->HasPairRepresentation()) {
992 locations[i] = Location::Pair(Location::Any(), Location::Any());
993 } else {
994 locations[i] = Location::Any();
995 }
996
997 if (def->IsPushArgument()) {
998 // Frame size is unknown until after allocation.
999 locations[i] = Location::NoLocation();
1000 continue;
1001 }
1002
1003 ConstantInstr* constant = def->AsConstant();
1004 if (constant != NULL) {
1005 locations[i] = Location::Constant(constant);
1006 continue;
1007 }
1008
1009 MaterializeObjectInstr* mat = def->AsMaterializeObject();
1010 if (mat != NULL) {
1011 // MaterializeObject itself produces no value. But its uses
1012 // are treated as part of the environment: allocated locations
1013 // will be used when building deoptimization data.
1014 locations[i] = Location::NoLocation();
1015 ProcessMaterializationUses(block, block_start_pos, use_pos, mat);
1016 continue;
1017 }
1018
1019 if (def->HasPairRepresentation()) {
1020 PairLocation* location_pair = locations[i].AsPairLocation();
1021 {
1022 // First live range.
1023 LiveRange* range = GetLiveRange(def->ssa_temp_index());
1024 range->AddUseInterval(block_start_pos, use_pos);
1025 range->AddUse(use_pos, location_pair->SlotAt(0));
1026 }
1027 {
1028 // Second live range.
1029 LiveRange* range =
1030 GetLiveRange(ToSecondPairVreg(def->ssa_temp_index()));
1031 range->AddUseInterval(block_start_pos, use_pos);
1032 range->AddUse(use_pos, location_pair->SlotAt(1));
1033 }
1034 } else {
1035 LiveRange* range = GetLiveRange(def->ssa_temp_index());
1036 range->AddUseInterval(block_start_pos, use_pos);
1037 range->AddUse(use_pos, &locations[i]);
1038 }
1039 }
1040
1041 env->set_locations(locations);
1042 env = env->outer();
1043 }
1044}
1045
1046void FlowGraphAllocator::ProcessMaterializationUses(
1047 BlockEntryInstr* block,
1048 const intptr_t block_start_pos,
1049 const intptr_t use_pos,
1050 MaterializeObjectInstr* mat) {
1051 // Materialization can occur several times in the same environment.
1052 // Check if we already processed this one.
1053 if (mat->locations() != NULL) {
1054 return; // Already processed.
1055 }
1056
1057 // Initialize location for every input of the MaterializeObject instruction.
1058 Location* locations = flow_graph_.zone()->Alloc<Location>(mat->InputCount());
1059 mat->set_locations(locations);
1060
1061 for (intptr_t i = 0; i < mat->InputCount(); ++i) {
1062 Definition* def = mat->InputAt(i)->definition();
1063
1064 ConstantInstr* constant = def->AsConstant();
1065 if (constant != NULL) {
1066 locations[i] = Location::Constant(constant);
1067 continue;
1068 }
1069
1070 if (def->HasPairRepresentation()) {
1071 locations[i] = Location::Pair(Location::Any(), Location::Any());
1072 PairLocation* location_pair = locations[i].AsPairLocation();
1073 {
1074 // First live range.
1075 LiveRange* range = GetLiveRange(def->ssa_temp_index());
1076 range->AddUseInterval(block_start_pos, use_pos);
1077 range->AddUse(use_pos, location_pair->SlotAt(0));
1078 }
1079 {
1080 // Second live range.
1081 LiveRange* range =
1082 GetLiveRange(ToSecondPairVreg(def->ssa_temp_index()));
1083 range->AddUseInterval(block_start_pos, use_pos);
1084 range->AddUse(use_pos, location_pair->SlotAt(1));
1085 }
1086 } else if (def->IsMaterializeObject()) {
1087 locations[i] = Location::NoLocation();
1088 ProcessMaterializationUses(block, block_start_pos, use_pos,
1089 def->AsMaterializeObject());
1090 } else {
1091 locations[i] = Location::Any();
1092 LiveRange* range = GetLiveRange(def->ssa_temp_index());
1093 range->AddUseInterval(block_start_pos, use_pos);
1094 range->AddUse(use_pos, &locations[i]);
1095 }
1096 }
1097}
1098
1099void FlowGraphAllocator::ProcessOneInput(BlockEntryInstr* block,
1100 intptr_t pos,
1101 Location* in_ref,
1102 Value* input,
1103 intptr_t vreg,
1104 RegisterSet* live_registers) {
1105 ASSERT(in_ref != NULL);
1106 ASSERT(!in_ref->IsPairLocation());
1107 ASSERT(input != NULL);
1108 ASSERT(block != NULL);
1109 LiveRange* range = GetLiveRange(vreg);
1110 if (in_ref->IsMachineRegister()) {
1111 // Input is expected in a fixed register. Expected shape of
1112 // live ranges:
1113 //
1114 // j' i i'
1115 // value --*
1116 // register [-----)
1117 //
1118 if (live_registers != NULL) {
1119 live_registers->Add(*in_ref, range->representation());
1120 }
1121 MoveOperands* move = AddMoveAt(pos - 1, *in_ref, Location::Any());
1122 ASSERT(!in_ref->IsRegister() ||
1123 ((1 << in_ref->reg()) & kDartAvailableCpuRegs) != 0);
1124 BlockLocation(*in_ref, pos - 1, pos + 1);
1125 range->AddUseInterval(block->start_pos(), pos - 1);
1126 range->AddHintedUse(pos - 1, move->src_slot(), in_ref);
1127 } else if (in_ref->IsUnallocated()) {
1128 if (in_ref->policy() == Location::kWritableRegister) {
1129 // Writable unallocated input. Expected shape of
1130 // live ranges:
1131 //
1132 // i i'
1133 // value --*
1134 // temp [--)
1135 MoveOperands* move = AddMoveAt(pos, Location::RequiresRegister(),
1136 Location::PrefersRegister());
1137
1138 // Add uses to the live range of the input.
1139 range->AddUseInterval(block->start_pos(), pos);
1140 range->AddUse(pos, move->src_slot());
1141
1142 // Create live range for the temporary.
1143 LiveRange* temp = MakeLiveRangeForTemporary();
1144 temp->AddUseInterval(pos, pos + 1);
1145 temp->AddHintedUse(pos, in_ref, move->src_slot());
1146 temp->AddUse(pos, move->dest_slot());
1147 *in_ref = Location::RequiresRegister();
1148 CompleteRange(temp, RegisterKindFromPolicy(*in_ref));
1149 } else {
1150 // Normal unallocated input. Expected shape of
1151 // live ranges:
1152 //
1153 // i i'
1154 // value -----*
1155 //
1156 range->AddUseInterval(block->start_pos(), pos + 1);
1157 range->AddUse(pos + 1, in_ref);
1158 }
1159 } else {
1160 ASSERT(in_ref->IsConstant());
1161 }
1162}
1163
1164void FlowGraphAllocator::ProcessOneOutput(BlockEntryInstr* block,
1165 intptr_t pos,
1166 Location* out,
1167 Definition* def,
1168 intptr_t vreg,
1169 bool output_same_as_first_input,
1170 Location* in_ref,
1171 Definition* input,
1172 intptr_t input_vreg,
1173 BitVector* interference_set) {
1174 ASSERT(out != NULL);
1175 ASSERT(!out->IsPairLocation());
1176 ASSERT(def != NULL);
1177 ASSERT(block != NULL);
1178
1179 LiveRange* range =
1180 vreg >= 0 ? GetLiveRange(vreg) : MakeLiveRangeForTemporary();
1181
1182 // Process output and finalize its liverange.
1183 if (out->IsMachineRegister()) {
1184 // Fixed output location. Expected shape of live range:
1185 //
1186 // i i' j j'
1187 // register [--)
1188 // output [-------
1189 //
1190 ASSERT(!out->IsRegister() ||
1191 ((1 << out->reg()) & kDartAvailableCpuRegs) != 0);
1192 BlockLocation(*out, pos, pos + 1);
1193
1194 if (range->vreg() == kTempVirtualRegister) return;
1195
1196 // We need to emit move connecting fixed register with another location
1197 // that will be allocated for this output's live range.
1198 // Special case: fixed output followed by a fixed input last use.
1199 UsePosition* use = range->first_use();
1200
1201 // If the value has no uses we don't need to allocate it.
1202 if (use == NULL) return;
1203
1204 // Connect fixed output to all inputs that immediately follow to avoid
1205 // allocating an intermediary register.
1206 for (; use != nullptr; use = use->next()) {
1207 if (use->pos() == (pos + 1)) {
1208 // Allocate and then drop this use.
1209 ASSERT(use->location_slot()->IsUnallocated());
1210 *(use->location_slot()) = *out;
1211 range->set_first_use(use->next());
1212 } else {
1213 ASSERT(use->pos() > (pos + 1)); // sorted
1214 break;
1215 }
1216 }
1217
1218 // Shorten live range to the point of definition, this might make the range
1219 // empty (if the only use immediately follows). If range is not empty add
1220 // move from a fixed register to an unallocated location.
1221 range->DefineAt(pos + 1);
1222 if (range->Start() == range->End()) return;
1223
1224 MoveOperands* move = AddMoveAt(pos + 1, Location::Any(), *out);
1225 range->AddHintedUse(pos + 1, move->dest_slot(), out);
1226 } else if (output_same_as_first_input) {
1227 ASSERT(in_ref != NULL);
1228 ASSERT(input != NULL);
1229 // Output register will contain a value of the first input at instruction's
1230 // start. Expected shape of live ranges:
1231 //
1232 // i i'
1233 // input #0 --*
1234 // output [----
1235 //
1236 ASSERT(in_ref->Equals(Location::RequiresRegister()) ||
1237 in_ref->Equals(Location::RequiresFpuRegister()));
1238 *out = *in_ref;
1239 // Create move that will copy value between input and output.
1240 MoveOperands* move =
1241 AddMoveAt(pos, Location::RequiresRegister(), Location::Any());
1242
1243 // Add uses to the live range of the input.
1244 LiveRange* input_range = GetLiveRange(input_vreg);
1245 input_range->AddUseInterval(block->start_pos(), pos);
1246 input_range->AddUse(pos, move->src_slot());
1247
1248 // Shorten output live range to the point of definition and add both input
1249 // and output uses slots to be filled by allocator.
1250 range->DefineAt(pos);
1251 range->AddHintedUse(pos, out, move->src_slot());
1252 range->AddUse(pos, move->dest_slot());
1253 range->AddUse(pos, in_ref);
1254
1255 if ((interference_set != NULL) && (range->vreg() >= 0) &&
1256 interference_set->Contains(range->vreg())) {
1257 interference_set->Add(input->ssa_temp_index());
1258 }
1259 } else {
1260 // Normal unallocated location that requires a register. Expected shape of
1261 // live range:
1262 //
1263 // i i'
1264 // output [-------
1265 //
1266 ASSERT(out->Equals(Location::RequiresRegister()) ||
1267 out->Equals(Location::RequiresFpuRegister()));
1268
1269 // Shorten live range to the point of definition and add use to be filled by
1270 // allocator.
1271 range->DefineAt(pos);
1272 range->AddUse(pos, out);
1273 }
1274
1275 AssignSafepoints(def, range);
1276 CompleteRange(range, def->RegisterKindForResult());
1277}
1278
1279// Create and update live ranges corresponding to instruction's inputs,
1280// temporaries and output.
1281void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block,
1282 Instruction* current,
1283 BitVector* interference_set) {
1284 LocationSummary* locs = current->locs();
1285
1286 Definition* def = current->AsDefinition();
1287 if ((def != NULL) && (def->AsConstant() != NULL)) {
1288 ASSERT(!def->HasPairRepresentation());
1289 LiveRange* range = (def->ssa_temp_index() != -1)
1290 ? GetLiveRange(def->ssa_temp_index())
1291 : NULL;
1292
1293 // Drop definitions of constants that have no uses.
1294 if ((range == NULL) || (range->first_use() == NULL)) {
1295 locs->set_out(0, Location::NoLocation());
1296 return;
1297 }
1298
1299 // If this constant has only unconstrained uses convert them all
1300 // to use the constant directly and drop this definition.
1301 // TODO(vegorov): improve allocation when we have enough registers to keep
1302 // constants used in the loop in them.
1303 if (HasOnlyUnconstrainedUses(range)) {
1304 ConstantInstr* constant_instr = def->AsConstant();
1305 range->set_assigned_location(Location::Constant(constant_instr));
1306 range->set_spill_slot(Location::Constant(constant_instr));
1307 range->finger()->Initialize(range);
1308 ConvertAllUses(range);
1309
1310 locs->set_out(0, Location::NoLocation());
1311 return;
1312 }
1313 }
1314
1315 const intptr_t pos = GetLifetimePosition(current);
1316 ASSERT(IsInstructionStartPosition(pos));
1317
1318 ASSERT(locs->input_count() == current->InputCount());
1319
1320 // Normalize same-as-first-input output if input is specified as
1321 // fixed register.
1322 if (locs->out(0).IsUnallocated() &&
1323 (locs->out(0).policy() == Location::kSameAsFirstInput)) {
1324 if (locs->in(0).IsPairLocation()) {
1325 // Pair input, pair output.
1326 PairLocation* in_pair = locs->in(0).AsPairLocation();
1327 ASSERT(in_pair->At(0).IsMachineRegister() ==
1328 in_pair->At(1).IsMachineRegister());
1329 if (in_pair->At(0).IsMachineRegister() &&
1330 in_pair->At(1).IsMachineRegister()) {
1331 locs->set_out(0, Location::Pair(in_pair->At(0), in_pair->At(1)));
1332 }
1333 } else if (locs->in(0).IsMachineRegister()) {
1334 // Single input, single output.
1335 locs->set_out(0, locs->in(0));
1336 }
1337 }
1338
1339 const bool output_same_as_first_input =
1340 locs->out(0).IsUnallocated() &&
1341 (locs->out(0).policy() == Location::kSameAsFirstInput);
1342
1343 // Output is same as first input which is a pair.
1344 if (output_same_as_first_input && locs->in(0).IsPairLocation()) {
1345 // Make out into a PairLocation.
1346 locs->set_out(0, Location::Pair(Location::RequiresRegister(),
1347 Location::RequiresRegister()));
1348 }
1349 // Add uses from the deoptimization environment.
1350 if (current->env() != NULL) ProcessEnvironmentUses(block, current);
1351
1352 // Process inputs.
1353 // Skip the first input if output is specified with kSameAsFirstInput policy,
1354 // they will be processed together at the very end.
1355 {
1356 for (intptr_t j = output_same_as_first_input ? 1 : 0;
1357 j < locs->input_count(); j++) {
1358 // Determine if we are dealing with a value pair, and if so, whether
1359 // the location is the first register or second register.
1360 Value* input = current->InputAt(j);
1361 Location* in_ref = locs->in_slot(j);
1362 RegisterSet* live_registers = NULL;
1363 if (locs->HasCallOnSlowPath()) {
1364 live_registers = locs->live_registers();
1365 }
1366 if (in_ref->IsPairLocation()) {
1367 ASSERT(input->definition()->HasPairRepresentation());
1368 PairLocation* pair = in_ref->AsPairLocation();
1369 const intptr_t vreg = input->definition()->ssa_temp_index();
1370 // Each element of the pair is assigned it's own virtual register number
1371 // and is allocated its own LiveRange.
1372 ProcessOneInput(block, pos, pair->SlotAt(0), input, vreg,
1373 live_registers);
1374 ProcessOneInput(block, pos, pair->SlotAt(1), input,
1375 ToSecondPairVreg(vreg), live_registers);
1376 } else {
1377 ProcessOneInput(block, pos, in_ref, input,
1378 input->definition()->ssa_temp_index(), live_registers);
1379 }
1380 }
1381 }
1382
1383 // Process temps.
1384 for (intptr_t j = 0; j < locs->temp_count(); j++) {
1385 // Expected shape of live range:
1386 //
1387 // i i'
1388 // [--)
1389 //
1390
1391 Location temp = locs->temp(j);
1392 // We do not support pair locations for temporaries.
1393 ASSERT(!temp.IsPairLocation());
1394 if (temp.IsMachineRegister()) {
1395 ASSERT(!temp.IsRegister() ||
1396 ((1 << temp.reg()) & kDartAvailableCpuRegs) != 0);
1397 BlockLocation(temp, pos, pos + 1);
1398 } else if (temp.IsUnallocated()) {
1399 LiveRange* range = MakeLiveRangeForTemporary();
1400 range->AddUseInterval(pos, pos + 1);
1401 range->AddUse(pos, locs->temp_slot(j));
1402 CompleteRange(range, RegisterKindFromPolicy(temp));
1403 } else {
1404 UNREACHABLE();
1405 }
1406 }
1407
1408// Block all allocatable registers for calls.
1409 if (locs->always_calls() && !locs->callee_safe_call()) {
1410 // Expected shape of live range:
1411 //
1412 // i i'
1413 // [--)
1414 //
1415 // The stack bitmap describes the position i.
1416 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
1417 BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)), pos,
1418 pos + 1);
1419 }
1420
1421 for (intptr_t reg = 0; reg < kNumberOfFpuRegisters; reg++) {
1422 BlockLocation(
1423 Location::FpuRegisterLocation(static_cast<FpuRegister>(reg)), pos,
1424 pos + 1);
1425 }
1426
1427#if defined(DEBUG)
1428 // Verify that temps, inputs and output were specified as fixed
1429 // locations. Every register is blocked now so attempt to
1430 // allocate will go on the stack.
1431 for (intptr_t j = 0; j < locs->temp_count(); j++) {
1432 ASSERT(!locs->temp(j).IsPairLocation());
1433 ASSERT(!locs->temp(j).IsUnallocated());
1434 }
1435
1436 for (intptr_t j = 0; j < locs->input_count(); j++) {
1437 if (locs->in(j).IsPairLocation()) {
1438 PairLocation* pair = locs->in_slot(j)->AsPairLocation();
1439 ASSERT(!pair->At(0).IsUnallocated() ||
1440 pair->At(0).policy() == Location::kAny);
1441 ASSERT(!pair->At(1).IsUnallocated() ||
1442 pair->At(1).policy() == Location::kAny);
1443 } else {
1444 ASSERT(!locs->in(j).IsUnallocated() ||
1445 locs->in(j).policy() == Location::kAny);
1446 }
1447 }
1448
1449 if (locs->out(0).IsPairLocation()) {
1450 PairLocation* pair = locs->out_slot(0)->AsPairLocation();
1451 ASSERT(!pair->At(0).IsUnallocated());
1452 ASSERT(!pair->At(1).IsUnallocated());
1453 } else {
1454 ASSERT(!locs->out(0).IsUnallocated());
1455 }
1456#endif
1457 }
1458
1459 if (locs->can_call()) {
1460 safepoints_.Add(current);
1461 }
1462
1463 if (def == NULL) {
1464 ASSERT(locs->out(0).IsInvalid());
1465 return;
1466 }
1467
1468 if (locs->out(0).IsInvalid()) {
1469 ASSERT(def->ssa_temp_index() < 0);
1470 return;
1471 }
1472
1473 ASSERT(locs->output_count() == 1);
1474 Location* out = locs->out_slot(0);
1475 if (out->IsPairLocation()) {
1476 ASSERT(def->HasPairRepresentation());
1477 PairLocation* pair = out->AsPairLocation();
1478 if (output_same_as_first_input) {
1479 ASSERT(locs->in_slot(0)->IsPairLocation());
1480 PairLocation* in_pair = locs->in_slot(0)->AsPairLocation();
1481 Definition* input = current->InputAt(0)->definition();
1482 ASSERT(input->HasPairRepresentation());
1483 // Each element of the pair is assigned it's own virtual register number
1484 // and is allocated its own LiveRange.
1485 ProcessOneOutput(block, pos, // BlockEntry, seq.
1486 pair->SlotAt(0), def, // (output) Location, Definition.
1487 def->ssa_temp_index(), // (output) virtual register.
1488 true, // output mapped to first input.
1489 in_pair->SlotAt(0), input, // (input) Location, Def.
1490 input->ssa_temp_index(), // (input) virtual register.
1491 interference_set);
1492 ProcessOneOutput(
1493 block, pos, pair->SlotAt(1), def,
1494 ToSecondPairVreg(def->ssa_temp_index()), true, in_pair->SlotAt(1),
1495 input, ToSecondPairVreg(input->ssa_temp_index()), interference_set);
1496 } else {
1497 // Each element of the pair is assigned it's own virtual register number
1498 // and is allocated its own LiveRange.
1499 ProcessOneOutput(block, pos, pair->SlotAt(0), def, def->ssa_temp_index(),
1500 false, // output is not mapped to first input.
1501 NULL, NULL, -1, // First input not needed.
1502 interference_set);
1503 ProcessOneOutput(block, pos, pair->SlotAt(1), def,
1504 ToSecondPairVreg(def->ssa_temp_index()), false, NULL,
1505 NULL, -1, interference_set);
1506 }
1507 } else {
1508 if (output_same_as_first_input) {
1509 Location* in_ref = locs->in_slot(0);
1510 Definition* input = current->InputAt(0)->definition();
1511 ASSERT(!in_ref->IsPairLocation());
1512 ProcessOneOutput(block, pos, // BlockEntry, Instruction, seq.
1513 out, def, // (output) Location, Definition.
1514 def->ssa_temp_index(), // (output) virtual register.
1515 true, // output mapped to first input.
1516 in_ref, input, // (input) Location, Def.
1517 input->ssa_temp_index(), // (input) virtual register.
1518 interference_set);
1519 } else {
1520 ProcessOneOutput(block, pos, out, def, def->ssa_temp_index(),
1521 false, // output is not mapped to first input.
1522 NULL, NULL, -1, // First input not needed.
1523 interference_set);
1524 }
1525 }
1526}
1527
1528static ParallelMoveInstr* CreateParallelMoveBefore(Instruction* instr,
1529 intptr_t pos) {
1530 ASSERT(pos > 0);
1531 Instruction* prev = instr->previous();
1532 ParallelMoveInstr* move = prev->AsParallelMove();
1533 if ((move == NULL) ||
1534 (FlowGraphAllocator::GetLifetimePosition(move) != pos)) {
1535 move = new ParallelMoveInstr();
1536 prev->LinkTo(move);
1537 move->LinkTo(instr);
1538 FlowGraphAllocator::SetLifetimePosition(move, pos);
1539 }
1540 return move;
1541}
1542
1543static ParallelMoveInstr* CreateParallelMoveAfter(Instruction* instr,
1544 intptr_t pos) {
1545 Instruction* next = instr->next();
1546 if (next->IsParallelMove() &&
1547 (FlowGraphAllocator::GetLifetimePosition(next) == pos)) {
1548 return next->AsParallelMove();
1549 }
1550 return CreateParallelMoveBefore(next, pos);
1551}
1552
1553// Linearize the control flow graph. The chosen order will be used by the
1554// linear-scan register allocator. Number most instructions with a pair of
1555// numbers representing lifetime positions. Introduce explicit parallel
1556// move instructions in the predecessors of join nodes. The moves are used
1557// for phi resolution.
1558void FlowGraphAllocator::NumberInstructions() {
1559 intptr_t pos = 0;
1560
1561 // The basic block order is reverse postorder.
1562 const intptr_t block_count = postorder_.length();
1563 for (intptr_t i = block_count - 1; i >= 0; i--) {
1564 BlockEntryInstr* block = postorder_[i];
1565
1566 instructions_.Add(block);
1567 block_entries_.Add(block);
1568 block->set_start_pos(pos);
1569 SetLifetimePosition(block, pos);
1570 pos += 2;
1571
1572 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
1573 Instruction* current = it.Current();
1574 // Do not assign numbers to parallel move instructions.
1575 if (!current->IsParallelMove()) {
1576 instructions_.Add(current);
1577 block_entries_.Add(block);
1578 SetLifetimePosition(current, pos);
1579 pos += 2;
1580 }
1581 }
1582 block->set_end_pos(pos);
1583 }
1584
1585 // Create parallel moves in join predecessors. This must be done after
1586 // all instructions are numbered.
1587 for (intptr_t i = block_count - 1; i >= 0; i--) {
1588 BlockEntryInstr* block = postorder_[i];
1589
1590 // For join entry predecessors create phi resolution moves if
1591 // necessary. They will be populated by the register allocator.
1592 JoinEntryInstr* join = block->AsJoinEntry();
1593 if (join != NULL) {
1594 intptr_t move_count = 0;
1595 for (PhiIterator it(join); !it.Done(); it.Advance()) {
1596 move_count += it.Current()->HasPairRepresentation() ? 2 : 1;
1597 }
1598 for (intptr_t i = 0; i < block->PredecessorCount(); i++) {
1599 // Insert the move between the last two instructions of the
1600 // predecessor block (all such blocks have at least two instructions:
1601 // the block entry and goto instructions.)
1602 Instruction* last = block->PredecessorAt(i)->last_instruction();
1603 ASSERT(last->IsGoto());
1604
1605 ParallelMoveInstr* move = last->AsGoto()->GetParallelMove();
1606
1607 // Populate the ParallelMove with empty moves.
1608 for (intptr_t j = 0; j < move_count; j++) {
1609 move->AddMove(Location::NoLocation(), Location::NoLocation());
1610 }
1611 }
1612 }
1613 }
1614
1615 // Prepare some extra information for each loop.
1616 Zone* zone = flow_graph_.zone();
1617 const LoopHierarchy& loop_hierarchy = flow_graph_.loop_hierarchy();
1618 const intptr_t num_loops = loop_hierarchy.num_loops();
1619 for (intptr_t i = 0; i < num_loops; i++) {
1620 extra_loop_info_.Add(
1621 ComputeExtraLoopInfo(zone, loop_hierarchy.headers()[i]->loop_info()));
1622 }
1623}
1624
1625Instruction* FlowGraphAllocator::InstructionAt(intptr_t pos) const {
1626 return instructions_[pos / 2];
1627}
1628
1629BlockEntryInstr* FlowGraphAllocator::BlockEntryAt(intptr_t pos) const {
1630 return block_entries_[pos / 2];
1631}
1632
1633bool FlowGraphAllocator::IsBlockEntry(intptr_t pos) const {
1634 return IsInstructionStartPosition(pos) && InstructionAt(pos)->IsBlockEntry();
1635}
1636
1637void AllocationFinger::Initialize(LiveRange* range) {
1638 first_pending_use_interval_ = range->first_use_interval();
1639 first_register_use_ = range->first_use();
1640 first_register_beneficial_use_ = range->first_use();
1641 first_hinted_use_ = range->first_use();
1642}
1643
1644bool AllocationFinger::Advance(const intptr_t start) {
1645 UseInterval* a = first_pending_use_interval_;
1646 while (a != NULL && a->end() <= start)
1647 a = a->next();
1648 first_pending_use_interval_ = a;
1649 return (first_pending_use_interval_ == NULL);
1650}
1651
1652Location AllocationFinger::FirstHint() {
1653 UsePosition* use = first_hinted_use_;
1654
1655 while (use != NULL) {
1656 if (use->HasHint()) return use->hint();
1657 use = use->next();
1658 }
1659
1660 return Location::NoLocation();
1661}
1662
1663static UsePosition* FirstUseAfter(UsePosition* use, intptr_t after) {
1664 while ((use != NULL) && (use->pos() < after)) {
1665 use = use->next();
1666 }
1667 return use;
1668}
1669
1670UsePosition* AllocationFinger::FirstRegisterUse(intptr_t after) {
1671 for (UsePosition* use = FirstUseAfter(first_register_use_, after);
1672 use != NULL; use = use->next()) {
1673 Location* loc = use->location_slot();
1674 if (loc->IsUnallocated() &&
1675 ((loc->policy() == Location::kRequiresRegister) ||
1676 (loc->policy() == Location::kRequiresFpuRegister))) {
1677 first_register_use_ = use;
1678 return use;
1679 }
1680 }
1681 return NULL;
1682}
1683
1684UsePosition* AllocationFinger::FirstRegisterBeneficialUse(intptr_t after) {
1685 for (UsePosition* use = FirstUseAfter(first_register_beneficial_use_, after);
1686 use != NULL; use = use->next()) {
1687 Location* loc = use->location_slot();
1688 if (loc->IsUnallocated() && loc->IsRegisterBeneficial()) {
1689 first_register_beneficial_use_ = use;
1690 return use;
1691 }
1692 }
1693 return NULL;
1694}
1695
1696UsePosition* AllocationFinger::FirstInterferingUse(intptr_t after) {
1697 if (IsInstructionEndPosition(after)) {
1698 // If after is a position at the end of the instruction disregard
1699 // any use occurring at it.
1700 after += 1;
1701 }
1702 return FirstRegisterUse(after);
1703}
1704
1705void AllocationFinger::UpdateAfterSplit(intptr_t first_use_after_split_pos) {
1706 if ((first_register_use_ != NULL) &&
1707 (first_register_use_->pos() >= first_use_after_split_pos)) {
1708 first_register_use_ = NULL;
1709 }
1710
1711 if ((first_register_beneficial_use_ != NULL) &&
1712 (first_register_beneficial_use_->pos() >= first_use_after_split_pos)) {
1713 first_register_beneficial_use_ = NULL;
1714 }
1715}
1716
1717intptr_t UseInterval::Intersect(UseInterval* other) {
1718 if (this->start() <= other->start()) {
1719 if (other->start() < this->end()) return other->start();
1720 } else if (this->start() < other->end()) {
1721 return this->start();
1722 }
1723 return kIllegalPosition;
1724}
1725
1726static intptr_t FirstIntersection(UseInterval* a, UseInterval* u) {
1727 while (a != NULL && u != NULL) {
1728 const intptr_t pos = a->Intersect(u);
1729 if (pos != kIllegalPosition) return pos;
1730
1731 if (a->start() < u->start()) {
1732 a = a->next();
1733 } else {
1734 u = u->next();
1735 }
1736 }
1737
1738 return kMaxPosition;
1739}
1740
1741template <typename PositionType>
1742PositionType* SplitListOfPositions(PositionType** head,
1743 intptr_t split_pos,
1744 bool split_at_start) {
1745 PositionType* last_before_split = NULL;
1746 PositionType* pos = *head;
1747 if (split_at_start) {
1748 while ((pos != NULL) && (pos->pos() < split_pos)) {
1749 last_before_split = pos;
1750 pos = pos->next();
1751 }
1752 } else {
1753 while ((pos != NULL) && (pos->pos() <= split_pos)) {
1754 last_before_split = pos;
1755 pos = pos->next();
1756 }
1757 }
1758
1759 if (last_before_split == NULL) {
1760 *head = NULL;
1761 } else {
1762 last_before_split->set_next(NULL);
1763 }
1764
1765 return pos;
1766}
1767
1768LiveRange* LiveRange::SplitAt(intptr_t split_pos) {
1769 if (Start() == split_pos) return this;
1770
1771 UseInterval* interval = finger_.first_pending_use_interval();
1772 if (interval == NULL) {
1773 finger_.Initialize(this);
1774 interval = finger_.first_pending_use_interval();
1775 }
1776
1777 ASSERT(split_pos < End());
1778
1779 // Corner case. Split position can be inside the a lifetime hole or at its
1780 // end. We need to start over to find the previous interval.
1781 if (split_pos <= interval->start()) interval = first_use_interval_;
1782
1783 UseInterval* last_before_split = NULL;
1784 while (interval->end() <= split_pos) {
1785 last_before_split = interval;
1786 interval = interval->next();
1787 }
1788
1789 const bool split_at_start = (interval->start() == split_pos);
1790
1791 UseInterval* first_after_split = interval;
1792 if (!split_at_start && interval->Contains(split_pos)) {
1793 first_after_split =
1794 new UseInterval(split_pos, interval->end(), interval->next());
1795 interval->end_ = split_pos;
1796 interval->next_ = first_after_split;
1797 last_before_split = interval;
1798 }
1799
1800 ASSERT(last_before_split != NULL);
1801 ASSERT(last_before_split->next() == first_after_split);
1802 ASSERT(last_before_split->end() <= split_pos);
1803 ASSERT(split_pos <= first_after_split->start());
1804
1805 UsePosition* first_use_after_split =
1806 SplitListOfPositions(&uses_, split_pos, split_at_start);
1807
1808 SafepointPosition* first_safepoint_after_split =
1809 SplitListOfPositions(&first_safepoint_, split_pos, split_at_start);
1810
1811 UseInterval* last_use_interval = (last_before_split == last_use_interval_)
1812 ? first_after_split
1813 : last_use_interval_;
1814 next_sibling_ = new LiveRange(vreg(), representation(), first_use_after_split,
1815 first_after_split, last_use_interval,
1816 first_safepoint_after_split, next_sibling_);
1817
1818 TRACE_ALLOC(THR_Print(" split sibling [%" Pd ", %" Pd ")\n",
1819 next_sibling_->Start(), next_sibling_->End()));
1820
1821 last_use_interval_ = last_before_split;
1822 last_use_interval_->next_ = NULL;
1823
1824 if (first_use_after_split != NULL) {
1825 finger_.UpdateAfterSplit(first_use_after_split->pos());
1826 }
1827
1828 return next_sibling_;
1829}
1830
1831LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range,
1832 intptr_t from,
1833 intptr_t to) {
1834 TRACE_ALLOC(THR_Print("split v%" Pd " [%" Pd ", %" Pd ") between [%" Pd
1835 ", %" Pd ")\n",
1836 range->vreg(), range->Start(), range->End(), from, to));
1837
1838 intptr_t split_pos = kIllegalPosition;
1839
1840 BlockEntryInstr* split_block_entry = BlockEntryAt(to);
1841 ASSERT(split_block_entry == InstructionAt(to)->GetBlock());
1842
1843 if (from < GetLifetimePosition(split_block_entry)) {
1844 // Interval [from, to) spans multiple blocks.
1845
1846 // If the last block is inside a loop, prefer splitting at the outermost
1847 // loop's header that follows the definition. Note that, as illustrated
1848 // below, if the potential split S linearly appears inside a loop, even
1849 // though it technically does not belong to the natural loop, we still
1850 // prefer splitting at the header H. Splitting in the "middle" of the loop
1851 // would disconnect the prefix of the loop from any block X that follows,
1852 // increasing the chance of "disconnected" allocations.
1853 //
1854 // +--------------------+
1855 // v |
1856 // |loop| |loop|
1857 // . . . . . . . . . . . . . . . . . . . . .
1858 // def------------use -----------
1859 // ^ ^ ^
1860 // H S X
1861 LoopInfo* loop_info = split_block_entry->loop_info();
1862 if (loop_info == nullptr) {
1863 const LoopHierarchy& loop_hierarchy = flow_graph_.loop_hierarchy();
1864 const intptr_t num_loops = loop_hierarchy.num_loops();
1865 for (intptr_t i = 0; i < num_loops; i++) {
1866 if (extra_loop_info_[i]->start < to && to < extra_loop_info_[i]->end) {
1867 // Split loop found!
1868 loop_info = loop_hierarchy.headers()[i]->loop_info();
1869 break;
1870 }
1871 }
1872 }
1873 while ((loop_info != nullptr) &&
1874 (from < GetLifetimePosition(loop_info->header()))) {
1875 split_block_entry = loop_info->header();
1876 loop_info = loop_info->outer();
1877 TRACE_ALLOC(THR_Print(" move back to loop header B%" Pd " at %" Pd "\n",
1878 split_block_entry->block_id(),
1879 GetLifetimePosition(split_block_entry)));
1880 }
1881
1882 // Split at block's start.
1883 split_pos = GetLifetimePosition(split_block_entry);
1884 } else {
1885 // Interval [from, to) is contained inside a single block.
1886
1887 // Split at position corresponding to the end of the previous
1888 // instruction.
1889 split_pos = ToInstructionStart(to) - 1;
1890 }
1891
1892 ASSERT(split_pos != kIllegalPosition);
1893 ASSERT(from < split_pos);
1894
1895 return range->SplitAt(split_pos);
1896}
1897
1898void FlowGraphAllocator::SpillBetween(LiveRange* range,
1899 intptr_t from,
1900 intptr_t to) {
1901 ASSERT(from < to);
1902 TRACE_ALLOC(THR_Print("spill v%" Pd " [%" Pd ", %" Pd ") "
1903 "between [%" Pd ", %" Pd ")\n",
1904 range->vreg(), range->Start(), range->End(), from, to));
1905 LiveRange* tail = range->SplitAt(from);
1906
1907 if (tail->Start() < to) {
1908 // There is an intersection of tail and [from, to).
1909 LiveRange* tail_tail = SplitBetween(tail, tail->Start(), to);
1910 Spill(tail);
1911 AddToUnallocated(tail_tail);
1912 } else {
1913 // No intersection between tail and [from, to).
1914 AddToUnallocated(tail);
1915 }
1916}
1917
1918void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) {
1919 TRACE_ALLOC(THR_Print("spill v%" Pd " [%" Pd ", %" Pd ") after %" Pd "\n",
1920 range->vreg(), range->Start(), range->End(), from));
1921
1922 // When spilling the value inside the loop check if this spill can
1923 // be moved outside.
1924 LoopInfo* loop_info = BlockEntryAt(from)->loop_info();
1925 if (loop_info != nullptr) {
1926 if ((range->Start() <= loop_info->header()->start_pos()) &&
1927 RangeHasOnlyUnconstrainedUsesInLoop(range, loop_info->id())) {
1928 ASSERT(loop_info->header()->start_pos() <= from);
1929 from = loop_info->header()->start_pos();
1930 TRACE_ALLOC(
1931 THR_Print(" moved spill position to loop header %" Pd "\n", from));
1932 }
1933 }
1934
1935 LiveRange* tail = range->SplitAt(from);
1936 Spill(tail);
1937}
1938
1939void FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) {
1940 ASSERT(range->spill_slot().IsInvalid());
1941
1942 // Compute range start and end.
1943 LiveRange* last_sibling = range;
1944 while (last_sibling->next_sibling() != NULL) {
1945 last_sibling = last_sibling->next_sibling();
1946 }
1947
1948 const intptr_t start = range->Start();
1949 const intptr_t end = last_sibling->End();
1950
1951 // During fpu register allocation spill slot indices are computed in terms of
1952 // double (64bit) stack slots. We treat quad stack slot (128bit) as a
1953 // consecutive pair of two double spill slots.
1954 // Special care is taken to never allocate the same index to both
1955 // double and quad spill slots as it complicates disambiguation during
1956 // parallel move resolution.
1957 const bool need_quad = (register_kind_ == Location::kFpuRegister) &&
1958 ((range->representation() == kUnboxedFloat32x4) ||
1959 (range->representation() == kUnboxedInt32x4) ||
1960 (range->representation() == kUnboxedFloat64x2));
1961 const bool need_untagged = (register_kind_ == Location::kRegister) &&
1962 ((range->representation() == kUntagged));
1963
1964 // Search for a free spill slot among allocated: the value in it should be
1965 // dead and its type should match (e.g. it should not be a part of the quad if
1966 // we are allocating normal double slot).
1967 // For CPU registers we need to take reserved slots for try-catch into
1968 // account.
1969 intptr_t idx = register_kind_ == Location::kRegister
1970 ? flow_graph_.graph_entry()->fixed_slot_count()
1971 : 0;
1972 for (; idx < spill_slots_.length(); idx++) {
1973 if ((need_quad == quad_spill_slots_[idx]) &&
1974 (need_untagged == untagged_spill_slots_[idx]) &&
1975 (spill_slots_[idx] <= start)) {
1976 break;
1977 }
1978 }
1979
1980 while (idx > spill_slots_.length()) {
1981 spill_slots_.Add(kMaxPosition);
1982 quad_spill_slots_.Add(false);
1983 untagged_spill_slots_.Add(false);
1984 }
1985
1986 if (idx == spill_slots_.length()) {
1987 idx = spill_slots_.length();
1988
1989 // No free spill slot found. Allocate a new one.
1990 spill_slots_.Add(0);
1991 quad_spill_slots_.Add(need_quad);
1992 untagged_spill_slots_.Add(need_untagged);
1993 if (need_quad) { // Allocate two double stack slots if we need quad slot.
1994 spill_slots_.Add(0);
1995 quad_spill_slots_.Add(need_quad);
1996 untagged_spill_slots_.Add(need_untagged);
1997 }
1998 }
1999
2000 // Set spill slot expiration boundary to the live range's end.
2001 spill_slots_[idx] = end;
2002 if (need_quad) {
2003 ASSERT(quad_spill_slots_[idx] && quad_spill_slots_[idx + 1]);
2004 idx++; // Use the higher index it corresponds to the lower stack address.
2005 spill_slots_[idx] = end;
2006 } else {
2007 ASSERT(!quad_spill_slots_[idx]);
2008 }
2009
2010 // Assign spill slot to the range.
2011 if (register_kind_ == Location::kRegister) {
2012 const intptr_t slot_index =
2013 compiler::target::frame_layout.FrameSlotForVariableIndex(-idx);
2014 range->set_spill_slot(Location::StackSlot(slot_index, FPREG));
2015 } else {
2016 // We use the index of the slot with the lowest address as an index for the
2017 // FPU register spill slot. In terms of indexes this relation is inverted:
2018 // so we have to take the highest index.
2019 const intptr_t slot_idx =
2020 compiler::target::frame_layout.FrameSlotForVariableIndex(
2021 -(cpu_spill_slot_count_ + idx * kDoubleSpillFactor +
2022 (kDoubleSpillFactor - 1)));
2023
2024 Location location;
2025 if ((range->representation() == kUnboxedFloat32x4) ||
2026 (range->representation() == kUnboxedInt32x4) ||
2027 (range->representation() == kUnboxedFloat64x2)) {
2028 ASSERT(need_quad);
2029 location = Location::QuadStackSlot(slot_idx, FPREG);
2030 } else {
2031 ASSERT(range->representation() == kUnboxedFloat ||
2032 range->representation() == kUnboxedDouble);
2033 location = Location::DoubleStackSlot(slot_idx, FPREG);
2034 }
2035 range->set_spill_slot(location);
2036 }
2037
2038 spilled_.Add(range);
2039}
2040
2041void FlowGraphAllocator::MarkAsObjectAtSafepoints(LiveRange* range) {
2042 Location spill_slot = range->spill_slot();
2043 intptr_t stack_index = spill_slot.stack_index();
2044 if (spill_slot.base_reg() == FPREG) {
2045 stack_index = -compiler::target::frame_layout.VariableIndexForFrameSlot(
2046 spill_slot.stack_index());
2047 }
2048 ASSERT(stack_index >= 0);
2049 while (range != NULL) {
2050 for (SafepointPosition* safepoint = range->first_safepoint();
2051 safepoint != NULL; safepoint = safepoint->next()) {
2052 // Mark the stack slot as having an object.
2053 safepoint->locs()->SetStackBit(stack_index);
2054 }
2055 range = range->next_sibling();
2056 }
2057}
2058
2059void FlowGraphAllocator::Spill(LiveRange* range) {
2060 LiveRange* parent = GetLiveRange(range->vreg());
2061 if (parent->spill_slot().IsInvalid()) {
2062 AllocateSpillSlotFor(parent);
2063 if (range->representation() == kTagged) {
2064 MarkAsObjectAtSafepoints(parent);
2065 }
2066 }
2067 range->set_assigned_location(parent->spill_slot());
2068 ConvertAllUses(range);
2069}
2070
2071intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated(
2072 intptr_t reg,
2073 LiveRange* unallocated) {
2074 intptr_t intersection = kMaxPosition;
2075 for (intptr_t i = 0; i < registers_[reg]->length(); i++) {
2076 LiveRange* allocated = (*registers_[reg])[i];
2077 if (allocated == NULL) continue;
2078
2079 UseInterval* allocated_head =
2080 allocated->finger()->first_pending_use_interval();
2081 if (allocated_head->start() >= intersection) continue;
2082
2083 const intptr_t pos = FirstIntersection(
2084 unallocated->finger()->first_pending_use_interval(), allocated_head);
2085 if (pos < intersection) intersection = pos;
2086 }
2087 return intersection;
2088}
2089
2090void ReachingDefs::AddPhi(PhiInstr* phi) {
2091 if (phi->reaching_defs() == NULL) {
2092 Zone* zone = flow_graph_.zone();
2093 phi->set_reaching_defs(
2094 new (zone) BitVector(zone, flow_graph_.max_virtual_register_number()));
2095
2096 // Compute initial set reaching defs set.
2097 bool depends_on_phi = false;
2098 for (intptr_t i = 0; i < phi->InputCount(); i++) {
2099 Definition* input = phi->InputAt(i)->definition();
2100 if (input->IsPhi()) {
2101 depends_on_phi = true;
2102 }
2103 phi->reaching_defs()->Add(input->ssa_temp_index());
2104 if (phi->HasPairRepresentation()) {
2105 phi->reaching_defs()->Add(ToSecondPairVreg(input->ssa_temp_index()));
2106 }
2107 }
2108
2109 // If this phi depends on another phi then we need fix point iteration.
2110 if (depends_on_phi) phis_.Add(phi);
2111 }
2112}
2113
2114void ReachingDefs::Compute() {
2115 // Transitively collect all phis that are used by the given phi.
2116 for (intptr_t i = 0; i < phis_.length(); i++) {
2117 PhiInstr* phi = phis_[i];
2118
2119 // Add all phis that affect this phi to the list.
2120 for (intptr_t i = 0; i < phi->InputCount(); i++) {
2121 PhiInstr* input_phi = phi->InputAt(i)->definition()->AsPhi();
2122 if (input_phi != NULL) {
2123 AddPhi(input_phi);
2124 }
2125 }
2126 }
2127
2128 // Propagate values until fix point is reached.
2129 bool changed;
2130 do {
2131 changed = false;
2132 for (intptr_t i = 0; i < phis_.length(); i++) {
2133 PhiInstr* phi = phis_[i];
2134 for (intptr_t i = 0; i < phi->InputCount(); i++) {
2135 PhiInstr* input_phi = phi->InputAt(i)->definition()->AsPhi();
2136 if (input_phi != NULL) {
2137 if (phi->reaching_defs()->AddAll(input_phi->reaching_defs())) {
2138 changed = true;
2139 }
2140 }
2141 }
2142 }
2143 } while (changed);
2144
2145 phis_.Clear();
2146}
2147
2148BitVector* ReachingDefs::Get(PhiInstr* phi) {
2149 if (phi->reaching_defs() == NULL) {
2150 ASSERT(phis_.is_empty());
2151 AddPhi(phi);
2152 Compute();
2153 }
2154 return phi->reaching_defs();
2155}
2156
2157bool FlowGraphAllocator::AllocateFreeRegister(LiveRange* unallocated) {
2158 intptr_t candidate = kNoRegister;
2159 intptr_t free_until = 0;
2160
2161 // If hint is available try hint first.
2162 // TODO(vegorov): ensure that phis are hinted on the back edge.
2163 Location hint = unallocated->finger()->FirstHint();
2164 if (hint.IsMachineRegister()) {
2165 if (!blocked_registers_[hint.register_code()]) {
2166 free_until =
2167 FirstIntersectionWithAllocated(hint.register_code(), unallocated);
2168 candidate = hint.register_code();
2169 }
2170
2171 TRACE_ALLOC(THR_Print("found hint %s for v%" Pd ": free until %" Pd "\n",
2172 hint.Name(), unallocated->vreg(), free_until));
2173 } else {
2174 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
2175 if (!blocked_registers_[reg] && (registers_[reg]->length() == 0)) {
2176 candidate = reg;
2177 free_until = kMaxPosition;
2178 break;
2179 }
2180 }
2181 }
2182
2183 ASSERT(0 <= kMaxPosition);
2184 if (free_until != kMaxPosition) {
2185 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
2186 if (blocked_registers_[reg] || (reg == candidate)) continue;
2187 const intptr_t intersection =
2188 FirstIntersectionWithAllocated(reg, unallocated);
2189 if (intersection > free_until) {
2190 candidate = reg;
2191 free_until = intersection;
2192 if (free_until == kMaxPosition) break;
2193 }
2194 }
2195 }
2196
2197 // All registers are blocked by active ranges.
2198 if (free_until <= unallocated->Start()) return false;
2199
2200 // We have a very good candidate (either hinted to us or completely free).
2201 // If we are in a loop try to reduce number of moves on the back edge by
2202 // searching for a candidate that does not interfere with phis on the back
2203 // edge.
2204 LoopInfo* loop_info = BlockEntryAt(unallocated->Start())->loop_info();
2205 if ((unallocated->vreg() >= 0) && (loop_info != nullptr) &&
2206 (free_until >= extra_loop_info_[loop_info->id()]->end) &&
2207 extra_loop_info_[loop_info->id()]->backedge_interference->Contains(
2208 unallocated->vreg())) {
2209 GrowableArray<bool> used_on_backedge(number_of_registers_);
2210 for (intptr_t i = 0; i < number_of_registers_; i++) {
2211 used_on_backedge.Add(false);
2212 }
2213
2214 for (PhiIterator it(loop_info->header()->AsJoinEntry()); !it.Done();
2215 it.Advance()) {
2216 PhiInstr* phi = it.Current();
2217 ASSERT(phi->is_alive());
2218 const intptr_t phi_vreg = phi->ssa_temp_index();
2219 LiveRange* range = GetLiveRange(phi_vreg);
2220 if (range->assigned_location().kind() == register_kind_) {
2221 const intptr_t reg = range->assigned_location().register_code();
2222 if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {
2223 used_on_backedge[reg] = true;
2224 }
2225 }
2226 if (phi->HasPairRepresentation()) {
2227 const intptr_t second_phi_vreg = ToSecondPairVreg(phi_vreg);
2228 LiveRange* second_range = GetLiveRange(second_phi_vreg);
2229 if (second_range->assigned_location().kind() == register_kind_) {
2230 const intptr_t reg =
2231 second_range->assigned_location().register_code();
2232 if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {
2233 used_on_backedge[reg] = true;
2234 }
2235 }
2236 }
2237 }
2238
2239 if (used_on_backedge[candidate]) {
2240 TRACE_ALLOC(THR_Print("considering %s for v%" Pd
2241 ": has interference on the back edge"
2242 " {loop [%" Pd ", %" Pd ")}\n",
2243 MakeRegisterLocation(candidate).Name(),
2244 unallocated->vreg(),
2245 extra_loop_info_[loop_info->id()]->start,
2246 extra_loop_info_[loop_info->id()]->end));
2247 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
2248 if (blocked_registers_[reg] || (reg == candidate) ||
2249 used_on_backedge[reg]) {
2250 continue;
2251 }
2252
2253 const intptr_t intersection =
2254 FirstIntersectionWithAllocated(reg, unallocated);
2255 if (intersection >= free_until) {
2256 candidate = reg;
2257 free_until = intersection;
2258 TRACE_ALLOC(THR_Print(
2259 "found %s for v%" Pd " with no interference on the back edge\n",
2260 MakeRegisterLocation(candidate).Name(), candidate));
2261 break;
2262 }
2263 }
2264 }
2265 }
2266
2267 TRACE_ALLOC(THR_Print("assigning free register "));
2268 TRACE_ALLOC(MakeRegisterLocation(candidate).Print());
2269 TRACE_ALLOC(THR_Print(" to v%" Pd "\n", unallocated->vreg()));
2270
2271 if (free_until != kMaxPosition) {
2272 // There was an intersection. Split unallocated.
2273 TRACE_ALLOC(THR_Print(" splitting at %" Pd "\n", free_until));
2274 LiveRange* tail = unallocated->SplitAt(free_until);
2275 AddToUnallocated(tail);
2276 }
2277
2278 registers_[candidate]->Add(unallocated);
2279 unallocated->set_assigned_location(MakeRegisterLocation(candidate));
2280 return true;
2281}
2282
2283bool FlowGraphAllocator::RangeHasOnlyUnconstrainedUsesInLoop(LiveRange* range,
2284 intptr_t loop_id) {
2285 if (range->vreg() >= 0) {
2286 LiveRange* parent = GetLiveRange(range->vreg());
2287 return parent->HasOnlyUnconstrainedUsesInLoop(loop_id);
2288 }
2289 return false;
2290}
2291
2292bool FlowGraphAllocator::IsCheapToEvictRegisterInLoop(LoopInfo* loop_info,
2293 intptr_t reg) {
2294 const intptr_t loop_start = extra_loop_info_[loop_info->id()]->start;
2295 const intptr_t loop_end = extra_loop_info_[loop_info->id()]->end;
2296
2297 for (intptr_t i = 0; i < registers_[reg]->length(); i++) {
2298 LiveRange* allocated = (*registers_[reg])[i];
2299 UseInterval* interval = allocated->finger()->first_pending_use_interval();
2300 if (interval->Contains(loop_start)) {
2301 if (!RangeHasOnlyUnconstrainedUsesInLoop(allocated, loop_info->id())) {
2302 return false;
2303 }
2304 } else if (interval->start() < loop_end) {
2305 return false;
2306 }
2307 }
2308
2309 return true;
2310}
2311
2312bool FlowGraphAllocator::HasCheapEvictionCandidate(LiveRange* phi_range) {
2313 ASSERT(phi_range->is_loop_phi());
2314
2315 BlockEntryInstr* header = BlockEntryAt(phi_range->Start());
2316
2317 ASSERT(header->IsLoopHeader());
2318 ASSERT(phi_range->Start() == header->start_pos());
2319
2320 for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) {
2321 if (blocked_registers_[reg]) continue;
2322 if (IsCheapToEvictRegisterInLoop(header->loop_info(), reg)) {
2323 return true;
2324 }
2325 }
2326
2327 return false;
2328}
2329
2330void FlowGraphAllocator::AllocateAnyRegister(LiveRange* unallocated) {
2331 // If a loop phi has no register uses we might still want to allocate it
2332 // to the register to reduce amount of memory moves on the back edge.
2333 // This is possible if there is a register blocked by a range that can be
2334 // cheaply evicted i.e. it has no register beneficial uses inside the
2335 // loop.
2336 UsePosition* register_use =
2337 unallocated->finger()->FirstRegisterUse(unallocated->Start());
2338 if ((register_use == NULL) &&
2339 !(unallocated->is_loop_phi() && HasCheapEvictionCandidate(unallocated))) {
2340 Spill(unallocated);
2341 return;
2342 }
2343
2344 intptr_t candidate = kNoRegister;
2345 intptr_t free_until = 0;
2346 intptr_t blocked_at = kMaxPosition;
2347
2348 for (int reg = 0; reg < NumberOfRegisters(); ++reg) {
2349 if (blocked_registers_[reg]) continue;
2350 if (UpdateFreeUntil(reg, unallocated, &free_until, &blocked_at)) {
2351 candidate = reg;
2352 }
2353 }
2354
2355 const intptr_t register_use_pos =
2356 (register_use != NULL) ? register_use->pos() : unallocated->Start();
2357 if (free_until < register_use_pos) {
2358 // Can't acquire free register. Spill until we really need one.
2359 ASSERT(unallocated->Start() < ToInstructionStart(register_use_pos));
2360 SpillBetween(unallocated, unallocated->Start(), register_use->pos());
2361 return;
2362 }
2363
2364 ASSERT(candidate != kNoRegister);
2365
2366 TRACE_ALLOC(THR_Print("assigning blocked register "));
2367 TRACE_ALLOC(MakeRegisterLocation(candidate).Print());
2368 TRACE_ALLOC(THR_Print(" to live range v%" Pd " until %" Pd "\n",
2369 unallocated->vreg(), blocked_at));
2370
2371 if (blocked_at < unallocated->End()) {
2372 // Register is blocked before the end of the live range. Split the range
2373 // at latest at blocked_at position.
2374 LiveRange* tail =
2375 SplitBetween(unallocated, unallocated->Start(), blocked_at + 1);
2376 AddToUnallocated(tail);
2377 }
2378
2379 AssignNonFreeRegister(unallocated, candidate);
2380}
2381
2382bool FlowGraphAllocator::UpdateFreeUntil(intptr_t reg,
2383 LiveRange* unallocated,
2384 intptr_t* cur_free_until,
2385 intptr_t* cur_blocked_at) {
2386 intptr_t free_until = kMaxPosition;
2387 intptr_t blocked_at = kMaxPosition;
2388 const intptr_t start = unallocated->Start();
2389
2390 for (intptr_t i = 0; i < registers_[reg]->length(); i++) {
2391 LiveRange* allocated = (*registers_[reg])[i];
2392
2393 UseInterval* first_pending_use_interval =
2394 allocated->finger()->first_pending_use_interval();
2395 if (first_pending_use_interval->Contains(start)) {
2396 // This is an active interval.
2397 if (allocated->vreg() < 0) {
2398 // This register blocked by an interval that
2399 // can't be spilled.
2400 return false;
2401 }
2402
2403 UsePosition* use = allocated->finger()->FirstInterferingUse(start);
2404 if ((use != NULL) && ((ToInstructionStart(use->pos()) - start) <= 1)) {
2405 // This register is blocked by interval that is used
2406 // as register in the current instruction and can't
2407 // be spilled.
2408 return false;
2409 }
2410
2411 const intptr_t use_pos = (use != NULL) ? use->pos() : allocated->End();
2412
2413 if (use_pos < free_until) free_until = use_pos;
2414 } else {
2415 // This is inactive interval.
2416 const intptr_t intersection = FirstIntersection(
2417 first_pending_use_interval, unallocated->first_use_interval());
2418 if (intersection != kMaxPosition) {
2419 if (intersection < free_until) free_until = intersection;
2420 if (allocated->vreg() == kNoVirtualRegister) blocked_at = intersection;
2421 }
2422 }
2423
2424 if (free_until <= *cur_free_until) {
2425 return false;
2426 }
2427 }
2428
2429 ASSERT(free_until > *cur_free_until);
2430 *cur_free_until = free_until;
2431 *cur_blocked_at = blocked_at;
2432 return true;
2433}
2434
2435void FlowGraphAllocator::RemoveEvicted(intptr_t reg, intptr_t first_evicted) {
2436 intptr_t to = first_evicted;
2437 intptr_t from = first_evicted + 1;
2438 while (from < registers_[reg]->length()) {
2439 LiveRange* allocated = (*registers_[reg])[from++];
2440 if (allocated != NULL) (*registers_[reg])[to++] = allocated;
2441 }
2442 registers_[reg]->TruncateTo(to);
2443}
2444
2445void FlowGraphAllocator::AssignNonFreeRegister(LiveRange* unallocated,
2446 intptr_t reg) {
2447 intptr_t first_evicted = -1;
2448 for (intptr_t i = registers_[reg]->length() - 1; i >= 0; i--) {
2449 LiveRange* allocated = (*registers_[reg])[i];
2450 if (allocated->vreg() < 0) continue; // Can't be evicted.
2451 if (EvictIntersection(allocated, unallocated)) {
2452 // If allocated was not spilled convert all pending uses.
2453 if (allocated->assigned_location().IsMachineRegister()) {
2454 ASSERT(allocated->End() <= unallocated->Start());
2455 ConvertAllUses(allocated);
2456 }
2457 (*registers_[reg])[i] = NULL;
2458 first_evicted = i;
2459 }
2460 }
2461
2462 // Remove evicted ranges from the array.
2463 if (first_evicted != -1) RemoveEvicted(reg, first_evicted);
2464
2465 registers_[reg]->Add(unallocated);
2466 unallocated->set_assigned_location(MakeRegisterLocation(reg));
2467}
2468
2469bool FlowGraphAllocator::EvictIntersection(LiveRange* allocated,
2470 LiveRange* unallocated) {
2471 UseInterval* first_unallocated =
2472 unallocated->finger()->first_pending_use_interval();
2473 const intptr_t intersection = FirstIntersection(
2474 allocated->finger()->first_pending_use_interval(), first_unallocated);
2475 if (intersection == kMaxPosition) return false;
2476
2477 const intptr_t spill_position = first_unallocated->start();
2478 UsePosition* use = allocated->finger()->FirstInterferingUse(spill_position);
2479 if (use == NULL) {
2480 // No register uses after this point.
2481 SpillAfter(allocated, spill_position);
2482 } else {
2483 const intptr_t restore_position =
2484 (spill_position < intersection) ? MinPosition(intersection, use->pos())
2485 : use->pos();
2486
2487 SpillBetween(allocated, spill_position, restore_position);
2488 }
2489
2490 return true;
2491}
2492
2493MoveOperands* FlowGraphAllocator::AddMoveAt(intptr_t pos,
2494 Location to,
2495 Location from) {
2496 ASSERT(!IsBlockEntry(pos));
2497
2498 // Now that the GraphEntry (B0) does no longer have any parameter instructions
2499 // in it so we should not attempt to add parallel moves to it.
2500 ASSERT(pos >= kNormalEntryPos);
2501
2502 ParallelMoveInstr* parallel_move = NULL;
2503 Instruction* instr = InstructionAt(pos);
2504 if (auto entry = instr->AsFunctionEntry()) {
2505 // Parallel moves added to the FunctionEntry will be added after the block
2506 // entry.
2507 parallel_move = CreateParallelMoveAfter(entry, pos);
2508 } else if (IsInstructionStartPosition(pos)) {
2509 parallel_move = CreateParallelMoveBefore(instr, pos);
2510 } else {
2511 parallel_move = CreateParallelMoveAfter(instr, pos);
2512 }
2513
2514 return parallel_move->AddMove(to, from);
2515}
2516
2517void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) {
2518 ASSERT(!loc.IsPairLocation());
2519 ASSERT(use->location_slot() != NULL);
2520 Location* slot = use->location_slot();
2521 ASSERT(slot->IsUnallocated());
2522 TRACE_ALLOC(THR_Print(" use at %" Pd " converted to ", use->pos()));
2523 TRACE_ALLOC(loc.Print());
2524 TRACE_ALLOC(THR_Print("\n"));
2525 *slot = loc;
2526}
2527
2528void FlowGraphAllocator::ConvertAllUses(LiveRange* range) {
2529 if (range->vreg() == kNoVirtualRegister) return;
2530
2531 const Location loc = range->assigned_location();
2532 ASSERT(!loc.IsInvalid());
2533
2534 TRACE_ALLOC(THR_Print("range [%" Pd ", %" Pd ") "
2535 "for v%" Pd " has been allocated to ",
2536 range->Start(), range->End(), range->vreg()));
2537 TRACE_ALLOC(loc.Print());
2538 TRACE_ALLOC(THR_Print(":\n"));
2539
2540 for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) {
2541 ConvertUseTo(use, loc);
2542 }
2543
2544 // Add live registers at all safepoints for instructions with slow-path
2545 // code.
2546 if (loc.IsMachineRegister()) {
2547 for (SafepointPosition* safepoint = range->first_safepoint();
2548 safepoint != NULL; safepoint = safepoint->next()) {
2549 if (!safepoint->locs()->always_calls()) {
2550 ASSERT(safepoint->locs()->can_call());
2551 safepoint->locs()->live_registers()->Add(loc, range->representation());
2552 }
2553 }
2554 }
2555}
2556
2557void FlowGraphAllocator::AdvanceActiveIntervals(const intptr_t start) {
2558 for (intptr_t reg = 0; reg < NumberOfRegisters(); reg++) {
2559 if (registers_[reg]->is_empty()) continue;
2560
2561 intptr_t first_evicted = -1;
2562 for (intptr_t i = registers_[reg]->length() - 1; i >= 0; i--) {
2563 LiveRange* range = (*registers_[reg])[i];
2564 if (range->finger()->Advance(start)) {
2565 ConvertAllUses(range);
2566 (*registers_[reg])[i] = NULL;
2567 first_evicted = i;
2568 }
2569 }
2570
2571 if (first_evicted != -1) RemoveEvicted(reg, first_evicted);
2572 }
2573}
2574
2575bool LiveRange::Contains(intptr_t pos) const {
2576 if (!CanCover(pos)) return false;
2577
2578 for (UseInterval* interval = first_use_interval_; interval != NULL;
2579 interval = interval->next()) {
2580 if (interval->Contains(pos)) {
2581 return true;
2582 }
2583 }
2584
2585 return false;
2586}
2587
2588void FlowGraphAllocator::AssignSafepoints(Definition* defn, LiveRange* range) {
2589 for (intptr_t i = safepoints_.length() - 1; i >= 0; i--) {
2590 Instruction* safepoint_instr = safepoints_[i];
2591 if (safepoint_instr == defn) {
2592 // The value is not live until after the definition is fully executed,
2593 // don't assign the safepoint inside the definition itself to
2594 // definition's liverange.
2595 continue;
2596 }
2597
2598 const intptr_t pos = GetLifetimePosition(safepoint_instr);
2599 if (range->End() <= pos) break;
2600
2601 if (range->Contains(pos)) {
2602 range->AddSafepoint(pos, safepoint_instr->locs());
2603 }
2604 }
2605}
2606
2607static inline bool ShouldBeAllocatedBefore(LiveRange* a, LiveRange* b) {
2608 // TODO(vegorov): consider first hint position when ordering live ranges.
2609 return a->Start() <= b->Start();
2610}
2611
2612static void AddToSortedListOfRanges(GrowableArray<LiveRange*>* list,
2613 LiveRange* range) {
2614 range->finger()->Initialize(range);
2615
2616 if (list->is_empty()) {
2617 list->Add(range);
2618 return;
2619 }
2620
2621 for (intptr_t i = list->length() - 1; i >= 0; i--) {
2622 if (ShouldBeAllocatedBefore(range, (*list)[i])) {
2623 list->InsertAt(i + 1, range);
2624 return;
2625 }
2626 }
2627 list->InsertAt(0, range);
2628}
2629
2630void FlowGraphAllocator::AddToUnallocated(LiveRange* range) {
2631 AddToSortedListOfRanges(&unallocated_, range);
2632}
2633
2634void FlowGraphAllocator::CompleteRange(LiveRange* range, Location::Kind kind) {
2635 switch (kind) {
2636 case Location::kRegister:
2637 AddToSortedListOfRanges(&unallocated_cpu_, range);
2638 break;
2639
2640 case Location::kFpuRegister:
2641 AddToSortedListOfRanges(&unallocated_xmm_, range);
2642 break;
2643
2644 default:
2645 UNREACHABLE();
2646 }
2647}
2648
2649#if defined(DEBUG)
2650bool FlowGraphAllocator::UnallocatedIsSorted() {
2651 for (intptr_t i = unallocated_.length() - 1; i >= 1; i--) {
2652 LiveRange* a = unallocated_[i];
2653 LiveRange* b = unallocated_[i - 1];
2654 if (!ShouldBeAllocatedBefore(a, b)) {
2655 UNREACHABLE();
2656 return false;
2657 }
2658 }
2659 return true;
2660}
2661#endif
2662
2663void FlowGraphAllocator::PrepareForAllocation(
2664 Location::Kind register_kind,
2665 intptr_t number_of_registers,
2666 const GrowableArray<LiveRange*>& unallocated,
2667 LiveRange** blocking_ranges,
2668 bool* blocked_registers) {
2669 register_kind_ = register_kind;
2670 number_of_registers_ = number_of_registers;
2671
2672 blocked_registers_.Clear();
2673 registers_.Clear();
2674 for (intptr_t i = 0; i < number_of_registers_; i++) {
2675 blocked_registers_.Add(false);
2676 registers_.Add(new ZoneGrowableArray<LiveRange*>);
2677 }
2678 ASSERT(unallocated_.is_empty());
2679 unallocated_.AddArray(unallocated);
2680
2681 for (intptr_t reg = 0; reg < number_of_registers; reg++) {
2682 blocked_registers_[reg] = blocked_registers[reg];
2683 ASSERT(registers_[reg]->is_empty());
2684
2685 LiveRange* range = blocking_ranges[reg];
2686 if (range != NULL) {
2687 range->finger()->Initialize(range);
2688 registers_[reg]->Add(range);
2689 }
2690 }
2691}
2692
2693void FlowGraphAllocator::AllocateUnallocatedRanges() {
2694#if defined(DEBUG)
2695 ASSERT(UnallocatedIsSorted());
2696#endif
2697
2698 while (!unallocated_.is_empty()) {
2699 LiveRange* range = unallocated_.RemoveLast();
2700 const intptr_t start = range->Start();
2701 TRACE_ALLOC(THR_Print("Processing live range for v%" Pd " "
2702 "starting at %" Pd "\n",
2703 range->vreg(), start));
2704
2705 // TODO(vegorov): eagerly spill liveranges without register uses.
2706 AdvanceActiveIntervals(start);
2707
2708 if (!AllocateFreeRegister(range)) {
2709 if (intrinsic_mode_) {
2710 // No spilling when compiling intrinsics.
2711 // TODO(fschneider): Handle spilling in intrinsics. For now, the
2712 // IR has to be built so that there are enough free registers.
2713 UNREACHABLE();
2714 }
2715 AllocateAnyRegister(range);
2716 }
2717 }
2718
2719 // All allocation decisions were done.
2720 ASSERT(unallocated_.is_empty());
2721
2722 // Finish allocation.
2723 AdvanceActiveIntervals(kMaxPosition);
2724 TRACE_ALLOC(THR_Print("Allocation completed\n"));
2725}
2726
2727bool FlowGraphAllocator::TargetLocationIsSpillSlot(LiveRange* range,
2728 Location target) {
2729 return GetLiveRange(range->vreg())->spill_slot().Equals(target);
2730}
2731
2732void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* parent,
2733 BlockEntryInstr* source_block,
2734 BlockEntryInstr* target_block) {
2735 TRACE_ALLOC(THR_Print("Connect v%" Pd " on the edge B%" Pd " -> B%" Pd "\n",
2736 parent->vreg(), source_block->block_id(),
2737 target_block->block_id()));
2738 if (parent->next_sibling() == NULL) {
2739 // Nothing to connect. The whole range was allocated to the same location.
2740 TRACE_ALLOC(THR_Print("range v%" Pd " has no siblings\n", parent->vreg()));
2741 return;
2742 }
2743
2744 const intptr_t source_pos = source_block->end_pos() - 1;
2745 ASSERT(IsInstructionEndPosition(source_pos));
2746
2747 const intptr_t target_pos = target_block->start_pos();
2748
2749 Location target;
2750 Location source;
2751
2752#if defined(INCLUDE_LINEAR_SCAN_TRACING_CODE)
2753 LiveRange* source_cover = NULL;
2754 LiveRange* target_cover = NULL;
2755#endif
2756
2757 LiveRange* range = parent;
2758 while ((range != NULL) && (source.IsInvalid() || target.IsInvalid())) {
2759 if (range->CanCover(source_pos)) {
2760 ASSERT(source.IsInvalid());
2761 source = range->assigned_location();
2762#if defined(INCLUDE_LINEAR_SCAN_TRACING_CODE)
2763 source_cover = range;
2764#endif
2765 }
2766 if (range->CanCover(target_pos)) {
2767 ASSERT(target.IsInvalid());
2768 target = range->assigned_location();
2769#if defined(INCLUDE_LINEAR_SCAN_TRACING_CODE)
2770 target_cover = range;
2771#endif
2772 }
2773
2774 range = range->next_sibling();
2775 }
2776
2777 TRACE_ALLOC(THR_Print("connecting v%" Pd " between [%" Pd ", %" Pd ") {%s} "
2778 "to [%" Pd ", %" Pd ") {%s}\n",
2779 parent->vreg(), source_cover->Start(),
2780 source_cover->End(), source.Name(),
2781 target_cover->Start(), target_cover->End(),
2782 target.Name()));
2783
2784 // Siblings were allocated to the same register.
2785 if (source.Equals(target)) return;
2786
2787 // Values are eagerly spilled. Spill slot already contains appropriate value.
2788 if (TargetLocationIsSpillSlot(parent, target)) {
2789 return;
2790 }
2791
2792 Instruction* last = source_block->last_instruction();
2793 if ((last->SuccessorCount() == 1) && !source_block->IsGraphEntry()) {
2794 ASSERT(last->IsGoto());
2795 last->AsGoto()->GetParallelMove()->AddMove(target, source);
2796 } else {
2797 target_block->GetParallelMove()->AddMove(target, source);
2798 }
2799}
2800
2801void FlowGraphAllocator::ResolveControlFlow() {
2802 // Resolve linear control flow between touching split siblings
2803 // inside basic blocks.
2804 for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) {
2805 LiveRange* range = live_ranges_[vreg];
2806 if (range == NULL) continue;
2807
2808 while (range->next_sibling() != NULL) {
2809 LiveRange* sibling = range->next_sibling();
2810 TRACE_ALLOC(THR_Print("connecting [%" Pd ", %" Pd ") [", range->Start(),
2811 range->End()));
2812 TRACE_ALLOC(range->assigned_location().Print());
2813 TRACE_ALLOC(THR_Print("] to [%" Pd ", %" Pd ") [", sibling->Start(),
2814 sibling->End()));
2815 TRACE_ALLOC(sibling->assigned_location().Print());
2816 TRACE_ALLOC(THR_Print("]\n"));
2817 if ((range->End() == sibling->Start()) &&
2818 !TargetLocationIsSpillSlot(range, sibling->assigned_location()) &&
2819 !range->assigned_location().Equals(sibling->assigned_location()) &&
2820 !IsBlockEntry(range->End())) {
2821 AddMoveAt(sibling->Start(), sibling->assigned_location(),
2822 range->assigned_location());
2823 }
2824 range = sibling;
2825 }
2826 }
2827
2828 // Resolve non-linear control flow across branches.
2829 for (intptr_t i = 1; i < block_order_.length(); i++) {
2830 BlockEntryInstr* block = block_order_[i];
2831 BitVector* live = liveness_.GetLiveInSet(block);
2832 for (BitVector::Iterator it(live); !it.Done(); it.Advance()) {
2833 LiveRange* range = GetLiveRange(it.Current());
2834 for (intptr_t j = 0; j < block->PredecessorCount(); j++) {
2835 ConnectSplitSiblings(range, block->PredecessorAt(j), block);
2836 }
2837 }
2838 }
2839
2840 // Eagerly spill values.
2841 // TODO(vegorov): if value is spilled on the cold path (e.g. by the call)
2842 // this will cause spilling to occur on the fast path (at the definition).
2843 for (intptr_t i = 0; i < spilled_.length(); i++) {
2844 LiveRange* range = spilled_[i];
2845 if (!range->assigned_location().Equals(range->spill_slot())) {
2846 AddMoveAt(range->Start() + 1, range->spill_slot(),
2847 range->assigned_location());
2848 }
2849 }
2850}
2851
2852static Representation RepresentationForRange(Representation definition_rep) {
2853 if (definition_rep == kUnboxedInt64) {
2854 // kUnboxedInt64 is split into two ranges, each of which are kUntagged.
2855 return kUntagged;
2856 } else if (definition_rep == kUnboxedUint32) {
2857 // kUnboxedUint32 is untagged.
2858 return kUntagged;
2859 }
2860 return definition_rep;
2861}
2862
2863void FlowGraphAllocator::CollectRepresentations() {
2864 // Constants.
2865 GraphEntryInstr* graph_entry = flow_graph_.graph_entry();
2866 auto initial_definitions = graph_entry->initial_definitions();
2867 for (intptr_t i = 0; i < initial_definitions->length(); ++i) {
2868 Definition* def = (*initial_definitions)[i];
2869 value_representations_[def->ssa_temp_index()] =
2870 RepresentationForRange(def->representation());
2871 ASSERT(!def->HasPairRepresentation());
2872 }
2873
2874 for (BlockIterator it = flow_graph_.reverse_postorder_iterator(); !it.Done();
2875 it.Advance()) {
2876 BlockEntryInstr* block = it.Current();
2877
2878 if (auto entry = block->AsBlockEntryWithInitialDefs()) {
2879 initial_definitions = entry->initial_definitions();
2880 for (intptr_t i = 0; i < initial_definitions->length(); ++i) {
2881 Definition* def = (*initial_definitions)[i];
2882 value_representations_[def->ssa_temp_index()] =
2883 RepresentationForRange(def->representation());
2884 if (def->HasPairRepresentation()) {
2885 value_representations_[ToSecondPairVreg(def->ssa_temp_index())] =
2886 RepresentationForRange(def->representation());
2887 }
2888 }
2889 } else if (auto join = block->AsJoinEntry()) {
2890 for (PhiIterator it(join); !it.Done(); it.Advance()) {
2891 PhiInstr* phi = it.Current();
2892 ASSERT(phi != NULL && phi->ssa_temp_index() >= 0);
2893 value_representations_[phi->ssa_temp_index()] =
2894 RepresentationForRange(phi->representation());
2895 if (phi->HasPairRepresentation()) {
2896 value_representations_[ToSecondPairVreg(phi->ssa_temp_index())] =
2897 RepresentationForRange(phi->representation());
2898 }
2899 }
2900 }
2901
2902 // Normal instructions.
2903 for (ForwardInstructionIterator instr_it(block); !instr_it.Done();
2904 instr_it.Advance()) {
2905 Definition* def = instr_it.Current()->AsDefinition();
2906 if ((def != NULL) && (def->ssa_temp_index() >= 0)) {
2907 const intptr_t vreg = def->ssa_temp_index();
2908 value_representations_[vreg] =
2909 RepresentationForRange(def->representation());
2910 if (def->HasPairRepresentation()) {
2911 value_representations_[ToSecondPairVreg(vreg)] =
2912 RepresentationForRange(def->representation());
2913 }
2914 }
2915 }
2916 }
2917}
2918
2919void FlowGraphAllocator::AllocateRegisters() {
2920 CollectRepresentations();
2921
2922 liveness_.Analyze();
2923
2924 NumberInstructions();
2925
2926 BuildLiveRanges();
2927
2928 if (FLAG_print_ssa_liveranges && CompilerState::ShouldTrace()) {
2929 const Function& function = flow_graph_.function();
2930 THR_Print("-- [before ssa allocator] ranges [%s] ---------\n",
2931 function.ToFullyQualifiedCString());
2932 PrintLiveRanges();
2933 THR_Print("----------------------------------------------\n");
2934
2935 THR_Print("-- [before ssa allocator] ir [%s] -------------\n",
2936 function.ToFullyQualifiedCString());
2937 if (FLAG_support_il_printer) {
2938#ifndef PRODUCT
2939 FlowGraphPrinter printer(flow_graph_, true);
2940 printer.PrintBlocks();
2941#endif
2942 }
2943 THR_Print("----------------------------------------------\n");
2944 }
2945
2946 PrepareForAllocation(Location::kRegister, kNumberOfCpuRegisters,
2947 unallocated_cpu_, cpu_regs_, blocked_cpu_registers_);
2948 AllocateUnallocatedRanges();
2949 // GraphEntryInstr::fixed_slot_count() stack slots are reserved for catch
2950 // entries. When allocating a spill slot, AllocateSpillSlotFor() accounts for
2951 // these reserved slots and allocates spill slots on top of them.
2952 // However, if there are no spill slots allocated, we still need to reserve
2953 // slots for catch entries in the spill area.
2954 cpu_spill_slot_count_ = Utils::Maximum(
2955 spill_slots_.length(), flow_graph_.graph_entry()->fixed_slot_count());
2956 spill_slots_.Clear();
2957 quad_spill_slots_.Clear();
2958 untagged_spill_slots_.Clear();
2959
2960 PrepareForAllocation(Location::kFpuRegister, kNumberOfFpuRegisters,
2961 unallocated_xmm_, fpu_regs_, blocked_fpu_registers_);
2962 AllocateUnallocatedRanges();
2963 ResolveControlFlow();
2964
2965 GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
2966 ASSERT(entry != NULL);
2967 intptr_t double_spill_slot_count = spill_slots_.length() * kDoubleSpillFactor;
2968 entry->set_spill_slot_count(cpu_spill_slot_count_ + double_spill_slot_count);
2969
2970 if (FLAG_print_ssa_liveranges && CompilerState::ShouldTrace()) {
2971 const Function& function = flow_graph_.function();
2972
2973 THR_Print("-- [after ssa allocator] ranges [%s] ---------\n",
2974 function.ToFullyQualifiedCString());
2975 PrintLiveRanges();
2976 THR_Print("----------------------------------------------\n");
2977
2978 THR_Print("-- [after ssa allocator] ir [%s] -------------\n",
2979 function.ToFullyQualifiedCString());
2980 if (FLAG_support_il_printer) {
2981#ifndef PRODUCT
2982 FlowGraphPrinter printer(flow_graph_, true);
2983 printer.PrintBlocks();
2984#endif
2985 }
2986 THR_Print("----------------------------------------------\n");
2987 }
2988}
2989
2990} // namespace dart
2991