src/compiler/graph-visualizer.cc - v8/v8.git - Git at Google

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "src/compiler/graph-visualizer.h"

 #include <sstream>
 #include <string>

 #include "src/code-stubs.h"
 #include "src/compiler/all-nodes.h"
 #include "src/compiler/graph.h"
 #include "src/compiler/node.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/opcodes.h"
 #include "src/compiler/operator.h"
 #include "src/compiler/operator-properties.h"
 #include "src/compiler/register-allocator.h"
 #include "src/compiler/schedule.h"
 #include "src/compiler/scheduler.h"
 #include "src/interpreter/bytecodes.h"
 #include "src/ostreams.h"

 namespace v8 {
 namespace internal {
 namespace compiler {

 base::SmartArrayPointer<const char> GetVisualizerLogFileName(
     CompilationInfo* info, const char* phase, const char* suffix) {
   EmbeddedVector<char, 256> filename(0);
   base::SmartArrayPointer<char> debug_name = info->GetDebugName();
   if (strlen(debug_name.get()) > 0) {
     SNPrintF(filename, "turbo-%s", debug_name.get());
   } else if (info->has_shared_info()) {
     SNPrintF(filename, "turbo-%p", static_cast<void*>(info));
   } else {
     SNPrintF(filename, "turbo-none-%s", phase);
   }
   std::replace(filename.start(), filename.start() + filename.length(), ' ',
                '_');

   EmbeddedVector<char, 256> full_filename;
   if (phase == nullptr) {
     SNPrintF(full_filename, "%s.%s", filename.start(), suffix);
   } else {
     SNPrintF(full_filename, "%s-%s.%s", filename.start(), phase, suffix);
   }

   char* buffer = new char[full_filename.length() + 1];
   memcpy(buffer, full_filename.start(), full_filename.length());
   buffer[full_filename.length()] = '\0';
   return base::SmartArrayPointer<const char>(buffer);
 }


 static int SafeId(Node* node) { return node == nullptr ? -1 : node->id(); }
 static const char* SafeMnemonic(Node* node) {
   return node == nullptr ? "null" : node->op()->mnemonic();
 }

 #define DEAD_COLOR "#999999"

 class Escaped {
  public:
   explicit Escaped(const std::ostringstream& os,
                    const char* escaped_chars = "<>|{}")
       : str_(os.str()), escaped_chars_(escaped_chars) {}

   friend std::ostream& operator<<(std::ostream& os, const Escaped& e) {
     for (std::string::const_iterator i = e.str_.begin(); i != e.str_.end();
          ++i) {
       if (e.needs_escape(*i)) os << "\\";
       os << *i;
     }
     return os;
   }

  private:
   bool needs_escape(char ch) const {
     for (size_t i = 0; i < strlen(escaped_chars_); ++i) {
       if (ch == escaped_chars_[i]) return true;
     }
     return false;
   }

   const std::string str_;
   const char* const escaped_chars_;
 };

 class JSONGraphNodeWriter {
  public:
   JSONGraphNodeWriter(std::ostream& os, Zone* zone, const Graph* graph,
                       const SourcePositionTable* positions)
       : os_(os), all_(zone, graph), positions_(positions), first_node_(true) {}

   void Print() {
     for (Node* const node : all_.live) PrintNode(node);
     os_ << "\n";
   }

   void PrintNode(Node* node) {
     if (first_node_) {
       first_node_ = false;
     } else {
       os_ << ",\n";
     }
     std::ostringstream label;
     label << *node->op();
     os_ << "{\"id\":" << SafeId(node) << ",\"label\":\"" << Escaped(label, "\"")
         << "\"";
     IrOpcode::Value opcode = node->opcode();
     if (IrOpcode::IsPhiOpcode(opcode)) {
       os_ << ",\"rankInputs\":[0," << NodeProperties::FirstControlIndex(node)
           << "]";
       os_ << ",\"rankWithInput\":[" << NodeProperties::FirstControlIndex(node)
           << "]";
     } else if (opcode == IrOpcode::kIfTrue || opcode == IrOpcode::kIfFalse ||
                opcode == IrOpcode::kLoop) {
       os_ << ",\"rankInputs\":[" << NodeProperties::FirstControlIndex(node)
           << "]";
     }
     if (opcode == IrOpcode::kBranch) {
       os_ << ",\"rankInputs\":[0]";
     }
     SourcePosition position = positions_->GetSourcePosition(node);
     if (position.IsKnown()) {
       os_ << ",\"pos\":" << position.raw();
     }
     os_ << ",\"opcode\":\"" << IrOpcode::Mnemonic(node->opcode()) << "\"";
     os_ << ",\"control\":" << (NodeProperties::IsControl(node) ? "true"
                                                                : "false");
     if (NodeProperties::IsTyped(node)) {
       Type* type = NodeProperties::GetType(node);
       std::ostringstream type_out;
       type->PrintTo(type_out);
       os_ << ",\"type\":\"" << Escaped(type_out, "\"") << "\"";
     }
     os_ << "}";
   }

  private:
   std::ostream& os_;
   AllNodes all_;
   const SourcePositionTable* positions_;
   bool first_node_;

   DISALLOW_COPY_AND_ASSIGN(JSONGraphNodeWriter);
 };


 class JSONGraphEdgeWriter {
  public:
   JSONGraphEdgeWriter(std::ostream& os, Zone* zone, const Graph* graph)
       : os_(os), all_(zone, graph), first_edge_(true) {}

   void Print() {
     for (Node* const node : all_.live) PrintEdges(node);
     os_ << "\n";
   }

   void PrintEdges(Node* node) {
     for (int i = 0; i < node->InputCount(); i++) {
       Node* input = node->InputAt(i);
       if (input == nullptr) continue;
       PrintEdge(node, i, input);
     }
   }

   void PrintEdge(Node* from, int index, Node* to) {
     if (first_edge_) {
       first_edge_ = false;
     } else {
       os_ << ",\n";
     }
     const char* edge_type = nullptr;
     if (index < NodeProperties::FirstValueIndex(from)) {
       edge_type = "unknown";
     } else if (index < NodeProperties::FirstContextIndex(from)) {
       edge_type = "value";
     } else if (index < NodeProperties::FirstFrameStateIndex(from)) {
       edge_type = "context";
     } else if (index < NodeProperties::FirstEffectIndex(from)) {
       edge_type = "frame-state";
     } else if (index < NodeProperties::FirstControlIndex(from)) {
       edge_type = "effect";
     } else {
       edge_type = "control";
     }
     os_ << "{\"source\":" << SafeId(to) << ",\"target\":" << SafeId(from)
         << ",\"index\":" << index << ",\"type\":\"" << edge_type << "\"}";
   }

  private:
   std::ostream& os_;
   AllNodes all_;
   bool first_edge_;

   DISALLOW_COPY_AND_ASSIGN(JSONGraphEdgeWriter);
 };


 std::ostream& operator<<(std::ostream& os, const AsJSON& ad) {
   base::AccountingAllocator allocator;
   Zone tmp_zone(&allocator);
   os << "{\n\"nodes\":[";
   JSONGraphNodeWriter(os, &tmp_zone, &ad.graph, ad.positions).Print();
   os << "],\n\"edges\":[";
   JSONGraphEdgeWriter(os, &tmp_zone, &ad.graph).Print();
   os << "]}";
   return os;
 }


 class GraphC1Visualizer {
  public:
   GraphC1Visualizer(std::ostream& os, Zone* zone);  // NOLINT

   void PrintCompilation(const CompilationInfo* info);
   void PrintSchedule(const char* phase, const Schedule* schedule,
                      const SourcePositionTable* positions,
                      const InstructionSequence* instructions);
   void PrintLiveRanges(const char* phase, const RegisterAllocationData* data);
   Zone* zone() const { return zone_; }

  private:
   void PrintIndent();
   void PrintStringProperty(const char* name, const char* value);
   void PrintLongProperty(const char* name, int64_t value);
   void PrintIntProperty(const char* name, int value);
   void PrintBlockProperty(const char* name, int rpo_number);
   void PrintNodeId(Node* n);
   void PrintNode(Node* n);
   void PrintInputs(Node* n);
   template <typename InputIterator>
   void PrintInputs(InputIterator* i, int count, const char* prefix);
   void PrintType(Node* node);

   void PrintLiveRange(const LiveRange* range, const char* type, int vreg);
   void PrintLiveRangeChain(const TopLevelLiveRange* range, const char* type);

   class Tag final BASE_EMBEDDED {
    public:
     Tag(GraphC1Visualizer* visualizer, const char* name) {
       name_ = name;
       visualizer_ = visualizer;
       visualizer->PrintIndent();
       visualizer_->os_ << "begin_" << name << "\n";
       visualizer->indent_++;
     }

     ~Tag() {
       visualizer_->indent_--;
       visualizer_->PrintIndent();
       visualizer_->os_ << "end_" << name_ << "\n";
       DCHECK(visualizer_->indent_ >= 0);
     }

    private:
     GraphC1Visualizer* visualizer_;
     const char* name_;
   };

   std::ostream& os_;
   int indent_;
   Zone* zone_;

   DISALLOW_COPY_AND_ASSIGN(GraphC1Visualizer);
 };


 void GraphC1Visualizer::PrintIndent() {
   for (int i = 0; i < indent_; i++) {
     os_ << "  ";
   }
 }


 GraphC1Visualizer::GraphC1Visualizer(std::ostream& os, Zone* zone)
     : os_(os), indent_(0), zone_(zone) {}


 void GraphC1Visualizer::PrintStringProperty(const char* name,
                                             const char* value) {
   PrintIndent();
   os_ << name << " \"" << value << "\"\n";
 }


 void GraphC1Visualizer::PrintLongProperty(const char* name, int64_t value) {
   PrintIndent();
   os_ << name << " " << static_cast<int>(value / 1000) << "\n";
 }


 void GraphC1Visualizer::PrintBlockProperty(const char* name, int rpo_number) {
   PrintIndent();
   os_ << name << " \"B" << rpo_number << "\"\n";
 }


 void GraphC1Visualizer::PrintIntProperty(const char* name, int value) {
   PrintIndent();
   os_ << name << " " << value << "\n";
 }


 void GraphC1Visualizer::PrintCompilation(const CompilationInfo* info) {
   Tag tag(this, "compilation");
   base::SmartArrayPointer<char> name = info->GetDebugName();
   if (info->IsOptimizing()) {
     PrintStringProperty("name", name.get());
     PrintIndent();
     os_ << "method \"" << name.get() << ":" << info->optimization_id()
         << "\"\n";
   } else {
     PrintStringProperty("name", name.get());
     PrintStringProperty("method", "stub");
   }
   PrintLongProperty("date",
                     static_cast<int64_t>(base::OS::TimeCurrentMillis()));
 }


 void GraphC1Visualizer::PrintNodeId(Node* n) { os_ << "n" << SafeId(n); }


 void GraphC1Visualizer::PrintNode(Node* n) {
   PrintNodeId(n);
   os_ << " " << *n->op() << " ";
   PrintInputs(n);
 }


 template <typename InputIterator>
 void GraphC1Visualizer::PrintInputs(InputIterator* i, int count,
                                     const char* prefix) {
   if (count > 0) {
     os_ << prefix;
   }
   while (count > 0) {
     os_ << " ";
     PrintNodeId(**i);
     ++(*i);
     count--;
   }
 }


 void GraphC1Visualizer::PrintInputs(Node* node) {
   auto i = node->inputs().begin();
   PrintInputs(&i, node->op()->ValueInputCount(), " ");
   PrintInputs(&i, OperatorProperties::GetContextInputCount(node->op()),
               " Ctx:");
   PrintInputs(&i, OperatorProperties::GetFrameStateInputCount(node->op()),
               " FS:");
   PrintInputs(&i, node->op()->EffectInputCount(), " Eff:");
   PrintInputs(&i, node->op()->ControlInputCount(), " Ctrl:");
 }


 void GraphC1Visualizer::PrintType(Node* node) {
   if (NodeProperties::IsTyped(node)) {
     Type* type = NodeProperties::GetType(node);
     os_ << " type:";
     type->PrintTo(os_);
   }
 }


 void GraphC1Visualizer::PrintSchedule(const char* phase,
                                       const Schedule* schedule,
                                       const SourcePositionTable* positions,
                                       const InstructionSequence* instructions) {
   Tag tag(this, "cfg");
   PrintStringProperty("name", phase);
   const BasicBlockVector* rpo = schedule->rpo_order();
   for (size_t i = 0; i < rpo->size(); i++) {
     BasicBlock* current = (*rpo)[i];
     Tag block_tag(this, "block");
     PrintBlockProperty("name", current->rpo_number());
     PrintIntProperty("from_bci", -1);
     PrintIntProperty("to_bci", -1);

     PrintIndent();
     os_ << "predecessors";
     for (BasicBlock* predecessor : current->predecessors()) {
       os_ << " \"B" << predecessor->rpo_number() << "\"";
     }
     os_ << "\n";

     PrintIndent();
     os_ << "successors";
     for (BasicBlock* successor : current->successors()) {
       os_ << " \"B" << successor->rpo_number() << "\"";
     }
     os_ << "\n";

     PrintIndent();
     os_ << "xhandlers\n";

     PrintIndent();
     os_ << "flags\n";

     if (current->dominator() != nullptr) {
       PrintBlockProperty("dominator", current->dominator()->rpo_number());
     }

     PrintIntProperty("loop_depth", current->loop_depth());

     const InstructionBlock* instruction_block =
         instructions->InstructionBlockAt(
             RpoNumber::FromInt(current->rpo_number()));
     if (instruction_block->code_start() >= 0) {
       int first_index = instruction_block->first_instruction_index();
       int last_index = instruction_block->last_instruction_index();
       PrintIntProperty(
           "first_lir_id",
           LifetimePosition::GapFromInstructionIndex(first_index).value());
       PrintIntProperty("last_lir_id",
                        LifetimePosition::InstructionFromInstructionIndex(
                            last_index).value());
     }

     {
       Tag states_tag(this, "states");
       Tag locals_tag(this, "locals");
       int total = 0;
       for (BasicBlock::const_iterator i = current->begin(); i != current->end();
            ++i) {
         if ((*i)->opcode() == IrOpcode::kPhi) total++;
       }
       PrintIntProperty("size", total);
       PrintStringProperty("method", "None");
       int index = 0;
       for (BasicBlock::const_iterator i = current->begin(); i != current->end();
            ++i) {
         if ((*i)->opcode() != IrOpcode::kPhi) continue;
         PrintIndent();
         os_ << index << " ";
         PrintNodeId(*i);
         os_ << " [";
         PrintInputs(*i);
         os_ << "]\n";
         index++;
       }
     }

     {
       Tag HIR_tag(this, "HIR");
       for (BasicBlock::const_iterator i = current->begin(); i != current->end();
            ++i) {
         Node* node = *i;
         if (node->opcode() == IrOpcode::kPhi) continue;
         int uses = node->UseCount();
         PrintIndent();
         os_ << "0 " << uses << " ";
         PrintNode(node);
         if (FLAG_trace_turbo_types) {
           os_ << " ";
           PrintType(node);
         }
         if (positions != nullptr) {
           SourcePosition position = positions->GetSourcePosition(node);
           if (position.IsKnown()) {
             os_ << " pos:" << position.raw();
           }
         }
         os_ << " <|@\n";
       }

       BasicBlock::Control control = current->control();
       if (control != BasicBlock::kNone) {
         PrintIndent();
         os_ << "0 0 ";
         if (current->control_input() != nullptr) {
           PrintNode(current->control_input());
         } else {
           os_ << -1 - current->rpo_number() << " Goto";
         }
         os_ << " ->";
         for (BasicBlock* successor : current->successors()) {
           os_ << " B" << successor->rpo_number();
         }
         if (FLAG_trace_turbo_types && current->control_input() != nullptr) {
           os_ << " ";
           PrintType(current->control_input());
         }
         os_ << " <|@\n";
       }
     }

     if (instructions != nullptr) {
       Tag LIR_tag(this, "LIR");
       for (int j = instruction_block->first_instruction_index();
            j <= instruction_block->last_instruction_index(); j++) {
         PrintIndent();
         PrintableInstruction printable = {
             RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN),
             instructions->InstructionAt(j)};
         os_ << j << " " << printable << " <|@\n";
       }
     }
   }
 }


 void GraphC1Visualizer::PrintLiveRanges(const char* phase,
                                         const RegisterAllocationData* data) {
   Tag tag(this, "intervals");
   PrintStringProperty("name", phase);

   for (const TopLevelLiveRange* range : data->fixed_double_live_ranges()) {
     PrintLiveRangeChain(range, "fixed");
   }

   for (const TopLevelLiveRange* range : data->fixed_live_ranges()) {
     PrintLiveRangeChain(range, "fixed");
   }

   for (const TopLevelLiveRange* range : data->live_ranges()) {
     PrintLiveRangeChain(range, "object");
   }
 }

 void GraphC1Visualizer::PrintLiveRangeChain(const TopLevelLiveRange* range,
                                             const char* type) {
   if (range == nullptr || range->IsEmpty()) return;
   int vreg = range->vreg();
   for (const LiveRange* child = range; child != nullptr;
        child = child->next()) {
     PrintLiveRange(child, type, vreg);
   }
 }

 void GraphC1Visualizer::PrintLiveRange(const LiveRange* range, const char* type,
                                        int vreg) {
   if (range != nullptr && !range->IsEmpty()) {
     PrintIndent();
     os_ << vreg << ":" << range->relative_id() << " " << type;
     if (range->HasRegisterAssigned()) {
       AllocatedOperand op = AllocatedOperand::cast(range->GetAssignedOperand());
       if (op.IsRegister()) {
         os_ << " \"" << op.GetRegister().ToString() << "\"";
       } else if (op.IsDoubleRegister()) {
         os_ << " \"" << op.GetDoubleRegister().ToString() << "\"";
       } else {
         DCHECK(op.IsFloatRegister());
         os_ << " \"" << op.GetFloatRegister().ToString() << "\"";
       }
     } else if (range->spilled()) {
       const TopLevelLiveRange* top = range->TopLevel();
       int index = -1;
       if (top->HasSpillRange()) {
         index = kMaxInt;  // This hasn't been set yet.
       } else if (top->GetSpillOperand()->IsConstant()) {
         os_ << " \"const(nostack):"
             << ConstantOperand::cast(top->GetSpillOperand())->virtual_register()
             << "\"";
       } else {
         index = AllocatedOperand::cast(top->GetSpillOperand())->index();
         if (top->kind() == FP_REGISTERS) {
           os_ << " \"double_stack:" << index << "\"";
         } else if (top->kind() == GENERAL_REGISTERS) {
           os_ << " \"stack:" << index << "\"";
         }
       }
     }

     os_ << " " << vreg;
     for (const UseInterval* interval = range->first_interval();
          interval != nullptr; interval = interval->next()) {
       os_ << " [" << interval->start().value() << ", "
           << interval->end().value() << "[";
     }

     UsePosition* current_pos = range->first_pos();
     while (current_pos != nullptr) {
       if (current_pos->RegisterIsBeneficial() || FLAG_trace_all_uses) {
         os_ << " " << current_pos->pos().value() << " M";
       }
       current_pos = current_pos->next();
     }

     os_ << " \"\"\n";
   }
 }


 std::ostream& operator<<(std::ostream& os, const AsC1VCompilation& ac) {
   base::AccountingAllocator allocator;
   Zone tmp_zone(&allocator);
   GraphC1Visualizer(os, &tmp_zone).PrintCompilation(ac.info_);
   return os;
 }


 std::ostream& operator<<(std::ostream& os, const AsC1V& ac) {
   base::AccountingAllocator allocator;
   Zone tmp_zone(&allocator);
   GraphC1Visualizer(os, &tmp_zone)
       .PrintSchedule(ac.phase_, ac.schedule_, ac.positions_, ac.instructions_);
   return os;
 }


 std::ostream& operator<<(std::ostream& os,
                          const AsC1VRegisterAllocationData& ac) {
   base::AccountingAllocator allocator;
   Zone tmp_zone(&allocator);
   GraphC1Visualizer(os, &tmp_zone).PrintLiveRanges(ac.phase_, ac.data_);
   return os;
 }

 const int kUnvisited = 0;
 const int kOnStack = 1;
 const int kVisited = 2;

 std::ostream& operator<<(std::ostream& os, const AsRPO& ar) {
   base::AccountingAllocator allocator;
   Zone local_zone(&allocator);

   // Do a post-order depth-first search on the RPO graph. For every node,
   // print:
   //
   //   - the node id
   //   - the operator mnemonic
   //   - in square brackets its parameter (if present)
   //   - in parentheses the list of argument ids and their mnemonics
   //   - the node type (if it is typed)

   // Post-order guarantees that all inputs of a node will be printed before
   // the node itself, if there are no cycles. Any cycles are broken
   // arbitrarily.

   ZoneVector<byte> state(ar.graph.NodeCount(), kUnvisited, &local_zone);
   ZoneStack<Node*> stack(&local_zone);

   stack.push(ar.graph.end());
   state[ar.graph.end()->id()] = kOnStack;
   while (!stack.empty()) {
     Node* n = stack.top();
     bool pop = true;
     for (Node* const i : n->inputs()) {
       if (state[i->id()] == kUnvisited) {
         state[i->id()] = kOnStack;
         stack.push(i);
         pop = false;
         break;
       }
     }
     if (pop) {
       state[n->id()] = kVisited;
       stack.pop();
       os << "#" << n->id() << ":" << *n->op() << "(";
       // Print the inputs.
       int j = 0;
       for (Node* const i : n->inputs()) {
         if (j++ > 0) os << ", ";
         os << "#" << SafeId(i) << ":" << SafeMnemonic(i);
       }
       os << ")";
       // Print the node type, if any.
       if (NodeProperties::IsTyped(n)) {
         os << "  [Type: ";
         NodeProperties::GetType(n)->PrintTo(os);
         os << "]";
       }
       os << std::endl;
     }
   }
   return os;
 }
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
	// Copyright 2013 the V8 project authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "src/compiler/graph-visualizer.h"

	#include <sstream>
	#include <string>

	#include "src/code-stubs.h"
	#include "src/compiler/all-nodes.h"
	#include "src/compiler/graph.h"
	#include "src/compiler/node.h"
	#include "src/compiler/node-properties.h"
	#include "src/compiler/opcodes.h"
	#include "src/compiler/operator.h"
	#include "src/compiler/operator-properties.h"
	#include "src/compiler/register-allocator.h"
	#include "src/compiler/schedule.h"
	#include "src/compiler/scheduler.h"
	#include "src/interpreter/bytecodes.h"
	#include "src/ostreams.h"

	namespace v8 {
	namespace internal {
	namespace compiler {

	base::SmartArrayPointer<const char> GetVisualizerLogFileName(
	CompilationInfo* info, const char* phase, const char* suffix) {
	EmbeddedVector<char, 256> filename(0);
	base::SmartArrayPointer<char> debug_name = info->GetDebugName();
	if (strlen(debug_name.get()) > 0) {
	SNPrintF(filename, "turbo-%s", debug_name.get());
	} else if (info->has_shared_info()) {
	SNPrintF(filename, "turbo-%p", static_cast<void*>(info));
	} else {
	SNPrintF(filename, "turbo-none-%s", phase);
	}
	std::replace(filename.start(), filename.start() + filename.length(), ' ',
	'_');

	EmbeddedVector<char, 256> full_filename;
	if (phase == nullptr) {
	SNPrintF(full_filename, "%s.%s", filename.start(), suffix);
	} else {
	SNPrintF(full_filename, "%s-%s.%s", filename.start(), phase, suffix);
	}

	char* buffer = new char[full_filename.length() + 1];
	memcpy(buffer, full_filename.start(), full_filename.length());
	buffer[full_filename.length()] = '\0';
	return base::SmartArrayPointer<const char>(buffer);
	}


	static int SafeId(Node* node) { return node == nullptr ? -1 : node->id(); }
	static const char* SafeMnemonic(Node* node) {
	return node == nullptr ? "null" : node->op()->mnemonic();
	}

	#define DEAD_COLOR "#999999"

	class Escaped {
	public:
	explicit Escaped(const std::ostringstream& os,
	const char* escaped_chars = "<>\|{}")
	: str_(os.str()), escaped_chars_(escaped_chars) {}

	friend std::ostream& operator<<(std::ostream& os, const Escaped& e) {
	for (std::string::const_iterator i = e.str_.begin(); i != e.str_.end();
	++i) {
	if (e.needs_escape(*i)) os << "\\";
	os << *i;
	}
	return os;
	}

	private:
	bool needs_escape(char ch) const {
	for (size_t i = 0; i < strlen(escaped_chars_); ++i) {
	if (ch == escaped_chars_[i]) return true;
	}
	return false;
	}

	const std::string str_;
	const char* const escaped_chars_;
	};

	class JSONGraphNodeWriter {
	public:
	JSONGraphNodeWriter(std::ostream& os, Zone* zone, const Graph* graph,
	const SourcePositionTable* positions)
	: os_(os), all_(zone, graph), positions_(positions), first_node_(true) {}

	void Print() {
	for (Node* const node : all_.live) PrintNode(node);
	os_ << "\n";
	}

	void PrintNode(Node* node) {
	if (first_node_) {
	first_node_ = false;
	} else {
	os_ << ",\n";
	}
	std::ostringstream label;
	label << *node->op();
	os_ << "{\"id\":" << SafeId(node) << ",\"label\":\"" << Escaped(label, "\"")
	<< "\"";
	IrOpcode::Value opcode = node->opcode();
	if (IrOpcode::IsPhiOpcode(opcode)) {
	os_ << ",\"rankInputs\":[0," << NodeProperties::FirstControlIndex(node)
	<< "]";
	os_ << ",\"rankWithInput\":[" << NodeProperties::FirstControlIndex(node)
	<< "]";
	} else if (opcode == IrOpcode::kIfTrue \|\| opcode == IrOpcode::kIfFalse \|\|
	opcode == IrOpcode::kLoop) {
	os_ << ",\"rankInputs\":[" << NodeProperties::FirstControlIndex(node)
	<< "]";
	}
	if (opcode == IrOpcode::kBranch) {
	os_ << ",\"rankInputs\":[0]";
	}
	SourcePosition position = positions_->GetSourcePosition(node);
	if (position.IsKnown()) {
	os_ << ",\"pos\":" << position.raw();
	}
	os_ << ",\"opcode\":\"" << IrOpcode::Mnemonic(node->opcode()) << "\"";
	os_ << ",\"control\":" << (NodeProperties::IsControl(node) ? "true"
	: "false");
	if (NodeProperties::IsTyped(node)) {
	Type* type = NodeProperties::GetType(node);
	std::ostringstream type_out;
	type->PrintTo(type_out);
	os_ << ",\"type\":\"" << Escaped(type_out, "\"") << "\"";
	}
	os_ << "}";
	}

	private:
	std::ostream& os_;
	AllNodes all_;
	const SourcePositionTable* positions_;
	bool first_node_;

	DISALLOW_COPY_AND_ASSIGN(JSONGraphNodeWriter);
	};


	class JSONGraphEdgeWriter {
	public:
	JSONGraphEdgeWriter(std::ostream& os, Zone* zone, const Graph* graph)
	: os_(os), all_(zone, graph), first_edge_(true) {}

	void Print() {
	for (Node* const node : all_.live) PrintEdges(node);
	os_ << "\n";
	}

	void PrintEdges(Node* node) {
	for (int i = 0; i < node->InputCount(); i++) {
	Node* input = node->InputAt(i);
	if (input == nullptr) continue;
	PrintEdge(node, i, input);
	}
	}

	void PrintEdge(Node* from, int index, Node* to) {
	if (first_edge_) {
	first_edge_ = false;
	} else {
	os_ << ",\n";
	}
	const char* edge_type = nullptr;
	if (index < NodeProperties::FirstValueIndex(from)) {
	edge_type = "unknown";
	} else if (index < NodeProperties::FirstContextIndex(from)) {
	edge_type = "value";
	} else if (index < NodeProperties::FirstFrameStateIndex(from)) {
	edge_type = "context";
	} else if (index < NodeProperties::FirstEffectIndex(from)) {
	edge_type = "frame-state";
	} else if (index < NodeProperties::FirstControlIndex(from)) {
	edge_type = "effect";
	} else {
	edge_type = "control";
	}
	os_ << "{\"source\":" << SafeId(to) << ",\"target\":" << SafeId(from)
	<< ",\"index\":" << index << ",\"type\":\"" << edge_type << "\"}";
	}

	private:
	std::ostream& os_;
	AllNodes all_;
	bool first_edge_;

	DISALLOW_COPY_AND_ASSIGN(JSONGraphEdgeWriter);
	};


	std::ostream& operator<<(std::ostream& os, const AsJSON& ad) {
	base::AccountingAllocator allocator;
	Zone tmp_zone(&allocator);
	os << "{\n\"nodes\":[";
	JSONGraphNodeWriter(os, &tmp_zone, &ad.graph, ad.positions).Print();
	os << "],\n\"edges\":[";
	JSONGraphEdgeWriter(os, &tmp_zone, &ad.graph).Print();
	os << "]}";
	return os;
	}


	class GraphC1Visualizer {
	public:
	GraphC1Visualizer(std::ostream& os, Zone* zone); // NOLINT

	void PrintCompilation(const CompilationInfo* info);
	void PrintSchedule(const char* phase, const Schedule* schedule,
	const SourcePositionTable* positions,
	const InstructionSequence* instructions);
	void PrintLiveRanges(const char* phase, const RegisterAllocationData* data);
	Zone* zone() const { return zone_; }

	private:
	void PrintIndent();
	void PrintStringProperty(const char* name, const char* value);
	void PrintLongProperty(const char* name, int64_t value);
	void PrintIntProperty(const char* name, int value);
	void PrintBlockProperty(const char* name, int rpo_number);
	void PrintNodeId(Node* n);
	void PrintNode(Node* n);
	void PrintInputs(Node* n);
	template <typename InputIterator>
	void PrintInputs(InputIterator* i, int count, const char* prefix);
	void PrintType(Node* node);

	void PrintLiveRange(const LiveRange* range, const char* type, int vreg);
	void PrintLiveRangeChain(const TopLevelLiveRange* range, const char* type);

	class Tag final BASE_EMBEDDED {
	public:
	Tag(GraphC1Visualizer* visualizer, const char* name) {
	name_ = name;
	visualizer_ = visualizer;
	visualizer->PrintIndent();
	visualizer_->os_ << "begin_" << name << "\n";
	visualizer->indent_++;
	}

	~Tag() {
	visualizer_->indent_--;
	visualizer_->PrintIndent();
	visualizer_->os_ << "end_" << name_ << "\n";
	DCHECK(visualizer_->indent_ >= 0);
	}

	private:
	GraphC1Visualizer* visualizer_;
	const char* name_;
	};

	std::ostream& os_;
	int indent_;
	Zone* zone_;

	DISALLOW_COPY_AND_ASSIGN(GraphC1Visualizer);
	};


	void GraphC1Visualizer::PrintIndent() {
	for (int i = 0; i < indent_; i++) {
	os_ << " ";
	}
	}


	GraphC1Visualizer::GraphC1Visualizer(std::ostream& os, Zone* zone)
	: os_(os), indent_(0), zone_(zone) {}


	void GraphC1Visualizer::PrintStringProperty(const char* name,
	const char* value) {
	PrintIndent();
	os_ << name << " \"" << value << "\"\n";
	}


	void GraphC1Visualizer::PrintLongProperty(const char* name, int64_t value) {
	PrintIndent();
	os_ << name << " " << static_cast<int>(value / 1000) << "\n";
	}


	void GraphC1Visualizer::PrintBlockProperty(const char* name, int rpo_number) {
	PrintIndent();
	os_ << name << " \"B" << rpo_number << "\"\n";
	}


	void GraphC1Visualizer::PrintIntProperty(const char* name, int value) {
	PrintIndent();
	os_ << name << " " << value << "\n";
	}


	void GraphC1Visualizer::PrintCompilation(const CompilationInfo* info) {
	Tag tag(this, "compilation");
	base::SmartArrayPointer<char> name = info->GetDebugName();
	if (info->IsOptimizing()) {
	PrintStringProperty("name", name.get());
	PrintIndent();
	os_ << "method \"" << name.get() << ":" << info->optimization_id()
	<< "\"\n";
	} else {
	PrintStringProperty("name", name.get());
	PrintStringProperty("method", "stub");
	}
	PrintLongProperty("date",
	static_cast<int64_t>(base::OS::TimeCurrentMillis()));
	}


	void GraphC1Visualizer::PrintNodeId(Node* n) { os_ << "n" << SafeId(n); }


	void GraphC1Visualizer::PrintNode(Node* n) {
	PrintNodeId(n);
	os_ << " " << *n->op() << " ";
	PrintInputs(n);
	}


	template <typename InputIterator>
	void GraphC1Visualizer::PrintInputs(InputIterator* i, int count,
	const char* prefix) {
	if (count > 0) {
	os_ << prefix;
	}
	while (count > 0) {
	os_ << " ";
	PrintNodeId(**i);
	++(*i);
	count--;
	}
	}


	void GraphC1Visualizer::PrintInputs(Node* node) {
	auto i = node->inputs().begin();
	PrintInputs(&i, node->op()->ValueInputCount(), " ");
	PrintInputs(&i, OperatorProperties::GetContextInputCount(node->op()),
	" Ctx:");
	PrintInputs(&i, OperatorProperties::GetFrameStateInputCount(node->op()),
	" FS:");
	PrintInputs(&i, node->op()->EffectInputCount(), " Eff:");
	PrintInputs(&i, node->op()->ControlInputCount(), " Ctrl:");
	}


	void GraphC1Visualizer::PrintType(Node* node) {
	if (NodeProperties::IsTyped(node)) {
	Type* type = NodeProperties::GetType(node);
	os_ << " type:";
	type->PrintTo(os_);
	}
	}


	void GraphC1Visualizer::PrintSchedule(const char* phase,
	const Schedule* schedule,
	const SourcePositionTable* positions,
	const InstructionSequence* instructions) {
	Tag tag(this, "cfg");
	PrintStringProperty("name", phase);
	const BasicBlockVector* rpo = schedule->rpo_order();
	for (size_t i = 0; i < rpo->size(); i++) {
	BasicBlock* current = (*rpo)[i];
	Tag block_tag(this, "block");
	PrintBlockProperty("name", current->rpo_number());
	PrintIntProperty("from_bci", -1);
	PrintIntProperty("to_bci", -1);

	PrintIndent();
	os_ << "predecessors";
	for (BasicBlock* predecessor : current->predecessors()) {
	os_ << " \"B" << predecessor->rpo_number() << "\"";
	}
	os_ << "\n";

	PrintIndent();
	os_ << "successors";
	for (BasicBlock* successor : current->successors()) {
	os_ << " \"B" << successor->rpo_number() << "\"";
	}
	os_ << "\n";

	PrintIndent();
	os_ << "xhandlers\n";

	PrintIndent();
	os_ << "flags\n";

	if (current->dominator() != nullptr) {
	PrintBlockProperty("dominator", current->dominator()->rpo_number());
	}

	PrintIntProperty("loop_depth", current->loop_depth());

	const InstructionBlock* instruction_block =
	instructions->InstructionBlockAt(
	RpoNumber::FromInt(current->rpo_number()));
	if (instruction_block->code_start() >= 0) {
	int first_index = instruction_block->first_instruction_index();
	int last_index = instruction_block->last_instruction_index();
	PrintIntProperty(
	"first_lir_id",
	LifetimePosition::GapFromInstructionIndex(first_index).value());
	PrintIntProperty("last_lir_id",
	LifetimePosition::InstructionFromInstructionIndex(
	last_index).value());
	}

	{
	Tag states_tag(this, "states");
	Tag locals_tag(this, "locals");
	int total = 0;
	for (BasicBlock::const_iterator i = current->begin(); i != current->end();
	++i) {
	if ((*i)->opcode() == IrOpcode::kPhi) total++;
	}
	PrintIntProperty("size", total);
	PrintStringProperty("method", "None");
	int index = 0;
	for (BasicBlock::const_iterator i = current->begin(); i != current->end();
	++i) {
	if ((*i)->opcode() != IrOpcode::kPhi) continue;
	PrintIndent();
	os_ << index << " ";
	PrintNodeId(*i);
	os_ << " [";
	PrintInputs(*i);
	os_ << "]\n";
	index++;
	}
	}

	{
	Tag HIR_tag(this, "HIR");
	for (BasicBlock::const_iterator i = current->begin(); i != current->end();
	++i) {
	Node* node = *i;
	if (node->opcode() == IrOpcode::kPhi) continue;
	int uses = node->UseCount();
	PrintIndent();
	os_ << "0 " << uses << " ";
	PrintNode(node);
	if (FLAG_trace_turbo_types) {
	os_ << " ";
	PrintType(node);
	}
	if (positions != nullptr) {
	SourcePosition position = positions->GetSourcePosition(node);
	if (position.IsKnown()) {
	os_ << " pos:" << position.raw();
	}
	}
	os_ << " <\|@\n";
	}

	BasicBlock::Control control = current->control();
	if (control != BasicBlock::kNone) {
	PrintIndent();
	os_ << "0 0 ";
	if (current->control_input() != nullptr) {
	PrintNode(current->control_input());
	} else {
	os_ << -1 - current->rpo_number() << " Goto";
	}
	os_ << " ->";
	for (BasicBlock* successor : current->successors()) {
	os_ << " B" << successor->rpo_number();
	}
	if (FLAG_trace_turbo_types && current->control_input() != nullptr) {
	os_ << " ";
	PrintType(current->control_input());
	}
	os_ << " <\|@\n";
	}
	}

	if (instructions != nullptr) {
	Tag LIR_tag(this, "LIR");
	for (int j = instruction_block->first_instruction_index();
	j <= instruction_block->last_instruction_index(); j++) {
	PrintIndent();
	PrintableInstruction printable = {
	RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN),
	instructions->InstructionAt(j)};
	os_ << j << " " << printable << " <\|@\n";
	}
	}
	}
	}


	void GraphC1Visualizer::PrintLiveRanges(const char* phase,
	const RegisterAllocationData* data) {
	Tag tag(this, "intervals");
	PrintStringProperty("name", phase);

	for (const TopLevelLiveRange* range : data->fixed_double_live_ranges()) {
	PrintLiveRangeChain(range, "fixed");
	}

	for (const TopLevelLiveRange* range : data->fixed_live_ranges()) {
	PrintLiveRangeChain(range, "fixed");
	}

	for (const TopLevelLiveRange* range : data->live_ranges()) {
	PrintLiveRangeChain(range, "object");
	}
	}

	void GraphC1Visualizer::PrintLiveRangeChain(const TopLevelLiveRange* range,
	const char* type) {
	if (range == nullptr \|\| range->IsEmpty()) return;
	int vreg = range->vreg();
	for (const LiveRange* child = range; child != nullptr;
	child = child->next()) {
	PrintLiveRange(child, type, vreg);
	}
	}

	void GraphC1Visualizer::PrintLiveRange(const LiveRange* range, const char* type,
	int vreg) {
	if (range != nullptr && !range->IsEmpty()) {
	PrintIndent();
	os_ << vreg << ":" << range->relative_id() << " " << type;
	if (range->HasRegisterAssigned()) {
	AllocatedOperand op = AllocatedOperand::cast(range->GetAssignedOperand());
	if (op.IsRegister()) {
	os_ << " \"" << op.GetRegister().ToString() << "\"";
	} else if (op.IsDoubleRegister()) {
	os_ << " \"" << op.GetDoubleRegister().ToString() << "\"";
	} else {
	DCHECK(op.IsFloatRegister());
	os_ << " \"" << op.GetFloatRegister().ToString() << "\"";
	}
	} else if (range->spilled()) {
	const TopLevelLiveRange* top = range->TopLevel();
	int index = -1;
	if (top->HasSpillRange()) {
	index = kMaxInt; // This hasn't been set yet.
	} else if (top->GetSpillOperand()->IsConstant()) {
	os_ << " \"const(nostack):"
	<< ConstantOperand::cast(top->GetSpillOperand())->virtual_register()
	<< "\"";
	} else {
	index = AllocatedOperand::cast(top->GetSpillOperand())->index();
	if (top->kind() == FP_REGISTERS) {
	os_ << " \"double_stack:" << index << "\"";
	} else if (top->kind() == GENERAL_REGISTERS) {
	os_ << " \"stack:" << index << "\"";
	}
	}
	}

	os_ << " " << vreg;
	for (const UseInterval* interval = range->first_interval();
	interval != nullptr; interval = interval->next()) {
	os_ << " [" << interval->start().value() << ", "
	<< interval->end().value() << "[";
	}

	UsePosition* current_pos = range->first_pos();
	while (current_pos != nullptr) {
	if (current_pos->RegisterIsBeneficial() \|\| FLAG_trace_all_uses) {
	os_ << " " << current_pos->pos().value() << " M";
	}
	current_pos = current_pos->next();
	}

	os_ << " \"\"\n";
	}
	}


	std::ostream& operator<<(std::ostream& os, const AsC1VCompilation& ac) {
	base::AccountingAllocator allocator;
	Zone tmp_zone(&allocator);
	GraphC1Visualizer(os, &tmp_zone).PrintCompilation(ac.info_);
	return os;
	}


	std::ostream& operator<<(std::ostream& os, const AsC1V& ac) {
	base::AccountingAllocator allocator;
	Zone tmp_zone(&allocator);
	GraphC1Visualizer(os, &tmp_zone)
	.PrintSchedule(ac.phase_, ac.schedule_, ac.positions_, ac.instructions_);
	return os;
	}


	std::ostream& operator<<(std::ostream& os,
	const AsC1VRegisterAllocationData& ac) {
	base::AccountingAllocator allocator;
	Zone tmp_zone(&allocator);
	GraphC1Visualizer(os, &tmp_zone).PrintLiveRanges(ac.phase_, ac.data_);
	return os;
	}

	const int kUnvisited = 0;
	const int kOnStack = 1;
	const int kVisited = 2;

	std::ostream& operator<<(std::ostream& os, const AsRPO& ar) {
	base::AccountingAllocator allocator;
	Zone local_zone(&allocator);

	// Do a post-order depth-first search on the RPO graph. For every node,
	// print:
	//
	// - the node id
	// - the operator mnemonic
	// - in square brackets its parameter (if present)
	// - in parentheses the list of argument ids and their mnemonics
	// - the node type (if it is typed)

	// Post-order guarantees that all inputs of a node will be printed before
	// the node itself, if there are no cycles. Any cycles are broken
	// arbitrarily.

	ZoneVector<byte> state(ar.graph.NodeCount(), kUnvisited, &local_zone);
	ZoneStack<Node*> stack(&local_zone);

	stack.push(ar.graph.end());
	state[ar.graph.end()->id()] = kOnStack;
	while (!stack.empty()) {
	Node* n = stack.top();
	bool pop = true;
	for (Node* const i : n->inputs()) {
	if (state[i->id()] == kUnvisited) {
	state[i->id()] = kOnStack;
	stack.push(i);
	pop = false;
	break;
	}
	}
	if (pop) {
	state[n->id()] = kVisited;
	stack.pop();
	os << "#" << n->id() << ":" << *n->op() << "(";
	// Print the inputs.
	int j = 0;
	for (Node* const i : n->inputs()) {
	if (j++ > 0) os << ", ";
	os << "#" << SafeId(i) << ":" << SafeMnemonic(i);
	}
	os << ")";
	// Print the node type, if any.
	if (NodeProperties::IsTyped(n)) {
	os << " [Type: ";
	NodeProperties::GetType(n)->PrintTo(os);
	os << "]";
	}
	os << std::endl;
	}
	}
	return os;
	}
	} // namespace compiler
	} // namespace internal
	} // namespace v8