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
8 namespace v8 {
9 namespace internal {
10 namespace compiler {
11
12 #define TRACE(...) \
13 do { \
14 if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \
15 } while (false)
16
17 struct JumpThreadingState {
18 bool forwarded;
19 ZoneVector<RpoNumber>& result;
20 ZoneStack<RpoNumber>& stack;
21
Clearv8::internal::compiler::JumpThreadingState22 void Clear(size_t count) { result.assign(count, unvisited()); }
PushIfUnvisitedv8::internal::compiler::JumpThreadingState23 void PushIfUnvisited(RpoNumber num) {
24 if (result[num.ToInt()] == unvisited()) {
25 stack.push(num);
26 result[num.ToInt()] = onstack();
27 }
28 }
Forwardv8::internal::compiler::JumpThreadingState29 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 }
unvisitedv8::internal::compiler::JumpThreadingState52 RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
onstackv8::internal::compiler::JumpThreadingState53 RpoNumber onstack() { return RpoNumber::FromInt(-2); }
54 };
55
ComputeForwarding(Zone * local_zone,ZoneVector<RpoNumber> & result,InstructionSequence * code,bool frame_at_start)56 bool 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
ApplyForwarding(ZoneVector<RpoNumber> & result,InstructionSequence * code)142 void 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