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