[Datapath] Operator definitions and canonicalization patterns #8647

cowardsa · 2025-07-03T08:40:41Z

Building on the boiler plate definition adding two operators

datapath.compress - compressor tree circuit
datapath.partial_product - partial product generation circuit

The key idea is to view datapath operators as generators of circuits that satisfy some contract, for example in the case of the datapath.compress summing it's results is equivalent to summing it's inputs. This allows us to defer implementing these critical circuits until later in the synthesis flow.

In a simple example, we can fold a*b+c using the datapath dialect to remove a carry-propagate adder:

%0 = comb.mul %a, %b : i4
%1 = comb.add %0, %c : i4

Which is equivalent to:

%0:4 = datapath.partial_product %a, %b : (i4, i4) -> (i4, i4, i4, i4)
%1:2 = datapath.compress %0#0, %0#1, %0#2, %0#3, %c : i4 [5 -> 2]
%2 = comb.add %1#0, %1#1 : i4

This is the first in a series of PRs to add datapath synthesis capabilities that will include the following (implemented but not merged):

Comb to Datapath pass
Datapath to Comb pass - for lowering datapath ops to comb gates
Datapath to SMT - for contract verification
Incorporating datapath passes into circt-synth
Replicate adds pass - to enable unsharing for better delay performance

… builder and assemblyFormat

…explicit reduction factor

…ingle compressor tree and removing zeros

…f results

…h_dialect_init

uenoku · 2025-07-03T08:50:26Z

include/circt/Dialect/Datapath/DatapathOps.td

+  let arguments = (ins Variadic<HWIntegerType>:$inputs);
+  let results   = (outs Variadic<HWIntegerType>:$results);
+
+  let hasCustomAssemblyFormat = true;


Can we use normal assembly format if possible for maintainability? I think functional-type is not that bad or you can also use custom-directives to print operand types nicely.

I found it really valuable to see to make it easy to count how many rows were in my compressor - will revisit if custom directives can achieve this - using functional-type involved a lot of counting (if I recall)

uenoku · 2025-07-03T09:04:00Z

lib/Dialect/Datapath/DatapathFolds.cpp

+                                PatternRewriter &rewriter) const override {
+    // Get operands of the AddOp
+    auto operands = compOp.getOperands();
+    SmallVector<Value, 8> processedCompressorResults;


Could you use SmallSetVector and replace llvm::is_contained with SmallSetVector::contains ? That should be as efficient as SmallVector + llvm::is_contained for small sizes and robust for large sets.

uenoku · 2025-07-03T09:07:22Z

include/circt/Dialect/Datapath/DatapathOps.td

+}
+
+// Construct partial product array from two operands
+def PartialProductOp : DatapathOp<"pp", 


super nit: can we use more verbose name than pp such as partial_prod or partial_product?

uenoku · 2025-07-03T09:22:58Z

include/circt/Dialect/Datapath/DatapathOps.td

+    The first step in a multiplication is to generate partial products, which 
+    when summed, yield the product of the two operands. The partial
+    product operator does not specify an implementation, only that summing the 
+    results will yield the product of the two operands. 


Could you briefly describe the semantics of op here? Especially correspondence of number/bit position, column/row and operands.

uenoku · 2025-07-03T09:25:08Z

lib/Dialect/Datapath/DatapathFolds.cpp

+    // pp(concat(0,a), concat(0,b)) -> reduce number of results
+    for (Value operand : operands) {
+      // If the extracted bits are all known, then return the result.
+      auto knownBits = comb::computeKnownBits(operand);


Not blocking but computeKnownBits is very expensive API (#4690) to use in canonicalizer so we might need to revisit this later.

…erators

cowardsa · 2025-07-03T14:14:20Z

Have now updated the datapath operator formatting to avoid custom assembly formats

maerhart · 2025-07-03T14:20:18Z

include/circt/Dialect/Datapath/DatapathOps.td

@@ -23,5 +23,85 @@ include "circt/Dialect/HW/HWTypes.td"
 class DatapathOp<string mnemonic, list<Trait> traits = []> :
    Op<DatapathDialect, mnemonic, traits>;

+//===----------------------------------------------------------------------===//
+
+// Compress an array of bitvectors to a smaller set of bitvectors (at least 2).


Nit: why not add this to the description (thus also the documentation on the website) instead?

maerhart · 2025-07-03T14:20:56Z

include/circt/Dialect/Datapath/DatapathOps.td

+
+// Compress an array of bitvectors to a smaller set of bitvectors (at least 2).
+def CompressOp : DatapathOp<"compress", 
+                                   [Pure, SameTypeOperands, 


Super-nit: this indentation looks a bit weird

maerhart · 2025-07-03T14:21:09Z

include/circt/Dialect/Datapath/DatapathOps.td

+  let results   = (outs Variadic<HWIntegerType>:$results);
+
+  let assemblyFormat = 
+    "$inputs attr-dict `:` custom<CompressFormat>(type($inputs), type($results))";


maerhart · 2025-07-03T14:23:04Z

include/circt/Dialect/Datapath/DatapathOps.td

+  ];
+}
+
+// Construct partial product array from two operands


Nit: comment seems redundant with the summary and could thus be removed

maerhart · 2025-07-03T14:23:14Z

include/circt/Dialect/Datapath/DatapathOps.td

+
+// Construct partial product array from two operands
+def PartialProductOp : DatapathOp<"partial_product", 
+                                    [Pure, SameTypeOperands, 


Nit: weird indentation

maerhart · 2025-07-03T14:26:52Z

include/circt/Dialect/Datapath/DatapathOps.td

+
+  // let hasCustomAssemblyFormat = true;
+  let assemblyFormat =
+    "$multiplicand `,` $multiplier attr-dict `:` functional-type(operands, results)";


maerhart · 2025-07-03T14:31:25Z

lib/Dialect/Datapath/DatapathOps.cpp

+  if (getNumOperands() < 3)
+    return emitOpError("Requires 3 or more arguments - otherwise use add");
+
+  if (getNumResults() >= getNumOperands())
+    return emitOpError("Must reduce the number of operands by at least 1");
+
+  if (getNumResults() < 2)
+    return emitOpError("Must produce at least 2 results");


I think the consensus is that these error strings shouldn't start with an uppercase letter (because it's not the start of a sentence and not even the start of the whole error message)

maerhart · 2025-07-03T14:34:10Z

include/circt/Dialect/Datapath/DatapathOps.td

+
+    Example:
+    ```mlir
+    %0:2 = datapath.compress %a, %b, %c : 3 x i16 -> (i16, i16)


Since all operands and result types are always the same, why is this not just

Suggested change

%0:2 = datapath.compress %a, %b, %c : 3 x i16 -> (i16, i16)

%0:2 = datapath.compress %a, %b, %c : i16

It would remove alll the redundant information and the entire custom parser and printer could go away. It would also be more consistent with how things are done in other CIRCT dialects (e.g. most comb ops).

My ideal format would be
%0:2 = datapath.compress %a, %b, %c : 3 x i16

Reasoning - when these compressors become large - it is valuable to be able to quickly read off how many rows the compressor is summing - without this annotation you need to count the number of arguments

Problems: have had great difficulties understanding how assemblyFormat works... So if anyone is able to help achieve the above that would be super helpful?

I'd argue that you can easily use your editor/IDE (e.g., vim) to give you this information by counting the number of % minus 1 in that line instead of annotating these things in the IR.

If you really want this format, you can significantly reduce what the custom directive is doing. It should just print num-operands x and in the parser it should parse a number and x and just throw it away as it is redundant anyway. The operands and type should be part of the assemblyFormat not the directive and with the right traits (the ones you already added should be enough) it will automatically infer the other operands and all result types.

@maerhart - do you have an example of how to print type($inputs[0[) as the comb example just uses the result - which in this case we have variadic inputs and outputs?

Ah sorry! This is trickier than I thought. One way I have seen people work around this is to define one extra operand or result outside of the variadic and use that as the anchor for the type but that leads to other annoyances, so I'd probably rather avoid that and pay the cost of the custom parser/printer.

I think there's also no way to get the number of results from the %0:2 = prefix (which I guess is the reason you kept the (i16, i16)). So I guess there are two options:

Custom parser/printer for something like %0:2 = datapath.compress %a, %b, %c : 2 x i16

Use the ODS functional-type

Ok how about the following that just involves one custom-directive and prints the type only once - I accept there is replication in the 2 but given the additional code required to get %0:2 this is perhaps more maintainable?

%0:2 = datapath.compress %a, %b, %c : i16 [3 -> 2]

maerhart · 2025-07-03T14:37:56Z

test/Dialect/Datapath/errors.mlir

In addition to there regression tests for the errors, we also have at least one test per operation (often in a file called basic.mlir) where circt-opt is only invoked with the round-trip option.

maerhart · 2025-07-03T14:45:22Z

lib/Dialect/Datapath/DatapathFolds.cpp

+  }
+};
+
+struct FoldAddIntoCompress : public OpRewritePattern<comb::AddOp> {


Nit: it often helps readability a lot to add a typical example of an application of a canonicalization to the docsting of the pattern struct.

Have added comments of basic examples and where we may have mutliple folds e.g. in Compress constant fold - have mimicked the CombFolds commenting style

cowardsa · 2025-07-04T09:59:22Z

Believe I've addressed all the comments above now - please let me know if any further concerns @maerhart or @uenoku?

uenoku

LGTM other than several nits 👍

uenoku · 2025-07-04T16:17:57Z

lib/Dialect/Datapath/DatapathFolds.cpp

+
+    // Only fold if we have constructed a larger compressor than what was
+    // already there
+    if (!(shouldFold))


Suggested change

if (!(shouldFold))

if (!shouldFold)

uenoku · 2025-07-04T16:30:08Z

test/Dialect/Datapath/basic.mlir

+  // CHECK-NEXT: datapath.partial_product %a, %b : (i3, i3) -> (i3, i3, i3)
+  %0:3 = datapath.partial_product %a, %b : (i3, i3) -> (i3, i3, i3)
+  hw.output %0#0, %0#1, %0#2 : i3, i3, i3
+}


nit: insert new line

Suggested change

}

}

uenoku · 2025-07-04T16:31:13Z

test/Dialect/Datapath/basic.mlir

@@ -0,0 +1,15 @@
+// RUN: circt-opt %s | circt-opt | FileCheck %s


nit: You ca ncheck with -verify-roundtrip

Suggested change

// RUN: circt-opt %s | circt-opt | FileCheck %s

// RUN: circt-opt %s -verify-roundtrip| FileCheck %s

uenoku · 2025-07-04T16:35:26Z

lib/Dialect/Datapath/DatapathFolds.cpp

+      auto newCompressOp = rewriter.create<CompressOp>(
+          op.getLoc(), inputs.drop_back(), op.getNumResults());
+
+      rewriter.replaceOp(op, newCompressOp.getResults());


Does this work?

Suggested change

auto newCompressOp = rewriter.create<CompressOp>(

op.getLoc(), inputs.drop_back(), op.getNumResults());

rewriter.replaceOp(op, newCompressOp.getResults());

rewriter.replaceOpWithNewOp<CompressOp>(

op, inputs.drop_back(), op.getNumResults());

uenoku · 2025-07-04T16:38:31Z

lib/Dialect/Datapath/DatapathFolds.cpp

+    while (newResults.size() < op.getNumResults())
+      newResults.push_back(zero);


Suggested change

while (newResults.size() < op.getNumResults())

newResults.push_back(zero);

newResults.append(op.getNumResults() - newResults.size(), zero);

Thanks for this - was looking for a neater way to do this!

uenoku · 2025-07-04T16:42:36Z

lib/Dialect/Datapath/DatapathFolds.cpp

+//===----------------------------------------------------------------------===//
+// Partial Product Operation
+//===----------------------------------------------------------------------===//
+struct ConstantFoldPartialProduct : public OpRewritePattern<PartialProductOp> {


nit: This canonicalization pattern looks like width narrowing. MLIR has folder API for constant folding so can we rename this pattern to avoid confusion?

cowardsa · 2025-07-07T08:44:29Z

Have now addressed the nits and still awaiting commit access approval so will need someone else to merge for me if satisfied please?

cowardsa added 24 commits July 1, 2025 11:52

Initialise datapath dialect implementation

157f8fc

Initial build working with datapath.compress operation defined - todo…

49846b5

… builder and assemblyFormat

Now with functional builder

aa029c6

Improve verifier - todo determine whether it is necessary to add the …

271dbb6

…explicit reduction factor

Resolve definition of compress op and include type constraints

4676369

Update datapath dialect operators

a8bd571

Compressor tree canonicalization - folding additional adders into a s…

8a39f00

…ingle compressor tree and removing zeros

Modify operator format to make it easier to read size of compressor tree

8311094

Add a partial product operator that can produce an arbitrary number o…

e6a88ce

…f results

Only fold compressors wiht a single use

9e36cd6

Formatting and code tidy-up

195e467

Datapath Dialect testing of canonicalizations and verifiers

f4a753d

Formatting correction

4d832fd

More formatting

fb7ea79

Define dialect include

76c34a4

Add boiler plate dialect definition

77b7f91

Formatting

6ff4361

Remove unecessary includes

836ba05

Remove unecessary includes

904d25c

Remove file header tags

981072f

Removed uneccessary include

d1235e5

Add datapath dialect documentation and rationale

b417f73

Merge branch 'coward/datapath_dialect_definition' into coward/datapat…

55314c1

…h_dialect_init

Merge branch 'main' into coward/datapath_dialect_init

0457ab3

uenoku reviewed Jul 3, 2025

View reviewed changes

cowardsa added 4 commits July 3, 2025 10:36

Formatting and updating canonicalization pass for compress constant fold

d66973a

Use SmallSetVector and update pp to partial_product (across all designs)

9c6fb89

Update formatting of PP

30439ee

Use custom-directives to avoid custom assembly format for datapath op…

9a2ee6e

…erators

cowardsa marked this pull request as ready for review July 3, 2025 14:13

Formatting

d13404e

maerhart reviewed Jul 3, 2025

View reviewed changes

cowardsa added 6 commits July 3, 2025 16:49

Additional comments and update formatting of compress

beee01e

Changing the compress format

ced00b5

Updated formatting of compress operator

0133263

Update documentation to reflect new format

41c66b7

Moving comments

2ad16c2

Formatting

067d29f

uenoku approved these changes Jul 4, 2025

View reviewed changes

Implement nit fixes from reviewers - mostly code simplifications

d02c3ac

uenoku merged commit f26f1ed into llvm:main Jul 7, 2025
7 checks passed

	%0:2 = datapath.compress %a, %b, %c : 3 x i16 -> (i16, i16)
	%0:2 = datapath.compress %a, %b, %c : i16

		@@ -0,0 +1,15 @@
		// RUN: circt-opt %s \| circt-opt \| FileCheck %s

	// RUN: circt-opt %s \| circt-opt \| FileCheck %s
	// RUN: circt-opt %s -verify-roundtrip\| FileCheck %s

		while (newResults.size() < op.getNumResults())
		newResults.push_back(zero);

	while (newResults.size() < op.getNumResults())
	newResults.push_back(zero);
	newResults.append(op.getNumResults() - newResults.size(), zero);

[Datapath] Operator definitions and canonicalization patterns #8647

[Datapath] Operator definitions and canonicalization patterns #8647

Uh oh!

Conversation

cowardsa commented Jul 3, 2025 • edited by uenoku Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

cowardsa commented Jul 3, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

cowardsa commented Jul 4, 2025

Uh oh!

uenoku left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

cowardsa commented Jul 7, 2025

Uh oh!

Uh oh!

Uh oh!

cowardsa commented Jul 3, 2025 •

edited by uenoku

Loading