| 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 |