Classes
struct	ZextByMatcher
struct	ReplExtMatcher
struct	SextByMatcher
class	CombinationalVisitor
	This helps visit Combinational nodes. More...

Enumerations
enum	MuxChainWithComparisonFoldingStyle { None , BalancedMuxTree , ArrayGet }
	Enum for mux chain folding styles. More...

Functions
KnownBits	computeKnownBits (Value value, unsigned maxDepth=5)
	Compute "known bits" information about the specified value - the set of bits that are guaranteed to always be zero, and the set of bits that are guaranteed to always be one (these must be exclusive!).
bool	shouldUseBoothEncoding (Value lhs, Value rhs, unsigned threshold=16)
	Return true when both operands are wider than the bitwidth threshold, have matching extension kinds (both zero-extended, both sign-extended, or neither), and should use Booth encoding.
Value	createZExt (OpBuilder &builder, Location loc, Value value, unsigned targetWidth)
	Create the ops to zero-extend a value to an integer of equal or larger type.
Value	createOrFoldSExt (OpBuilder &builder, Location loc, Value value, Type destTy)
	Create a sign extension operation from a value of integer type to an equal or larger integer type.
Value	createOrFoldSExt (ImplicitLocOpBuilder &builder, Value value, Type destTy)
Value	createOrFoldNot (OpBuilder &builder, Location loc, Value value, bool twoState=false)
	Create a ``Not'' gate on a value.
Value	createOrFoldNot (ImplicitLocOpBuilder &builder, Value value, bool twoState=false)
void	extractBits (OpBuilder &builder, Value val, SmallVectorImpl< Value > &bits)
	Extract bits from a value.
Value	constructMuxTree (OpBuilder &builder, Location loc, ArrayRef< Value > selectors, ArrayRef< Value > leafNodes, Value outOfBoundsValue)
	Construct a mux tree for given leaf nodes.
Value	createDynamicExtract (OpBuilder &builder, Location loc, Value value, Value offset, unsigned width)
	Extract a range of bits from an integer at a dynamic offset.
Value	createDynamicInject (OpBuilder &builder, Location loc, Value value, Value offset, Value replacement, bool twoState=false)
	Replace a range of bits in an integer at a dynamic offset, and return the updated integer value.
Value	createInject (OpBuilder &builder, Location loc, Value value, unsigned offset, Value replacement)
	Replace a range of bits in an integer and return the updated integer value.
LogicalResult	convertSubToAdd (comb::SubOp subOp, mlir::PatternRewriter &rewriter)
	Replace a subtraction with an addition of the two's complement.
LogicalResult	convertDivUByPowerOfTwo (DivUOp divOp, mlir::PatternRewriter &rewriter)
	Convert unsigned division or modulo by a power of two.
LogicalResult	convertModUByPowerOfTwo (ModUOp modOp, mlir::PatternRewriter &rewriter)
bool	foldMuxChainWithComparison (PatternRewriter &rewriter, MuxOp rootMux, bool isFalseSide, llvm::function_ref< MuxChainWithComparisonFoldingStyle(size_t indexWidth, size_t numEntries)> styleFn)
	Mux chain folding that converts chains of muxes with index comparisons into array operations or balanced mux trees.
template<typename SubType>
static ZextByMatcher< SubType >	m_ZextBy (const SubType &subExpr)
	Helper function to create a zero extension matcher.
template<typename SubType>
static ReplExtMatcher< SubType >	m_ReplExt (const SubType &subExpr)
	Helper function to create a replicated extension matcher.
template<typename SubType>
static SextByMatcher< SubType >	m_SextBy (const SubType &subExpr)
	Helper function to create a sign extension matcher.
void	populateCombNarrowingPatterns (mlir::RewritePatternSet &patterns, mlir::DataFlowSolver &solver)
	Add patterns for int range based narrowing.

Enumeration Type Documentation

◆ MuxChainWithComparisonFoldingStyle

enum circt::comb::MuxChainWithComparisonFoldingStyle

Enum for mux chain folding styles.

Enumerator
None
BalancedMuxTree
ArrayGet

Definition at line 110 of file CombOps.h.

Function Documentation

◆ computeKnownBits()

KnownBits circt::comb::computeKnownBits	(	Value	v,
		unsigned	maxDepth = 5 )

Compute "known bits" information about the specified value - the set of bits that are guaranteed to always be zero, and the set of bits that are guaranteed to always be one (these must be exclusive!).

Given an integer SSA value, check to see if we know anything about the result of the computation.

A bit that exists in neither set is unknown.

For example, we know that "and with a constant" always returns zeros for the zero bits in a constant.

Expression trees can be very large, so we need to make sure to cap our recursion, this is controlled by maxDepth.

Definition at line 22 of file CombAnalysis.cpp.

References computeKnownBits().

Referenced by addLowBitsCannotCarry(), calculateNonZeroBits(), circt::datapath::CompressorTree::CompressorTree(), computeKnownBits(), extractFromAdd(), and subLowBitsCannotBorrow().

◆ constructMuxTree()

Value circt::comb::constructMuxTree	(	OpBuilder &	builder,
		Location	loc,
		ArrayRef< Value >	selectors,
		ArrayRef< Value >	leafNodes,
		Value	outOfBoundsValue )

Construct a mux tree for given leaf nodes.

selectors is the selector for each level of the tree. Currently the selector is tested from MSB to LSB.

Definition at line 151 of file CombOps.cpp.

◆ convertDivUByPowerOfTwo()

LogicalResult circt::comb::convertDivUByPowerOfTwo	(	DivUOp	divOp,
		mlir::PatternRewriter &	rewriter )

Convert unsigned division or modulo by a power of two.

For division: divu(x, 2^n) -> concat(0...0, extract(x, n, width-n)). For modulo: modu(x, 2^n) -> concat(0...0, extract(x, 0, n)) TODO: Support signed division and modulo.

◆ convertModUByPowerOfTwo()

LogicalResult circt::comb::convertModUByPowerOfTwo	(	ModUOp	modOp,
		mlir::PatternRewriter &	rewriter )

◆ convertSubToAdd()

llvm::LogicalResult circt::comb::convertSubToAdd	(	comb::SubOp	subOp,
		mlir::PatternRewriter &	rewriter )

Replace a subtraction with an addition of the two's complement.

Definition at line 267 of file CombOps.cpp.

References hw.ConstantOp::create(), circt::replaceOpWithNewOpAndCopyNamehint(), and success().

◆ createDynamicExtract()

Value circt::comb::createDynamicExtract	(	OpBuilder &	builder,
		Location	loc,
		Value	value,
		Value	offset,
		unsigned	width )

Extract a range of bits from an integer at a dynamic offset.

Definition at line 178 of file CombOps.cpp.

References assert(), and createZExt().

Referenced by unpackProjections().

◆ createDynamicInject()

Value circt::comb::createDynamicInject	(	OpBuilder &	builder,
		Location	loc,
		Value	value,
		Value	offset,
		Value	replacement,
		bool	twoState = false )

Replace a range of bits in an integer at a dynamic offset, and return the updated integer value.

Calls createInject if the offset is constant.

Definition at line 198 of file CombOps.cpp.

References assert(), hw.ConstantOp::create(), createInject(), createOrFoldNot(), and createZExt().

Referenced by packProjections().

◆ createInject()

Value circt::comb::createInject	(	OpBuilder &	builder,
		Location	loc,
		Value	value,
		unsigned	offset,
		Value	replacement )

Replace a range of bits in an integer and return the updated integer value.

Definition at line 233 of file CombOps.cpp.

References assert(), and comb.ExtractOp::create().

Referenced by createDynamicInject().

◆ createOrFoldNot() [1/2]

Value circt::comb::createOrFoldNot	(	ImplicitLocOpBuilder &	builder,
		Value	value,
		bool	twoState = false )

Definition at line 118 of file CombOps.cpp.

References createOrFoldNot().

◆ createOrFoldNot() [2/2]

Value circt::comb::createOrFoldNot	(	OpBuilder &	builder,
		Location	loc,
		Value	value,
		bool	twoState = false )

Create a ``Not'' gate on a value.

Definition at line 112 of file CombOps.cpp.

References hw.ConstantOp::create().

Referenced by circt::scftocalyx::BuildOpGroups::buildFpIntTypeCastOp(), circt::scftocalyx::BuildOpGroups::buildLibraryBinaryPipeOp(), circt::scftocalyx::BuildOpGroups::buildOp(), ConvertCellOp::convertPipelineOp(), ConvertCellOp::convertPrimitiveOp(), createDynamicInject(), createOrFoldNot(), SextCompress::matchAndRewrite(), SignedPartialProducts::matchAndRewrite(), SignedPosPartialProducts::matchAndRewrite(), and CompileControlVisitor::visit().

◆ createOrFoldSExt() [1/2]

Value circt::comb::createOrFoldSExt	(	ImplicitLocOpBuilder &	builder,
		Value	value,
		Type	destTy )

◆ createOrFoldSExt() [2/2]

Value circt::comb::createOrFoldSExt	(	OpBuilder &	builder,
		Location	loc,
		Value	value,
		Type	destTy )

Create a sign extension operation from a value of integer type to an equal or larger integer type.

Referenced by ConvertCellOp::convertPrimitiveOp().

◆ createZExt()

Value circt::comb::createZExt	(	OpBuilder &	builder,
		Location	loc,
		Value	value,
		unsigned	targetWidth )

Create the ops to zero-extend a value to an integer of equal or larger type.

Definition at line 71 of file CombOps.cpp.

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

Referenced by createDynamicExtract(), createDynamicInject(), SextCompress::matchAndRewrite(), SignedPartialProducts::matchAndRewrite(), SignedPosPartialProducts::matchAndRewrite(), and zeroPad().

◆ extractBits()

void circt::comb::extractBits	(	OpBuilder &	builder,
		Value	val,
		SmallVectorImpl< Value > &	bits )

Extract bits from a value.

Definition at line 124 of file CombOps.cpp.

References assert(), and concat().

Referenced by extractBits().

◆ foldMuxChainWithComparison()

bool circt::comb::foldMuxChainWithComparison	(	PatternRewriter &	rewriter,
		MuxOp	rootMux,
		bool	isFalseSide,
		llvm::function_ref< MuxChainWithComparisonFoldingStyle(size_t indexWidth, size_t numEntries)>	styleFn )

Mux chain folding that converts chains of muxes with index comparisons into array operations or balanced mux trees.

styleFn is a callback that returns the desired folding style based on the index width and number of entries.

◆ m_ReplExt()

template<typename SubType>

ReplExtMatcher< SubType > circt::comb::m_ReplExt ( const SubType & subExpr )

inlinestatic

Helper function to create a replicated extension matcher.

Definition at line 186 of file CombOps.h.

Referenced by SextCompress::matchAndRewrite().

◆ m_SextBy()

template<typename SubType>

SextByMatcher< SubType > circt::comb::m_SextBy ( const SubType & subExpr )

inlinestatic

Helper function to create a sign extension matcher.

Definition at line 239 of file CombOps.h.

Referenced by getBaseOfExt(), SextCompress::matchAndRewrite(), SignedPartialProducts::matchAndRewrite(), and SignedPosPartialProducts::matchAndRewrite().

◆ m_ZextBy()

template<typename SubType>

ZextByMatcher< SubType > circt::comb::m_ZextBy ( const SubType & subExpr )

inlinestatic

Helper function to create a zero extension matcher.

Definition at line 149 of file CombOps.h.

Referenced by getBaseOfExt().

◆ populateCombNarrowingPatterns()

void circt::comb::populateCombNarrowingPatterns	(	mlir::RewritePatternSet &	patterns,
		mlir::DataFlowSolver &	solver )

Add patterns for int range based narrowing.

◆ shouldUseBoothEncoding()

bool circt::comb::shouldUseBoothEncoding	(	Value	lhs,
		Value	rhs,
		unsigned	threshold = 16 )

Return true when both operands are wider than the bitwidth threshold, have matching extension kinds (both zero-extended, both sign-extended, or neither), and should use Booth encoding.

Definition at line 32 of file CombOps.cpp.

Referenced by SignedPartialProducts::matchAndRewrite(), and SignedPosPartialProducts::matchAndRewrite().

Classes

Enumerations

Functions

Enumeration Type Documentation

◆ MuxChainWithComparisonFoldingStyle

Function Documentation

◆ computeKnownBits()

◆ constructMuxTree()

◆ convertDivUByPowerOfTwo()

◆ convertModUByPowerOfTwo()

◆ convertSubToAdd()

◆ createDynamicExtract()

◆ createDynamicInject()

◆ createInject()

◆ createOrFoldNot() [1/2]

◆ createOrFoldNot() [2/2]

◆ createOrFoldSExt() [1/2]

◆ createOrFoldSExt() [2/2]

◆ createZExt()

◆ extractBits()

◆ foldMuxChainWithComparison()

◆ m_ReplExt()

◆ m_SextBy()

◆ m_ZextBy()

◆ populateCombNarrowingPatterns()

◆ shouldUseBoothEncoding()