OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/jump-threading.h" | 5 #include "src/compiler/jump-threading.h" |
6 #include "src/compiler/code-generator-impl.h" | 6 #include "src/compiler/code-generator-impl.h" |
7 | 7 |
8 namespace v8 { | 8 namespace v8 { |
9 namespace internal { | 9 namespace internal { |
10 namespace compiler { | 10 namespace compiler { |
11 | 11 |
12 #define TRACE(x) \ | 12 #define TRACE(...) \ |
13 if (FLAG_trace_turbo_jt) PrintF x | 13 do { \ |
| 14 if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \ |
| 15 } while (false) |
14 | 16 |
15 struct JumpThreadingState { | 17 struct JumpThreadingState { |
16 bool forwarded; | 18 bool forwarded; |
17 ZoneVector<RpoNumber>& result; | 19 ZoneVector<RpoNumber>& result; |
18 ZoneStack<RpoNumber>& stack; | 20 ZoneStack<RpoNumber>& stack; |
19 | 21 |
20 void Clear(size_t count) { result.assign(count, unvisited()); } | 22 void Clear(size_t count) { result.assign(count, unvisited()); } |
21 void PushIfUnvisited(RpoNumber num) { | 23 void PushIfUnvisited(RpoNumber num) { |
22 if (result[num.ToInt()] == unvisited()) { | 24 if (result[num.ToInt()] == unvisited()) { |
23 stack.push(num); | 25 stack.push(num); |
24 result[num.ToInt()] = onstack(); | 26 result[num.ToInt()] = onstack(); |
25 } | 27 } |
26 } | 28 } |
27 void Forward(RpoNumber to) { | 29 void Forward(RpoNumber to) { |
28 RpoNumber from = stack.top(); | 30 RpoNumber from = stack.top(); |
29 RpoNumber to_to = result[to.ToInt()]; | 31 RpoNumber to_to = result[to.ToInt()]; |
30 bool pop = true; | 32 bool pop = true; |
31 if (to == from) { | 33 if (to == from) { |
32 TRACE((" xx %d\n", from.ToInt())); | 34 TRACE(" xx %d\n", from.ToInt()); |
33 result[from.ToInt()] = from; | 35 result[from.ToInt()] = from; |
34 } else if (to_to == unvisited()) { | 36 } else if (to_to == unvisited()) { |
35 TRACE((" fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt())); | 37 TRACE(" fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt()); |
36 stack.push(to); | 38 stack.push(to); |
37 result[to.ToInt()] = onstack(); | 39 result[to.ToInt()] = onstack(); |
38 pop = false; // recurse. | 40 pop = false; // recurse. |
39 } else if (to_to == onstack()) { | 41 } else if (to_to == onstack()) { |
40 TRACE((" fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt())); | 42 TRACE(" fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt()); |
41 result[from.ToInt()] = to; // break the cycle. | 43 result[from.ToInt()] = to; // break the cycle. |
42 forwarded = true; | 44 forwarded = true; |
43 } else { | 45 } else { |
44 TRACE((" fw %d -> %d (forward)\n", from.ToInt(), to.ToInt())); | 46 TRACE(" fw %d -> %d (forward)\n", from.ToInt(), to.ToInt()); |
45 result[from.ToInt()] = to_to; // forward the block. | 47 result[from.ToInt()] = to_to; // forward the block. |
46 forwarded = true; | 48 forwarded = true; |
47 } | 49 } |
48 if (pop) stack.pop(); | 50 if (pop) stack.pop(); |
49 } | 51 } |
50 RpoNumber unvisited() { return RpoNumber::FromInt(-1); } | 52 RpoNumber unvisited() { return RpoNumber::FromInt(-1); } |
51 RpoNumber onstack() { return RpoNumber::FromInt(-2); } | 53 RpoNumber onstack() { return RpoNumber::FromInt(-2); } |
52 }; | 54 }; |
53 | 55 |
54 | 56 |
55 bool JumpThreading::ComputeForwarding(Zone* local_zone, | 57 bool JumpThreading::ComputeForwarding(Zone* local_zone, |
56 ZoneVector<RpoNumber>& result, | 58 ZoneVector<RpoNumber>& result, |
57 InstructionSequence* code) { | 59 InstructionSequence* code) { |
58 ZoneStack<RpoNumber> stack(local_zone); | 60 ZoneStack<RpoNumber> stack(local_zone); |
59 JumpThreadingState state = {false, result, stack}; | 61 JumpThreadingState state = {false, result, stack}; |
60 state.Clear(code->InstructionBlockCount()); | 62 state.Clear(code->InstructionBlockCount()); |
61 | 63 |
62 // Iterate over the blocks forward, pushing the blocks onto the stack. | 64 // Iterate over the blocks forward, pushing the blocks onto the stack. |
63 for (auto const block : code->instruction_blocks()) { | 65 for (auto const block : code->instruction_blocks()) { |
64 RpoNumber current = block->rpo_number(); | 66 RpoNumber current = block->rpo_number(); |
65 state.PushIfUnvisited(current); | 67 state.PushIfUnvisited(current); |
66 | 68 |
67 // Process the stack, which implements DFS through empty blocks. | 69 // Process the stack, which implements DFS through empty blocks. |
68 while (!state.stack.empty()) { | 70 while (!state.stack.empty()) { |
69 InstructionBlock* block = code->InstructionBlockAt(state.stack.top()); | 71 InstructionBlock* block = code->InstructionBlockAt(state.stack.top()); |
70 // Process the instructions in a block up to a non-empty instruction. | 72 // Process the instructions in a block up to a non-empty instruction. |
71 TRACE(("jt [%d] B%d\n", static_cast<int>(stack.size()), | 73 TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()), |
72 block->rpo_number().ToInt())); | 74 block->rpo_number().ToInt()); |
73 bool fallthru = true; | 75 bool fallthru = true; |
74 RpoNumber fw = block->rpo_number(); | 76 RpoNumber fw = block->rpo_number(); |
75 for (int i = block->code_start(); i < block->code_end(); ++i) { | 77 for (int i = block->code_start(); i < block->code_end(); ++i) { |
76 Instruction* instr = code->InstructionAt(i); | 78 Instruction* instr = code->InstructionAt(i); |
77 if (instr->IsGapMoves() && GapInstruction::cast(instr)->IsRedundant()) { | 79 if (instr->IsGapMoves() && GapInstruction::cast(instr)->IsRedundant()) { |
78 // skip redundant gap moves. | 80 // skip redundant gap moves. |
79 TRACE((" nop gap\n")); | 81 TRACE(" nop gap\n"); |
80 continue; | 82 continue; |
81 } else if (instr->IsSourcePosition()) { | 83 } else if (instr->IsSourcePosition()) { |
82 // skip source positions. | 84 // skip source positions. |
83 TRACE((" src pos\n")); | 85 TRACE(" src pos\n"); |
84 continue; | 86 continue; |
85 } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) { | 87 } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) { |
86 // can't skip instructions with flags continuations. | 88 // can't skip instructions with flags continuations. |
87 TRACE((" flags\n")); | 89 TRACE(" flags\n"); |
88 fallthru = false; | 90 fallthru = false; |
89 } else if (instr->IsNop()) { | 91 } else if (instr->IsNop()) { |
90 // skip nops. | 92 // skip nops. |
91 TRACE((" nop\n")); | 93 TRACE(" nop\n"); |
92 continue; | 94 continue; |
93 } else if (instr->arch_opcode() == kArchJmp) { | 95 } else if (instr->arch_opcode() == kArchJmp) { |
94 // try to forward the jump instruction. | 96 // try to forward the jump instruction. |
95 TRACE((" jmp\n")); | 97 TRACE(" jmp\n"); |
96 fw = code->InputRpo(instr, 0); | 98 fw = code->InputRpo(instr, 0); |
97 fallthru = false; | 99 fallthru = false; |
98 } else { | 100 } else { |
99 // can't skip other instructions. | 101 // can't skip other instructions. |
100 TRACE((" other\n")); | 102 TRACE(" other\n"); |
101 fallthru = false; | 103 fallthru = false; |
102 } | 104 } |
103 break; | 105 break; |
104 } | 106 } |
105 if (fallthru) { | 107 if (fallthru) { |
106 int next = 1 + block->rpo_number().ToInt(); | 108 int next = 1 + block->rpo_number().ToInt(); |
107 if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next); | 109 if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next); |
108 } | 110 } |
109 state.Forward(fw); | 111 state.Forward(fw); |
110 } | 112 } |
111 } | 113 } |
112 | 114 |
113 #ifdef DEBUG | 115 #ifdef DEBUG |
114 for (RpoNumber num : result) { | 116 for (RpoNumber num : result) { |
115 CHECK(num.IsValid()); | 117 CHECK(num.IsValid()); |
116 } | 118 } |
117 #endif | 119 #endif |
118 | 120 |
119 if (FLAG_trace_turbo_jt) { | 121 if (FLAG_trace_turbo_jt) { |
120 for (int i = 0; i < static_cast<int>(result.size()); i++) { | 122 for (int i = 0; i < static_cast<int>(result.size()); i++) { |
121 TRACE(("B%d ", i)); | 123 TRACE("B%d ", i); |
122 int to = result[i].ToInt(); | 124 int to = result[i].ToInt(); |
123 if (i != to) { | 125 if (i != to) { |
124 TRACE(("-> B%d\n", to)); | 126 TRACE("-> B%d\n", to); |
125 } else { | 127 } else { |
126 TRACE(("\n")); | 128 TRACE("\n"); |
127 } | 129 } |
128 } | 130 } |
129 } | 131 } |
130 | 132 |
131 return state.forwarded; | 133 return state.forwarded; |
132 } | 134 } |
133 | 135 |
134 | 136 |
135 void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result, | 137 void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result, |
136 InstructionSequence* code) { | 138 InstructionSequence* code) { |
137 if (!FLAG_turbo_jt) return; | 139 if (!FLAG_turbo_jt) return; |
138 | 140 |
139 Zone local_zone; | 141 Zone local_zone; |
140 ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone); | 142 ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone); |
141 | 143 |
142 // Skip empty blocks when the previous block doesn't fall through. | 144 // Skip empty blocks when the previous block doesn't fall through. |
143 bool prev_fallthru = true; | 145 bool prev_fallthru = true; |
144 for (auto const block : code->instruction_blocks()) { | 146 for (auto const block : code->instruction_blocks()) { |
145 int block_num = block->rpo_number().ToInt(); | 147 int block_num = block->rpo_number().ToInt(); |
146 skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num; | 148 skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num; |
147 | 149 |
148 bool fallthru = true; | 150 bool fallthru = true; |
149 for (int i = block->code_start(); i < block->code_end(); ++i) { | 151 for (int i = block->code_start(); i < block->code_end(); ++i) { |
150 Instruction* instr = code->InstructionAt(i); | 152 Instruction* instr = code->InstructionAt(i); |
151 if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) { | 153 if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) { |
152 fallthru = false; // branches don't fall through to the next block. | 154 fallthru = false; // branches don't fall through to the next block. |
153 } else if (instr->arch_opcode() == kArchJmp) { | 155 } else if (instr->arch_opcode() == kArchJmp) { |
154 if (skip[block_num]) { | 156 if (skip[block_num]) { |
155 // Overwrite a redundant jump with a nop. | 157 // Overwrite a redundant jump with a nop. |
156 TRACE(("jt-fw nop @%d\n", i)); | 158 TRACE("jt-fw nop @%d\n", i); |
157 instr->OverwriteWithNop(); | 159 instr->OverwriteWithNop(); |
158 } | 160 } |
159 fallthru = false; // jumps don't fall through to the next block. | 161 fallthru = false; // jumps don't fall through to the next block. |
160 } | 162 } |
161 } | 163 } |
162 prev_fallthru = fallthru; | 164 prev_fallthru = fallthru; |
163 } | 165 } |
164 | 166 |
165 // Patch RPO immediates. | 167 // Patch RPO immediates. |
166 InstructionSequence::Immediates& immediates = code->immediates(); | 168 InstructionSequence::Immediates& immediates = code->immediates(); |
(...skipping 18 matching lines...) Expand all Loading... |
185 if (block->IsDeferred()) { | 187 if (block->IsDeferred()) { |
186 block->set_ao_number(RpoNumber::FromInt(ao)); | 188 block->set_ao_number(RpoNumber::FromInt(ao)); |
187 if (!skip[block->rpo_number().ToInt()]) ao++; | 189 if (!skip[block->rpo_number().ToInt()]) ao++; |
188 } | 190 } |
189 } | 191 } |
190 } | 192 } |
191 | 193 |
192 } // namespace compiler | 194 } // namespace compiler |
193 } // namespace internal | 195 } // namespace internal |
194 } // namespace v8 | 196 } // namespace v8 |
OLD | NEW |