Home | History | Annotate | Download | only in compiler 
      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
    283