From ae064fca48da36f0c1704f6607ee06ea02443487 Mon Sep 17 00:00:00 2001
From: "vegorov@chromium.org"
 <vegorov@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Fri, 15 Mar 2013 13:25:54 +0000
Subject: [PATCH] When spilling live range with not register uses inside the
 loop try to move spilling out of the loop.

This allows to minimize amount of memory moves on the back edge.

R=danno@chromium.org
BUG=

Review URL: https://codereview.chromium.org/11437015

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@13960 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/lithium-allocator.cc | 50 ++++++++++++++++++++++++++++++++++++++++++++++--
 src/lithium-allocator.h  |  9 +++++++++
 2 files changed, 57 insertions(+), 2 deletions(-)

diff --git a/src/lithium-allocator.cc b/src/lithium-allocator.cc
index 6ee9ef2..7049a58 100644
--- a/src/lithium-allocator.cc
+++ b/src/lithium-allocator.cc
@@ -196,6 +196,18 @@ UsePosition* LiveRange::NextUsePositionRegisterIsBeneficial(
 }
 
 
+UsePosition* LiveRange::PreviousUsePositionRegisterIsBeneficial(
+    LifetimePosition start) {
+  UsePosition* pos = first_pos();
+  UsePosition* prev = NULL;
+  while (pos != NULL && pos->pos().Value() < start.Value()) {
+    if (pos->RegisterIsBeneficial()) prev = pos;
+    pos = pos->next();
+  }
+  return prev;
+}
+
+
 UsePosition* LiveRange::NextRegisterPosition(LifetimePosition start) {
   UsePosition* pos = NextUsePosition(start);
   while (pos != NULL && !pos->RequiresRegister()) {
@@ -1943,6 +1955,39 @@ void LAllocator::AllocateBlockedReg(LiveRange* current) {
 }
 
 
+LifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range,
+                                                    LifetimePosition pos) {
+  HBasicBlock* block = GetBlock(pos.InstructionStart());
+  HBasicBlock* loop_header =
+      block->IsLoopHeader() ? block : block->parent_loop_header();
+
+  if (loop_header == NULL) return pos;
+
+  UsePosition* prev_use =
+    range->PreviousUsePositionRegisterIsBeneficial(pos);
+
+  while (loop_header != NULL) {
+    // We are going to spill live range inside the loop.
+    // If possible try to move spilling position backwards to loop header.
+    // This will reduce number of memory moves on the back edge.
+    LifetimePosition loop_start = LifetimePosition::FromInstructionIndex(
+        loop_header->first_instruction_index());
+
+    if (range->Covers(loop_start)) {
+      if (prev_use == NULL || prev_use->pos().Value() < loop_start.Value()) {
+        // No register beneficial use inside the loop before the pos.
+        pos = loop_start;
+      }
+    }
+
+    // Try hoisting out to an outer loop.
+    loop_header = loop_header->parent_loop_header();
+  }
+
+  return pos;
+}
+
+
 void LAllocator::SplitAndSpillIntersecting(LiveRange* current) {
   ASSERT(current->HasRegisterAssigned());
   int reg = current->assigned_register();
@@ -1951,10 +1996,11 @@ void LAllocator::SplitAndSpillIntersecting(LiveRange* current) {
     LiveRange* range = active_live_ranges_[i];
     if (range->assigned_register() == reg) {
       UsePosition* next_pos = range->NextRegisterPosition(current->Start());
+      LifetimePosition spill_pos = FindOptimalSpillingPos(range, split_pos);
       if (next_pos == NULL) {
-        SpillAfter(range, split_pos);
+        SpillAfter(range, spill_pos);
       } else {
-        SpillBetween(range, split_pos, next_pos->pos());
+        SpillBetween(range, spill_pos, next_pos->pos());
       }
       if (!AllocationOk()) return;
       ActiveToHandled(range);
diff --git a/src/lithium-allocator.h b/src/lithium-allocator.h
index 0e24d54..70f3182 100644
--- a/src/lithium-allocator.h
+++ b/src/lithium-allocator.h
@@ -311,6 +311,10 @@ class LiveRange: public ZoneObject {
   // Modifies internal state of live range!
   UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start);
 
+  // Returns use position for which register is beneficial in this live
+  // range and which precedes start.
+  UsePosition* PreviousUsePositionRegisterIsBeneficial(LifetimePosition start);
+
   // Can this live range be spilled at this position.
   bool CanBeSpilled(LifetimePosition pos);
 
@@ -539,6 +543,11 @@ class LAllocator BASE_EMBEDDED {
 
   void SplitAndSpillIntersecting(LiveRange* range);
 
+  // If we are trying to spill a range inside the loop try to
+  // hoist spill position out to the point just before the loop.
+  LifetimePosition FindOptimalSpillingPos(LiveRange* range,
+                                          LifetimePosition pos);
+
   void Spill(LiveRange* range);
   bool IsBlockBoundary(LifetimePosition pos);
 
-- 
2.7.4