llvm::HashRecognize Class Reference

The analysis. More...

#include "llvm/Analysis/HashRecognize.h"

Public Member Functions
LLVM_ABI	HashRecognize (const Loop &L, ScalarEvolution &SE)
LLVM_ABI std::variant< PolynomialInfo, StringRef >	recognizeCRC () const
	The main entry point for analyzing a loop and recognizing the CRC algorithm.
LLVM_ABI std::optional< PolynomialInfo >	getResult () const
LLVM_ABI void	print (raw_ostream &OS) const
LLVM_DUMP_METHOD void	dump () const

Static Public Member Functions
static LLVM_ABI CRCTable	genSarwateTable (const APInt &GenPoly, bool IsBigEndian)
	Generate a lookup table of 256 entries by interleaving the generating polynomial.
static LLVM_ABI std::pair< APInt, APInt >	genBarrettConstants (const PolynomialInfo &Info)
	Auxilary entry point after analysis to generate constants for a GF(2) Barrett Reduction.

Detailed Description

The analysis.

Definition at line 75 of file HashRecognize.h.

Constructor & Destructor Documentation

HashRecognize()

HashRecognize::HashRecognize	(	const Loop &	L,
		ScalarEvolution &	SE )

Definition at line 664 of file HashRecognize.cpp.

Referenced by getResult().

Member Function Documentation

dump()

void HashRecognize::dump

(

)

const

Definition at line 654 of file HashRecognize.cpp.

References llvm::dbgs(), and print().

genBarrettConstants()

std::pair< APInt, APInt > HashRecognize::genBarrettConstants ( const PolynomialInfo & Info )

static

Auxilary entry point after analysis to generate constants for a GF(2) Barrett Reduction.

Generate the constants for performing a Polynomial (GF(2)) Barrett Reduction according to Intel's Fast CRC Computation white paper with some adjustments to account for the fact that bit width and trip count can vary.

Returns a pair of Mu of bitwidth TC+1 and FullGenPoly of bitwidth BW+1. Mu is used in the first clmul operation. Mu = floor(x^(BW+TC) / P(x)). FullGenPoly is used in the second clmul operation, and is Info.RHS with the implied BW'th bit. Endianness is accounted for using Info.IsBigEndian.

Definition at line 414 of file HashRecognize.cpp.

References floorDivideGF2(), llvm::APInt::getBitWidth(), llvm::APInt::getOneBitSet(), llvm::APInt::reverseBits(), llvm::APInt::setBit(), llvm::APInt::trunc(), and llvm::APInt::zext().

Referenced by print().

genSarwateTable()

CRCTable HashRecognize::genSarwateTable ( const APInt & GenPoly, bool IsBigEndian )

static

Generate a lookup table of 256 entries by interleaving the generating polynomial.

The optimization technique of table-lookup for CRC is also called the Sarwate algorithm.

Definition at line 353 of file HashRecognize.cpp.

References llvm::APInt::getBitWidth(), llvm::APInt::getSignedMinValue(), llvm::APInt::getZero(), I, llvm::APInt::isSignBitSet(), llvm::APInt::lshr(), and llvm::APInt::shl().

Referenced by print().

getResult()

std::optional< PolynomialInfo > HashRecognize::getResult

(

)

const

Definition at line 657 of file HashRecognize.cpp.

References HashRecognize().

print()

void HashRecognize::print

(

raw_ostream &

OS

)

const

Definition at line 610 of file HashRecognize.cpp.

References genBarrettConstants(), genSarwateTable(), llvm::raw_ostream::indent(), llvm::CRCTable::print(), and recognizeCRC().

Referenced by dump(), and llvm::HashRecognizePrinterPass::run().

recognizeCRC()

std::variant< PolynomialInfo, StringRef > HashRecognize::recognizeCRC

(

)

const

The main entry point for analyzing a loop and recognizing the CRC algorithm.

Returns a PolynomialInfo on success, and a StringRef on failure.

Definition at line 505 of file HashRecognize.cpp.

References assert(), llvm::cast(), containsUnreachable(), llvm::PHINode::getIncomingValueForBlock(), llvm::Type::getIntegerBitWidth(), getRecurrences(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), isBigEndianBitShift(), isConditionalOnXorOfPHIs(), isSignificantBitCheckWellFormed(), llvm::none_of(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by print().

---

The documentation for this class was generated from the following files:

• include/llvm/Analysis/HashRecognize.h
• lib/Analysis/HashRecognize.cpp