[WIP][turbofan] Instruction scheduler for Turbofan.

src/compiler/instruction-scheduler.h

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..8b401107b1ca5f0b645cad7e762faeff610956c9
--- /dev/null
+++ b/src/compiler/instruction-scheduler.h
@@ -0,0 +1,117 @@
+// 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 {
+
+class InstructionScheduler final : public ZoneObject {
+ public:
+  InstructionScheduler(Zone* zone, InstructionSequence* sequence);
+
+  void StartBlock(RpoNumber rpo);
+  void EndBlock(RpoNumber rpo);
+
+  void AddInstruction(Instruction* instr);
+
+ private:
+  // A scheduling graph node.
+  // Represent an instruction and their dependencies.
+  class ScheduleGraphNode: public ZoneObject {
+   public:
+    ScheduleGraphNode(Zone* zone, Instruction* instr);
+
+    // Add an edge between two nodes in the scheduling graph.
+    // Edges are directed and an edge from A -> B means that instruction A must
+    // be scheduled before B.

[Jarin, 2015/10/26 15:12:35]

You might want to say that it means A is a dependency of B. (And possibly also
explain that dependencies of N are unscheduled predessors of N because the
terminology is a bit confusing here.)

Alternatively, you might avoid the term "Dependency" altogether and call it
"UnscheduledPredecessor".

[baptiste.afsa1, 2015/10/27 16:00:24]

Done.

Good idea. Using the term UnscheduledPredecessor does make things clearer.

+    void AddSuccessor(ScheduleGraphNode* node);
+
+    bool HasDependency() { return dependency_count_ != 0; }
+
+    // Record that we have scheduled one of the dependencies of the current
+    // node.
+    void DropDependency() {
+      DCHECK(dependency_count_ > 0);
+      dependency_count_--;
+    }
+
+    Instruction* instruction() { return instr_; }
+    ZoneVector<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_;
+    ZoneVector<ScheduleGraphNode*> successors_;

[Jarin, 2015/10/26 15:12:35]

I think it is better to use ZoneDeque here.

[baptiste.afsa1, 2015/10/27 16:00:24]

Done.

+    int dependency_count_;  // Number of dependencies for a given node.
+
+    // Estimate of the instruction latency (the number of cycles it takes for
+    // instruction to complete).
+    int latency_;
+
+    // The sum of all the latencies from a node to the root of the graph.

[Jarin, 2015/10/26 15:12:35]

What is the "root of the graph" here? From the code it looks like the root is
the end of the graph. Please, clarify the comment.

[baptiste.afsa1, 2015/10/27 16:00:24]

Done.

+    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 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 instruction_flags_[instr->arch_opcode()] & kHasSideEffect;
+  }
+
+  // Return true if the instruction is a memory load.
+  bool IsLoadOperation(const Instruction* instr) const {
+    return instruction_flags_[instr->arch_opcode()] & kIsLoadOperation;
+  }
+
+  void ComputeTotalLatency(ScheduleGraphNode* node);
+
+  static int GetInstructionLatency(const Instruction* instr);
+
+  Zone* zone() { return zone_; }
+  InstructionSequence* sequence() { return sequence_; }
+
+  static const int instruction_flags_[];
+
+  Zone* zone_;
+  InstructionSequence* sequence_;
+  ZoneVector<ScheduleGraphNode*> graph_;
+};
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_INSTRUCTION_SCHEDULER_H_