[turbofan] Avoid large deopt blocks

src/compiler/register-allocator.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/base/adapters.h"
 #include "src/compiler/linkage.h"
 #include "src/compiler/register-allocator.h"
 #include "src/string-stream.h"
 
 namespace v8 {
@@ skipping 324 matching lines @@
         DCHECK(op.IsStackSlot() || op.IsFPStackSlot());
         return UsePositionHintType::kNone;
       }
     case InstructionOperand::INVALID:
       break;
   }
   UNREACHABLE();
   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);
   if (HintTypeField::decode(flags_) != UsePositionHintType::kUnresolved) return;
   hint_ = use_pos;
   flags_ = HintTypeField::update(flags_, UsePositionHintType::kUsePos);
 }
 
 
 void UsePosition::set_type(UsePositionType type, bool register_beneficial) {
@@ skipping 219 matching lines @@
                                : current_interval_->start();
   if (to_start_of->start() > start) {
     current_interval_ = to_start_of;
   }
 }
 
 
 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_;
   next_ = child;
   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());
   // Find the last interval that ends before the position. If the
   // position is contained in one of the intervals in the chain, we
   // split that interval and use the first part.
   UseInterval* current = FirstSearchIntervalForPosition(position);
 
   // If the split position coincides with the beginning of a use interval
   // we need to split use positons in a special way.
@@ skipping 58 matching lines @@
   } else {
     first_pos_ = nullptr;
   }
   result->first_pos_ = use_after;
 
   // Discard cached iteration state. It might be pointing
   // to the use that no longer belongs to this live range.
   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();
 #endif
   return use_before;
 }
 
 
 void LiveRange::UpdateParentForAllChildren(TopLevelLiveRange* new_top_level) {
   LiveRange* child = this;
@@ skipping 26 matching lines @@
 
 // This implements an ordering on live ranges so that they are ordered by their
 // start positions.  This is needed for the correctness of the register
 // allocation algorithm.  If two live ranges start at the same offset then there
 // is a tie breaker based on where the value is first used.  This part of the
 // ordering is merely a heuristic.
 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();
     if (other_pos == nullptr) return true;
     return pos->pos() < other_pos->pos();
   }
   return start < other_start;
 }
 
 
@@ skipping 176 matching lines @@
 
   TopLevelLiveRange splinter_temp(-1, representation());
   UsePosition* last_in_splinter = nullptr;
   // Live ranges defined in deferred blocks stay in deferred blocks, so we
   // don't need to splinter them. That means that start should always be
   // after the beginning of the range.
   DCHECK(start > Start());
 
   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_);
     // The next splinter will happen either at or after the current interval.
     // We can optimize DetachAt by setting current_interval_ accordingly,
     // which will then be picked up by FirstSearchIntervalForPosition.
     current_interval_ = last_interval_;
     last_interval_ = end_part.last_interval_;
 
     if (first_pos_ == nullptr) {
@@ skipping 1458 matching lines @@
         (range->HasSpillRange() && !range->has_slot_use())) {
       continue;
     }
     LifetimePosition start = range->Start();
     TRACE("Live range %d:%d is defined by a spill operand.\n",
           range->TopLevel()->vreg(), range->relative_id());
     LifetimePosition next_pos = start;
     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) {
       Spill(range);
     } else if (pos->pos() > range->Start().NextStart()) {
       // Do not spill live range eagerly if use position that can benefit from
       // the register is too close to the start of live range.
       LifetimePosition split_pos = GetSplitPositionForInstruction(
           range, pos->pos().ToInstructionIndex());
       // There is no place to split, so we can't split and spill.
@@ skipping 382 matching lines @@
     // The desired register is free until the end of the current live range.
     if (free_until_pos[hint_register] >= current->End()) {
       TRACE("Assigning preferred reg %s to live range %d:%d\n",
             RegisterName(hint_register), current->TopLevel()->vreg(),
             current->relative_id());
       SetLiveRangeAssignedRegister(current, hint_register);
       return true;
     }
   }
 
+  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) {
     int code = codes[i];
     if (free_until_pos[code] > free_until_pos[reg]) {
       reg = code;
     }
   }
 
   LifetimePosition pos = free_until_pos[reg];
@@ skipping 803 matching lines @@
         }
       }
     }
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8