Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 |