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 #ifndef V8_COMPILER_INSTRUCTION_SCHEDULER_H_ |
| 6 #define V8_COMPILER_INSTRUCTION_SCHEDULER_H_ |
| 7 |
| 8 #include "src/compiler/instruction.h" |
| 9 #include "src/zone-containers.h" |
| 10 |
| 11 namespace v8 { |
| 12 namespace internal { |
| 13 namespace compiler { |
| 14 |
| 15 // A set of flags describing properties of the instructions so that the |
| 16 // scheduler is aware of dependencies between instructions. |
| 17 enum ArchOpcodeFlags { |
| 18 kNoOpcodeFlags = 0, |
| 19 kIsBlockTerminator = 1, // The instruction marks the end of a basic block |
| 20 // e.g.: jump and return instructions. |
| 21 kHasSideEffect = 2, // The instruction has some side effects (memory |
| 22 // store, function call...) |
| 23 kIsLoadOperation = 4, // The instruction is a memory load. |
| 24 }; |
| 25 |
| 26 |
| 27 class InstructionScheduler final : public ZoneObject { |
| 28 public: |
| 29 InstructionScheduler(Zone* zone, InstructionSequence* sequence); |
| 30 |
| 31 void StartBlock(RpoNumber rpo); |
| 32 void EndBlock(RpoNumber rpo); |
| 33 |
| 34 void AddInstruction(Instruction* instr); |
| 35 |
| 36 static bool SchedulerSupported(); |
| 37 |
| 38 private: |
| 39 // A scheduling graph node. |
| 40 // Represent an instruction and their dependencies. |
| 41 class ScheduleGraphNode: public ZoneObject { |
| 42 public: |
| 43 ScheduleGraphNode(Zone* zone, Instruction* instr); |
| 44 |
| 45 // Mark the instruction represented by 'node' as a dependecy of this one. |
| 46 // The current instruction will be registered as an unscheduled predecessor |
| 47 // of 'node' (i.e. it must be scheduled before 'node'). |
| 48 void AddSuccessor(ScheduleGraphNode* node); |
| 49 |
| 50 // Check if all the predecessors of this instruction have been scheduled. |
| 51 bool HasUnscheduledPredecessor() { |
| 52 return unscheduled_predecessors_count_ != 0; |
| 53 } |
| 54 |
| 55 // Record that we have scheduled one of the predecessors of this node. |
| 56 void DropUnscheduledPredecessor() { |
| 57 DCHECK(unscheduled_predecessors_count_ > 0); |
| 58 unscheduled_predecessors_count_--; |
| 59 } |
| 60 |
| 61 Instruction* instruction() { return instr_; } |
| 62 ZoneDeque<ScheduleGraphNode*>& successors() { return successors_; } |
| 63 int latency() const { return latency_; } |
| 64 |
| 65 int total_latency() const { return total_latency_; } |
| 66 void set_total_latency(int latency) { total_latency_ = latency; } |
| 67 |
| 68 int start_cycle() const { return start_cycle_; } |
| 69 void set_start_cycle(int start_cycle) { start_cycle_ = start_cycle; } |
| 70 |
| 71 private: |
| 72 Instruction* instr_; |
| 73 ZoneDeque<ScheduleGraphNode*> successors_; |
| 74 |
| 75 // Number of unscheduled predecessors for this node. |
| 76 int unscheduled_predecessors_count_; |
| 77 |
| 78 // Estimate of the instruction latency (the number of cycles it takes for |
| 79 // instruction to complete). |
| 80 int latency_; |
| 81 |
| 82 // The sum of all the latencies on the path from this node to the end of |
| 83 // the graph (i.e. a node with no successor). |
| 84 int total_latency_; |
| 85 |
| 86 // The scheduler keeps a nominal cycle count to keep track of when the |
| 87 // result of an instruction is available. This field is updated by the |
| 88 // scheduler to indicate when the value of all the operands of this |
| 89 // instruction will be available. |
| 90 int start_cycle_; |
| 91 }; |
| 92 |
| 93 // Compare the two nodes and return true if node1 is a better candidate than |
| 94 // node2 (i.e. node1 should be scheduled before node2). |
| 95 bool CompareNodes(ScheduleGraphNode *node1, ScheduleGraphNode *node2) const; |
| 96 |
| 97 // Perform scheduling for the current block. |
| 98 void ScheduleBlock(); |
| 99 |
| 100 // Return the scheduling properties of the given instruction. |
| 101 int GetInstructionFlags(const Instruction* instr) const; |
| 102 int GetTargetInstructionFlags(const Instruction* instr) const; |
| 103 |
| 104 // Return true if instr2 uses any value defined by instr1. |
| 105 bool HasOperandDependency(const Instruction* instr1, |
| 106 const Instruction* instr2) const; |
| 107 |
| 108 // Return true if the instruction is a basic block terminator. |
| 109 bool IsBlockTerminator(const Instruction* instr) const; |
| 110 |
| 111 // Check whether the given instruction has side effects (e.g. function call, |
| 112 // memory store). |
| 113 bool HasSideEffect(const Instruction* instr) const { |
| 114 return GetInstructionFlags(instr) & kHasSideEffect; |
| 115 } |
| 116 |
| 117 // Return true if the instruction is a memory load. |
| 118 bool IsLoadOperation(const Instruction* instr) const { |
| 119 return GetInstructionFlags(instr) & kIsLoadOperation; |
| 120 } |
| 121 |
| 122 // Identify nops used as a definition point for live-in registers at |
| 123 // function entry. |
| 124 bool IsFixedRegisterParameter(const Instruction* instr) const { |
| 125 return (instr->arch_opcode() == kArchNop) && |
| 126 (instr->OutputCount() == 1) && |
| 127 (instr->OutputAt(0)->IsUnallocated()) && |
| 128 UnallocatedOperand::cast(instr->OutputAt(0))->HasFixedRegisterPolicy(); |
| 129 } |
| 130 |
| 131 void ComputeTotalLatencies(); |
| 132 |
| 133 static int GetInstructionLatency(const Instruction* instr); |
| 134 |
| 135 Zone* zone() { return zone_; } |
| 136 InstructionSequence* sequence() { return sequence_; } |
| 137 |
| 138 Zone* zone_; |
| 139 InstructionSequence* sequence_; |
| 140 ZoneVector<ScheduleGraphNode*> graph_; |
| 141 |
| 142 // Last side effect instruction encountered while building the graph. |
| 143 ScheduleGraphNode* last_side_effect_instr_; |
| 144 |
| 145 // Set of load instructions encountered since the last side effect instruction |
| 146 // which will be added as predecessors of the next instruction with side |
| 147 // effects. |
| 148 ZoneVector<ScheduleGraphNode*> pending_loads_; |
| 149 |
| 150 // Live-in register markers are nop instructions which are emitted at the |
| 151 // beginning of a basic block so that the register allocator will find a |
| 152 // defining instruction for live-in values. They must not be moved. |
| 153 // All these nops are chained together and added as a predecessor of every |
| 154 // other instructions in the basic block. |
| 155 ScheduleGraphNode* last_live_in_reg_marker_; |
| 156 }; |
| 157 |
| 158 } // namespace compiler |
| 159 } // namespace internal |
| 160 } // namespace v8 |
| 161 |
| 162 #endif // V8_COMPILER_INSTRUCTION_SCHEDULER_H_ |
OLD | NEW |