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