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 : #include "src/objects-inl.h"
8 :
9 : namespace v8 {
10 : namespace internal {
11 : namespace compiler {
12 :
13 : #define TRACE(...) \
14 : do { \
15 : if (FLAG_trace_turbo_jt) PrintF(__VA_ARGS__); \
16 : } while (false)
17 :
18 : struct JumpThreadingState {
19 : bool forwarded;
20 : ZoneVector<RpoNumber>& result;
21 : ZoneStack<RpoNumber>& stack;
22 :
23 1835029 : void Clear(size_t count) { result.assign(count, unvisited()); }
24 11471216 : void PushIfUnvisited(RpoNumber num) {
25 32778817 : if (result[num.ToInt()] == unvisited()) {
26 9836378 : stack.push(num);
27 19672770 : result[num.ToInt()] = onstack();
28 : }
29 11471223 : }
30 13106040 : void Forward(RpoNumber to) {
31 26212080 : RpoNumber from = stack.top();
32 39318170 : RpoNumber to_to = result[to.ToInt()];
33 : bool pop = true;
34 13106040 : if (to == from) {
35 8693774 : TRACE(" xx %d\n", from.ToInt());
36 17387626 : result[from.ToInt()] = from;
37 4412266 : } else if (to_to == unvisited()) {
38 1634838 : TRACE(" fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt());
39 1634838 : stack.push(to);
40 3269690 : result[to.ToInt()] = onstack();
41 : pop = false; // recurse.
42 2777428 : } else if (to_to == onstack()) {
43 63 : TRACE(" fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt());
44 126 : result[from.ToInt()] = to; // break the cycle.
45 63 : forwarded = true;
46 : } else {
47 2777365 : TRACE(" fw %d -> %d (forward)\n", from.ToInt(), to.ToInt());
48 5554738 : result[from.ToInt()] = to_to; // forward the block.
49 2777369 : forwarded = true;
50 : }
51 13106090 : if (pop) stack.pop();
52 13106090 : }
53 : RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
54 : RpoNumber onstack() { return RpoNumber::FromInt(-2); }
55 : };
56 :
57 917387 : bool JumpThreading::ComputeForwarding(Zone* local_zone,
58 : ZoneVector<RpoNumber>& result,
59 15856729 : InstructionSequence* code,
60 : bool frame_at_start) {
61 917387 : ZoneStack<RpoNumber> stack(local_zone);
62 917487 : JumpThreadingState state = {false, result, stack};
63 917487 : state.Clear(code->InstructionBlockCount());
64 :
65 : // Iterate over the blocks forward, pushing the blocks onto the stack.
66 13306230 : for (auto const block : code->instruction_blocks()) {
67 11471215 : RpoNumber current = block->rpo_number();
68 11471215 : state.PushIfUnvisited(current);
69 :
70 : // Process the stack, which implements DFS through empty blocks.
71 60625316 : while (!state.stack.empty()) {
72 62674288 : InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
73 : // Process the instructions in a block up to a non-empty instruction.
74 13105939 : TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()),
75 : block->rpo_number().ToInt());
76 : bool fallthru = true;
77 13105965 : RpoNumber fw = block->rpo_number();
78 43768974 : for (int i = block->code_start(); i < block->code_end(); ++i) {
79 16847759 : Instruction* instr = code->InstructionAt(i);
80 20968582 : if (!instr->AreMovesRedundant()) {
81 : // can't skip instructions with non redundant moves.
82 4121100 : TRACE(" parallel move\n");
83 : fallthru = false;
84 33695518 : } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
85 : // can't skip instructions with flags continuations.
86 1361563 : TRACE(" flags\n");
87 : fallthru = false;
88 15486196 : } else if (instr->IsNop()) {
89 : // skip nops.
90 8778523 : TRACE(" nop\n");
91 : continue;
92 6707673 : } else if (instr->arch_opcode() == kArchJmp) {
93 : // try to forward the jump instruction.
94 4418472 : TRACE(" jmp\n");
95 : // if this block deconstructs the frame, we can't forward it.
96 : // TODO(mtrofin): we can still forward if we end up building
97 : // the frame at start. So we should move the decision of whether
98 : // to build a frame or not in the register allocator, and trickle it
99 : // here and to the code generator.
100 9573030 : if (frame_at_start ||
101 : !(block->must_deconstruct_frame() ||
102 735908 : block->must_construct_frame())) {
103 4411950 : fw = code->InputRpo(instr, 0);
104 : }
105 : fallthru = false;
106 : } else {
107 : // can't skip other instructions.
108 2289201 : TRACE(" other\n");
109 : fallthru = false;
110 : }
111 : break;
112 : }
113 13105911 : if (fallthru) {
114 915781 : int next = 1 + block->rpo_number().ToInt();
115 915781 : if (next < code->InstructionBlockCount()) fw = RpoNumber::FromInt(next);
116 : }
117 13105911 : state.Forward(fw);
118 : }
119 : }
120 :
121 : #ifdef DEBUG
122 : for (RpoNumber num : result) {
123 : CHECK(num.IsValid());
124 : }
125 : #endif
126 :
127 917473 : if (FLAG_trace_turbo_jt) {
128 0 : for (int i = 0; i < static_cast<int>(result.size()); i++) {
129 0 : TRACE("B%d ", i);
130 0 : int to = result[i].ToInt();
131 0 : if (i != to) {
132 0 : TRACE("-> B%d\n", to);
133 : } else {
134 0 : TRACE("\n");
135 : }
136 : }
137 : }
138 :
139 1834914 : return state.forwarded;
140 : }
141 :
142 :
143 557287 : void JumpThreading::ApplyForwarding(ZoneVector<RpoNumber>& result,
144 1672063 : InstructionSequence* code) {
145 557287 : if (!FLAG_turbo_jt) return;
146 :
147 557287 : Zone local_zone(code->isolate()->allocator(), ZONE_NAME);
148 23109835 : ZoneVector<bool> skip(static_cast<int>(result.size()), false, &local_zone);
149 :
150 : // Skip empty blocks when the previous block doesn't fall through.
151 : bool prev_fallthru = true;
152 68697179 : for (auto const block : code->instruction_blocks()) {
153 : int block_num = block->rpo_number().ToInt();
154 19820777 : skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
155 :
156 : bool fallthru = true;
157 92528146 : for (int i = block->code_start(); i < block->code_end(); ++i) {
158 35604907 : Instruction* instr = code->InstructionAt(i);
159 71209814 : if (FlagsModeField::decode(instr->opcode()) == kFlags_branch) {
160 : fallthru = false; // branches don't fall through to the next block.
161 32331830 : } else if (instr->arch_opcode() == kArchJmp) {
162 11780488 : if (skip[block_num]) {
163 : // Overwrite a redundant jump with a nop.
164 2631369 : TRACE("jt-fw nop @%d\n", i);
165 : instr->OverwriteWithNop();
166 : }
167 : fallthru = false; // jumps don't fall through to the next block.
168 : }
169 : }
170 : prev_fallthru = fallthru;
171 : }
172 :
173 : // Patch RPO immediates.
174 : InstructionSequence::Immediates& immediates = code->immediates();
175 56888871 : for (size_t i = 0; i < immediates.size(); i++) {
176 56888871 : Constant constant = immediates[i];
177 28165748 : if (constant.type() == Constant::kRpoNumber) {
178 : RpoNumber rpo = constant.ToRpoNumber();
179 25667118 : RpoNumber fw = result[rpo.ToInt()];
180 15902469 : if (!(fw == rpo)) immediates[i] = Constant(fw);
181 : }
182 : }
183 :
184 : // Recompute assembly order numbers.
185 : int ao = 0;
186 11773791 : for (auto const block : code->instruction_blocks()) {
187 10659041 : if (!block->IsDeferred()) {
188 : block->set_ao_number(RpoNumber::FromInt(ao));
189 15905666 : if (!skip[block->rpo_number().ToInt()]) ao++;
190 : }
191 : }
192 21875389 : for (auto const block : code->instruction_blocks()) {
193 10659007 : if (block->IsDeferred()) {
194 : block->set_ao_number(RpoNumber::FromInt(ao));
195 5412982 : if (!skip[block->rpo_number().ToInt()]) ao++;
196 : }
197 557375 : }
198 : }
199 :
200 : } // namespace compiler
201 : } // namespace internal
202 : } // namespace v8
|
