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