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.
5 #include "src/compiler/jump-threading.h"
6 #include "src/compiler/code-generator-impl.h"
14 if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \
17 struct JumpThreadingState {
19 ZoneVector<RpoNumber>& result;
20 ZoneStack<RpoNumber>& stack;
22 void Clear(size_t count) { result.assign(count, unvisited()); }
23 void PushIfUnvisited(RpoNumber num) {
24 if (result[num.ToInt()] == unvisited()) {
26 result[num.ToInt()] = onstack();
29 void Forward(RpoNumber to) {
30 RpoNumber from = stack.top();
31 RpoNumber to_to = result[to.ToInt()];
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());
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.
46 TRACE(" fw %d -> %d (forward)\n", from.ToInt(), to.ToInt());
47 result[from.ToInt()] = to_to; // forward the block.
52 RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
53 RpoNumber onstack() { return RpoNumber::FromInt(-2); }
57 bool JumpThreading::ComputeForwarding(Zone* local_zone,
58 ZoneVector<RpoNumber>& result,
59 InstructionSequence* code) {
60 ZoneStack<RpoNumber> stack(local_zone);
61 JumpThreadingState state = {false, result, stack};
62 state.Clear(code->InstructionBlockCount());
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);
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());
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->IsGapMoves() && GapInstruction::cast(instr)->IsRedundant()) {
80 // skip redundant gap moves.
83 } else if (instr->IsSourcePosition()) {
84 // skip source positions.
87 } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
88 // can't skip instructions with flags continuations.
91 } else if (instr->IsNop()) {
95 } else if (instr->arch_opcode() == kArchJmp) {
96 // try to forward the jump instruction.
98 fw = code->InputRpo(instr, 0);
101 // can't skip other instructions.
108 int next = 1 + block->rpo_number().ToInt();
109 if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
116 for (RpoNumber num : result) {
117 CHECK(num.IsValid());
121 if (FLAG_trace_turbo_jt) {
122 for (int i = 0; i < static_cast<int>(result.size()); i++) {
124 int to = result[i].ToInt();
126 TRACE("-> B%d\n", to);
133 return state.forwarded;
137 void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
138 InstructionSequence* code) {
139 if (!FLAG_turbo_jt) return;
142 ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone);
144 // Skip empty blocks when the previous block doesn't fall through.
145 bool prev_fallthru = true;
146 for (auto const block : code->instruction_blocks()) {
147 int block_num = block->rpo_number().ToInt();
148 skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
150 bool fallthru = true;
151 for (int i = block->code_start(); i < block->code_end(); ++i) {
152 Instruction* instr = code->InstructionAt(i);
153 if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) {
154 fallthru = false; // branches don't fall through to the next block.
155 } else if (instr->arch_opcode() == kArchJmp) {
156 if (skip[block_num]) {
157 // Overwrite a redundant jump with a nop.
158 TRACE("jt-fw nop @%d\n", i);
159 instr->OverwriteWithNop();
161 fallthru = false; // jumps don't fall through to the next block.
164 prev_fallthru = fallthru;
167 // Patch RPO immediates.
168 InstructionSequence::Immediates& immediates = code->immediates();
169 for (size_t i = 0; i < immediates.size(); i++) {
170 Constant constant = immediates[i];
171 if (constant.type() == Constant::kRpoNumber) {
172 RpoNumber rpo = constant.ToRpoNumber();
173 RpoNumber fw = result[rpo.ToInt()];
174 if (!(fw == rpo)) immediates[i] = Constant(fw);
178 // Recompute assembly order numbers.
180 for (auto const block : code->instruction_blocks()) {
181 if (!block->IsDeferred()) {
182 block->set_ao_number(RpoNumber::FromInt(ao));
183 if (!skip[block->rpo_number().ToInt()]) ao++;
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++;
194 } // namespace compiler
195 } // namespace internal