1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/compiler/jump-threading.h"
6#include "src/compiler/code-generator-impl.h"
7
8namespace v8 {
9namespace internal {
10namespace compiler {
11
12#define TRACE(...)                                \
13  do {                                            \
14    if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \
15  } while (false)
16
17struct JumpThreadingState {
18  bool forwarded;
19  ZoneVector<RpoNumber>& result;
20  ZoneStack<RpoNumber>& stack;
21
22  void Clear(size_t count) { result.assign(count, unvisited()); }
23  void PushIfUnvisited(RpoNumber num) {
24    if (result[num.ToInt()] == unvisited()) {
25      stack.push(num);
26      result[num.ToInt()] = onstack();
27    }
28  }
29  void Forward(RpoNumber to) {
30    RpoNumber from = stack.top();
31    RpoNumber to_to = result[to.ToInt()];
32    bool pop = true;
33    if (to == from) {
34      TRACE("  xx %d\n", from.ToInt());
35      result[from.ToInt()] = from;
36    } else if (to_to == unvisited()) {
37      TRACE("  fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt());
38      stack.push(to);
39      result[to.ToInt()] = onstack();
40      pop = false;  // recurse.
41    } else if (to_to == onstack()) {
42      TRACE("  fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt());
43      result[from.ToInt()] = to;  // break the cycle.
44      forwarded = true;
45    } else {
46      TRACE("  fw %d -> %d (forward)\n", from.ToInt(), to.ToInt());
47      result[from.ToInt()] = to_to;  // forward the block.
48      forwarded = true;
49    }
50    if (pop) stack.pop();
51  }
52  RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
53  RpoNumber onstack() { return RpoNumber::FromInt(-2); }
54};
55
56bool JumpThreading::ComputeForwarding(Zone* local_zone,
57                                      ZoneVector<RpoNumber>& result,
58                                      InstructionSequence* code,
59                                      bool frame_at_start) {
60  ZoneStack<RpoNumber> stack(local_zone);
61  JumpThreadingState state = {false, result, stack};
62  state.Clear(code->InstructionBlockCount());
63
64  // Iterate over the blocks forward, pushing the blocks onto the stack.
65  for (auto const block : code->instruction_blocks()) {
66    RpoNumber current = block->rpo_number();
67    state.PushIfUnvisited(current);
68
69    // Process the stack, which implements DFS through empty blocks.
70    while (!state.stack.empty()) {
71      InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
72      // Process the instructions in a block up to a non-empty instruction.
73      TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()),
74            block->rpo_number().ToInt());
75      bool fallthru = true;
76      RpoNumber fw = block->rpo_number();
77      for (int i = block->code_start(); i < block->code_end(); ++i) {
78        Instruction* instr = code->InstructionAt(i);
79        if (!instr->AreMovesRedundant()) {
80          // can't skip instructions with non redundant moves.
81          TRACE("  parallel move\n");
82          fallthru = false;
83        } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
84          // can't skip instructions with flags continuations.
85          TRACE("  flags\n");
86          fallthru = false;
87        } else if (instr->IsNop()) {
88          // skip nops.
89          TRACE("  nop\n");
90          continue;
91        } else if (instr->arch_opcode() == kArchJmp) {
92          // try to forward the jump instruction.
93          TRACE("  jmp\n");
94          // if this block deconstructs the frame, we can't forward it.
95          // TODO(mtrofin): we can still forward if we end up building
96          // the frame at start. So we should move the decision of whether
97          // to build a frame or not in the register allocator, and trickle it
98          // here and to the code generator.
99          if (frame_at_start ||
100              !(block->must_deconstruct_frame() ||
101                block->must_construct_frame())) {
102            fw = code->InputRpo(instr, 0);
103          }
104          fallthru = false;
105        } else {
106          // can't skip other instructions.
107          TRACE("  other\n");
108          fallthru = false;
109        }
110        break;
111      }
112      if (fallthru) {
113        int next = 1 + block->rpo_number().ToInt();
114        if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
115      }
116      state.Forward(fw);
117    }
118  }
119
120#ifdef DEBUG
121  for (RpoNumber num : result) {
122    CHECK(num.IsValid());
123  }
124#endif
125
126  if (FLAG_trace_turbo_jt) {
127    for (int i = 0; i < static_cast<int>(result.size()); i++) {
128      TRACE("B%d ", i);
129      int to = result[i].ToInt();
130      if (i != to) {
131        TRACE("-> B%d\n", to);
132      } else {
133        TRACE("\n");
134      }
135    }
136  }
137
138  return state.forwarded;
139}
140
141
142void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
143                                    InstructionSequence* code) {
144  if (!FLAG_turbo_jt) return;
145
146  Zone local_zone(code->isolate()->allocator(), ZONE_NAME);
147  ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone);
148
149  // Skip empty blocks when the previous block doesn't fall through.
150  bool prev_fallthru = true;
151  for (auto const block : code->instruction_blocks()) {
152    int block_num = block->rpo_number().ToInt();
153    skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
154
155    bool fallthru = true;
156    for (int i = block->code_start(); i < block->code_end(); ++i) {
157      Instruction* instr = code->InstructionAt(i);
158      if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) {
159        fallthru = false;  // branches don't fall through to the next block.
160      } else if (instr->arch_opcode() == kArchJmp) {
161        if (skip[block_num]) {
162          // Overwrite a redundant jump with a nop.
163          TRACE("jt-fw nop @%d\n", i);
164          instr->OverwriteWithNop();
165        }
166        fallthru = false;  // jumps don't fall through to the next block.
167      }
168    }
169    prev_fallthru = fallthru;
170  }
171
172  // Patch RPO immediates.
173  InstructionSequence::Immediates& immediates = code->immediates();
174  for (size_t i = 0; i < immediates.size(); i++) {
175    Constant constant = immediates[i];
176    if (constant.type() == Constant::kRpoNumber) {
177      RpoNumber rpo = constant.ToRpoNumber();
178      RpoNumber fw = result[rpo.ToInt()];
179      if (!(fw == rpo)) immediates[i] = Constant(fw);
180    }
181  }
182
183  // Recompute assembly order numbers.
184  int ao = 0;
185  for (auto const block : code->instruction_blocks()) {
186    if (!block->IsDeferred()) {
187      block->set_ao_number(RpoNumber::FromInt(ao));
188      if (!skip[block->rpo_number().ToInt()]) ao++;
189    }
190  }
191  for (auto const block : code->instruction_blocks()) {
192    if (block->IsDeferred()) {
193      block->set_ao_number(RpoNumber::FromInt(ao));
194      if (!skip[block->rpo_number().ToInt()]) ao++;
195    }
196  }
197}
198
199}  // namespace compiler
200}  // namespace internal
201}  // namespace v8
202