Line data Source code
1 : // Copyright 2015 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/instruction-scheduler.h"
6 :
7 : #include "src/base/adapters.h"
8 : #include "src/base/utils/random-number-generator.h"
9 :
10 : namespace v8 {
11 : namespace internal {
12 : namespace compiler {
13 :
14 0 : void InstructionScheduler::SchedulingQueueBase::AddNode(
15 : ScheduleGraphNode* node) {
16 : // We keep the ready list sorted by total latency so that we can quickly find
17 : // the next best candidate to schedule.
18 0 : auto it = nodes_.begin();
19 0 : while ((it != nodes_.end()) &&
20 0 : ((*it)->total_latency() >= node->total_latency())) {
21 : ++it;
22 : }
23 0 : nodes_.insert(it, node);
24 0 : }
25 :
26 :
27 : InstructionScheduler::ScheduleGraphNode*
28 0 : InstructionScheduler::CriticalPathFirstQueue::PopBestCandidate(int cycle) {
29 : DCHECK(!IsEmpty());
30 0 : auto candidate = nodes_.end();
31 0 : for (auto iterator = nodes_.begin(); iterator != nodes_.end(); ++iterator) {
32 : // We only consider instructions that have all their operands ready.
33 0 : if (cycle >= (*iterator)->start_cycle()) {
34 : candidate = iterator;
35 : break;
36 : }
37 : }
38 :
39 0 : if (candidate != nodes_.end()) {
40 0 : ScheduleGraphNode *result = *candidate;
41 : nodes_.erase(candidate);
42 0 : return result;
43 : }
44 :
45 : return nullptr;
46 : }
47 :
48 :
49 : InstructionScheduler::ScheduleGraphNode*
50 0 : InstructionScheduler::StressSchedulerQueue::PopBestCandidate(int cycle) {
51 : DCHECK(!IsEmpty());
52 : // Choose a random element from the ready list.
53 0 : auto candidate = nodes_.begin();
54 : std::advance(candidate, isolate()->random_number_generator()->NextInt(
55 0 : static_cast<int>(nodes_.size())));
56 0 : ScheduleGraphNode *result = *candidate;
57 : nodes_.erase(candidate);
58 0 : return result;
59 : }
60 :
61 :
62 0 : InstructionScheduler::ScheduleGraphNode::ScheduleGraphNode(
63 : Zone* zone,
64 : Instruction* instr)
65 : : instr_(instr),
66 : successors_(zone),
67 : unscheduled_predecessors_count_(0),
68 0 : latency_(GetInstructionLatency(instr)),
69 : total_latency_(-1),
70 0 : start_cycle_(-1) {
71 0 : }
72 :
73 :
74 0 : void InstructionScheduler::ScheduleGraphNode::AddSuccessor(
75 : ScheduleGraphNode* node) {
76 0 : successors_.push_back(node);
77 0 : node->unscheduled_predecessors_count_++;
78 0 : }
79 :
80 :
81 0 : InstructionScheduler::InstructionScheduler(Zone* zone,
82 : InstructionSequence* sequence)
83 : : zone_(zone),
84 : sequence_(sequence),
85 : graph_(zone),
86 : last_side_effect_instr_(nullptr),
87 : pending_loads_(zone),
88 : last_live_in_reg_marker_(nullptr),
89 : last_deopt_(nullptr),
90 0 : operands_map_(zone) {}
91 :
92 :
93 0 : void InstructionScheduler::StartBlock(RpoNumber rpo) {
94 : DCHECK(graph_.empty());
95 : DCHECK(last_side_effect_instr_ == nullptr);
96 : DCHECK(pending_loads_.empty());
97 : DCHECK(last_live_in_reg_marker_ == nullptr);
98 : DCHECK(last_deopt_ == nullptr);
99 : DCHECK(operands_map_.empty());
100 0 : sequence()->StartBlock(rpo);
101 0 : }
102 :
103 :
104 0 : void InstructionScheduler::EndBlock(RpoNumber rpo) {
105 0 : if (FLAG_turbo_stress_instruction_scheduling) {
106 0 : ScheduleBlock<StressSchedulerQueue>();
107 : } else {
108 0 : ScheduleBlock<CriticalPathFirstQueue>();
109 : }
110 0 : sequence()->EndBlock(rpo);
111 : graph_.clear();
112 0 : last_side_effect_instr_ = nullptr;
113 : pending_loads_.clear();
114 0 : last_live_in_reg_marker_ = nullptr;
115 0 : last_deopt_ = nullptr;
116 : operands_map_.clear();
117 0 : }
118 :
119 :
120 0 : void InstructionScheduler::AddInstruction(Instruction* instr) {
121 0 : ScheduleGraphNode* new_node = new (zone()) ScheduleGraphNode(zone(), instr);
122 :
123 0 : if (IsBlockTerminator(instr)) {
124 : // Make sure that basic block terminators are not moved by adding them
125 : // as successor of every instruction.
126 0 : for (ScheduleGraphNode* node : graph_) {
127 0 : node->AddSuccessor(new_node);
128 : }
129 0 : } else if (IsFixedRegisterParameter(instr)) {
130 0 : if (last_live_in_reg_marker_ != nullptr) {
131 0 : last_live_in_reg_marker_->AddSuccessor(new_node);
132 : }
133 0 : last_live_in_reg_marker_ = new_node;
134 : } else {
135 0 : if (last_live_in_reg_marker_ != nullptr) {
136 0 : last_live_in_reg_marker_->AddSuccessor(new_node);
137 : }
138 :
139 : // Make sure that instructions are not scheduled before the last
140 : // deoptimization point when they depend on it.
141 0 : if ((last_deopt_ != nullptr) && DependsOnDeoptimization(instr)) {
142 0 : last_deopt_->AddSuccessor(new_node);
143 : }
144 :
145 : // Instructions with side effects and memory operations can't be
146 : // reordered with respect to each other.
147 0 : if (HasSideEffect(instr)) {
148 0 : if (last_side_effect_instr_ != nullptr) {
149 0 : last_side_effect_instr_->AddSuccessor(new_node);
150 : }
151 0 : for (ScheduleGraphNode* load : pending_loads_) {
152 0 : load->AddSuccessor(new_node);
153 : }
154 : pending_loads_.clear();
155 0 : last_side_effect_instr_ = new_node;
156 0 : } else if (IsLoadOperation(instr)) {
157 : // Load operations can't be reordered with side effects instructions but
158 : // independent loads can be reordered with respect to each other.
159 0 : if (last_side_effect_instr_ != nullptr) {
160 0 : last_side_effect_instr_->AddSuccessor(new_node);
161 : }
162 0 : pending_loads_.push_back(new_node);
163 0 : } else if (instr->IsDeoptimizeCall()) {
164 : // Ensure that deopts are not reordered with respect to side-effect
165 : // instructions.
166 0 : if (last_side_effect_instr_ != nullptr) {
167 0 : last_side_effect_instr_->AddSuccessor(new_node);
168 : }
169 0 : last_deopt_ = new_node;
170 : }
171 :
172 : // Look for operand dependencies.
173 0 : for (size_t i = 0; i < instr->InputCount(); ++i) {
174 0 : const InstructionOperand* input = instr->InputAt(i);
175 0 : if (input->IsUnallocated()) {
176 0 : int32_t vreg = UnallocatedOperand::cast(input)->virtual_register();
177 : auto it = operands_map_.find(vreg);
178 0 : if (it != operands_map_.end()) {
179 0 : it->second->AddSuccessor(new_node);
180 : }
181 : }
182 : }
183 :
184 : // Record the virtual registers defined by this instruction.
185 0 : for (size_t i = 0; i < instr->OutputCount(); ++i) {
186 0 : const InstructionOperand* output = instr->OutputAt(i);
187 0 : if (output->IsUnallocated()) {
188 0 : operands_map_[UnallocatedOperand::cast(output)->virtual_register()] =
189 0 : new_node;
190 0 : } else if (output->IsConstant()) {
191 0 : operands_map_[ConstantOperand::cast(output)->virtual_register()] =
192 0 : new_node;
193 : }
194 : }
195 : }
196 :
197 0 : graph_.push_back(new_node);
198 0 : }
199 :
200 :
201 : template <typename QueueType>
202 0 : void InstructionScheduler::ScheduleBlock() {
203 : QueueType ready_list(this);
204 :
205 : // Compute total latencies so that we can schedule the critical path first.
206 0 : ComputeTotalLatencies();
207 :
208 : // Add nodes which don't have dependencies to the ready list.
209 0 : for (ScheduleGraphNode* node : graph_) {
210 0 : if (!node->HasUnscheduledPredecessor()) {
211 0 : ready_list.AddNode(node);
212 : }
213 : }
214 :
215 : // Go through the ready list and schedule the instructions.
216 : int cycle = 0;
217 0 : while (!ready_list.IsEmpty()) {
218 0 : ScheduleGraphNode* candidate = ready_list.PopBestCandidate(cycle);
219 :
220 0 : if (candidate != nullptr) {
221 0 : sequence()->AddInstruction(candidate->instruction());
222 :
223 0 : for (ScheduleGraphNode* successor : candidate->successors()) {
224 : successor->DropUnscheduledPredecessor();
225 : successor->set_start_cycle(
226 : std::max(successor->start_cycle(),
227 0 : cycle + candidate->latency()));
228 :
229 0 : if (!successor->HasUnscheduledPredecessor()) {
230 0 : ready_list.AddNode(successor);
231 : }
232 : }
233 : }
234 :
235 0 : cycle++;
236 : }
237 0 : }
238 :
239 :
240 0 : int InstructionScheduler::GetInstructionFlags(const Instruction* instr) const {
241 0 : switch (instr->arch_opcode()) {
242 : case kArchNop:
243 : case kArchFramePointer:
244 : case kArchParentFramePointer:
245 : case kArchTruncateDoubleToI:
246 : case kArchStackSlot:
247 : case kArchDebugBreak:
248 : case kArchComment:
249 : case kIeee754Float64Acos:
250 : case kIeee754Float64Acosh:
251 : case kIeee754Float64Asin:
252 : case kIeee754Float64Asinh:
253 : case kIeee754Float64Atan:
254 : case kIeee754Float64Atanh:
255 : case kIeee754Float64Atan2:
256 : case kIeee754Float64Cbrt:
257 : case kIeee754Float64Cos:
258 : case kIeee754Float64Cosh:
259 : case kIeee754Float64Exp:
260 : case kIeee754Float64Expm1:
261 : case kIeee754Float64Log:
262 : case kIeee754Float64Log1p:
263 : case kIeee754Float64Log10:
264 : case kIeee754Float64Log2:
265 : case kIeee754Float64Pow:
266 : case kIeee754Float64Sin:
267 : case kIeee754Float64Sinh:
268 : case kIeee754Float64Tan:
269 : case kIeee754Float64Tanh:
270 : return kNoOpcodeFlags;
271 :
272 : case kArchStackPointer:
273 : // ArchStackPointer instruction loads the current stack pointer value and
274 : // must not be reordered with instruction with side effects.
275 0 : return kIsLoadOperation;
276 :
277 : case kArchPrepareCallCFunction:
278 : case kArchPrepareTailCall:
279 : case kArchCallCFunction:
280 : case kArchCallCodeObject:
281 : case kArchCallJSFunction:
282 0 : return kHasSideEffect;
283 :
284 : case kArchTailCallCodeObjectFromJSFunction:
285 : case kArchTailCallCodeObject:
286 : case kArchTailCallJSFunctionFromJSFunction:
287 : case kArchTailCallAddress:
288 0 : return kHasSideEffect | kIsBlockTerminator;
289 :
290 : case kArchDeoptimize:
291 : case kArchJmp:
292 : case kArchLookupSwitch:
293 : case kArchTableSwitch:
294 : case kArchRet:
295 : case kArchThrowTerminator:
296 0 : return kIsBlockTerminator;
297 :
298 : case kCheckedLoadInt8:
299 : case kCheckedLoadUint8:
300 : case kCheckedLoadInt16:
301 : case kCheckedLoadUint16:
302 : case kCheckedLoadWord32:
303 : case kCheckedLoadWord64:
304 : case kCheckedLoadFloat32:
305 : case kCheckedLoadFloat64:
306 0 : return kIsLoadOperation;
307 :
308 : case kCheckedStoreWord8:
309 : case kCheckedStoreWord16:
310 : case kCheckedStoreWord32:
311 : case kCheckedStoreWord64:
312 : case kCheckedStoreFloat32:
313 : case kCheckedStoreFloat64:
314 : case kArchStoreWithWriteBarrier:
315 0 : return kHasSideEffect;
316 :
317 : case kAtomicLoadInt8:
318 : case kAtomicLoadUint8:
319 : case kAtomicLoadInt16:
320 : case kAtomicLoadUint16:
321 : case kAtomicLoadWord32:
322 0 : return kIsLoadOperation;
323 :
324 : case kAtomicStoreWord8:
325 : case kAtomicStoreWord16:
326 : case kAtomicStoreWord32:
327 0 : return kHasSideEffect;
328 :
329 : case kAtomicExchangeInt8:
330 : case kAtomicExchangeUint8:
331 : case kAtomicExchangeInt16:
332 : case kAtomicExchangeUint16:
333 : case kAtomicExchangeWord32:
334 : case kAtomicCompareExchangeInt8:
335 : case kAtomicCompareExchangeUint8:
336 : case kAtomicCompareExchangeInt16:
337 : case kAtomicCompareExchangeUint16:
338 : case kAtomicCompareExchangeWord32:
339 : case kAtomicAddInt8:
340 : case kAtomicAddUint8:
341 : case kAtomicAddInt16:
342 : case kAtomicAddUint16:
343 : case kAtomicAddWord32:
344 : case kAtomicSubInt8:
345 : case kAtomicSubUint8:
346 : case kAtomicSubInt16:
347 : case kAtomicSubUint16:
348 : case kAtomicSubWord32:
349 : case kAtomicAndInt8:
350 : case kAtomicAndUint8:
351 : case kAtomicAndInt16:
352 : case kAtomicAndUint16:
353 : case kAtomicAndWord32:
354 : case kAtomicOrInt8:
355 : case kAtomicOrUint8:
356 : case kAtomicOrInt16:
357 : case kAtomicOrUint16:
358 : case kAtomicOrWord32:
359 : case kAtomicXorInt8:
360 : case kAtomicXorUint8:
361 : case kAtomicXorInt16:
362 : case kAtomicXorUint16:
363 : case kAtomicXorWord32:
364 0 : return kHasSideEffect;
365 :
366 : #define CASE(Name) case k##Name:
367 : TARGET_ARCH_OPCODE_LIST(CASE)
368 : #undef CASE
369 0 : return GetTargetInstructionFlags(instr);
370 : }
371 :
372 0 : UNREACHABLE();
373 : return kNoOpcodeFlags;
374 : }
375 :
376 :
377 0 : bool InstructionScheduler::IsBlockTerminator(const Instruction* instr) const {
378 0 : return ((GetInstructionFlags(instr) & kIsBlockTerminator) ||
379 0 : (instr->flags_mode() == kFlags_branch));
380 : }
381 :
382 :
383 0 : void InstructionScheduler::ComputeTotalLatencies() {
384 0 : for (ScheduleGraphNode* node : base::Reversed(graph_)) {
385 : int max_latency = 0;
386 :
387 0 : for (ScheduleGraphNode* successor : node->successors()) {
388 : DCHECK(successor->total_latency() != -1);
389 0 : if (successor->total_latency() > max_latency) {
390 : max_latency = successor->total_latency();
391 : }
392 : }
393 :
394 0 : node->set_total_latency(max_latency + node->latency());
395 : }
396 0 : }
397 :
398 : } // namespace compiler
399 : } // namespace internal
400 : } // namespace v8
|
