[turbofan] Implement jump threading after register allocation.

src/compiler/jump-threading.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/compiler/jump-threading.h"
+#include "src/compiler/code-generator-impl.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+typedef BasicBlock::RpoNumber RpoNumber;
+
+#define TRACE(x) \
+  if (FLAG_trace_turbo_jt) PrintF x
+
+struct JumpThreadingState {
+  bool forwarded;
+  ZoneVector<RpoNumber>& result;
+  ZoneStack<RpoNumber>& stack;
+
+  void Clear(size_t count) { result.assign(count, unvisited()); }
+  void PushIfUnvisited(RpoNumber num) {
+    if (result[num.ToInt()] == unvisited()) {
+      stack.push(num);
+      result[num.ToInt()] = onstack();
+    }
+  }
+  void Forward(RpoNumber to) {
+    RpoNumber from = stack.top();
+    RpoNumber to_to = result[to.ToInt()];
+    bool pop = true;
+    if (to == from) {
+      TRACE(("  xx %d\n", from.ToInt()));
+      result[from.ToInt()] = from;
+    } else if (to_to == unvisited()) {
+      TRACE(("  fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt()));
+      stack.push(to);
+      result[to.ToInt()] = onstack();
+      pop = false;  // recurse.
+    } else if (to_to == onstack()) {
+      TRACE(("  fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt()));
+      result[from.ToInt()] = to;  // break the cycle.
+      forwarded = true;
+    } else {
+      TRACE(("  fw %d -> %d (forward)\n", from.ToInt(), to.ToInt()));
+      result[from.ToInt()] = to_to;  // forward the block.
+      forwarded = true;
+    }
+    if (pop) stack.pop();
+  }
+  RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
+  RpoNumber onstack() { return RpoNumber::FromInt(-2); }
+};
+
+
+bool JumpThreading::ComputeForwarding(Zone* local_zone,
+                                      ZoneVector<RpoNumber>& result,
+                                      InstructionSequence* code) {
+  ZoneStack<RpoNumber> stack(local_zone);
+  JumpThreadingState state = {false, result, stack};
+  state.Clear(code->InstructionBlockCount());
+
+  // Iterate over the blocks forward, pushing the blocks onto the stack.
+  for (auto const block : code->instruction_blocks()) {
+    RpoNumber current = block->rpo_number();
+    state.PushIfUnvisited(current);
+
+    // Process the stack, which implements DFS through empty blocks.
+    while (!state.stack.empty()) {
+      InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
+      // Process the instructions in a block up to a non-empty instruction.
+      TRACE(("jt [%d] B%d RPO%d\n", static_cast<int>(stack.size()),
+             block->id().ToInt(), block->rpo_number().ToInt()));
+      bool fallthru = true;
+      RpoNumber fw = block->rpo_number();
+      for (int i = block->code_start(); i < block->code_end(); ++i) {
+        Instruction* instr = code->InstructionAt(i);
+        if (instr->IsGapMoves() && GapInstruction::cast(instr)->IsRedundant()) {
+          // skip redundant gap moves.
+          TRACE(("  nop gap\n"));
+          continue;
+        } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
+          // can't skip instructions with flags continuations.
+          TRACE(("  flags\n"));
+          fallthru = false;
+        } else if (instr->IsNop()) {
+          // skip nops.
+          TRACE(("  nop\n"));
+          continue;
+        } else if (instr->arch_opcode() == kArchJmp) {
+          // try to forward the jump instruction.
+          TRACE(("  jmp\n"));
+          fw = code->InputRpo(instr, 0);
+          fallthru = false;
+        } else {
+          // can't skip other instructions.

[dcarney, 2014/11/25 20:32:36]

you forgot to skip sourceposition instructions

[titzer, 2014/11/26 09:37:23]

Done.

+          TRACE(("  other\n"));
+          fallthru = false;
+        }
+        break;
+      }
+      if (fallthru) {
+        int next = 1 + block->rpo_number().ToInt();
+        if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
+      }
+      state.Forward(fw);
+    }
+  }
+
+#if DEBUG
+  for (RpoNumber num : result) DCHECK(num.IsValid());
+#endif
+
+  for (int i = 0; i < static_cast<int>(result.size()); i++) {
+    TRACE(("RPO%d B%d ", i,
+           code->InstructionBlockAt(RpoNumber::FromInt(i))->id().ToInt()));
+    int to = result[i].ToInt();
+    if (i != to) {
+      TRACE(("-> B%d\n",
+             code->InstructionBlockAt(RpoNumber::FromInt(to))->id().ToInt()));
+    } else {
+      TRACE(("\n"));
+    }
+  }
+
+  return state.forwarded;
+}
+
+
+static void ForwardInputRpo(ZoneVector<RpoNumber>& result,
+                            InstructionSequence* code, Instruction* instr,
+                            size_t index) {
+  RpoNumber to = code->InputRpo(instr, index);
+  RpoNumber new_to = result[to.ToInt()];
+  if (!(new_to == to)) {
+    TRACE(("[B%d -> B%d]", code->InstructionBlockAt(to)->id().ToInt(),
+           code->InstructionBlockAt(new_to)->id().ToInt()));
+    int rpo = code->AddImmediate(Constant(new_to.ToInt()));
+    instr->SetInputAt(index, ImmediateOperand::Create(rpo, code->zone()));
+  }
+}
+
+void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
+                                    InstructionSequence* code) {
+  if (!FLAG_turbo_jt) return;
+
+  Zone local_zone(code->zone()->isolate());
+  ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone);
+
+  bool prev_fallthru = true;
+  for (auto const block : code->instruction_blocks()) {
+    // Skip a block if the previous doesn't fall through and we should forward.
+    int block_num = block->rpo_number().ToInt();
+    skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
+
+    bool fallthru = true;
+    for (int i = block->code_start(); i < block->code_end(); ++i) {
+      Instruction* instr = code->InstructionAt(i);
+      if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) {
+        // forward the targets of a branch.
+        TRACE(("jt-fw br @%d ", i));
+        ForwardInputRpo(result, code, instr, instr->InputCount() - 2);
+        ForwardInputRpo(result, code, instr, instr->InputCount() - 1);
+        TRACE(("\n"));
+        fallthru = false;
+      } else if (instr->arch_opcode() == kArchJmp) {
+        if (skip[block_num]) {
+          // Overwrite a redundant jump with a nop if the previous block
+          // did not fall through to this one.
+          TRACE(("jt-fw nop @%d\n", i));
+          instr->OverwriteWithNop();
+        } else {
+          // forward the target of a jump.
+          TRACE(("jt-fw jmp @%d ", i));
+          ForwardInputRpo(result, code, instr, 0);
+          TRACE(("\n"));
+        }
+        fallthru = false;
+      }
+    }
+    prev_fallthru = fallthru;
+  }

[titzer, 2014/11/26 09:37:23]

Note that I update all the immediates in the instruction sequence now, so I
don't have to hunt through the operands of the instructions like a monkey.

+  // Recompute assembly order numbers.
+  int ao = 0;
+  for (auto const block : code->instruction_blocks()) {
+    if (!block->IsDeferred()) {
+      block->set_ao_number(RpoNumber::FromInt(ao));
+      if (!skip[block->rpo_number().ToInt()]) ao++;
+    }
+  }
+  for (auto const block : code->instruction_blocks()) {
+    if (block->IsDeferred()) {
+      block->set_ao_number(RpoNumber::FromInt(ao));
+      if (!skip[block->rpo_number().ToInt()]) ao++;
+    }
+  }
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8