Line data Source code
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 :
22 2605795 : void Clear(size_t count) { result.assign(count, unvisited()); }
23 13052900 : void PushIfUnvisited(RpoNumber num) {
24 37390319 : if (result[num.ToInt()] == unvisited()) {
25 11284483 : stack.push(num);
26 22569038 : result[num.ToInt()] = onstack();
27 : }
28 13052936 : }
29 14821379 : void Forward(RpoNumber to) {
30 29642758 : RpoNumber from = stack.top();
31 44464191 : RpoNumber to_to = result[to.ToInt()];
32 : bool pop = true;
33 14821379 : if (to == from) {
34 10061520 : TRACE(" xx %d\n", from.ToInt());
35 20123126 : result[from.ToInt()] = from;
36 4759859 : } else if (to_to == unvisited()) {
37 1768456 : TRACE(" fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt());
38 1768456 : stack.push(to);
39 3536932 : result[to.ToInt()] = onstack();
40 : pop = false; // recurse.
41 2991403 : } else if (to_to == onstack()) {
42 54 : TRACE(" fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt());
43 108 : result[from.ToInt()] = to; // break the cycle.
44 54 : forwarded = true;
45 : } else {
46 2991349 : TRACE(" fw %d -> %d (forward)\n", from.ToInt(), to.ToInt());
47 5982700 : result[from.ToInt()] = to_to; // forward the block.
48 2991350 : forwarded = true;
49 : }
50 14821433 : if (pop) stack.pop();
51 14821433 : }
52 : RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
53 : RpoNumber onstack() { return RpoNumber::FromInt(-2); }
54 : };
55 :
56 1302793 : bool JumpThreading::ComputeForwarding(Zone* local_zone,
57 : ZoneVector<RpoNumber>& result,
58 18728617 : InstructionSequence* code,
59 : bool frame_at_start) {
60 1302793 : ZoneStack<RpoNumber> stack(local_zone);
61 1302896 : JumpThreadingState state = {false, result, stack};
62 1302896 : state.Clear(code->InstructionBlockCount());
63 :
64 : // Iterate over the blocks forward, pushing the blocks onto the stack.
65 15658719 : for (auto const block : code->instruction_blocks()) {
66 13052897 : RpoNumber current = block->rpo_number();
67 13052897 : state.PushIfUnvisited(current);
68 :
69 : // Process the stack, which implements DFS through empty blocks.
70 68801329 : while (!state.stack.empty()) {
71 69952617 : InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
72 : // Process the instructions in a block up to a non-empty instruction.
73 14821296 : TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()),
74 : block->rpo_number().ToInt());
75 : bool fallthru = true;
76 14821332 : RpoNumber fw = block->rpo_number();
77 48361628 : for (int i = block->code_start(); i < block->code_end(); ++i) {
78 18162657 : Instruction* instr = code->InstructionAt(i);
79 22879240 : if (!instr->AreMovesRedundant()) {
80 : // can't skip instructions with non redundant moves.
81 4716800 : TRACE(" parallel move\n");
82 : fallthru = false;
83 36325314 : } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
84 : // can't skip instructions with flags continuations.
85 1514266 : TRACE(" flags\n");
86 : fallthru = false;
87 16648391 : } else if (instr->IsNop()) {
88 : // skip nops.
89 9359501 : TRACE(" nop\n");
90 : continue;
91 7288890 : } else if (instr->arch_opcode() == kArchJmp) {
92 : // try to forward the jump instruction.
93 4766576 : 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 10187250 : if (frame_at_start ||
100 : !(block->must_deconstruct_frame() ||
101 653769 : block->must_construct_frame())) {
102 4758929 : fw = code->InputRpo(instr, 0);
103 : }
104 : fallthru = false;
105 : } else {
106 : // can't skip other instructions.
107 2522314 : TRACE(" other\n");
108 : fallthru = false;
109 : }
110 : break;
111 : }
112 14821284 : if (fallthru) {
113 1301541 : int next = 1 + block->rpo_number().ToInt();
114 1301541 : if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
115 : }
116 14821284 : state.Forward(fw);
117 : }
118 : }
119 :
120 : #ifdef DEBUG
121 : for (RpoNumber num : result) {
122 : DCHECK(num.IsValid());
123 : }
124 : #endif
125 :
126 1302923 : if (FLAG_trace_turbo_jt) {
127 0 : for (int i = 0; i < static_cast<int>(result.size()); i++) {
128 0 : TRACE("B%d ", i);
129 0 : int to = result[i].ToInt();
130 0 : if (i != to) {
131 0 : TRACE("-> B%d\n", to);
132 : } else {
133 0 : TRACE("\n");
134 : }
135 : }
136 : }
137 :
138 2605836 : return state.forwarded;
139 : }
140 :
141 :
142 676323 : void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
143 2705450 : InstructionSequence* code) {
144 676323 : if (!FLAG_turbo_jt) return;
145 :
146 676323 : Zone local_zone(code->isolate()->allocator(), ZONE_NAME);
147 25073324 : 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 76116232 : for (auto const block : code->instruction_blocks()) {
152 : int block_num = block->rpo_number().ToInt();
153 21477982 : skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
154 :
155 : bool fallthru = true;
156 102852778 : for (int i = block->code_start(); i < block->code_end(); ++i) {
157 39757846 : Instruction* instr = code->InstructionAt(i);
158 79515692 : if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) {
159 : fallthru = false; // branches don't fall through to the next block.
160 36203289 : } else if (instr->arch_opcode() == kArchJmp) {
161 12513346 : if (skip[block_num]) {
162 : // Overwrite a redundant jump with a nop.
163 2883182 : 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 61687606 : for (size_t i = 0; i < immediates.size(); i++) {
175 61687606 : Constant constant = immediates[i];
176 30505618 : if (constant.type() == Constant::kRpoNumber) {
177 : RpoNumber rpo = constant.ToRpoNumber();
178 27822370 : RpoNumber fw = result[rpo.ToInt()];
179 17199406 : if (!(fw == rpo)) immediates[i] = Constant(fw);
180 : }
181 : }
182 :
183 : // Recompute assembly order numbers.
184 : int ao = 0;
185 13021311 : for (auto const block : code->instruction_blocks()) {
186 11668571 : if (!block->IsDeferred()) {
187 : block->set_ao_number(RpoNumber::FromInt(ao));
188 17180118 : if (!skip[block->rpo_number().ToInt()]) ao++;
189 : }
190 : }
191 13021390 : for (auto const block : code->instruction_blocks()) {
192 11668650 : if (block->IsDeferred()) {
193 : block->set_ao_number(RpoNumber::FromInt(ao));
194 6157132 : if (!skip[block->rpo_number().ToInt()]) ao++;
195 : }
196 676370 : }
197 : }
198 :
199 : #undef TRACE
200 :
201 : } // namespace compiler
202 : } // namespace internal
203 : } // namespace v8
|
