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 : #ifndef V8_COMPILER_INSTRUCTION_SCHEDULER_H_
6 : #define V8_COMPILER_INSTRUCTION_SCHEDULER_H_
7 :
8 : #include "src/compiler/instruction.h"
9 : #include "src/zone/zone-containers.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 : namespace compiler {
14 :
15 : // A set of flags describing properties of the instructions so that the
16 : // scheduler is aware of dependencies between instructions.
17 : enum ArchOpcodeFlags {
18 : kNoOpcodeFlags = 0,
19 : kIsBlockTerminator = 1, // The instruction marks the end of a basic block
20 : // e.g.: jump and return instructions.
21 : kHasSideEffect = 2, // The instruction has some side effects (memory
22 : // store, function call...)
23 : kIsLoadOperation = 4, // The instruction is a memory load.
24 : kMayNeedDeoptOrTrapCheck = 8, // The instruction may be associated with a
25 : // deopt or trap check which must be run before
26 : // instruction e.g. div on Intel platform which
27 : // will raise an exception when the divisor is
28 : // zero.
29 : };
30 :
31 : class InstructionScheduler final : public ZoneObject {
32 : public:
33 : InstructionScheduler(Zone* zone, InstructionSequence* sequence);
34 :
35 : void StartBlock(RpoNumber rpo);
36 : void EndBlock(RpoNumber rpo);
37 :
38 : void AddInstruction(Instruction* instr);
39 :
40 : static bool SchedulerSupported();
41 :
42 : private:
43 : // A scheduling graph node.
44 : // Represent an instruction and their dependencies.
45 : class ScheduleGraphNode: public ZoneObject {
46 : public:
47 : ScheduleGraphNode(Zone* zone, Instruction* instr);
48 :
49 : // Mark the instruction represented by 'node' as a dependecy of this one.
50 : // The current instruction will be registered as an unscheduled predecessor
51 : // of 'node' (i.e. it must be scheduled before 'node').
52 : void AddSuccessor(ScheduleGraphNode* node);
53 :
54 : // Check if all the predecessors of this instruction have been scheduled.
55 : bool HasUnscheduledPredecessor() {
56 : return unscheduled_predecessors_count_ != 0;
57 : }
58 :
59 : // Record that we have scheduled one of the predecessors of this node.
60 : void DropUnscheduledPredecessor() {
61 : DCHECK_LT(0, unscheduled_predecessors_count_);
62 0 : unscheduled_predecessors_count_--;
63 : }
64 :
65 : Instruction* instruction() { return instr_; }
66 : ZoneDeque<ScheduleGraphNode*>& successors() { return successors_; }
67 : int latency() const { return latency_; }
68 :
69 : int total_latency() const { return total_latency_; }
70 0 : void set_total_latency(int latency) { total_latency_ = latency; }
71 :
72 : int start_cycle() const { return start_cycle_; }
73 0 : void set_start_cycle(int start_cycle) { start_cycle_ = start_cycle; }
74 :
75 : private:
76 : Instruction* instr_;
77 : ZoneDeque<ScheduleGraphNode*> successors_;
78 :
79 : // Number of unscheduled predecessors for this node.
80 : int unscheduled_predecessors_count_;
81 :
82 : // Estimate of the instruction latency (the number of cycles it takes for
83 : // instruction to complete).
84 : int latency_;
85 :
86 : // The sum of all the latencies on the path from this node to the end of
87 : // the graph (i.e. a node with no successor).
88 : int total_latency_;
89 :
90 : // The scheduler keeps a nominal cycle count to keep track of when the
91 : // result of an instruction is available. This field is updated by the
92 : // scheduler to indicate when the value of all the operands of this
93 : // instruction will be available.
94 : int start_cycle_;
95 : };
96 :
97 : // Keep track of all nodes ready to be scheduled (i.e. all their dependencies
98 : // have been scheduled. Note that this class is inteded to be extended by
99 : // concrete implementation of the scheduling queue which define the policy
100 : // to pop node from the queue.
101 : class SchedulingQueueBase {
102 : public:
103 0 : explicit SchedulingQueueBase(InstructionScheduler* scheduler)
104 : : scheduler_(scheduler),
105 0 : nodes_(scheduler->zone()) {
106 : }
107 :
108 : void AddNode(ScheduleGraphNode* node);
109 :
110 : bool IsEmpty() const {
111 : return nodes_.empty();
112 : }
113 :
114 : protected:
115 : InstructionScheduler* scheduler_;
116 : ZoneLinkedList<ScheduleGraphNode*> nodes_;
117 : };
118 :
119 : // A scheduling queue which prioritize nodes on the critical path (we look
120 : // for the instruction with the highest latency on the path to reach the end
121 : // of the graph).
122 : class CriticalPathFirstQueue : public SchedulingQueueBase {
123 : public:
124 : explicit CriticalPathFirstQueue(InstructionScheduler* scheduler)
125 : : SchedulingQueueBase(scheduler) { }
126 :
127 : // Look for the best candidate to schedule, remove it from the queue and
128 : // return it.
129 : ScheduleGraphNode* PopBestCandidate(int cycle);
130 : };
131 :
132 : // A queue which pop a random node from the queue to perform stress tests on
133 : // the scheduler.
134 : class StressSchedulerQueue : public SchedulingQueueBase {
135 : public:
136 : explicit StressSchedulerQueue(InstructionScheduler* scheduler)
137 : : SchedulingQueueBase(scheduler) { }
138 :
139 : ScheduleGraphNode* PopBestCandidate(int cycle);
140 :
141 : private:
142 : Isolate *isolate() {
143 : return scheduler_->isolate();
144 : }
145 : };
146 :
147 : // Perform scheduling for the current block specifying the queue type to
148 : // use to determine the next best candidate.
149 : template <typename QueueType>
150 0 : void ScheduleBlock();
151 :
152 : // Return the scheduling properties of the given instruction.
153 : int GetInstructionFlags(const Instruction* instr) const;
154 : int GetTargetInstructionFlags(const Instruction* instr) const;
155 :
156 : // Return true if the instruction is a basic block terminator.
157 : bool IsBlockTerminator(const Instruction* instr) const;
158 :
159 : // Check whether the given instruction has side effects (e.g. function call,
160 : // memory store).
161 : bool HasSideEffect(const Instruction* instr) const {
162 0 : return (GetInstructionFlags(instr) & kHasSideEffect) != 0;
163 : }
164 :
165 : // Return true if the instruction is a memory load.
166 : bool IsLoadOperation(const Instruction* instr) const {
167 0 : return (GetInstructionFlags(instr) & kIsLoadOperation) != 0;
168 : }
169 :
170 : // The scheduler will not move the following instructions before the last
171 : // deopt/trap check:
172 : // * loads (this is conservative)
173 : // * instructions with side effect
174 : // * other deopts/traps
175 : // Any other instruction can be moved, apart from those that raise exceptions
176 : // on specific inputs - these are filtered out by the deopt/trap check.
177 : bool MayNeedDeoptOrTrapCheck(const Instruction* instr) const {
178 0 : return (GetInstructionFlags(instr) & kMayNeedDeoptOrTrapCheck) != 0;
179 : }
180 :
181 : // Return true if the instruction cannot be moved before the last deopt or
182 : // trap point we encountered.
183 0 : bool DependsOnDeoptOrTrap(const Instruction* instr) const {
184 0 : return MayNeedDeoptOrTrapCheck(instr) || instr->IsDeoptimizeCall() ||
185 0 : instr->IsTrap() || HasSideEffect(instr) || IsLoadOperation(instr);
186 : }
187 :
188 : // Identify nops used as a definition point for live-in registers at
189 : // function entry.
190 0 : bool IsFixedRegisterParameter(const Instruction* instr) const {
191 0 : return (instr->arch_opcode() == kArchNop) && (instr->OutputCount() == 1) &&
192 0 : (instr->OutputAt(0)->IsUnallocated()) &&
193 : (UnallocatedOperand::cast(instr->OutputAt(0))
194 0 : ->HasFixedRegisterPolicy() ||
195 : UnallocatedOperand::cast(instr->OutputAt(0))
196 0 : ->HasFixedFPRegisterPolicy());
197 : }
198 :
199 : void ComputeTotalLatencies();
200 :
201 : static int GetInstructionLatency(const Instruction* instr);
202 :
203 : Zone* zone() { return zone_; }
204 : InstructionSequence* sequence() { return sequence_; }
205 0 : Isolate* isolate() { return sequence()->isolate(); }
206 :
207 : Zone* zone_;
208 : InstructionSequence* sequence_;
209 : ZoneVector<ScheduleGraphNode*> graph_;
210 :
211 : // Last side effect instruction encountered while building the graph.
212 : ScheduleGraphNode* last_side_effect_instr_;
213 :
214 : // Set of load instructions encountered since the last side effect instruction
215 : // which will be added as predecessors of the next instruction with side
216 : // effects.
217 : ZoneVector<ScheduleGraphNode*> pending_loads_;
218 :
219 : // Live-in register markers are nop instructions which are emitted at the
220 : // beginning of a basic block so that the register allocator will find a
221 : // defining instruction for live-in values. They must not be moved.
222 : // All these nops are chained together and added as a predecessor of every
223 : // other instructions in the basic block.
224 : ScheduleGraphNode* last_live_in_reg_marker_;
225 :
226 : // Last deoptimization or trap instruction encountered while building the
227 : // graph.
228 : ScheduleGraphNode* last_deopt_or_trap_;
229 :
230 : // Keep track of definition points for virtual registers. This is used to
231 : // record operand dependencies in the scheduling graph.
232 : ZoneMap<int32_t, ScheduleGraphNode*> operands_map_;
233 : };
234 :
235 : } // namespace compiler
236 : } // namespace internal
237 : } // namespace v8
238 :
239 : #endif // V8_COMPILER_INSTRUCTION_SCHEDULER_H_
|
