LLVM: lib/Analysis/HashRecognize.cpp Source File

LLVM 22.0.0git
HashRecognize.cpp
Go to the documentation of this file.
1//===- HashRecognize.cpp ----------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// The HashRecognize analysis recognizes unoptimized polynomial hash functions
10// with operations over a Galois field of characteristic 2, also called binary
11// fields, or GF(2^n). 2^n is termed the order of the Galois field. This class
12// of hash functions can be optimized using a lookup-table-driven
13// implementation, or with target-specific instructions.
14//
15// Examples:
16//
17// 1. Cyclic redundancy check (CRC), which is a polynomial division in GF(2).
18// 2. Rabin fingerprint, a component of the Rabin-Karp algorithm, which is a
19// rolling hash polynomial division in GF(2).
20// 3. Rijndael MixColumns, a step in AES computation, which is a polynomial
21// multiplication in GF(2^3).
22// 4. GHASH, the authentication mechanism in AES Galois/Counter Mode (GCM),
23// which is a polynomial evaluation in GF(2^128).
24//
25// All of them use an irreducible generating polynomial of degree m,
26//
27// c_m * x^m + c_(m-1) * x^(m-1) + ... + c_0 * x^0
28//
29// where each coefficient c is can take values 0 or 1. The polynomial is simply
30// represented by m+1 bits, corresponding to the coefficients. The different
31// variants of CRC are named by degree of generating polynomial used: so CRC-32
32// would use a polynomial of degree 32.
33//
34// The reason algorithms on GF(2^n) can be optimized with a lookup-table is the
35// following: in such fields, polynomial addition and subtraction are identical
36// and equivalent to XOR, polynomial multiplication is an AND, and polynomial
37// division is identity: the XOR and AND operations in unoptimized
38// implementations are performed bit-wise, and can be optimized to be performed
39// chunk-wise, by interleaving copies of the generating polynomial, and storing
40// the pre-computed values in a table.
41//
42// A generating polynomial of m bits always has the MSB set, so we usually
43// omit it. An example of a 16-bit polynomial is the CRC-16-CCITT polynomial:
44//
45// (x^16) + x^12 + x^5 + 1 = (1) 0001 0000 0010 0001 =わ 0x1021
46//
47// Transmissions are either in big-endian or little-endian form, and hash
48// algorithms are written according to this. For example, IEEE 802 and RS-232
49// specify little-endian transmission.
50//
51//===----------------------------------------------------------------------===//
52//
53// At the moment, we only recognize the CRC algorithm.
54// Documentation on CRC32 from the kernel:
55// https://www.kernel.org/doc/Documentation/crc32.txt
56//
57//
58//===----------------------------------------------------------------------===//
59
60#include "llvm/Analysis/HashRecognize.h"
61#include "llvm/ADT/APInt.h"
62#include "llvm/Analysis/LoopAnalysisManager.h"
63#include "llvm/Analysis/LoopInfo.h"
64#include "llvm/Analysis/ScalarEvolution.h"
65#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
66#include "llvm/Analysis/ValueTracking.h"
67#include "llvm/IR/PatternMatch.h"
68#include "llvm/Support/KnownBits.h"
69
70using namespace llvm;
71using namespace PatternMatch;
72using namespace SCEVPatternMatch;
73
74 #define DEBUG_TYPE "hash-recognize"
75
76/// Checks if there's a stray instruction in the loop \p L outside of the
77/// use-def chains from \p Roots, or if we escape the loop during the use-def
78/// walk.
79 static bool containsUnreachable(const Loop &L,
82 BasicBlock *Latch = L.getLoopLatch();
83
85 while (!Worklist.empty()) {
86 const Instruction *I = Worklist.pop_back_val();
87 Visited.insert(I);
88
89 if (isa<PHINode>(I))
90 continue;
91
92 for (const Use &U : I->operands()) {
93 if (auto *UI = dyn_cast<Instruction>(U)) {
94 if (!L.contains(UI))
95 return true;
96 Worklist.push_back(UI);
97 }
98 }
99 }
100 return Latch->size() != Visited.size();
101}
102
103/// A structure that can hold either a Simple Recurrence or a Conditional
104/// Recurrence. Note that in the case of a Simple Recurrence, Step is an operand
105/// of the BO, while in a Conditional Recurrence, it is a SelectInst.
107 const Loop &L;
108 const PHINode *Phi = nullptr;
109 BinaryOperator *BO = nullptr;
110 Value *Start = nullptr;
111 Value *Step = nullptr;
112 std::optional<APInt> ExtraConst;
113
114 RecurrenceInfo(const Loop &L) : L(L) {}
115 operator bool() const { return BO; }
116
117 void print(raw_ostream &OS, unsigned Indent = 0) const {
118 OS.indent(Indent) << "Phi: ";
119 Phi->print(OS);
120 OS << "\n";
121 OS.indent(Indent) << "BinaryOperator: ";
122 BO->print(OS);
123 OS << "\n";
124 OS.indent(Indent) << "Start: ";
125 Start->print(OS);
126 OS << "\n";
127 OS.indent(Indent) << "Step: ";
128 Step->print(OS);
129 OS << "\n";
130 if (ExtraConst) {
131 OS.indent(Indent) << "ExtraConst: ";
132 ExtraConst->print(OS, false);
133 OS << "\n";
134 }
135 }
136
137#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
138 LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
139#endif
140
141 bool matchSimpleRecurrence(const PHINode *P);
143 const PHINode *P,
144 Instruction::BinaryOps BOWithConstOpToMatch = Instruction::BinaryOpsEnd);
145
146private:
147 BinaryOperator *digRecurrence(
148 Instruction *V,
149 Instruction::BinaryOps BOWithConstOpToMatch = Instruction::BinaryOpsEnd);
150};
151
152/// Check the well-formedness of the (most|least) significant bit check given \p
153/// ConditionalRecurrence, \p SimpleRecurrence, depending on \p
154/// ByteOrderSwapped. We check that ConditionalRecurrence.Step is a
155/// Select(Cmp()) where the compare is `>= 0` in the big-endian case, and `== 0`
156/// in the little-endian case (or the inverse, in which case the branches of the
157/// compare are swapped). We check that the LHS is (ConditionalRecurrence.Phi
158/// [xor SimpleRecurrence.Phi]) in the big-endian case, and additionally check
159/// for an AND with one in the little-endian case. We then check AllowedByR
160/// against CheckAllowedByR, which is [0, smin) in the big-endian case, and is
161/// [0, 1) in the little-endian case. CheckAllowedByR checks for
162/// significant-bit-clear, and we match the corresponding arms of the select
163/// against bit-shift and bit-shift-and-xor-gen-poly.
164static bool
166 const RecurrenceInfo &SimpleRecurrence,
167 bool ByteOrderSwapped) {
168 auto *SI = cast<SelectInst>(ConditionalRecurrence.Step);
169 CmpPredicate Pred;
170 const Value *L;
171 const APInt *R;
172 Instruction *TV, *FV;
173 if (!match(SI, m_Select(m_ICmp(Pred, m_Value(L), m_APInt(R)),
174 m_Instruction(TV), m_Instruction(FV))))
175 return false;
176
177 // Match predicate with or without a SimpleRecurrence (the corresponding data
178 // is LHSAux).
179 auto MatchPred = m_CombineOr(
180 m_Specific(ConditionalRecurrence.Phi),
181 m_c_Xor(m_ZExtOrTruncOrSelf(m_Specific(ConditionalRecurrence.Phi)),
182 m_ZExtOrTruncOrSelf(m_Specific(SimpleRecurrence.Phi))));
183 bool LWellFormed = ByteOrderSwapped ? match(L, MatchPred)
184 : match(L, m_c_And(MatchPred, m_One()));
185 if (!LWellFormed)
186 return false;
187
189 unsigned BW = KnownR.getBitWidth();
190 auto RCR = ConstantRange::fromKnownBits(KnownR, false);
191 auto AllowedByR = ConstantRange::makeAllowedICmpRegion(Pred, RCR);
192 ConstantRange CheckAllowedByR(APInt::getZero(BW),
193 ByteOrderSwapped ? APInt::getSignedMinValue(BW)
194 : APInt(BW, 1));
195
196 BinaryOperator *BitShift = ConditionalRecurrence.BO;
197 if (AllowedByR == CheckAllowedByR)
198 return TV == BitShift &&
199 match(FV, m_c_Xor(m_Specific(BitShift),
200 m_SpecificInt(*ConditionalRecurrence.ExtraConst)));
201 if (AllowedByR.inverse() == CheckAllowedByR)
202 return FV == BitShift &&
203 match(TV, m_c_Xor(m_Specific(BitShift),
204 m_SpecificInt(*ConditionalRecurrence.ExtraConst)));
205 return false;
206}
207
208/// Wraps llvm::matchSimpleRecurrence. Match a simple first order recurrence
209/// cycle of the form:
210///
211/// loop:
212/// %rec = phi [%start, %entry], [%BO, %loop]
213/// ...
214/// %BO = binop %rec, %step
215///
216/// or
217///
218/// loop:
219/// %rec = phi [%start, %entry], [%BO, %loop]
220/// ...
221/// %BO = binop %step, %rec
222///
225 Phi = P;
226 return true;
227 }
228 return false;
229}
230
231/// Digs for a recurrence starting with \p V hitting the PHI node in a use-def
232/// chain. Used by matchConditionalRecurrence.
233BinaryOperator *
234RecurrenceInfo::digRecurrence(Instruction *V,
235 Instruction::BinaryOps BOWithConstOpToMatch) {
236 SmallVector<Instruction *> Worklist;
237 Worklist.push_back(V);
238 while (!Worklist.empty()) {
239 Instruction *I = Worklist.pop_back_val();
240
241 // Don't add a PHI's operands to the Worklist.
242 if (isa<PHINode>(I))
243 continue;
244
245 // Find a recurrence over a BinOp, by matching either of its operands
246 // with with the PHINode.
247 if (match(I, m_c_BinOp(m_Value(), m_Specific(Phi))))
248 return cast<BinaryOperator>(I);
249
250 // Bind to ExtraConst, if we match exactly one.
251 if (I->getOpcode() == BOWithConstOpToMatch) {
252 if (ExtraConst)
253 return nullptr;
254 const APInt *C = nullptr;
255 if (match(I, m_c_BinOp(m_APInt(C), m_Value())))
256 ExtraConst = *C;
257 }
258
259 // Continue along the use-def chain.
260 for (Use &U : I->operands())
261 if (auto *UI = dyn_cast<Instruction>(U))
262 if (L.contains(UI))
263 Worklist.push_back(UI);
264 }
265 return nullptr;
266}
267
268/// A Conditional Recurrence is a recurrence of the form:
269///
270/// loop:
271/// %rec = phi [%start, %entry], [%step, %loop]
272/// ...
273/// %step = select _, %tv, %fv
274///
275/// where %tv and %fv ultimately end up using %rec via the same %BO instruction,
276/// after digging through the use-def chain.
277///
278/// ExtraConst is relevant if \p BOWithConstOpToMatch is supplied: when digging
279/// the use-def chain, a BinOp with opcode \p BOWithConstOpToMatch is matched,
280/// and ExtraConst is a constant operand of that BinOp. This peculiarity exists,
281/// because in a CRC algorithm, the \p BOWithConstOpToMatch is an XOR, and the
282/// ExtraConst ends up being the generating polynomial.
284 const PHINode *P, Instruction::BinaryOps BOWithConstOpToMatch) {
285 Phi = P;
286 if (Phi->getNumIncomingValues() != 2)
287 return false;
288
289 for (unsigned Idx = 0; Idx != 2; ++Idx) {
290 Value *FoundStep = Phi->getIncomingValue(Idx);
291 Value *FoundStart = Phi->getIncomingValue(!Idx);
292
293 Instruction *TV, *FV;
294 if (!match(FoundStep,
296 continue;
297
298 // For a conditional recurrence, both the true and false values of the
299 // select must ultimately end up in the same recurrent BinOp.
300 BinaryOperator *FoundBO = digRecurrence(TV, BOWithConstOpToMatch);
301 BinaryOperator *AltBO = digRecurrence(FV, BOWithConstOpToMatch);
302 if (!FoundBO || FoundBO != AltBO)
303 return false;
304
305 if (BOWithConstOpToMatch != Instruction::BinaryOpsEnd && !ExtraConst) {
306 LLVM_DEBUG(dbgs() << "HashRecognize: Unable to match single BinaryOp "
307 "with constant in conditional recurrence\n");
308 return false;
309 }
310
311 BO = FoundBO;
312 Start = FoundStart;
313 Step = FoundStep;
314 return true;
315 }
316 return false;
317}
318
319/// Iterates over all the phis in \p LoopLatch, and attempts to extract a
320/// Conditional Recurrence and an optional Simple Recurrence.
321static std::optional<std::pair<RecurrenceInfo, RecurrenceInfo>>
322 getRecurrences(BasicBlock *LoopLatch, const PHINode *IndVar, const Loop &L) {
323 auto Phis = LoopLatch->phis();
324 unsigned NumPhis = std::distance(Phis.begin(), Phis.end());
325 if (NumPhis != 2 && NumPhis != 3)
326 return {};
327
328 RecurrenceInfo SimpleRecurrence(L);
329 RecurrenceInfo ConditionalRecurrence(L);
330 for (PHINode &P : Phis) {
331 if (&P == IndVar)
332 continue;
333 if (!SimpleRecurrence)
334 SimpleRecurrence.matchSimpleRecurrence(&P);
335 if (!ConditionalRecurrence)
336 ConditionalRecurrence.matchConditionalRecurrence(
337 &P, Instruction::BinaryOps::Xor);
338 }
339 if (NumPhis == 3 && (!SimpleRecurrence || !ConditionalRecurrence))
340 return {};
341 return std::make_pair(SimpleRecurrence, ConditionalRecurrence);
342}
343
349
350/// Generate a lookup table of 256 entries by interleaving the generating
351/// polynomial. The optimization technique of table-lookup for CRC is also
352/// called the Sarwate algorithm.
354 bool ByteOrderSwapped) {
355 unsigned BW = GenPoly.getBitWidth();
356 CRCTable Table;
357 Table[0] = APInt::getZero(BW);
358
359 if (ByteOrderSwapped) {
360 APInt CRCInit = APInt::getSignedMinValue(BW);
361 for (unsigned I = 1; I < 256; I <<= 1) {
362 CRCInit = CRCInit.shl(1) ^
363 (CRCInit.isSignBitSet() ? GenPoly : APInt::getZero(BW));
364 for (unsigned J = 0; J < I; ++J)
365 Table[I + J] = CRCInit ^ Table[J];
366 }
367 return Table;
368 }
369
370 APInt CRCInit(BW, 1);
371 for (unsigned I = 128; I; I >>= 1) {
372 CRCInit = CRCInit.lshr(1) ^ (CRCInit[0] ? GenPoly : APInt::getZero(BW));
373 for (unsigned J = 0; J < 256; J += (I << 1))
374 Table[I + J] = CRCInit ^ Table[J];
375 }
376 return Table;
377}
378
379/// Checks that \p P1 and \p P2 are used together in an XOR in the use-def chain
380/// of \p SI's condition, ignoring any casts. The purpose of this function is to
381/// ensure that LHSAux from the SimpleRecurrence is used correctly in the CRC
382/// computation.
383///
384/// In other words, it checks for the following pattern:
385///
386/// loop:
387/// %P1 = phi [_, %entry], [%P1.next, %loop]
388/// %P2 = phi [_, %entry], [%P2.next, %loop]
389/// ...
390/// %xor = xor (CastOrSelf %P1), (CastOrSelf %P2)
391///
392/// where %xor is in the use-def chain of \p SI's condition.
393 static bool isConditionalOnXorOfPHIs(const SelectInst *SI, const PHINode *P1,
394 const PHINode *P2, const Loop &L) {
396
397 // matchConditionalRecurrence has already ensured that the SelectInst's
398 // condition is an Instruction.
399 Worklist.push_back(cast<Instruction>(SI->getCondition()));
400
401 while (!Worklist.empty()) {
402 const Instruction *I = Worklist.pop_back_val();
403
404 // Don't add a PHI's operands to the Worklist.
405 if (isa<PHINode>(I))
406 continue;
407
408 // If we match an XOR of the two PHIs ignoring casts, we're done.
411 return true;
412
413 // Continue along the use-def chain.
414 for (const Use &U : I->operands())
415 if (auto *UI = dyn_cast<Instruction>(U))
416 if (L.contains(UI))
417 Worklist.push_back(UI);
418 }
419 return false;
420}
421
422// Recognizes a multiplication or division by the constant two, using SCEV. By
423// doing this, we're immune to whether the IR expression is mul/udiv or
424// equivalently shl/lshr. Return false when it is a UDiv, true when it is a Mul,
425// and std::nullopt otherwise.
426 static std::optional<bool> isBigEndianBitShift(Value *V, ScalarEvolution &SE) {
427 if (!V->getType()->isIntegerTy())
428 return {};
429
430 const SCEV *E = SE.getSCEV(V);
432 return false;
434 return true;
435 return {};
436}
437
438/// The main entry point for analyzing a loop and recognizing the CRC algorithm.
439/// Returns a PolynomialInfo on success, and a StringRef on failure.
440 std::variant<PolynomialInfo, StringRef> HashRecognize::recognizeCRC() const {
441 if (!L.isInnermost())
442 return "Loop is not innermost";
443 BasicBlock *Latch = L.getLoopLatch();
444 BasicBlock *Exit = L.getExitBlock();
445 const PHINode *IndVar = L.getCanonicalInductionVariable();
446 if (!Latch || !Exit || !IndVar || L.getNumBlocks() != 1)
447 return "Loop not in canonical form";
448 unsigned TC = SE.getSmallConstantTripCount(&L);
449 if (!TC || TC % 8)
450 return "Unable to find a small constant byte-multiple trip count";
451
452 auto R = getRecurrences(Latch, IndVar, L);
453 if (!R)
454 return "Found stray PHI";
455 auto [SimpleRecurrence, ConditionalRecurrence] = *R;
456 if (!ConditionalRecurrence)
457 return "Unable to find conditional recurrence";
458
459 // Make sure that all recurrences are either all SCEVMul with two or SCEVDiv
460 // with two, or in other words, that they're single bit-shifts.
461 std::optional<bool> ByteOrderSwapped =
462 isBigEndianBitShift(ConditionalRecurrence.BO, SE);
463 if (!ByteOrderSwapped)
464 return "Loop with non-unit bitshifts";
465 if (SimpleRecurrence) {
466 if (isBigEndianBitShift(SimpleRecurrence.BO, SE) != ByteOrderSwapped)
467 return "Loop with non-unit bitshifts";
468
469 // Ensure that the PHIs have exactly two uses:
470 // the bit-shift, and the XOR (or a cast feeding into the XOR).
471 // Also ensure that the SimpleRecurrence's evolution doesn't have stray
472 // users.
473 if (!ConditionalRecurrence.Phi->hasNUses(2) ||
474 !SimpleRecurrence.Phi->hasNUses(2) ||
475 SimpleRecurrence.BO->getUniqueUndroppableUser() != SimpleRecurrence.Phi)
476 return "Recurrences have stray uses";
477
478 // Check that the SelectInst ConditionalRecurrence.Step is conditional on
479 // the XOR of SimpleRecurrence.Phi and ConditionalRecurrence.Phi.
480 if (!isConditionalOnXorOfPHIs(cast<SelectInst>(ConditionalRecurrence.Step),
481 SimpleRecurrence.Phi,
482 ConditionalRecurrence.Phi, L))
483 return "Recurrences not intertwined with XOR";
484 }
485
486 // Make sure that the TC doesn't exceed the bitwidth of LHSAux, or LHS.
487 Value *LHS = ConditionalRecurrence.Start;
488 Value *LHSAux = SimpleRecurrence ? SimpleRecurrence.Start : nullptr;
489 if (TC > (LHSAux ? LHSAux->getType()->getIntegerBitWidth()
490 : LHS->getType()->getIntegerBitWidth()))
491 return "Loop iterations exceed bitwidth of data";
492
493 // Make sure that the computed value is used in the exit block: this should be
494 // true even if it is only really used in an outer loop's exit block, since
495 // the loop is in LCSSA form.
496 auto *ComputedValue = cast<SelectInst>(ConditionalRecurrence.Step);
497 if (none_of(ComputedValue->users(), [Exit](User *U) {
498 auto *UI = dyn_cast<Instruction>(U);
499 return UI && UI->getParent() == Exit;
500 }))
501 return "Unable to find use of computed value in loop exit block";
502
503 assert(ConditionalRecurrence.ExtraConst &&
504 "Expected ExtraConst in conditional recurrence");
505 const APInt &GenPoly = *ConditionalRecurrence.ExtraConst;
506
507 if (!isSignificantBitCheckWellFormed(ConditionalRecurrence, SimpleRecurrence,
508 *ByteOrderSwapped))
509 return "Malformed significant-bit check";
510
512 {ComputedValue,
514 L.getLatchCmpInst(), Latch->getTerminator()});
515 if (SimpleRecurrence)
516 Roots.push_back(SimpleRecurrence.BO);
517 if (containsUnreachable(L, Roots))
518 return "Found stray unvisited instructions";
519
520 return PolynomialInfo(TC, LHS, GenPoly, ComputedValue, *ByteOrderSwapped,
521 LHSAux);
522}
523
524 void CRCTable::print(raw_ostream &OS) const {
525 for (unsigned I = 0; I < 256; I++) {
526 (*this)[I].print(OS, false);
527 OS << (I % 16 == 15 ? '\n' : ' ');
528 }
529}
530
531#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
532 void CRCTable::dump() const { print(dbgs()); }
533#endif
534
536 if (!L.isInnermost())
537 return;
538 OS << "HashRecognize: Checking a loop in '"
539 << L.getHeader()->getParent()->getName() << "' from " << L.getLocStr()
540 << "\n";
541 auto Ret = recognizeCRC();
542 if (!std::holds_alternative<PolynomialInfo>(Ret)) {
543 OS << "Did not find a hash algorithm\n";
544 if (std::holds_alternative<StringRef>(Ret))
545 OS << "Reason: " << std::get<StringRef>(Ret) << "\n";
546 return;
547 }
548
549 auto Info = std::get<PolynomialInfo>(Ret);
550 OS << "Found" << (Info.ByteOrderSwapped ? " big-endian " : " little-endian ")
551 << "CRC-" << Info.RHS.getBitWidth() << " loop with trip count "
552 << Info.TripCount << "\n";
553 OS.indent(2) << "Initial CRC: ";
554 Info.LHS->print(OS);
555 OS << "\n";
556 OS.indent(2) << "Generating polynomial: ";
557 Info.RHS.print(OS, false);
558 OS << "\n";
559 OS.indent(2) << "Computed CRC: ";
560 Info.ComputedValue->print(OS);
561 OS << "\n";
562 if (Info.LHSAux) {
563 OS.indent(2) << "Auxiliary data: ";
564 Info.LHSAux->print(OS);
565 OS << "\n";
566 }
567 OS.indent(2) << "Computed CRC lookup table:\n";
568 genSarwateTable(Info.RHS, Info.ByteOrderSwapped).print(OS);
569}
570
571#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
572 void HashRecognize::dump() const { print(dbgs()); }
573#endif
574
575 std::optional<PolynomialInfo> HashRecognize::getResult() const {
576 auto Res = HashRecognize(L, SE).recognizeCRC();
577 if (std::holds_alternative<PolynomialInfo>(Res))
578 return std::get<PolynomialInfo>(Res);
579 return std::nullopt;
580}
581
583 : L(L), SE(SE) {}
584
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:638
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,...
static bool isSignificantBitCheckWellFormed(const RecurrenceInfo &ConditionalRecurrence, const RecurrenceInfo &SimpleRecurrence, bool ByteOrderSwapped)
Check the well-formedness of the (most|least) significant bit check given ConditionalRecurrence,...
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)
This header provides classes for managing per-loop analyses.
I
#define I(x, y, z)
Definition MD5.cpp:58
P
#define P(N)
#define LLVM_DEBUG(...)
Definition Debug.h:114
Class for arbitrary precision integers.
Definition APInt.h:78
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition APInt.h:1489
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition APInt.h:220
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition APInt.h:874
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
Definition APInt.h:342
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition APInt.h:201
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition APInt.h:852
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:41
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition BasicBlock.h:528
size_t size() const
Definition BasicBlock.h:480
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...
Definition BasicBlock.h:233
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Definition CmpPredicate.h:23
This class represents a range of values.
Definition ConstantRange.h:47
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...
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &)
The analysis.
Definition HashRecognize.h:74
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, 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...
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
Value * getIncomingValueForBlock(const BasicBlock *BB) const
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
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.
This class represents the LLVM 'select' instruction.
size_type size() const
Definition SmallPtrSet.h:99
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition SmallPtrSet.h:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition SmallPtrSet.h:527
void push_back(const T &Elt)
Definition SmallVector.h:417
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition SmallVector.h:1203
LLVM_ABI unsigned getIntegerBitWidth() const
Definition DerivedTypes.h:99
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
Definition User.h:44
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:256
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
@ C
The default llvm calling convention, compatible with C.
Definition CallingConv.h:34
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition PatternMatch.h:311
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
bool match(Val *V, const Pattern &P)
Definition PatternMatch.h:49
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition PatternMatch.h:874
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition PatternMatch.h:974
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition PatternMatch.h:604
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.
Definition PatternMatch.h:118
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition PatternMatch.h:105
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)
match_combine_or< match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, TruncInst > >, OpTy > m_ZExtOrTruncOrSelf(const OpTy &Op)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition PatternMatch.h:272
bind_ty< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
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.
Definition AddressRanges.h:18
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
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.
Definition Debug.cpp:207
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1739
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
A structure that can hold either a Simple Recurrence or a Conditional Recurrence.
const Loop & L
const PHINode * Phi
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.
BinaryOperator * BO
RecurrenceInfo(const Loop &L)
A custom std::array with 256 entries, that also has a print function.
Definition HashRecognize.h:30
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.
Definition KnownBits.h:301
unsigned getBitWidth() const
Get the bit width of this value.
Definition KnownBits.h:44
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.
Definition HashRecognize.h:40
PolynomialInfo(unsigned TripCount, Value *LHS, const APInt &RHS, Value *ComputedValue, bool ByteOrderSwapped, Value *LHSAux=nullptr)
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /