Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(80)

Unified Diff: src/compiler/instruction-scheduler.h

Issue 1375253002: [WIP][turbofan] Instruction scheduler for Turbofan. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: rebase the patch Created 5 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/compiler/instruction-codes.h ('k') | src/compiler/instruction-scheduler.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/instruction-scheduler.h
diff --git a/src/compiler/instruction-scheduler.h b/src/compiler/instruction-scheduler.h
new file mode 100644
index 0000000000000000000000000000000000000000..fafbe47908019115d95f2dabfb3aec3f73c80b1f
--- /dev/null
+++ b/src/compiler/instruction-scheduler.h
@@ -0,0 +1,162 @@
+// Copyright 2015 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef V8_COMPILER_INSTRUCTION_SCHEDULER_H_
+#define V8_COMPILER_INSTRUCTION_SCHEDULER_H_
+
+#include "src/compiler/instruction.h"
+#include "src/zone-containers.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+// A set of flags describing properties of the instructions so that the
+// scheduler is aware of dependencies between instructions.
+enum ArchOpcodeFlags {
+ kNoOpcodeFlags = 0,
+ kIsBlockTerminator = 1, // The instruction marks the end of a basic block
+ // e.g.: jump and return instructions.
+ kHasSideEffect = 2, // The instruction has some side effects (memory
+ // store, function call...)
+ kIsLoadOperation = 4, // The instruction is a memory load.
+};
+
+
+class InstructionScheduler final : public ZoneObject {
+ public:
+ InstructionScheduler(Zone* zone, InstructionSequence* sequence);
+
+ void StartBlock(RpoNumber rpo);
+ void EndBlock(RpoNumber rpo);
+
+ void AddInstruction(Instruction* instr);
+
+ static bool SchedulerSupported();
+
+ private:
+ // A scheduling graph node.
+ // Represent an instruction and their dependencies.
+ class ScheduleGraphNode: public ZoneObject {
+ public:
+ ScheduleGraphNode(Zone* zone, Instruction* instr);
+
+ // Mark the instruction represented by 'node' as a dependecy of this one.
+ // The current instruction will be registered as an unscheduled predecessor
+ // of 'node' (i.e. it must be scheduled before 'node').
+ void AddSuccessor(ScheduleGraphNode* node);
+
+ // Check if all the predecessors of this instruction have been scheduled.
+ bool HasUnscheduledPredecessor() {
+ return unscheduled_predecessors_count_ != 0;
+ }
+
+ // Record that we have scheduled one of the predecessors of this node.
+ void DropUnscheduledPredecessor() {
+ DCHECK(unscheduled_predecessors_count_ > 0);
+ unscheduled_predecessors_count_--;
+ }
+
+ Instruction* instruction() { return instr_; }
+ ZoneDeque<ScheduleGraphNode*>& successors() { return successors_; }
+ int latency() const { return latency_; }
+
+ int total_latency() const { return total_latency_; }
+ void set_total_latency(int latency) { total_latency_ = latency; }
+
+ int start_cycle() const { return start_cycle_; }
+ void set_start_cycle(int start_cycle) { start_cycle_ = start_cycle; }
+
+ private:
+ Instruction* instr_;
+ ZoneDeque<ScheduleGraphNode*> successors_;
+
+ // Number of unscheduled predecessors for this node.
+ int unscheduled_predecessors_count_;
+
+ // Estimate of the instruction latency (the number of cycles it takes for
+ // instruction to complete).
+ int latency_;
+
+ // The sum of all the latencies on the path from this node to the end of
+ // the graph (i.e. a node with no successor).
+ int total_latency_;
+
+ // The scheduler keeps a nominal cycle count to keep track of when the
+ // result of an instruction is available. This field is updated by the
+ // scheduler to indicate when the value of all the operands of this
+ // instruction will be available.
+ int start_cycle_;
+ };
+
+ // Compare the two nodes and return true if node1 is a better candidate than
+ // node2 (i.e. node1 should be scheduled before node2).
+ bool CompareNodes(ScheduleGraphNode *node1, ScheduleGraphNode *node2) const;
+
+ // Perform scheduling for the current block.
+ void ScheduleBlock();
+
+ // Return the scheduling properties of the given instruction.
+ int GetInstructionFlags(const Instruction* instr) const;
+ int GetTargetInstructionFlags(const Instruction* instr) const;
+
+ // Return true if instr2 uses any value defined by instr1.
+ bool HasOperandDependency(const Instruction* instr1,
+ const Instruction* instr2) const;
+
+ // Return true if the instruction is a basic block terminator.
+ bool IsBlockTerminator(const Instruction* instr) const;
+
+ // Check whether the given instruction has side effects (e.g. function call,
+ // memory store).
+ bool HasSideEffect(const Instruction* instr) const {
+ return GetInstructionFlags(instr) & kHasSideEffect;
+ }
+
+ // Return true if the instruction is a memory load.
+ bool IsLoadOperation(const Instruction* instr) const {
+ return GetInstructionFlags(instr) & kIsLoadOperation;
+ }
+
+ // Identify nops used as a definition point for live-in registers at
+ // function entry.
+ bool IsFixedRegisterParameter(const Instruction* instr) const {
+ return (instr->arch_opcode() == kArchNop) &&
+ (instr->OutputCount() == 1) &&
+ (instr->OutputAt(0)->IsUnallocated()) &&
+ UnallocatedOperand::cast(instr->OutputAt(0))->HasFixedRegisterPolicy();
+ }
+
+ void ComputeTotalLatencies();
+
+ static int GetInstructionLatency(const Instruction* instr);
+
+ Zone* zone() { return zone_; }
+ InstructionSequence* sequence() { return sequence_; }
+
+ Zone* zone_;
+ InstructionSequence* sequence_;
+ ZoneVector<ScheduleGraphNode*> graph_;
+
+ // Last side effect instruction encountered while building the graph.
+ ScheduleGraphNode* last_side_effect_instr_;
+
+ // Set of load instructions encountered since the last side effect instruction
+ // which will be added as predecessors of the next instruction with side
+ // effects.
+ ZoneVector<ScheduleGraphNode*> pending_loads_;
+
+ // Live-in register markers are nop instructions which are emitted at the
+ // beginning of a basic block so that the register allocator will find a
+ // defining instruction for live-in values. They must not be moved.
+ // All these nops are chained together and added as a predecessor of every
+ // other instructions in the basic block.
+ ScheduleGraphNode* last_live_in_reg_marker_;
+};
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
+
+#endif // V8_COMPILER_INSTRUCTION_SCHEDULER_H_
« no previous file with comments | « src/compiler/instruction-codes.h ('k') | src/compiler/instruction-scheduler.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698