Add support for fixed parameters in the register allocator.

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2012, 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_builder.h"
@@ skipping 121 matching lines @@
               BlockEntryInstr* pred = block->PredecessorAt(k);
               const intptr_t use = val->AsUse()->definition()->ssa_temp_index();
               live_out_[pred->postorder_number()]->Add(use);
             }
           }
         }
       }
     }
   }
 
+  // Process incomming parameters.

[srdjan, 2012/07/26 00:33:56]

s/incomming/incoming/

[Vyacheslav Egorov (Google), 2012/07/26 11:33:53]

Done.

+  GraphEntryInstr* graph_entry = postorder_[block_count - 1]->AsGraphEntry();
+  for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) {
+    Value* val = graph_entry->start_env()->values()[i];
+    if (val->IsUse()) {
+      const intptr_t vreg = val->AsUse()->definition()->ssa_temp_index();
+      kill_[0]->Add(vreg);

[Kevin Millikin (Google), 2012/07/26 09:29:08]

It probably doesn't make a big difference to anything, but I don't understand
why the incoming parameters are not live at the graph entry.

[Vyacheslav Egorov (Google), 2012/07/26 11:33:53]

It does not change anything. I just choose to define them at graph entry.

+      live_in_[0]->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]);
   }
 }
 
 
 bool FlowGraphAllocator::UpdateLiveOut(const BlockEntryInstr& instr) {
   BitVector* live_out = live_out_[instr.postorder_number()];
@@ skipping 237 matching lines @@
     while (current != block) {
       // Skip parallel moves that we insert while processing instructions.
       if (!current->IsParallelMove()) {
         ProcessOneInstruction(block, current);
       }
       current = current->previous();
     }
 
     ConnectIncomingPhiMoves(block);
   }
+
+  // Process incomming parameters.

[srdjan, 2012/07/26 00:33:56]

ditto

[Vyacheslav Egorov (Google), 2012/07/26 11:33:53]

Done.

+  GraphEntryInstr* graph_entry = postorder_[block_count - 1]->AsGraphEntry();
+  for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) {
+    Value* val = graph_entry->start_env()->values()[i];
+    if (val->IsUse()) {
+      ParameterInstr* param = val->AsUse()->definition()->AsParameter();
+
+      LiveRange* range = GetLiveRange(param->ssa_temp_index());
+      range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos());
+      range->DefineAt(graph_entry->start_pos());
+      range->set_assigned_location(Location::StackSlot(param->index()));
+
+      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());
+        AddToUnallocated(tail);
+      }
+      ConvertAllUses(range);
+    }
+  }
 }
 
 //
 // When describing shape of live ranges in comments below we are going to use
 // the following notation:
 //
 //    B  block entry
 //    g  goto instruction
 //    m  parallel move
 //    i  any other instruction
@@ skipping 131 matching lines @@
   const intptr_t pos = current->lifetime_position();
   ASSERT(IsInstructionPosition(pos));
 
   LocationSummary* locs = current->locs();
 
   // TODO(vegorov): number of inputs must match number of input locations.
   if (locs->input_count() != current->InputCount()) {
     builder_->Bailout("ssa allocator: number of input locations mismatch");
   }
 
+  // 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).IsRegister())) {
+    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) {
     // 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:
     //
@@ skipping 528 matching lines @@
       return i;
     }
   }
   spill_slots_.Add(0);
   return spill_slots_.length() - 1;
 }
 
 
 void FlowGraphAllocator::Spill(LiveRange* range) {
   const intptr_t spill_index = AllocateSpillSlotFor(range);
-  ASSERT(spill_slots_[spill_index] < range->Start());
+  ASSERT(spill_slots_[spill_index] <= range->Start());
   spill_slots_[spill_index] = range->End();
-  range->set_assigned_location(Location::SpillSlot(spill_index));
+  range->set_assigned_location(Location::StackSlot(spill_index));
   ConvertAllUses(range);
 }
 
 
 intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated(
   Register reg, LiveRange* unallocated) {
   intptr_t intersection = kMaxPosition;
   for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) {
     LiveRange* allocated = cpu_regs_[reg][i];
     if (allocated == NULL) continue;
@@ skipping 457 matching lines @@
       LiveRange* range = GetLiveRange(it.Current());
       for (intptr_t j = 0; j < block->PredecessorCount(); j++) {
         ConnectSplitSiblings(range, block->PredecessorAt(j), block);
       }
     }
   }
 }
 
 
 void FlowGraphAllocator::AllocateRegisters() {
-  GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
-  ASSERT(entry != NULL);
-
-  for (intptr_t i = 0; i < entry->start_env()->values().length(); i++) {
-    if (entry->start_env()->values()[i]->IsUse()) {
-      builder_->Bailout("ssa allocator: unsupported start environment");
-    }
-  }
-
   AnalyzeLiveness();
 
   BuildLiveRanges();
 
   if (FLAG_print_ssa_liveness) {
     DumpLiveness();
   }
 
   if (FLAG_trace_ssa_allocator) {
     PrintLiveRanges();
   }
 
   AllocateCPURegisters();
 
   ResolveControlFlow();
 
+  GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
+  ASSERT(entry != NULL);
+  entry->set_spill_slot_count(spill_slots_.length());
+
   if (FLAG_trace_ssa_allocator) {
     OS::Print("-- ir after allocation -------------------------\n");
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart