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 <memory>
8#include <sstream>
9#include <string>
10
11#include "src/code-stubs.h"
12#include "src/compilation-info.h"
13#include "src/compiler/all-nodes.h"
14#include "src/compiler/compiler-source-position-table.h"
15#include "src/compiler/graph.h"
16#include "src/compiler/node-properties.h"
17#include "src/compiler/node.h"
18#include "src/compiler/opcodes.h"
19#include "src/compiler/operator-properties.h"
20#include "src/compiler/operator.h"
21#include "src/compiler/register-allocator.h"
22#include "src/compiler/schedule.h"
23#include "src/compiler/scheduler.h"
24#include "src/interpreter/bytecodes.h"
25#include "src/objects-inl.h"
26#include "src/ostreams.h"
27
28namespace v8 {
29namespace internal {
30namespace compiler {
31
32std::unique_ptr<char[]> GetVisualizerLogFileName(CompilationInfo* info,
33                                                 const char* phase,
34                                                 const char* suffix) {
35  EmbeddedVector<char, 256> filename(0);
36  std::unique_ptr<char[]> debug_name = info->GetDebugName();
37  if (strlen(debug_name.get()) > 0) {
38    if (info->has_shared_info()) {
39      int attempt = info->shared_info()->opt_count();
40      SNPrintF(filename, "turbo-%s-%i", debug_name.get(), attempt);
41    } else {
42      SNPrintF(filename, "turbo-%s", debug_name.get());
43    }
44  } else if (info->has_shared_info()) {
45    int attempt = info->shared_info()->opt_count();
46    SNPrintF(filename, "turbo-%p-%i", static_cast<void*>(info), attempt);
47  } else {
48    SNPrintF(filename, "turbo-none-%s", phase);
49  }
50  EmbeddedVector<char, 256> source_file(0);
51  bool source_available = false;
52  if (FLAG_trace_file_names && info->parse_info()) {
53    Object* source_name = info->script()->name();
54    if (source_name->IsString()) {
55      String* str = String::cast(source_name);
56      if (str->length() > 0) {
57        SNPrintF(source_file, "%s", str->ToCString().get());
58        std::replace(source_file.start(),
59                     source_file.start() + source_file.length(), '/', '_');
60        source_available = true;
61      }
62    }
63  }
64  std::replace(filename.start(), filename.start() + filename.length(), ' ',
65               '_');
66
67  EmbeddedVector<char, 256> full_filename;
68  if (phase == nullptr && !source_available) {
69    SNPrintF(full_filename, "%s.%s", filename.start(), suffix);
70  } else if (phase != nullptr && !source_available) {
71    SNPrintF(full_filename, "%s-%s.%s", filename.start(), phase, suffix);
72  } else if (phase == nullptr && source_available) {
73    SNPrintF(full_filename, "%s_%s.%s", filename.start(), source_file.start(),
74             suffix);
75  } else {
76    SNPrintF(full_filename, "%s_%s-%s.%s", filename.start(),
77             source_file.start(), phase, suffix);
78  }
79
80  char* buffer = new char[full_filename.length() + 1];
81  memcpy(buffer, full_filename.start(), full_filename.length());
82  buffer[full_filename.length()] = '\0';
83  return std::unique_ptr<char[]>(buffer);
84}
85
86
87static int SafeId(Node* node) { return node == nullptr ? -1 : node->id(); }
88static const char* SafeMnemonic(Node* node) {
89  return node == nullptr ? "null" : node->op()->mnemonic();
90}
91
92class JSONEscaped {
93 public:
94  explicit JSONEscaped(const std::ostringstream& os) : str_(os.str()) {}
95
96  friend std::ostream& operator<<(std::ostream& os, const JSONEscaped& e) {
97    for (char c : e.str_) PipeCharacter(os, c);
98    return os;
99  }
100
101 private:
102  static std::ostream& PipeCharacter(std::ostream& os, char c) {
103    if (c == '"') return os << "\\\"";
104    if (c == '\\') return os << "\\\\";
105    if (c == '\b') return os << "\\b";
106    if (c == '\f') return os << "\\f";
107    if (c == '\n') return os << "\\n";
108    if (c == '\r') return os << "\\r";
109    if (c == '\t') return os << "\\t";
110    return os << c;
111  }
112
113  const std::string str_;
114};
115
116class JSONGraphNodeWriter {
117 public:
118  JSONGraphNodeWriter(std::ostream& os, Zone* zone, const Graph* graph,
119                      const SourcePositionTable* positions)
120      : os_(os),
121        all_(zone, graph, false),
122        live_(zone, graph, true),
123        positions_(positions),
124        first_node_(true) {}
125
126  void Print() {
127    for (Node* const node : all_.reachable) PrintNode(node);
128    os_ << "\n";
129  }
130
131  void PrintNode(Node* node) {
132    if (first_node_) {
133      first_node_ = false;
134    } else {
135      os_ << ",\n";
136    }
137    std::ostringstream label, title, properties;
138    node->op()->PrintTo(label, Operator::PrintVerbosity::kSilent);
139    node->op()->PrintTo(title, Operator::PrintVerbosity::kVerbose);
140    node->op()->PrintPropsTo(properties);
141    os_ << "{\"id\":" << SafeId(node) << ",\"label\":\"" << JSONEscaped(label)
142        << "\""
143        << ",\"title\":\"" << JSONEscaped(title) << "\""
144        << ",\"live\": " << (live_.IsLive(node) ? "true" : "false")
145        << ",\"properties\":\"" << JSONEscaped(properties) << "\"";
146    IrOpcode::Value opcode = node->opcode();
147    if (IrOpcode::IsPhiOpcode(opcode)) {
148      os_ << ",\"rankInputs\":[0," << NodeProperties::FirstControlIndex(node)
149          << "]";
150      os_ << ",\"rankWithInput\":[" << NodeProperties::FirstControlIndex(node)
151          << "]";
152    } else if (opcode == IrOpcode::kIfTrue || opcode == IrOpcode::kIfFalse ||
153               opcode == IrOpcode::kLoop) {
154      os_ << ",\"rankInputs\":[" << NodeProperties::FirstControlIndex(node)
155          << "]";
156    }
157    if (opcode == IrOpcode::kBranch) {
158      os_ << ",\"rankInputs\":[0]";
159    }
160    SourcePosition position = positions_->GetSourcePosition(node);
161    if (position.IsKnown()) {
162      os_ << ",\"pos\":" << position.ScriptOffset();
163    }
164    os_ << ",\"opcode\":\"" << IrOpcode::Mnemonic(node->opcode()) << "\"";
165    os_ << ",\"control\":" << (NodeProperties::IsControl(node) ? "true"
166                                                               : "false");
167    os_ << ",\"opinfo\":\"" << node->op()->ValueInputCount() << " v "
168        << node->op()->EffectInputCount() << " eff "
169        << node->op()->ControlInputCount() << " ctrl in, "
170        << node->op()->ValueOutputCount() << " v "
171        << node->op()->EffectOutputCount() << " eff "
172        << node->op()->ControlOutputCount() << " ctrl out\"";
173    if (NodeProperties::IsTyped(node)) {
174      Type* type = NodeProperties::GetType(node);
175      std::ostringstream type_out;
176      type->PrintTo(type_out);
177      os_ << ",\"type\":\"" << JSONEscaped(type_out) << "\"";
178    }
179    os_ << "}";
180  }
181
182 private:
183  std::ostream& os_;
184  AllNodes all_;
185  AllNodes live_;
186  const SourcePositionTable* positions_;
187  bool first_node_;
188
189  DISALLOW_COPY_AND_ASSIGN(JSONGraphNodeWriter);
190};
191
192
193class JSONGraphEdgeWriter {
194 public:
195  JSONGraphEdgeWriter(std::ostream& os, Zone* zone, const Graph* graph)
196      : os_(os), all_(zone, graph, false), first_edge_(true) {}
197
198  void Print() {
199    for (Node* const node : all_.reachable) PrintEdges(node);
200    os_ << "\n";
201  }
202
203  void PrintEdges(Node* node) {
204    for (int i = 0; i < node->InputCount(); i++) {
205      Node* input = node->InputAt(i);
206      if (input == nullptr) continue;
207      PrintEdge(node, i, input);
208    }
209  }
210
211  void PrintEdge(Node* from, int index, Node* to) {
212    if (first_edge_) {
213      first_edge_ = false;
214    } else {
215      os_ << ",\n";
216    }
217    const char* edge_type = nullptr;
218    if (index < NodeProperties::FirstValueIndex(from)) {
219      edge_type = "unknown";
220    } else if (index < NodeProperties::FirstContextIndex(from)) {
221      edge_type = "value";
222    } else if (index < NodeProperties::FirstFrameStateIndex(from)) {
223      edge_type = "context";
224    } else if (index < NodeProperties::FirstEffectIndex(from)) {
225      edge_type = "frame-state";
226    } else if (index < NodeProperties::FirstControlIndex(from)) {
227      edge_type = "effect";
228    } else {
229      edge_type = "control";
230    }
231    os_ << "{\"source\":" << SafeId(to) << ",\"target\":" << SafeId(from)
232        << ",\"index\":" << index << ",\"type\":\"" << edge_type << "\"}";
233  }
234
235 private:
236  std::ostream& os_;
237  AllNodes all_;
238  bool first_edge_;
239
240  DISALLOW_COPY_AND_ASSIGN(JSONGraphEdgeWriter);
241};
242
243
244std::ostream& operator<<(std::ostream& os, const AsJSON& ad) {
245  AccountingAllocator allocator;
246  Zone tmp_zone(&allocator, ZONE_NAME);
247  os << "{\n\"nodes\":[";
248  JSONGraphNodeWriter(os, &tmp_zone, &ad.graph, ad.positions).Print();
249  os << "],\n\"edges\":[";
250  JSONGraphEdgeWriter(os, &tmp_zone, &ad.graph).Print();
251  os << "]}";
252  return os;
253}
254
255
256class GraphC1Visualizer {
257 public:
258  GraphC1Visualizer(std::ostream& os, Zone* zone);  // NOLINT
259
260  void PrintCompilation(const CompilationInfo* info);
261  void PrintSchedule(const char* phase, const Schedule* schedule,
262                     const SourcePositionTable* positions,
263                     const InstructionSequence* instructions);
264  void PrintLiveRanges(const char* phase, const RegisterAllocationData* data);
265  Zone* zone() const { return zone_; }
266
267 private:
268  void PrintIndent();
269  void PrintStringProperty(const char* name, const char* value);
270  void PrintLongProperty(const char* name, int64_t value);
271  void PrintIntProperty(const char* name, int value);
272  void PrintBlockProperty(const char* name, int rpo_number);
273  void PrintNodeId(Node* n);
274  void PrintNode(Node* n);
275  void PrintInputs(Node* n);
276  template <typename InputIterator>
277  void PrintInputs(InputIterator* i, int count, const char* prefix);
278  void PrintType(Node* node);
279
280  void PrintLiveRange(const LiveRange* range, const char* type, int vreg);
281  void PrintLiveRangeChain(const TopLevelLiveRange* range, const char* type);
282
283  class Tag final BASE_EMBEDDED {
284   public:
285    Tag(GraphC1Visualizer* visualizer, const char* name) {
286      name_ = name;
287      visualizer_ = visualizer;
288      visualizer->PrintIndent();
289      visualizer_->os_ << "begin_" << name << "\n";
290      visualizer->indent_++;
291    }
292
293    ~Tag() {
294      visualizer_->indent_--;
295      visualizer_->PrintIndent();
296      visualizer_->os_ << "end_" << name_ << "\n";
297      DCHECK(visualizer_->indent_ >= 0);
298    }
299
300   private:
301    GraphC1Visualizer* visualizer_;
302    const char* name_;
303  };
304
305  std::ostream& os_;
306  int indent_;
307  Zone* zone_;
308
309  DISALLOW_COPY_AND_ASSIGN(GraphC1Visualizer);
310};
311
312
313void GraphC1Visualizer::PrintIndent() {
314  for (int i = 0; i < indent_; i++) {
315    os_ << "  ";
316  }
317}
318
319
320GraphC1Visualizer::GraphC1Visualizer(std::ostream& os, Zone* zone)
321    : os_(os), indent_(0), zone_(zone) {}
322
323
324void GraphC1Visualizer::PrintStringProperty(const char* name,
325                                            const char* value) {
326  PrintIndent();
327  os_ << name << " \"" << value << "\"\n";
328}
329
330
331void GraphC1Visualizer::PrintLongProperty(const char* name, int64_t value) {
332  PrintIndent();
333  os_ << name << " " << static_cast<int>(value / 1000) << "\n";
334}
335
336
337void GraphC1Visualizer::PrintBlockProperty(const char* name, int rpo_number) {
338  PrintIndent();
339  os_ << name << " \"B" << rpo_number << "\"\n";
340}
341
342
343void GraphC1Visualizer::PrintIntProperty(const char* name, int value) {
344  PrintIndent();
345  os_ << name << " " << value << "\n";
346}
347
348
349void GraphC1Visualizer::PrintCompilation(const CompilationInfo* info) {
350  Tag tag(this, "compilation");
351  std::unique_ptr<char[]> name = info->GetDebugName();
352  if (info->IsOptimizing()) {
353    PrintStringProperty("name", name.get());
354    PrintIndent();
355    os_ << "method \"" << name.get() << ":" << info->optimization_id()
356        << "\"\n";
357  } else {
358    PrintStringProperty("name", name.get());
359    PrintStringProperty("method", "stub");
360  }
361  PrintLongProperty("date",
362                    static_cast<int64_t>(base::OS::TimeCurrentMillis()));
363}
364
365
366void GraphC1Visualizer::PrintNodeId(Node* n) { os_ << "n" << SafeId(n); }
367
368
369void GraphC1Visualizer::PrintNode(Node* n) {
370  PrintNodeId(n);
371  os_ << " " << *n->op() << " ";
372  PrintInputs(n);
373}
374
375
376template <typename InputIterator>
377void GraphC1Visualizer::PrintInputs(InputIterator* i, int count,
378                                    const char* prefix) {
379  if (count > 0) {
380    os_ << prefix;
381  }
382  while (count > 0) {
383    os_ << " ";
384    PrintNodeId(**i);
385    ++(*i);
386    count--;
387  }
388}
389
390
391void GraphC1Visualizer::PrintInputs(Node* node) {
392  auto i = node->inputs().begin();
393  PrintInputs(&i, node->op()->ValueInputCount(), " ");
394  PrintInputs(&i, OperatorProperties::GetContextInputCount(node->op()),
395              " Ctx:");
396  PrintInputs(&i, OperatorProperties::GetFrameStateInputCount(node->op()),
397              " FS:");
398  PrintInputs(&i, node->op()->EffectInputCount(), " Eff:");
399  PrintInputs(&i, node->op()->ControlInputCount(), " Ctrl:");
400}
401
402
403void GraphC1Visualizer::PrintType(Node* node) {
404  if (NodeProperties::IsTyped(node)) {
405    Type* type = NodeProperties::GetType(node);
406    os_ << " type:";
407    type->PrintTo(os_);
408  }
409}
410
411
412void GraphC1Visualizer::PrintSchedule(const char* phase,
413                                      const Schedule* schedule,
414                                      const SourcePositionTable* positions,
415                                      const InstructionSequence* instructions) {
416  Tag tag(this, "cfg");
417  PrintStringProperty("name", phase);
418  const BasicBlockVector* rpo = schedule->rpo_order();
419  for (size_t i = 0; i < rpo->size(); i++) {
420    BasicBlock* current = (*rpo)[i];
421    Tag block_tag(this, "block");
422    PrintBlockProperty("name", current->rpo_number());
423    PrintIntProperty("from_bci", -1);
424    PrintIntProperty("to_bci", -1);
425
426    PrintIndent();
427    os_ << "predecessors";
428    for (BasicBlock* predecessor : current->predecessors()) {
429      os_ << " \"B" << predecessor->rpo_number() << "\"";
430    }
431    os_ << "\n";
432
433    PrintIndent();
434    os_ << "successors";
435    for (BasicBlock* successor : current->successors()) {
436      os_ << " \"B" << successor->rpo_number() << "\"";
437    }
438    os_ << "\n";
439
440    PrintIndent();
441    os_ << "xhandlers\n";
442
443    PrintIndent();
444    os_ << "flags\n";
445
446    if (current->dominator() != nullptr) {
447      PrintBlockProperty("dominator", current->dominator()->rpo_number());
448    }
449
450    PrintIntProperty("loop_depth", current->loop_depth());
451
452    const InstructionBlock* instruction_block =
453        instructions->InstructionBlockAt(
454            RpoNumber::FromInt(current->rpo_number()));
455    if (instruction_block->code_start() >= 0) {
456      int first_index = instruction_block->first_instruction_index();
457      int last_index = instruction_block->last_instruction_index();
458      PrintIntProperty(
459          "first_lir_id",
460          LifetimePosition::GapFromInstructionIndex(first_index).value());
461      PrintIntProperty("last_lir_id",
462                       LifetimePosition::InstructionFromInstructionIndex(
463                           last_index).value());
464    }
465
466    {
467      Tag states_tag(this, "states");
468      Tag locals_tag(this, "locals");
469      int total = 0;
470      for (BasicBlock::const_iterator i = current->begin(); i != current->end();
471           ++i) {
472        if ((*i)->opcode() == IrOpcode::kPhi) total++;
473      }
474      PrintIntProperty("size", total);
475      PrintStringProperty("method", "None");
476      int index = 0;
477      for (BasicBlock::const_iterator i = current->begin(); i != current->end();
478           ++i) {
479        if ((*i)->opcode() != IrOpcode::kPhi) continue;
480        PrintIndent();
481        os_ << index << " ";
482        PrintNodeId(*i);
483        os_ << " [";
484        PrintInputs(*i);
485        os_ << "]\n";
486        index++;
487      }
488    }
489
490    {
491      Tag HIR_tag(this, "HIR");
492      for (BasicBlock::const_iterator i = current->begin(); i != current->end();
493           ++i) {
494        Node* node = *i;
495        if (node->opcode() == IrOpcode::kPhi) continue;
496        int uses = node->UseCount();
497        PrintIndent();
498        os_ << "0 " << uses << " ";
499        PrintNode(node);
500        if (FLAG_trace_turbo_types) {
501          os_ << " ";
502          PrintType(node);
503        }
504        if (positions != nullptr) {
505          SourcePosition position = positions->GetSourcePosition(node);
506          if (position.IsKnown()) {
507            os_ << " pos:";
508            if (position.isInlined()) {
509              os_ << "inlining(" << position.InliningId() << "),";
510            }
511            os_ << position.ScriptOffset();
512          }
513        }
514        os_ << " <|@\n";
515      }
516
517      BasicBlock::Control control = current->control();
518      if (control != BasicBlock::kNone) {
519        PrintIndent();
520        os_ << "0 0 ";
521        if (current->control_input() != nullptr) {
522          PrintNode(current->control_input());
523        } else {
524          os_ << -1 - current->rpo_number() << " Goto";
525        }
526        os_ << " ->";
527        for (BasicBlock* successor : current->successors()) {
528          os_ << " B" << successor->rpo_number();
529        }
530        if (FLAG_trace_turbo_types && current->control_input() != nullptr) {
531          os_ << " ";
532          PrintType(current->control_input());
533        }
534        os_ << " <|@\n";
535      }
536    }
537
538    if (instructions != nullptr) {
539      Tag LIR_tag(this, "LIR");
540      for (int j = instruction_block->first_instruction_index();
541           j <= instruction_block->last_instruction_index(); j++) {
542        PrintIndent();
543        PrintableInstruction printable = {RegisterConfiguration::Turbofan(),
544                                          instructions->InstructionAt(j)};
545        os_ << j << " " << printable << " <|@\n";
546      }
547    }
548  }
549}
550
551
552void GraphC1Visualizer::PrintLiveRanges(const char* phase,
553                                        const RegisterAllocationData* data) {
554  Tag tag(this, "intervals");
555  PrintStringProperty("name", phase);
556
557  for (const TopLevelLiveRange* range : data->fixed_double_live_ranges()) {
558    PrintLiveRangeChain(range, "fixed");
559  }
560
561  for (const TopLevelLiveRange* range : data->fixed_live_ranges()) {
562    PrintLiveRangeChain(range, "fixed");
563  }
564
565  for (const TopLevelLiveRange* range : data->live_ranges()) {
566    PrintLiveRangeChain(range, "object");
567  }
568}
569
570void GraphC1Visualizer::PrintLiveRangeChain(const TopLevelLiveRange* range,
571                                            const char* type) {
572  if (range == nullptr || range->IsEmpty()) return;
573  int vreg = range->vreg();
574  for (const LiveRange* child = range; child != nullptr;
575       child = child->next()) {
576    PrintLiveRange(child, type, vreg);
577  }
578}
579
580void GraphC1Visualizer::PrintLiveRange(const LiveRange* range, const char* type,
581                                       int vreg) {
582  if (range != nullptr && !range->IsEmpty()) {
583    PrintIndent();
584    os_ << vreg << ":" << range->relative_id() << " " << type;
585    if (range->HasRegisterAssigned()) {
586      AllocatedOperand op = AllocatedOperand::cast(range->GetAssignedOperand());
587      const auto config = RegisterConfiguration::Turbofan();
588      if (op.IsRegister()) {
589        os_ << " \"" << config->GetGeneralRegisterName(op.register_code())
590            << "\"";
591      } else if (op.IsDoubleRegister()) {
592        os_ << " \"" << config->GetDoubleRegisterName(op.register_code())
593            << "\"";
594      } else {
595        DCHECK(op.IsFloatRegister());
596        os_ << " \"" << config->GetFloatRegisterName(op.register_code())
597            << "\"";
598      }
599    } else if (range->spilled()) {
600      const TopLevelLiveRange* top = range->TopLevel();
601      int index = -1;
602      if (top->HasSpillRange()) {
603        index = kMaxInt;  // This hasn't been set yet.
604      } else if (top->GetSpillOperand()->IsConstant()) {
605        os_ << " \"const(nostack):"
606            << ConstantOperand::cast(top->GetSpillOperand())->virtual_register()
607            << "\"";
608      } else {
609        index = AllocatedOperand::cast(top->GetSpillOperand())->index();
610        if (IsFloatingPoint(top->representation())) {
611          os_ << " \"fp_stack:" << index << "\"";
612        } else {
613          os_ << " \"stack:" << index << "\"";
614        }
615      }
616    }
617
618    os_ << " " << vreg;
619    for (const UseInterval* interval = range->first_interval();
620         interval != nullptr; interval = interval->next()) {
621      os_ << " [" << interval->start().value() << ", "
622          << interval->end().value() << "[";
623    }
624
625    UsePosition* current_pos = range->first_pos();
626    while (current_pos != nullptr) {
627      if (current_pos->RegisterIsBeneficial() || FLAG_trace_all_uses) {
628        os_ << " " << current_pos->pos().value() << " M";
629      }
630      current_pos = current_pos->next();
631    }
632
633    os_ << " \"\"\n";
634  }
635}
636
637
638std::ostream& operator<<(std::ostream& os, const AsC1VCompilation& ac) {
639  AccountingAllocator allocator;
640  Zone tmp_zone(&allocator, ZONE_NAME);
641  GraphC1Visualizer(os, &tmp_zone).PrintCompilation(ac.info_);
642  return os;
643}
644
645
646std::ostream& operator<<(std::ostream& os, const AsC1V& ac) {
647  AccountingAllocator allocator;
648  Zone tmp_zone(&allocator, ZONE_NAME);
649  GraphC1Visualizer(os, &tmp_zone)
650      .PrintSchedule(ac.phase_, ac.schedule_, ac.positions_, ac.instructions_);
651  return os;
652}
653
654
655std::ostream& operator<<(std::ostream& os,
656                         const AsC1VRegisterAllocationData& ac) {
657  AccountingAllocator allocator;
658  Zone tmp_zone(&allocator, ZONE_NAME);
659  GraphC1Visualizer(os, &tmp_zone).PrintLiveRanges(ac.phase_, ac.data_);
660  return os;
661}
662
663const int kUnvisited = 0;
664const int kOnStack = 1;
665const int kVisited = 2;
666
667std::ostream& operator<<(std::ostream& os, const AsRPO& ar) {
668  AccountingAllocator allocator;
669  Zone local_zone(&allocator, ZONE_NAME);
670
671  // Do a post-order depth-first search on the RPO graph. For every node,
672  // print:
673  //
674  //   - the node id
675  //   - the operator mnemonic
676  //   - in square brackets its parameter (if present)
677  //   - in parentheses the list of argument ids and their mnemonics
678  //   - the node type (if it is typed)
679
680  // Post-order guarantees that all inputs of a node will be printed before
681  // the node itself, if there are no cycles. Any cycles are broken
682  // arbitrarily.
683
684  ZoneVector<byte> state(ar.graph.NodeCount(), kUnvisited, &local_zone);
685  ZoneStack<Node*> stack(&local_zone);
686
687  stack.push(ar.graph.end());
688  state[ar.graph.end()->id()] = kOnStack;
689  while (!stack.empty()) {
690    Node* n = stack.top();
691    bool pop = true;
692    for (Node* const i : n->inputs()) {
693      if (state[i->id()] == kUnvisited) {
694        state[i->id()] = kOnStack;
695        stack.push(i);
696        pop = false;
697        break;
698      }
699    }
700    if (pop) {
701      state[n->id()] = kVisited;
702      stack.pop();
703      os << "#" << n->id() << ":" << *n->op() << "(";
704      // Print the inputs.
705      int j = 0;
706      for (Node* const i : n->inputs()) {
707        if (j++ > 0) os << ", ";
708        os << "#" << SafeId(i) << ":" << SafeMnemonic(i);
709      }
710      os << ")";
711      // Print the node type, if any.
712      if (NodeProperties::IsTyped(n)) {
713        os << "  [Type: ";
714        NodeProperties::GetType(n)->PrintTo(os);
715        os << "]";
716      }
717      os << std::endl;
718    }
719  }
720  return os;
721}
722}  // namespace compiler
723}  // namespace internal
724}  // namespace v8
725