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
struct	RecurrenceInfo
	A structure that can hold either a Simple Recurrence or a Conditional Recurrence. More...

Macros
#define	DEBUG_TYPE   "hash-recognize"

Functions
static bool	containsUnreachable (const Loop &L, ArrayRef< const Instruction * > Roots)
	Checks if there's a stray instruction in the loop L outside of the use-def chains from Roots, or if we escape the loop during the use-def walk.
static bool	isSignificantBitCheckWellFormed (const RecurrenceInfo &ConditionalRecurrence, const RecurrenceInfo &SimpleRecurrence, bool ByteOrderSwapped)
	Check the well-formedness of the (most|least) significant bit check given ConditionalRecurrence, SimpleRecurrence, depending on ByteOrderSwapped.
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	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.

Function Documentation

containsUnreachable()

bool containsUnreachable ( const Loop & L, ArrayRef< const Instruction * > Roots )

static

Checks if there's a stray instruction in the loop L outside of the use-def chains from Roots, or if we escape the loop during the use-def walk.

Definition at line 79 of file HashRecognize.cpp.

References llvm::BasicBlock::begin(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::BasicBlock::end(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallPtrSetImplBase::size().

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

getRecurrences()

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 322 of file HashRecognize.cpp.

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

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

isBigEndianBitShift()

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

static

Definition at line 426 of file HashRecognize.cpp.

References E(), 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()

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.

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 393 of file HashRecognize.cpp.

References llvm::cast(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), I, llvm::isa(), llvm::PatternMatch::m_c_Xor(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_ZExtOrTruncOrSelf(), llvm::PatternMatch::match(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

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

isSignificantBitCheckWellFormed()

bool isSignificantBitCheckWellFormed ( const RecurrenceInfo & ConditionalRecurrence, const RecurrenceInfo & SimpleRecurrence, bool ByteOrderSwapped )

static

Check the well-formedness of the (most|least) significant bit check given ConditionalRecurrence, SimpleRecurrence, depending on ByteOrderSwapped.

We check that ConditionalRecurrence.Step is a Select(Cmp()) where the compare is >= 0 in the big-endian case, and == 0 in the little-endian case (or the inverse, in which case the branches of the compare are swapped). We check that the LHS is (ConditionalRecurrence.Phi [xor SimpleRecurrence.Phi]) in the big-endian case, and additionally check for an AND with one in the little-endian case. We then check AllowedByR against CheckAllowedByR, which is [0, smin) in the big-endian case, and is [0, 1) in the little-endian case. CheckAllowedByR checks for significant-bit-clear, and we match the corresponding arms of the select against bit-shift and bit-shift-and-xor-gen-poly.

Definition at line 165 of file HashRecognize.cpp.

References RecurrenceInfo::BO, llvm::cast(), RecurrenceInfo::ExtraConst, llvm::ConstantRange::fromKnownBits(), llvm::KnownBits::getBitWidth(), llvm::APInt::getSignedMinValue(), llvm::APInt::getZero(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_c_Xor(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_One(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_SpecificInt(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExtOrTruncOrSelf(), llvm::ConstantRange::makeAllowedICmpRegion(), llvm::KnownBits::makeConstant(), llvm::SCEVPatternMatch::match(), RecurrenceInfo::Phi, and RecurrenceInfo::Step.

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