#include "circt/Dialect/Comb/CombOps.h"
#include "circt/Dialect/HW/HWAttributes.h"
#include "circt/Dialect/HW/HWOps.h"
#include "mlir/IR/Matchers.h"
#include "mlir/IR/PatternMatch.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/TypeSwitch.h"
#include "llvm/Support/KnownBits.h"

Include dependency graph for CombFolds.cpp:

Functions
static bool	hasOperandsOutsideOfBlock (Operation *op)
	In comb, we assume no knowledge of the semantics of cross-block dataflow. More...

static Value	createGenericOp (Location loc, OperationName name, ArrayRef< Value > operands, OpBuilder &builder)
	Create a new instance of a generic operation that only has value operands, and has a single result value whose type matches the first operand. More...

static TypedAttr	getIntAttr (const APInt &value, MLIRContext *context)

static void	getConcatOperands (Value v, SmallVectorImpl< Value > &result)
	Flatten concat and mux operands into a vector. More...

static void	replaceOpAndCopyName (PatternRewriter &rewriter, Operation *op, Value newValue)
	A wrapper of `PatternRewriter::replaceOp` to propagate "sv.namehint" attribute. More...

template<typename OpTy , typename... Args>
static OpTy	replaceOpWithNewOpAndCopyName (PatternRewriter &rewriter, Operation *op, Args &&...args)
	A wrapper of `PatternRewriter::replaceOpWithNewOp` to propagate "sv.namehint" attribute. More...

static bool	hasSVAttributes (Operation *op)

template<typename SubType >
static ComplementMatcher< SubType >	m_Complement (const SubType &subExpr)

static bool	shouldBeFlattened (Operation *op)
	Return true if the op will be flattened afterwards. More...

static bool	tryFlatteningOperands (Operation *op, PatternRewriter &rewriter)
	Flattens a single input in `op` if `hasOneUse` is true and it can be defined as an Op. More...

static std::pair< size_t, size_t >	getLowestBitAndHighestBitRequired (Operation *op, bool narrowTrailingBits, size_t originalOpWidth)

template<class OpTy >
static bool	narrowOperationWidth (OpTy op, bool narrowTrailingBits, PatternRewriter &rewriter)

static Attribute	constFoldBinaryOp (ArrayRef< Attribute > operands, hw::PEO paramOpcode)
	Performs constant folding `calculate` with element-wise behavior on the two attributes in `operands` and returns the result if possible. More...

static LogicalResult	extractConcatToConcatExtract (ExtractOp op, ConcatOp innerCat, PatternRewriter &rewriter)

static bool	extractFromReplicate (ExtractOp op, ReplicateOp replicate, PatternRewriter &rewriter)

static Attribute	constFoldAssociativeOp (ArrayRef< Attribute > operands, hw::PEO paramOpcode)

static bool	canonicalizeLogicalCstWithConcat (Operation *logicalOp, size_t concatIdx, const APInt &cst, PatternRewriter &rewriter)
	When we find a logical operation (and, or, xor) with a constant e.g. More...

static bool	canCombineOppositeBinCmpIntoConstant (OperandRange operands)

template<typename Op >
static Value	getCommonOperand (Op op)
	Returns a single common operand that all inputs of the operation `op` can be traced back to, or an empty `Value` if no such operand exists. More...

template<typename Op >
static bool	canonicalizeIdempotentInputs (Op op, PatternRewriter &rewriter)
	Canonicalize an idempotent operation `op` so that only one input of any kind occurs. More...

static void	canonicalizeXorIcmpTrue (XorOp op, unsigned icmpOperand, PatternRewriter &rewriter)

template<class Op , bool isSigned>
static OpFoldResult	foldDiv (Op op, ArrayRef< Attribute > constants)

template<class Op , bool isSigned>
static OpFoldResult	foldMod (Op op, ArrayRef< Attribute > constants)

static bool	getMuxChainCondConstant (Value cond, Value indexValue, bool isInverted, std::function< void(hw::ConstantOp)> constantFn)
	Check to see if the condition to the specified mux is an equality comparison `indexValue` and one or more constants. More...

static bool	foldMuxChain (MuxOp rootMux, bool isFalseSide, PatternRewriter &rewriter)
	Given a mux, check to see if the "on true" value (or "on false" value if isFalseSide=true) is a mux tree with the same condition. More...

static Value	extractOperandFromFullyAssociative (Operation *fullyAssoc, size_t operandNo, PatternRewriter &rewriter)
	Given a fully associative variadic operation like (a+b+c+d), break the expression into two parts, one without the specified operand (e.g. More...

static bool	foldCommonMuxValue (MuxOp op, bool isTrueOperand, PatternRewriter &rewriter)
	Fold things like `mux(cond, x\|y\|z\|a, a)` -> `(x\|y\|z)&replicate(cond)\|a` and `mux(cond, a, x\|y\|z\|a) ->`(x\|y\|z)&replicate(~cond) \| a` (when isTrueOperand is true. More...

static bool	foldCommonMuxOperation (MuxOp mux, Operation trueOp, Operation falseOp, PatternRewriter &rewriter)
	This function is invoke when we find a mux with true/false operations that have the same opcode. More...

static bool	foldMuxOfUniformArrays (MuxOp op, PatternRewriter &rewriter)

static bool	applyCmpPredicate (ICmpPredicate predicate, const APInt &lhs, const APInt &rhs)

static bool	applyCmpPredicateToEqualOperands (ICmpPredicate predicate)

template<typename Range >
static size_t	computeCommonPrefixLength (const Range &a, const Range &b)

static size_t	getTotalWidth (ArrayRef< Value > operands)

static LogicalResult	matchAndRewriteCompareConcat (ICmpOp op, Operation lhs, Operation rhs, PatternRewriter &rewriter)
	Reduce the strength icmp(concat(...), concat(...)) by doing a element-wise comparison on common prefix and suffixes. More...

static void	combineEqualityICmpWithKnownBitsAndConstant (ICmpOp cmpOp, const KnownBits &bitAnalysis, const APInt &rhsCst, PatternRewriter &rewriter)
	Given an equality comparison with a constant value and some operand that has known bits, simplify the comparison to check only the unknown bits of the input. More...

static void	combineEqualityICmpWithXorOfConstant (ICmpOp cmpOp, XorOp xorOp, const APInt &rhs, PatternRewriter &rewriter)

Function Documentation

◆ applyCmpPredicate()

static bool applyCmpPredicate	(	ICmpPredicate	predicate,
		const APInt &	lhs,
		const APInt &	rhs
	)

static

Definition at line 2691 of file CombFolds.cpp.

◆ applyCmpPredicateToEqualOperands()

static bool applyCmpPredicateToEqualOperands ( ICmpPredicate predicate )

static

Definition at line 2728 of file CombFolds.cpp.

Referenced by matchAndRewriteCompareConcat().

◆ canCombineOppositeBinCmpIntoConstant()

static bool canCombineOppositeBinCmpIntoConstant ( OperandRange operands )

static

Definition at line 836 of file CombFolds.cpp.

◆ canonicalizeIdempotentInputs()

template<typename Op >

static bool canonicalizeIdempotentInputs	(	Op	op,
		PatternRewriter &	rewriter
	)

static

Canonicalize an idempotent operation op so that only one input of any kind occurs.

Example: and(x, y, x, z) -> and(x, y, z)

Definition at line 946 of file CombFolds.cpp.

◆ canonicalizeLogicalCstWithConcat()

static bool canonicalizeLogicalCstWithConcat	(	Operation *	logicalOp,
		size_t	concatIdx,
		const APInt &	cst,
		PatternRewriter &	rewriter
	)

static

When we find a logical operation (and, or, xor) with a constant e.g.

X & 42, we want to push the constant into the computation of X if it leads to simplification.

This function handles the case where the logical operation has a concat operand. We check to see if we can simplify the concat, e.g. when it has constant operands.

This returns true when a simplification happens.

Definition at line 759 of file CombFolds.cpp.

References assert(), hw.ConstantOp::create(), createGenericOp(), and replaceOpAndCopyName().

◆ canonicalizeXorIcmpTrue()

static void canonicalizeXorIcmpTrue	(	XorOp	op,
		unsigned	icmpOperand,
		PatternRewriter &	rewriter
	)

static

Definition at line 1308 of file CombFolds.cpp.

References replaceOpAndCopyName().

◆ combineEqualityICmpWithKnownBitsAndConstant()

static void combineEqualityICmpWithKnownBitsAndConstant	(	ICmpOp	cmpOp,
		const KnownBits &	bitAnalysis,
		const APInt &	rhsCst,
		PatternRewriter &	rewriter
	)

static

Given an equality comparison with a constant value and some operand that has known bits, simplify the comparison to check only the unknown bits of the input.

One simple example of this is that concat(0, stuff) == 0 can be simplified to stuff == 0, or and(x, 3) == 0 can be simplified to extract x[1:0] == 0

Definition at line 2902 of file CombFolds.cpp.

◆ combineEqualityICmpWithXorOfConstant()

static void combineEqualityICmpWithXorOfConstant	(	ICmpOp	cmpOp,
		XorOp	xorOp,
		const APInt &	rhs,
		PatternRewriter &	rewriter
	)

static

Definition at line 2986 of file CombFolds.cpp.

References hw.ConstantOp::create().

◆ computeCommonPrefixLength()

template<typename Range >

static size_t computeCommonPrefixLength	(	const Range &	a,
		const Range &	b
	)

static

Definition at line 2775 of file CombFolds.cpp.

Referenced by matchAndRewriteCompareConcat().

◆ constFoldAssociativeOp()

static Attribute constFoldAssociativeOp	(	ArrayRef< Attribute >	operands,
		hw::PEO	paramOpcode
	)

static

Definition at line 724 of file CombFolds.cpp.

References assert(), and circt::calyx::direction::get().

◆ constFoldBinaryOp()

static Attribute constFoldBinaryOp	(	ArrayRef< Attribute >	operands,
		hw::PEO	paramOpcode
	)

static

Performs constant folding calculate with element-wise behavior on the two attributes in operands and returns the result if possible.

Definition at line 346 of file CombFolds.cpp.

References assert(), and circt::calyx::direction::get().

Referenced by foldDiv(), and foldMod().

◆ createGenericOp()

static Value createGenericOp	(	Location	loc,
		OperationName	name,
		ArrayRef< Value >	operands,
		OpBuilder &	builder
	)

static

Create a new instance of a generic operation that only has value operands, and has a single result value whose type matches the first operand.

This should not be used to create instances of ops with attributes or with more complicated type signatures.

Definition at line 44 of file CombFolds.cpp.

Referenced by canonicalizeLogicalCstWithConcat(), extractOperandFromFullyAssociative(), and tryFlatteningOperands().

◆ extractConcatToConcatExtract()

static LogicalResult extractConcatToConcatExtract	(	ExtractOp	op,
		ConcatOp	innerCat,
		PatternRewriter &	rewriter
	)

static

Definition at line 507 of file CombFolds.cpp.

References assert(), circt::calyx::direction::get(), and replaceOpAndCopyName().

◆ extractFromReplicate()

static bool extractFromReplicate	(	ExtractOp	op,
		ReplicateOp	replicate,
		PatternRewriter &	rewriter
	)

static

Definition at line 588 of file CombFolds.cpp.

◆ extractOperandFromFullyAssociative()

static Value extractOperandFromFullyAssociative	(	Operation *	fullyAssoc,
		size_t	operandNo,
		PatternRewriter &	rewriter
	)

static

Given a fully associative variadic operation like (a+b+c+d), break the expression into two parts, one without the specified operand (e.g.

tmp = a+b+d) and one that combines that into the full expression (e.g. tmp+c), and return the inner expression.

NOTE: This mutates the operation in place if it only has a single user, which assumes that user will be removed.

Definition at line 2115 of file CombFolds.cpp.

References assert(), createGenericOp(), and replaceOpAndCopyName().

Referenced by foldCommonMuxValue().

◆ foldCommonMuxOperation()

static bool foldCommonMuxOperation	(	MuxOp	mux,
		Operation *	trueOp,
		Operation *	falseOp,
		PatternRewriter &	rewriter
	)

static

This function is invoke when we find a mux with true/false operations that have the same opcode.

Check to see if we can strength reduce the mux by applying it to less data by applying this transformation: mux(cond, op(a, b), op(a, c)) -> op(a, mux(cond, b, c))

Definition at line 2254 of file CombFolds.cpp.

References getConcatOperands(), and replaceOpAndCopyName().

◆ foldCommonMuxValue()

static bool foldCommonMuxValue	(	MuxOp	op,
		bool	isTrueOperand,
		PatternRewriter &	rewriter
	)

static

Fold things like mux(cond, x|y|z|a, a) -> (x|y|z)&replicate(cond)|a and mux(cond, a, x|y|z|a) ->(x|y|z)&replicate(~cond) | a` (when isTrueOperand is true.

Return true on successful transformation, false if not.

These are various forms of "predicated ops" that can be handled with a replicate/and combination.

Definition at line 2156 of file CombFolds.cpp.

References assert(), circt::comb::createOrFoldNot(), and extractOperandFromFullyAssociative().

◆ foldDiv()

template<class Op , bool isSigned>

static OpFoldResult foldDiv	(	Op	op,
		ArrayRef< Attribute >	constants
	)

static

Definition at line 1657 of file CombFolds.cpp.

References constFoldBinaryOp().

◆ foldMod()

template<class Op , bool isSigned>

static OpFoldResult foldMod	(	Op	op,
		ArrayRef< Attribute >	constants
	)

static

Definition at line 1686 of file CombFolds.cpp.

References constFoldBinaryOp(), and getIntAttr().

◆ foldMuxChain()

static bool foldMuxChain	(	MuxOp	rootMux,
		bool	isFalseSide,
		PatternRewriter &	rewriter
	)

static

Given a mux, check to see if the "on true" value (or "on false" value if isFalseSide=true) is a mux tree with the same condition.

This allows us to turn things like mux(VAL == 0, A, (mux (VAL == 1), B, C)) into array_get (array_create(A, B, C), VAL) which is far more compact and allows synthesis tools to do more interesting optimizations.

This returns false if we cannot form the mux tree (or do not want to) and returns true if the mux was replaced.

Extract constants and values into valuesFound and return true if this is part of the mux tree, otherwise return false.

Definition at line 2002 of file CombFolds.cpp.

References getMuxChainCondConstant().

◆ foldMuxOfUniformArrays()

static bool foldMuxOfUniformArrays	(	MuxOp	op,
		PatternRewriter &	rewriter
	)

static

Definition at line 2349 of file CombFolds.cpp.

References hw.ArrayCreateOp::create().

◆ getCommonOperand()

template<typename Op >

static Value getCommonOperand ( Op op )

static

Returns a single common operand that all inputs of the operation op can be traced back to, or an empty Value if no such operand exists.

For example for or(a[0], a[1], ..., a[n-1]) this function returns a (assuming the bit-width of a is n).

Definition at line 911 of file CombFolds.cpp.

◆ getConcatOperands()

static void getConcatOperands	(	Value	v,
		SmallVectorImpl< Value > &	result
	)

static

Flatten concat and mux operands into a vector.

Definition at line 58 of file CombFolds.cpp.

References concat().

Referenced by foldCommonMuxOperation(), and matchAndRewriteCompareConcat().

◆ getIntAttr()

static TypedAttr getIntAttr	(	const APInt &	value,
		MLIRContext *	context
	)

static

Definition at line 52 of file CombFolds.cpp.

References circt::calyx::direction::get().

Referenced by foldMod().

◆ getLowestBitAndHighestBitRequired()

static std::pair<size_t, size_t> getLowestBitAndHighestBitRequired	(	Operation *	op,
		bool	narrowTrailingBits,
		size_t	originalOpWidth
	)

static

Definition at line 222 of file CombFolds.cpp.

References assert().

Referenced by narrowOperationWidth().

◆ getMuxChainCondConstant()

static bool getMuxChainCondConstant	(	Value	cond,
		Value	indexValue,
		bool	isInverted,
		std::function< void(hw::ConstantOp)>	constantFn
	)

static

Check to see if the condition to the specified mux is an equality comparison indexValue and one or more constants.

If so, put the constants in the constants vector and return true, otherwise return false.

This is part of foldMuxChain.

Definition at line 1955 of file CombFolds.cpp.

Referenced by foldMuxChain().

◆ getTotalWidth()

static size_t getTotalWidth ( ArrayRef< Value > operands )

static

Definition at line 2789 of file CombFolds.cpp.

References assert().

Referenced by matchAndRewriteCompareConcat().

◆ hasOperandsOutsideOfBlock()

static bool hasOperandsOutsideOfBlock ( Operation * op )

static

In comb, we assume no knowledge of the semantics of cross-block dataflow.

As such, cross-block dataflow is interpreted as a canonicalization barrier. This is a conservative approach which:

still allows for efficient canonicalization for the common CIRCT usecase of comb (comb logic nested inside single-block hw.module's)
allows comb operations to be used in non-HW container ops - that may use MLIR blocks and regions to represent various forms of hierarchical abstractions, thus allowing comb to compose with other dialects.

Definition at line 32 of file CombFolds.cpp.

◆ hasSVAttributes()

static bool hasSVAttributes ( Operation * op )

static

Definition at line 103 of file CombFolds.cpp.

Referenced by findNestedElseIf().

◆ m_Complement()

template<typename SubType >

static ComplementMatcher<SubType> m_Complement ( const SubType & subExpr )

inlinestatic

Definition at line 120 of file CombFolds.cpp.

◆ matchAndRewriteCompareConcat()

static LogicalResult matchAndRewriteCompareConcat	(	ICmpOp	op,
		Operation *	lhs,
		Operation *	rhs,
		PatternRewriter &	rewriter
	)

static

Reduce the strength icmp(concat(...), concat(...)) by doing a element-wise comparison on common prefix and suffixes.

Returns success() if a rewriting happens. This handles both concat and replicate.

Definition at line 2804 of file CombFolds.cpp.

References applyCmpPredicateToEqualOperands(), assert(), computeCommonPrefixLength(), comb.ExtractOp::create(), getConcatOperands(), and getTotalWidth().

◆ narrowOperationWidth()

template<class OpTy >

static bool narrowOperationWidth	(	OpTy	op,
		bool	narrowTrailingBits,
		PatternRewriter &	rewriter
	)

static

Definition at line 253 of file CombFolds.cpp.

References getLowestBitAndHighestBitRequired().

◆ replaceOpAndCopyName()

static void replaceOpAndCopyName	(	PatternRewriter &	rewriter,
		Operation *	op,
		Value	newValue
	)

static

A wrapper of PatternRewriter::replaceOp to propagate "sv.namehint" attribute.

If a replaced op has a "sv.namehint" attribute, this function propagates the name to the new value.

Definition at line 73 of file CombFolds.cpp.

Referenced by canonicalizeLogicalCstWithConcat(), canonicalizeXorIcmpTrue(), extractConcatToConcatExtract(), extractOperandFromFullyAssociative(), foldCommonMuxOperation(), and tryFlatteningOperands().

◆ replaceOpWithNewOpAndCopyName()

template<typename OpTy , typename... Args>

static OpTy replaceOpWithNewOpAndCopyName	(	PatternRewriter &	rewriter,
		Operation *	op,
		Args &&...	args
	)

static

A wrapper of PatternRewriter::replaceOpWithNewOp to propagate "sv.namehint" attribute.

If a replaced op has a "sv.namehint" attribute, this function propagates the name to the new value.

Definition at line 88 of file CombFolds.cpp.

◆ shouldBeFlattened()

static bool shouldBeFlattened ( Operation * op )

static

Return true if the op will be flattened afterwards.

Op will be flattend if it has a single user which has a same op type. User must be in same block.

Definition at line 126 of file CombFolds.cpp.

References assert().

Referenced by tryFlatteningOperands().

◆ tryFlatteningOperands()

static bool tryFlatteningOperands	(	Operation *	op,
		PatternRewriter &	rewriter
	)

static

Flattens a single input in op if hasOneUse is true and it can be defined as an Op.

Returns true if successful, and false otherwise.

Example: op(1, 2, op(3, 4), 5) -> op(1, 2, 3, 4, 5) // returns true

Definition at line 144 of file CombFolds.cpp.

References createGenericOp(), circt::calyx::direction::get(), replaceOpAndCopyName(), and shouldBeFlattened().

Functions

Function Documentation

◆ applyCmpPredicate()

◆ applyCmpPredicateToEqualOperands()

◆ canCombineOppositeBinCmpIntoConstant()

◆ canonicalizeIdempotentInputs()

◆ canonicalizeLogicalCstWithConcat()

◆ canonicalizeXorIcmpTrue()

◆ combineEqualityICmpWithKnownBitsAndConstant()

◆ combineEqualityICmpWithXorOfConstant()

◆ computeCommonPrefixLength()

◆ constFoldAssociativeOp()

◆ constFoldBinaryOp()

◆ createGenericOp()

◆ extractConcatToConcatExtract()

◆ extractFromReplicate()

◆ extractOperandFromFullyAssociative()

◆ foldCommonMuxOperation()

◆ foldCommonMuxValue()

◆ foldDiv()

◆ foldMod()

◆ foldMuxChain()

◆ foldMuxOfUniformArrays()

◆ getCommonOperand()

◆ getConcatOperands()

◆ getIntAttr()

◆ getLowestBitAndHighestBitRequired()

◆ getMuxChainCondConstant()

◆ getTotalWidth()

◆ hasOperandsOutsideOfBlock()

◆ hasSVAttributes()

◆ m_Complement()

◆ matchAndRewriteCompareConcat()

◆ narrowOperationWidth()

◆ replaceOpAndCopyName()

◆ replaceOpWithNewOpAndCopyName()

◆ shouldBeFlattened()

◆ tryFlatteningOperands()