1 //===- HashRecognize.h ------------------------------------------*- 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 // Interface for the HashRecognize analysis, which identifies hash functions 10 // that can be optimized using a lookup-table or with target-specific 11 // instructions. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ANALYSIS_HASHRECOGNIZE_H 16 #define LLVM_ANALYSIS_HASHRECOGNIZE_H 17 18 #include "llvm/ADT/APInt.h" 19 #include "llvm/Analysis/LoopAnalysisManager.h" 20 #include "llvm/Analysis/ScalarEvolution.h" 21 #include "llvm/IR/PassManager.h" 22 #include "llvm/IR/Value.h" 23 #include "llvm/Support/KnownBits.h" 24 #include <variant> 25 26 namespace llvm { 27 28 class LPMUpdater; 29 30 /// A tuple of bits that are expected to be zero, number N of them expected to 31 /// be zero, with a boolean indicating whether it's the top or bottom N bits 32 /// expected to be zero. 33 using ErrBits = std::tuple<KnownBits, unsigned, bool>; 34 35 /// A custom std::array with 256 entries, that also has a print function. 36 struct CRCTable : public std::array<APInt, 256> { 37 void print(raw_ostream &OS) const; 38 39 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 40 LLVM_DUMP_METHOD void dump() const; 41 #endif 42 }; 43 44 /// The structure that is returned when a polynomial algorithm was recognized by 45 /// the analysis. Currently, only the CRC algorithm is recognized. 46 struct PolynomialInfo { 47 // The small constant trip-count of the analyzed loop. 48 unsigned TripCount; 49 50 // The LHS in a polynomial operation, or the initial variable of the 51 // computation, since all polynomial operations must have a constant RHS, 52 // which is the generating polynomial. It is the LHS of the polynomial 53 // division in the case of CRC. Since polynomial division is an XOR in 54 // GF(2^m), this variable must be XOR'ed with RHS in a loop to yield the 55 // ComputedValue. 56 Value *LHS; 57 58 // The generating polynomial, or the RHS of the polynomial division in the 59 // case of CRC. 60 APInt RHS; 61 62 // The final computed value. This is a remainder of a polynomial division in 63 // the case of CRC, which must be zero. 64 Value *ComputedValue; 65 66 // Set to true in the case of big-endian. 67 bool ByteOrderSwapped; 68 69 // An optional auxiliary checksum that augments the LHS. In the case of CRC, 70 // it is XOR'ed with the LHS, so that the computation's final remainder is 71 // zero. 72 Value *LHSAux; 73 74 PolynomialInfo(unsigned TripCount, Value *LHS, const APInt &RHS, 75 Value *ComputedValue, bool ByteOrderSwapped, 76 Value *LHSAux = nullptr); 77 }; 78 79 /// The analysis. 80 class HashRecognize { 81 const Loop &L; 82 ScalarEvolution &SE; 83 84 public: 85 HashRecognize(const Loop &L, ScalarEvolution &SE); 86 87 // The main analysis entry points. 88 std::variant<PolynomialInfo, ErrBits, StringRef> recognizeCRC() const; 89 std::optional<PolynomialInfo> getResult() const; 90 91 // Auxilary entry point after analysis to interleave the generating polynomial 92 // and return a 256-entry CRC table. 93 static CRCTable genSarwateTable(const APInt &GenPoly, bool ByteOrderSwapped); 94 95 void print(raw_ostream &OS) const; 96 97 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 98 LLVM_DUMP_METHOD void dump() const; 99 #endif 100 }; 101 102 class HashRecognizePrinterPass 103 : public PassInfoMixin<HashRecognizePrinterPass> { 104 raw_ostream &OS; 105 106 public: HashRecognizePrinterPass(raw_ostream & OS)107 explicit HashRecognizePrinterPass(raw_ostream &OS) : OS(OS) {} 108 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 109 LoopStandardAnalysisResults &AR, LPMUpdater &); 110 }; 111 } // namespace llvm 112 113 #endif 114