CIRCT  19.0.0git
Utilities.cpp
Go to the documentation of this file.
1 //===- Utilities.cpp - Library of scheduling utilities --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains useful helpers for scheduler implementations.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 
15 #include "mlir/IR/Operation.h"
16 #include "mlir/Support/IndentedOstream.h"
17 
18 using namespace circt;
19 using namespace circt::scheduling;
20 
22  HandleOpFn fun) {
23  auto &allOps = prob.getOperations();
24  SmallVector<Operation *> unhandledOps;
25  unhandledOps.insert(unhandledOps.begin(), allOps.begin(), allOps.end());
26 
27  while (!unhandledOps.empty()) {
28  // Remember how many unhandled operations we have at the beginning of this
29  // attempt. This is a fail-safe for cyclic dependence graphs: If we do not
30  // successfully handle at least one operation per attempt, we have
31  // encountered a cycle.
32  unsigned numUnhandledBefore = unhandledOps.size();
33 
34  // Set up the worklist for this attempt, and initialize it in reverse order
35  // so that we can pop off its back later.
36  SmallVector<Operation *> worklist;
37  worklist.insert(worklist.begin(), unhandledOps.rbegin(),
38  unhandledOps.rend());
39  unhandledOps.clear();
40 
41  while (!worklist.empty()) {
42  Operation *op = worklist.pop_back_val();
43  auto res = fun(op);
44  if (failed(res))
45  unhandledOps.push_back(op);
46  }
47 
48  if (numUnhandledBefore == unhandledOps.size())
49  return prob.getContainingOp()->emitError() << "dependence cycle detected";
50  }
51 
52  return success();
53 }
54 
55 void scheduling::dumpAsDOT(Problem &prob, StringRef fileName) {
56  std::error_code ec;
57  llvm::raw_fd_ostream out(fileName, ec);
58  scheduling::dumpAsDOT(prob, out);
59  out.close();
60 }
61 
62 void scheduling::dumpAsDOT(Problem &prob, raw_ostream &stream) {
63  mlir::raw_indented_ostream os(stream);
64 
65  os << "digraph G {\n";
66  os.indent();
67  os << "rankdir = TB // top to bottom\n";
68  os << "splines = spline // draw edges and route around nodes\n";
69  os << "nodesep = 0.2 // horizontal compression\n";
70  os << "ranksep = 0.5 // vertical compression\n";
71  os << "node [shape=box] // default node style\n";
72  os << "compound = true // allow edges between subgraphs\n";
73 
74  auto startHTMLLabel = [&os]() {
75  os << "<<TABLE BORDER=\"0\">\n";
76  os.indent();
77  };
78  auto emitTableHeader = [&os](std::string str) {
79  os << "<TR><TD COLSPAN=\"2\"><B>" << str << "</B></TD></TR>\n";
80  };
81  auto emitTableRow = [&os](std::pair<std::string, std::string> &kv) {
82  os << "<TR><TD ALIGN=\"LEFT\">" << std::get<0>(kv)
83  << ":</TD><TD ALIGN=\"RIGHT\">" << std::get<1>(kv) << "</TD></TR>\n";
84  };
85  auto endHTMLLabel = [&os]() {
86  os.unindent();
87  os << "</TABLE>>";
88  };
89 
90  DenseMap<Operation *, std::string> nodes;
91 
92  os << "\n// Operations\n";
93  os << "subgraph dependence_graph {\n";
94  os.indent();
95 
96  for (auto *op : prob.getOperations()) {
97  auto id = std::to_string(nodes.size());
98  auto node = "op" + id;
99  nodes[op] = node;
100 
101  os << node << " [label = ";
102  startHTMLLabel();
103  emitTableHeader(("#" + id + " " + op->getName().getStringRef()).str());
104  for (auto &kv : prob.getProperties(op))
105  emitTableRow(kv);
106  endHTMLLabel();
107  os << "]\n";
108  }
109 
110  os << "\n// Dependences\n";
111  for (auto *op : prob.getOperations())
112  for (auto &dep : prob.getDependences(op)) {
113  os << nodes[dep.getSource()] << " -> " << nodes[dep.getDestination()]
114  << " [";
115  if (dep.isAuxiliary())
116  os << "style = dashed ";
117  if (auto props = prob.getProperties(dep); !props.empty()) {
118  os << "label = ";
119  startHTMLLabel();
120  for (auto &kv : props)
121  emitTableRow(kv);
122  endHTMLLabel();
123  }
124  os << "]\n";
125  }
126  os.unindent();
127  os << "}\n";
128 
129  os << "\n// Operator types\n";
130  os << "subgraph cluster_operator_types {\n";
131  os.indent();
132  os << "label = \"Operator types\"\n";
133  os << "style = filled fillcolor = lightgray\n";
134  os << "node [style = \"rounded,filled\" fillcolor = white]\n";
135  unsigned oprId = 0;
136  for (auto opr : prob.getOperatorTypes()) {
137  os << "opr" << oprId << " [label = ";
138  startHTMLLabel();
139  emitTableHeader(opr.str());
140  for (auto &kv : prob.getProperties(opr))
141  emitTableRow(kv);
142  endHTMLLabel();
143  os << "]\n";
144  ++oprId;
145  }
146  os.unindent();
147  os << "}\n";
148 
149  if (auto instanceProps = prob.getProperties(); !instanceProps.empty()) {
150  os << "\n// Instance\n";
151  os << "instance [shape = note, label = ";
152  startHTMLLabel();
153  emitTableHeader("Instance");
154  for (auto &kv : instanceProps)
155  emitTableRow(kv);
156  endHTMLLabel();
157  os << "]\n";
158  }
159 
160  os.unindent();
161  os << "}\n";
162 }
This class models the most basic scheduling problem.
Definition: Problems.h:87
virtual PropertyStringVector getProperties(Operation *op)
Definition: Problems.cpp:58
const OperatorTypeSet & getOperatorTypes()
Return the set of operator types.
Definition: Problems.h:195
DependenceRange getDependences(Operation *op)
Return a range object to transparently iterate over op's incoming 1) implicit def-use dependences (ba...
Definition: Problems.cpp:53
const OperationSet & getOperations()
Return the set of operations.
Definition: Problems.h:178
Operation * getContainingOp()
Return the operation containing this problem, e.g. to emit diagnostics.
Definition: Problems.h:171
LogicalResult handleOperationsInTopologicalOrder(Problem &prob, HandleOpFn fun)
Visit prob's operations in topological order, using an internal worklist.
Definition: Utilities.cpp:21
void dumpAsDOT(Problem &prob, StringRef fileName)
Export prob as a DOT graph into fileName.
Definition: Utilities.cpp:55
std::function< LogicalResult(Operation *)> HandleOpFn
Definition: Utilities.h:25
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21