OLD | NEW |
1 // Copyright 2015 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/instruction-scheduler.h" | 5 #include "src/compiler/instruction-scheduler.h" |
6 | 6 |
7 #include "src/base/adapters.h" | 7 #include "src/base/adapters.h" |
8 #include "src/base/utils/random-number-generator.h" | 8 #include "src/base/utils/random-number-generator.h" |
9 | 9 |
10 namespace v8 { | 10 namespace v8 { |
(...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
108 last_live_in_reg_marker_ = nullptr; | 108 last_live_in_reg_marker_ = nullptr; |
109 } | 109 } |
110 | 110 |
111 | 111 |
112 void InstructionScheduler::AddInstruction(Instruction* instr) { | 112 void InstructionScheduler::AddInstruction(Instruction* instr) { |
113 ScheduleGraphNode* new_node = new (zone()) ScheduleGraphNode(zone(), instr); | 113 ScheduleGraphNode* new_node = new (zone()) ScheduleGraphNode(zone(), instr); |
114 | 114 |
115 if (IsBlockTerminator(instr)) { | 115 if (IsBlockTerminator(instr)) { |
116 // Make sure that basic block terminators are not moved by adding them | 116 // Make sure that basic block terminators are not moved by adding them |
117 // as successor of every instruction. | 117 // as successor of every instruction. |
118 for (auto node : graph_) { | 118 for (ScheduleGraphNode* node : graph_) { |
119 node->AddSuccessor(new_node); | 119 node->AddSuccessor(new_node); |
120 } | 120 } |
121 } else if (IsFixedRegisterParameter(instr)) { | 121 } else if (IsFixedRegisterParameter(instr)) { |
122 if (last_live_in_reg_marker_ != nullptr) { | 122 if (last_live_in_reg_marker_ != nullptr) { |
123 last_live_in_reg_marker_->AddSuccessor(new_node); | 123 last_live_in_reg_marker_->AddSuccessor(new_node); |
124 } | 124 } |
125 last_live_in_reg_marker_ = new_node; | 125 last_live_in_reg_marker_ = new_node; |
126 } else { | 126 } else { |
127 if (last_live_in_reg_marker_ != nullptr) { | 127 if (last_live_in_reg_marker_ != nullptr) { |
128 last_live_in_reg_marker_->AddSuccessor(new_node); | 128 last_live_in_reg_marker_->AddSuccessor(new_node); |
129 } | 129 } |
130 | 130 |
131 // Instructions with side effects and memory operations can't be | 131 // Instructions with side effects and memory operations can't be |
132 // reordered with respect to each other. | 132 // reordered with respect to each other. |
133 if (HasSideEffect(instr)) { | 133 if (HasSideEffect(instr)) { |
134 if (last_side_effect_instr_ != nullptr) { | 134 if (last_side_effect_instr_ != nullptr) { |
135 last_side_effect_instr_->AddSuccessor(new_node); | 135 last_side_effect_instr_->AddSuccessor(new_node); |
136 } | 136 } |
137 for (auto load : pending_loads_) { | 137 for (ScheduleGraphNode* load : pending_loads_) { |
138 load->AddSuccessor(new_node); | 138 load->AddSuccessor(new_node); |
139 } | 139 } |
140 pending_loads_.clear(); | 140 pending_loads_.clear(); |
141 last_side_effect_instr_ = new_node; | 141 last_side_effect_instr_ = new_node; |
142 } else if (IsLoadOperation(instr)) { | 142 } else if (IsLoadOperation(instr)) { |
143 // Load operations can't be reordered with side effects instructions but | 143 // Load operations can't be reordered with side effects instructions but |
144 // independent loads can be reordered with respect to each other. | 144 // independent loads can be reordered with respect to each other. |
145 if (last_side_effect_instr_ != nullptr) { | 145 if (last_side_effect_instr_ != nullptr) { |
146 last_side_effect_instr_->AddSuccessor(new_node); | 146 last_side_effect_instr_->AddSuccessor(new_node); |
147 } | 147 } |
148 pending_loads_.push_back(new_node); | 148 pending_loads_.push_back(new_node); |
149 } | 149 } |
150 | 150 |
151 // Look for operand dependencies. | 151 // Look for operand dependencies. |
152 for (auto node : graph_) { | 152 for (ScheduleGraphNode* node : graph_) { |
153 if (HasOperandDependency(node->instruction(), instr)) { | 153 if (HasOperandDependency(node->instruction(), instr)) { |
154 node->AddSuccessor(new_node); | 154 node->AddSuccessor(new_node); |
155 } | 155 } |
156 } | 156 } |
157 } | 157 } |
158 | 158 |
159 graph_.push_back(new_node); | 159 graph_.push_back(new_node); |
160 } | 160 } |
161 | 161 |
162 | 162 |
163 template <typename QueueType> | 163 template <typename QueueType> |
164 void InstructionScheduler::ScheduleBlock() { | 164 void InstructionScheduler::ScheduleBlock() { |
165 QueueType ready_list(this); | 165 QueueType ready_list(this); |
166 | 166 |
167 // Compute total latencies so that we can schedule the critical path first. | 167 // Compute total latencies so that we can schedule the critical path first. |
168 ComputeTotalLatencies(); | 168 ComputeTotalLatencies(); |
169 | 169 |
170 // Add nodes which don't have dependencies to the ready list. | 170 // Add nodes which don't have dependencies to the ready list. |
171 for (auto node : graph_) { | 171 for (ScheduleGraphNode* node : graph_) { |
172 if (!node->HasUnscheduledPredecessor()) { | 172 if (!node->HasUnscheduledPredecessor()) { |
173 ready_list.AddNode(node); | 173 ready_list.AddNode(node); |
174 } | 174 } |
175 } | 175 } |
176 | 176 |
177 // Go through the ready list and schedule the instructions. | 177 // Go through the ready list and schedule the instructions. |
178 int cycle = 0; | 178 int cycle = 0; |
179 while (!ready_list.IsEmpty()) { | 179 while (!ready_list.IsEmpty()) { |
180 auto candidate = ready_list.PopBestCandidate(cycle); | 180 ScheduleGraphNode* candidate = ready_list.PopBestCandidate(cycle); |
181 | 181 |
182 if (candidate != nullptr) { | 182 if (candidate != nullptr) { |
183 sequence()->AddInstruction(candidate->instruction()); | 183 sequence()->AddInstruction(candidate->instruction()); |
184 | 184 |
185 for (auto successor : candidate->successors()) { | 185 for (ScheduleGraphNode* successor : candidate->successors()) { |
186 successor->DropUnscheduledPredecessor(); | 186 successor->DropUnscheduledPredecessor(); |
187 successor->set_start_cycle( | 187 successor->set_start_cycle( |
188 std::max(successor->start_cycle(), | 188 std::max(successor->start_cycle(), |
189 cycle + candidate->latency())); | 189 cycle + candidate->latency())); |
190 | 190 |
191 if (!successor->HasUnscheduledPredecessor()) { | 191 if (!successor->HasUnscheduledPredecessor()) { |
192 ready_list.AddNode(successor); | 192 ready_list.AddNode(successor); |
193 } | 193 } |
194 } | 194 } |
195 } | 195 } |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
289 } | 289 } |
290 | 290 |
291 | 291 |
292 bool InstructionScheduler::IsBlockTerminator(const Instruction* instr) const { | 292 bool InstructionScheduler::IsBlockTerminator(const Instruction* instr) const { |
293 return ((GetInstructionFlags(instr) & kIsBlockTerminator) || | 293 return ((GetInstructionFlags(instr) & kIsBlockTerminator) || |
294 (instr->flags_mode() == kFlags_branch)); | 294 (instr->flags_mode() == kFlags_branch)); |
295 } | 295 } |
296 | 296 |
297 | 297 |
298 void InstructionScheduler::ComputeTotalLatencies() { | 298 void InstructionScheduler::ComputeTotalLatencies() { |
299 for (auto node : base::Reversed(graph_)) { | 299 for (ScheduleGraphNode* node : base::Reversed(graph_)) { |
300 int max_latency = 0; | 300 int max_latency = 0; |
301 | 301 |
302 for (auto successor : node->successors()) { | 302 for (ScheduleGraphNode* successor : node->successors()) { |
303 DCHECK(successor->total_latency() != -1); | 303 DCHECK(successor->total_latency() != -1); |
304 if (successor->total_latency() > max_latency) { | 304 if (successor->total_latency() > max_latency) { |
305 max_latency = successor->total_latency(); | 305 max_latency = successor->total_latency(); |
306 } | 306 } |
307 } | 307 } |
308 | 308 |
309 node->set_total_latency(max_latency + node->latency()); | 309 node->set_total_latency(max_latency + node->latency()); |
310 } | 310 } |
311 } | 311 } |
312 | 312 |
313 } // namespace compiler | 313 } // namespace compiler |
314 } // namespace internal | 314 } // namespace internal |
315 } // namespace v8 | 315 } // namespace v8 |
OLD | NEW |