OLD | NEW |
| (Empty) |
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-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 }; | |
25 | |
26 | |
27 class InstructionScheduler final : public ZoneObject { | |
28 public: | |
29 InstructionScheduler(Zone* zone, InstructionSequence* sequence); | |
30 | |
31 void StartBlock(RpoNumber rpo); | |
32 void EndBlock(RpoNumber rpo); | |
33 | |
34 void AddInstruction(Instruction* instr); | |
35 | |
36 static bool SchedulerSupported(); | |
37 | |
38 private: | |
39 // A scheduling graph node. | |
40 // Represent an instruction and their dependencies. | |
41 class ScheduleGraphNode: public ZoneObject { | |
42 public: | |
43 ScheduleGraphNode(Zone* zone, Instruction* instr); | |
44 | |
45 // Mark the instruction represented by 'node' as a dependecy of this one. | |
46 // The current instruction will be registered as an unscheduled predecessor | |
47 // of 'node' (i.e. it must be scheduled before 'node'). | |
48 void AddSuccessor(ScheduleGraphNode* node); | |
49 | |
50 // Check if all the predecessors of this instruction have been scheduled. | |
51 bool HasUnscheduledPredecessor() { | |
52 return unscheduled_predecessors_count_ != 0; | |
53 } | |
54 | |
55 // Record that we have scheduled one of the predecessors of this node. | |
56 void DropUnscheduledPredecessor() { | |
57 DCHECK(unscheduled_predecessors_count_ > 0); | |
58 unscheduled_predecessors_count_--; | |
59 } | |
60 | |
61 Instruction* instruction() { return instr_; } | |
62 ZoneDeque<ScheduleGraphNode*>& successors() { return successors_; } | |
63 int latency() const { return latency_; } | |
64 | |
65 int total_latency() const { return total_latency_; } | |
66 void set_total_latency(int latency) { total_latency_ = latency; } | |
67 | |
68 int start_cycle() const { return start_cycle_; } | |
69 void set_start_cycle(int start_cycle) { start_cycle_ = start_cycle; } | |
70 | |
71 private: | |
72 Instruction* instr_; | |
73 ZoneDeque<ScheduleGraphNode*> successors_; | |
74 | |
75 // Number of unscheduled predecessors for this node. | |
76 int unscheduled_predecessors_count_; | |
77 | |
78 // Estimate of the instruction latency (the number of cycles it takes for | |
79 // instruction to complete). | |
80 int latency_; | |
81 | |
82 // The sum of all the latencies on the path from this node to the end of | |
83 // the graph (i.e. a node with no successor). | |
84 int total_latency_; | |
85 | |
86 // The scheduler keeps a nominal cycle count to keep track of when the | |
87 // result of an instruction is available. This field is updated by the | |
88 // scheduler to indicate when the value of all the operands of this | |
89 // instruction will be available. | |
90 int start_cycle_; | |
91 }; | |
92 | |
93 // Compare the two nodes and return true if node1 is a better candidate than | |
94 // node2 (i.e. node1 should be scheduled before node2). | |
95 bool CompareNodes(ScheduleGraphNode *node1, ScheduleGraphNode *node2) const; | |
96 | |
97 // Perform scheduling for the current block. | |
98 void ScheduleBlock(); | |
99 | |
100 // Return the scheduling properties of the given instruction. | |
101 int GetInstructionFlags(const Instruction* instr) const; | |
102 int GetTargetInstructionFlags(const Instruction* instr) const; | |
103 | |
104 // Return true if instr2 uses any value defined by instr1. | |
105 bool HasOperandDependency(const Instruction* instr1, | |
106 const Instruction* instr2) const; | |
107 | |
108 // Return true if the instruction is a basic block terminator. | |
109 bool IsBlockTerminator(const Instruction* instr) const; | |
110 | |
111 // Check whether the given instruction has side effects (e.g. function call, | |
112 // memory store). | |
113 bool HasSideEffect(const Instruction* instr) const { | |
114 return GetInstructionFlags(instr) & kHasSideEffect; | |
115 } | |
116 | |
117 // Return true if the instruction is a memory load. | |
118 bool IsLoadOperation(const Instruction* instr) const { | |
119 return GetInstructionFlags(instr) & kIsLoadOperation; | |
120 } | |
121 | |
122 // Identify nops used as a definition point for live-in registers at | |
123 // function entry. | |
124 bool IsFixedRegisterParameter(const Instruction* instr) const { | |
125 return (instr->arch_opcode() == kArchNop) && | |
126 (instr->OutputCount() == 1) && | |
127 (instr->OutputAt(0)->IsUnallocated()) && | |
128 UnallocatedOperand::cast(instr->OutputAt(0))->HasFixedRegisterPolicy(); | |
129 } | |
130 | |
131 void ComputeTotalLatencies(); | |
132 | |
133 static int GetInstructionLatency(const Instruction* instr); | |
134 | |
135 Zone* zone() { return zone_; } | |
136 InstructionSequence* sequence() { return sequence_; } | |
137 | |
138 Zone* zone_; | |
139 InstructionSequence* sequence_; | |
140 ZoneVector<ScheduleGraphNode*> graph_; | |
141 | |
142 // Last side effect instruction encountered while building the graph. | |
143 ScheduleGraphNode* last_side_effect_instr_; | |
144 | |
145 // Set of load instructions encountered since the last side effect instruction | |
146 // which will be added as predecessors of the next instruction with side | |
147 // effects. | |
148 ZoneVector<ScheduleGraphNode*> pending_loads_; | |
149 | |
150 // Live-in register markers are nop instructions which are emitted at the | |
151 // beginning of a basic block so that the register allocator will find a | |
152 // defining instruction for live-in values. They must not be moved. | |
153 // All these nops are chained together and added as a predecessor of every | |
154 // other instructions in the basic block. | |
155 ScheduleGraphNode* last_live_in_reg_marker_; | |
156 }; | |
157 | |
158 } // namespace compiler | |
159 } // namespace internal | |
160 } // namespace v8 | |
161 | |
162 #endif // V8_COMPILER_INSTRUCTION_SCHEDULER_H_ | |
OLD | NEW |