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