CIRCT  19.0.0git
PrettifyVerilog.cpp
Go to the documentation of this file.
1 //===- PrettifyVerilog.cpp - Transformations to improve Verilog quality ---===//
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 pass contains elective transformations that improve the quality of
10 // SystemVerilog generated by the ExportVerilog library. This pass is not
11 // compulsory: things that are required for ExportVerilog to be correct should
12 // be included as part of the ExportVerilog pass itself to make sure it is self
13 // contained. This allows the ExportVerilog pass to be simpler.
14 //
15 // PrettifyVerilog is run prior to Verilog emission but must be aware of the
16 // options in LoweringOptions. It shouldn't introduce invalid constructs that
17 // aren't present in the IR already: this isn't a general "raising" pass.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #include "PassDetail.h"
23 #include "circt/Dialect/HW/HWOps.h"
26 #include "mlir/IR/ImplicitLocOpBuilder.h"
27 #include "mlir/IR/Matchers.h"
28 #include "llvm/ADT/TypeSwitch.h"
29 
30 using namespace circt;
31 
32 //===----------------------------------------------------------------------===//
33 // PrettifyVerilogPass
34 //===----------------------------------------------------------------------===//
35 
36 namespace {
37 struct PrettifyVerilogPass
38  : public sv::PrettifyVerilogBase<PrettifyVerilogPass> {
39  void runOnOperation() override;
40 
41 private:
42  void processPostOrder(Block &block);
43  bool prettifyUnaryOperator(Operation *op);
44  void sinkOrCloneOpToUses(Operation *op);
45  void sinkExpression(Operation *op);
46  void useNamedOperands(Operation *op, DenseMap<Value, Operation *> &pipeMap);
47 
48  bool splitStructAssignment(OpBuilder &builder, hw::StructType ty, Value dst,
49  Value src);
50  bool splitArrayAssignment(OpBuilder &builder, hw::ArrayType ty, Value dst,
51  Value src);
52  bool splitAssignment(OpBuilder &builder, Value dst, Value src);
53 
54  bool anythingChanged;
55  LoweringOptions options;
56 
57  DenseSet<Operation *> toDelete;
58 };
59 } // end anonymous namespace
60 
61 /// Return true if this is something that will get printed as a unary operator
62 /// by the Verilog printer.
63 static bool isVerilogUnaryOperator(Operation *op) {
64  if (isa<comb::ParityOp>(op))
65  return true;
66 
67  if (auto xorOp = dyn_cast<comb::XorOp>(op))
68  return xorOp.isBinaryNot();
69 
70  if (auto icmpOp = dyn_cast<comb::ICmpOp>(op))
71  return icmpOp.isEqualAllOnes() || icmpOp.isNotEqualZero();
72 
73  return false;
74 }
75 
76 /// Helper to convert a value to a constant integer if it is one.
77 static std::optional<APInt> getInt(Value value) {
78  if (auto cst = dyn_cast_or_null<hw::ConstantOp>(value.getDefiningOp()))
79  return cst.getValue();
80  return std::nullopt;
81 }
82 
83 // Checks whether the destination and the source of an assignment are the same.
84 // However, the destination is a value with an inout type in SV form, while the
85 // source is built using ops from HWAggregates.
86 static bool isSelfWrite(Value dst, Value src) {
87  if (dst == src)
88  return true;
89 
90  auto *srcOp = src.getDefiningOp();
91  auto *dstOp = dst.getDefiningOp();
92  if (!srcOp || !dstOp)
93  return false;
94 
95  return TypeSwitch<Operation *, bool>(srcOp)
96  .Case<hw::StructExtractOp>([&](auto extract) {
97  auto toField = dyn_cast<sv::StructFieldInOutOp>(dstOp);
98  if (!toField)
99  return false;
100  if (toField.getFieldAttr() != extract.getFieldNameAttr())
101  return false;
102  return isSelfWrite(toField.getInput(), extract.getInput());
103  })
104  .Case<hw::ArrayGetOp>([&](auto get) {
105  auto toGet = dyn_cast<sv::ArrayIndexInOutOp>(dstOp);
106  if (!toGet || toGet.getIndex().getType() != get.getIndex().getType())
107  return false;
108  auto toIdx = getInt(toGet.getIndex());
109  auto fromIdx = getInt(get.getIndex());
110  if (!toIdx || !fromIdx || toIdx != fromIdx)
111  return false;
112  return isSelfWrite(toGet.getInput(), get.getInput());
113  })
114  .Case<sv::ReadInOutOp>([&](auto read) { return dst == read.getInput(); })
115  .Default([&](auto srcOp) { return false; });
116 }
117 
118 /// Split an assignment to a structure to writes of individual fields.
119 bool PrettifyVerilogPass::splitStructAssignment(OpBuilder &builder,
120  hw::StructType ty, Value dst,
121  Value src) {
122  // Follow a chain of injects to find all fields overwritten and separate
123  // them into a series of field updates instead of a whole-structure write.
124  DenseMap<StringAttr, std::pair<Location, Value>> fields;
125  while (auto inj = dyn_cast_or_null<hw::StructInjectOp>(src.getDefiningOp())) {
126  // Inner injects are overwritten by outer injects.
127  // Insert does not overwrite the store to be lowered.
128  auto field = std::make_pair(inj.getLoc(), inj.getNewValue());
129  fields.try_emplace(inj.getFieldNameAttr(), field);
130  src = inj.getInput();
131  }
132 
133  // The origin must be either the object itself (partial update)
134  // or the whole object must be overwritten.
135  if (!isSelfWrite(dst, src) && ty.getElements().size() != fields.size())
136  return false;
137 
138  // Emit the field assignments in the order of their definition.
139  for (auto &field : ty.getElements()) {
140  const auto &name = field.name;
141 
142  auto it = fields.find(name);
143  if (it == fields.end())
144  continue;
145 
146  auto &[loc, value] = it->second;
147  auto ref = builder.create<sv::StructFieldInOutOp>(loc, dst, name);
148  if (!splitAssignment(builder, ref, value))
149  builder.create<sv::PAssignOp>(loc, ref, value);
150  }
151  return true;
152 }
153 
154 /// Split an assignment to an array element to writes of individual indices.
155 bool PrettifyVerilogPass::splitArrayAssignment(OpBuilder &builder,
156  hw::ArrayType ty, Value dst,
157  Value src) {
158  // Follow a chain of concat + slice operations that alter a single element.
159  if (auto op = dyn_cast_or_null<hw::ArrayCreateOp>(src.getDefiningOp())) {
160  // TODO: consider breaking up array assignments into assignments
161  // to individual fields.
162  auto ty = hw::type_cast<hw::ArrayType>(op.getType());
163  if (ty.getNumElements() != 1)
164  return false;
165  APInt zero(std::max(1u, llvm::Log2_64_Ceil(ty.getNumElements())), 0);
166 
167  Value value = op.getInputs()[0];
168  auto loc = op.getLoc();
169  auto index = builder.create<hw::ConstantOp>(loc, zero);
170 
171  auto field = builder.create<sv::ArrayIndexInOutOp>(loc, dst, index);
172  if (!splitAssignment(builder, field, value))
173  builder.create<sv::PAssignOp>(loc, field, value);
174  return true;
175  }
176 
177  // TODO: generalise to ranges and arbitrary concatenations.
178  SmallVector<std::tuple<APInt, Location, Value>> fields;
179  while (auto concat =
180  dyn_cast_or_null<hw::ArrayConcatOp>(src.getDefiningOp())) {
181  auto loc = concat.getLoc();
182 
183  // Look for a slice and an element:
184  // concat(slice(a, 0, size - 1), elem)
185  // concat(elem, slice(a, 1, size - 1))
186  if (concat.getNumOperands() == 2) {
187  auto c = concat.getInputs();
188 
189  auto lhs = dyn_cast_or_null<hw::ArraySliceOp>(c[1].getDefiningOp());
190  auto rhs = dyn_cast_or_null<hw::ArraySliceOp>(c[0].getDefiningOp());
191  auto midL = dyn_cast_or_null<hw::ArrayCreateOp>(c[1].getDefiningOp());
192  auto midR = dyn_cast_or_null<hw::ArrayCreateOp>(c[0].getDefiningOp());
193 
194  auto size =
195  hw::type_cast<hw::ArrayType>(concat.getType()).getNumElements();
196  if (lhs && midR) {
197  auto baseIdx = getInt(lhs.getLowIndex());
198  if (!baseIdx || *baseIdx != 0 || midR.getInputs().size() != 1)
199  break;
200  fields.emplace_back(APInt(baseIdx->getBitWidth(), size - 1), loc,
201  midR.getInputs()[0]);
202  src = lhs.getInput();
203  continue;
204  }
205  if (rhs && midL) {
206  auto baseIdx = getInt(rhs.getLowIndex());
207  if (!baseIdx || *baseIdx != 1 || midL.getInputs().size() != 1)
208  break;
209  src = rhs.getInput();
210  fields.emplace_back(APInt(baseIdx->getBitWidth(), 0), loc,
211  midL.getInputs()[0]);
212  continue;
213  }
214  break;
215  }
216 
217  // Look for a pattern overwriting a single element of the array.
218  // concat(slice(a, 0, n - 1), create(get(a, n)), slice(n + 1, size -
219  // n))
220  if (concat.getNumOperands() == 3) {
221  auto c = concat.getInputs();
222  auto rhs = dyn_cast_or_null<hw::ArraySliceOp>(c[0].getDefiningOp());
223  auto mid = dyn_cast_or_null<hw::ArrayCreateOp>(c[1].getDefiningOp());
224  auto lhs = dyn_cast_or_null<hw::ArraySliceOp>(c[2].getDefiningOp());
225  if (!lhs || !mid || !rhs || mid.getInputs().size() != 1)
226  break;
227  auto elem = mid.getInputs()[0];
228  auto arr = lhs.getInput();
229  if (arr != rhs.getInput() || arr.getType() != concat.getType())
230  break;
231 
232  auto lhsSize =
233  hw::type_cast<hw::ArrayType>(lhs.getType()).getNumElements();
234  auto lhsIdx = getInt(lhs.getLowIndex());
235  auto rhsIdx = getInt(rhs.getLowIndex());
236  if (!lhsIdx || *lhsIdx != 0)
237  break;
238  if (!rhsIdx || *rhsIdx != lhsSize + 1)
239  break;
240  fields.emplace_back(*rhsIdx - 1, loc, elem);
241  src = arr;
242  continue;
243  }
244  break;
245  }
246 
247  if (!isSelfWrite(dst, src))
248  return false;
249 
250  // Emit the assignments in the order of the indices.
251  std::stable_sort(fields.begin(), fields.end(), [](auto l, auto r) {
252  return std::get<0>(l).ult(std::get<0>(r));
253  });
254 
255  std::optional<APInt> last;
256  for (auto &[i, loc, value] : fields) {
257  if (i == last)
258  continue;
259  auto index = builder.create<hw::ConstantOp>(loc, i);
260  auto field = builder.create<sv::ArrayIndexInOutOp>(loc, dst, index);
261  if (!splitAssignment(builder, field, value))
262  builder.create<sv::PAssignOp>(loc, field, value);
263  last = i;
264  }
265  return true;
266 }
267 
268 /// Instead of emitting a struct_inject to alter fields or concatenation
269 /// to adjust array elements, emit a more readable sequence of disjoint
270 /// assignments to individual fields and indices. Returns true if
271 /// sub-assignments were emitted and the original one can be deleted.
272 bool PrettifyVerilogPass::splitAssignment(OpBuilder &builder, Value dst,
273  Value src) {
274  if (isSelfWrite(dst, src))
275  return true;
276 
277  if (auto ty = hw::type_dyn_cast<hw::StructType>(src.getType()))
278  return splitStructAssignment(builder, ty, dst, src);
279 
280  if (auto ty = hw::type_dyn_cast<hw::ArrayType>(src.getType()))
281  return splitArrayAssignment(builder, ty, dst, src);
282 
283  return false;
284 }
285 
286 /// Sink an operation into the same block where it is used. This will clone the
287 /// operation so it can be sunk into multiple blocks. If there are no more uses
288 /// in the current block, the op will be removed.
289 void PrettifyVerilogPass::sinkOrCloneOpToUses(Operation *op) {
290  assert(mlir::isMemoryEffectFree(op) &&
291  "Op with side effects cannot be sunk to its uses.");
292  auto block = op->getBlock();
293  // This maps a block to the block local instance of the op.
294  SmallDenseMap<Block *, Value, 8> blockLocalValues;
295  for (auto &use : llvm::make_early_inc_range(op->getUses())) {
296  // If the current use is in the same block as the operation, there is
297  // nothing to do.
298  auto localBlock = use.getOwner()->getBlock();
299  if (block == localBlock)
300  continue;
301  // Find the block local clone of the operation. If there is not one already,
302  // the op will be cloned in to the block.
303  auto &localValue = blockLocalValues[localBlock];
304  if (!localValue) {
305  // Clone the operation and insert it to the beginning of the block.
306  localValue = OpBuilder::atBlockBegin(localBlock).clone(*op)->getResult(0);
307  }
308  // Replace the current use, removing it from the use list.
309  use.set(localValue);
310  anythingChanged = true;
311  }
312  // If this op is no longer used, drop it.
313  if (op->use_empty()) {
314  toDelete.insert(op);
315  anythingChanged = true;
316  }
317 }
318 
319 /// This is called on unary operators. This returns true if the operator is
320 /// moved.
321 bool PrettifyVerilogPass::prettifyUnaryOperator(Operation *op) {
322  // If this is a multiple use unary operator, duplicate it and move it into the
323  // block corresponding to the user. This avoids emitting a temporary just for
324  // a unary operator. Instead of:
325  //
326  // tmp1 = ^(thing+thing);
327  // = tmp1 + 42
328  //
329  // we get:
330  //
331  // tmp2 = thing+thing;
332  // = ^tmp2 + 42
333  //
334  // This is particularly helpful when the operand of the unary op has multiple
335  // uses as well.
336  if (op->use_empty() || op->hasOneUse())
337  return false;
338 
339  // If this operation has any users that cannot inline the operation, then
340  // don't duplicate any of them.
341  for (auto *user : op->getUsers()) {
342  if (isa<comb::ExtractOp, hw::ArraySliceOp>(user))
343  return false;
344  if (!options.allowExprInEventControl &&
345  isa<sv::AlwaysFFOp, sv::AlwaysOp>(user))
346  return false;
347  }
348 
349  // Duplicating unary operations can move them across blocks (down the region
350  // tree). Make sure to keep referenced constants local.
351  auto cloneConstantOperandsIfNeeded = [&](Operation *op) {
352  for (auto &operand : op->getOpOperands()) {
353  auto constant = operand.get().getDefiningOp<hw::ConstantOp>();
354  if (!constant)
355  continue;
356 
357  // If the constant is in a different block, clone or move it into the
358  // block.
359  if (constant->getBlock() != op->getBlock())
360  operand.set(OpBuilder(op).clone(*constant)->getResult(0));
361  }
362  };
363 
364  while (!op->hasOneUse()) {
365  OpOperand &use = *op->use_begin();
366  Operation *user = use.getOwner();
367 
368  // Clone the operation and insert before this user.
369  auto *cloned = OpBuilder(user).clone(*op);
370  cloneConstantOperandsIfNeeded(cloned);
371 
372  // Update user's operand to the new value.
373  use.set(cloned->getResult(0));
374  }
375 
376  // There is exactly one user left, so move this before it.
377  Operation *user = *op->user_begin();
378  op->moveBefore(user);
379  cloneConstantOperandsIfNeeded(op);
380 
381  anythingChanged = true;
382  return true;
383 }
384 
385 // Return the depth of the specified block in the region tree, stopping at
386 // 'topBlock'.
387 static unsigned getBlockDepth(Block *block, Block *topBlock) {
388  unsigned result = 0;
389  while (block != topBlock) {
390  block = block->getParentOp()->getBlock();
391  ++result;
392  }
393  return result;
394 }
395 
396 /// This method is called on expressions to see if we can sink them down the
397 /// region tree. This is a good thing to do to reduce scope of the expression.
398 ///
399 /// This is called on expressions that may have side effects, and filters out
400 /// the side effecting cases late for efficiency.
401 void PrettifyVerilogPass::sinkExpression(Operation *op) {
402  // Ignore expressions with no users.
403  if (op->use_empty())
404  return;
405 
406  Block *curOpBlock = op->getBlock();
407 
408  // Single-used expressions are the most common and simple to handle.
409  if (op->hasOneUse()) {
410  if (curOpBlock != op->user_begin()->getBlock()) {
411  // Ok, we're about to make a change, ensure that there are no side
412  // effects.
413  if (!mlir::isMemoryEffectFree(op))
414  return;
415 
416  op->moveBefore(*op->user_begin());
417  anythingChanged = true;
418  }
419  return;
420  }
421 
422  // Find the nearest common ancestor of all the users.
423  auto userIt = op->user_begin();
424  Block *ncaBlock = userIt->getBlock();
425  ++userIt;
426  unsigned ncaBlockDepth = getBlockDepth(ncaBlock, curOpBlock);
427  if (ncaBlockDepth == 0)
428  return; // Have a user in the current block.
429 
430  for (auto e = op->user_end(); userIt != e; ++userIt) {
431  auto *userBlock = userIt->getBlock();
432  if (userBlock == curOpBlock)
433  return; // Op has a user in it own block, can't sink it.
434  if (userBlock == ncaBlock)
435  continue;
436 
437  // Get the region depth of the user block so we can march up the region tree
438  // to a common ancestor.
439  unsigned userBlockDepth = getBlockDepth(userBlock, curOpBlock);
440  while (userBlock != ncaBlock) {
441  if (ncaBlockDepth < userBlockDepth) {
442  userBlock = userBlock->getParentOp()->getBlock();
443  --userBlockDepth;
444  } else if (userBlockDepth < ncaBlockDepth) {
445  ncaBlock = ncaBlock->getParentOp()->getBlock();
446  --ncaBlockDepth;
447  } else {
448  userBlock = userBlock->getParentOp()->getBlock();
449  --userBlockDepth;
450  ncaBlock = ncaBlock->getParentOp()->getBlock();
451  --ncaBlockDepth;
452  }
453  }
454 
455  if (ncaBlockDepth == 0)
456  return; // Have a user in the current block.
457  }
458 
459  // Ok, we're about to make a change, ensure that there are no side
460  // effects.
461  if (!mlir::isMemoryEffectFree(op))
462  return;
463 
464  // Ok, we found a common ancestor between all the users that is deeper than
465  // the current op. Sink it into the start of that block.
466  assert(ncaBlock != curOpBlock && "should have bailed out earlier");
467  op->moveBefore(&ncaBlock->front());
468  anythingChanged = true;
469 }
470 
471 void PrettifyVerilogPass::processPostOrder(Block &body) {
472  SmallVector<Operation *> instances;
473 
474  // Walk the block bottom-up, processing the region tree inside out.
475  for (auto &op :
476  llvm::make_early_inc_range(llvm::reverse(body.getOperations()))) {
477  if (op.getNumRegions()) {
478  for (auto &region : op.getRegions())
479  for (auto &regionBlock : region.getBlocks())
480  processPostOrder(regionBlock);
481  }
482 
483  // Simplify assignments involving structures and arrays.
484  if (auto assign = dyn_cast<sv::PAssignOp>(op)) {
485  auto dst = assign.getDest();
486  auto src = assign.getSrc();
487  if (!isSelfWrite(dst, src)) {
488  OpBuilder builder(assign);
489  if (splitAssignment(builder, dst, src)) {
490  anythingChanged = true;
491  toDelete.insert(src.getDefiningOp());
492  toDelete.insert(dst.getDefiningOp());
493  assign.erase();
494  continue;
495  }
496  }
497  }
498 
499  // Sink and duplicate unary operators.
500  if (isVerilogUnaryOperator(&op) && prettifyUnaryOperator(&op))
501  continue;
502 
503  // Sink or duplicate constant ops and invisible "free" ops into the same
504  // block as their use. This will allow the verilog emitter to inline
505  // constant expressions and avoids ReadInOutOp from preventing motion.
506  if (matchPattern(&op, mlir::m_Constant()) ||
507  isa<sv::ReadInOutOp, sv::ArrayIndexInOutOp, sv::StructFieldInOutOp,
508  sv::IndexedPartSelectInOutOp, hw::ParamValueOp>(op)) {
509  sinkOrCloneOpToUses(&op);
510  continue;
511  }
512 
513  // Sink normal expressions down the region tree if they aren't used within
514  // their current block. This allows them to be folded into the using
515  // expression inline in the best case, and better scopes the temporary wire
516  // they generate in the worst case. Our overall traversal order is
517  // post-order here which means all users will already be sunk.
518  if (hw::isCombinational(&op) || sv::isExpression(&op)) {
519  sinkExpression(&op);
520  continue;
521  }
522 
523  if (isa<hw::InstanceOp>(op))
524  instances.push_back(&op);
525  }
526 
527  // If we have any instances, keep their relative order but shift them to the
528  // end of the module. Any outputs will be writing to a wire or an output port
529  // of the enclosing module anyway, and this allows inputs to be inlined into
530  // the operand list as parameters.
531  if (!instances.empty()) {
532  for (Operation *instance : llvm::reverse(instances)) {
533  if (instance != &body.back())
534  instance->moveBefore(&body.back());
535  }
536  }
537 }
538 
539 void PrettifyVerilogPass::runOnOperation() {
540  hw::HWModuleOp thisModule = getOperation();
541  options = LoweringOptions(thisModule->getParentOfType<mlir::ModuleOp>());
542 
543  // Keeps track if anything changed during this pass, used to determine if
544  // the analyses were preserved.
545  anythingChanged = false;
546 
547  // Walk the operations in post-order, transforming any that are interesting.
548  processPostOrder(*thisModule.getBodyBlock());
549 
550  // Erase any dangling operands of simplified operations.
551  while (!toDelete.empty()) {
552  auto it = toDelete.begin();
553  Operation *op = *it;
554  toDelete.erase(it);
555 
556  if (!op || !isOpTriviallyDead(op))
557  continue;
558 
559  for (auto operand : op->getOperands())
560  toDelete.insert(operand.getDefiningOp());
561 
562  op->erase();
563  }
564 
565  // If we did not change anything in the graph mark all analysis as
566  // preserved.
567  if (!anythingChanged)
568  markAllAnalysesPreserved();
569 }
570 
571 std::unique_ptr<Pass> circt::sv::createPrettifyVerilogPass() {
572  return std::make_unique<PrettifyVerilogPass>();
573 }
assert(baseType &&"element must be base type")
static SmallVector< T > concat(const SmallVectorImpl< T > &a, const SmallVectorImpl< T > &b)
Returns a new vector containing the concatenation of vectors a and b.
Definition: CalyxOps.cpp:539
Builder builder
static bool isSelfWrite(Value dst, Value src)
static unsigned getBlockDepth(Block *block, Block *topBlock)
static bool isVerilogUnaryOperator(Operation *op)
Return true if this is something that will get printed as a unary operator by the Verilog printer.
static std::optional< APInt > getInt(Value value)
Helper to convert a value to a constant integer if it is one.
Direction get(bool isOutput)
Returns an output direction if isOutput is true, otherwise returns an input direction.
Definition: CalyxOps.cpp:54
bool isCombinational(Operation *op)
Return true if the specified operation is a combinational logic op.
Definition: HWOps.cpp:59
bool isExpression(Operation *op)
Return true if the specified operation is an expression.
Definition: SVOps.cpp:48
std::unique_ptr< mlir::Pass > createPrettifyVerilogPass()
This file defines an intermediate representation for circuits acting as an abstraction for constraint...
Definition: DebugAnalysis.h:21
Options which control the emission from CIRCT to Verilog.