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/backend/jump-threading.h"
6 : #include "src/compiler/backend/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 : namespace {
18 :
19 : struct JumpThreadingState {
20 : bool forwarded;
21 : ZoneVector<RpoNumber>& result;
22 : ZoneStack<RpoNumber>& stack;
23 :
24 5288365 : void Clear(size_t count) { result.assign(count, unvisited()); }
25 20500956 : void PushIfUnvisited(RpoNumber num) {
26 41001912 : if (result[num.ToInt()] == unvisited()) {
27 18010415 : stack.push(num);
28 36022666 : result[num.ToInt()] = onstack();
29 : }
30 20501874 : }
31 22991669 : void Forward(RpoNumber to) {
32 45983338 : RpoNumber from = stack.top();
33 45983338 : RpoNumber to_to = result[to.ToInt()];
34 : bool pop = true;
35 22991669 : if (to == from) {
36 16267841 : TRACE(" xx %d\n", from.ToInt());
37 32537440 : result[from.ToInt()] = from;
38 6723828 : } else if (to_to == unvisited()) {
39 2490482 : TRACE(" fw %d -> %d (recurse)\n", from.ToInt(), to.ToInt());
40 2490482 : stack.push(to);
41 4980988 : result[to.ToInt()] = onstack();
42 : pop = false; // recurse.
43 4233346 : } else if (to_to == onstack()) {
44 45 : TRACE(" fw %d -> %d (cycle)\n", from.ToInt(), to.ToInt());
45 90 : result[from.ToInt()] = to; // break the cycle.
46 45 : forwarded = true;
47 : } else {
48 4233301 : TRACE(" fw %d -> %d (forward)\n", from.ToInt(), to.ToInt());
49 8466610 : result[from.ToInt()] = to_to; // forward the block.
50 4233305 : forwarded = true;
51 : }
52 22992564 : if (pop) stack.pop();
53 22992900 : }
54 : RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
55 : RpoNumber onstack() { return RpoNumber::FromInt(-2); }
56 : };
57 :
58 22991210 : bool IsBlockWithBranchPoisoning(InstructionSequence* code,
59 : InstructionBlock* block) {
60 22991210 : if (block->PredecessorCount() != 1) return false;
61 16278524 : RpoNumber pred_rpo = (block->predecessors())[0];
62 16278524 : const InstructionBlock* pred = code->InstructionBlockAt(pred_rpo);
63 16278483 : if (pred->code_start() == pred->code_end()) return false;
64 16278553 : Instruction* instr = code->InstructionAt(pred->code_end() - 1);
65 16278047 : FlagsMode mode = FlagsModeField::decode(instr->opcode());
66 16278047 : return mode == kFlags_branch_and_poison;
67 : }
68 :
69 : } // namespace
70 :
71 2641372 : bool JumpThreading::ComputeForwarding(Zone* local_zone,
72 : ZoneVector<RpoNumber>& result,
73 : InstructionSequence* code,
74 : bool frame_at_start) {
75 2641372 : ZoneStack<RpoNumber> stack(local_zone);
76 2644522 : JumpThreadingState state = {false, result, stack};
77 2644522 : state.Clear(code->InstructionBlockCount());
78 :
79 : // Iterate over the blocks forward, pushing the blocks onto the stack.
80 23146025 : for (auto const block : code->instruction_blocks()) {
81 20501372 : RpoNumber current = block->rpo_number();
82 20501372 : state.PushIfUnvisited(current);
83 :
84 : // Process the stack, which implements DFS through empty blocks.
85 66486977 : while (!state.stack.empty()) {
86 22992316 : InstructionBlock* block = code->InstructionBlockAt(state.stack.top());
87 : // Process the instructions in a block up to a non-empty instruction.
88 22992654 : TRACE("jt [%d] B%d\n", static_cast<int>(stack.size()),
89 : block->rpo_number().ToInt());
90 22992654 : RpoNumber fw = block->rpo_number();
91 22992654 : if (!IsBlockWithBranchPoisoning(code, block)) {
92 : bool fallthru = true;
93 51257310 : for (int i = block->code_start(); i < block->code_end(); ++i) {
94 : Instruction* instr = code->InstructionAt(i);
95 34481625 : if (!instr->AreMovesRedundant()) {
96 : // can't skip instructions with non redundant moves.
97 7167658 : TRACE(" parallel move\n");
98 : fallthru = false;
99 54629312 : } else if (FlagsModeField::decode(instr->opcode()) != kFlags_none) {
100 : // can't skip instructions with flags continuations.
101 1705365 : TRACE(" flags\n");
102 : fallthru = false;
103 25609291 : } else if (instr->IsNop()) {
104 : // skip nops.
105 14133316 : TRACE(" nop\n");
106 : continue;
107 11475975 : } else if (instr->arch_opcode() == kArchJmp) {
108 : // try to forward the jump instruction.
109 6737815 : TRACE(" jmp\n");
110 : // if this block deconstructs the frame, we can't forward it.
111 : // TODO(mtrofin): we can still forward if we end up building
112 : // the frame at start. So we should move the decision of whether
113 : // to build a frame or not in the register allocator, and trickle it
114 : // here and to the code generator.
115 13475642 : if (frame_at_start || !(block->must_deconstruct_frame() ||
116 462568 : block->must_construct_frame())) {
117 6723709 : fw = code->InputRpo(instr, 0);
118 : }
119 : fallthru = false;
120 : } else {
121 : // can't skip other instructions.
122 4738160 : TRACE(" other\n");
123 : fallthru = false;
124 : }
125 : break;
126 : }
127 22991812 : if (fallthru) {
128 2643792 : int next = 1 + block->rpo_number().ToInt();
129 2643792 : if (next < code->InstructionBlockCount())
130 272 : fw = RpoNumber::FromInt(next);
131 : }
132 : }
133 22991510 : state.Forward(fw);
134 : }
135 : }
136 :
137 : #ifdef DEBUG
138 : for (RpoNumber num : result) {
139 : DCHECK(num.IsValid());
140 : }
141 : #endif
142 :
143 2644653 : if (FLAG_trace_turbo_jt) {
144 0 : for (int i = 0; i < static_cast<int>(result.size()); i++) {
145 0 : TRACE("B%d ", i);
146 0 : int to = result[i].ToInt();
147 0 : if (i != to) {
148 0 : TRACE("-> B%d\n", to);
149 : } else {
150 0 : TRACE("\n");
151 : }
152 : }
153 : }
154 :
155 5289197 : return state.forwarded;
156 : }
157 :
158 731890 : void JumpThreading::ApplyForwarding(Zone* local_zone,
159 : ZoneVector<RpoNumber>& result,
160 : InstructionSequence* code) {
161 731890 : if (!FLAG_turbo_jt) return;
162 :
163 731890 : ZoneVector<bool> skip(static_cast<int>(result.size()), false, local_zone);
164 :
165 : // Skip empty blocks when the previous block doesn't fall through.
166 : bool prev_fallthru = true;
167 17281570 : for (auto const block : code->instruction_blocks()) {
168 : int block_num = block->rpo_number().ToInt();
169 30862294 : skip[block_num] = !prev_fallthru && result[block_num].ToInt() != block_num;
170 :
171 : bool fallthru = true;
172 119076130 : for (int i = block->code_start(); i < block->code_end(); ++i) {
173 : Instruction* instr = code->InstructionAt(i);
174 51263327 : FlagsMode mode = FlagsModeField::decode(instr->opcode());
175 51263327 : if (mode == kFlags_branch || mode == kFlags_branch_and_poison) {
176 : fallthru = false; // branches don't fall through to the next block.
177 45940062 : } else if (instr->arch_opcode() == kArchJmp) {
178 8990333 : if (skip[block_num]) {
179 : // Overwrite a redundant jump with a nop.
180 4054669 : TRACE("jt-fw nop @%d\n", i);
181 : instr->OverwriteWithNop();
182 : }
183 : fallthru = false; // jumps don't fall through to the next block.
184 : }
185 : }
186 : prev_fallthru = fallthru;
187 : }
188 :
189 : // Patch RPO immediates.
190 : InstructionSequence::Immediates& immediates = code->immediates();
191 85986124 : for (size_t i = 0; i < immediates.size(); i++) {
192 42627011 : Constant constant = immediates[i];
193 42627011 : if (constant.type() == Constant::kRpoNumber) {
194 : RpoNumber rpo = constant.ToRpoNumber();
195 41084568 : RpoNumber fw = result[rpo.ToInt()];
196 25186321 : if (!(fw == rpo)) immediates[i] = Constant(fw);
197 : }
198 : }
199 :
200 : // Renumber the blocks so that IsNextInAssemblyOrder() will return true,
201 : // even if there are skipped blocks in-between.
202 : int ao = 0;
203 17280182 : for (auto const block : code->ao_blocks()) {
204 : block->set_ao_number(RpoNumber::FromInt(ao));
205 33096160 : if (!skip[block->rpo_number().ToInt()]) ao++;
206 : }
207 : }
208 :
209 : #undef TRACE
210 :
211 : } // namespace compiler
212 : } // namespace internal
213 122004 : } // namespace v8
|
