For the values defined in the loop and spilled outside sink spill store out of the loop down to loo…

src/lithium-allocator.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 121 matching lines @@
       is_double_(false),
       assigned_register_(kInvalidAssignment),
       last_interval_(NULL),
       first_interval_(NULL),
       first_pos_(NULL),
       parent_(NULL),
       next_(NULL),
       current_interval_(NULL),
       last_processed_use_(NULL),
       spill_operand_(new(zone) LOperand()),
-      spill_start_index_(kMaxInt) { }
+      spill_start_index_(kMaxInt),
+      spill_source_(NULL) { }
 
 
 void LiveRange::set_assigned_register(int reg,
                                       RegisterKind register_kind,
                                       Zone* zone) {
   ASSERT(!HasRegisterAssigned() && !IsSpilled());
   assigned_register_ = reg;
   is_double_ = (register_kind == DOUBLE_REGISTERS);
   ConvertOperands(zone);
 }
@@ skipping 381 matching lines @@
     : zone_(graph->zone()),
       chunk_(NULL),
       live_in_sets_(graph->blocks()->length(), zone_),
       live_ranges_(num_values * 2, zone_),
       fixed_live_ranges_(NULL),
       fixed_double_live_ranges_(NULL),
       unhandled_live_ranges_(num_values * 2, zone_),
       active_live_ranges_(8, zone_),
       inactive_live_ranges_(8, zone_),
       reusable_slots_(8, zone_),
+      pending_spilled_(8, zone_),
       next_virtual_register_(num_values),
       first_artificial_register_(num_values),
       mode_(GENERAL_REGISTERS),
       num_registers_(-1),
       graph_(graph),
       has_osr_entry_(false),
       allocation_ok_(true) { }
 
 
 void LAllocator::InitializeLivenessAnalysis() {
@@ skipping 237 matching lines @@
       if (temp->HasFixedPolicy()) {
         AllocateFixed(temp, gap_index - 1, false);
       }
     }
   }
 
   // Handle fixed output operand.
   if (first != NULL && first->Output() != NULL) {
     LUnallocated* first_output = LUnallocated::cast(first->Output());
     LiveRange* range = LiveRangeFor(first_output->virtual_register());
-    bool assigned = false;
     if (first_output->HasFixedPolicy()) {
       LUnallocated* output_copy = first_output->CopyUnconstrained(zone());
       bool is_tagged = HasTaggedValue(first_output->virtual_register());
       AllocateFixed(first_output, gap_index, is_tagged);
 
       // This value is produced on the stack, we never need to spill it.
       if (first_output->IsStackSlot()) {
         range->SetSpillOperand(first_output);
-        range->SetSpillStartIndex(gap_index - 1);
-        assigned = true;
+        range->set_spill_start_index(gap_index - 1);
       }
       chunk_->AddGapMove(gap_index, first_output, output_copy);
     }
 
-    if (!assigned) {
-      range->SetSpillStartIndex(gap_index);
+    if (!range->HasAllocatedSpillOperand()) {
+      // Instructions that are emitted at uses produce values multiple times
+      // from different spill sources. There is however no dominance relation
+      // between different occurrence of the same constant and thus we have to
+      // emit spill stores eagerly at all of them.
+      if (range->spill_source() != NULL) {
+        if (range->HasPendingSpillStore()) {
+          EmitSpillStore(range);
+          range->DisableSpillStoreSinking();
+        }
 
-      // This move to spill operand is not a real use. Liveness analysis
-      // and splitting of live ranges do not account for it.
-      // Thus it should be inserted to a lifetime position corresponding to
-      // the instruction end.
-      LGap* gap = GapAt(gap_index);
-      LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE, zone());
-      move->AddMove(first_output, range->GetSpillOperand(), zone());
+        EmitSpillStore(gap_index, first_output, range->GetSpillOperand());
+      } else {
+        range->set_spill_start_index(gap_index);
+        range->set_spill_source(first_output);
+      }
     }
   }
 
   // Handle fixed input operands of second instruction.
   if (second != NULL) {
     for (UseIterator it(second); !it.Done(); it.Advance()) {
       LUnallocated* cur_input = LUnallocated::cast(it.Current());
       if (cur_input->HasFixedPolicy()) {
         LUnallocated* input_copy = cur_input->CopyUnconstrained(zone());
         bool is_tagged = HasTaggedValue(cur_input->virtual_register());
@@ skipping 211 matching lines @@
       if (branch->HasPointerMap()) {
         if (phi->representation().IsTagged()) {
           branch->pointer_map()->RecordPointer(phi_operand, zone());
         } else if (!phi->representation().IsDouble()) {
           branch->pointer_map()->RecordUntagged(phi_operand, zone());
         }
       }
     }
 
     LiveRange* live_range = LiveRangeFor(phi->id());
-    LLabel* label = chunk_->GetLabel(phi->block()->block_id());
-    label->GetOrCreateParallelMove(LGap::START, zone())->
-        AddMove(phi_operand, live_range->GetSpillOperand(), zone());
-    live_range->SetSpillStartIndex(phi->block()->first_instruction_index());
+    live_range->set_spill_start_index(phi->block()->first_instruction_index());
+    live_range->set_spill_source(phi_operand);
   }
 }
 
+
+void LAllocator::TrySinkSpillStoreTo(LiveRange* range, HBasicBlock* block) {
+  LifetimePosition pos = LifetimePosition::FromInstructionIndex(
+      block->first_instruction_index());
+
+  if (!range->Covers(pos)) {
+    // For now we are limiting sinking to the case when initial live range
+    // extends beyond the loop and covers the position to which we are trying
+    // to sink the spill store.
+    return;
+  }
+
+  // Check that selected position dominates all spilled siblings.
+  for (LiveRange* sibling = range; sibling != NULL; sibling = sibling->next()) {
+    if (!sibling->IsSpilled()) {
+      continue;
+    }
+
+    if (pos.Value() > sibling->Start().Value()) {
+      return;
+    }
+
+    HBasicBlock* sibling_block = GetBlock(sibling->Start());
+    if ((block != sibling_block) && !block->Dominates(sibling_block)) {
+      return;
+    }
+  }
+
+  // Sink the spill store.
+  range->set_spill_source(range->CreateAssignedOperand(zone()));
+  range->set_spill_start_index(pos.InstructionIndex());
+}
+
+
+void LAllocator::SinkSpillStores() {
+  for (int i = 0; i < pending_spilled_.length(); i++) {
+    LiveRange* range = pending_spilled_[i];
+
+    HBasicBlock* range_block = GetBlock(range->Start());
+
+    HBasicBlock* loop_header = range_block->IsLoopHeader() ?
+        range_block : range_block->parent_loop_header();
+    ASSERT(loop_header != NULL);
+
+    HBasicBlock* block = loop_header->loop_information()->exit_block();

[danno, 2013/01/10 15:33:27]

How about a loop here that tries to spill to the outer-most first and backs off
to the most nested loop (which is what you currently handle?)

[Vyacheslav Egorov (Google), 2013/01/25 13:49:17]

Done.

+    if (block != NULL) {
+      TrySinkSpillStoreTo(range, block);
+    }
+
+    EmitSpillStore(range);
+  }
+}
+
 
 bool LAllocator::Allocate(LChunk* chunk) {
   ASSERT(chunk_ == NULL);
   chunk_ = static_cast<LPlatformChunk*>(chunk);
   MeetRegisterConstraints();
   if (!AllocationOk()) return false;
   ResolvePhis();
   BuildLiveRanges();
   AllocateGeneralRegisters();
   if (!AllocationOk()) return false;
   AllocateDoubleRegisters();
   if (!AllocationOk()) return false;
+
+  // Sink pending spill stores down to loop exits. Should be done before
+  // pointer maps are populated.
+  SinkSpillStores();
+
   PopulatePointerMaps();
   if (has_osr_entry_) ProcessOsrEntry();
   ConnectRanges();
   ResolveControlFlow();
   return true;
 }
 
 
 void LAllocator::MeetRegisterConstraints() {
   HPhase phase("L_Register constraints", chunk_);
@@ skipping 999 matching lines @@
 
 void LAllocator::Spill(LiveRange* range) {
   ASSERT(!range->IsSpilled());
   TraceAlloc("Spilling live range %d\n", range->id());
   LiveRange* first = range->TopLevel();
 
   if (!first->HasAllocatedSpillOperand()) {
     LOperand* op = TryReuseSpillSlot(range);
     if (op == NULL) op = chunk_->GetNextSpillSlot(mode_ == DOUBLE_REGISTERS);
     first->SetSpillOperand(op);
+
+    // This is the first time we are spilling a sibling of this range.
+    // If the spill store was not eagerly at parent's start then we need

[danno, 2013/01/10 15:33:27]

nit: not eagerly emitted

[Vyacheslav Egorov (Google), 2013/01/25 13:49:17]

Done.

+    // to either emit it eagerly or postpone it for spill store sinking pass.
+    if (first->HasPendingSpillStore()) {
+      HBasicBlock* first_block = GetBlock(first->Start());
+      HBasicBlock* loop_header = first_block->IsLoopHeader() ?
+          first_block : first_block->parent_loop_header();
+      if ((first != range) &&
+          (loop_header != NULL) &&
+          (GetBlock(range->Start())->parent_loop_header() != loop_header)) {

[danno, 2013/01/10 15:33:27]

Why don't you have to handle the case there
GetBlock(range->Start()->IsLoopHeader()) is true in a slightly different way
like you do with first_block?

[Vyacheslav Egorov (Google), 2013/01/25 13:49:17]

Done.

+        // If the range was defined inside the loop but is spilled outside then
+        // we should try to sink corresponding spill store out of the loop to
+        // reduce amount of memory writes.

[danno, 2013/01/10 15:33:27]

You check that it's a different loop, but don't you need to check the loop depth
of loop_header and and GetBlock(range->Start())->parent_loop_header()? You don't
want to make the situation worse by moving a spill from a loop into an inner
loop? Oh, I see. I suppose this is handled by making sure to always trying to
sink to the exit_block().

[Vyacheslav Egorov (Google), 2013/01/25 13:49:17]

We are always moving spilling *up*, so it can't go into loops that are deeper
nested.

+        pending_spilled_.Add(first, zone_);
+      } else {
+        EmitSpillStore(first);
+      }
+    }
   }
   range->MakeSpilled(zone_);
 }
 
 
+void LAllocator::EmitSpillStore(LiveRange* range) {
+  ASSERT(range->HasPendingSpillStore());
+  EmitSpillStore(range->spill_start_index(),
+                 range->spill_source(),
+                 range->GetSpillOperand());
+}
+
+
+void LAllocator::EmitSpillStore(int pos, LOperand* source, LOperand* spill) {
+  // This move to spill operand is not a real use. Liveness analysis
+  // and splitting of live ranges do not account for it.
+  // Thus it should be inserted to a lifetime position corresponding to
+  // the instruction end.
+  LGap* gap = GapAt(pos);
+  LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE, zone());
+  move->AddMove(source, spill, zone());
+}
+
+
 int LAllocator::RegisterCount() const {
   return num_registers_;
 }
 
 
 #ifdef DEBUG
 
 
 void LAllocator::Verify() const {
   for (int i = 0; i < live_ranges()->length(); ++i) {
     LiveRange* current = live_ranges()->at(i);
     if (current != NULL) current->Verify();
   }
 }
 
 
 #endif
 
 
 } }  // namespace v8::internal