Improve phi hinting heuristics.

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 cdf4e9976b6d11ff974e10cf481f8b0466693585..82b762cc7f640acfe8d1ba5ae4faf9be102d5231 100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -2200,33 +2200,96 @@ void LiveRangeBuilder::ProcessPhis(const InstructionBlock* block,
     // block.
     int phi_vreg = phi->virtual_register();
     live->Remove(phi_vreg);
-    // Select the hint from the first predecessor block that preceeds this block
-    // in the rpo ordering. Prefer non-deferred blocks. The enforcement of
-    // hinting in rpo order is required because hint resolution that happens
-    // later in the compiler pipeline visits instructions in reverse rpo,
-    // relying on the fact that phis are encountered before their hints.
-    const Instruction* instr = nullptr;
-    const InstructionBlock::Predecessors& predecessors = block->predecessors();
-    for (size_t i = 0; i < predecessors.size(); ++i) {
-      const InstructionBlock* predecessor_block =
-          code()->InstructionBlockAt(predecessors[i]);
-      if (predecessor_block->rpo_number() < block->rpo_number()) {
-        instr = GetLastInstruction(code(), predecessor_block);
-        if (!predecessor_block->IsDeferred()) break;
-      }
-    }
-    DCHECK_NOT_NULL(instr);
-
+    // Select a hint from a predecessor block that preceeds this block in the
+    // rpo order. In order of priority:
+    // - Avoid hints from deferred blocks.
+    // - Prefer hints from allocated (or explicit) operands.
+    // - Prefer hints from empty blocks (containing just parallel moves and a
+    //   jump). This helps to avoid otherwise useless move + jump sequences.

[Mircea Trofin, 2016/07/04 16:32:15]

Nit: the moves wouldn't be useless, I think you're trying to say that if the
hint comes from there and we succeed in eliding the move ("the hint is taken"),
then maybe the jump threader can elide the jump, too?

If so, mind expanding the sentence for the benefit of the reader?

[jbramley, 2016/07/04 16:58:54]

Yes, that's what I meant. I'll re-word it.

+    // The enforcement of hinting in rpo order is required because hint
+    // resolution that happens later in the compiler pipeline visits
+    // instructions in reverse rpo order, relying on the fact that phis are
+    // encountered before their hints.
     InstructionOperand* hint = nullptr;
-    for (MoveOperands* move : *instr->GetParallelMove(Instruction::END)) {
-      InstructionOperand& to = move->destination();
-      if (to.IsUnallocated() &&
-          UnallocatedOperand::cast(to).virtual_register() == phi_vreg) {
-        hint = &move->source();
-        break;
+    int hint_preference = 0;
+
+    for (RpoNumber predecessor : block->predecessors()) {
+      const InstructionBlock* predecessor_block =
+          code()->InstructionBlockAt(predecessor);
+      DCHECK_EQ(predecessor_block->rpo_number(), predecessor);
+
+      // Only take hints from earlier rpo numbers.
+      if (predecessor >= block->rpo_number()) continue;
+
+      // Look up the predecessor instruction.
+      const Instruction* predecessor_instr =
+          GetLastInstruction(code(), predecessor_block);
+      InstructionOperand* predecessor_hint = nullptr;
+      // Phis are assigned in an END move after the last instruction in each

[Mircea Trofin, 2016/07/04 16:32:15]

I think you meant to say "in the END position of the last instruction".

[jbramley, 2016/07/04 16:58:54]

Acknowledged.

+      // predecessor block.
+      for (MoveOperands* move :
+           *predecessor_instr->GetParallelMove(Instruction::END)) {
+        InstructionOperand& to = move->destination();
+        if (to.IsUnallocated() &&
+            UnallocatedOperand::cast(to).virtual_register() == phi_vreg) {
+          predecessor_hint = &move->source();
+          break;
+        }
+      }
+      DCHECK_NOT_NULL(predecessor_hint);
+
+      // For each predecessor, calculate a score according to the priorities
+      // described above, and pick the best one.
+      int predecessor_hint_preference = 0;
+      const int kNotDeferredBlockPreference = 4;
+      const int kMoveIsAllocatedPreference = 2;
+      const int kBlockIsEmptyPreference = 1;
+
+      // - Avoid hints from deferred blocks.
+      if (!predecessor_block->IsDeferred()) {
+        predecessor_hint_preference += kNotDeferredBlockPreference;

[Mircea Trofin, 2016/07/04 16:32:15]

Nit: replace with bitwise or, I think that'd make it more clear. 

[jbramley, 2016/07/04 16:58:54]

I'd half planned to support an arithmetic score, though it didn't turn out that
way in the end. (It's co-incidental that the values are powers of two.)
Nonetheless, I thought that addition would be more flexible for future
modifications.

[Mircea Trofin, 2016/07/04 21:20:35]

Oh - the fact that they are powers of 2 threw me off. Mind adding a comment
saying "they just happen they are" or something like that, to avoid confusion
later? Thanks!

+      }
+
+      // - Prefer hints from allocated (or explicit) operands.
+      //
+      // Already-allocated or explicit operands are typically assigned using
+      // the parallel moves on the last instruction. For example:
+      //
+      //      gap (v101 = [x0|R|w32]) (v100 = v101)
+      //      ArchJmp
+      //    ...
+      //    phi: v100 = v101 v102
+      //
+      // We have already found the END move, so look for a matching START move
+      // from an allocated (or explicit) operand.

[Mircea Trofin, 2016/07/04 16:32:15]

This happens if the previous instruction (the one before predecessor_instr)
happens to output to a fixed 
register, which then participates in the phi. Is this a common pattern? Or could
you comment why not walk 
up the instruction sequence, finding the def?

On that, I think you could avoid the search for the def through the moves by
fetching the live range and picking
its first use position.

[jbramley, 2016/07/04 16:58:54]

Reasonably common. Without this, the empty-block check causes regressions in the
cases you described.
I actually considered it, but I thought it would be too expensive to be
worthwhile in practice. (I examined a lot of benchmarks and didn't see it occur,
yet we'd do the search for every case that would otherwise not hit.) I think
that the negative case is the common case, and needs to be the fast.
If that is likely to be fast in the negative case, it would probably be wise. I
didn't realise it was feasible here. Otherwise, I'll add a comment to explain
why we don't look beyond the last instruction.

[Mircea Trofin, 2016/07/04 21:20:35]

It may be worth investigating. The compile benchmark shows a 12-13% regression. 
What I'm talking about is O(1):

TopLevelLiveRange* top =data()->live_ranges()[whatever the vreg]
top->first_pos() (etc, etc)

+      auto moves = predecessor_instr->GetParallelMove(Instruction::START);
+      if (moves != nullptr) {
+        for (MoveOperands* move : *moves) {
+          InstructionOperand& to = move->destination();
+          if (predecessor_hint->Equals(to)) {
+            if (move->source().IsAllocated() || move->source().IsExplicit()) {
+              predecessor_hint_preference += kMoveIsAllocatedPreference;
+            }
+            break;
+          }
+        }
+      }
+
+      // - Prefer hints from empty blocks.
+      if (predecessor_block->last_instruction_index() ==
+          predecessor_block->first_instruction_index()) {
+        predecessor_hint_preference += kBlockIsEmptyPreference;
+      }
+
+      if ((hint == nullptr) ||
+          (predecessor_hint_preference > hint_preference)) {
+        // Take the hint from this predecessor.
+        hint = predecessor_hint;
+        hint_preference = predecessor_hint_preference;
       }
     }
-    DCHECK(hint != nullptr);
+    DCHECK_NOT_NULL(hint);
+
     LifetimePosition block_start = LifetimePosition::GapFromInstructionIndex(
         block->first_instruction_index());
     UsePosition* use_pos = Define(block_start, &phi->output(), hint,