Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 12 | #define TRACE(...) \ |
| 13 | do { \ |
| 14 | if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \ |
| 15 | } while (false) |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 16 | |
| 17 | struct 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) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 34 | TRACE(" xx %d\n", from.ToInt()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 35 | result[from.ToInt()] = from; |
| 36 | } else if (to_to == unvisited()) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 37 | TRACE(" fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 38 | stack.push(to); |
| 39 | result[to.ToInt()] = onstack(); |
| 40 | pop = false; // recurse. |
| 41 | } else if (to_to == onstack()) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 42 | TRACE(" fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 43 | result[from.ToInt()] = to; // break the cycle. |
| 44 | forwarded = true; |
| 45 | } else { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 46 | TRACE(" fw %d -> %d (forward)\n", from.ToInt(), to.ToInt()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 56 | bool JumpThreading::ComputeForwarding(Zone* local_zone, |
| 57 | ZoneVector<RpoNumber>& result, |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 58 | InstructionSequence* code, |
| 59 | bool frame_at_start) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 73 | TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()), |
| 74 | block->rpo_number().ToInt()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 79 | if (!instr->AreMovesRedundant()) { |
| 80 | // can't skip instructions with non redundant moves. |
| 81 | TRACE(" parallel move\n"); |
| 82 | fallthru = false; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 83 | } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) { |
| 84 | // can't skip instructions with flags continuations. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 85 | TRACE(" flags\n"); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 86 | fallthru = false; |
| 87 | } else if (instr->IsNop()) { |
| 88 | // skip nops. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 89 | TRACE(" nop\n"); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 90 | continue; |
| 91 | } else if (instr->arch_opcode() == kArchJmp) { |
| 92 | // try to forward the jump instruction. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 93 | TRACE(" jmp\n"); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 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. |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 99 | if (frame_at_start || |
| 100 | !(block->must_deconstruct_frame() || |
| 101 | block->must_construct_frame())) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 102 | fw = code->InputRpo(instr, 0); |
| 103 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 104 | fallthru = false; |
| 105 | } else { |
| 106 | // can't skip other instructions. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 107 | TRACE(" other\n"); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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++) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 128 | TRACE("B%d ", i); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 129 | int to = result[i].ToInt(); |
| 130 | if (i != to) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 131 | TRACE("-> B%d\n", to); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 132 | } else { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 133 | TRACE("\n"); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 134 | } |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | return state.forwarded; |
| 139 | } |
| 140 | |
| 141 | |
| 142 | void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result, |
| 143 | InstructionSequence* code) { |
| 144 | if (!FLAG_turbo_jt) return; |
| 145 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 146 | Zone local_zone(code->isolate()->allocator()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 163 | TRACE("jt-fw nop @%d\n", i); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 |