[turbofan] Avoid large deopt blocks

src/compiler/register-allocator.cc

Index: src/compiler/register-allocator.cc
diff --git a/src/compiler/register-allocator.cc b/src/compiler/register-allocator.cc
index efcdcb42e64eb79ef0546c0215c1974feb5bb6c8..e2df7bbba3301c469446d50bcf306b6da7420307 100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -342,6 +342,11 @@ UsePositionHintType UsePosition::HintTypeForOperand(
   return UsePositionHintType::kNone;
 }
 
+void UsePosition::SetHint(UsePosition* use_pos) {
+  DCHECK_NOT_NULL(use_pos);
+  hint_ = use_pos;
+  flags_ = HintTypeField::update(flags_, UsePositionHintType::kUsePos);
+}
 
 void UsePosition::ResolveHint(UsePosition* use_pos) {
   DCHECK_NOT_NULL(use_pos);
@@ -581,7 +586,10 @@ void LiveRange::AdvanceLastProcessedMarker(
 LiveRange* LiveRange::SplitAt(LifetimePosition position, Zone* zone) {
   int new_id = TopLevel()->GetNextChildId();
   LiveRange* child = new (zone) LiveRange(new_id, representation(), TopLevel());
-  DetachAt(position, child, zone);
+  // If we split, we do so because we're about to switch registers or move
+  // to/from

[Jarin, 2016/09/29 14:20:34]

nit: merge the comment with the next line.

+  // a slot, so there's no value in connecting hints.
+  DetachAt(position, child, zone, false);
 
   child->top_level_ = TopLevel();
   child->next_ = next_;
@@ -589,9 +597,8 @@ LiveRange* LiveRange::SplitAt(LifetimePosition position, Zone* zone) {
   return child;
 }
 
-
 UsePosition* LiveRange::DetachAt(LifetimePosition position, LiveRange* result,
-                                 Zone* zone) {
+                                 Zone* zone, bool connect_hints) {
   DCHECK(Start() < position);
   DCHECK(End() > position);
   DCHECK(result->IsEmpty());
@@ -670,6 +677,9 @@ UsePosition* LiveRange::DetachAt(LifetimePosition position, LiveRange* result,
   last_processed_use_ = nullptr;
   current_interval_ = nullptr;
 
+  if (connect_hints && use_before != nullptr && use_after != nullptr) {
+    use_after->SetHint(use_before);
+  }
 #ifdef DEBUG
   VerifyChildStructure();
   result->VerifyChildStructure();
@@ -716,6 +726,18 @@ bool LiveRange::ShouldBeAllocatedBefore(const LiveRange* other) const {
   LifetimePosition start = Start();
   LifetimePosition other_start = other->Start();
   if (start == other_start) {
+    bool this_is_splinter = TopLevel()->IsSplinter();
+    bool other_is_splinter = other->TopLevel()->IsSplinter();
+    if (this_is_splinter && other_is_splinter &&
+        (this->FirstHintPosition() == nullptr) ==
+            (other->FirstHintPosition() == nullptr)) {
+      if (this->FirstHintPosition() != nullptr &&
+          other->FirstHintPosition() == nullptr)

[Jarin, 2016/09/29 14:20:35]

I have no idea what these conditions say.

The condition in the outer "if" says "(this->FirstHintPosition() == nullptr) ==
(other->FirstHintPosition() == nullptr)", so "this->FirstHintPosition() !=
nullptr && other->FirstHintPosition() == nullptr" will be always false, no?

[Mircea Trofin, 2016/09/30 05:16:51]

Ya, they make no sense as written. Fixed.

+        return true;
+      if (this->FirstHintPosition() == nullptr &&
+          other->FirstHintPosition() != nullptr)

[Jarin, 2016/09/29 14:20:35]

Also seems to be always false, which means that all this newly introduced block
is a no-op?

In any case, such complicated conditions need some explanation in comments.

[Mircea Trofin, 2016/09/30 05:16:51]

Acknowledged.

+        return false;
+    }
     UsePosition* pos = first_pos();
     if (pos == nullptr) return false;
     UsePosition* other_pos = other->first_pos();
@@ -912,17 +934,20 @@ void TopLevelLiveRange::Splinter(LifetimePosition start, LifetimePosition end,
 
   if (end >= End()) {
     DCHECK(start > Start());
-    DetachAt(start, &splinter_temp, zone);
+    DetachAt(start, &splinter_temp, zone, true);

[Jarin, 2016/09/29 14:20:35]

Here it is not really clear what "true" refers to. Could you introduce an enum
for readability?

[Mircea Trofin, 2016/09/30 05:16:51]

Done.

     next_ = nullptr;
   } else {
     DCHECK(start < End() && Start() < end);
 
     const int kInvalidId = std::numeric_limits<int>::max();
 
-    UsePosition* last = DetachAt(start, &splinter_temp, zone);
+    UsePosition* last = DetachAt(start, &splinter_temp, zone, true);
 
     LiveRange end_part(kInvalidId, this->representation(), nullptr);
-    last_in_splinter = splinter_temp.DetachAt(end, &end_part, zone);
+    // The last chunk exits the deferred region, and we don't want to connect
+    // hints here, because the non-deferred region shouldn't be affected
+    // by allocation decisions on the deferred path.
+    last_in_splinter = splinter_temp.DetachAt(end, &end_part, zone, false);
 
     next_ = end_part.next_;
     last_interval_->set_next(end_part.first_interval_);
@@ -2401,7 +2426,13 @@ void RegisterAllocator::SplitAndSpillRangesDefinedByMemoryOperand() {
     if (next_pos.IsGapPosition()) {
       next_pos = next_pos.NextStart();
     }
-    UsePosition* pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
+
+    // With splinters, we can be more strict and skip over positions
+    // not strictly needing registers.
+    UsePosition* pos =
+        range->IsSplinter()
+            ? range->NextRegisterPosition(next_pos)
+            : range->NextUsePositionRegisterIsBeneficial(next_pos);

[Jarin, 2016/09/29 14:20:35]

Does this make any measurable difference?

[Mircea Trofin, 2016/09/30 05:16:51]

I remember seeing a case where this helped avoid a split and therefore a move.

     // If the range already has a spill operand and it doesn't need a
     // register immediately, split it and spill the first part of the range.
     if (pos == nullptr) {
@@ -2804,6 +2835,29 @@ bool LinearScanAllocator::TryAllocateFreeReg(LiveRange* current) {
     }
   }
 
+  if (current->TopLevel()->IsSplinter()) {
+    // We weren't able to give the splinter the hinted register. Whatever we do,
+    // it will result in a move. For splinters, our goal is to minimize

[Jarin, 2016/09/29 14:20:35]

I do not understand this reasoning - if there is no hint, then I do not see why
we would have to insert a move. Could you explain?

[Mircea Trofin, 2016/09/30 05:16:51]

The hint says, for splinters, what operand the previous range segment had (the
parent one). So if we can meet the hint, we don't need to move.

[Jarin, 2016/09/30 13:23:03]

I still do not really understand when we get here. How do you even know that
there was any hinted position when we get here? Are you sure that not meeting
hint automatically means inserting move (could not it be that we just have to
use less efficient instruction encoding or some such?)

[Mircea Trofin, 2016/09/30 14:45:48]

The hints for splinters are added when we create them, and they are 
the last operand that brings the value into the splinter interval. The splinter
range itself is interrupted by intervals where the range is not deferred, so
whenever a new deferred interval is added to the splinter range, its top gets
hint-linked this way.

Since linear scan works top-down, we would have already allocated the segments
above the splinter.

If we don't match the hint, we'll need somehow to transfer the value
of the vreg, so that's where the move comes from. 

+    // moves, for code size, not their quality - meaning, no need to try hard
+    // and keep the value in a register.
+    // If we can spill the whole range, great. Otherwise, split above the
+    // first use needing a register and spill the top part. No need to involve
+    // the hint (e.g. what if we could give the upper chunk the hint), because
+    // we

[Jarin, 2016/09/29 14:20:35]

What's up with the formatting of the comments in the CL?

[Mircea Trofin, 2016/09/30 05:16:51]

probably git cl format :) I'll re-brush them.

+    // would then have at least the same number of moves.
+    const UsePosition* next_reg =
+        current->NextRegisterPosition(current->Start());
+    if (next_reg == nullptr) {
+      Spill(current);
+      return true;
+    } else if (next_reg->pos().PrevStart() > current->Start()) {
+      LiveRange* tail = SplitRangeAt(current, next_reg->pos().PrevStart());
+      AddToUnhandledSorted(tail);
+      Spill(current);
+      return true;
+    }
+  }
+
   // Find the register which stays free for the longest time.
   int reg = codes[0];
   for (int i = 1; i < num_codes; ++i) {