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 
Clearv8::internal::compiler::JumpThreadingState22   void Clear(size_t count) { result.assign(count, unvisited()); }
PushIfUnvisitedv8::internal::compiler::JumpThreadingState23   void PushIfUnvisited(RpoNumber num) {
24     if (result[num.ToInt()] == unvisited()) {
25       stack.push(num);
26       result[num.ToInt()] = onstack();
27     }
28   }
Forwardv8::internal::compiler::JumpThreadingState29   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   }
unvisitedv8::internal::compiler::JumpThreadingState52   RpoNumber unvisited() { return RpoNumber::FromInt(-1); }
onstackv8::internal::compiler::JumpThreadingState53   RpoNumber onstack() { return RpoNumber::FromInt(-2); }
54 };
55 
ComputeForwarding(Zone * local_zone,ZoneVector<RpoNumber> & result,InstructionSequence * code,bool frame_at_start)56 bool 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 
ApplyForwarding(ZoneVector<RpoNumber> & result,InstructionSequence * code)142 void 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