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 #include "src/compiler/instruction-scheduler.h" | |
6 | |
7 #include "src/base/adapters.h" | |
8 | |
9 namespace v8 { | |
10 namespace internal { | |
11 namespace compiler { | |
12 | |
13 InstructionScheduler::ScheduleGraphNode::ScheduleGraphNode( | |
14 Zone* zone, | |
15 Instruction* instr) | |
16 : instr_(instr), | |
17 successors_(zone), | |
18 unscheduled_predecessors_count_(0), | |
19 latency_(GetInstructionLatency(instr)), | |
20 total_latency_(-1), | |
21 start_cycle_(-1) { | |
22 } | |
23 | |
24 | |
25 void InstructionScheduler::ScheduleGraphNode::AddSuccessor( | |
26 ScheduleGraphNode* node) { | |
27 successors_.push_back(node); | |
28 node->unscheduled_predecessors_count_++; | |
29 } | |
30 | |
31 | |
32 InstructionScheduler::InstructionScheduler(Zone* zone, | |
33 InstructionSequence* sequence) | |
34 : zone_(zone), | |
35 sequence_(sequence), | |
36 graph_(zone), | |
37 last_side_effect_instr_(nullptr), | |
38 pending_loads_(zone), | |
39 last_live_in_reg_marker_(nullptr) { | |
40 } | |
41 | |
42 | |
43 void InstructionScheduler::StartBlock(RpoNumber rpo) { | |
44 DCHECK(graph_.empty()); | |
45 DCHECK(last_side_effect_instr_ == nullptr); | |
46 DCHECK(pending_loads_.empty()); | |
47 DCHECK(last_live_in_reg_marker_ == nullptr); | |
48 sequence()->StartBlock(rpo); | |
49 } | |
50 | |
51 | |
52 void InstructionScheduler::EndBlock(RpoNumber rpo) { | |
53 ScheduleBlock(); | |
54 sequence()->EndBlock(rpo); | |
55 graph_.clear(); | |
56 last_side_effect_instr_ = nullptr; | |
57 pending_loads_.clear(); | |
58 last_live_in_reg_marker_ = nullptr; | |
59 } | |
60 | |
61 | |
62 void InstructionScheduler::AddInstruction(Instruction* instr) { | |
63 ScheduleGraphNode* new_node = new (zone()) ScheduleGraphNode(zone(), instr); | |
64 | |
65 if (IsBlockTerminator(instr)) { | |
66 // Make sure that basic block terminators are not moved by adding them | |
67 // as successor of every instruction. | |
68 for (auto node : graph_) { | |
69 node->AddSuccessor(new_node); | |
70 } | |
71 } else if (IsFixedRegisterParameter(instr)) { | |
72 if (last_live_in_reg_marker_ != nullptr) { | |
73 last_live_in_reg_marker_->AddSuccessor(new_node); | |
74 } | |
75 last_live_in_reg_marker_ = new_node; | |
76 } else { | |
77 if (last_live_in_reg_marker_ != nullptr) { | |
78 last_live_in_reg_marker_->AddSuccessor(new_node); | |
79 } | |
80 | |
81 // Instructions with side effects and memory operations can't be | |
82 // reordered with respect to each other. | |
83 if (HasSideEffect(instr)) { | |
84 if (last_side_effect_instr_ != nullptr) { | |
85 last_side_effect_instr_->AddSuccessor(new_node); | |
86 } | |
87 for (auto load : pending_loads_) { | |
88 load->AddSuccessor(new_node); | |
89 } | |
90 pending_loads_.clear(); | |
91 last_side_effect_instr_ = new_node; | |
92 } else if (IsLoadOperation(instr)) { | |
93 // Load operations can't be reordered with side effects instructions but | |
94 // independent loads can be reordered with respect to each other. | |
95 if (last_side_effect_instr_ != nullptr) { | |
96 last_side_effect_instr_->AddSuccessor(new_node); | |
97 } | |
98 pending_loads_.push_back(new_node); | |
99 } | |
100 | |
101 // Look for operand dependencies. | |
102 for (auto node : graph_) { | |
103 if (HasOperandDependency(node->instruction(), instr)) { | |
104 node->AddSuccessor(new_node); | |
105 } | |
106 } | |
107 } | |
108 | |
109 graph_.push_back(new_node); | |
110 } | |
111 | |
112 | |
113 bool InstructionScheduler::CompareNodes(ScheduleGraphNode *node1, | |
114 ScheduleGraphNode *node2) const { | |
115 return node1->total_latency() > node2->total_latency(); | |
116 } | |
117 | |
118 | |
119 void InstructionScheduler::ScheduleBlock() { | |
120 ZoneLinkedList<ScheduleGraphNode*> ready_list(zone()); | |
121 | |
122 // Compute total latencies so that we can schedule the critical path first. | |
123 ComputeTotalLatencies(); | |
124 | |
125 // Add nodes which don't have dependencies to the ready list. | |
126 for (auto node : graph_) { | |
127 if (!node->HasUnscheduledPredecessor()) { | |
128 ready_list.push_back(node); | |
129 } | |
130 } | |
131 | |
132 // Go through the ready list and schedule the instructions. | |
133 int cycle = 0; | |
134 while (!ready_list.empty()) { | |
135 auto candidate = ready_list.end(); | |
136 for (auto iterator = ready_list.begin(); iterator != ready_list.end(); | |
137 ++iterator) { | |
138 // Look for the best candidate to schedule. | |
139 // We only consider instructions that have all their operands ready and | |
140 // we try to schedule the critical path first (we look for the instruction | |
141 // with the highest latency on the path to reach the end of the graph). | |
142 if (cycle >= (*iterator)->start_cycle()) { | |
143 if ((candidate == ready_list.end()) || | |
144 CompareNodes(*iterator, *candidate)) { | |
145 candidate = iterator; | |
146 } | |
147 } | |
148 } | |
149 | |
150 if (candidate != ready_list.end()) { | |
151 sequence()->AddInstruction((*candidate)->instruction()); | |
152 | |
153 for (auto successor : (*candidate)->successors()) { | |
154 successor->DropUnscheduledPredecessor(); | |
155 successor->set_start_cycle( | |
156 std::max(successor->start_cycle(), | |
157 cycle + (*candidate)->latency())); | |
158 | |
159 if (!successor->HasUnscheduledPredecessor()) { | |
160 ready_list.push_back(successor); | |
161 } | |
162 } | |
163 | |
164 ready_list.erase(candidate); | |
165 } | |
166 | |
167 cycle++; | |
168 } | |
169 } | |
170 | |
171 | |
172 int InstructionScheduler::GetInstructionFlags(const Instruction* instr) const { | |
173 switch (instr->arch_opcode()) { | |
174 case kArchNop: | |
175 case kArchStackPointer: | |
176 case kArchFramePointer: | |
177 case kArchTruncateDoubleToI: | |
178 return kNoOpcodeFlags; | |
179 | |
180 case kArchPrepareCallCFunction: | |
181 case kArchPrepareTailCall: | |
182 case kArchCallCFunction: | |
183 case kArchCallCodeObject: | |
184 case kArchCallJSFunction: | |
185 case kArchLazyBailout: | |
186 return kHasSideEffect; | |
187 | |
188 case kArchTailCallCodeObject: | |
189 case kArchTailCallJSFunction: | |
190 return kHasSideEffect | kIsBlockTerminator; | |
191 | |
192 case kArchDeoptimize: | |
193 case kArchJmp: | |
194 case kArchLookupSwitch: | |
195 case kArchTableSwitch: | |
196 case kArchRet: | |
197 case kArchThrowTerminator: | |
198 return kIsBlockTerminator; | |
199 | |
200 case kCheckedLoadInt8: | |
201 case kCheckedLoadUint8: | |
202 case kCheckedLoadInt16: | |
203 case kCheckedLoadUint16: | |
204 case kCheckedLoadWord32: | |
205 case kCheckedLoadWord64: | |
206 case kCheckedLoadFloat32: | |
207 case kCheckedLoadFloat64: | |
208 return kIsLoadOperation; | |
209 | |
210 case kCheckedStoreWord8: | |
211 case kCheckedStoreWord16: | |
212 case kCheckedStoreWord32: | |
213 case kCheckedStoreWord64: | |
214 case kCheckedStoreFloat32: | |
215 case kCheckedStoreFloat64: | |
216 case kArchStoreWithWriteBarrier: | |
217 return kHasSideEffect; | |
218 | |
219 #define CASE(Name) case k##Name: | |
220 TARGET_ARCH_OPCODE_LIST(CASE) | |
221 #undef CASE | |
222 return GetTargetInstructionFlags(instr); | |
223 } | |
224 | |
225 UNREACHABLE(); | |
226 return kNoOpcodeFlags; | |
227 } | |
228 | |
229 | |
230 bool InstructionScheduler::HasOperandDependency( | |
231 const Instruction* instr1, const Instruction* instr2) const { | |
232 for (size_t i = 0; i < instr1->OutputCount(); ++i) { | |
233 for (size_t j = 0; j < instr2->InputCount(); ++j) { | |
234 const InstructionOperand* output = instr1->OutputAt(i); | |
235 const InstructionOperand* input = instr2->InputAt(j); | |
236 | |
237 if (output->IsUnallocated() && input->IsUnallocated() && | |
238 (UnallocatedOperand::cast(output)->virtual_register() == | |
239 UnallocatedOperand::cast(input)->virtual_register())) { | |
240 return true; | |
241 } | |
242 | |
243 if (output->IsConstant() && input->IsUnallocated() && | |
244 (ConstantOperand::cast(output)->virtual_register() == | |
245 UnallocatedOperand::cast(input)->virtual_register())) { | |
246 return true; | |
247 } | |
248 } | |
249 } | |
250 | |
251 // TODO(bafsa): Do we need to look for anti-dependencies/output-dependencies? | |
252 | |
253 return false; | |
254 } | |
255 | |
256 | |
257 bool InstructionScheduler::IsBlockTerminator(const Instruction* instr) const { | |
258 return ((GetInstructionFlags(instr) & kIsBlockTerminator) || | |
259 (instr->flags_mode() == kFlags_branch)); | |
260 } | |
261 | |
262 | |
263 void InstructionScheduler::ComputeTotalLatencies() { | |
264 for (auto node : base::Reversed(graph_)) { | |
265 int max_latency = 0; | |
266 | |
267 for (auto successor : node->successors()) { | |
268 DCHECK(successor->total_latency() != -1); | |
269 if (successor->total_latency() > max_latency) { | |
270 max_latency = successor->total_latency(); | |
271 } | |
272 } | |
273 | |
274 node->set_total_latency(max_latency + node->latency()); | |
275 } | |
276 } | |
277 | |
278 } // namespace compiler | |
279 } // namespace internal | |
280 } // namespace v8 | |
OLD | NEW |