jump-threading.cc 6.78 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11
// 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 {

12 13 14 15
#define TRACE(...)                                \
  do {                                            \
    if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \
  } while (false)
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

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) {
34
      TRACE("  xx %d\n", from.ToInt());
35 36
      result[from.ToInt()] = from;
    } else if (to_to == unvisited()) {
37
      TRACE("  fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt());
38 39 40 41
      stack.push(to);
      result[to.ToInt()] = onstack();
      pop = false;  // recurse.
    } else if (to_to == onstack()) {
42
      TRACE("  fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt());
43 44 45
      result[from.ToInt()] = to;  // break the cycle.
      forwarded = true;
    } else {
46
      TRACE("  fw %d -> %d (forward)\n", from.ToInt(), to.ToInt());
47 48 49 50 51 52 53 54 55 56 57
      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,
58 59
                                      InstructionSequence* code,
                                      bool frame_at_start) {
60 61 62 63 64 65 66 67 68 69 70 71 72
  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.
73 74
      TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()),
            block->rpo_number().ToInt());
75 76 77 78
      bool fallthru = true;
      RpoNumber fw = block->rpo_number();
      for (int i = block->code_start(); i < block->code_end(); ++i) {
        Instruction* instr = code->InstructionAt(i);
79 80 81 82
        if (!instr->AreMovesRedundant()) {
          // can't skip instructions with non redundant moves.
          TRACE("  parallel move\n");
          fallthru = false;
83 84
        } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
          // can't skip instructions with flags continuations.
85
          TRACE("  flags\n");
86 87 88
          fallthru = false;
        } else if (instr->IsNop()) {
          // skip nops.
89
          TRACE("  nop\n");
90 91 92
          continue;
        } else if (instr->arch_opcode() == kArchJmp) {
          // try to forward the jump instruction.
93
          TRACE("  jmp\n");
94 95 96 97 98
          // if this block deconstructs the frame, we can't forward it.
          // TODO(mtrofin): we can still forward if we end up building
          // the frame at start. So we should move the decision of whether
          // to build a frame or not in the register allocator, and trickle it
          // here and to the code generator.
99 100 101
          if (frame_at_start ||
              !(block->must_deconstruct_frame() ||
                block->must_construct_frame())) {
102 103
            fw = code->InputRpo(instr, 0);
          }
104 105 106
          fallthru = false;
        } else {
          // can't skip other instructions.
107
          TRACE("  other\n");
108 109 110 111 112 113 114 115 116 117 118 119
          fallthru = false;
        }
        break;
      }
      if (fallthru) {
        int next = 1 + block->rpo_number().ToInt();
        if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
      }
      state.Forward(fw);
    }
  }

Ben L. Titzer's avatar
Ben L. Titzer committed
120 121 122 123
#ifdef DEBUG
  for (RpoNumber num : result) {
    CHECK(num.IsValid());
  }
124 125
#endif

Ben L. Titzer's avatar
Ben L. Titzer committed
126 127
  if (FLAG_trace_turbo_jt) {
    for (int i = 0; i < static_cast<int>(result.size()); i++) {
128
      TRACE("B%d ", i);
Ben L. Titzer's avatar
Ben L. Titzer committed
129 130
      int to = result[i].ToInt();
      if (i != to) {
131
        TRACE("-> B%d\n", to);
Ben L. Titzer's avatar
Ben L. Titzer committed
132
      } else {
133
        TRACE("\n");
Ben L. Titzer's avatar
Ben L. Titzer committed
134
      }
135 136 137 138 139 140 141 142 143 144 145
    }
  }

  return state.forwarded;
}


void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
                                    InstructionSequence* code) {
  if (!FLAG_turbo_jt) return;

146
  Zone local_zone(code->isolate()->allocator(), ZONE_NAME);
147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
  ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone);

  // Skip empty blocks when the previous block doesn't fall through.
  bool prev_fallthru = true;
  for (auto const block : code->instruction_blocks()) {
    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) {
        fallthru = false;  // branches don't fall through to the next block.
      } else if (instr->arch_opcode() == kArchJmp) {
        if (skip[block_num]) {
          // Overwrite a redundant jump with a nop.
163
          TRACE("jt-fw nop @%d\n", i);
164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201
          instr->OverwriteWithNop();
        }
        fallthru = false;  // jumps don't fall through to the next block.
      }
    }
    prev_fallthru = fallthru;
  }

  // Patch RPO immediates.
  InstructionSequence::Immediates& immediates = code->immediates();
  for (size_t i = 0; i < immediates.size(); i++) {
    Constant constant = immediates[i];
    if (constant.type() == Constant::kRpoNumber) {
      RpoNumber rpo = constant.ToRpoNumber();
      RpoNumber fw = result[rpo.ToInt()];
      if (!(fw == rpo)) immediates[i] = Constant(fw);
    }
  }

  // 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