HashRecognize.cpp File Reference

#include "llvm/Analysis/HashRecognize.h"
#include "llvm/ADT/APInt.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/KnownBits.h"

Go to the source code of this file.

Classes
class	ValueEvolution
	A much simpler version of ValueTracking, in that it computes KnownBits of values, except that it computes the evolution of KnownBits in a loop with a given trip count, and predication is specialized for a significant-bit check. More...
struct	RecurrenceInfo
	A structure that can hold either a Simple Recurrence or a Conditional Recurrence. More...

Macros
#define	DEBUG_TYPE   "hash-recognize"

Typedefs
using	KnownPhiMap = SmallDenseMap< const PHINode *, KnownBits, 2 >
using	PhiStepPair = std::pair< const PHINode *, const Instruction * >

Functions
static std::optional< std::pair< RecurrenceInfo, RecurrenceInfo > >	getRecurrences (BasicBlock *LoopLatch, const PHINode *IndVar, const Loop &L)
	Iterates over all the phis in LoopLatch, and attempts to extract a Conditional Recurrence and an optional Simple Recurrence.
static bool	checkExtractBits (const KnownBits &Known, unsigned N, function_ref< bool(const KnownBits &)> CheckFn, bool ByteOrderSwapped)
	In the big-endian case, checks the bottom N bits against CheckFn, and that the rest are unknown.
static bool	isConditionalOnXorOfPHIs (const SelectInst *SI, const PHINode *P1, const PHINode *P2, const Loop &L)
	Checks that P1 and P2 are used together in an XOR in the use-def chain of SI's condition, ignoring any casts.
static std::optional< bool >	isBigEndianBitShift (Value *V, ScalarEvolution &SE)

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "hash-recognize"

Definition at line 74 of file HashRecognize.cpp.

Typedef Documentation

KnownPhiMap

using KnownPhiMap = SmallDenseMap<const PHINode *, KnownBits, 2>

Definition at line 79 of file HashRecognize.cpp.

PhiStepPair

using PhiStepPair = std::pair<const PHINode *, const Instruction *>

Definition at line 82 of file HashRecognize.cpp.

Function Documentation

checkExtractBits()

static bool checkExtractBits ( const KnownBits &  Known, unsigned  N, function_ref< bool(const KnownBits &)>  CheckFn, bool  ByteOrderSwapped  )

static

In the big-endian case, checks the bottom N bits against CheckFn, and that the rest are unknown.

In the little-endian case, checks the top N bits against CheckFn, and that the rest are unknown. Callers usually call this function with N = TripCount, and CheckFn checking that the remainder bits of the CRC polynomial division are zero.

Definition at line 467 of file HashRecognize.cpp.

References llvm::KnownBits::extractBits(), llvm::KnownBits::getBitWidth(), llvm::KnownBits::isUnknown(), and N.

Referenced by llvm::HashRecognize::recognizeCRC().

getRecurrences()

static std::optional< std::pair< RecurrenceInfo, RecurrenceInfo > > getRecurrences ( BasicBlock *  LoopLatch, const PHINode *  IndVar, const Loop &  L  )

static

Iterates over all the phis in LoopLatch, and attempts to extract a Conditional Recurrence and an optional Simple Recurrence.

Definition at line 434 of file HashRecognize.cpp.

References RecurrenceInfo::matchConditionalRecurrence(), RecurrenceInfo::matchSimpleRecurrence(), P, and llvm::BasicBlock::phis().

Referenced by llvm::HashRecognize::recognizeCRC().

isBigEndianBitShift()

static std::optional< bool > isBigEndianBitShift ( Value *  V, ScalarEvolution &  SE  )

static

Definition at line 560 of file HashRecognize.cpp.

References llvm::ScalarEvolution::getSCEV(), llvm::SCEVPatternMatch::m_SCEV(), llvm::SCEVPatternMatch::m_scev_Mul(), llvm::SCEVPatternMatch::m_scev_SpecificInt(), llvm::SCEVPatternMatch::m_scev_UDiv(), and llvm::PatternMatch::match().

Referenced by llvm::HashRecognize::recognizeCRC().

isConditionalOnXorOfPHIs()

static bool isConditionalOnXorOfPHIs ( const SelectInst *  SI, const PHINode *  P1, const PHINode *  P2, const Loop &  L  )

static

Checks that P1 and P2 are used together in an XOR in the use-def chain of SI's condition, ignoring any casts.

The purpose of this function is to ensure that LHSAux from the SimpleRecurrence is used correctly in the CRC computation. We cannot check the correctness of casts at this point, and rely on the KnownBits propagation to check correctness of the CRC computation.

In other words, it checks for the following pattern:

loop: P1 = phi [_, entry], [P1.next, loop] P2 = phi [_, entry], [P2.next, loop] ... xor = xor (CastOrSelf P1), (CastOrSelf P2)

where xor is in the use-def chain of SI's condition.

Definition at line 527 of file HashRecognize.cpp.

References llvm::SmallVectorBase< Size_T >::empty(), I, llvm::PatternMatch::m_c_Xor(), llvm::PatternMatch::m_CastOrSelf(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::match(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::HashRecognize::recognizeCRC().