Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 16419b6

Browse filesBrowse files
artagnonartagnon
committed
[HashRecognize] Address review
1 parent d12d3f7 commit 16419b6
Copy full SHA for 16419b6

File tree

Expand file treeCollapse file tree

3 files changed

+37
-22
lines changed
Filter options
Expand file treeCollapse file tree

3 files changed

+37
-22
lines changed

‎llvm/include/llvm/Analysis/HashRecognize.h

Copy file name to clipboardExpand all lines: llvm/include/llvm/Analysis/HashRecognize.h
+21Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,12 +37,33 @@ struct CRCTable : public std::array<APInt, 256> {
3737
/// The structure that is returned when a polynomial algorithm was recognized by
3838
/// the analysis. Currently, only the CRC algorithm is recognized.
3939
struct PolynomialInfo {
40+
// The small constant trip-count of the analyzed loop.
4041
unsigned TripCount;
42+
43+
// The LHS in a polynomial operation, or the initial variable of the
44+
// computation, since all polynomial operations must have a constant RHS,
45+
// which is the generating polynomial. It is the LHS of the polynomial
46+
// division in the case of CRC. Since polynomial division is an XOR in
47+
// GF(2^m), this variable must be XOR'ed with RHS in a loop to yield the
48+
// ComputedValue.
4149
const Value *LHS;
50+
51+
// The generating polynomial, or the RHS of the polynomial division in the
52+
// case of CRC.
4253
APInt RHS;
54+
55+
// The final computed value. This is a remainder of a polynomial division in
56+
// the case of CRC, which must be zero.
4357
const Value *ComputedValue;
58+
59+
// Set to true in the case of big-endian.
4460
bool ByteOrderSwapped;
61+
62+
// An optional auxiliary checksum that augments the LHS. In the case of CRC,
63+
// it is XOR'ed with the LHS, so that the computation's final remainder is
64+
// zero.
4565
const Value *LHSAux;
66+
4667
PolynomialInfo(unsigned TripCount, const Value *LHS, const APInt &RHS,
4768
const Value *ComputedValue, bool ByteOrderSwapped,
4869
const Value *LHSAux = nullptr);

‎llvm/lib/Analysis/HashRecognize.cpp

Copy file name to clipboardExpand all lines: llvm/lib/Analysis/HashRecognize.cpp
+14-20Lines changed: 14 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@
3535
// following: in such fields, polynomial addition and subtraction are identical
3636
// and equivalent to XOR, polynomial multiplication is an AND, and polynomial
3737
// division is identity: the XOR and AND operations in unoptimized
38-
// implmentations are performed bit-wise, and can be optimized to be performed
38+
// implementations are performed bit-wise, and can be optimized to be performed
3939
// chunk-wise, by interleaving copies of the generating polynomial, and storing
4040
// the pre-computed values in a table.
4141
//
@@ -87,11 +87,10 @@ using PhiStepPair = std::pair<const PHINode *, const Instruction *>;
8787
/// given trip count, and predication is specialized for a significant-bit
8888
/// check.
8989
class ValueEvolution {
90-
unsigned TripCount;
91-
bool ByteOrderSwapped;
90+
const unsigned TripCount;
91+
const bool ByteOrderSwapped;
9292
APInt GenPoly;
9393
StringRef ErrStr;
94-
unsigned AtIteration;
9594

9695
KnownBits computeBinOp(const BinaryOperator *I, const KnownPhiMap &KnownPhis);
9796
KnownBits computeInstr(const Instruction *I, const KnownPhiMap &KnownPhis);
@@ -182,8 +181,8 @@ KnownBits ValueEvolution::computeInstr(const Instruction *I,
182181
if (const PHINode *P = dyn_cast<PHINode>(I))
183182
return KnownPhis.lookup_or(P, BitWidth);
184183

185-
// Compute the KnownBits for a Select(Cmp()), forcing it to take the take the
186-
// branch that is predicated on the (least|most)-significant-bit check.
184+
// Compute the KnownBits for a Select(Cmp()), forcing it to take the branch
185+
// that is predicated on the (least|most)-significant-bit check.
187186
CmpPredicate Pred;
188187
Value *L, *R, *TV, *FV;
189188
if (match(I, m_Select(m_ICmp(Pred, m_Value(L), m_Value(R)), m_Value(TV),
@@ -239,8 +238,6 @@ KnownBits ValueEvolution::computeInstr(const Instruction *I,
239238
/// Compute the KnownBits of Value \p V.
240239
KnownBits ValueEvolution::compute(const Value *V,
241240
const KnownPhiMap &KnownPhis) {
242-
unsigned BitWidth = V->getType()->getScalarSizeInBits();
243-
244241
const APInt *C;
245242
if (match(V, m_APInt(C)))
246243
return KnownBits::makeConstant(*C);
@@ -249,6 +246,7 @@ KnownBits ValueEvolution::compute(const Value *V,
249246
return computeInstr(I, KnownPhis);
250247

251248
ErrStr = "Unknown Value";
249+
unsigned BitWidth = V->getType()->getScalarSizeInBits();
252250
return {BitWidth};
253251
}
254252

@@ -258,7 +256,6 @@ std::optional<KnownPhiMap>
258256
ValueEvolution::computeEvolutions(ArrayRef<PhiStepPair> PhiEvolutions) {
259257
KnownPhiMap KnownPhis;
260258
for (unsigned I = 0; I < TripCount; ++I) {
261-
AtIteration = I;
262259
for (auto [Phi, Step] : PhiEvolutions) {
263260
KnownBits KnownAtIter = computeInstr(Step, KnownPhis);
264261
if (KnownAtIter.getBitWidth() < I + 1) {
@@ -320,8 +317,8 @@ digRecurrence(Instruction *V, const PHINode *P, const Loop &L,
320317
/// \p ExtraConst is relevant if \p BOWithConstOpToMatch is supplied: when
321318
/// digging the use-def chain, a BinOp with opcode \p BOWithConstOpToMatch is
322319
/// matched, and \p ExtraConst is a constant operand of that BinOp. This
323-
/// peculiary exists, because in a CRC algorithm, the \p BOWithConstOpToMatch is
324-
/// an XOR, and the \p ExtraConst ends up being the generating polynomial.
320+
/// peculiarity exists, because in a CRC algorithm, the \p BOWithConstOpToMatch
321+
/// is an XOR, and the \p ExtraConst ends up being the generating polynomial.
325322
static bool matchConditionalRecurrence(
326323
const PHINode *P, BinaryOperator *&BO, Value *&Start, Value *&Step,
327324
const Loop &L, const APInt *&ExtraConst,
@@ -434,9 +431,9 @@ PolynomialInfo::PolynomialInfo(unsigned TripCount, const Value *LHS,
434431
: TripCount(TripCount), LHS(LHS), RHS(RHS), ComputedValue(ComputedValue),
435432
ByteOrderSwapped(ByteOrderSwapped), LHSAux(LHSAux) {}
436433

437-
/// In big-endian case, checks that bottom N bits against CheckFn, and that the
438-
/// rest are unknown. In little-endian case, checks that the top N bits against
439-
/// CheckFn, and that the rest are unknown.
434+
/// In big-endian case, checks that the bottom N bits against CheckFn, and that
435+
/// the rest are unknown. In little-endian case, checks that the top N bits
436+
/// against CheckFn, and that the rest are unknown.
440437
static bool checkExtractBits(const KnownBits &Known, unsigned N,
441438
function_ref<bool(const KnownBits &)> CheckFn,
442439
bool ByteOrderSwapped) {
@@ -459,15 +456,14 @@ static bool checkExtractBits(const KnownBits &Known, unsigned N,
459456
CRCTable HashRecognize::genSarwateTable(const APInt &GenPoly,
460457
bool ByteOrderSwapped) const {
461458
unsigned BW = GenPoly.getBitWidth();
462-
unsigned MSB = 1 << (BW - 1);
463459
CRCTable Table;
464460
Table[0] = APInt::getZero(BW);
465461

466462
if (ByteOrderSwapped) {
467463
APInt CRCInit(BW, 1);
468464
for (unsigned I = 1; I < 256; I <<= 1) {
469465
CRCInit = CRCInit.shl(1) ^
470-
((CRCInit & MSB).isZero() ? APInt::getZero(BW) : GenPoly);
466+
(CRCInit.isSignBitSet() ? GenPoly : APInt::getZero(BW));
471467
for (unsigned J = 0; J < I; ++J)
472468
Table[I + J] = CRCInit ^ Table[J];
473469
}
@@ -476,8 +472,7 @@ CRCTable HashRecognize::genSarwateTable(const APInt &GenPoly,
476472

477473
APInt CRCInit(BW, 128);
478474
for (unsigned I = 128; I; I >>= 1) {
479-
CRCInit = CRCInit.lshr(1) ^
480-
((CRCInit & 1).isZero() ? APInt::getZero(BW) : GenPoly);
475+
CRCInit = CRCInit.lshr(1) ^ (CRCInit[0] ? GenPoly : APInt::getZero(BW));
481476
for (unsigned J = 0; J < 256; J += (I << 1))
482477
Table[I + J] = CRCInit ^ Table[J];
483478
}
@@ -597,8 +592,6 @@ HashRecognize::recognizeCRC() const {
597592
if (SimpleRecurrence)
598593
PhiEvolutions.emplace_back(SimpleRecurrence->Phi, SimpleRecurrence->BO);
599594

600-
const Value *LHSAux = SimpleRecurrence ? SimpleRecurrence->Start : nullptr;
601-
602595
ValueEvolution VE(TC, ByteOrderSwapped);
603596
std::optional<KnownPhiMap> KnownPhis = VE.computeEvolutions(PhiEvolutions);
604597

@@ -610,6 +603,7 @@ HashRecognize::recognizeCRC() const {
610603
if (!checkExtractBits(ResultBits, TC, IsZero, ByteOrderSwapped))
611604
return ErrBits(ResultBits, TC, ByteOrderSwapped);
612605

606+
const Value *LHSAux = SimpleRecurrence ? SimpleRecurrence->Start : nullptr;
613607
return PolynomialInfo(TC, ConditionalRecurrence->Start, GenPoly,
614608
ComputedValue, ByteOrderSwapped, LHSAux);
615609
}

‎llvm/test/Analysis/HashRecognize/cyclic-redundancy-check.ll

Copy file name to clipboardExpand all lines: llvm/test/Analysis/HashRecognize/cyclic-redundancy-check.ll
+2-2Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -332,8 +332,8 @@ exit: ; preds = %outer.loop
332332
ret i8 %crc.outer
333333
}
334334

335-
define i32 @crc16.le.tc8.data32(i32 %checksum, i32 %msg) {
336-
; CHECK-LABEL: 'crc16.le.tc8.data32'
335+
define i32 @crc32.le.tc8.data32(i32 %checksum, i32 %msg) {
336+
; CHECK-LABEL: 'crc32.le.tc8.data32'
337337
; CHECK-NEXT: Found little-endian CRC-32 loop with trip count 8
338338
; CHECK-NEXT: Initial CRC: i32 %checksum
339339
; CHECK-NEXT: Generating polynomial: 33800

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.