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 8namespace v8 { 9namespace internal { 10namespace compiler { 11 12#define TRACE(...) \ 13 do { \ 14 if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \ 15 } while (false) 16 17struct 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) { 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 } 52 RpoNumber unvisited() { return RpoNumber::FromInt(-1); } 53 RpoNumber onstack() { return RpoNumber::FromInt(-2); } 54}; 55 56bool 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 142void 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