From e53845d41cc82f681e04c9ff2c1894f42939a292 Mon Sep 17 00:00:00 2001 From: bmeurer Date: Wed, 7 Jan 2015 06:42:38 -0800 Subject: [PATCH] [turbofan] Cleanup Graph and related classes. - Move NodeMarker to its own file, and introduce a non templatized base class. - Cleanup the include hell. - Sanitize the Node construction methods now that we got rid of that GenericNode/GenericGraph stuff. - Protect against NodeId overflow in Graph. - Various minor cleanups. TEST=cctest,mjsunit,unittests Review URL: https://codereview.chromium.org/838783002 Cr-Commit-Position: refs/heads/master@{#25977} --- BUILD.gn | 2 + src/compiler/common-operator-reducer.cc | 1 + src/compiler/control-reducer.cc | 1 + src/compiler/graph-builder.h | 1 + src/compiler/graph-reducer.h | 7 +- src/compiler/graph.cc | 48 +++++++------ src/compiler/graph.h | 78 ++++++---------------- src/compiler/loop-analysis.cc | 4 +- src/compiler/node-marker.cc | 40 +++++++++++ src/compiler/node-marker.h | 62 +++++++++++++++++ src/compiler/node.cc | 18 +++-- src/compiler/node.h | 28 +++----- src/compiler/scheduler.cc | 2 +- src/compiler/simplified-operator-reducer.h | 1 + test/cctest/compiler/test-graph-reducer.cc | 5 ++ test/cctest/compiler/test-node-cache.cc | 10 +-- .../compiler/common-operator-reducer-unittest.cc | 1 + test/unittests/compiler/graph-reducer-unittest.cc | 1 + .../compiler/value-numbering-reducer-unittest.cc | 2 + tools/gyp/v8.gyp | 2 + 20 files changed, 202 insertions(+), 112 deletions(-) create mode 100644 src/compiler/node-marker.cc create mode 100644 src/compiler/node-marker.h diff --git a/BUILD.gn b/BUILD.gn index 6534eea..62da990 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -559,6 +559,8 @@ source_set("v8_base") { "src/compiler/node-aux-data.h", "src/compiler/node-cache.cc", "src/compiler/node-cache.h", + "src/compiler/node-marker.cc", + "src/compiler/node-marker.h", "src/compiler/node-matchers.h", "src/compiler/node-properties-inl.h", "src/compiler/node-properties.h", diff --git a/src/compiler/common-operator-reducer.cc b/src/compiler/common-operator-reducer.cc index cf597ea..c3cbcde 100644 --- a/src/compiler/common-operator-reducer.cc +++ b/src/compiler/common-operator-reducer.cc @@ -5,6 +5,7 @@ #include "src/compiler/common-operator-reducer.h" #include "src/compiler/common-operator.h" +#include "src/compiler/node.h" namespace v8 { namespace internal { diff --git a/src/compiler/control-reducer.cc b/src/compiler/control-reducer.cc index eef8a49..bc619bc 100644 --- a/src/compiler/control-reducer.cc +++ b/src/compiler/control-reducer.cc @@ -6,6 +6,7 @@ #include "src/compiler/control-reducer.h" #include "src/compiler/graph.h" #include "src/compiler/js-graph.h" +#include "src/compiler/node-marker.h" #include "src/compiler/node-matchers.h" #include "src/compiler/node-properties-inl.h" #include "src/zone-containers.h" diff --git a/src/compiler/graph-builder.h b/src/compiler/graph-builder.h index d88b125..241e6cf 100644 --- a/src/compiler/graph-builder.h +++ b/src/compiler/graph-builder.h @@ -10,6 +10,7 @@ #include "src/allocation.h" #include "src/compiler/common-operator.h" #include "src/compiler/graph.h" +#include "src/compiler/node.h" #include "src/unique.h" namespace v8 { diff --git a/src/compiler/graph-reducer.h b/src/compiler/graph-reducer.h index 09a650c..5c612ba 100644 --- a/src/compiler/graph-reducer.h +++ b/src/compiler/graph-reducer.h @@ -5,13 +5,18 @@ #ifndef V8_COMPILER_GRAPH_REDUCER_H_ #define V8_COMPILER_GRAPH_REDUCER_H_ -#include "src/compiler/graph.h" +#include "src/compiler/node-marker.h" #include "src/zone-containers.h" namespace v8 { namespace internal { namespace compiler { +// Forward declarations. +class Graph; +class Node; + + // Represents the result of trying to reduce a node in the graph. class Reduction FINAL { public: diff --git a/src/compiler/graph.cc b/src/compiler/graph.cc index 995046b..1650bdf 100644 --- a/src/compiler/graph.cc +++ b/src/compiler/graph.cc @@ -4,14 +4,10 @@ #include "src/compiler/graph.h" -#include "src/compiler/common-operator.h" -#include "src/compiler/graph-inl.h" +#include + +#include "src/base/bits.h" #include "src/compiler/node.h" -#include "src/compiler/node-aux-data-inl.h" -#include "src/compiler/node-properties.h" -#include "src/compiler/node-properties-inl.h" -#include "src/compiler/opcodes.h" -#include "src/compiler/operator-properties.h" namespace v8 { namespace internal { @@ -19,30 +15,44 @@ namespace compiler { Graph::Graph(Zone* zone) : zone_(zone), - start_(NULL), - end_(NULL), + start_(nullptr), + end_(nullptr), mark_max_(0), next_node_id_(0), decorators_(zone) {} void Graph::Decorate(Node* node) { - for (ZoneVector::iterator i = decorators_.begin(); - i != decorators_.end(); ++i) { - (*i)->Decorate(node); - } + for (auto const decorator : decorators_) decorator->Decorate(node); +} + + +void Graph::AddDecorator(GraphDecorator* decorator) { + decorators_.push_back(decorator); +} + + +void Graph::RemoveDecorator(GraphDecorator* decorator) { + auto const it = std::find(decorators_.begin(), decorators_.end(), decorator); + DCHECK(it != decorators_.end()); + decorators_.erase(it); } Node* Graph::NewNode(const Operator* op, int input_count, Node** inputs, bool incomplete) { DCHECK_LE(op->ValueInputCount(), input_count); - Node* result = Node::New(this, input_count, inputs, incomplete); - result->Initialize(op); - if (!incomplete) { - Decorate(result); - } - return result; + Node* const node = + Node::New(zone(), NextNodeId(), op, input_count, inputs, incomplete); + if (!incomplete) Decorate(node); + return node; +} + + +NodeId Graph::NextNodeId() { + NodeId const id = next_node_id_; + CHECK(!base::bits::SignedAddOverflow32(id, 1, &next_node_id_)); + return id; } } // namespace compiler diff --git a/src/compiler/graph.h b/src/compiler/graph.h index d619da2..e825b7e 100644 --- a/src/compiler/graph.h +++ b/src/compiler/graph.h @@ -5,12 +5,8 @@ #ifndef V8_COMPILER_GRAPH_H_ #define V8_COMPILER_GRAPH_H_ -#include -#include - -#include "src/compiler/node.h" -#include "src/compiler/node-aux-data.h" -#include "src/compiler/source-position.h" +#include "src/zone.h" +#include "src/zone-containers.h" namespace v8 { namespace internal { @@ -18,6 +14,19 @@ namespace compiler { // Forward declarations. class GraphDecorator; +class Node; +class Operator; + + +// Marks are used during traversal of the graph to distinguish states of nodes. +// Each node has a mark which is a monotonically increasing integer, and a +// {NodeMarker} has a range of values that indicate states of a node. +typedef uint32_t Mark; + + +// NodeIds are identifying numbers for nodes that can be used to index auxiliary +// out-of-line data associated with each node. +typedef int32_t NodeId; class Graph : public ZoneObject { @@ -71,27 +80,18 @@ class Graph : public ZoneObject { void SetStart(Node* start) { start_ = start; } void SetEnd(Node* end) { end_ = end; } - NodeId NextNodeID() { return next_node_id_++; } - NodeId NodeCount() const { return next_node_id_; } + int NodeCount() const { return next_node_id_; } void Decorate(Node* node); - - void AddDecorator(GraphDecorator* decorator) { - decorators_.push_back(decorator); - } - - void RemoveDecorator(GraphDecorator* decorator) { - ZoneVector::iterator it = - std::find(decorators_.begin(), decorators_.end(), decorator); - DCHECK(it != decorators_.end()); - decorators_.erase(it, it + 1); - } + void AddDecorator(GraphDecorator* decorator); + void RemoveDecorator(GraphDecorator* decorator); private: - template - friend class NodeMarker; + friend class NodeMarkerBase; - Zone* zone_; + inline NodeId NextNodeId(); + + Zone* const zone_; Node* start_; Node* end_; Mark mark_max_; @@ -102,40 +102,6 @@ class Graph : public ZoneObject { }; -// A NodeMarker uses monotonically increasing marks to assign local "states" -// to nodes. Only one NodeMarker per graph is valid at a given time. -template -class NodeMarker BASE_EMBEDDED { - public: - NodeMarker(Graph* graph, uint32_t num_states) - : mark_min_(graph->mark_max_), mark_max_(graph->mark_max_ += num_states) { - DCHECK(num_states > 0); // user error! - DCHECK(mark_max_ > mark_min_); // check for wraparound. - } - - State Get(Node* node) { - Mark mark = node->mark(); - if (mark < mark_min_) { - mark = mark_min_; - node->set_mark(mark_min_); - } - DCHECK_LT(mark, mark_max_); - return static_cast(mark - mark_min_); - } - - void Set(Node* node, State state) { - Mark local = static_cast(state); - DCHECK(local < (mark_max_ - mark_min_)); - DCHECK_LT(node->mark(), mark_max_); - node->set_mark(local + mark_min_); - } - - private: - Mark mark_min_; - Mark mark_max_; -}; - - // A graph decorator can be used to add behavior to the creation of nodes // in a graph. class GraphDecorator : public ZoneObject { diff --git a/src/compiler/loop-analysis.cc b/src/compiler/loop-analysis.cc index e1b703e..01b9659 100644 --- a/src/compiler/loop-analysis.cc +++ b/src/compiler/loop-analysis.cc @@ -2,9 +2,11 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -#include "src/compiler/graph.h" #include "src/compiler/loop-analysis.h" + +#include "src/compiler/graph.h" #include "src/compiler/node.h" +#include "src/compiler/node-marker.h" #include "src/compiler/node-properties-inl.h" #include "src/zone.h" diff --git a/src/compiler/node-marker.cc b/src/compiler/node-marker.cc new file mode 100644 index 0000000..4bf12f9 --- /dev/null +++ b/src/compiler/node-marker.cc @@ -0,0 +1,40 @@ +// 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. + +#include "src/compiler/node-marker.h" + +#include "src/compiler/graph.h" +#include "src/compiler/node.h" + +namespace v8 { +namespace internal { +namespace compiler { + +NodeMarkerBase::NodeMarkerBase(Graph* graph, uint32_t num_states) + : mark_min_(graph->mark_max_), mark_max_(graph->mark_max_ += num_states) { + DCHECK(num_states > 0); // user error! + DCHECK(mark_max_ > mark_min_); // check for wraparound. +} + + +Mark NodeMarkerBase::Get(Node* node) { + Mark mark = node->mark(); + if (mark < mark_min_) { + mark = mark_min_; + node->set_mark(mark_min_); + } + DCHECK_LT(mark, mark_max_); + return mark - mark_min_; +} + + +void NodeMarkerBase::Set(Node* node, Mark mark) { + DCHECK_LT(mark, mark_max_ - mark_min_); + DCHECK_LT(node->mark(), mark_max_); + node->set_mark(mark + mark_min_); +} + +} // namespace compiler +} // namespace internal +} // namespace v8 diff --git a/src/compiler/node-marker.h b/src/compiler/node-marker.h new file mode 100644 index 0000000..837c92c --- /dev/null +++ b/src/compiler/node-marker.h @@ -0,0 +1,62 @@ +// 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_NODE_MARKER_H_ +#define V8_COMPILER_NODE_MARKER_H_ + +#include "src/base/macros.h" + +namespace v8 { +namespace internal { +namespace compiler { + +// Forward declarations. +class Graph; +class Node; + + +// Marks are used during traversal of the graph to distinguish states of nodes. +// Each node has a mark which is a monotonically increasing integer, and a +// {NodeMarker} has a range of values that indicate states of a node. +typedef uint32_t Mark; + + +// Base class for templatized NodeMarkers. +class NodeMarkerBase { + public: + NodeMarkerBase(Graph* graph, uint32_t num_states); + + Mark Get(Node* node); + void Set(Node* node, Mark mark); + + private: + Mark mark_min_; + Mark mark_max_; + + DISALLOW_COPY_AND_ASSIGN(NodeMarkerBase); +}; + + +// A NodeMarker uses monotonically increasing marks to assign local "states" +// to nodes. Only one NodeMarker per graph is valid at a given time. +template +class NodeMarker : public NodeMarkerBase { + public: + NodeMarker(Graph* graph, uint32_t num_states) + : NodeMarkerBase(graph, num_states) {} + + State Get(Node* node) { + return static_cast(NodeMarkerBase::Get(node)); + } + + void Set(Node* node, State state) { + NodeMarkerBase::Set(node, static_cast(state)); + } +}; + +} // namespace compiler +} // namespace internal +} // namespace v8 + +#endif // V8_COMPILER_NODE_MARKER_H_ diff --git a/src/compiler/node.cc b/src/compiler/node.cc index 8f44c24..b86b0bd 100644 --- a/src/compiler/node.cc +++ b/src/compiler/node.cc @@ -4,15 +4,15 @@ #include "src/compiler/node.h" -#include "src/compiler/graph.h" -#include "src/zone.h" - namespace v8 { namespace internal { namespace compiler { -Node::Node(NodeId id, int input_count, int reserved_input_count) - : id_(id), +Node::Node(NodeId id, const Operator* op, int input_count, + int reserved_input_count) + : op_(op), + mark_(0), + id_(id), bit_field_(InputCountField::encode(input_count) | ReservedInputCountField::encode(reserved_input_count) | HasAppendableInputsField::encode(false)), @@ -22,17 +22,15 @@ Node::Node(NodeId id, int input_count, int reserved_input_count) } -Node* Node::New(Graph* graph, int input_count, Node** inputs, - bool has_extensible_inputs) { +Node* Node::New(Zone* zone, NodeId id, const Operator* op, int input_count, + Node** inputs, bool has_extensible_inputs) { size_t node_size = sizeof(Node); int reserve_input_count = has_extensible_inputs ? kDefaultReservedInputs : 0; size_t inputs_size = (input_count + reserve_input_count) * sizeof(Input); size_t uses_size = input_count * sizeof(Use); int size = static_cast(node_size + inputs_size + uses_size); - Zone* zone = graph->zone(); void* buffer = zone->New(size); - Node* result = - new (buffer) Node(graph->NextNodeID(), input_count, reserve_input_count); + Node* result = new (buffer) Node(id, op, input_count, reserve_input_count); Input* input = reinterpret_cast(reinterpret_cast(buffer) + node_size); Use* use = diff --git a/src/compiler/node.h b/src/compiler/node.h index 2295b7b..9d3a2b0 100644 --- a/src/compiler/node.h +++ b/src/compiler/node.h @@ -6,14 +6,11 @@ #define V8_COMPILER_NODE_H_ #include -#include #include -#include "src/v8.h" - #include "src/compiler/opcodes.h" #include "src/compiler/operator.h" -#include "src/types.h" +#include "src/types-inl.h" #include "src/zone.h" #include "src/zone-allocator.h" #include "src/zone-containers.h" @@ -32,9 +29,11 @@ class Graph; // {NodeMarker} has a range of values that indicate states of a node. typedef uint32_t Mark; + // NodeIds are identifying numbers for nodes that can be used to index auxiliary // out-of-line data associated with each node. -typedef int NodeId; +typedef int32_t NodeId; + // A Node is the basic primitive of graphs. Nodes are chained together by // input/use chains but by default otherwise contain only an identifying number @@ -47,11 +46,6 @@ typedef int NodeId; // by the Node's id. class Node FINAL { public: - void Initialize(const Operator* op) { - set_op(op); - set_mark(0); - } - bool IsDead() const { return InputCount() > 0 && InputAt(0) == NULL; } void Kill(); @@ -144,8 +138,8 @@ class Node FINAL { bool OwnedBy(Node* owner) const; - static Node* New(Graph* graph, int input_count, Node** inputs, - bool has_extensible_inputs); + static Node* New(Zone* zone, NodeId id, const Operator* op, int input_count, + Node** inputs, bool has_extensible_inputs); protected: friend class Graph; @@ -183,13 +177,13 @@ class Node FINAL { void* operator new(size_t, void* location) { return location; } private: - inline Node(NodeId id, int input_count, int reserve_input_count); + inline Node(NodeId id, const Operator* op, int input_count, + int reserve_input_count); typedef ZoneDeque InputDeque; + friend class NodeMarkerBase; friend class NodeProperties; - template - friend class NodeMarker; // Only NodeProperties should manipulate the bounds. Bounds bounds() { return bounds_; } @@ -441,10 +435,6 @@ class Node::Uses::iterator { std::ostream& operator<<(std::ostream& os, const Node& n); -typedef std::set, zone_allocator > NodeSet; -typedef NodeSet::iterator NodeSetIter; -typedef NodeSet::reverse_iterator NodeSetRIter; - typedef ZoneDeque NodeDeque; typedef ZoneVector NodeVector; diff --git a/src/compiler/scheduler.cc b/src/compiler/scheduler.cc index f12c631..c2d043f 100644 --- a/src/compiler/scheduler.cc +++ b/src/compiler/scheduler.cc @@ -12,7 +12,7 @@ #include "src/compiler/graph.h" #include "src/compiler/graph-inl.h" #include "src/compiler/node.h" -#include "src/compiler/node-properties.h" +#include "src/compiler/node-marker.h" #include "src/compiler/node-properties-inl.h" namespace v8 { diff --git a/src/compiler/simplified-operator-reducer.h b/src/compiler/simplified-operator-reducer.h index 1e565b8..32a7bcc 100644 --- a/src/compiler/simplified-operator-reducer.h +++ b/src/compiler/simplified-operator-reducer.h @@ -12,6 +12,7 @@ namespace v8 { namespace internal { // Forward declarations. +class Factory; class Heap; namespace compiler { diff --git a/test/cctest/compiler/test-graph-reducer.cc b/test/cctest/compiler/test-graph-reducer.cc index 70b57b9..d425c90 100644 --- a/test/cctest/compiler/test-graph-reducer.cc +++ b/test/cctest/compiler/test-graph-reducer.cc @@ -2,10 +2,14 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. +#include + #include "src/v8.h" #include "graph-tester.h" #include "src/compiler/graph-reducer.h" +#include "src/compiler/node.h" +#include "src/compiler/operator.h" using namespace v8::internal; using namespace v8::internal::compiler; @@ -181,6 +185,7 @@ class AB2Sorter : public Reducer { // Simply records the nodes visited. class ReducerRecorder : public Reducer { public: + typedef std::set, zone_allocator> NodeSet; explicit ReducerRecorder(Zone* zone) : set(NodeSet::key_compare(), NodeSet::allocator_type(zone)) {} virtual Reduction Reduce(Node* node) { diff --git a/test/cctest/compiler/test-node-cache.cc b/test/cctest/compiler/test-node-cache.cc index a48adb9..835c028 100644 --- a/test/cctest/compiler/test-node-cache.cc +++ b/test/cctest/compiler/test-node-cache.cc @@ -115,7 +115,7 @@ TEST(Int64Constant_hits) { } -static bool Contains(NodeVector* nodes, Node* n) { +static bool Contains(ZoneVector* nodes, Node* n) { for (size_t i = 0; i < nodes->size(); i++) { if (nodes->at(i) == n) return true; } @@ -135,11 +135,11 @@ TEST(NodeCache_GetCachedNodes_int32) { int32_t k = constants[i]; Node** pos = cache.Find(graph.zone(), k); if (*pos != NULL) { - NodeVector nodes(graph.zone()); + ZoneVector nodes(graph.zone()); cache.GetCachedNodes(&nodes); CHECK(Contains(&nodes, *pos)); } else { - NodeVector nodes(graph.zone()); + ZoneVector nodes(graph.zone()); Node* n = graph.NewNode(common.Int32Constant(k)); *pos = n; cache.GetCachedNodes(&nodes); @@ -161,11 +161,11 @@ TEST(NodeCache_GetCachedNodes_int64) { int64_t k = constants[i]; Node** pos = cache.Find(graph.zone(), k); if (*pos != NULL) { - NodeVector nodes(graph.zone()); + ZoneVector nodes(graph.zone()); cache.GetCachedNodes(&nodes); CHECK(Contains(&nodes, *pos)); } else { - NodeVector nodes(graph.zone()); + ZoneVector nodes(graph.zone()); Node* n = graph.NewNode(common.Int64Constant(k)); *pos = n; cache.GetCachedNodes(&nodes); diff --git a/test/unittests/compiler/common-operator-reducer-unittest.cc b/test/unittests/compiler/common-operator-reducer-unittest.cc index c713815..1f6044b 100644 --- a/test/unittests/compiler/common-operator-reducer-unittest.cc +++ b/test/unittests/compiler/common-operator-reducer-unittest.cc @@ -5,6 +5,7 @@ #include "src/compiler/common-operator.h" #include "src/compiler/common-operator-reducer.h" #include "src/compiler/machine-type.h" +#include "src/compiler/operator.h" #include "test/unittests/compiler/graph-unittest.h" namespace v8 { diff --git a/test/unittests/compiler/graph-reducer-unittest.cc b/test/unittests/compiler/graph-reducer-unittest.cc index dbdd4bb..c3fc4ce 100644 --- a/test/unittests/compiler/graph-reducer-unittest.cc +++ b/test/unittests/compiler/graph-reducer-unittest.cc @@ -4,6 +4,7 @@ #include "src/compiler/graph.h" #include "src/compiler/graph-reducer.h" +#include "src/compiler/node.h" #include "src/compiler/operator.h" #include "test/unittests/test-utils.h" #include "testing/gmock/include/gmock/gmock.h" diff --git a/test/unittests/compiler/value-numbering-reducer-unittest.cc b/test/unittests/compiler/value-numbering-reducer-unittest.cc index b6be0bf..52b792f 100644 --- a/test/unittests/compiler/value-numbering-reducer-unittest.cc +++ b/test/unittests/compiler/value-numbering-reducer-unittest.cc @@ -5,6 +5,8 @@ #include #include "src/compiler/graph.h" +#include "src/compiler/node.h" +#include "src/compiler/operator.h" #include "src/compiler/value-numbering-reducer.h" #include "test/unittests/test-utils.h" diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 696434d..14b2acb 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -486,6 +486,8 @@ '../../src/compiler/node-aux-data.h', '../../src/compiler/node-cache.cc', '../../src/compiler/node-cache.h', + '../../src/compiler/node-marker.cc', + '../../src/compiler/node-marker.h', '../../src/compiler/node-matchers.h', '../../src/compiler/node-properties-inl.h', '../../src/compiler/node-properties.h', -- 2.7.4