| 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 |
|---|
Chromium Code Reviews
Issue 1526913002:
Revert of [WIP][turbofan] Instruction scheduler for Turbofan. (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master