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