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 
GetVisualizerLogFileName(CompilationInfo * info,const char * phase,const char * suffix)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 
SafeId(Node * node)80 static int SafeId(Node* node) { return node == nullptr ? -1 : node->id(); }
SafeMnemonic(Node * node)81 static const char* SafeMnemonic(Node* node) {
82   return node == nullptr ? "null" : node->op()->mnemonic();
83 }
84 
85 class JSONEscaped {
86  public:
JSONEscaped(const std::ostringstream & os)87   explicit JSONEscaped(const std::ostringstream& os) : str_(os.str()) {}
88 
operator <<(std::ostream & os,const JSONEscaped & e)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:
PipeCharacter(std::ostream & os,char c)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:
JSONGraphNodeWriter(std::ostream & os,Zone * zone,const Graph * graph,const SourcePositionTable * positions)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 
Print()119   void Print() {
120     for (Node* const node : all_.reachable) PrintNode(node);
121     os_ << "\n";
122   }
123 
PrintNode(Node * node)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:
JSONGraphEdgeWriter(std::ostream & os,Zone * zone,const Graph * graph)188   JSONGraphEdgeWriter(std::ostream& os, Zone* zone, const Graph* graph)
189       : os_(os), all_(zone, graph, false), first_edge_(true) {}
190 
Print()191   void Print() {
192     for (Node* const node : all_.reachable) PrintEdges(node);
193     os_ << "\n";
194   }
195 
PrintEdges(Node * node)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 
PrintEdge(Node * from,int index,Node * to)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 
operator <<(std::ostream & os,const AsJSON & ad)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);
zone() const258   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:
Tag(GraphC1Visualizer * visualizer,const char * name)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 
~Tag()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 
PrintIndent()306 void GraphC1Visualizer::PrintIndent() {
307   for (int i = 0; i < indent_; i++) {
308     os_ << "  ";
309   }
310 }
311 
312 
GraphC1Visualizer(std::ostream & os,Zone * zone)313 GraphC1Visualizer::GraphC1Visualizer(std::ostream& os, Zone* zone)
314     : os_(os), indent_(0), zone_(zone) {}
315 
316 
PrintStringProperty(const char * name,const char * value)317 void GraphC1Visualizer::PrintStringProperty(const char* name,
318                                             const char* value) {
319   PrintIndent();
320   os_ << name << " \"" << value << "\"\n";
321 }
322 
323 
PrintLongProperty(const char * name,int64_t value)324 void GraphC1Visualizer::PrintLongProperty(const char* name, int64_t value) {
325   PrintIndent();
326   os_ << name << " " << static_cast<int>(value / 1000) << "\n";
327 }
328 
329 
PrintBlockProperty(const char * name,int rpo_number)330 void GraphC1Visualizer::PrintBlockProperty(const char* name, int rpo_number) {
331   PrintIndent();
332   os_ << name << " \"B" << rpo_number << "\"\n";
333 }
334 
335 
PrintIntProperty(const char * name,int value)336 void GraphC1Visualizer::PrintIntProperty(const char* name, int value) {
337   PrintIndent();
338   os_ << name << " " << value << "\n";
339 }
340 
341 
PrintCompilation(const CompilationInfo * info)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 
PrintNodeId(Node * n)359 void GraphC1Visualizer::PrintNodeId(Node* n) { os_ << "n" << SafeId(n); }
360 
361 
PrintNode(Node * n)362 void GraphC1Visualizer::PrintNode(Node* n) {
363   PrintNodeId(n);
364   os_ << " " << *n->op() << " ";
365   PrintInputs(n);
366 }
367 
368 
369 template <typename InputIterator>
PrintInputs(InputIterator * i,int count,const char * prefix)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 
PrintInputs(Node * node)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 
PrintType(Node * node)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 
PrintSchedule(const char * phase,const Schedule * schedule,const SourcePositionTable * positions,const InstructionSequence * instructions)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 
PrintLiveRanges(const char * phase,const RegisterAllocationData * data)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 
PrintLiveRangeChain(const TopLevelLiveRange * range,const char * type)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 
PrintLiveRange(const LiveRange * range,const char * type,int vreg)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 
operator <<(std::ostream & os,const AsC1VCompilation & ac)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 
operator <<(std::ostream & os,const AsC1V & ac)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 
operator <<(std::ostream & os,const AsC1VRegisterAllocationData & ac)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 
operator <<(std::ostream & os,const AsRPO & ar)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