IVDescriptors.cpp Source File (original) (raw)

27using namespace llvm;

31#define DEBUG_TYPE "iv-descriptors"

35 for (const Use &Use : I->operands())

37 return false;

38 return true;

39}

42 switch (Kind) {

43 default:

44 break;

61 return true;

62 }

63 return false;

64}

77 if (!Phi->hasOneUse())

78 return Phi;

80 const APInt *M = nullptr;

86 int32_t Bits = (*M + 1).exactLogBase2();

87 if (Bits > 0) {

91 return J;

92 }

93 }

94 return Phi;

95}

103 bool IsSigned = false;

104 const DataLayout &DL = Exit->getDataLayout();

105 uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());

106

107 if (DB) {

108

109

110

111

112

113 auto Mask = DB->getDemandedBits(Exit);

114 MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero();

115 }

116

117 if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {

118

119

120

122 auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());

123 MaxBitWidth = NumTypeBits - NumSignBits;

125 if (!Bits.isNonNegative()) {

126

127

128

129 IsSigned = true;

130

131

132 ++MaxBitWidth;

133 }

134 }

136

137 return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),

138 IsSigned);

139}

140

141

142

143

144

146 Type *RecurrenceType,

148 unsigned &MinWidthCastToRecurTy) {

149

153 MinWidthCastToRecurTy = -1U;

154

155 while (!Worklist.empty()) {

159 if (Cast->getSrcTy() == RecurrenceType) {

160

161

162

164 continue;

165 }

166 if (Cast->getDestTy() == RecurrenceType) {

167

168

169

170

171 MinWidthCastToRecurTy = std::min(

172 MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits());

173 continue;

174 }

175 }

176

177

182 }

183}

184

185

186

189

191 return false;

192

193 if (Kind == RecurKind::FAdd && Exit->getOpcode() != Instruction::FAdd)

194 return false;

195

198 return false;

199

200

201 if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3))

202 return false;

203

204

205

206 auto *Op0 = Exit->getOperand(0);

207 auto *Op1 = Exit->getOperand(1);

209 return false;

211 return false;

212

213 LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phi

214 << ", ExitInst: " << *Exit << "\n");

215

216 return true;

217}

218

219

220

221

225 if (!Latch)

226 return false;

227

228 assert(Phi->getNumIncomingValues() == 2 && "phi must have 2 incoming values");

229 Value *Inc = Phi->getIncomingValueForBlock(Latch);

230 if (Phi->hasOneUse() || !Inc->hasOneUse() ||

232 return false;

233

235 bool IsMinMax = [&]() {

236 switch (Kind) {

245 default:

247 }

248 }();

249 if (!IsMinMax)

250 return false;

251

252 if (A == B || (A != Phi && B != Phi))

253 return false;

254

257 RedDes =

259 FastMathFlags(), nullptr, Phi->getType(),

260 false, false, CastInsts,

261 -1U, true);

262 return true;

263}

264

269 if (Phi->getNumIncomingValues() != 2)

270 return false;

271

272

273 if (Phi->getParent() != TheLoop->getHeader())

274 return false;

275

276

278 RedDes))

279 return true;

280

281

282

284

285

286

287

288

290

291

292

293

295

296

297 bool FoundReduxOp = false;

298

299

300

301

302

303 bool FoundStartPHI = false;

304

305

306

307

308 unsigned NumCmpSelectPatternInst = 0;

309 InstDesc ReduxDesc(false, nullptr);

310

311

312 Type *RecurrenceType = Phi->getType();

314 unsigned MinWidthCastToRecurrenceType;

316 bool IsSigned = false;

317

320

321

322

323

324

325

326

330 return false;

333 return false;

335 Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);

336 } else {

337

338 return false;

339 }

340

342 VisitedInsts.insert(Start);

343

344

345

347

348

349

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371 while (!Worklist.empty()) {

373

374

375

377 if (!SE) {

378 LLVM_DEBUG(dbgs() << "Store instructions are not processed without "

379 << "Scalar Evolution Analysis\n");

380 return false;

381 }

382

383 const SCEV *PtrScev = SE->getSCEV(SI->getPointerOperand());

384

386 const SCEV *OtherScev =

388

389 if (OtherScev != PtrScev) {

390 LLVM_DEBUG(dbgs() << "Storing reduction value to different addresses "

391 << "inside the loop: " << *SI->getPointerOperand()

392 << " and "

394 return false;

395 }

396 }

397

398

400 LLVM_DEBUG(dbgs() << "Storing reduction value to non-uniform address "

401 << "inside the loop: " << *SI->getPointerOperand()

402 << '\n');

403 return false;

404 }

405

406

408 continue;

409 }

410

411

412

413

415 return false;

416

418

419

420 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())

421 return false;

422

423

424

428 return false;

429

430

431

432

433 if (Cur != Start) {

434 ReduxDesc =

435 isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF, SE);

436 ExactFPMathInst = ExactFPMathInst == nullptr

438 : ExactFPMathInst;

440 return false;

441

445

446

447

448

450 CurFMF |= FCmp->getFastMathFlags();

451 }

452 FMF &= CurFMF;

453 }

454

455

456

459 }

460

462

463

464

467 return false;

468

469

472 return false;

473

474

475 if (IsAPhi && Cur != Phi && areAllUsesIn (Cur, VisitedInsts))

476 return false;

477

479 ++NumCmpSelectPatternInst;

481 ++NumCmpSelectPatternInst;

483 ++NumCmpSelectPatternInst;

484

485

486 FoundReduxOp |= !IsAPhi && Cur != Start;

487

488

489

490

495

496

497

500 return false;

501

502

504 if (!TheLoop->contains(Parent)) {

505

506

507 if (ExitInstruction == Cur)

508 continue;

509

510

511

512

513

514 if (ExitInstruction != nullptr || Cur == Phi)

515 return false;

516

517

518

519

521 return false;

522

523 ExitInstruction = Cur;

524 continue;

525 }

526

527

528

529

530 InstDesc IgnoredVal(false, nullptr);

531 if (VisitedInsts.insert(UI).second) {

534 } else {

536 if (SI && SI->getPointerOperand() == Cur) {

537

538

539 return false;

540 }

542 }

548 .isRecurrence() &&

550 return false;

551

552

553 if (UI == Phi)

554 FoundStartPHI = true;

555 }

558 }

559

560

561

562

564 NumCmpSelectPatternInst != 0)

565 return false;

566

568 return false;

569

571

572

573

575 LLVM_DEBUG(dbgs() << "Not a final reduction value stored: "

577 return false;

578 }

579

580

581

582 if (ExitInstruction &&

584 LLVM_DEBUG(dbgs() << "Last store Instruction of reduction value does not "

585 "store last calculated value of the reduction: "

587 return false;

588 }

589

590

591

592 if (!ExitInstruction)

594 }

595

596 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)

597 return false;

598

599 const bool IsOrdered =

601

602 if (Start != Phi) {

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627 Type *ComputedType;

628 std::tie(ComputedType, IsSigned) =

630 if (ComputedType != RecurrenceType)

631 return false;

632 }

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647 collectCastInstrs(TheLoop, ExitInstruction, RecurrenceType, CastInsts,

648 MinWidthCastToRecurrenceType);

649

650

651

652

653

654

655

656

658 FMF, ExactFPMathInst, RecurrenceType, IsSigned,

659 IsOrdered, CastInsts, MinWidthCastToRecurrenceType);

660 RedDes = RD;

661

662 return true;

663}

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

689

690

694 }

695

698

700 Value *NonPhi = nullptr;

701

703 NonPhi = SI->getFalseValue();

705 NonPhi = SI->getTrueValue();

706 else

708

709

710

711

714

716}

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

752

753

754

755

758

759

760

761

762

763 Value *NonRdxPhi = nullptr;

769

770

771

772 auto GetRecurKind = [&](Value *V) -> std::optional {

773 Type *Ty = V->getType();

775 return std::nullopt;

776

777 auto *AR = SE.getSCEV(V);

778 const SCEV *Step;

781 return std::nullopt;

782

785 return std::nullopt;

786

787

788

789

790

791

792

793

794

795 auto CheckRange = [&](bool IsSigned) {

798 unsigned NumBits = Ty->getIntegerBitWidth();

799 ConstantRange ValidRange = ConstantRange::getEmpty(NumBits);

804 } else {

805 if (IsSigned)

806 ValidRange =

809 else

812 }

813

816 : "FindFirstIV")

817 << " valid range is " << ValidRange

818 << ", and the range of " << *AR << " is " << IVRange

819 << "\n");

820

821

822

823 return ValidRange.contains(IVRange);

824 };

826 if (CheckRange(true))

828 if (CheckRange(false))

830 return std::nullopt;

831 }

833 "Kind must either be a FindLastIV or FindFirstIV");

834

835 if (CheckRange(true))

837 if (CheckRange(false))

839 return std::nullopt;

840 };

841

842 if (auto RK = GetRecurKind(NonRdxPhi))

844

846}

847

852 "Expected a cmp or select or call instruction");

855

856

857

861 }

862

863

867

868

893

895}

896

897

898

899

900

901

902

903

904

905

908 Value *TrueVal, *FalseVal;

909

913

914

915

919

922 if (!I1 || !I1->isBinaryOp())

924

925 Value *Op1, *Op2;

928 I1->isFast()) ||

934

937 if (!IPhi || IPhi != FalseVal)

939

941}

942

947 switch (I->getOpcode()) {

948 default:

950 case Instruction::PHI:

952 case Instruction::Sub:

955 case Instruction::Add:

958 case Instruction::Mul:

960 case Instruction::And:

962 case Instruction::Or:

964 case Instruction::Xor:

966 case Instruction::FDiv:

967 case Instruction::FMul:

969 I->hasAllowReassoc() ? nullptr : I);

970 case Instruction::FSub:

971 case Instruction::FAdd:

973 I->hasAllowReassoc() ? nullptr : I);

974 case Instruction::Select:

981 [[fallthrough]];

982 case Instruction::FCmp:

983 case Instruction::ICmp:

984 case Instruction::Call:

987 auto HasRequiredFMF = [&]() {

989 return true;

991 return true;

992

993

994

1000 };

1007 if (HasRequiredFMF())

1008 return Res;

1009

1010

1011

1014 "unexpected recurrence kind for maxnum");

1016 }

1019 "unexpected recurrence kind for minnum");

1021 }

1023 }

1026 I->hasAllowReassoc() ? nullptr : I);

1028 }

1029}

1030

1033 unsigned MaxNumUses) {

1034 unsigned NumUses = 0;

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

1037 ++NumUses;

1038 if (NumUses > MaxNumUses)

1039 return true;

1040 }

1041

1042 return false;

1043}

1044

1051 Function &F = *Header->getParent();

1054 F.getFnAttribute("no-nans-fp-math").getValueAsBool());

1055 FMF.setNoSignedZeros(

1056 F.getFnAttribute("no-signed-zeros-fp-math").getValueAsBool());

1057

1059 SE)) {

1060 LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");

1061 return true;

1062 }

1064 SE)) {

1065 LLVM_DEBUG(dbgs() << "Found a SUB reduction PHI." << *Phi << "\n");

1066 return true;

1067 }

1069 DB, AC, DT, SE)) {

1070 LLVM_DEBUG(dbgs() << "Found a chained ADD-SUB reduction PHI." << *Phi

1071 << "\n");

1072 return true;

1073 }

1075 SE)) {

1076 LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");

1077 return true;

1078 }

1080 SE)) {

1081 LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");

1082 return true;

1083 }

1085 SE)) {

1086 LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");

1087 return true;

1088 }

1090 SE)) {

1091 LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");

1092 return true;

1093 }

1095 SE)) {

1096 LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n");

1097 return true;

1098 }

1100 SE)) {

1101 LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n");

1102 return true;

1103 }

1105 SE)) {

1106 LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n");

1107 return true;

1108 }

1110 SE)) {

1111 LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n");

1112 return true;

1113 }

1115 SE)) {

1116 LLVM_DEBUG(dbgs() << "Found a conditional select reduction PHI." << *Phi

1117 << "\n");

1118 return true;

1119 }

1121 AC, DT, SE)) {

1122 LLVM_DEBUG(dbgs() << "Found a FindLastIV reduction PHI." << *Phi << "\n");

1123 return true;

1124 }

1126 AC, DT, SE)) {

1127 LLVM_DEBUG(dbgs() << "Found a FindFirstIV reduction PHI." << *Phi << "\n");

1128 return true;

1129 }

1131 SE)) {

1132 LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");

1133 return true;

1134 }

1136 SE)) {

1137 LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");

1138 return true;

1139 }

1141 SE)) {

1142 LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n");

1143 return true;

1144 }

1146 SE)) {

1147 LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n");

1148 return true;

1149 }

1151 SE)) {

1152 LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n");

1153 return true;

1154 }

1156 SE)) {

1157 LLVM_DEBUG(dbgs() << "Found a float MAXIMUM reduction PHI." << *Phi << "\n");

1158 return true;

1159 }

1161 SE)) {

1162 LLVM_DEBUG(dbgs() << "Found a float MINIMUM reduction PHI." << *Phi << "\n");

1163 return true;

1164 }

1166 DT, SE)) {

1167 LLVM_DEBUG(dbgs() << "Found a float MAXIMUMNUM reduction PHI." << *Phi

1168 << "\n");

1169 return true;

1170 }

1172 DT, SE)) {

1173 LLVM_DEBUG(dbgs() << "Found a float MINIMUMNUM reduction PHI." << *Phi

1174 << "\n");

1175 return true;

1176 }

1177

1178

1179 return false;

1180}

1181

1184

1185

1186 if (Phi->getParent() != TheLoop->getHeader() ||

1187 Phi->getNumIncomingValues() != 2)

1188 return false;

1189

1190

1191

1194 if (!Preheader || !Latch)

1195 return false;

1196

1197

1198 if (Phi->getBasicBlockIndex(Preheader) < 0 ||

1199 Phi->getBasicBlockIndex(Latch) < 0)

1200 return false;

1201

1202

1203

1205

1206

1207

1208

1209

1212 if (PrevPhi->getParent() != Phi->getParent())

1213 return false;

1214 if (!SeenPhis.insert(PrevPhi).second)

1215 return false;

1217 }

1218

1220 return false;

1221

1222

1223

1224

1225

1226

1227

1229 BasicBlock *PhiBB = Phi->getParent();

1231 auto TryToPushSinkCandidate = [&](Instruction *SinkCandidate) {

1232

1233 if (Previous == SinkCandidate)

1234 return false;

1235

1236 if (!Seen.insert(SinkCandidate).second)

1237 return true;

1239 SinkCandidate))

1240 return true;

1241

1242 if (SinkCandidate->getParent() != PhiBB ||

1243 SinkCandidate->mayHaveSideEffects() ||

1244 SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())

1245 return false;

1246

1247

1248

1250 return true;

1251

1252

1253 WorkList.push_back(SinkCandidate);

1254 return true;

1255 };

1256

1258

1259 while (!WorkList.empty()) {

1263 return false;

1264 }

1265 }

1266

1267 return true;

1268}

1269

1271 switch (Kind) {

1273 return Instruction::Sub;

1276 return Instruction::Add;

1278 return Instruction::Mul;

1280 return Instruction::Or;

1282 return Instruction::And;

1284 return Instruction::Xor;

1286 return Instruction::FMul;

1289 return Instruction::FAdd;

1294 return Instruction::ICmp;

1301 return Instruction::FCmp;

1307

1308

1309 default:

1311 }

1312}

1313

1318

1319

1320

1321

1322

1323

1324

1325

1326

1327

1328

1329

1330

1331

1332

1333

1334 unsigned ExpectedUses = 1;

1335 if (IsMinMax)

1336 ExpectedUses = 2;

1337

1339 for (auto *User : Cur->users()) {

1342 continue;

1343 if (IsMinMax) {

1344

1345

1347 return UI;

1348 continue;

1349 }

1350 return UI;

1351 }

1352 return nullptr;

1353 };

1354 auto isCorrectOpcode = [&](Instruction *Cur) {

1355 if (IsMinMax) {

1356 Value *LHS, *RHS;

1359 }

1360

1362 return true;

1363

1364 if (Cur->getOpcode() == Instruction::Sub &&

1366 return true;

1367

1368 return Cur->getOpcode() == getOpcode();

1369 };

1370

1371

1372 unsigned ExtraPhiUses = 0;

1375 if (ExitPhi->getNumIncomingValues() != 2)

1376 return {};

1377

1380

1382 if (Inc0 == Phi)

1383 Chain = Inc1;

1384 else if (Inc1 == Phi)

1385 Chain = Inc0;

1386 else

1387 return {};

1388

1389 RdxInstr = Chain;

1390 ExtraPhiUses = 1;

1391 }

1392

1393

1394

1395

1396

1397 if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->hasNUses(2))

1398 return {};

1399

1400

1401

1402 if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses))

1403 return {};

1404

1405 Instruction *Cur = getNextInstruction(Phi);

1406

1407

1408

1409 while (Cur != RdxInstr) {

1410 if (!Cur || !isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses))

1411 return {};

1412

1413 ReductionOperations.push_back(Cur);

1414 Cur = getNextInstruction(Cur);

1415 }

1416

1417 ReductionOperations.push_back(Cur);

1418 return ReductionOperations;

1419}

1420

1424 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) {

1425 assert(IK != IK_NoInduction && "Not an induction");

1426

1427

1428

1429 assert(StartValue && "StartValue is null");

1430 assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&

1431 "StartValue is not a pointer for pointer induction");

1432 assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&

1433 "StartValue is not an integer for integer induction");

1434

1435

1436 assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&

1437 "Step value is zero");

1438

1440 "StepValue is not an integer");

1441

1443 "StepValue is not FP for FpInduction");

1444 assert((IK != IK_FpInduction ||

1445 (InductionBinOp &&

1446 (InductionBinOp->getOpcode() == Instruction::FAdd ||

1447 InductionBinOp->getOpcode() == Instruction::FSub))) &&

1448 "Binary opcode should be specified for FP induction");

1449

1450 if (Casts)

1452}

1453

1457 return nullptr;

1458}

1459

1463

1464

1465 assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");

1466

1467 if (TheLoop->getHeader() != Phi->getParent())

1468 return false;

1469

1470

1471

1472 if (Phi->getNumIncomingValues() != 2)

1473 return false;

1474 Value *BEValue = nullptr, *StartValue = nullptr;

1475 if (TheLoop->contains(Phi->getIncomingBlock(0))) {

1476 BEValue = Phi->getIncomingValue(0);

1477 StartValue = Phi->getIncomingValue(1);

1478 } else {

1479 assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&

1480 "Unexpected Phi node in the loop");

1481 BEValue = Phi->getIncomingValue(1);

1482 StartValue = Phi->getIncomingValue(0);

1483 }

1484

1486 if (!BOp)

1487 return false;

1488

1489 Value *Addend = nullptr;

1490 if (BOp->getOpcode() == Instruction::FAdd) {

1495 } else if (BOp->getOpcode() == Instruction::FSub)

1498

1499 if (!Addend)

1500 return false;

1501

1502

1505 return false;

1506

1507

1510 return true;

1511}

1512

1513

1514

1515

1516

1517

1518

1519

1520

1521

1522

1523

1524

1525

1526

1527

1528

1529

1530

1531

1532

1533

1534

1535

1536

1537

1538

1539

1540

1541

1542

1543

1544

1549

1550 assert(CastInsts.empty() && "CastInsts is expected to be empty.");

1552 assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression");

1554

1555

1556

1557

1558

1559

1560

1561

1562

1565 if (!BinOp)

1566 return nullptr;

1569 Value *Def = nullptr;

1570 if (L->isLoopInvariant(Op0))

1571 Def = Op1;

1572 else if (L->isLoopInvariant(Op1))

1573 Def = Op0;

1574 return Def;

1575 };

1576

1577

1578

1579 BasicBlock *Latch = L->getLoopLatch();

1580 if (!Latch)

1581 return false;

1582 Value *Val = PN->getIncomingValueForBlock(Latch);

1583 if (!Val)

1584 return false;

1585

1586

1587

1588

1589

1590 bool InCastSequence = false;

1592 while (Val != PN) {

1593

1594

1595 if (!Inst || !L->contains(Inst)) {

1596 return false;

1597 }

1600 InCastSequence = true;

1601 if (InCastSequence) {

1602

1603

1604 if (!CastInsts.empty())

1605 if (!Inst->hasOneUse())

1606 return false;

1608 }

1610 if (!Val)

1611 return false;

1613 }

1614

1615 return InCastSequence;

1616}

1617

1621 Type *PhiTy = Phi->getType();

1622

1623

1624

1625

1626

1629 return false;

1630

1633

1636

1637

1638 if (Assume && !AR)

1640

1641 if (!AR) {

1642 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");

1643 return false;

1644 }

1645

1646

1648

1649

1650

1651

1652

1653 if (PhiScev != AR && SymbolicPhi) {

1657 }

1658

1660}

1661

1666 Type *PhiTy = Phi->getType();

1667

1669 return false;

1670

1671

1672 const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);

1673 const SCEV *Step;

1674

1675

1676

1677

1681 dbgs() << "LV: PHI is not a poly recurrence for requested loop.\n");

1682 return false;

1683 }

1684

1685

1686

1687

1689 "Invalid Phi node, not present in loop header");

1690

1691 Value *StartValue =

1693

1695 if (!Latch)

1696 return false;

1697

1702 CastsToIgnore);

1703 return true;

1704 }

1705

1707

1708

1710 return true;

1711}

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

AMDGPU Register Bank Select

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR, SmallVectorImpl< Instruction * > &CastInsts)

This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expr...

Definition IVDescriptors.cpp:1545

static bool isMinMaxReductionPhiWithUsersOutsideReductionChain(PHINode *Phi, RecurKind Kind, Loop *TheLoop, RecurrenceDescriptor &RedDes)

Returns true if Phi is a min/max reduction matching Kind where Phi is used outside the reduction chai...

Definition IVDescriptors.cpp:222

static void collectCastInstrs(Loop *TheLoop, Instruction *Exit, Type *RecurrenceType, SmallPtrSetImpl< Instruction * > &Casts, unsigned &MinWidthCastToRecurTy)

Collect cast instructions that can be ignored in the vectorizer's cost model, given a reduction exit ...

Definition IVDescriptors.cpp:145

static bool checkOrderedReduction(RecurKind Kind, Instruction *ExactFPMathInst, Instruction *Exit, PHINode *Phi)

Definition IVDescriptors.cpp:187

static Instruction * lookThroughAnd(PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction * > &Visited, SmallPtrSetImpl< Instruction * > &CI)

Determines if Phi may have been type-promoted.

Definition IVDescriptors.cpp:74

static std::pair< Type *, bool > computeRecurrenceType(Instruction *Exit, DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT)

Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit...

Definition IVDescriptors.cpp:99

static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)

Class for arbitrary precision integers.

static APInt getMaxValue(unsigned numBits)

Gets maximum unsigned value of APInt for specific bit width.

static APInt getSignedMaxValue(unsigned numBits)

Gets maximum signed value of APInt for a specific bit width.

static APInt getMinValue(unsigned numBits)

Gets minimum unsigned value of APInt for a specific bit width.

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

A cache of @llvm.assume calls within a function.

LLVM Basic Block Representation.

BinaryOps getOpcode() const

This is the shared class of boolean and integer constants.

This class represents a range of values.

LLVM_ABI bool contains(const APInt &Val) const

Return true if the specified value is in the set.

static ConstantRange getNonEmpty(APInt Lower, APInt Upper)

Create non-empty constant range with the given bounds.

A parsed version of the target data layout string in and methods for querying it.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

Convenience struct for specifying and reasoning about fast-math flags.

bool noSignedZeros() const

void setNoNaNs(bool B=true)

static FastMathFlags getFast()

@ IK_FpInduction

Floating point induction variable.

@ IK_PtrInduction

Pointer induction var. Step = C.

@ IK_IntInduction

Integer induction variable. Step = C.

static LLVM_ABI bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)

Returns true if Phi is an induction in the loop L.

Definition IVDescriptors.cpp:1662

static LLVM_ABI bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D)

Returns true if Phi is a floating point induction in the loop L.

Definition IVDescriptors.cpp:1460

InductionDescriptor()=default

Default constructor - creates an invalid induction.

LLVM_ABI ConstantInt * getConstIntStepValue() const

Definition IVDescriptors.cpp:1454

LLVM_ABI bool isCommutative() const LLVM_READONLY

Return true if the instruction is commutative:

LLVM_ABI FastMathFlags getFastMathFlags() const LLVM_READONLY

Convenience function for getting all the fast-math flags, which must be an operator which supports th...

static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)

This static method is the primary way of constructing an IntegerType.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

BlockT * getHeader() const

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

Represents a single loop in the control flow graph.

bool isLoopInvariant(const Value *V) const

Return true if the specified value is loop invariant.

An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...

ScalarEvolution * getSE() const

Returns the ScalarEvolution analysis used.

LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const

Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.

LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V)

Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.

LLVM_ABI const SCEV * getSCEV(Value *V)

Returns the SCEV expression of V, in the context of the current SCEV predicate.

This POD struct holds information about a potential recurrence operation.

RecurKind getRecKind() const

Instruction * getPatternInst() const

bool isRecurrence() const

Instruction * getExactFPMathInst() const

The RecurrenceDescriptor is used to identify recurrences variables in a loop.

static bool isFPMinMaxRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is a floating-point min/max kind.

static bool isFMulAddIntrinsic(Instruction *I)

Returns true if the instruction is a call to the llvm.fmuladd intrinsic.

static bool isFindFirstIVRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

static LLVM_ABI bool isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, DominatorTree *DT)

Returns true if Phi is a fixed-order recurrence.

Definition IVDescriptors.cpp:1182

unsigned getOpcode() const

static LLVM_ABI InstDesc isConditionalRdxPattern(Instruction *I)

Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode),...

Definition IVDescriptors.cpp:907

static LLVM_ABI bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction * > &Insts, unsigned MaxNumUses)

Returns true if instruction I has multiple uses in Insts.

Definition IVDescriptors.cpp:1031

static LLVM_ABI bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)

Returns true if Phi is a reduction in TheLoop.

Definition IVDescriptors.cpp:1045

static LLVM_ABI bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction * > &Set)

Returns true if all uses of the instruction I is within the Set.

Definition IVDescriptors.cpp:33

RecurrenceDescriptor()=default

LLVM_ABI SmallVector< Instruction *, 4 > getReductionOpChain(PHINode *Phi, Loop *L) const

Attempts to find a chain of operations from Phi to LoopExitInst that can be treated as a set of reduc...

Definition IVDescriptors.cpp:1315

static bool isAnyOfRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

static LLVM_ABI InstDesc isAnyOfPattern(Loop *Loop, PHINode *OrigPhi, Instruction *I, InstDesc &Prev)

Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...

Definition IVDescriptors.cpp:687

static bool isFindLastIVRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

StoreInst * IntermediateStore

Reductions may store temporary or final result to an invariant address.

static LLVM_ABI InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I, RecurKind Kind, InstDesc &Prev, FastMathFlags FuncFMF, ScalarEvolution *SE)

Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a ...

Definition IVDescriptors.cpp:943

static LLVM_ABI InstDesc isFindIVPattern(RecurKind Kind, Loop *TheLoop, PHINode *OrigPhi, Instruction *I, ScalarEvolution &SE)

Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...

Definition IVDescriptors.cpp:749

static LLVM_ABI bool isFloatingPointRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is a floating point kind.

Definition IVDescriptors.cpp:66

static bool isFindIVRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

static LLVM_ABI InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind, const InstDesc &Prev)

Returns a struct describing if the instruction is a llvm.

Definition IVDescriptors.cpp:849

static LLVM_ABI bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)

Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.

Definition IVDescriptors.cpp:265

static LLVM_ABI bool isIntegerRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is an integer kind.

Definition IVDescriptors.cpp:41

static bool isIntMinMaxRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is an integer min/max kind.

static bool isMinMaxRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is any min/max kind.

This node represents a polynomial recurrence on the trip count of the specified loop.

const Loop * getLoop() const

This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...

This class represents an analyzed expression in the program.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

LLVM_ABI bool isKnownNegative(const SCEV *S)

Test if the given expression is known to be negative.

LLVM_ABI const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

ConstantRange getSignedRange(const SCEV *S)

Determine the signed range for a particular SCEV.

LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)

Return true if the value of the given SCEV is unchanging in the specified loop.

LLVM_ABI bool isKnownPositive(const SCEV *S)

Test if the given expression is known to be positive.

LLVM_ABI bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

ConstantRange getUnsignedRange(const SCEV *S)

Determine the unsigned range for a particular SCEV.

LLVM_ABI const SCEV * getUnknown(Value *V)

This class represents the LLVM 'select' instruction.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

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.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

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

An instruction for storing to memory.

The instances of the Type class are immutable: once they are created, they are never changed.

bool isPointerTy() const

True if this is an instance of PointerType.

bool isFloatTy() const

Return true if this is 'float', a 32-bit IEEE fp type.

Type * getScalarType() const

If this is a vector type, return the element type, otherwise return 'this'.

bool isHalfTy() const

Return true if this is 'half', a 16-bit IEEE fp type.

bool isDoubleTy() const

Return true if this is 'double', a 64-bit IEEE fp type.

bool isFloatingPointTy() const

Return true if this is one of the floating-point types.

bool isIntegerTy() const

True if this is an instance of IntegerType.

static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)

A Use represents the edge between a Value definition and its users.

Value * getOperand(unsigned i) const

LLVM Value Representation.

bool hasOneUse() const

Return true if there is exactly one use of this value.

iterator_range< user_iterator > users()

LLVM_ABI bool hasNUses(unsigned N) const

Return true if this Value has exactly N uses.

const ParentTy * getParent() const

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

OneUse_match< SubPat > m_OneUse(const SubPat &SP)

BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)

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::FMul > m_FMul(const LHS &L, const RHS &R)

bool match(Val *V, const Pattern &P)

bind_ty< Instruction > m_Instruction(Instruction *&I)

Match an instruction, capturing it if we match.

m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMaxNum(const Opnd0 &Op0, const Opnd1 &Op1)

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_IntrinsicIntrinsic::fabs(m_Value(X))

ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)

Matches SelectInst.

m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMinimum(const Opnd0 &Op0, const Opnd1 &Op1)

match_combine_or< MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty >, MaxMin_match< FCmpInst, LHS, RHS, ufmin_pred_ty > > m_OrdOrUnordFMin(const LHS &L, const RHS &R)

Match an 'ordered' or 'unordered' floating point minimum function.

MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)

m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMaximum(const Opnd0 &Op0, const Opnd1 &Op1)

BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)

BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)

m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMaximumNum(const Opnd0 &Op0, const Opnd1 &Op1)

MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)

class_match< CmpInst > m_Cmp()

Matches any compare instruction and ignore it.

m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMinimumNum(const Opnd0 &Op0, const Opnd1 &Op1)

match_combine_or< MaxMin_match< FCmpInst, LHS, RHS, ofmax_pred_ty >, MaxMin_match< FCmpInst, LHS, RHS, ufmax_pred_ty > > m_OrdOrUnordFMax(const LHS &L, const RHS &R)

Match an 'ordered' or 'unordered' floating point maximum function.

MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMinNum(const Opnd0 &Op0, const Opnd1 &Op1)

BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)

MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)

match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)

Combine two pattern matchers matching L || R.

specificloop_ty m_SpecificLoop(const Loop *L)

SCEVAffineAddRec_match< Op0_t, Op1_t, class_match< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)

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.

MachineInstr * getDef(const MachineOperand &MO, const MachineRegisterInfo *MRI)

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

T bit_ceil(T Value)

Returns the smallest integral power of two no smaller than Value if Value is nonzero.

auto dyn_cast_or_null(const Y &Val)

LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)

Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...

LLVM_ABI SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)

Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

bool isa(const From &Val)

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

RecurKind

These are the kinds of recurrences that we support.

@ UMin

Unsigned integer min implemented in terms of select(cmp()).

@ FMinimumNum

FP min with llvm.minimumnum semantics.

@ FindLastIVUMax

FindLast reduction with select(cmp(),x,y) where one of (x,y) is increasing loop induction,...

@ FindFirstIVUMin

FindFirst reduction with select(icmp(),x,y) where one of (x,y) is a decreasing loop induction,...

@ Or

Bitwise or logical OR of integers.

@ FMinimum

FP min with llvm.minimum semantics.

@ FMaxNum

FP max with llvm.maxnum semantics including NaNs.

@ FindLastIVSMax

FindFirst reduction with select(icmp(),x,y) where one of (x,y) is a decreasing loop induction,...

@ Mul

Product of integers.

@ AnyOf

AnyOf reduction with select(cmp(),x,y) where one of (x,y) is loop invariant, and both x and y are int...

@ Xor

Bitwise or logical XOR of integers.

@ FMax

FP max implemented in terms of select(cmp()).

@ FMaximum

FP max with llvm.maximum semantics.

@ FMulAdd

Sum of float products with llvm.fmuladd(a * b + sum).

@ SMax

Signed integer max implemented in terms of select(cmp()).

@ And

Bitwise or logical AND of integers.

@ SMin

Signed integer min implemented in terms of select(cmp()).

@ FMin

FP min implemented in terms of select(cmp()).

@ FMinNum

FP min with llvm.minnum semantics including NaNs.

@ Sub

Subtraction of integers.

@ AddChainWithSubs

A chain of adds and subs.

@ FMaximumNum

FP max with llvm.maximumnum semantics.

@ UMax

Unsigned integer max implemented in terms of select(cmp()).

LLVM_ABI unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)

Return the number of times the sign bit of the register is replicated into the other bits.

decltype(auto) cast(const From &Val)

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

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

static bool isMinOrMax(SelectPatternFlavor SPF)

When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?