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