1// Copyright (c) 2016 Google Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "tools/cfg/bin_to_dot.h"
16
17#include <cassert>
18#include <iostream>
19#include <utility>
20#include <vector>
21
22#include "source/assembly_grammar.h"
23#include "source/name_mapper.h"
24
25namespace {
26
27const char* kMergeStyle = "style=dashed";
28const char* kContinueStyle = "style=dotted";
29
30// A DotConverter can be used to dump the GraphViz "dot" graph for
31// a SPIR-V module.
32class DotConverter {
33 public:
34  DotConverter(spvtools::NameMapper name_mapper, std::iostream* out)
35      : name_mapper_(std::move(name_mapper)), out_(*out) {}
36
37  // Emits the graph preamble.
38  void Begin() const {
39    out_ << "digraph {\n";
40    // Emit a simple legend
41    out_ << "legend_merge_src [shape=plaintext, label=\"\"];\n"
42         << "legend_merge_dest [shape=plaintext, label=\"\"];\n"
43         << "legend_merge_src -> legend_merge_dest [label=\" merge\","
44         << kMergeStyle << "];\n"
45         << "legend_continue_src [shape=plaintext, label=\"\"];\n"
46         << "legend_continue_dest [shape=plaintext, label=\"\"];\n"
47         << "legend_continue_src -> legend_continue_dest [label=\" continue\","
48         << kContinueStyle << "];\n";
49  }
50  // Emits the graph postamble.
51  void End() const { out_ << "}\n"; }
52
53  // Emits the Dot commands for the given instruction.
54  spv_result_t HandleInstruction(const spv_parsed_instruction_t& inst);
55
56 private:
57  // Ends processing for the current block, emitting its dot code.
58  void FlushBlock(const std::vector<uint32_t>& successors);
59
60  // The ID of the current function, or 0 if outside of a function.
61  uint32_t current_function_id_ = 0;
62
63  // The ID of the current basic block, or 0 if outside of a block.
64  uint32_t current_block_id_ = 0;
65
66  // Have we completed processing for the entry block to this function?
67  bool seen_function_entry_block_ = false;
68
69  // The Id of the merge block for this block if it exists, or 0 otherwise.
70  uint32_t merge_ = 0;
71  // The Id of the continue target block for this block if it exists, or 0
72  // otherwise.
73  uint32_t continue_target_ = 0;
74
75  // An object for mapping Ids to names.
76  spvtools::NameMapper name_mapper_;
77
78  // The output stream.
79  std::ostream& out_;
80};
81
82spv_result_t DotConverter::HandleInstruction(
83    const spv_parsed_instruction_t& inst) {
84  switch (spv::Op(inst.opcode)) {
85    case spv::Op::OpFunction:
86      current_function_id_ = inst.result_id;
87      seen_function_entry_block_ = false;
88      break;
89    case spv::Op::OpFunctionEnd:
90      current_function_id_ = 0;
91      break;
92
93    case spv::Op::OpLabel:
94      current_block_id_ = inst.result_id;
95      break;
96
97    case spv::Op::OpBranch:
98      FlushBlock({inst.words[1]});
99      break;
100    case spv::Op::OpBranchConditional:
101      FlushBlock({inst.words[2], inst.words[3]});
102      break;
103    case spv::Op::OpSwitch: {
104      std::vector<uint32_t> successors{inst.words[2]};
105      for (size_t i = 3; i < inst.num_operands; i += 2) {
106        successors.push_back(inst.words[inst.operands[i].offset]);
107      }
108      FlushBlock(successors);
109    } break;
110
111    case spv::Op::OpKill:
112    case spv::Op::OpReturn:
113    case spv::Op::OpUnreachable:
114    case spv::Op::OpReturnValue:
115      FlushBlock({});
116      break;
117
118    case spv::Op::OpLoopMerge:
119      merge_ = inst.words[1];
120      continue_target_ = inst.words[2];
121      break;
122    case spv::Op::OpSelectionMerge:
123      merge_ = inst.words[1];
124      break;
125    default:
126      break;
127  }
128  return SPV_SUCCESS;
129}
130
131void DotConverter::FlushBlock(const std::vector<uint32_t>& successors) {
132  out_ << current_block_id_;
133  if (!seen_function_entry_block_) {
134    out_ << " [label=\"" << name_mapper_(current_block_id_) << "\nFn "
135         << name_mapper_(current_function_id_) << " entry\", shape=box];\n";
136  } else {
137    out_ << " [label=\"" << name_mapper_(current_block_id_) << "\"];\n";
138  }
139
140  for (auto successor : successors) {
141    out_ << current_block_id_ << " -> " << successor << ";\n";
142  }
143
144  if (merge_) {
145    out_ << current_block_id_ << " -> " << merge_ << " [" << kMergeStyle
146         << "];\n";
147  }
148  if (continue_target_) {
149    out_ << current_block_id_ << " -> " << continue_target_ << " ["
150         << kContinueStyle << "];\n";
151  }
152
153  // Reset the book-keeping for a block.
154  seen_function_entry_block_ = true;
155  merge_ = 0;
156  continue_target_ = 0;
157}
158
159spv_result_t HandleInstruction(
160    void* user_data, const spv_parsed_instruction_t* parsed_instruction) {
161  assert(user_data);
162  auto converter = static_cast<DotConverter*>(user_data);
163  return converter->HandleInstruction(*parsed_instruction);
164}
165
166}  // anonymous namespace
167
168spv_result_t BinaryToDot(const spv_const_context context, const uint32_t* words,
169                         size_t num_words, std::iostream* out,
170                         spv_diagnostic* diagnostic) {
171  // Invalid arguments return error codes, but don't necessarily generate
172  // diagnostics.  These are programmer errors, not user errors.
173  if (!diagnostic) return SPV_ERROR_INVALID_DIAGNOSTIC;
174  const spvtools::AssemblyGrammar grammar(context);
175  if (!grammar.isValid()) return SPV_ERROR_INVALID_TABLE;
176
177  spvtools::FriendlyNameMapper friendly_mapper(context, words, num_words);
178  DotConverter converter(friendly_mapper.GetNameMapper(), out);
179  converter.Begin();
180  if (auto error = spvBinaryParse(context, &converter, words, num_words,
181                                  nullptr, HandleInstruction, diagnostic)) {
182    return error;
183  }
184  converter.End();
185
186  return SPV_SUCCESS;
187}
188