Implement representation selection as part of SimplifiedLowering. Representation selection also req…

src/compiler/node-sketch.cc

Index: src/compiler/node-sketch.cc
diff --git a/src/compiler/node-sketch.cc b/src/compiler/node-sketch.cc
new file mode 100644
index 0000000000000000000000000000000000000000..66eb0a0f3b033b586c6b33a08ad5db9a5c30c62a
--- /dev/null
+++ b/src/compiler/node-sketch.cc
@@ -0,0 +1,147 @@
+// Copyright 2014 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.
+
+#include "src/compiler/opcodes.h"
+#include "src/compiler/operator.h"
+#include "src/zone.h"
+#include "src/zone-allocator.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+//==={ Node }===================================================================
+// Represents a node in the graph. Every node has 0 or more outputs and 0 or
+// more inputs. Edges go between inputs and outputs and not between nodes.
+class Node {
+ public:
+  // Represents the different kinds of edges in the graph.
+  enum EdgeKind { kValue, kEffect, kControl };
+
+  class Output;
+  //==={ Input }================================================================
+  // Represents an input to a node. Every input has an edge kind and an index.
+  // An input can be connected to at most one output at a time, and the edge
+  // kind between the input and the output must always match.
+  class Input {
+   public:
+    // Get the owning node of this input. Note: not the owner of the
+    // output to which this input is connected.
+    Node* node();
+
+    // Get the index of this input relative to all the inputs for
+    // this node.
+    int index() { return static_cast<int>(tag_ >> 2); }
+
+    // Get the edge kind of this input.
+    EdgeKind kind() { return static_cast<EdgeKind>(tag_ & 3); }
+
+    // Get the target output to which this input is connected.
+    Output* target() { return target_; }

[rossberg, 2014/08/07 14:00:45]

Isn't this rather a source than a target? The data is flowing from that output
to this input.

+
+    // Connect this input to the given output.
+    void Connect(Output* out) {
+      if (out == target_) return;  // Redundant.

[rossberg, 2014/08/07 14:00:45]

Hm, when would you willingly connect the same edge twice?

+      if (out == NULL) {
+        if (target_ != NULL) target_->RemoveUse(this);
+        target_ = NULL;
+      } else {
+        DCHECK_EQ(kind(), out->kind());
+        target_->RemoveUse(this);
+        target_ = out;
+        target_->AddUse(this);
+      }
+    }
+
+   private:
+    int32_t tag_;     // both the index and the edge kind.
+    Output* target_;  // the target output to which this input is connected.
+  };
+
+  //==={ Output }===============================================================
+  // Represents an output from a node. Every output has an edge kind and an
+  // index. Many inputs may be connected to this output, and they are recorded
+  // in an internal use list.
+  class Output {
+   public:
+    // Get the owning node of this output.
+    Node* node() { return reinterpret_cast<Node*>(this + index()); }
+
+    // Get the edge kind of this output.
+    EdgeKind kind() { return static_cast<EdgeKind>(tag_ & 3); }
+
+    // Get the index of this output.
+    int index() { return tag_ & 0x4 ? tag_ >> 3 : 0; }
+
+    // Replace uses of this output with {that}.
+    void ReplaceUses(Output* that);
+
+   private:
+    int32_t tag_;  // both the index and the edge kind; if output 0, stores
+                   // the node id.
+    void* uses;    // pointer to either the single {Input} using this or an
+                   // out-of-line array of inputs that use this output.
+
+    friend class Input;
+    friend class Node;
+
+    void RemoveUse(Input* input);
+    void AddUse(Input* input);
+  };
+
+  //==={ Node public API }======================================================
+
+  // Get the unique id of this node.
+  int id() { return output0_.tag_ >> 3; }  // id of node is stored in output0.
+
+  // Get the output of this node at the given index.
+  Output* OutputAt(int index) { return (&output0_) - index; }
+
+  // Get the input of this node at the given index.
+  Input* InputAt(int index) { return &inputs_[index]; }
+
+  // Get the operator associated with this node.
+  Operator* op() { return op_; }
+
+  // Get the opcode of this node (from the operator).
+  IrOpcode::Value opcode() {
+    return static_cast<IrOpcode::Value>(op_->opcode());
+  }
+
+ private:
+  Output output0_;  // The first output of this node.
+  Operator* op_;    // operator of this node.
+  Input* inputs_;   // inputs to this node.
+};
+
+
+// Graphs are made of nodes.
+class Graph {
+ public:
+  // Get the count of nodes created in this graph so far.
+  int NodeCount() { return node_count_; }
+
+  // Create a new node in this graph and connect its inputs to the targets.
+  Node* NewNode(Operator* op, Node::Output** targets, int count);
+
+  // Connect the input of the node at {index} to the output {out}.
+  void ConnectInputAt(Node* node, int index, Node::Output* out) {
+    node->InputAt(index)->Connect(out);
+  }
+
+  // Remove all but {count} inputs from this node.
+  void TrimInputs(Node* node, int count);
+
+  // Append a new input at the given node and connect it to {out}.
+  void AppendInput(Node* node, Node::Output* out);
+
+ private:
+  Zone* zone_;
+  Node* start_;
+  Node* end_;
+  int node_count_;
+};
+}
+}
+}  // namespace v8::internal::compiler