71using namespace PatternMatch;
72using namespace SCEVPatternMatch;
74#define DEBUG_TYPE "hash-recognize"
82using PhiStepPair = std::pair<const PHINode *, const Instruction *>;
89 const unsigned TripCount;
90 const bool ByteOrderSwapped;
128 : TripCount(TripCount), ByteOrderSwapped(ByteOrderSwapped) {}
134 switch (
I->getOpcode()) {
135 case Instruction::BinaryOps::And:
136 return KnownL & KnownR;
137 case Instruction::BinaryOps::Or:
138 return KnownL | KnownR;
139 case Instruction::BinaryOps::Xor:
140 return KnownL ^ KnownR;
141 case Instruction::BinaryOps::Shl: {
142 auto *OBO = cast<OverflowingBinaryOperator>(
I);
144 OBO->hasNoSignedWrap());
146 case Instruction::BinaryOps::LShr:
148 case Instruction::BinaryOps::AShr:
150 case Instruction::BinaryOps::Add: {
151 auto *OBO = cast<OverflowingBinaryOperator>(
I);
153 OBO->hasNoSignedWrap());
155 case Instruction::BinaryOps::Sub: {
156 auto *OBO = cast<OverflowingBinaryOperator>(
I);
158 OBO->hasNoSignedWrap());
160 case Instruction::BinaryOps::Mul: {
161 Value *Op0 =
I->getOperand(0);
162 Value *Op1 =
I->getOperand(1);
166 case Instruction::BinaryOps::UDiv:
168 case Instruction::BinaryOps::SDiv:
170 case Instruction::BinaryOps::URem:
172 case Instruction::BinaryOps::SRem:
175 ErrStr =
"Unknown BinaryOperator";
176 unsigned BitWidth =
I->getType()->getScalarSizeInBits();
182 unsigned BitWidth =
I->getType()->getScalarSizeInBits();
189 if (
const PHINode *
P = dyn_cast<PHINode>(
I))
203 if (!ByteOrderSwapped) {
208 if (LCR != CheckLCR) {
209 ErrStr =
"Bad LHS of significant-bit-check";
225 if (AllowedR == CheckRCR) {
229 if (AllowedR.inverse() == CheckRCR) {
234 ErrStr =
"Bad RHS of significant-bit-check";
238 if (
auto *BO = dyn_cast<BinaryOperator>(
I))
239 return computeBinOp(BO);
241 switch (
I->getOpcode()) {
242 case Instruction::CastOps::Trunc:
244 case Instruction::CastOps::ZExt:
246 case Instruction::CastOps::SExt:
249 ErrStr =
"Unknown Instruction";
255 if (
auto *CI = dyn_cast<ConstantInt>(V))
258 if (
auto *
I = dyn_cast<Instruction>(V))
259 return computeInstr(
I);
261 ErrStr =
"Unknown Value";
262 unsigned BitWidth =
V->getType()->getScalarSizeInBits();
267 for (
unsigned I = 0;
I < TripCount; ++
I)
268 for (
auto [Phi, Step] : PhiEvolutions)
271 return ErrStr.
empty();
292 OS.
indent(Indent) <<
"BinaryOperator: ";
302 OS.
indent(Indent) <<
"ExtraConst: ";
308#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
350 while (!Worklist.
empty()) {
360 return cast<BinaryOperator>(
I);
363 if (
I->getOpcode() == BOWithConstOpToMatch) {
372 for (
Use &U :
I->operands())
373 if (
auto *UI = dyn_cast<Instruction>(U))
401 for (
unsigned Idx = 0;
Idx != 2; ++
Idx) {
406 if (!
match(FoundStep,
412 BinaryOperator *FoundBO = digRecurrence(TV, BOWithConstOpToMatch);
414 if (!FoundBO || FoundBO != AltBO)
417 if (BOWithConstOpToMatch != Instruction::BinaryOpsEnd && !
ExtraConst) {
418 LLVM_DEBUG(
dbgs() <<
"HashRecognize: Unable to match single BinaryOp "
419 "with constant in conditional recurrence\n");
433static std::optional<std::pair<RecurrenceInfo, RecurrenceInfo>>
435 auto Phis = LoopLatch->
phis();
436 unsigned NumPhis = std::distance(Phis.begin(), Phis.end());
437 if (NumPhis != 2 && NumPhis != 3)
445 if (!SimpleRecurrence)
447 if (!ConditionalRecurrence)
449 &
P, Instruction::BinaryOps::Xor);
451 if (NumPhis == 3 && (!SimpleRecurrence || !ConditionalRecurrence))
453 return std::make_pair(SimpleRecurrence, ConditionalRecurrence);
457 Value *ComputedValue,
bool ByteOrderSwapped,
459 : TripCount(TripCount),
LHS(
LHS),
RHS(
RHS), ComputedValue(ComputedValue),
460 ByteOrderSwapped(ByteOrderSwapped), LHSAux(LHSAux) {}
469 bool ByteOrderSwapped) {
476 unsigned BitPos = ByteOrderSwapped ? 0 : Known.
getBitWidth() -
N;
477 unsigned SwappedBitPos = ByteOrderSwapped ?
N : 0;
486 bool ByteOrderSwapped) {
491 if (ByteOrderSwapped) {
493 for (
unsigned I = 1;
I < 256;
I <<= 1) {
494 CRCInit = CRCInit.
shl(1) ^
496 for (
unsigned J = 0; J <
I; ++J)
497 Table[
I + J] = CRCInit ^ Table[J];
502 APInt CRCInit(BW, 1);
503 for (
unsigned I = 128;
I;
I >>= 1) {
505 for (
unsigned J = 0; J < 256; J += (
I << 1))
506 Table[
I + J] = CRCInit ^ Table[J];
533 Worklist.
push_back(cast<Instruction>(SI->getCondition()));
535 while (!Worklist.
empty()) {
548 for (
const Use &U :
I->operands())
549 if (
auto *UI = dyn_cast<Instruction>(U))
561 if (!V->getType()->isIntegerTy())
575std::variant<PolynomialInfo, ErrBits, StringRef>
577 if (!L.isInnermost())
578 return "Loop is not innermost";
581 const PHINode *IndVar = L.getCanonicalInductionVariable();
582 if (!Latch || !Exit || !IndVar || L.getNumBlocks() != 1)
583 return "Loop not in canonical form";
585 if (!TC || TC > 256 || TC % 8)
586 return "Unable to find a small constant byte-multiple trip count";
590 return "Found stray PHI";
591 auto [SimpleRecurrence, ConditionalRecurrence] = *R;
592 if (!ConditionalRecurrence)
593 return "Unable to find conditional recurrence";
597 std::optional<bool> ByteOrderSwapped =
599 if (!ByteOrderSwapped)
600 return "Loop with non-unit bitshifts";
601 if (SimpleRecurrence) {
603 return "Loop with non-unit bitshifts";
607 if (!ConditionalRecurrence.Phi->hasNUses(2) ||
608 !SimpleRecurrence.Phi->hasNUses(2))
609 return "Recurrences have stray uses";
614 SimpleRecurrence.Phi,
615 ConditionalRecurrence.Phi, L))
616 return "Recurrences not intertwined with XOR";
620 Value *
LHS = ConditionalRecurrence.Start;
621 Value *LHSAux = SimpleRecurrence ? SimpleRecurrence.Start :
nullptr;
624 return "Loop iterations exceed bitwidth of data";
629 auto *ComputedValue = cast<SelectInst>(ConditionalRecurrence.Step);
630 if (
none_of(ComputedValue->users(), [Exit](
User *U) {
631 auto *UI = dyn_cast<Instruction>(U);
632 return UI && UI->getParent() == Exit;
634 return "Unable to find use of computed value in loop exit block";
636 assert(ConditionalRecurrence.ExtraConst &&
637 "Expected ExtraConst in conditional recurrence");
638 const APInt &GenPoly = *ConditionalRecurrence.ExtraConst;
645 PhiEvolutions.
emplace_back(ConditionalRecurrence.Phi, ComputedValue);
646 if (SimpleRecurrence)
647 PhiEvolutions.
emplace_back(SimpleRecurrence.Phi, SimpleRecurrence.BO);
658 std::initializer_list<const Instruction *> AugmentVisited = {
663 return "Found stray unvisited instructions";
666 auto IsZero = [](
const KnownBits &K) {
return K.isZero(); };
668 return ErrBits(ResultBits, TC, *ByteOrderSwapped);
675 for (
unsigned I = 0;
I < 256;
I++) {
676 (*this)[
I].print(
OS,
false);
677 OS << (
I % 16 == 15 ?
'\n' :
' ');
681#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
686 if (!L.isInnermost())
688 OS <<
"HashRecognize: Checking a loop in '"
689 << L.getHeader()->getParent()->getName() <<
"' from " << L.getLocStr()
692 if (!std::holds_alternative<PolynomialInfo>(Ret)) {
693 OS <<
"Did not find a hash algorithm\n";
694 if (std::holds_alternative<StringRef>(Ret))
695 OS <<
"Reason: " << std::get<StringRef>(Ret) <<
"\n";
696 if (std::holds_alternative<ErrBits>(Ret)) {
697 auto [Actual, Iter, ByteOrderSwapped] = std::get<ErrBits>(Ret);
698 OS <<
"Reason: Expected " << (ByteOrderSwapped ?
"bottom " :
"top ")
699 << Iter <<
" bits zero (";
706 auto Info = std::get<PolynomialInfo>(Ret);
707 OS <<
"Found" << (
Info.ByteOrderSwapped ?
" big-endian " :
" little-endian ")
708 <<
"CRC-" <<
Info.RHS.getBitWidth() <<
" loop with trip count "
709 <<
Info.TripCount <<
"\n";
713 OS.
indent(2) <<
"Generating polynomial: ";
714 Info.RHS.print(
OS,
false);
717 Info.ComputedValue->print(
OS);
724 OS.
indent(2) <<
"Computed CRC lookup table:\n";
728#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
734 if (std::holds_alternative<PolynomialInfo>(Res))
735 return std::get<PolynomialInfo>(Res);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
Analysis containing CSE Info
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
std::pair< const PHINode *, const Instruction * > PhiStepPair
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,...
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 opti...
static std::optional< bool > isBigEndianBitShift(Value *V, ScalarEvolution &SE)
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.
This header provides classes for managing per-loop analyses.
A much simpler version of ValueTracking, in that it computes KnownBits of values, except that it comp...
StringRef getError() const
SmallPtrSet< const Instruction *, 16 > Visited
bool computeEvolutions(ArrayRef< PhiStepPair > PhiEvolutions)
ValueEvolution(unsigned TripCount, bool ByteOrderSwapped)
Class for arbitrary precision integers.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
A container for analyses that lazily runs them and caches their results.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This class represents a range of values.
static LLVM_ABI ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
static LLVM_ABI ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
std::pair< iterator, bool > emplace_or_assign(const KeyT &Key, Ts &&...Args)
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
ValueT lookup_or(const_arg_type_t< KeyT > Val, U &&Default) const
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &)
static CRCTable genSarwateTable(const APInt &GenPoly, bool ByteOrderSwapped)
Generate a lookup table of 256 entries by interleaving the generating polynomial.
std::optional< PolynomialInfo > getResult() const
LLVM_DUMP_METHOD void dump() const
HashRecognize(const Loop &L, ScalarEvolution &SE)
void print(raw_ostream &OS) const
std::variant< PolynomialInfo, ErrBits, StringRef > recognizeCRC() const
The main entry point for analyzing a loop and recognizing the CRC algorithm.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Represents a single loop in the control flow graph.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
This class represents an analyzed expression in the program.
The main scalar evolution driver.
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
This class represents the LLVM 'select' instruction.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
constexpr bool empty() const
empty - Check if the string is empty.
LLVM_ABI unsigned getIntegerBitWidth() const
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
@ C
The default llvm calling convention, compatible with C.
match_combine_or< CastInst_match< OpTy, CastInst >, OpTy > m_CastOrSelf(const OpTy &Op)
Matches any cast or self. Used to ignore casts.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
SCEVBinaryExpr_match< SCEVMulExpr, Op0_t, Op1_t > m_scev_Mul(const Op0_t &Op0, const Op1_t &Op1)
bool match(const SCEV *S, const Pattern &P)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
cst_pred_ty< is_specific_cst > m_scev_SpecificInt(uint64_t V)
Match an SCEV constant with a plain unsigned integer.
class_match< const SCEV > m_SCEV()
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI bool isGuaranteedNotToBeUndef(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be undef, but may be poison.
LLVM_ABI bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step)
Attempt to match a simple first order recurrence cycle of the form: iv = phi Ty [Start,...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
std::tuple< KnownBits, unsigned, bool > ErrBits
A tuple of bits that are expected to be zero, number N of them expected to be zero,...
constexpr unsigned BitWidth
A structure that can hold either a Simple Recurrence or a Conditional Recurrence.
LLVM_DUMP_METHOD void dump() const
bool matchConditionalRecurrence(const PHINode *P, Instruction::BinaryOps BOWithConstOpToMatch=Instruction::BinaryOpsEnd)
A Conditional Recurrence is a recurrence of the form:
void print(raw_ostream &OS, unsigned Indent=0) const
std::optional< APInt > ExtraConst
bool matchSimpleRecurrence(const PHINode *P)
Wraps llvm::matchSimpleRecurrence.
RecurrenceInfo(const Loop &L)
A custom std::array with 256 entries, that also has a print function.
LLVM_DUMP_METHOD void dump() const
void print(raw_ostream &OS) const
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits urem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for urem(LHS, RHS).
bool isUnknown() const
Returns true if we don't know any bits.
KnownBits trunc(unsigned BitWidth) const
Return known bits for a truncation of the value we're tracking.
unsigned getBitWidth() const
Get the bit width of this value.
KnownBits zext(unsigned BitWidth) const
Return known bits for a zero extension of the value we're tracking.
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
KnownBits sext(unsigned BitWidth) const
Return known bits for a sign extension of the value we're tracking.
static KnownBits add(const KnownBits &LHS, const KnownBits &RHS, bool NSW=false, bool NUW=false)
Compute knownbits resulting from addition of LHS and RHS.
static LLVM_ABI KnownBits srem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for srem(LHS, RHS).
static LLVM_ABI KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for udiv(LHS, RHS).
static LLVM_ABI KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for sdiv(LHS, RHS).
static KnownBits sub(const KnownBits &LHS, const KnownBits &RHS, bool NSW=false, bool NUW=false)
Compute knownbits resulting from subtraction of LHS and RHS.
static LLVM_ABI KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
The structure that is returned when a polynomial algorithm was recognized by the analysis.
PolynomialInfo(unsigned TripCount, Value *LHS, const APInt &RHS, Value *ComputedValue, bool ByteOrderSwapped, Value *LHSAux=nullptr)