src/v8/src/compiler/graph-visualizer.cc

   1 // Copyright 2013 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/graph-visualizer.h"
   6
   7 #include "src/compiler/generic-algorithm.h"
   8 #include "src/compiler/generic-node.h"
   9 #include "src/compiler/generic-node-inl.h"
  10 #include "src/compiler/graph.h"
  11 #include "src/compiler/graph-inl.h"
  12 #include "src/compiler/node.h"
  13 #include "src/compiler/node-properties.h"
  14 #include "src/compiler/node-properties-inl.h"
  15 #include "src/compiler/opcodes.h"
  16 #include "src/compiler/operator.h"
  17 #include "src/ostreams.h"
  18
  19 namespace v8 {
  20 namespace internal {
  21 namespace compiler {
  22
  23 #define DEAD_COLOR "#999999"
  24
  25 class GraphVisualizer : public NullNodeVisitor {
  26  public:
  27   GraphVisualizer(OStream& os, Zone* zone, const Graph* graph);  // NOLINT
  28
  29   void Print();
  30
  31   GenericGraphVisit::Control Pre(Node* node);
  32   GenericGraphVisit::Control PreEdge(Node* from, int index, Node* to);
  33
  34  private:
  35   void AnnotateNode(Node* node);
  36   void PrintEdge(Node::Edge edge);
  37
  38   Zone* zone_;
  39   NodeSet all_nodes_;
  40   NodeSet white_nodes_;
  41   bool use_to_def_;
  42   OStream& os_;
  43   const Graph* const graph_;
  44
  45   DISALLOW_COPY_AND_ASSIGN(GraphVisualizer);
  46 };
  47
  48
  49 static Node* GetControlCluster(Node* node) {
  50   if (OperatorProperties::IsBasicBlockBegin(node->op())) {
  51     return node;
  52   } else if (OperatorProperties::GetControlInputCount(node->op()) == 1) {
  53     Node* control = NodeProperties::GetControlInput(node, 0);
  54     return OperatorProperties::IsBasicBlockBegin(control->op()) ? control
  55                                                                 : NULL;
  56   } else {
  57     return NULL;
  58   }
  59 }
  60
  61
  62 GenericGraphVisit::Control GraphVisualizer::Pre(Node* node) {
  63   if (all_nodes_.count(node) == 0) {
  64     Node* control_cluster = GetControlCluster(node);
  65     if (control_cluster != NULL) {
  66       os_ << "  subgraph cluster_BasicBlock" << control_cluster->id() << " {\n";
  67     }
  68     os_ << "  ID" << node->id() << " [\n";
  69     AnnotateNode(node);
  70     os_ << "  ]\n";
  71     if (control_cluster != NULL) os_ << "  }\n";
  72     all_nodes_.insert(node);
  73     if (use_to_def_) white_nodes_.insert(node);
  74   }
  75   return GenericGraphVisit::CONTINUE;
  76 }
  77
  78
  79 GenericGraphVisit::Control GraphVisualizer::PreEdge(Node* from, int index,
  80                                                     Node* to) {
  81   if (use_to_def_) return GenericGraphVisit::CONTINUE;
  82   // When going from def to use, only consider white -> other edges, which are
  83   // the dead nodes that use live nodes. We're probably not interested in
  84   // dead nodes that only use other dead nodes.
  85   if (white_nodes_.count(from) > 0) return GenericGraphVisit::CONTINUE;
  86   return GenericGraphVisit::SKIP;
  87 }
  88
  89
  90 class Escaped {
  91  public:
  92   explicit Escaped(const OStringStream& os) : str_(os.c_str()) {}
  93
  94   friend OStream& operator<<(OStream& os, const Escaped& e) {
  95     for (const char* s = e.str_; *s != '\0'; ++s) {
  96       if (needs_escape(*s)) os << "\\";
  97       os << *s;
  98     }
  99     return os;
 100   }
 101
 102  private:
 103   static bool needs_escape(char ch) {
 104     switch (ch) {
 105       case '>':
 106       case '<':
 107       case '|':
 108       case '}':
 109       case '{':
 110         return true;
 111       default:
 112         return false;
 113     }
 114   }
 115
 116   const char* const str_;
 117 };
 118
 119
 120 static bool IsLikelyBackEdge(Node* from, int index, Node* to) {
 121   if (from->opcode() == IrOpcode::kPhi ||
 122       from->opcode() == IrOpcode::kEffectPhi) {
 123     Node* control = NodeProperties::GetControlInput(from, 0);
 124     return control->opcode() != IrOpcode::kMerge && control != to && index != 0;
 125   } else if (from->opcode() == IrOpcode::kLoop) {
 126     return index != 0;
 127   } else {
 128     return false;
 129   }
 130 }
 131
 132
 133 void GraphVisualizer::AnnotateNode(Node* node) {
 134   if (!use_to_def_) {
 135     os_ << "    style=\"filled\"\n"
 136         << "    fillcolor=\"" DEAD_COLOR "\"\n";
 137   }
 138
 139   os_ << "    shape=\"record\"\n";
 140   switch (node->opcode()) {
 141     case IrOpcode::kEnd:
 142     case IrOpcode::kDead:
 143     case IrOpcode::kStart:
 144       os_ << "    style=\"diagonals\"\n";
 145       break;
 146     case IrOpcode::kMerge:
 147     case IrOpcode::kIfTrue:
 148     case IrOpcode::kIfFalse:
 149     case IrOpcode::kLoop:
 150       os_ << "    style=\"rounded\"\n";
 151       break;
 152     default:
 153       break;
 154   }
 155
 156   OStringStream label;
 157   label << *node->op();
 158   os_ << "    label=\"{{#" << node->id() << ":" << Escaped(label);
 159
 160   InputIter i = node->inputs().begin();
 161   for (int j = OperatorProperties::GetValueInputCount(node->op()); j > 0;
 162        ++i, j--) {
 163     os_ << "|<I" << i.index() << ">#" << (*i)->id();
 164   }
 165   for (int j = OperatorProperties::GetContextInputCount(node->op()); j > 0;
 166        ++i, j--) {
 167     os_ << "|<I" << i.index() << ">X #" << (*i)->id();
 168   }
 169   for (int j = OperatorProperties::GetFrameStateInputCount(node->op()); j > 0;
 170        ++i, j--) {
 171     os_ << "|<I" << i.index() << ">F #" << (*i)->id();
 172   }
 173   for (int j = OperatorProperties::GetEffectInputCount(node->op()); j > 0;
 174        ++i, j--) {
 175     os_ << "|<I" << i.index() << ">E #" << (*i)->id();
 176   }
 177
 178   if (!use_to_def_ || OperatorProperties::IsBasicBlockBegin(node->op()) ||
 179       GetControlCluster(node) == NULL) {
 180     for (int j = OperatorProperties::GetControlInputCount(node->op()); j > 0;
 181          ++i, j--) {
 182       os_ << "|<I" << i.index() << ">C #" << (*i)->id();
 183     }
 184   }
 185   os_ << "}";
 186
 187   if (FLAG_trace_turbo_types && !NodeProperties::IsControl(node)) {
 188     Bounds bounds = NodeProperties::GetBounds(node);
 189     OStringStream upper;
 190     bounds.upper->PrintTo(upper);
 191     OStringStream lower;
 192     bounds.lower->PrintTo(lower);
 193     os_ << "|" << Escaped(upper) << "|" << Escaped(lower);
 194   }
 195   os_ << "}\"\n";
 196 }
 197
 198
 199 void GraphVisualizer::PrintEdge(Node::Edge edge) {
 200   Node* from = edge.from();
 201   int index = edge.index();
 202   Node* to = edge.to();
 203   bool unconstrained = IsLikelyBackEdge(from, index, to);
 204   os_ << "  ID" << from->id();
 205   if (all_nodes_.count(to) == 0) {
 206     os_ << ":I" << index << ":n -> DEAD_INPUT";
 207   } else if (OperatorProperties::IsBasicBlockBegin(from->op()) ||
 208              GetControlCluster(from) == NULL ||
 209              (OperatorProperties::GetControlInputCount(from->op()) > 0 &&
 210               NodeProperties::GetControlInput(from) != to)) {
 211     os_ << ":I" << index << ":n -> ID" << to->id() << ":s"
 212         << "[" << (unconstrained ? "constraint=false, " : "")
 213         << (NodeProperties::IsControlEdge(edge) ? "style=bold, " : "")
 214         << (NodeProperties::IsEffectEdge(edge) ? "style=dotted, " : "")
 215         << (NodeProperties::IsContextEdge(edge) ? "style=dashed, " : "") << "]";
 216   } else {
 217     os_ << " -> ID" << to->id() << ":s [color=transparent, "
 218         << (unconstrained ? "constraint=false, " : "")
 219         << (NodeProperties::IsControlEdge(edge) ? "style=dashed, " : "") << "]";
 220   }
 221   os_ << "\n";
 222 }
 223
 224
 225 void GraphVisualizer::Print() {
 226   os_ << "digraph D {\n"
 227       << "  node [fontsize=8,height=0.25]\n"
 228       << "  rankdir=\"BT\"\n"
 229       << "  ranksep=\"1.2 equally\"\n"
 230       << "  overlap=\"false\"\n"
 231       << "  splines=\"true\"\n"
 232       << "  concentrate=\"true\"\n"
 233       << "  \n";
 234
 235   // Make sure all nodes have been output before writing out the edges.
 236   use_to_def_ = true;
 237   // TODO(svenpanne) Remove the need for the const_casts.
 238   const_cast<Graph*>(graph_)->VisitNodeInputsFromEnd(this);
 239   white_nodes_.insert(const_cast<Graph*>(graph_)->start());
 240
 241   // Visit all uses of white nodes.
 242   use_to_def_ = false;
 243   GenericGraphVisit::Visit<GraphVisualizer, NodeUseIterationTraits<Node> >(
 244       const_cast<Graph*>(graph_), zone_, white_nodes_.begin(),
 245       white_nodes_.end(), this);
 246
 247   os_ << "  DEAD_INPUT [\n"
 248       << "    style=\"filled\" \n"
 249       << "    fillcolor=\"" DEAD_COLOR "\"\n"
 250       << "  ]\n"
 251       << "\n";
 252
 253   // With all the nodes written, add the edges.
 254   for (NodeSetIter i = all_nodes_.begin(); i != all_nodes_.end(); ++i) {
 255     Node::Inputs inputs = (*i)->inputs();
 256     for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end();
 257          ++iter) {
 258       PrintEdge(iter.edge());
 259     }
 260   }
 261   os_ << "}\n";
 262 }
 263
 264
 265 GraphVisualizer::GraphVisualizer(OStream& os, Zone* zone,
 266                                  const Graph* graph)  // NOLINT
 267     : zone_(zone),
 268       all_nodes_(NodeSet::key_compare(), NodeSet::allocator_type(zone)),
 269       white_nodes_(NodeSet::key_compare(), NodeSet::allocator_type(zone)),
 270       use_to_def_(true),
 271       os_(os),
 272       graph_(graph) {}
 273
 274
 275 OStream& operator<<(OStream& os, const AsDOT& ad) {
 276   Zone tmp_zone(ad.graph.zone()->isolate());
 277   GraphVisualizer(os, &tmp_zone, &ad.graph).Print();
 278   return os;
 279 }
 280 }
 281 }
 282 }  // namespace v8::internal::compiler