[turbofan] Fix phi-hinting problem with deferred 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 2166 matching lines @@
 }
 
 
 void LiveRangeBuilder::ProcessPhis(const InstructionBlock* block,
                                    BitVector* live) {
   for (PhiInstruction* phi : block->phis()) {
     // The live range interval already ends at the first instruction of the
     // block.
     int phi_vreg = phi->virtual_register();
     live->Remove(phi_vreg);
-    InstructionOperand* hint = nullptr;
+    // Select the hint from the first predecessor block that preceeds this block
+    // in the rpo ordering. Prefer non-deferred blocks.

[Mircea Trofin, 2016/06/01 15:02:58]

Could you add a comment as to why the rpo ordering matters?

[danno, 2016/06/02 01:29:37]

Done.

[Mircea Trofin, 2016/06/02 01:42:43]

(nit, sorry) what's the motivation, though? Why does the hint need to be in that
order?

[danno, 2016/06/02 13:17:06]

Whoops, lost the edit. Updated the comment in a later patch set with the
explanation.

+    const Instruction* instr = nullptr;
     const InstructionBlock::Predecessors& predecessors = block->predecessors();
-    const InstructionBlock* predecessor_block =
-        code()->InstructionBlockAt(predecessors[0]);
-    const Instruction* instr = GetLastInstruction(code(), predecessor_block);
-    if (predecessor_block->IsDeferred()) {
-      // "Prefer the hint from the first non-deferred predecessor, if any.
-      for (size_t i = 1; i < predecessors.size(); ++i) {
-        predecessor_block = code()->InstructionBlockAt(predecessors[i]);
-        if (!predecessor_block->IsDeferred()) {
-          instr = GetLastInstruction(code(), predecessor_block);
-          break;
-        }
+    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;

[Mircea Trofin, 2016/06/01 15:02:58]

Before, if the phi block was deferred, and all its predecessors were also
deferred, there would still be a hint. That may matter for code size. Perhaps
add to the condition here a "block->IsDeferred() || " ?

[danno, 2016/06/02 01:29:37]

Hmmm. Sorry, perhaps I'm missing something here, but I think the case you
mention remains unchanged. There is always a hint. If all the predecessor blocks
are deferred, then now you get a hint from the last deferred block that is a rpo
predecessor, not the first one like in the old version, but you still always get
a hint.

[Mircea Trofin, 2016/06/02 01:39:51]

Oh! You are right, sorry. I now see instr is always not null. In fact, the
DCHECK just below exposes that invariant :)

Could you kick off a perf try, so we see the impact of this change (the hint
being last rather than first in deferred subgraphs, that is). I know we don't
expect any, but code size => various alignments, who knows.

       }
     }
     DCHECK_NOT_NULL(instr);
 
+    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;
       }
     }
     DCHECK(hint != nullptr);
     LifetimePosition block_start = LifetimePosition::GapFromInstructionIndex(
@@ skipping 1443 matching lines @@
         }
       }
     }
   }
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8