HashRecognize.cpp Source File (original) (raw)

70using namespace llvm;

74#define DEBUG_TYPE "hash-recognize"

85 while (!Worklist.empty()) {

90 continue;

92 for (const Use &U : I->operands()) {

94 if (!L.contains(UI))

95 return true;

97 }

98 }

99 }

100 return Latch->size() != Visited.size();

101}

102

103

104

105

113

115 operator bool() const { return BO; }

116

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";

131 OS.indent(Indent) << "ExtraConst: ";

133 OS << "\n";

134 }

135 }

136

137#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

139#endif

140

145

146private:

150};

151

152

153

154

155

156

157

158

159

160

161

162

163

164static bool

167 bool ByteOrderSwapped) {

175 return false;

176

177

178

183 bool LWellFormed = ByteOrderSwapped ? match(L, MatchPred)

185 if (!LWellFormed)

186 return false;

187

195

197 if (AllowedByR == CheckAllowedByR)

198 return TV == BitShift &&

201 if (AllowedByR.inverse() == CheckAllowedByR)

202 return FV == BitShift &&

205 return false;

206}

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

226 return true;

227 }

228 return false;

229}

230

231

232

234RecurrenceInfo::digRecurrence(Instruction *V,

238 while (!Worklist.empty()) {

240

241

243 continue;

244

245

246

249

250

251 if (I->getOpcode() == BOWithConstOpToMatch) {

253 return nullptr;

254 const APInt *C = nullptr;

257 }

258

259

260 for (Use &U : I->operands())

262 if (L.contains(UI))

264 }

265 return nullptr;

266}

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

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

294 if ( match (FoundStep,

296 continue;

297

298

299

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

320

321static std::optional<std::pair<RecurrenceInfo, RecurrenceInfo>>

323 auto Phis = LoopLatch->phis();

324 unsigned NumPhis = std::distance(Phis.begin(), Phis.end());

325 if (NumPhis != 2 && NumPhis != 3)

326 return {};

327

331 if (&P == IndVar)

332 continue;

333 if (!SimpleRecurrence)

335 if (!ConditionalRecurrence)

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

351

352

354 bool ByteOrderSwapped) {

358

359 if (ByteOrderSwapped) {

361 for (unsigned I = 1; I < 256; I <<= 1) {

362 CRCInit = CRCInit.shl(1) ^

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

380

381

382

383

384

385

386

387

388

389

390

391

392

396

397

398

400

401 while (!Worklist.empty()) {

403

404

406 continue;

407

408

411 return true;

412

413

414 for (const Use &U : I->operands())

416 if (L.contains(UI))

418 }

419 return false;

420}

421

422

423

424

425

427 if (!V->getType()->isIntegerTy())

428 return {};

429

432 return false;

434 return true;

435 return {};

436}

437

438

439

441 if (!L.isInnermost())

442 return "Loop is not innermost";

443 BasicBlock *Latch = L.getLoopLatch();

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

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

460

461 std::optional ByteOrderSwapped =

463 if (!ByteOrderSwapped)

464 return "Loop with non-unit bitshifts";

465 if (SimpleRecurrence) {

467 return "Loop with non-unit bitshifts";

468

469

470

471

472

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

479

481 SimpleRecurrence.Phi,

482 ConditionalRecurrence.Phi, L))

483 return "Recurrences not intertwined with XOR";

484 }

485

486

487 Value *LHS = ConditionalRecurrence.Start;

488 Value *LHSAux = SimpleRecurrence ? SimpleRecurrence.Start : nullptr;

490 : LHS->getType()->getIntegerBitWidth()))

491 return "Loop iterations exceed bitwidth of data";

492

493

494

495

496 auto *ComputedValue = cast(ConditionalRecurrence.Step);

497 if (none_of(ComputedValue->users(), [Exit](User *U) {

498 auto *UI = dyn_cast(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

508 *ByteOrderSwapped))

509 return "Malformed significant-bit check";

510

512 {ComputedValue,

515 if (SimpleRecurrence)

516 Roots.push_back(SimpleRecurrence.BO);

518 return "Found stray unvisited instructions";

519

520 return PolynomialInfo(TC, LHS, GenPoly, ComputedValue, *ByteOrderSwapped,

521 LHSAux);

522}

523

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)

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";

542 if (!std::holds_alternative(Ret)) {

543 OS << "Did not find a hash algorithm\n";

544 if (std::holds_alternative(Ret))

545 OS << "Reason: " << std::get(Ret) << "\n";

546 return;

547 }

548

549 auto Info = std::get(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";

569}

570

571#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

573#endif

574

577 if (std::holds_alternative(Res))

578 return std::get(Res);

579 return std::nullopt;

580}

581

584

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements a class to represent arbitrary precision integral constant values and operations...

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.

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,...

Definition HashRecognize.cpp:79

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

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

Definition HashRecognize.cpp:165

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,...

Definition HashRecognize.cpp:393

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...

Definition HashRecognize.cpp:322

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

Definition HashRecognize.cpp:426

This header provides classes for managing per-loop analyses.

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.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LLVM Basic Block Representation.

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...

PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &)

Definition HashRecognize.cpp:585

static CRCTable genSarwateTable(const APInt &GenPoly, bool ByteOrderSwapped)

Generate a lookup table of 256 entries by interleaving the generating polynomial.

Definition HashRecognize.cpp:353

std::optional< PolynomialInfo > getResult() const

Definition HashRecognize.cpp:575

LLVM_DUMP_METHOD void dump() const

Definition HashRecognize.cpp:572

HashRecognize(const Loop &L, ScalarEvolution &SE)

Definition HashRecognize.cpp:582

void print(raw_ostream &OS) const

Definition HashRecognize.cpp:535

std::variant< PolynomialInfo, StringRef > recognizeCRC() const

The main entry point for analyzing a loop and recognizing the CRC algorithm.

Definition HashRecognize.cpp:440

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.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

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.

This class represents the LLVM 'select' instruction.

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.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

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.

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.

ap_match< APInt > m_APInt(const APInt *&Res)

Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.

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)

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.

cst_pred_ty< is_one > m_One()

Match an integer 1 or a vector with all elements equal to 1.

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.

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)

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.

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.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

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.

bool none_of(R &&Range, UnaryPredicate P)

Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

A structure that can hold either a Simple Recurrence or a Conditional Recurrence.

Definition HashRecognize.cpp:106

Value * Step

Definition HashRecognize.cpp:111

const Loop & L

Definition HashRecognize.cpp:107

const PHINode * Phi

Definition HashRecognize.cpp:108

LLVM_DUMP_METHOD void dump() const

Definition HashRecognize.cpp:138

bool matchConditionalRecurrence(const PHINode *P, Instruction::BinaryOps BOWithConstOpToMatch=Instruction::BinaryOpsEnd)

A Conditional Recurrence is a recurrence of the form:

Definition HashRecognize.cpp:283

void print(raw_ostream &OS, unsigned Indent=0) const

Definition HashRecognize.cpp:117

std::optional< APInt > ExtraConst

Definition HashRecognize.cpp:112

bool matchSimpleRecurrence(const PHINode *P)

Wraps llvm::matchSimpleRecurrence.

Definition HashRecognize.cpp:223

Value * Start

Definition HashRecognize.cpp:110

BinaryOperator * BO

Definition HashRecognize.cpp:109

RecurrenceInfo(const Loop &L)

Definition HashRecognize.cpp:114

A custom std::array with 256 entries, that also has a print function.

LLVM_DUMP_METHOD void dump() const

Definition HashRecognize.cpp:532

void print(raw_ostream &OS) const

Definition HashRecognize.cpp:524

static KnownBits makeConstant(const APInt &C)

Create known bits from a known constant.

unsigned getBitWidth() const

Get the bit width of this value.

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)

Definition HashRecognize.cpp:344