| // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| #include "vm/flow_graph_allocator.h" |
| |
| #include "vm/bit_vector.h" |
| #include "vm/intermediate_language.h" |
| #include "vm/il_printer.h" |
| #include "vm/flow_graph.h" |
| #include "vm/flow_graph_compiler.h" |
| #include "vm/parser.h" |
| |
| namespace dart { |
| |
| DEFINE_FLAG(bool, print_ssa_liveness, false, |
| "Print liveness for ssa variables."); |
| DEFINE_FLAG(bool, trace_ssa_allocator, false, |
| "Trace register allocation over SSA."); |
| DEFINE_FLAG(bool, print_ssa_liveranges, false, |
| "Print live ranges after allocation."); |
| |
| #if defined(DEBUG) |
| #define TRACE_ALLOC(statement) \ |
| do { \ |
| if (FLAG_trace_ssa_allocator) statement; \ |
| } while (0) |
| #else |
| #define TRACE_ALLOC(statement) |
| #endif |
| |
| |
| static const intptr_t kNoVirtualRegister = -1; |
| static const intptr_t kTempVirtualRegister = -2; |
| static const intptr_t kIllegalPosition = -1; |
| static const intptr_t kMaxPosition = 0x7FFFFFFF; |
| |
| static intptr_t MinPosition(intptr_t a, intptr_t b) { |
| return (a < b) ? a : b; |
| } |
| |
| |
| static bool IsInstructionStartPosition(intptr_t pos) { |
| return (pos & 1) == 0; |
| } |
| |
| |
| static bool IsInstructionEndPosition(intptr_t pos) { |
| return (pos & 1) == 1; |
| } |
| |
| |
| static intptr_t ToInstructionStart(intptr_t pos) { |
| return (pos & ~1); |
| } |
| |
| |
| static intptr_t ToInstructionEnd(intptr_t pos) { |
| return (pos | 1); |
| } |
| |
| |
| FlowGraphAllocator::FlowGraphAllocator(const FlowGraph& flow_graph) |
| : flow_graph_(flow_graph), |
| reaching_defs_(flow_graph), |
| value_representations_(flow_graph.max_virtual_register_number()), |
| block_order_(flow_graph.reverse_postorder()), |
| postorder_(flow_graph.postorder()), |
| liveness_(flow_graph), |
| vreg_count_(flow_graph.max_virtual_register_number()), |
| live_ranges_(flow_graph.max_virtual_register_number()), |
| cpu_regs_(), |
| fpu_regs_(), |
| blocked_cpu_registers_(), |
| blocked_fpu_registers_(), |
| cpu_spill_slot_count_(0) { |
| for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL); |
| for (intptr_t i = 0; i < vreg_count_; i++) { |
| value_representations_.Add(kNoRepresentation); |
| } |
| |
| // All registers are marked as "not blocked" (array initialized to false). |
| // Mark the unavailable ones as "blocked" (true). |
| for (intptr_t i = 0; i < kFirstFreeCpuRegister; i++) { |
| blocked_cpu_registers_[i] = true; |
| } |
| for (intptr_t i = kLastFreeCpuRegister + 1; i < kNumberOfCpuRegisters; i++) { |
| blocked_cpu_registers_[i] = true; |
| } |
| blocked_cpu_registers_[CTX] = true; |
| if (TMP != kNoRegister) { |
| blocked_cpu_registers_[TMP] = true; |
| } |
| if (PP != kNoRegister) { |
| blocked_cpu_registers_[PP] = true; |
| } |
| blocked_cpu_registers_[SPREG] = true; |
| blocked_cpu_registers_[FPREG] = true; |
| |
| // FpuTMP is used as scratch by optimized code and parallel move resolver. |
| blocked_fpu_registers_[FpuTMP] = true; |
| } |
| |
| |
| // Remove environments from the instructions which can't deoptimize. |
| void FlowGraphAllocator::EliminateEnvironments() { |
| for (intptr_t i = 0; i < block_order_.length(); ++i) { |
| BlockEntryInstr* block = block_order_[i]; |
| for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| Instruction* current = it.Current(); |
| if (!current->CanDeoptimize()) current->RemoveEnvironment(); |
| } |
| } |
| } |
| |
| |
| void SSALivenessAnalysis::ComputeInitialSets() { |
| const intptr_t block_count = postorder_.length(); |
| for (intptr_t i = 0; i < block_count; i++) { |
| BlockEntryInstr* block = postorder_[i]; |
| |
| BitVector* kill = kill_[i]; |
| BitVector* live_in = live_in_[i]; |
| |
| // Iterate backwards starting at the last instruction. |
| for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| Instruction* current = it.Current(); |
| |
| // Handle definitions. |
| Definition* current_def = current->AsDefinition(); |
| if ((current_def != NULL) && current_def->HasSSATemp()) { |
| kill->Add(current_def->ssa_temp_index()); |
| live_in->Remove(current_def->ssa_temp_index()); |
| } |
| |
| // Handle uses. |
| LocationSummary* locs = current->locs(); |
| ASSERT(locs->input_count() == current->InputCount()); |
| for (intptr_t j = 0; j < current->InputCount(); j++) { |
| Value* input = current->InputAt(j); |
| const intptr_t use = input->definition()->ssa_temp_index(); |
| |
| ASSERT(!locs->in(j).IsConstant() || input->BindsToConstant()); |
| if (locs->in(j).IsConstant()) continue; |
| |
| live_in->Add(use); |
| } |
| |
| // Add non-argument uses from the deoptimization environment (pushed |
| // arguments are not allocated by the register allocator). |
| if (current->env() != NULL) { |
| for (Environment::DeepIterator env_it(current->env()); |
| !env_it.Done(); |
| env_it.Advance()) { |
| Value* value = env_it.CurrentValue(); |
| if (!value->definition()->IsPushArgument() && |
| !value->BindsToConstant()) { |
| live_in->Add(value->definition()->ssa_temp_index()); |
| } |
| } |
| } |
| } |
| |
| // Handle phis. |
| if (block->IsJoinEntry()) { |
| JoinEntryInstr* join = block->AsJoinEntry(); |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| ASSERT(phi != NULL); |
| kill->Add(phi->ssa_temp_index()); |
| live_in->Remove(phi->ssa_temp_index()); |
| |
| // If a phi input is not defined by the corresponding predecessor it |
| // must be marked live-in for that predecessor. |
| for (intptr_t k = 0; k < phi->InputCount(); k++) { |
| Value* val = phi->InputAt(k); |
| if (val->BindsToConstant()) continue; |
| |
| BlockEntryInstr* pred = block->PredecessorAt(k); |
| const intptr_t use = val->definition()->ssa_temp_index(); |
| if (!kill_[pred->postorder_number()]->Contains(use)) { |
| live_in_[pred->postorder_number()]->Add(use); |
| } |
| } |
| } |
| } |
| } |
| |
| // Process initial definitions, ie, constants and incoming parameters. |
| for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); i++) { |
| intptr_t vreg = (*graph_entry_->initial_definitions())[i]->ssa_temp_index(); |
| kill_[graph_entry_->postorder_number()]->Add(vreg); |
| live_in_[graph_entry_->postorder_number()]->Remove(vreg); |
| } |
| |
| // Update initial live_in sets to match live_out sets. Has to be |
| // done in a separate path because of backwards branches. |
| for (intptr_t i = 0; i < block_count; i++) { |
| UpdateLiveIn(*postorder_[i]); |
| } |
| } |
| |
| |
| void LiveRange::AddUse(intptr_t pos, Location* location_slot) { |
| ASSERT(location_slot != NULL); |
| ASSERT((first_use_interval_->start_ <= pos) && |
| (pos <= first_use_interval_->end_)); |
| if ((uses_ != NULL) && |
| (uses_->pos() == pos) && |
| (uses_->location_slot() == location_slot)) { |
| return; |
| } |
| uses_ = new UsePosition(pos, uses_, location_slot); |
| } |
| |
| |
| void LiveRange::AddSafepoint(intptr_t pos, LocationSummary* locs) { |
| ASSERT(IsInstructionStartPosition(pos)); |
| SafepointPosition* safepoint = |
| new SafepointPosition(ToInstructionEnd(pos), locs); |
| |
| if (first_safepoint_ == NULL) { |
| ASSERT(last_safepoint_ == NULL); |
| first_safepoint_ = last_safepoint_ = safepoint; |
| } else { |
| ASSERT(last_safepoint_ != NULL); |
| // We assume that safepoints list is sorted by position and that |
| // safepoints are added in this order. |
| ASSERT(last_safepoint_->pos() < pos); |
| last_safepoint_->set_next(safepoint); |
| last_safepoint_ = safepoint; |
| } |
| } |
| |
| |
| void LiveRange::AddHintedUse(intptr_t pos, |
| Location* location_slot, |
| Location* hint) { |
| ASSERT(hint != NULL); |
| AddUse(pos, location_slot); |
| uses_->set_hint(hint); |
| } |
| |
| |
| void LiveRange::AddUseInterval(intptr_t start, intptr_t end) { |
| ASSERT(start < end); |
| |
| // Live ranges are being build by visiting instructions in post-order. |
| // This implies that use intervals will be perpended in a monotonically |
| // decreasing order. |
| if (first_use_interval() != NULL) { |
| // If the first use interval and the use interval we are adding |
| // touch then we can just extend the first interval to cover their |
| // union. |
| if (start >= first_use_interval()->start()) { |
| // The only case when we can add intervals with start greater than |
| // start of an already created interval is BlockLocation. |
| ASSERT((start == first_use_interval()->start()) || |
| (vreg() == kNoVirtualRegister)); |
| ASSERT(end <= first_use_interval()->end()); |
| return; |
| } else if (end == first_use_interval()->start()) { |
| first_use_interval()->start_ = start; |
| return; |
| } |
| |
| ASSERT(end < first_use_interval()->start()); |
| } |
| |
| first_use_interval_ = new UseInterval(start, end, first_use_interval_); |
| if (last_use_interval_ == NULL) { |
| ASSERT(first_use_interval_->next() == NULL); |
| last_use_interval_ = first_use_interval_; |
| } |
| } |
| |
| |
| void LiveRange::DefineAt(intptr_t pos) { |
| // Live ranges are being build by visiting instructions in post-order. |
| // This implies that use intervals will be prepended in a monotonically |
| // decreasing order. |
| // When we encounter a use of a value inside a block we optimistically |
| // expand the first use interval to cover the block from the start |
| // to the last use in the block and then we shrink it if we encounter |
| // definition of the value inside the same block. |
| if (first_use_interval_ == NULL) { |
| // Definition without a use. |
| first_use_interval_ = new UseInterval(pos, pos + 1, NULL); |
| last_use_interval_ = first_use_interval_; |
| } else { |
| // Shrink the first use interval. It was optimistically expanded to |
| // cover the the block from the start to the last use in the block. |
| ASSERT(first_use_interval_->start_ <= pos); |
| first_use_interval_->start_ = pos; |
| } |
| } |
| |
| |
| LiveRange* FlowGraphAllocator::GetLiveRange(intptr_t vreg) { |
| if (live_ranges_[vreg] == NULL) { |
| Representation rep = value_representations_[vreg]; |
| ASSERT(rep != kNoRepresentation); |
| live_ranges_[vreg] = new LiveRange(vreg, rep); |
| } |
| return live_ranges_[vreg]; |
| } |
| |
| |
| LiveRange* FlowGraphAllocator::MakeLiveRangeForTemporary() { |
| // Representation does not matter for temps. |
| Representation ignored = kNoRepresentation; |
| LiveRange* range = new LiveRange(kTempVirtualRegister, ignored); |
| #if defined(DEBUG) |
| temporaries_.Add(range); |
| #endif |
| return range; |
| } |
| |
| |
| void FlowGraphAllocator::BlockRegisterLocation(Location loc, |
| intptr_t from, |
| intptr_t to, |
| bool* blocked_registers, |
| LiveRange** blocking_ranges) { |
| if (blocked_registers[loc.register_code()]) { |
| return; |
| } |
| |
| if (blocking_ranges[loc.register_code()] == NULL) { |
| Representation ignored = kNoRepresentation; |
| LiveRange* range = new LiveRange(kNoVirtualRegister, ignored); |
| blocking_ranges[loc.register_code()] = range; |
| range->set_assigned_location(loc); |
| #if defined(DEBUG) |
| temporaries_.Add(range); |
| #endif |
| } |
| |
| blocking_ranges[loc.register_code()]->AddUseInterval(from, to); |
| } |
| |
| |
| // Block location from the start of the instruction to its end. |
| void FlowGraphAllocator::BlockLocation(Location loc, |
| intptr_t from, |
| intptr_t to) { |
| if (loc.IsRegister()) { |
| BlockRegisterLocation(loc, from, to, blocked_cpu_registers_, cpu_regs_); |
| } else if (loc.IsFpuRegister()) { |
| BlockRegisterLocation(loc, from, to, blocked_fpu_registers_, fpu_regs_); |
| } else { |
| UNREACHABLE(); |
| } |
| } |
| |
| |
| void LiveRange::Print() { |
| if (first_use_interval() == NULL) { |
| return; |
| } |
| |
| OS::Print(" live range v%"Pd" [%"Pd", %"Pd") in ", vreg(), Start(), End()); |
| assigned_location().Print(); |
| OS::Print("\n"); |
| |
| UsePosition* use_pos = uses_; |
| for (UseInterval* interval = first_use_interval_; |
| interval != NULL; |
| interval = interval->next()) { |
| OS::Print(" use interval [%"Pd", %"Pd")\n", |
| interval->start(), |
| interval->end()); |
| while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) { |
| OS::Print(" use at %"Pd"", use_pos->pos()); |
| if (use_pos->location_slot() != NULL) { |
| OS::Print(" as "); |
| use_pos->location_slot()->Print(); |
| } |
| OS::Print("\n"); |
| use_pos = use_pos->next(); |
| } |
| } |
| |
| if (next_sibling() != NULL) { |
| next_sibling()->Print(); |
| } |
| } |
| |
| |
| void FlowGraphAllocator::PrintLiveRanges() { |
| #if defined(DEBUG) |
| for (intptr_t i = 0; i < temporaries_.length(); i++) { |
| temporaries_[i]->Print(); |
| } |
| #endif |
| |
| for (intptr_t i = 0; i < live_ranges_.length(); i++) { |
| if (live_ranges_[i] != NULL) { |
| live_ranges_[i]->Print(); |
| } |
| } |
| } |
| |
| |
| // Returns true if all uses of the given range inside the given loop |
| // have Any allocation policy. |
| static bool HasOnlyUnconstrainedUsesInLoop(LiveRange* range, |
| BlockInfo* loop_header) { |
| const intptr_t boundary = loop_header->last_block()->end_pos(); |
| |
| UsePosition* use = range->first_use(); |
| while ((use != NULL) && (use->pos() < boundary)) { |
| if (!use->location_slot()->Equals(Location::Any())) { |
| return false; |
| } |
| use = use->next(); |
| } |
| |
| return true; |
| } |
| |
| |
| // Returns true if all uses of the given range have Any allocation policy. |
| static bool HasOnlyUnconstrainedUses(LiveRange* range) { |
| UsePosition* use = range->first_use(); |
| while (use != NULL) { |
| if (!use->location_slot()->Equals(Location::Any())) { |
| return false; |
| } |
| use = use->next(); |
| } |
| return true; |
| } |
| |
| |
| void FlowGraphAllocator::BuildLiveRanges() { |
| const intptr_t block_count = postorder_.length(); |
| ASSERT(postorder_.Last()->IsGraphEntry()); |
| BitVector* current_interference_set = NULL; |
| for (intptr_t i = 0; i < (block_count - 1); i++) { |
| BlockEntryInstr* block = postorder_[i]; |
| |
| BlockInfo* block_info = BlockInfoAt(block->start_pos()); |
| |
| // For every SSA value that is live out of this block, create an interval |
| // that covers the whole block. It will be shortened if we encounter a |
| // definition of this value in this block. |
| for (BitVector::Iterator it(liveness_.GetLiveOutSetAt(i)); |
| !it.Done(); |
| it.Advance()) { |
| LiveRange* range = GetLiveRange(it.Current()); |
| range->AddUseInterval(block->start_pos(), block->end_pos()); |
| } |
| |
| BlockInfo* loop_header = block_info->loop_header(); |
| if ((loop_header != NULL) && (loop_header->last_block() == block)) { |
| current_interference_set = |
| new BitVector(flow_graph_.max_virtual_register_number()); |
| ASSERT(loop_header->backedge_interference() == NULL); |
| // All values flowing into the loop header are live at the back-edge and |
| // can interfere with phi moves. |
| current_interference_set->AddAll( |
| liveness_.GetLiveInSet(loop_header->entry())); |
| loop_header->set_backedge_interference( |
| current_interference_set); |
| } |
| |
| // Connect outgoing phi-moves that were created in NumberInstructions |
| // and find last instruction that contributes to liveness. |
| Instruction* current = ConnectOutgoingPhiMoves(block, |
| current_interference_set); |
| |
| // Now process all instructions in reverse order. |
| while (current != block) { |
| // Skip parallel moves that we insert while processing instructions. |
| if (!current->IsParallelMove()) { |
| ProcessOneInstruction(block, current, current_interference_set); |
| } |
| current = current->previous(); |
| } |
| |
| |
| // Check if any values live into the loop can be spilled for free. |
| if (block_info->is_loop_header()) { |
| current_interference_set = NULL; |
| for (BitVector::Iterator it(liveness_.GetLiveInSetAt(i)); |
| !it.Done(); |
| it.Advance()) { |
| LiveRange* range = GetLiveRange(it.Current()); |
| if (HasOnlyUnconstrainedUsesInLoop(range, block_info)) { |
| range->MarkHasOnlyUnconstrainedUsesInLoop(block_info->loop_id()); |
| } |
| } |
| } |
| |
| ConnectIncomingPhiMoves(block); |
| } |
| |
| // Process incoming parameters and constants. Do this after all other |
| // instructions so that safepoints for all calls have already been found. |
| GraphEntryInstr* graph_entry = flow_graph_.graph_entry(); |
| for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) { |
| Definition* defn = (*graph_entry->initial_definitions())[i]; |
| LiveRange* range = GetLiveRange(defn->ssa_temp_index()); |
| range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos()); |
| range->DefineAt(graph_entry->start_pos()); |
| if (defn->IsParameter()) { |
| ParameterInstr* param = defn->AsParameter(); |
| // Assert that copied and non-copied parameters are mutually exclusive. |
| // This might change in the future and, if so, the index will be wrong. |
| ASSERT((flow_graph_.num_copied_params() == 0) || |
| (flow_graph_.num_non_copied_params() == 0)); |
| // Slot index for the leftmost copied parameter is 0. |
| intptr_t slot_index = param->index(); |
| // Slot index for the rightmost fixed parameter is -1. |
| slot_index -= flow_graph_.num_non_copied_params(); |
| |
| range->set_assigned_location(Location::StackSlot(slot_index)); |
| range->set_spill_slot(Location::StackSlot(slot_index)); |
| if (flow_graph_.num_copied_params() > 0) { |
| ASSERT(spill_slots_.length() == slot_index); |
| spill_slots_.Add(range->End()); |
| quad_spill_slots_.Add(false); |
| } |
| AssignSafepoints(range); |
| } else { |
| ConstantInstr* constant = defn->AsConstant(); |
| ASSERT(constant != NULL); |
| range->set_assigned_location(Location::Constant(constant->value())); |
| range->set_spill_slot(Location::Constant(constant->value())); |
| } |
| range->finger()->Initialize(range); |
| UsePosition* use = |
| range->finger()->FirstRegisterBeneficialUse(graph_entry->start_pos()); |
| if (use != NULL) { |
| LiveRange* tail = |
| SplitBetween(range, graph_entry->start_pos(), use->pos()); |
| // Parameters and constants are tagged, so allocated to CPU registers. |
| CompleteRange(tail, Location::kRegister); |
| } |
| ConvertAllUses(range); |
| |
| if (defn->IsParameter() && flow_graph_.num_copied_params() > 0) { |
| MarkAsObjectAtSafepoints(range); |
| } |
| } |
| } |
| |
| |
| static Location::Kind RegisterKindFromPolicy(Location loc) { |
| if (loc.policy() == Location::kRequiresFpuRegister) { |
| return Location::kFpuRegister; |
| } else { |
| return Location::kRegister; |
| } |
| } |
| |
| |
| static Location::Kind RegisterKindForResult(Instruction* instr) { |
| if ((instr->representation() == kUnboxedDouble) || |
| (instr->representation() == kUnboxedMint) || |
| (instr->representation() == kUnboxedFloat32x4) || |
| (instr->representation() == kUnboxedUint32x4)) { |
| return Location::kFpuRegister; |
| } else { |
| return Location::kRegister; |
| } |
| } |
| |
| |
| // |
| // When describing shape of live ranges in comments below we are going to use |
| // the following notation: |
| // |
| // B block entry |
| // g g' start and end of goto instruction |
| // i i' start and end of any other instruction |
| // j j' start and end of any other instruction |
| |
| // - body of a use interval |
| // [ start of a use interval |
| // ) end of a use interval |
| // * use |
| // |
| // For example diagram |
| // |
| // i i' |
| // value --*--) |
| // |
| // can be read as: use interval for value starts somewhere before instruction |
| // and extends until currently processed instruction, there is a use of value |
| // at the start of the instruction. |
| // |
| |
| Instruction* FlowGraphAllocator::ConnectOutgoingPhiMoves( |
| BlockEntryInstr* block, BitVector* interfere_at_backedge) { |
| Instruction* last = block->last_instruction(); |
| |
| GotoInstr* goto_instr = last->AsGoto(); |
| if (goto_instr == NULL) return last; |
| |
| // If we have a parallel move here then the successor block must be a |
| // join with phis. The phi inputs contribute uses to each predecessor |
| // block (and the phi outputs contribute definitions in the successor |
| // block). |
| if (!goto_instr->HasParallelMove()) return goto_instr->previous(); |
| ParallelMoveInstr* parallel_move = goto_instr->parallel_move(); |
| |
| // All uses are recorded at the position of parallel move preceding goto. |
| const intptr_t pos = goto_instr->lifetime_position(); |
| |
| JoinEntryInstr* join = goto_instr->successor(); |
| ASSERT(join != NULL); |
| |
| // Search for the index of the current block in the predecessors of |
| // the join. |
| const intptr_t pred_idx = join->IndexOfPredecessor(block); |
| |
| // Record the corresponding phi input use for each phi. |
| intptr_t move_idx = 0; |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| Value* val = phi->InputAt(pred_idx); |
| MoveOperands* move = parallel_move->MoveOperandsAt(move_idx); |
| |
| ConstantInstr* constant = val->definition()->AsConstant(); |
| if (constant != NULL) { |
| move->set_src(Location::Constant(constant->value())); |
| move_idx++; |
| continue; |
| } |
| |
| // Expected shape of live ranges: |
| // |
| // g g' |
| // value --* |
| // |
| |
| const intptr_t vreg = val->definition()->ssa_temp_index(); |
| LiveRange* range = GetLiveRange(vreg); |
| if (interfere_at_backedge != NULL) interfere_at_backedge->Add(vreg); |
| |
| range->AddUseInterval(block->start_pos(), pos); |
| range->AddHintedUse(pos, move->src_slot(), move->dest_slot()); |
| |
| move->set_src(Location::PrefersRegister()); |
| move_idx++; |
| } |
| |
| // Begin backward iteration with the instruction before the parallel |
| // move. |
| return goto_instr->previous(); |
| } |
| |
| |
| void FlowGraphAllocator::ConnectIncomingPhiMoves(BlockEntryInstr* block) { |
| // If this block is a join we need to add destinations of phi |
| // resolution moves to phi's live range so that register allocator will |
| // fill them with moves. |
| JoinEntryInstr* join = block->AsJoinEntry(); |
| if (join == NULL) return; |
| |
| // All uses are recorded at the start position in the block. |
| const intptr_t pos = join->start_pos(); |
| const bool is_loop_header = BlockInfoAt(join->start_pos())->is_loop_header(); |
| intptr_t move_idx = 0; |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| ASSERT(phi != NULL); |
| const intptr_t vreg = phi->ssa_temp_index(); |
| ASSERT(vreg >= 0); |
| |
| // Expected shape of live range: |
| // |
| // B |
| // phi [-------- |
| // |
| LiveRange* range = GetLiveRange(vreg); |
| range->DefineAt(pos); // Shorten live range. |
| |
| if (is_loop_header) range->mark_loop_phi(); |
| |
| for (intptr_t pred_idx = 0; pred_idx < phi->InputCount(); pred_idx++) { |
| BlockEntryInstr* pred = block->PredecessorAt(pred_idx); |
| GotoInstr* goto_instr = pred->last_instruction()->AsGoto(); |
| ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove())); |
| MoveOperands* move = |
| goto_instr->parallel_move()->MoveOperandsAt(move_idx); |
| move->set_dest(Location::PrefersRegister()); |
| range->AddUse(pos, move->dest_slot()); |
| } |
| |
| // All phi resolution moves are connected. Phi's live range is |
| // complete. |
| AssignSafepoints(range); |
| |
| CompleteRange(range, RegisterKindForResult(phi)); |
| |
| move_idx++; |
| } |
| } |
| |
| |
| void FlowGraphAllocator::ProcessEnvironmentUses(BlockEntryInstr* block, |
| Instruction* current) { |
| ASSERT(current->env() != NULL); |
| Environment* env = current->env(); |
| while (env != NULL) { |
| // Any value mentioned in the deoptimization environment should survive |
| // until the end of instruction but it does not need to be in the register. |
| // Expected shape of live range: |
| // |
| // i i' |
| // value -----* |
| // |
| |
| if (env->Length() == 0) { |
| env = env->outer(); |
| continue; |
| } |
| |
| const intptr_t block_start_pos = block->start_pos(); |
| const intptr_t use_pos = current->lifetime_position() + 1; |
| |
| Location* locations = |
| Isolate::Current()->current_zone()->Alloc<Location>(env->Length()); |
| |
| for (intptr_t i = 0; i < env->Length(); ++i) { |
| Value* value = env->ValueAt(i); |
| locations[i] = Location::Any(); |
| Definition* def = value->definition(); |
| |
| if (def->IsPushArgument()) { |
| // Frame size is unknown until after allocation. |
| locations[i] = Location::NoLocation(); |
| continue; |
| } |
| |
| ConstantInstr* constant = def->AsConstant(); |
| if (constant != NULL) { |
| locations[i] = Location::Constant(constant->value()); |
| continue; |
| } |
| |
| const intptr_t vreg = def->ssa_temp_index(); |
| LiveRange* range = GetLiveRange(vreg); |
| range->AddUseInterval(block_start_pos, use_pos); |
| range->AddUse(use_pos, &locations[i]); |
| } |
| |
| env->set_locations(locations); |
| env = env->outer(); |
| } |
| } |
| |
| |
| // Create and update live ranges corresponding to instruction's inputs, |
| // temporaries and output. |
| void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block, |
| Instruction* current, |
| BitVector* interference_set) { |
| LocationSummary* locs = current->locs(); |
| |
| Definition* def = current->AsDefinition(); |
| if ((def != NULL) && (def->AsConstant() != NULL)) { |
| LiveRange* range = (def->ssa_temp_index() != -1) ? |
| GetLiveRange(def->ssa_temp_index()) : NULL; |
| |
| // Drop definitions of constants that have no uses. |
| if ((range == NULL) || (range->first_use() == NULL)) { |
| locs->set_out(Location::NoLocation()); |
| return; |
| } |
| |
| // If this constant has only unconstrained uses convert them all |
| // to use the constant directly and drop this definition. |
| // TODO(vegorov): improve allocation when we have enough registers to keep |
| // constants used in the loop in them. |
| if (HasOnlyUnconstrainedUses(range)) { |
| const Object& value = def->AsConstant()->value(); |
| range->set_assigned_location(Location::Constant(value)); |
| range->set_spill_slot(Location::Constant(value)); |
| range->finger()->Initialize(range); |
| ConvertAllUses(range); |
| |
| locs->set_out(Location::NoLocation()); |
| return; |
| } |
| } |
| |
| const intptr_t pos = current->lifetime_position(); |
| ASSERT(IsInstructionStartPosition(pos)); |
| |
| // Number of input locations and number of input operands have to agree. |
| ASSERT(locs->input_count() == current->InputCount()); |
| |
| // Normalize same-as-first-input output if input is specified as |
| // fixed register. |
| if (locs->out().IsUnallocated() && |
| (locs->out().policy() == Location::kSameAsFirstInput) && |
| (locs->in(0).IsMachineRegister())) { |
| locs->set_out(locs->in(0)); |
| } |
| |
| const bool output_same_as_first_input = |
| locs->out().IsUnallocated() && |
| (locs->out().policy() == Location::kSameAsFirstInput); |
| |
| // Add uses from the deoptimization environment. |
| if (current->env() != NULL) ProcessEnvironmentUses(block, current); |
| |
| // Process inputs. |
| // Skip the first input if output is specified with kSameAsFirstInput policy, |
| // they will be processed together at the very end. |
| for (intptr_t j = output_same_as_first_input ? 1 : 0; |
| j < current->InputCount(); |
| j++) { |
| Value* input = current->InputAt(j); |
| const intptr_t vreg = input->definition()->ssa_temp_index(); |
| LiveRange* range = GetLiveRange(vreg); |
| |
| Location* in_ref = locs->in_slot(j); |
| |
| if (in_ref->IsMachineRegister()) { |
| // Input is expected in a fixed register. Expected shape of |
| // live ranges: |
| // |
| // j' i i' |
| // value --* |
| // register [-----) |
| // |
| MoveOperands* move = |
| AddMoveAt(pos - 1, *in_ref, Location::Any()); |
| BlockLocation(*in_ref, pos - 1, pos + 1); |
| range->AddUseInterval(block->start_pos(), pos - 1); |
| range->AddHintedUse(pos - 1, move->src_slot(), in_ref); |
| } else if (in_ref->IsUnallocated()) { |
| if (in_ref->policy() == Location::kWritableRegister) { |
| // Writable unallocated input. Expected shape of |
| // live ranges: |
| // |
| // i i' |
| // value --* |
| // temp [--) |
| MoveOperands* move = AddMoveAt(pos, |
| Location::RequiresRegister(), |
| Location::PrefersRegister()); |
| |
| // Add uses to the live range of the input. |
| range->AddUseInterval(block->start_pos(), pos); |
| range->AddUse(pos, move->src_slot()); |
| |
| // Create live range for the temporary. |
| LiveRange* temp = MakeLiveRangeForTemporary(); |
| temp->AddUseInterval(pos, pos + 1); |
| temp->AddHintedUse(pos, in_ref, move->src_slot()); |
| temp->AddUse(pos, move->dest_slot()); |
| *in_ref = Location::RequiresRegister(); |
| CompleteRange(temp, RegisterKindFromPolicy(*in_ref)); |
| } else { |
| // Normal unallocated input. Expected shape of |
| // live ranges: |
| // |
| // i i' |
| // value -----* |
| // |
| range->AddUseInterval(block->start_pos(), pos + 1); |
| range->AddUse(pos + 1, in_ref); |
| } |
| } else { |
| ASSERT(in_ref->IsConstant()); |
| } |
| } |
| |
| // Process temps. |
| for (intptr_t j = 0; j < locs->temp_count(); j++) { |
| // Expected shape of live range: |
| // |
| // i i' |
| // [--) |
| // |
| |
| Location temp = locs->temp(j); |
| if (temp.IsMachineRegister()) { |
| BlockLocation(temp, pos, pos + 1); |
| } else if (temp.IsUnallocated()) { |
| LiveRange* range = MakeLiveRangeForTemporary(); |
| range->AddUseInterval(pos, pos + 1); |
| range->AddUse(pos, locs->temp_slot(j)); |
| CompleteRange(range, RegisterKindFromPolicy(temp)); |
| } else { |
| UNREACHABLE(); |
| } |
| } |
| |
| // Block all allocatable registers for calls and record the stack bitmap. |
| if (locs->always_calls()) { |
| // Expected shape of live range: |
| // |
| // i i' |
| // [--) |
| // |
| // The stack bitmap describes the position i. |
| for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) { |
| BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)), |
| pos, |
| pos + 1); |
| } |
| |
| for (intptr_t reg = 0; reg < kNumberOfFpuRegisters; reg++) { |
| BlockLocation( |
| Location::FpuRegisterLocation(static_cast<FpuRegister>(reg)), |
| pos, |
| pos + 1); |
| } |
| |
| |
| #if defined(DEBUG) |
| // Verify that temps, inputs and output were specified as fixed |
| // locations. Every register is blocked now so attempt to |
| // allocate will not succeed. |
| for (intptr_t j = 0; j < locs->temp_count(); j++) { |
| ASSERT(!locs->temp(j).IsUnallocated()); |
| } |
| |
| for (intptr_t j = 0; j < locs->input_count(); j++) { |
| ASSERT(!locs->in(j).IsUnallocated()); |
| } |
| |
| ASSERT(!locs->out().IsUnallocated()); |
| #endif |
| } |
| |
| if (locs->can_call()) { |
| safepoints_.Add(current); |
| } |
| |
| if (def == NULL) { |
| ASSERT(locs->out().IsInvalid()); |
| return; |
| } |
| |
| if (locs->out().IsInvalid()) { |
| ASSERT(def->ssa_temp_index() < 0); |
| return; |
| } |
| |
| // We might have a definition without use. We do not assign SSA index to |
| // such definitions. |
| LiveRange* range = (def->ssa_temp_index() >= 0) ? |
| GetLiveRange(def->ssa_temp_index()) : |
| MakeLiveRangeForTemporary(); |
| Location* out = locs->out_slot(); |
| |
| // Process output and finalize its liverange. |
| if (out->IsMachineRegister()) { |
| // Fixed output location. Expected shape of live range: |
| // |
| // i i' j j' |
| // register [--) |
| // output [------- |
| // |
| BlockLocation(*out, pos, pos + 1); |
| |
| if (range->vreg() == kTempVirtualRegister) return; |
| |
| // We need to emit move connecting fixed register with another location |
| // that will be allocated for this output's live range. |
| // Special case: fixed output followed by a fixed input last use. |
| UsePosition* use = range->first_use(); |
| |
| // If the value has no uses we don't need to allocate it. |
| if (use == NULL) return; |
| |
| if (use->pos() == (pos + 1)) { |
| ASSERT(use->location_slot()->IsUnallocated()); |
| *(use->location_slot()) = *out; |
| |
| // Remove first use. It was allocated. |
| range->set_first_use(range->first_use()->next()); |
| } |
| |
| // Shorten live range to the point of definition, this might make the range |
| // empty (if the only use immediately follows). If range is not empty add |
| // move from a fixed register to an unallocated location. |
| range->DefineAt(pos + 1); |
| if (range->Start() == range->End()) return; |
| |
| MoveOperands* move = AddMoveAt(pos + 1, Location::Any(), *out); |
| range->AddHintedUse(pos + 1, move->dest_slot(), out); |
| } else if (output_same_as_first_input) { |
| // Output register will contain a value of the first input at instruction's |
| // start. Expected shape of live ranges: |
| // |
| // i i' |
| // input #0 --* |
| // output [---- |
| // |
| ASSERT(locs->in(0).Equals(Location::RequiresRegister()) || |
| locs->in(0).Equals(Location::RequiresFpuRegister())); |
| |
| // Create move that will copy value between input and output. |
| locs->set_out(Location::RequiresRegister()); |
| MoveOperands* move = AddMoveAt(pos, |
| Location::RequiresRegister(), |
| Location::Any()); |
| |
| // Add uses to the live range of the input. |
| Definition* input = current->InputAt(0)->definition(); |
| LiveRange* input_range = |
| GetLiveRange(input->ssa_temp_index()); |
| input_range->AddUseInterval(block->start_pos(), pos); |
| input_range->AddUse(pos, move->src_slot()); |
| |
| // Shorten output live range to the point of definition and add both input |
| // and output uses slots to be filled by allocator. |
| range->DefineAt(pos); |
| range->AddHintedUse(pos, out, move->src_slot()); |
| range->AddUse(pos, move->dest_slot()); |
| range->AddUse(pos, locs->in_slot(0)); |
| |
| if ((interference_set != NULL) && |
| (range->vreg() >= 0) && |
| interference_set->Contains(range->vreg())) { |
| interference_set->Add(input->ssa_temp_index()); |
| } |
| } else { |
| // Normal unallocated location that requires a register. Expected shape of |
| // live range: |
| // |
| // i i' |
| // output [------- |
| // |
| ASSERT(locs->out().Equals(Location::RequiresRegister()) || |
| locs->out().Equals(Location::RequiresFpuRegister())); |
| |
| // Shorten live range to the point of definition and add use to be filled by |
| // allocator. |
| range->DefineAt(pos); |
| range->AddUse(pos, out); |
| } |
| |
| AssignSafepoints(range); |
| CompleteRange(range, RegisterKindForResult(current)); |
| } |
| |
| |
| static ParallelMoveInstr* CreateParallelMoveBefore(Instruction* instr, |
| intptr_t pos) { |
| ASSERT(pos > 0); |
| Instruction* prev = instr->previous(); |
| ParallelMoveInstr* move = prev->AsParallelMove(); |
| if ((move == NULL) || (move->lifetime_position() != pos)) { |
| move = new ParallelMoveInstr(); |
| prev->LinkTo(move); |
| move->LinkTo(instr); |
| move->set_lifetime_position(pos); |
| } |
| return move; |
| } |
| |
| |
| static ParallelMoveInstr* CreateParallelMoveAfter(Instruction* instr, |
| intptr_t pos) { |
| Instruction* next = instr->next(); |
| if (next->IsParallelMove() && (next->lifetime_position() == pos)) { |
| return next->AsParallelMove(); |
| } |
| return CreateParallelMoveBefore(next, pos); |
| } |
| |
| |
| // Linearize the control flow graph. The chosen order will be used by the |
| // linear-scan register allocator. Number most instructions with a pair of |
| // numbers representing lifetime positions. Introduce explicit parallel |
| // move instructions in the predecessors of join nodes. The moves are used |
| // for phi resolution. |
| void FlowGraphAllocator::NumberInstructions() { |
| intptr_t pos = 0; |
| |
| // The basic block order is reverse postorder. |
| const intptr_t block_count = postorder_.length(); |
| for (intptr_t i = block_count - 1; i >= 0; i--) { |
| BlockEntryInstr* block = postorder_[i]; |
| BlockInfo* info = new BlockInfo(block); |
| |
| instructions_.Add(block); |
| block_info_.Add(info); |
| block->set_start_pos(pos); |
| block->set_lifetime_position(pos); |
| pos += 2; |
| |
| for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| Instruction* current = it.Current(); |
| // Do not assign numbers to parallel move instructions. |
| if (!current->IsParallelMove()) { |
| instructions_.Add(current); |
| block_info_.Add(info); |
| current->set_lifetime_position(pos); |
| pos += 2; |
| } |
| } |
| block->set_end_pos(pos); |
| } |
| |
| // Create parallel moves in join predecessors. This must be done after |
| // all instructions are numbered. |
| for (intptr_t i = block_count - 1; i >= 0; i--) { |
| BlockEntryInstr* block = postorder_[i]; |
| |
| // For join entry predecessors create phi resolution moves if |
| // necessary. They will be populated by the register allocator. |
| JoinEntryInstr* join = block->AsJoinEntry(); |
| if ((join != NULL) && |
| (join->phis() != NULL) && |
| !join->phis()->is_empty()) { |
| const intptr_t phi_count = join->phis()->length(); |
| for (intptr_t i = 0; i < block->PredecessorCount(); i++) { |
| // Insert the move between the last two instructions of the |
| // predecessor block (all such blocks have at least two instructions: |
| // the block entry and goto instructions.) |
| Instruction* last = block->PredecessorAt(i)->last_instruction(); |
| ASSERT(last->IsGoto()); |
| |
| ParallelMoveInstr* move = last->AsGoto()->GetParallelMove(); |
| |
| // Populate the ParallelMove with empty moves. |
| for (intptr_t j = 0; j < phi_count; j++) { |
| move->AddMove(Location::NoLocation(), Location::NoLocation()); |
| } |
| } |
| } |
| } |
| } |
| |
| |
| // Discover structural (reducible) loops nesting structure. |
| void FlowGraphAllocator::DiscoverLoops() { |
| // This algorithm relies on the assumption that we emit blocks in reverse |
| // postorder, so postorder number can be used to identify loop nesting. |
| // |
| // TODO(vegorov): consider using a generic algorithm to correctly discover |
| // both headers of reducible and irreducible loops. |
| BlockInfo* current_loop = NULL; |
| |
| intptr_t loop_id = 0; // All loop headers have a unique id. |
| |
| const intptr_t block_count = postorder_.length(); |
| for (intptr_t i = 0; i < block_count; i++) { |
| BlockEntryInstr* block = postorder_[i]; |
| GotoInstr* goto_instr = block->last_instruction()->AsGoto(); |
| if (goto_instr != NULL) { |
| JoinEntryInstr* successor = goto_instr->successor(); |
| if (successor->postorder_number() > i) { |
| // This is back-edge. |
| BlockInfo* successor_info = BlockInfoAt(successor->lifetime_position()); |
| ASSERT(successor_info->entry() == successor); |
| if (!successor_info->is_loop_header() && |
| ((current_loop == NULL) || |
| (current_loop->entry()->postorder_number() > |
| successor_info->entry()->postorder_number()))) { |
| ASSERT(successor_info != current_loop); |
| |
| successor_info->mark_loop_header(); |
| successor_info->set_loop_id(loop_id++); |
| successor_info->set_last_block(block); |
| // For loop header loop information points to the outer loop. |
| successor_info->set_loop(current_loop); |
| current_loop = successor_info; |
| } |
| } |
| } |
| |
| if (current_loop != NULL) { |
| BlockInfo* current_info = BlockInfoAt(block->lifetime_position()); |
| if (current_info == current_loop) { |
| ASSERT(current_loop->is_loop_header()); |
| current_loop = current_info->loop(); |
| } else { |
| current_info->set_loop(current_loop); |
| } |
| } |
| } |
| } |
| |
| |
| Instruction* FlowGraphAllocator::InstructionAt(intptr_t pos) const { |
| return instructions_[pos / 2]; |
| } |
| |
| |
| BlockInfo* FlowGraphAllocator::BlockInfoAt(intptr_t pos) const { |
| return block_info_[pos / 2]; |
| } |
| |
| |
| bool FlowGraphAllocator::IsBlockEntry(intptr_t pos) const { |
| return IsInstructionStartPosition(pos) && InstructionAt(pos)->IsBlockEntry(); |
| } |
| |
| |
| void AllocationFinger::Initialize(LiveRange* range) { |
| first_pending_use_interval_ = range->first_use_interval(); |
| first_register_use_ = range->first_use(); |
| first_register_beneficial_use_ = range->first_use(); |
| first_hinted_use_ = range->first_use(); |
| } |
| |
| |
| bool AllocationFinger::Advance(const intptr_t start) { |
| UseInterval* a = first_pending_use_interval_; |
| while (a != NULL && a->end() <= start) a = a->next(); |
| first_pending_use_interval_ = a; |
| if (first_pending_use_interval_ == NULL) { |
| return true; |
| } |
| return false; |
| } |
| |
| |
| Location AllocationFinger::FirstHint() { |
| UsePosition* use = first_hinted_use_; |
| |
| while (use != NULL) { |
| if (use->HasHint()) return use->hint(); |
| use = use->next(); |
| } |
| |
| return Location::NoLocation(); |
| } |
| |
| |
| static UsePosition* FirstUseAfter(UsePosition* use, intptr_t after) { |
| while ((use != NULL) && (use->pos() < after)) { |
| use = use->next(); |
| } |
| return use; |
| } |
| |
| |
| UsePosition* AllocationFinger::FirstRegisterUse(intptr_t after) { |
| for (UsePosition* use = FirstUseAfter(first_register_use_, after); |
| use != NULL; |
| use = use->next()) { |
| Location* loc = use->location_slot(); |
| if (loc->IsUnallocated() && |
| ((loc->policy() == Location::kRequiresRegister) || |
| (loc->policy() == Location::kRequiresFpuRegister))) { |
| first_register_use_ = use; |
| return use; |
| } |
| } |
| return NULL; |
| } |
| |
| |
| UsePosition* AllocationFinger::FirstRegisterBeneficialUse(intptr_t after) { |
| for (UsePosition* use = FirstUseAfter(first_register_beneficial_use_, after); |
| use != NULL; |
| use = use->next()) { |
| Location* loc = use->location_slot(); |
| if (loc->IsUnallocated() && loc->IsRegisterBeneficial()) { |
| first_register_beneficial_use_ = use; |
| return use; |
| } |
| } |
| return NULL; |
| } |
| |
| |
| void AllocationFinger::UpdateAfterSplit(intptr_t first_use_after_split_pos) { |
| if ((first_register_use_ != NULL) && |
| (first_register_use_->pos() >= first_use_after_split_pos)) { |
| first_register_use_ = NULL; |
| } |
| |
| if ((first_register_beneficial_use_ != NULL) && |
| (first_register_beneficial_use_->pos() >= first_use_after_split_pos)) { |
| first_register_beneficial_use_ = NULL; |
| } |
| } |
| |
| |
| intptr_t UseInterval::Intersect(UseInterval* other) { |
| if (this->start() <= other->start()) { |
| if (other->start() < this->end()) return other->start(); |
| } else if (this->start() < other->end()) { |
| return this->start(); |
| } |
| return kIllegalPosition; |
| } |
| |
| |
| static intptr_t FirstIntersection(UseInterval* a, UseInterval* u) { |
| while (a != NULL && u != NULL) { |
| const intptr_t pos = a->Intersect(u); |
| if (pos != kIllegalPosition) return pos; |
| |
| if (a->start() < u->start()) { |
| a = a->next(); |
| } else { |
| u = u->next(); |
| } |
| } |
| |
| return kMaxPosition; |
| } |
| |
| |
| LiveRange* LiveRange::MakeTemp(intptr_t pos, Location* location_slot) { |
| UNREACHABLE(); |
| return NULL; |
| } |
| |
| |
| template<typename PositionType> |
| PositionType* SplitListOfPositions(PositionType** head, |
| intptr_t split_pos, |
| bool split_at_start) { |
| PositionType* last_before_split = NULL; |
| PositionType* pos = *head; |
| if (split_at_start) { |
| while ((pos != NULL) && (pos->pos() < split_pos)) { |
| last_before_split = pos; |
| pos = pos->next(); |
| } |
| } else { |
| while ((pos != NULL) && (pos->pos() <= split_pos)) { |
| last_before_split = pos; |
| pos = pos->next(); |
| } |
| } |
| |
| if (last_before_split == NULL) { |
| *head = NULL; |
| } else { |
| last_before_split->set_next(NULL); |
| } |
| |
| return pos; |
| } |
| |
| |
| LiveRange* LiveRange::SplitAt(intptr_t split_pos) { |
| if (Start() == split_pos) return this; |
| |
| UseInterval* interval = finger_.first_pending_use_interval(); |
| if (interval == NULL) { |
| finger_.Initialize(this); |
| interval = finger_.first_pending_use_interval(); |
| } |
| |
| ASSERT(split_pos < End()); |
| |
| // Corner case. Split position can be inside the a lifetime hole or at its |
| // end. We need to start over to find the previous interval. |
| if (split_pos <= interval->start()) interval = first_use_interval_; |
| |
| UseInterval* last_before_split = NULL; |
| while (interval->end() <= split_pos) { |
| last_before_split = interval; |
| interval = interval->next(); |
| } |
| |
| const bool split_at_start = (interval->start() == split_pos); |
| |
| UseInterval* first_after_split = interval; |
| if (!split_at_start && interval->Contains(split_pos)) { |
| first_after_split = new UseInterval(split_pos, |
| interval->end(), |
| interval->next()); |
| interval->end_ = split_pos; |
| interval->next_ = first_after_split; |
| last_before_split = interval; |
| } |
| |
| ASSERT(last_before_split != NULL); |
| ASSERT(last_before_split->next() == first_after_split); |
| ASSERT(last_before_split->end() <= split_pos); |
| ASSERT(split_pos <= first_after_split->start()); |
| |
| UsePosition* first_use_after_split = |
| SplitListOfPositions(&uses_, split_pos, split_at_start); |
| |
| SafepointPosition* first_safepoint_after_split = |
| SplitListOfPositions(&first_safepoint_, split_pos, split_at_start); |
| |
| UseInterval* last_use_interval = (last_before_split == last_use_interval_) ? |
| first_after_split : last_use_interval_; |
| next_sibling_ = new LiveRange(vreg(), |
| representation(), |
| first_use_after_split, |
| first_after_split, |
| last_use_interval, |
| first_safepoint_after_split, |
| next_sibling_); |
| |
| TRACE_ALLOC(OS::Print(" split sibling [%"Pd", %"Pd")\n", |
| next_sibling_->Start(), next_sibling_->End())); |
| |
| last_use_interval_ = last_before_split; |
| last_use_interval_->next_ = NULL; |
| |
| if (first_use_after_split != NULL) { |
| finger_.UpdateAfterSplit(first_use_after_split->pos()); |
| } |
| |
| return next_sibling_; |
| } |
| |
| |
| LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range, |
| intptr_t from, |
| intptr_t to) { |
| TRACE_ALLOC(OS::Print("split v%"Pd" [%"Pd", %"Pd") between [%"Pd", %"Pd")\n", |
| range->vreg(), range->Start(), range->End(), from, to)); |
| |
| intptr_t split_pos = kIllegalPosition; |
| |
| BlockInfo* split_block = BlockInfoAt(to); |
| if (from < split_block->entry()->lifetime_position()) { |
| // Interval [from, to) spans multiple blocks. |
| |
| // If last block is inside a loop prefer splitting at outermost loop's |
| // header. |
| BlockInfo* loop_header = split_block->loop(); |
| while ((loop_header != NULL) && |
| (from < loop_header->entry()->lifetime_position())) { |
| split_block = loop_header; |
| loop_header = loop_header->loop(); |
| } |
| |
| // Split at block's start. |
| split_pos = split_block->entry()->lifetime_position(); |
| } else { |
| // Interval [from, to) is contained inside a single block. |
| |
| // Split at position corresponding to the end of the previous |
| // instruction. |
| split_pos = ToInstructionStart(to) - 1; |
| } |
| |
| ASSERT((split_pos != kIllegalPosition) && (from < split_pos)); |
| |
| return range->SplitAt(split_pos); |
| } |
| |
| |
| void FlowGraphAllocator::SpillBetween(LiveRange* range, |
| intptr_t from, |
| intptr_t to) { |
| ASSERT(from < to); |
| TRACE_ALLOC(OS::Print("spill v%"Pd" [%"Pd", %"Pd") " |
| "between [%"Pd", %"Pd")\n", |
| range->vreg(), range->Start(), range->End(), from, to)); |
| LiveRange* tail = range->SplitAt(from); |
| |
| if (tail->Start() < to) { |
| // There is an intersection of tail and [from, to). |
| LiveRange* tail_tail = SplitBetween(tail, tail->Start(), to); |
| Spill(tail); |
| AddToUnallocated(tail_tail); |
| } else { |
| // No intersection between tail and [from, to). |
| AddToUnallocated(tail); |
| } |
| } |
| |
| |
| void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) { |
| TRACE_ALLOC(OS::Print("spill v%"Pd" [%"Pd", %"Pd") after %"Pd"\n", |
| range->vreg(), range->Start(), range->End(), from)); |
| |
| // When spilling the value inside the loop check if this spill can |
| // be moved outside. |
| BlockInfo* block_info = BlockInfoAt(from); |
| if (block_info->is_loop_header() || (block_info->loop() != NULL)) { |
| BlockInfo* loop_header = |
| block_info->is_loop_header() ? block_info : block_info->loop(); |
| |
| if ((range->Start() <= loop_header->entry()->start_pos()) && |
| RangeHasOnlyUnconstrainedUsesInLoop(range, loop_header->loop_id())) { |
| ASSERT(loop_header->entry()->start_pos() <= from); |
| from = loop_header->entry()->start_pos(); |
| TRACE_ALLOC(OS::Print(" moved spill position to loop header %"Pd"\n", |
| from)); |
| } |
| } |
| |
| LiveRange* tail = range->SplitAt(from); |
| Spill(tail); |
| } |
| |
| |
| void FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) { |
| ASSERT(range->spill_slot().IsInvalid()); |
| |
| // Compute range start and end. |
| LiveRange* last_sibling = range; |
| while (last_sibling->next_sibling() != NULL) { |
| last_sibling = last_sibling->next_sibling(); |
| } |
| |
| const intptr_t start = range->Start(); |
| const intptr_t end = last_sibling->End(); |
| |
| // During fpu register allocation spill slot indices are computed in terms of |
| // double (64bit) stack slots. We treat quad stack slot (128bit) as a |
| // consecutive pair of two double spill slots. |
| // Special care is taken to never allocate the same index to both |
| // double and quad spill slots as it complicates disambiguation during |
| // parallel move resolution. |
| const bool need_quad = (register_kind_ == Location::kFpuRegister) && |
| ((range->representation() == kUnboxedFloat32x4) || |
| (range->representation() == kUnboxedUint32x4)); |
| |
| // Search for a free spill slot among allocated: the value in it should be |
| // dead and its type should match (e.g. it should not be a part of the quad if |
| // we are allocating normal double slot). |
| intptr_t idx = 0; |
| for (; idx < spill_slots_.length(); idx++) { |
| if ((need_quad == quad_spill_slots_[idx]) && |
| (spill_slots_[idx] <= start)) { |
| break; |
| } |
| } |
| |
| if (idx == spill_slots_.length()) { |
| // No free spill slot found. Allocate a new one. |
| spill_slots_.Add(0); |
| quad_spill_slots_.Add(need_quad); |
| if (need_quad) { // Allocate two double stack slots if we need quad slot. |
| spill_slots_.Add(0); |
| quad_spill_slots_.Add(need_quad); |
| } |
| } |
| |
| |
| // Set spill slot expiration boundary to the live range's end. |
| spill_slots_[idx] = end; |
| if (need_quad) { |
| ASSERT(quad_spill_slots_[idx] && quad_spill_slots_[idx + 1]); |
| idx++; // Use the higher index it corresponds to the lower stack address. |
| spill_slots_[idx] = end; |
| } else { |
| ASSERT(!quad_spill_slots_[idx]); |
| } |
| |
| // Assign spill slot to the range. |
| if (register_kind_ == Location::kRegister) { |
| range->set_spill_slot(Location::StackSlot(idx)); |
| } else { |
| // We use the index of the slot with the lowest address as an index for the |
| // FPU register spill slot. In terms of indexes this relation is inverted: |
| // so we have to take the highest index. |
| const intptr_t slot_idx = cpu_spill_slot_count_ + |
| idx * kDoubleSpillFactor + (kDoubleSpillFactor - 1); |
| |
| Location location; |
| if ((range->representation() == kUnboxedFloat32x4) || |
| (range->representation() == kUnboxedUint32x4)) { |
| ASSERT(need_quad); |
| location = Location::QuadStackSlot(slot_idx); |
| } else { |
| ASSERT((range->representation() == kUnboxedDouble) || |
| (range->representation() == kUnboxedMint)); |
| location = Location::DoubleStackSlot(slot_idx); |
| } |
| range->set_spill_slot(location); |
| } |
| |
| spilled_.Add(range); |
| } |
| |
| |
| void FlowGraphAllocator::MarkAsObjectAtSafepoints(LiveRange* range) { |
| intptr_t stack_index = range->spill_slot().stack_index(); |
| ASSERT(stack_index >= 0); |
| |
| while (range != NULL) { |
| for (SafepointPosition* safepoint = range->first_safepoint(); |
| safepoint != NULL; |
| safepoint = safepoint->next()) { |
| safepoint->locs()->stack_bitmap()->Set(stack_index, true); |
| } |
| range = range->next_sibling(); |
| } |
| } |
| |
| |
| void FlowGraphAllocator::Spill(LiveRange* range) { |
| LiveRange* parent = GetLiveRange(range->vreg()); |
| if (parent->spill_slot().IsInvalid()) { |
| AllocateSpillSlotFor(parent); |
| if (range->representation() == kTagged) { |
| MarkAsObjectAtSafepoints(parent); |
| } |
| } |
| range->set_assigned_location(parent->spill_slot()); |
| ConvertAllUses(range); |
| } |
| |
| |
| intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated( |
| intptr_t reg, LiveRange* unallocated) { |
| intptr_t intersection = kMaxPosition; |
| for (intptr_t i = 0; i < registers_[reg].length(); i++) { |
| LiveRange* allocated = registers_[reg][i]; |
| if (allocated == NULL) continue; |
| |
| UseInterval* allocated_head = |
| allocated->finger()->first_pending_use_interval(); |
| if (allocated_head->start() >= intersection) continue; |
| |
| const intptr_t pos = FirstIntersection( |
| unallocated->finger()->first_pending_use_interval(), |
| allocated_head); |
| if (pos < intersection) intersection = pos; |
| } |
| return intersection; |
| } |
| |
| |
| void ReachingDefs::AddPhi(PhiInstr* phi) { |
| if (phi->reaching_defs() == NULL) { |
| phi->set_reaching_defs( |
| new BitVector(flow_graph_.max_virtual_register_number())); |
| |
| // Compute initial set reaching defs set. |
| bool depends_on_phi = false; |
| for (intptr_t i = 0; i < phi->InputCount(); i++) { |
| Definition* input = phi->InputAt(i)->definition(); |
| if (input->IsPhi()) { |
| depends_on_phi = true; |
| } |
| phi->reaching_defs()->Add(input->ssa_temp_index()); |
| } |
| |
| // If this phi depends on another phi then we need fix point iteration. |
| if (depends_on_phi) phis_.Add(phi); |
| } |
| } |
| |
| |
| void ReachingDefs::Compute() { |
| // Transitively collect all phis that are used by the given phi. |
| for (intptr_t i = 0; i < phis_.length(); i++) { |
| PhiInstr* phi = phis_[i]; |
| |
| // Add all phis that affect this phi to the list. |
| for (intptr_t i = 0; i < phi->InputCount(); i++) { |
| PhiInstr* input_phi = phi->InputAt(i)->definition()->AsPhi(); |
| if (input_phi != NULL) { |
| AddPhi(input_phi); |
| } |
| } |
| } |
| |
| // Propagate values until fix point is reached. |
| bool changed; |
| do { |
| changed = false; |
| for (intptr_t i = 0; i < phis_.length(); i++) { |
| PhiInstr* phi = phis_[i]; |
| for (intptr_t i = 0; i < phi->InputCount(); i++) { |
| PhiInstr* input_phi = phi->InputAt(i)->definition()->AsPhi(); |
| if (input_phi != NULL) { |
| if (phi->reaching_defs()->AddAll(input_phi->reaching_defs())) { |
| changed = true; |
| } |
| } |
| } |
| } |
| } while (changed); |
| |
| phis_.Clear(); |
| } |
| |
| |
| BitVector* ReachingDefs::Get(PhiInstr* phi) { |
| if (phi->reaching_defs() == NULL) { |
| ASSERT(phis_.is_empty()); |
| AddPhi(phi); |
| Compute(); |
| } |
| return phi->reaching_defs(); |
| } |
| |
| |
| bool FlowGraphAllocator::AllocateFreeRegister(LiveRange* unallocated) { |
| intptr_t candidate = kNoRegister; |
| intptr_t free_until = 0; |
| |
| // If hint is available try hint first. |
| // TODO(vegorov): ensure that phis are hinted on the back edge. |
| Location hint = unallocated->finger()->FirstHint(); |
| if (hint.IsMachineRegister()) { |
| if (!blocked_registers_[hint.register_code()]) { |
| free_until = FirstIntersectionWithAllocated(hint.register_code(), |
| unallocated); |
| candidate = hint.register_code(); |
| } |
| |
| TRACE_ALLOC(OS::Print("found hint %s for v%"Pd": free until %"Pd"\n", |
| hint.Name(), |
| unallocated->vreg(), |
| free_until)); |
| } else { |
| for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { |
| if (!blocked_registers_[reg] && (registers_[reg].length() == 0)) { |
| candidate = reg; |
| free_until = kMaxPosition; |
| break; |
| } |
| } |
| } |
| |
| ASSERT(0 <= kMaxPosition); |
| if (free_until != kMaxPosition) { |
| for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { |
| if (blocked_registers_[reg] || (reg == candidate)) continue; |
| const intptr_t intersection = |
| FirstIntersectionWithAllocated(reg, unallocated); |
| if (intersection > free_until) { |
| candidate = reg; |
| free_until = intersection; |
| if (free_until == kMaxPosition) break; |
| } |
| } |
| } |
| |
| // All registers are blocked by active ranges. |
| if (free_until <= unallocated->Start()) return false; |
| |
| // We have a very good candidate (either hinted to us or completely free). |
| // If we are in a loop try to reduce number of moves on the back edge by |
| // searching for a candidate that does not interfere with phis on the back |
| // edge. |
| BlockInfo* loop_header = BlockInfoAt(unallocated->Start())->loop_header(); |
| if ((unallocated->vreg() >= 0) && |
| (loop_header != NULL) && |
| (free_until >= loop_header->last_block()->end_pos()) && |
| loop_header->backedge_interference()->Contains(unallocated->vreg())) { |
| ASSERT(static_cast<intptr_t>(kNumberOfFpuRegisters) <= |
| kNumberOfCpuRegisters); |
| bool used_on_backedge[kNumberOfCpuRegisters] = { false }; |
| |
| for (PhiIterator it(loop_header->entry()->AsJoinEntry()); |
| !it.Done(); |
| it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| ASSERT(phi->is_alive()); |
| const intptr_t phi_vreg = phi->ssa_temp_index(); |
| LiveRange* range = GetLiveRange(phi_vreg); |
| if (range->assigned_location().kind() == register_kind_) { |
| const intptr_t reg = range->assigned_location().register_code(); |
| |
| if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) { |
| used_on_backedge[reg] = true; |
| } |
| } |
| } |
| |
| if (used_on_backedge[candidate]) { |
| TRACE_ALLOC(OS::Print( |
| "considering %s for v%"Pd": has interference on the back edge" |
| " {loop [%"Pd", %"Pd")}\n", |
| MakeRegisterLocation(candidate).Name(), |
| unallocated->vreg(), |
| loop_header->entry()->start_pos(), |
| loop_header->last_block()->end_pos())); |
| for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { |
| if (blocked_registers_[reg] || |
| (reg == candidate) || |
| used_on_backedge[reg]) { |
| continue; |
| } |
| |
| const intptr_t intersection = |
| FirstIntersectionWithAllocated(reg, unallocated); |
| if (intersection >= free_until) { |
| candidate = reg; |
| free_until = intersection; |
| TRACE_ALLOC(OS::Print( |
| "found %s for v%"Pd" with no interference on the back edge\n", |
| MakeRegisterLocation(candidate).Name(), |
| candidate)); |
| break; |
| } |
| } |
| } |
| } |
| |
| TRACE_ALLOC(OS::Print("assigning free register ")); |
| TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); |
| TRACE_ALLOC(OS::Print(" to v%"Pd"\n", unallocated->vreg())); |
| |
| if (free_until != kMaxPosition) { |
| // There was an intersection. Split unallocated. |
| TRACE_ALLOC(OS::Print(" splitting at %"Pd"\n", free_until)); |
| LiveRange* tail = unallocated->SplitAt(free_until); |
| AddToUnallocated(tail); |
| } |
| |
| registers_[candidate].Add(unallocated); |
| unallocated->set_assigned_location(MakeRegisterLocation(candidate)); |
| |
| return true; |
| } |
| |
| |
| bool FlowGraphAllocator::RangeHasOnlyUnconstrainedUsesInLoop(LiveRange* range, |
| intptr_t loop_id) { |
| if (range->vreg() >= 0) { |
| return GetLiveRange(range->vreg())->HasOnlyUnconstrainedUsesInLoop(loop_id); |
| } |
| return false; |
| } |
| |
| |
| bool FlowGraphAllocator::IsCheapToEvictRegisterInLoop(BlockInfo* loop, |
| intptr_t reg) { |
| const intptr_t loop_start = loop->entry()->start_pos(); |
| const intptr_t loop_end = loop->last_block()->end_pos(); |
| |
| for (intptr_t i = 0; i < registers_[reg].length(); i++) { |
| LiveRange* allocated = registers_[reg][i]; |
| |
| UseInterval* interval = allocated->finger()->first_pending_use_interval(); |
| if (interval->Contains(loop_start)) { |
| if (!RangeHasOnlyUnconstrainedUsesInLoop(allocated, loop->loop_id())) { |
| return false; |
| } |
| } else if (interval->start() < loop_end) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| |
| bool FlowGraphAllocator::HasCheapEvictionCandidate(LiveRange* phi_range) { |
| ASSERT(phi_range->is_loop_phi()); |
| |
| BlockInfo* loop_header = BlockInfoAt(phi_range->Start()); |
| ASSERT(loop_header->is_loop_header()); |
| ASSERT(phi_range->Start() == loop_header->entry()->start_pos()); |
| |
| for (intptr_t reg = 0; reg < NumberOfRegisters(); ++reg) { |
| if (blocked_registers_[reg]) continue; |
| if (IsCheapToEvictRegisterInLoop(loop_header, reg)) { |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| |
| void FlowGraphAllocator::AllocateAnyRegister(LiveRange* unallocated) { |
| // If a loop phi has no register uses we might still want to allocate it |
| // to the register to reduce amount of memory moves on the back edge. |
| // This is possible if there is a register blocked by a range that can be |
| // cheaply evicted i.e. it has no register beneficial uses inside the |
| // loop. |
| UsePosition* register_use = |
| unallocated->finger()->FirstRegisterUse(unallocated->Start()); |
| if ((register_use == NULL) && |
| !(unallocated->is_loop_phi() && HasCheapEvictionCandidate(unallocated))) { |
| Spill(unallocated); |
| return; |
| } |
| |
| intptr_t candidate = kNoRegister; |
| intptr_t free_until = 0; |
| intptr_t blocked_at = kMaxPosition; |
| |
| for (int reg = 0; reg < NumberOfRegisters(); ++reg) { |
| if (blocked_registers_[reg]) continue; |
| if (UpdateFreeUntil(reg, unallocated, &free_until, &blocked_at)) { |
| candidate = reg; |
| } |
| } |
| |
| const intptr_t register_use_pos = |
| (register_use != NULL) ? register_use->pos() |
| : unallocated->Start(); |
| if (free_until < register_use_pos) { |
| // Can't acquire free register. Spill until we really need one. |
| ASSERT(unallocated->Start() < ToInstructionStart(register_use_pos)); |
| SpillBetween(unallocated, unallocated->Start(), register_use->pos()); |
| return; |
| } |
| |
| TRACE_ALLOC(OS::Print("assigning blocked register ")); |
| TRACE_ALLOC(MakeRegisterLocation(candidate).Print()); |
| TRACE_ALLOC(OS::Print(" to live range v%"Pd" until %"Pd"\n", |
| unallocated->vreg(), blocked_at)); |
| |
| if (blocked_at < unallocated->End()) { |
| // Register is blocked before the end of the live range. Split the range |
| // at latest at blocked_at position. |
| LiveRange* tail = SplitBetween(unallocated, |
| unallocated->Start(), |
| blocked_at + 1); |
| AddToUnallocated(tail); |
| } |
| |
| AssignNonFreeRegister(unallocated, candidate); |
| } |
| |
| |
| bool FlowGraphAllocator::UpdateFreeUntil(intptr_t reg, |
| LiveRange* unallocated, |
| intptr_t* cur_free_until, |
| intptr_t* cur_blocked_at) { |
| intptr_t free_until = kMaxPosition; |
| intptr_t blocked_at = kMaxPosition; |
| const intptr_t start = unallocated->Start(); |
| |
| for (intptr_t i = 0; i < registers_[reg].length(); i++) { |
| LiveRange* allocated = registers_[reg][i]; |
| |
| UseInterval* first_pending_use_interval = |
| allocated->finger()->first_pending_use_interval(); |
| if (first_pending_use_interval->Contains(start)) { |
| // This is an active interval. |
| if (allocated->vreg() < 0) { |
| // This register blocked by an interval that |
| // can't be spilled. |
| return false; |
| } |
| |
| const UsePosition* use = |
| allocated->finger()->FirstRegisterBeneficialUse(unallocated->Start()); |
| |
| if ((use != NULL) && ((ToInstructionStart(use->pos()) - start) <= 1)) { |
| // This register is blocked by interval that is used |
| // as register in the current instruction and can't |
| // be spilled. |
| return false; |
| } |
| |
| const intptr_t use_pos = (use != NULL) ? use->pos() |
| : allocated->End(); |
| |
| if (use_pos < free_until) free_until = use_pos; |
| } else { |
| // This is inactive interval. |
| const intptr_t intersection = FirstIntersection( |
| first_pending_use_interval, unallocated->first_use_interval()); |
| if (intersection != kMaxPosition) { |
| if (intersection < free_until) free_until = intersection; |
| if (allocated->vreg() == kNoVirtualRegister) blocked_at = intersection; |
| } |
| } |
| |
| if (free_until <= *cur_free_until) { |
| return false; |
| } |
| } |
| |
| ASSERT(free_until > *cur_free_until); |
| *cur_free_until = free_until; |
| *cur_blocked_at = blocked_at; |
| return true; |
| } |
| |
| |
| void FlowGraphAllocator::RemoveEvicted(intptr_t reg, intptr_t first_evicted) { |
| intptr_t to = first_evicted; |
| intptr_t from = first_evicted + 1; |
| while (from < registers_[reg].length()) { |
| LiveRange* allocated = registers_[reg][from++]; |
| if (allocated != NULL) registers_[reg][to++] = allocated; |
| } |
| registers_[reg].TruncateTo(to); |
| } |
| |
| |
| void FlowGraphAllocator::AssignNonFreeRegister(LiveRange* unallocated, |
| intptr_t reg) { |
| intptr_t first_evicted = -1; |
| for (intptr_t i = registers_[reg].length() - 1; i >= 0; i--) { |
| LiveRange* allocated = registers_[reg][i]; |
| if (allocated->vreg() < 0) continue; // Can't be evicted. |
| if (EvictIntersection(allocated, unallocated)) { |
| // If allocated was not spilled convert all pending uses. |
| if (allocated->assigned_location().IsMachineRegister()) { |
| ASSERT(allocated->End() <= unallocated->Start()); |
| ConvertAllUses(allocated); |
| } |
| registers_[reg][i] = NULL; |
| first_evicted = i; |
| } |
| } |
| |
| // Remove evicted ranges from the array. |
| if (first_evicted != -1) RemoveEvicted(reg, first_evicted); |
| |
| registers_[reg].Add(unallocated); |
| unallocated->set_assigned_location(MakeRegisterLocation(reg)); |
| } |
| |
| |
| bool FlowGraphAllocator::EvictIntersection(LiveRange* allocated, |
| LiveRange* unallocated) { |
| UseInterval* first_unallocated = |
| unallocated->finger()->first_pending_use_interval(); |
| const intptr_t intersection = FirstIntersection( |
| allocated->finger()->first_pending_use_interval(), |
| first_unallocated); |
| if (intersection == kMaxPosition) return false; |
| |
| const intptr_t spill_position = first_unallocated->start(); |
| UsePosition* use = allocated->finger()->FirstRegisterUse(spill_position); |
| if (use == NULL) { |
| // No register uses after this point. |
| SpillAfter(allocated, spill_position); |
| } else { |
| const intptr_t restore_position = |
| (spill_position < intersection) ? MinPosition(intersection, use->pos()) |
| : use->pos(); |
| |
| SpillBetween(allocated, spill_position, restore_position); |
| } |
| |
| return true; |
| } |
| |
| |
| MoveOperands* FlowGraphAllocator::AddMoveAt(intptr_t pos, |
| Location to, |
| Location from) { |
| ASSERT(!IsBlockEntry(pos)); |
| |
| Instruction* instr = InstructionAt(pos); |
| |
| ParallelMoveInstr* parallel_move = NULL; |
| if (IsInstructionStartPosition(pos)) { |
| parallel_move = CreateParallelMoveBefore(instr, pos); |
| } else { |
| parallel_move = CreateParallelMoveAfter(instr, pos); |
| } |
| |
| return parallel_move->AddMove(to, from); |
| } |
| |
| |
| void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) { |
| ASSERT(use->location_slot() != NULL); |
| Location* slot = use->location_slot(); |
| ASSERT(slot->IsUnallocated()); |
| TRACE_ALLOC(OS::Print(" use at %"Pd" converted to ", use->pos())); |
| TRACE_ALLOC(loc.Print()); |
| TRACE_ALLOC(OS::Print("\n")); |
| *slot = loc; |
| } |
| |
| |
| void FlowGraphAllocator::ConvertAllUses(LiveRange* range) { |
| if (range->vreg() == kNoVirtualRegister) return; |
| |
| const Location loc = range->assigned_location(); |
| ASSERT(!loc.IsInvalid()); |
| |
| TRACE_ALLOC(OS::Print("range [%"Pd", %"Pd") " |
| "for v%"Pd" has been allocated to ", |
| range->Start(), range->End(), range->vreg())); |
| TRACE_ALLOC(loc.Print()); |
| TRACE_ALLOC(OS::Print(":\n")); |
| |
| for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) { |
| ConvertUseTo(use, loc); |
| } |
| |
| // Add live registers at all safepoints for instructions with slow-path |
| // code. |
| if (loc.IsMachineRegister()) { |
| for (SafepointPosition* safepoint = range->first_safepoint(); |
| safepoint != NULL; |
| safepoint = safepoint->next()) { |
| if (!safepoint->locs()->always_calls()) { |
| ASSERT(safepoint->locs()->can_call()); |
| safepoint->locs()->live_registers()->Add(loc); |
| } |
| } |
| } |
| } |
| |
| |
| void FlowGraphAllocator::AdvanceActiveIntervals(const intptr_t start) { |
| for (intptr_t reg = 0; reg < NumberOfRegisters(); reg++) { |
| if (registers_[reg].is_empty()) continue; |
| |
| intptr_t first_evicted = -1; |
| for (intptr_t i = registers_[reg].length() - 1; i >= 0; i--) { |
| LiveRange* range = registers_[reg][i]; |
| if (range->finger()->Advance(start)) { |
| ConvertAllUses(range); |
| registers_[reg][i] = NULL; |
| first_evicted = i; |
| } |
| } |
| |
| if (first_evicted != -1) RemoveEvicted(reg, first_evicted); |
| } |
| } |
| |
| |
| bool LiveRange::Contains(intptr_t pos) const { |
| if (!CanCover(pos)) return false; |
| |
| for (UseInterval* interval = first_use_interval_; |
| interval != NULL; |
| interval = interval->next()) { |
| if (interval->Contains(pos)) { |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| |
| void FlowGraphAllocator::AssignSafepoints(LiveRange* range) { |
| for (intptr_t i = safepoints_.length() - 1; i >= 0; i--) { |
| Instruction* instr = safepoints_[i]; |
| |
| const intptr_t pos = instr->lifetime_position(); |
| if (range->End() <= pos) break; |
| |
| if (range->Contains(pos)) range->AddSafepoint(pos, instr->locs()); |
| } |
| } |
| |
| |
| static inline bool ShouldBeAllocatedBefore(LiveRange* a, LiveRange* b) { |
| // TODO(vegorov): consider first hint position when ordering live ranges. |
| return a->Start() <= b->Start(); |
| } |
| |
| |
| static void AddToSortedListOfRanges(GrowableArray<LiveRange*>* list, |
| LiveRange* range) { |
| range->finger()->Initialize(range); |
| |
| if (list->is_empty()) { |
| list->Add(range); |
| return; |
| } |
| |
| for (intptr_t i = list->length() - 1; i >= 0; i--) { |
| if (ShouldBeAllocatedBefore(range, (*list)[i])) { |
| list->InsertAt(i + 1, range); |
| return; |
| } |
| } |
| list->InsertAt(0, range); |
| } |
| |
| |
| void FlowGraphAllocator::AddToUnallocated(LiveRange* range) { |
| AddToSortedListOfRanges(&unallocated_, range); |
| } |
| |
| |
| void FlowGraphAllocator::CompleteRange(LiveRange* range, Location::Kind kind) { |
| switch (kind) { |
| case Location::kRegister: |
| AddToSortedListOfRanges(&unallocated_cpu_, range); |
| break; |
| |
| case Location::kFpuRegister: |
| AddToSortedListOfRanges(&unallocated_xmm_, range); |
| break; |
| |
| default: |
| UNREACHABLE(); |
| } |
| } |
| |
| |
| #if defined(DEBUG) |
| bool FlowGraphAllocator::UnallocatedIsSorted() { |
| for (intptr_t i = unallocated_.length() - 1; i >= 1; i--) { |
| LiveRange* a = unallocated_[i]; |
| LiveRange* b = unallocated_[i - 1]; |
| if (!ShouldBeAllocatedBefore(a, b)) return false; |
| } |
| return true; |
| } |
| #endif |
| |
| |
| void FlowGraphAllocator::PrepareForAllocation( |
| Location::Kind register_kind, |
| intptr_t number_of_registers, |
| const GrowableArray<LiveRange*>& unallocated, |
| LiveRange** blocking_ranges, |
| bool* blocked_registers) { |
| ASSERT(number_of_registers <= kNumberOfCpuRegisters); |
| register_kind_ = register_kind; |
| number_of_registers_ = number_of_registers; |
| |
| ASSERT(unallocated_.is_empty()); |
| unallocated_.AddArray(unallocated); |
| |
| for (intptr_t reg = 0; reg < number_of_registers; reg++) { |
| blocked_registers_[reg] = blocked_registers[reg]; |
| ASSERT(registers_[reg].is_empty()); |
| |
| LiveRange* range = blocking_ranges[reg]; |
| if (range != NULL) { |
| range->finger()->Initialize(range); |
| registers_[reg].Add(range); |
| } |
| } |
| } |
| |
| |
| void FlowGraphAllocator::AllocateUnallocatedRanges() { |
| #if defined(DEBUG) |
| ASSERT(UnallocatedIsSorted()); |
| #endif |
| |
| while (!unallocated_.is_empty()) { |
| LiveRange* range = unallocated_.RemoveLast(); |
| const intptr_t start = range->Start(); |
| TRACE_ALLOC(OS::Print("Processing live range for v%"Pd" " |
| "starting at %"Pd"\n", |
| range->vreg(), |
| start)); |
| |
| // TODO(vegorov): eagerly spill liveranges without register uses. |
| AdvanceActiveIntervals(start); |
| |
| if (!AllocateFreeRegister(range)) { |
| AllocateAnyRegister(range); |
| } |
| } |
| |
| // All allocation decisions were done. |
| ASSERT(unallocated_.is_empty()); |
| |
| // Finish allocation. |
| AdvanceActiveIntervals(kMaxPosition); |
| TRACE_ALLOC(OS::Print("Allocation completed\n")); |
| } |
| |
| |
| bool FlowGraphAllocator::TargetLocationIsSpillSlot(LiveRange* range, |
| Location target) { |
| if (target.IsStackSlot() || |
| target.IsDoubleStackSlot() || |
| target.IsConstant()) { |
| ASSERT(GetLiveRange(range->vreg())->spill_slot().Equals(target)); |
| return true; |
| } |
| return false; |
| } |
| |
| |
| void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* parent, |
| BlockEntryInstr* source_block, |
| BlockEntryInstr* target_block) { |
| TRACE_ALLOC(OS::Print("Connect v%"Pd" on the edge B%"Pd" -> B%"Pd"\n", |
| parent->vreg(), |
| source_block->block_id(), |
| target_block->block_id())); |
| if (parent->next_sibling() == NULL) { |
| // Nothing to connect. The whole range was allocated to the same location. |
| TRACE_ALLOC(OS::Print("range v%"Pd" has no siblings\n", parent->vreg())); |
| return; |
| } |
| |
| const intptr_t source_pos = source_block->end_pos() - 1; |
| ASSERT(IsInstructionEndPosition(source_pos)); |
| |
| const intptr_t target_pos = target_block->start_pos(); |
| |
| Location target; |
| Location source; |
| |
| #if defined(DEBUG) |
| LiveRange* source_cover = NULL; |
| LiveRange* target_cover = NULL; |
| #endif |
| |
| LiveRange* range = parent; |
| while ((range != NULL) && (source.IsInvalid() || target.IsInvalid())) { |
| if (range->CanCover(source_pos)) { |
| ASSERT(source.IsInvalid()); |
| source = range->assigned_location(); |
| #if defined(DEBUG) |
| source_cover = range; |
| #endif |
| } |
| if (range->CanCover(target_pos)) { |
| ASSERT(target.IsInvalid()); |
| target = range->assigned_location(); |
| #if defined(DEBUG) |
| target_cover = range; |
| #endif |
| } |
| |
| range = range->next_sibling(); |
| } |
| |
| TRACE_ALLOC(OS::Print("connecting v%"Pd" between [%"Pd", %"Pd") {%s} " |
| "to [%"Pd", %"Pd") {%s}\n", |
| parent->vreg(), |
| source_cover->Start(), |
| source_cover->End(), |
| source.Name(), |
| target_cover->Start(), |
| target_cover->End(), |
| target.Name())); |
| |
| // Siblings were allocated to the same register. |
| if (source.Equals(target)) return; |
| |
| // Values are eagerly spilled. Spill slot already contains appropriate value. |
| if (TargetLocationIsSpillSlot(parent, target)) { |
| return; |
| } |
| |
| Instruction* last = source_block->last_instruction(); |
| if ((last->SuccessorCount() == 1) && !source_block->IsGraphEntry()) { |
| ASSERT(last->IsGoto()); |
| last->AsGoto()->GetParallelMove()->AddMove(target, source); |
| } else { |
| target_block->GetParallelMove()->AddMove(target, source); |
| } |
| } |
| |
| |
| void FlowGraphAllocator::ResolveControlFlow() { |
| // Resolve linear control flow between touching split siblings |
| // inside basic blocks. |
| for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) { |
| LiveRange* range = live_ranges_[vreg]; |
| if (range == NULL) continue; |
| |
| while (range->next_sibling() != NULL) { |
| LiveRange* sibling = range->next_sibling(); |
| TRACE_ALLOC(OS::Print("connecting [%"Pd", %"Pd") [", |
| range->Start(), range->End())); |
| TRACE_ALLOC(range->assigned_location().Print()); |
| TRACE_ALLOC(OS::Print("] to [%"Pd", %"Pd") [", |
| sibling->Start(), sibling->End())); |
| TRACE_ALLOC(sibling->assigned_location().Print()); |
| TRACE_ALLOC(OS::Print("]\n")); |
| if ((range->End() == sibling->Start()) && |
| !TargetLocationIsSpillSlot(range, sibling->assigned_location()) && |
| !range->assigned_location().Equals(sibling->assigned_location()) && |
| !IsBlockEntry(range->End())) { |
| AddMoveAt(sibling->Start(), |
| sibling->assigned_location(), |
| range->assigned_location()); |
| } |
| range = sibling; |
| } |
| } |
| |
| // Resolve non-linear control flow across branches. |
| for (intptr_t i = 1; i < block_order_.length(); i++) { |
| BlockEntryInstr* block = block_order_[i]; |
| BitVector* live = liveness_.GetLiveInSet(block); |
| for (BitVector::Iterator it(live); !it.Done(); it.Advance()) { |
| LiveRange* range = GetLiveRange(it.Current()); |
| for (intptr_t j = 0; j < block->PredecessorCount(); j++) { |
| ConnectSplitSiblings(range, block->PredecessorAt(j), block); |
| } |
| } |
| } |
| |
| // Eagerly spill values. |
| // TODO(vegorov): if value is spilled on the cold path (e.g. by the call) |
| // this will cause spilling to occur on the fast path (at the definition). |
| for (intptr_t i = 0; i < spilled_.length(); i++) { |
| LiveRange* range = spilled_[i]; |
| if (range->assigned_location().IsStackSlot() || |
| range->assigned_location().IsDoubleStackSlot() || |
| range->assigned_location().IsConstant()) { |
| ASSERT(range->assigned_location().Equals(range->spill_slot())); |
| } else { |
| AddMoveAt(range->Start() + 1, |
| range->spill_slot(), |
| range->assigned_location()); |
| } |
| } |
| } |
| |
| |
| void FlowGraphAllocator::CollectRepresentations() { |
| // Parameters. |
| GraphEntryInstr* graph_entry = flow_graph_.graph_entry(); |
| for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); ++i) { |
| Definition* def = (*graph_entry->initial_definitions())[i]; |
| value_representations_[def->ssa_temp_index()] = def->representation(); |
| } |
| |
| for (BlockIterator it = flow_graph_.reverse_postorder_iterator(); |
| !it.Done(); |
| it.Advance()) { |
| BlockEntryInstr* block = it.Current(); |
| // Phis. |
| if (block->IsJoinEntry()) { |
| JoinEntryInstr* join = block->AsJoinEntry(); |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| if ((phi != NULL) && (phi->ssa_temp_index() >= 0)) { |
| value_representations_[phi->ssa_temp_index()] = phi->representation(); |
| } |
| } |
| } |
| // Normal instructions. |
| for (ForwardInstructionIterator instr_it(block); |
| !instr_it.Done(); |
| instr_it.Advance()) { |
| Definition* def = instr_it.Current()->AsDefinition(); |
| if ((def != NULL) && (def->ssa_temp_index() >= 0)) { |
| value_representations_[def->ssa_temp_index()] = def->representation(); |
| } |
| } |
| } |
| } |
| |
| |
| void FlowGraphAllocator::AllocateRegisters() { |
| CollectRepresentations(); |
| |
| EliminateEnvironments(); |
| |
| liveness_.Analyze(); |
| |
| NumberInstructions(); |
| |
| DiscoverLoops(); |
| |
| BuildLiveRanges(); |
| |
| if (FLAG_print_ssa_liveness) { |
| liveness_.Dump(); |
| } |
| |
| if (FLAG_print_ssa_liveranges) { |
| const Function& function = flow_graph_.parsed_function().function(); |
| |
| OS::Print("-- [before ssa allocator] ranges [%s] ---------\n", |
| function.ToFullyQualifiedCString()); |
| PrintLiveRanges(); |
| OS::Print("----------------------------------------------\n"); |
| |
| OS::Print("-- [before ssa allocator] ir [%s] -------------\n", |
| function.ToFullyQualifiedCString()); |
| FlowGraphPrinter printer(flow_graph_, true); |
| printer.PrintBlocks(); |
| OS::Print("----------------------------------------------\n"); |
| } |
| |
| PrepareForAllocation(Location::kRegister, |
| kNumberOfCpuRegisters, |
| unallocated_cpu_, |
| cpu_regs_, |
| blocked_cpu_registers_); |
| AllocateUnallocatedRanges(); |
| |
| cpu_spill_slot_count_ = spill_slots_.length(); |
| spill_slots_.Clear(); |
| quad_spill_slots_.Clear(); |
| |
| PrepareForAllocation(Location::kFpuRegister, |
| kNumberOfFpuRegisters, |
| unallocated_xmm_, |
| fpu_regs_, |
| blocked_fpu_registers_); |
| AllocateUnallocatedRanges(); |
| |
| ResolveControlFlow(); |
| |
| GraphEntryInstr* entry = block_order_[0]->AsGraphEntry(); |
| ASSERT(entry != NULL); |
| intptr_t double_spill_slot_count = spill_slots_.length() * kDoubleSpillFactor; |
| entry->set_spill_slot_count(cpu_spill_slot_count_ + double_spill_slot_count); |
| |
| if (FLAG_print_ssa_liveranges) { |
| const Function& function = flow_graph_.parsed_function().function(); |
| |
| OS::Print("-- [after ssa allocator] ranges [%s] ---------\n", |
| function.ToFullyQualifiedCString()); |
| PrintLiveRanges(); |
| OS::Print("----------------------------------------------\n"); |
| |
| OS::Print("-- [after ssa allocator] ir [%s] -------------\n", |
| function.ToFullyQualifiedCString()); |
| FlowGraphPrinter printer(flow_graph_, true); |
| printer.PrintBlocks(); |
| OS::Print("----------------------------------------------\n"); |
| } |
| } |
| |
| |
| } // namespace dart |