From 5bba6b20e638142648f59d96132b772d26843c8f Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Mon, 3 Nov 2014 17:41:53 +0000 Subject: [PATCH] Make visualizer robust to graphs with NULL inputs. R=mstarzinger@chromium.org, jarin@chromium.org BUG= Review URL: https://codereview.chromium.org/652263002 Cr-Commit-Position: refs/heads/master@{#25084} git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@25084 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/compiler/generic-graph.h | 4 +- src/compiler/graph-visualizer.cc | 343 ++++++++++++++------------ test/cctest/cctest.gyp | 1 + test/cctest/compiler/test-graph-visualizer.cc | 92 +++++++ 4 files changed, 281 insertions(+), 159 deletions(-) create mode 100644 test/cctest/compiler/test-graph-visualizer.cc diff --git a/src/compiler/generic-graph.h b/src/compiler/generic-graph.h index a555456..11f6aa2 100644 --- a/src/compiler/generic-graph.h +++ b/src/compiler/generic-graph.h @@ -34,8 +34,8 @@ class GenericGraph : public GenericGraphBase { explicit GenericGraph(Zone* zone) : GenericGraphBase(zone), start_(NULL), end_(NULL) {} - V* start() { return start_; } - V* end() { return end_; } + V* start() const { return start_; } + V* end() const { return end_; } void SetStart(V* start) { start_ = start; } void SetEnd(V* end) { end_ = end; } diff --git a/src/compiler/graph-visualizer.cc b/src/compiler/graph-visualizer.cc index e0cf8f0..707a695 100644 --- a/src/compiler/graph-visualizer.cc +++ b/src/compiler/graph-visualizer.cc @@ -8,7 +8,6 @@ #include #include "src/code-stubs.h" -#include "src/compiler/generic-algorithm.h" #include "src/compiler/generic-node.h" #include "src/compiler/generic-node-inl.h" #include "src/compiler/graph.h" @@ -27,8 +26,61 @@ namespace v8 { namespace internal { namespace compiler { +static int SafeId(Node* node) { return node == NULL ? -1 : node->id(); } + #define DEAD_COLOR "#999999" +class AllNodes { + public: + enum State { kDead, kGray, kLive }; + + AllNodes(Zone* local_zone, const Graph* graph) + : state(graph->NodeCount(), kDead, local_zone), + live(local_zone), + gray(local_zone) { + Node* end = graph->end(); + state[end->id()] = kLive; + live.push_back(end); + // Find all live nodes reachable from end. + for (size_t i = 0; i < live.size(); i++) { + for (Node* const input : live[i]->inputs()) { + if (input == NULL) { + // TODO(titzer): print a warning. + continue; + } + if (input->id() >= graph->NodeCount()) { + // TODO(titzer): print a warning. + continue; + } + if (state[input->id()] != kLive) { + live.push_back(input); + state[input->id()] = kLive; + } + } + } + + // Find all nodes that are not reachable from end that use live nodes. + for (size_t i = 0; i < live.size(); i++) { + for (Node* const use : live[i]->uses()) { + if (state[use->id()] == kDead) { + gray.push_back(use); + state[use->id()] = kGray; + } + } + } + } + + bool IsLive(Node* node) { + return node != NULL && node->id() < static_cast(state.size()) && + state[node->id()] == kLive; + } + + ZoneVector state; + NodeVector live; + NodeVector gray; +}; + + class Escaped { public: explicit Escaped(const std::ostringstream& os, @@ -56,104 +108,104 @@ class Escaped { const char* const escaped_chars_; }; -class JSONGraphNodeWriter : public NullNodeVisitor { +class JSONGraphNodeWriter { public: - JSONGraphNodeWriter(std::ostream& os, Zone* zone, - const Graph* graph) // NOLINT - : os_(os), - graph_(graph), - first_node_(true) {} + JSONGraphNodeWriter(std::ostream& os, Zone* zone, const Graph* graph) + : os_(os), all_(zone, graph), first_node_(true) {} - void Print() { const_cast(graph_)->VisitNodeInputsFromEnd(this); } + void Print() { + for (Node* const node : all_.live) PrintNode(node); + } - void Pre(Node* node); + void PrintNode(Node* node) { + if (first_node_) { + first_node_ = false; + } else { + os_ << ","; + } + std::ostringstream label; + label << *node->op(); + os_ << "{\"id\":" << SafeId(node) << ",\"label\":\"" << Escaped(label, "\"") + << "\""; + IrOpcode::Value opcode = node->opcode(); + if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) { + os_ << ",\"rankInputs\":[0," << NodeProperties::FirstControlIndex(node) + << "]"; + os_ << ",\"rankWithInput\":[" << NodeProperties::FirstControlIndex(node) + << "]"; + } else if (opcode == IrOpcode::kIfTrue || opcode == IrOpcode::kIfFalse || + opcode == IrOpcode::kLoop) { + os_ << ",\"rankInputs\":[" << NodeProperties::FirstControlIndex(node) + << "]"; + } + if (opcode == IrOpcode::kBranch) { + os_ << ",\"rankInputs\":[0]"; + } + os_ << ",\"opcode\":\"" << IrOpcode::Mnemonic(node->opcode()) << "\""; + os_ << ",\"control\":" << (NodeProperties::IsControl(node) ? "true" + : "false"); + os_ << "}"; + } private: std::ostream& os_; - const Graph* const graph_; + AllNodes all_; bool first_node_; DISALLOW_COPY_AND_ASSIGN(JSONGraphNodeWriter); }; -void JSONGraphNodeWriter::Pre(Node* node) { - if (first_node_) { - first_node_ = false; - } else { - os_ << ","; - } - std::ostringstream label; - label << *node->op(); - os_ << "{\"id\":" << node->id() << ",\"label\":\"" << Escaped(label, "\"") - << "\""; - IrOpcode::Value opcode = node->opcode(); - if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) { - os_ << ",\"rankInputs\":[0," << NodeProperties::FirstControlIndex(node) - << "]"; - os_ << ",\"rankWithInput\":[" << NodeProperties::FirstControlIndex(node) - << "]"; - } else if (opcode == IrOpcode::kIfTrue || opcode == IrOpcode::kIfFalse || - opcode == IrOpcode::kLoop) { - os_ << ",\"rankInputs\":[" << NodeProperties::FirstControlIndex(node) - << "]"; - } - if (opcode == IrOpcode::kBranch) { - os_ << ",\"rankInputs\":[0]"; - } - os_ << ",\"opcode\":\"" << IrOpcode::Mnemonic(node->opcode()) << "\""; - os_ << ",\"control\":" << (NodeProperties::IsControl(node) ? "true" - : "false"); - os_ << "}"; -} - - -class JSONGraphEdgeWriter : public NullNodeVisitor { +class JSONGraphEdgeWriter { public: - JSONGraphEdgeWriter(std::ostream& os, Zone* zone, - const Graph* graph) // NOLINT - : os_(os), - graph_(graph), - first_edge_(true) {} + JSONGraphEdgeWriter(std::ostream& os, Zone* zone, const Graph* graph) + : os_(os), all_(zone, graph), first_edge_(true) {} - void Print() { const_cast(graph_)->VisitNodeInputsFromEnd(this); } + void Print() { + for (Node* const node : all_.live) PrintEdges(node); + } - void PreEdge(Node* from, int index, Node* to); + void PrintEdges(Node* node) { + for (int i = 0; i < node->InputCount(); i++) { + Node* input = node->InputAt(i); + if (input == NULL) continue; + PrintEdge(node, i, input); + } + } + + void PrintEdge(Node* from, int index, Node* to) { + if (first_edge_) { + first_edge_ = false; + } else { + os_ << ","; + } + const char* edge_type = NULL; + if (index < NodeProperties::FirstValueIndex(from)) { + edge_type = "unknown"; + } else if (index < NodeProperties::FirstContextIndex(from)) { + edge_type = "value"; + } else if (index < NodeProperties::FirstFrameStateIndex(from)) { + edge_type = "context"; + } else if (index < NodeProperties::FirstEffectIndex(from)) { + edge_type = "frame-state"; + } else if (index < NodeProperties::FirstControlIndex(from)) { + edge_type = "effect"; + } else { + edge_type = "control"; + } + os_ << "{\"source\":" << SafeId(to) << ",\"target\":" << SafeId(from) + << ",\"index\":" << index << ",\"type\":\"" << edge_type << "\"}"; + } private: std::ostream& os_; - const Graph* const graph_; + AllNodes all_; bool first_edge_; DISALLOW_COPY_AND_ASSIGN(JSONGraphEdgeWriter); }; -void JSONGraphEdgeWriter::PreEdge(Node* from, int index, Node* to) { - if (first_edge_) { - first_edge_ = false; - } else { - os_ << ","; - } - const char* edge_type = NULL; - if (index < NodeProperties::FirstValueIndex(from)) { - edge_type = "unknown"; - } else if (index < NodeProperties::FirstContextIndex(from)) { - edge_type = "value"; - } else if (index < NodeProperties::FirstFrameStateIndex(from)) { - edge_type = "context"; - } else if (index < NodeProperties::FirstEffectIndex(from)) { - edge_type = "frame-state"; - } else if (index < NodeProperties::FirstControlIndex(from)) { - edge_type = "effect"; - } else { - edge_type = "control"; - } - os_ << "{\"source\":" << to->id() << ",\"target\":" << from->id() - << ",\"index\":" << index << ",\"type\":\"" << edge_type << "\"}"; -} - - std::ostream& operator<<(std::ostream& os, const AsJSON& ad) { Zone tmp_zone(ad.graph.zone()->isolate()); os << "{\"nodes\":["; @@ -165,22 +217,19 @@ std::ostream& operator<<(std::ostream& os, const AsJSON& ad) { } -class GraphVisualizer : public NullNodeVisitor { +class GraphVisualizer { public: GraphVisualizer(std::ostream& os, Zone* zone, const Graph* graph); // NOLINT void Print(); - void Pre(Node* node); + void PrintNode(Node* node, bool gray); private: - void AnnotateNode(Node* node); void PrintEdge(Node::Edge edge); Zone* zone_; - NodeSet all_nodes_; - NodeSet white_nodes_; - bool use_to_def_; + AllNodes all_; std::ostream& os_; const Graph* const graph_; @@ -193,48 +242,22 @@ static Node* GetControlCluster(Node* node) { return node; } else if (node->op()->ControlInputCount() == 1) { Node* control = NodeProperties::GetControlInput(node, 0); - return OperatorProperties::IsBasicBlockBegin(control->op()) ? control - : NULL; + return control != NULL && + OperatorProperties::IsBasicBlockBegin(control->op()) + ? control + : NULL; } else { return NULL; } } -void GraphVisualizer::Pre(Node* node) { - if (all_nodes_.count(node) == 0) { - Node* control_cluster = GetControlCluster(node); - if (control_cluster != NULL) { - os_ << " subgraph cluster_BasicBlock" << control_cluster->id() << " {\n"; - } - os_ << " ID" << node->id() << " [\n"; - AnnotateNode(node); - os_ << " ]\n"; - if (control_cluster != NULL) os_ << " }\n"; - all_nodes_.insert(node); - if (use_to_def_) white_nodes_.insert(node); - } -} - - -static bool IsLikelyBackEdge(Node* from, int index, Node* to) { - if (from->opcode() == IrOpcode::kPhi || - from->opcode() == IrOpcode::kEffectPhi) { - Node* control = NodeProperties::GetControlInput(from, 0); - return control->opcode() != IrOpcode::kMerge && control != to && index != 0; - } else if (from->opcode() == IrOpcode::kLoop) { - return index != 0; - } else { - return false; - } -} - - -void GraphVisualizer::AnnotateNode(Node* node) { - if (!use_to_def_) { - os_ << " style=\"filled\"\n" - << " fillcolor=\"" DEAD_COLOR "\"\n"; +void GraphVisualizer::PrintNode(Node* node, bool gray) { + Node* control_cluster = GetControlCluster(node); + if (control_cluster != NULL) { + os_ << " subgraph cluster_BasicBlock" << control_cluster->id() << " {\n"; } + os_ << " ID" << SafeId(node) << " [\n"; os_ << " shape=\"record\"\n"; switch (node->opcode()) { @@ -253,30 +276,35 @@ void GraphVisualizer::AnnotateNode(Node* node) { break; } + if (gray) { + os_ << " style=\"filled\"\n" + << " fillcolor=\"" DEAD_COLOR "\"\n"; + } + std::ostringstream label; label << *node->op(); - os_ << " label=\"{{#" << node->id() << ":" << Escaped(label); + os_ << " label=\"{{#" << SafeId(node) << ":" << Escaped(label); InputIter i = node->inputs().begin(); for (int j = node->op()->ValueInputCount(); j > 0; ++i, j--) { - os_ << "|#" << (*i)->id(); + os_ << "|#" << SafeId(*i); } for (int j = OperatorProperties::GetContextInputCount(node->op()); j > 0; ++i, j--) { - os_ << "|X #" << (*i)->id(); + os_ << "|X #" << SafeId(*i); } for (int j = OperatorProperties::GetFrameStateInputCount(node->op()); j > 0; ++i, j--) { - os_ << "|F #" << (*i)->id(); + os_ << "|F #" << SafeId(*i); } for (int j = node->op()->EffectInputCount(); j > 0; ++i, j--) { - os_ << "|E #" << (*i)->id(); + os_ << "|E #" << SafeId(*i); } - if (!use_to_def_ || OperatorProperties::IsBasicBlockBegin(node->op()) || + if (OperatorProperties::IsBasicBlockBegin(node->op()) || GetControlCluster(node) == NULL) { for (int j = node->op()->ControlInputCount(); j > 0; ++i, j--) { - os_ << "|C #" << (*i)->id(); + os_ << "|C #" << SafeId(*i); } } os_ << "}"; @@ -290,6 +318,23 @@ void GraphVisualizer::AnnotateNode(Node* node) { os_ << "|" << Escaped(upper) << "|" << Escaped(lower); } os_ << "}\"\n"; + + os_ << " ]\n"; + if (control_cluster != NULL) os_ << " }\n"; +} + + +static bool IsLikelyBackEdge(Node* from, int index, Node* to) { + if (from->opcode() == IrOpcode::kPhi || + from->opcode() == IrOpcode::kEffectPhi) { + Node* control = NodeProperties::GetControlInput(from, 0); + return control != NULL && control->opcode() != IrOpcode::kMerge && + control != to && index != 0; + } else if (from->opcode() == IrOpcode::kLoop) { + return index != 0; + } else { + return false; + } } @@ -297,21 +342,23 @@ void GraphVisualizer::PrintEdge(Node::Edge edge) { Node* from = edge.from(); int index = edge.index(); Node* to = edge.to(); + + if (!all_.IsLive(to)) return; // skip inputs that point to dead or NULL. + bool unconstrained = IsLikelyBackEdge(from, index, to); - os_ << " ID" << from->id(); - if (all_nodes_.count(to) == 0) { - os_ << ":I" << index << ":n -> DEAD_INPUT"; - } else if (OperatorProperties::IsBasicBlockBegin(from->op()) || - GetControlCluster(from) == NULL || - (from->op()->ControlInputCount() > 0 && - NodeProperties::GetControlInput(from) != to)) { - os_ << ":I" << index << ":n -> ID" << to->id() << ":s" + os_ << " ID" << SafeId(from); + + if (OperatorProperties::IsBasicBlockBegin(from->op()) || + GetControlCluster(from) == NULL || + (from->op()->ControlInputCount() > 0 && + NodeProperties::GetControlInput(from) != to)) { + os_ << ":I" << index << ":n -> ID" << SafeId(to) << ":s" << "[" << (unconstrained ? "constraint=false, " : "") << (NodeProperties::IsControlEdge(edge) ? "style=bold, " : "") << (NodeProperties::IsEffectEdge(edge) ? "style=dotted, " : "") << (NodeProperties::IsContextEdge(edge) ? "style=dashed, " : "") << "]"; } else { - os_ << " -> ID" << to->id() << ":s [color=transparent, " + os_ << " -> ID" << SafeId(to) << ":s [color=transparent, " << (unconstrained ? "constraint=false, " : "") << (NodeProperties::IsControlEdge(edge) ? "style=dashed, " : "") << "]"; } @@ -330,29 +377,13 @@ void GraphVisualizer::Print() { << " \n"; // Make sure all nodes have been output before writing out the edges. - use_to_def_ = true; - // TODO(svenpanne) Remove the need for the const_casts. - const_cast(graph_)->VisitNodeInputsFromEnd(this); - white_nodes_.insert(const_cast(graph_)->start()); - - // Visit all uses of white nodes. - use_to_def_ = false; - GenericGraphVisit::Visit >( - const_cast(graph_), zone_, white_nodes_.begin(), - white_nodes_.end(), this); - - os_ << " DEAD_INPUT [\n" - << " style=\"filled\" \n" - << " fillcolor=\"" DEAD_COLOR "\"\n" - << " ]\n" - << "\n"; + for (Node* const node : all_.live) PrintNode(node, false); + for (Node* const node : all_.gray) PrintNode(node, true); // With all the nodes written, add the edges. - for (NodeSetIter i = all_nodes_.begin(); i != all_nodes_.end(); ++i) { - Node::Inputs inputs = (*i)->inputs(); - for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end(); - ++iter) { - PrintEdge(iter.edge()); + for (Node* const node : all_.live) { + for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) { + PrintEdge(i.edge()); } } os_ << "}\n"; @@ -362,9 +393,7 @@ void GraphVisualizer::Print() { GraphVisualizer::GraphVisualizer(std::ostream& os, Zone* zone, const Graph* graph) // NOLINT : zone_(zone), - all_nodes_(NodeSet::key_compare(), NodeSet::allocator_type(zone)), - white_nodes_(NodeSet::key_compare(), NodeSet::allocator_type(zone)), - use_to_def_(true), + all_(zone, graph), os_(os), graph_(graph) {} @@ -485,7 +514,7 @@ void GraphC1Visualizer::PrintCompilation(const CompilationInfo* info) { } -void GraphC1Visualizer::PrintNodeId(Node* n) { os_ << "n" << n->id(); } +void GraphC1Visualizer::PrintNodeId(Node* n) { os_ << "n" << SafeId(n); } void GraphC1Visualizer::PrintNode(Node* n) { diff --git a/test/cctest/cctest.gyp b/test/cctest/cctest.gyp index d762c45..5e7ab99 100644 --- a/test/cctest/cctest.gyp +++ b/test/cctest/cctest.gyp @@ -60,6 +60,7 @@ 'compiler/test-control-reducer.cc', 'compiler/test-gap-resolver.cc', 'compiler/test-graph-reducer.cc', + 'compiler/test-graph-visualizer.cc', 'compiler/test-instruction.cc', 'compiler/test-js-context-specialization.cc', 'compiler/test-js-constant-cache.cc', diff --git a/test/cctest/compiler/test-graph-visualizer.cc b/test/cctest/compiler/test-graph-visualizer.cc new file mode 100644 index 0000000..9d394bb --- /dev/null +++ b/test/cctest/compiler/test-graph-visualizer.cc @@ -0,0 +1,92 @@ +// 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/v8.h" +#include "test/cctest/cctest.h" + +#include "src/compiler/common-operator.h" +#include "src/compiler/generic-node-inl.h" +#include "src/compiler/generic-node.h" +#include "src/compiler/graph.h" +#include "src/compiler/graph-visualizer.h" +#include "src/compiler/js-operator.h" +#include "src/compiler/machine-operator.h" +#include "src/compiler/node.h" +#include "src/compiler/operator.h" +#include "src/compiler/schedule.h" +#include "src/compiler/scheduler.h" +#include "src/compiler/verifier.h" + +using namespace v8::internal; +using namespace v8::internal::compiler; + +TEST(NodeWithNullInputReachableFromEnd) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + + Node* start = graph.NewNode(common.Start(0)); + graph.SetStart(start); + Node* k = graph.NewNode(common.Int32Constant(0)); + Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 1), k, start); + phi->ReplaceInput(0, NULL); + graph.SetEnd(phi); + + OFStream os(stdout); + os << AsDOT(graph); + os << AsJSON(graph); +} + + +TEST(NodeWithNullControlReachableFromEnd) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + + Node* start = graph.NewNode(common.Start(0)); + graph.SetStart(start); + Node* k = graph.NewNode(common.Int32Constant(0)); + Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 1), k, start); + phi->ReplaceInput(1, NULL); + graph.SetEnd(phi); + + OFStream os(stdout); + os << AsDOT(graph); + os << AsJSON(graph); +} + + +TEST(NodeWithNullInputReachableFromStart) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + + Node* start = graph.NewNode(common.Start(0)); + graph.SetStart(start); + Node* k = graph.NewNode(common.Int32Constant(0)); + Node* phi = graph.NewNode(common.Phi(kMachAnyTagged, 1), k, start); + phi->ReplaceInput(0, NULL); + graph.SetEnd(start); + + OFStream os(stdout); + os << AsDOT(graph); + os << AsJSON(graph); +} + + +TEST(NodeWithNullControlReachableFromStart) { + HandleAndZoneScope scope; + Graph graph(scope.main_zone()); + CommonOperatorBuilder common(scope.main_zone()); + + Node* start = graph.NewNode(common.Start(0)); + graph.SetStart(start); + Node* merge = graph.NewNode(common.Merge(2), start, start); + merge->ReplaceInput(1, NULL); + graph.SetEnd(merge); + + OFStream os(stdout); + os << AsDOT(graph); + os << AsJSON(graph); +} -- 2.7.4