CIRCT  18.0.0git
SplitLoops.cpp
Go to the documentation of this file.
1 //===- SplitLoops.cpp -----------------------------------------------------===//
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 
12 #include "mlir/IR/IRMapping.h"
13 #include "mlir/IR/ImplicitLocOpBuilder.h"
14 #include "mlir/Pass/Pass.h"
15 #include "llvm/ADT/SetVector.h"
16 #include "llvm/Support/Debug.h"
17 
18 #define DEBUG_TYPE "arc-split-loops"
19 
20 namespace circt {
21 namespace arc {
22 #define GEN_PASS_DEF_SPLITLOOPS
23 #include "circt/Dialect/Arc/ArcPasses.h.inc"
24 } // namespace arc
25 } // namespace circt
26 
27 using namespace circt;
28 using namespace arc;
29 using namespace hw;
30 
31 using llvm::SmallSetVector;
32 
33 //===----------------------------------------------------------------------===//
34 // Arc Splitter
35 //===----------------------------------------------------------------------===//
36 
37 namespace {
38 /// A value imported into a split.
39 struct ImportedValue {
40  /// Indicates where this value originates from. If true, the value is an input
41  /// of the original arc. If false the value is exported from a different
42  /// split.
43  unsigned isInput : 1;
44  /// The original arc's input number, or the result number of the split that
45  /// exports this value.
46  unsigned index : 15;
47  /// If this value is exported from a different split, this is that split's
48  /// index.
49  unsigned split : 16;
50 };
51 
52 /// A single arc split out from another arc.
53 struct Split {
54  Split(MLIRContext *context, unsigned index, const APInt &color)
55  : index(index), color(color), block(std::make_unique<Block>()),
56  builder(context) {
57  builder.setInsertionPointToStart(block.get());
58  }
59 
60  /// Map an input of the original arc into this split.
61  void importInput(BlockArgument arg) {
62  importedValues.push_back({true, arg.getArgNumber(), 0});
63  mapping.map(arg, block->addArgument(arg.getType(), arg.getLoc()));
64  }
65 
66  /// Map a value in a different split into this split.
67  void importFromOtherSplit(Value value, Split &otherSplit) {
68  auto resultIdx = otherSplit.exportValue(value);
69  importedValues.push_back({false, resultIdx, otherSplit.index});
70  mapping.map(value, block->addArgument(value.getType(), value.getLoc()));
71  }
72 
73  /// Export a value in this split as an output. Returns result number this
74  /// value will have.
75  unsigned exportValue(Value value) {
76  value = mapping.lookup(value);
77  auto result = exportedValueIndices.insert({value, exportedValues.size()});
78  if (result.second)
79  exportedValues.push_back(value);
80  return result.first->second;
81  }
82 
83  unsigned index;
84  APInt color;
85 
86  std::unique_ptr<Block> block;
87  OpBuilder builder;
88  IRMapping mapping;
89 
90  /// Where each value mapped to a block argument is coming from.
91  SmallVector<ImportedValue> importedValues;
92  /// Which values of this split are exposed as outputs.
93  SmallVector<Value> exportedValues;
94  SmallDenseMap<Value, unsigned> exportedValueIndices;
95 };
96 
97 /// Helper structure to split one arc into multiple ones.
98 struct Splitter {
99  Splitter(MLIRContext *context, Location loc) : context(context), loc(loc) {}
100  void run(Block &block, DenseMap<Operation *, APInt> &coloring);
101  Split &getSplit(const APInt &color);
102 
103  MLIRContext *context;
104  Location loc;
105 
106  /// A split for each distinct operation coloring in the original arc.
107  SmallVector<Split *> splits;
109 
110  /// Where each of the original arc's outputs come from after splitting.
111  SmallVector<ImportedValue> outputs;
112 };
113 } // namespace
114 
115 /// Create a separate arc body block for every unique coloring of operations.
116 void Splitter::run(Block &block, DenseMap<Operation *, APInt> &coloring) {
117  for (auto &op : block.without_terminator()) {
118  auto color = coloring.lookup(&op);
119  auto &split = getSplit(color);
120 
121  // Collect the operands of the current operation.
122  SmallSetVector<Value, 4> operands;
123  op.walk([&](Operation *op) {
124  for (auto operand : op->getOperands())
125  if (operand.getParentBlock() == &block)
126  operands.insert(operand);
127  });
128 
129  // Each operand that is either an input of the original arc or that is
130  // defined by an operation that got moved to a different split, create an
131  // input to the current split for that value.
132  for (auto operand : operands) {
133  if (split.mapping.contains(operand))
134  continue;
135  if (auto blockArg = dyn_cast<BlockArgument>(operand)) {
136  split.importInput(blockArg);
137  continue;
138  }
139  auto *operandOp = operand.getDefiningOp();
140  auto operandColor = coloring.lookup(operandOp);
141  assert(operandOp && color != operandColor);
142  auto &operandSplit = getSplit(operandColor);
143  split.importFromOtherSplit(operand, operandSplit);
144  }
145 
146  // Move the operation into the split.
147  split.builder.clone(op, split.mapping);
148  }
149 
150  // Reconstruct where each of the original arc outputs got mapped to.
151  for (auto operand : block.getTerminator()->getOperands()) {
152  if (auto blockArg = dyn_cast<BlockArgument>(operand)) {
153  outputs.push_back({true, blockArg.getArgNumber(), 0});
154  continue;
155  }
156  auto &operandSplit = getSplit(coloring.lookup(operand.getDefiningOp()));
157  auto resultIdx = operandSplit.exportValue(operand);
158  outputs.push_back({false, resultIdx, operandSplit.index});
159  }
160 
161  // Create the final `arc.output` op for each of the splits.
162  for (auto &split : splits)
163  split->builder.create<arc::OutputOp>(loc, split->exportedValues);
164 }
165 
166 /// Get or create the split for a given operation color.
167 Split &Splitter::getSplit(const APInt &color) {
168  auto &split = splitsByColor[color];
169  if (!split) {
170  auto index = splits.size();
171  LLVM_DEBUG(llvm::dbgs()
172  << "- Creating split " << index << " for " << color << "\n");
173  split = std::make_unique<Split>(context, index, color);
174  splits.push_back(split.get());
175  }
176  return *split;
177 }
178 
179 //===----------------------------------------------------------------------===//
180 // Pass Implementation
181 //===----------------------------------------------------------------------===//
182 
183 namespace {
184 struct SplitLoopsPass : public arc::impl::SplitLoopsBase<SplitLoopsPass> {
185  void runOnOperation() override;
186  void splitArc(Namespace &arcNamespace, DefineOp defOp,
187  ArrayRef<StateOp> arcUses);
188  void replaceArcUse(StateOp arcUse, ArrayRef<DefineOp> splitDefs,
189  ArrayRef<Split *> splits, ArrayRef<ImportedValue> outputs);
190  LogicalResult ensureNoLoops();
191 
192  DenseSet<StateOp> allArcUses;
193 };
194 } // namespace
195 
196 void SplitLoopsPass::runOnOperation() {
197  auto module = getOperation();
198  allArcUses.clear();
199 
200  // Collect all arc definitions.
201  Namespace arcNamespace;
202  DenseMap<StringAttr, DefineOp> arcDefs;
203  for (auto arcDef : module.getOps<DefineOp>()) {
204  arcNamespace.newName(arcDef.getSymName());
205  arcDefs[arcDef.getSymNameAttr()] = arcDef;
206  }
207 
208  // Collect all arc uses and determine which arcs we should split.
209  SetVector<DefineOp> arcsToSplit;
210  DenseMap<DefineOp, SmallVector<StateOp>> arcUses;
211  SetVector<StateOp> allArcUses;
212 
213  module.walk([&](StateOp stateOp) {
214  auto sym = stateOp.getArcAttr().getAttr();
215  auto defOp = arcDefs.lookup(sym);
216  arcUses[defOp].push_back(stateOp);
217  allArcUses.insert(stateOp);
218  if (stateOp.getLatency() == 0 && stateOp.getNumResults() > 1)
219  arcsToSplit.insert(defOp);
220  });
221 
222  // Split all arcs with more than one result.
223  // TODO: This is ugly and we should only split arcs that are truly involved in
224  // a loop. But detecting the minimal split among the arcs is fairly
225  // non-trivial and needs a dedicated implementation effort.
226  for (auto defOp : arcsToSplit)
227  splitArc(arcNamespace, defOp, arcUses[defOp]);
228 
229  // Ensure that there are no loops through arcs remaining.
230  if (failed(ensureNoLoops()))
231  return signalPassFailure();
232 }
233 
234 /// Split a single arc into a separate arc for each result.
235 void SplitLoopsPass::splitArc(Namespace &arcNamespace, DefineOp defOp,
236  ArrayRef<StateOp> arcUses) {
237  LLVM_DEBUG(llvm::dbgs() << "Splitting arc " << defOp.getSymNameAttr()
238  << "\n");
239 
240  // Mark the operations in the arc according to which result they contribute
241  // to.
242  auto numResults = defOp.getNumResults();
243  DenseMap<Value, APInt> valueColoring;
244  DenseMap<Operation *, APInt> opColoring;
245 
246  for (auto &operand : defOp.getBodyBlock().getTerminator()->getOpOperands())
247  valueColoring.insert(
248  {operand.get(),
249  APInt::getOneBitSet(numResults, operand.getOperandNumber())});
250 
251  for (auto &op : llvm::reverse(defOp.getBodyBlock().without_terminator())) {
252  auto coloring = APInt::getZero(numResults);
253  for (auto result : op.getResults())
254  if (auto it = valueColoring.find(result); it != valueColoring.end())
255  coloring |= it->second;
256  opColoring.insert({&op, coloring});
257  op.walk([&](Operation *op) {
258  for (auto &operand : op->getOpOperands())
259  valueColoring.try_emplace(operand.get(), numResults, 0).first->second |=
260  coloring;
261  });
262  }
263 
264  // Determine the splits for this arc.
265  Splitter splitter(&getContext(), defOp.getLoc());
266  splitter.run(defOp.getBodyBlock(), opColoring);
267 
268  // Materialize the split arc definitions.
269  ImplicitLocOpBuilder builder(defOp.getLoc(), defOp);
270  SmallVector<DefineOp> splitArcs;
271  splitArcs.reserve(splitter.splits.size());
272  for (auto &split : splitter.splits) {
273  auto splitName = defOp.getSymName();
274  if (splitter.splits.size() > 1)
275  splitName = arcNamespace.newName(defOp.getSymName() + "_split_" +
276  Twine(split->index));
277  auto splitArc = builder.create<DefineOp>(
278  splitName, builder.getFunctionType(
279  split->block->getArgumentTypes(),
280  split->block->getTerminator()->getOperandTypes()));
281  splitArc.getBody().push_back(split->block.release());
282  splitArcs.push_back(splitArc);
283  }
284 
285  // Replace all uses with the new splits and remove the old definition.
286  for (auto arcUse : arcUses)
287  replaceArcUse(arcUse, splitArcs, splitter.splits, splitter.outputs);
288  defOp.erase();
289 }
290 
291 /// Replace a use of the original arc with new uses for the splits.
292 void SplitLoopsPass::replaceArcUse(StateOp arcUse, ArrayRef<DefineOp> splitDefs,
293  ArrayRef<Split *> splits,
294  ArrayRef<ImportedValue> outputs) {
295  ImplicitLocOpBuilder builder(arcUse.getLoc(), arcUse);
296  SmallVector<StateOp> newUses(splits.size());
297 
298  // Resolve an `ImportedValue` to either an operand of the original arc or the
299  // result of another split.
300  auto getMappedValue = [&](ImportedValue value) {
301  if (value.isInput)
302  return arcUse.getInputs()[value.index];
303  return newUses[value.split].getResult(value.index);
304  };
305 
306  // Collect the operands for each split and create a new use for each. These
307  // are either operands of the original arc, or values from other splits
308  // exported as results.
309  DenseMap<unsigned, unsigned> splitIdxMap;
310  for (auto [i, split] : llvm::enumerate(splits))
311  splitIdxMap[split->index] = i;
312 
313  DenseSet<unsigned> splitsDone;
314  SmallVector<std::pair<const DefineOp, const Split *>> worklist;
315 
316  auto getMappedValuesOrSchedule = [&](ArrayRef<ImportedValue> importedValues,
317  SmallVector<Value> &operands) {
318  for (auto importedValue : importedValues) {
319  if (!importedValue.isInput && !splitsDone.contains(importedValue.split)) {
320  unsigned idx = splitIdxMap[importedValue.split];
321  worklist.push_back({splitDefs[idx], splits[idx]});
322  return false;
323  }
324 
325  operands.push_back(getMappedValue(importedValue));
326  }
327 
328  return true;
329  };
330 
331  // Initialize worklist
332  for (auto [splitDef, split] : llvm::reverse(llvm::zip(splitDefs, splits)))
333  worklist.push_back({splitDef, split});
334 
335  // Process worklist
336  while (!worklist.empty()) {
337  auto [splitDef, split] = worklist.back();
338 
339  if (splitsDone.contains(split->index)) {
340  worklist.pop_back();
341  continue;
342  }
343 
344  SmallVector<Value> operands;
345  if (!getMappedValuesOrSchedule(split->importedValues, operands))
346  continue;
347 
348  auto newUse =
349  builder.create<StateOp>(splitDef, Value{}, Value{}, 0, operands);
350  allArcUses.insert(newUse);
351  newUses[split->index] = newUse;
352 
353  splitsDone.insert(split->index);
354  worklist.pop_back();
355  }
356 
357  // Update the users of the original arc results.
358  for (auto [result, importedValue] : llvm::zip(arcUse.getResults(), outputs))
359  result.replaceAllUsesWith(getMappedValue(importedValue));
360  allArcUses.erase(arcUse);
361  arcUse.erase();
362 }
363 
364 /// Check that there are no more zero-latency loops through arcs.
365 LogicalResult SplitLoopsPass::ensureNoLoops() {
366  SmallVector<std::pair<Operation *, unsigned>, 0> worklist;
367  DenseSet<Operation *> finished;
368  DenseSet<Operation *> seen;
369  for (auto op : allArcUses) {
370  if (finished.contains(op))
371  continue;
372  assert(seen.empty());
373  worklist.push_back({op, 0});
374  while (!worklist.empty()) {
375  auto [op, idx] = worklist.back();
376  ++worklist.back().second;
377  if (idx == op->getNumOperands()) {
378  seen.erase(op);
379  finished.insert(op);
380  worklist.pop_back();
381  continue;
382  }
383  auto operand = op->getOperand(idx);
384  auto *def = operand.getDefiningOp();
385  if (!def || finished.contains(def))
386  continue;
387  if (auto stateOp = dyn_cast<StateOp>(def);
388  stateOp && stateOp.getLatency() > 0)
389  continue;
390  if (!seen.insert(def).second) {
391  auto d = def->emitError(
392  "loop splitting did not eliminate all loops; loop detected");
393  for (auto [op, idx] : llvm::reverse(worklist)) {
394  d.attachNote(op->getLoc())
395  << "through operand " << (idx - 1) << " here:";
396  if (op == def)
397  break;
398  }
399  return failure();
400  }
401  worklist.push_back({def, 0});
402  }
403  }
404  return success();
405 }
406 
407 std::unique_ptr<Pass> arc::createSplitLoopsPass() {
408  return std::make_unique<SplitLoopsPass>();
409 }
lowerAnnotationsNoRefTypePorts FirtoolPreserveValuesMode value
Definition: Firtool.cpp:95
assert(baseType &&"element must be base type")
static Attribute getAttr(ArrayRef< NamedAttribute > attrs, StringRef name)
Get an attribute by name from a list of named attributes.
Definition: FIRRTLOps.cpp:3429
llvm::SmallVector< StringAttr > outputs
Builder builder
A namespace that is used to store existing names and generate new names in some scope within the IR.
Definition: Namespace.h:29
StringRef newName(const Twine &name)
Return a unique name, derived from the input name, and add the new name to the internal namespace.
Definition: Namespace.h:63
std::unique_ptr< mlir::Pass > createSplitLoopsPass()
Definition: SplitLoops.cpp:407
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
Definition: hw.py:1
mlir::raw_indented_ostream & dbgs()
Definition: Utility.h:28