IVDescriptors.cpp Source File (original) (raw)

26using namespace llvm;

29#define DEBUG_TYPE "iv-descriptors"

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

34 if (!Set.count(dyn_cast(Use)))

35 return false;

36 return true;

37}

40 switch (Kind) {

41 default:

42 break;

56 return true;

57 }

58 return false;

59}

63}

72 if (!Phi->hasOneUse())

73 return Phi;

75 const APInt *M = nullptr;

76 Instruction *I, *J = cast(Phi->use_begin()->getUser());

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

82 if (Bits > 0) {

86 return J;

87 }

88 }

89 return Phi;

90}

98 bool IsSigned = false;

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

101

102 if (DB) {

103

104

105

106

107

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

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

110 }

111

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

113

114

115

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

118 MaxBitWidth = NumTypeBits - NumSignBits;

120 if (!Bits.isNonNegative()) {

121

122

123

124 IsSigned = true;

125

126

127 ++MaxBitWidth;

128 }

129 }

131

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

133 IsSigned);

134}

135

136

137

138

139

141 Type *RecurrenceType,

143 unsigned &MinWidthCastToRecurTy) {

144

148 MinWidthCastToRecurTy = -1U;

149

150 while (!Worklist.empty()) {

153 if (auto *Cast = dyn_cast(Val)) {

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

155

156

157

159 continue;

160 }

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

162

163

164

165

166 MinWidthCastToRecurTy = std::min(

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

168 continue;

169 }

170 }

171

172

173 for (Value *O : cast(Val)->operands())

174 if (auto *I = dyn_cast(O))

177 }

178}

179

180

181

184

186 return false;

187

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

189 return false;

190

193 return false;

194

195

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

197 return false;

198

199

200

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

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

204 return false;

206 return false;

207

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

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

210

211 return true;

212}

213

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

219 return false;

220

221

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

223 return false;

224

225

226

228

229

230

231

232

234

235

236

237

239

240

241 bool FoundReduxOp = false;

242

243

244

245

246

247 bool FoundStartPHI = false;

248

249

250

251

252 unsigned NumCmpSelectPatternInst = 0;

253 InstDesc ReduxDesc(false, nullptr);

254

255

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

258 unsigned MinWidthCastToRecurrenceType;

260 bool IsSigned = false;

261

264

265

266

267

268

269

272 return false;

273 } else if (RecurrenceType->isIntegerTy()) {

275 return false;

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

278 } else {

279

280 return false;

281 }

282

284 VisitedInsts.insert(Start);

285

286

287

289

290

291

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313 while (!Worklist.empty()) {

315

316

317

318 if (auto *SI = dyn_cast(Cur)) {

319 if (!SE) {

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

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

322 return false;

323 }

324

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

326

328 const SCEV *OtherScev =

330

331 if (OtherScev != PtrScev) {

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

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

334 << " and "

336 return false;

337 }

338 }

339

340

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

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

344 << '\n');

345 return false;

346 }

347

348

350 continue;

351 }

352

353

354

355

357 return false;

358

359 bool IsAPhi = isa(Cur);

360

361

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

363 return false;

364

365

366

367 if (!Cur->isCommutative() && !IsAPhi && !isa(Cur) &&

368 !isa(Cur) && !isa(Cur) &&

369 !VisitedInsts.count(dyn_cast(Cur->getOperand(0))))

370 return false;

371

372

373

374

375 if (Cur != Start) {

376 ReduxDesc =

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

378 ExactFPMathInst = ExactFPMathInst == nullptr

380 : ExactFPMathInst;

382 return false;

383

384 if (isa(ReduxDesc.getPatternInst()) && !IsAPhi) {

386 if (auto *Sel = dyn_cast(ReduxDesc.getPatternInst())) {

387

388

389

390

391 if (auto *FCmp = dyn_cast(Sel->getCondition()))

392 CurFMF |= FCmp->getFastMathFlags();

393 }

394 FMF &= CurFMF;

395 }

396

397

398

401 }

402

403 bool IsASelect = isa(Cur);

404

405

406

409 return false;

410

411

414 return false;

415

416

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

418 return false;

419

421 (isa(Cur) || isa(Cur)))

422 ++NumCmpSelectPatternInst;

424 (isa(Cur) || isa(Cur)))

425 ++NumCmpSelectPatternInst;

426

427

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

429

430

431

432

437

438

439

442 return false;

443

444

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

447

448

449 if (ExitInstruction == Cur)

450 continue;

451

452

453

454

455

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

457 return false;

458

459

460

461

463 return false;

464

465 ExitInstruction = Cur;

466 continue;

467 }

468

469

470

471

472 InstDesc IgnoredVal(false, nullptr);

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

474 if (isa(UI)) {

476 } else {

477 StoreInst *SI = dyn_cast(UI);

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

479

480

481 return false;

482 }

484 }

485 } else if (!isa(UI) &&

486 ((!isa(UI) && !isa(UI) &&

487 !isa(UI)) ||

490 .isRecurrence() &&

492 return false;

493

494

495 if (UI == Phi)

496 FoundStartPHI = true;

497 }

500 }

501

502

503

504

506 NumCmpSelectPatternInst != 0)

507 return false;

508

510 return false;

511

513

514

515

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

519 return false;

520 }

521

522

523

524 if (ExitInstruction &&

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

527 "store last calculated value of the reduction: "

529 return false;

530 }

531

532

533

534 if (!ExitInstruction)

536 }

537

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

539 return false;

540

541 const bool IsOrdered =

543

544 if (Start != Phi) {

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569 Type *ComputedType;

570 std::tie(ComputedType, IsSigned) =

572 if (ComputedType != RecurrenceType)

573 return false;

574 }

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589 collectCastInstrs(TheLoop, ExitInstruction, RecurrenceType, CastInsts,

590 MinWidthCastToRecurrenceType);

591

592

593

594

595

596

597

598

600 FMF, ExactFPMathInst, RecurrenceType, IsSigned,

601 IsOrdered, CastInsts, MinWidthCastToRecurrenceType);

602 RedDes = RD;

603

604 return true;

605}

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

631

632

635 if (auto *Select = dyn_cast(*I->user_begin()))

637 }

638

642

644 Value *NonPhi = nullptr;

645

646 if (OrigPhi == dyn_cast(SI->getTrueValue()))

647 NonPhi = SI->getFalseValue();

648 else if (OrigPhi == dyn_cast(SI->getFalseValue()))

649 NonPhi = SI->getTrueValue();

650 else

652

653

654

655

658

661}

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

693

694

695

696

699

700

701 Value *NonRdxPhi = nullptr;

707

708 auto IsIncreasingLoopInduction = [&](Value *V) {

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

711 return false;

712

713 auto *AR = dyn_cast(SE.getSCEV(V));

714 if (!AR || AR->getLoop() != TheLoop)

715 return false;

716

717 const SCEV *Step = AR->getStepRecurrence(SE);

719 return false;

720

723

724

725

726

727

728

729

733 LLVM_DEBUG(dbgs() << "LV: FindLastIV valid range is " << ValidRange

734 << ", and the signed range of " << *AR << " is "

735 << IVRange << "\n");

736

737

738 return ValidRange.contains(IVRange);

739 };

740

741

742

743

744

745 if (!IsIncreasingLoopInduction(NonRdxPhi))

747

750}

751

755 assert((isa(I) || isa(I) || isa(I)) &&

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

759

760

761

764 if (auto *Select = dyn_cast(*I->user_begin()))

766 }

767

768

769 if (!isa(I) &&

773

774

795

797}

798

799

800

801

802

803

804

805

806

807

810 SelectInst *SI = dyn_cast(I);

811 if (!SI)

813

814 CmpInst *CI = dyn_cast(SI->getCondition());

815

818

819 Value *TrueVal = SI->getTrueValue();

820 Value *FalseVal = SI->getFalseValue();

821

822

823 if ((isa(TrueVal) && isa(FalseVal)) ||

824 (!isa(TrueVal) && !isa(FalseVal)))

826

827 Instruction *I1 = isa(TrueVal) ? dyn_cast(FalseVal)

828 : dyn_cast(TrueVal);

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

831

832 Value *Op1, *Op2;

835 I1->isFast()) ||

841

842 Instruction *IPhi = isa(Op1) ? dyn_cast(Op1)

843 : dyn_cast(Op2);

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

846

848}

849

854 switch (I->getOpcode()) {

855 default:

857 case Instruction::PHI:

859 case Instruction::Sub:

860 case Instruction::Add:

862 case Instruction::Mul:

864 case Instruction::And:

866 case Instruction::Or:

868 case Instruction::Xor:

870 case Instruction::FDiv:

871 case Instruction::FMul:

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

874 case Instruction::FSub:

875 case Instruction::FAdd:

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

878 case Instruction::Select:

884 [[fallthrough]];

885 case Instruction::FCmp:

886 case Instruction::ICmp:

887 case Instruction::Call:

890 auto HasRequiredFMF = [&]() {

892 return true;

893 if (isa(I) && I->hasNoNaNs() && I->hasNoSignedZeros())

894 return true;

895

896

899 };

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

907 }

908}

909

912 unsigned MaxNumUses) {

913 unsigned NumUses = 0;

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

915 if (Insts.count(dyn_cast(U)))

916 ++NumUses;

917 if (NumUses > MaxNumUses)

918 return true;

919 }

920

921 return false;

922}

923

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

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

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

936

938 SE)) {

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

940 return true;

941 }

943 SE)) {

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

945 return true;

946 }

948 SE)) {

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

950 return true;

951 }

953 SE)) {

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

955 return true;

956 }

958 SE)) {

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

960 return true;

961 }

963 SE)) {

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

965 return true;

966 }

968 SE)) {

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

970 return true;

971 }

973 SE)) {

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

975 return true;

976 }

978 SE)) {

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

980 return true;

981 }

983 SE)) {

984 LLVM_DEBUG(dbgs() << "Found an integer conditional select reduction PHI."

985 << *Phi << "\n");

986 return true;

987 }

989 DT, SE)) {

992 ? "F"

993 : "I")

994 << "FindLastIV reduction PHI." << *Phi << "\n");

995 return true;

996 }

998 SE)) {

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

1000 return true;

1001 }

1003 SE)) {

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

1005 return true;

1006 }

1008 SE)) {

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

1010 return true;

1011 }

1013 SE)) {

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

1015 return true;

1016 }

1018 SE)) {

1019 LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI."

1020 << " PHI." << *Phi << "\n");

1021 return true;

1022 }

1024 SE)) {

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

1026 return true;

1027 }

1029 SE)) {

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

1031 return true;

1032 }

1034 SE)) {

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

1036 return true;

1037 }

1038

1039 return false;

1040}

1041

1044

1045

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

1047 Phi->getNumIncomingValues() != 2)

1048 return false;

1049

1050

1051

1054 if (!Preheader || !Latch)

1055 return false;

1056

1057

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

1059 Phi->getBasicBlockIndex(Latch) < 0)

1060 return false;

1061

1062

1063

1064 auto *Previous = dyn_cast(Phi->getIncomingValueForBlock(Latch));

1065

1066

1067

1068

1069

1071 while (auto *PrevPhi = dyn_cast_or_null(Previous)) {

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

1073 return false;

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

1075 return false;

1076 Previous = dyn_cast(PrevPhi->getIncomingValueForBlock(Latch));

1077 }

1078

1079 if (!Previous || !TheLoop->contains(Previous) || isa(Previous))

1080 return false;

1081

1082

1083

1084

1085

1086

1087

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

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

1092

1093 if (Previous == SinkCandidate)

1094 return false;

1095

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

1097 return true;

1099 SinkCandidate))

1100 return true;

1101

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

1103 SinkCandidate->mayHaveSideEffects() ||

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

1105 return false;

1106

1107

1108

1109 if (isa(SinkCandidate))

1110 return true;

1111

1112

1113 WorkList.push_back(SinkCandidate);

1114 return true;

1115 };

1116

1118

1119 while (!WorkList.empty()) {

1122 if (!TryToPushSinkCandidate(cast(User)))

1123 return false;

1124 }

1125 }

1126

1127 return true;

1128}

1129

1131 switch (Kind) {

1133 return Instruction::Add;

1135 return Instruction::Mul;

1137 return Instruction::Or;

1139 return Instruction::And;

1141 return Instruction::Xor;

1143 return Instruction::FMul;

1146 return Instruction::FAdd;

1153 return Instruction::ICmp;

1160 return Instruction::FCmp;

1161 default:

1163 }

1164}

1165

1170

1171

1172

1173

1174

1175

1176

1177

1178

1179

1180

1181

1182

1183

1184

1185

1186 unsigned ExpectedUses = 1;

1187 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp)

1188 ExpectedUses = 2;

1189

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

1193 if (isa(UI))

1194 continue;

1195 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {

1196

1197

1198 if (isa(UI))

1199 return UI;

1200 continue;

1201 }

1202 return UI;

1203 }

1204 return nullptr;

1205 };

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

1207 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) {

1211 }

1212

1214 return true;

1215

1216 return Cur->getOpcode() == RedOp;

1217 };

1218

1219

1220 unsigned ExtraPhiUses = 0;

1222 if (auto ExitPhi = dyn_cast(LoopExitInstr)) {

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

1224 return {};

1225

1226 Instruction *Inc0 = dyn_cast(ExitPhi->getIncomingValue(0));

1227 Instruction *Inc1 = dyn_cast(ExitPhi->getIncomingValue(1));

1228

1230 if (Inc0 == Phi)

1231 Chain = Inc1;

1232 else if (Inc1 == Phi)

1233 Chain = Inc0;

1234 else

1235 return {};

1236

1237 RdxInstr = Chain;

1238 ExtraPhiUses = 1;

1239 }

1240

1241

1242

1243

1244

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

1246 return {};

1247

1248

1249

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

1251 return {};

1252

1253 Instruction *Cur = getNextInstruction(Phi);

1254

1255

1256

1257 while (Cur != RdxInstr) {

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

1259 return {};

1260

1261 ReductionOperations.push_back(Cur);

1262 Cur = getNextInstruction(Cur);

1263 }

1264

1265 ReductionOperations.push_back(Cur);

1266 return ReductionOperations;

1267}

1268

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

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

1274

1275

1276

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

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

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

1282

1283

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

1285 "Step value is zero");

1286

1288 "StepValue is not an integer");

1289

1291 "StepValue is not FP for FpInduction");

1292 assert((IK != IK_FpInduction ||

1293 (InductionBinOp &&

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

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

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

1297

1298 if (Casts) {

1299 for (auto &Inst : *Casts) {

1300 RedundantCasts.push_back(Inst);

1301 }

1302 }

1303}

1304

1306 if (isa(Step))

1307 return dyn_cast(cast(Step)->getValue());

1308 return nullptr;

1309}

1310

1314

1315

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

1317

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

1319 return false;

1320

1321

1322

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

1324 return false;

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

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

1327 BEValue = Phi->getIncomingValue(0);

1328 StartValue = Phi->getIncomingValue(1);

1329 } else {

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

1331 "Unexpected Phi node in the loop");

1332 BEValue = Phi->getIncomingValue(1);

1333 StartValue = Phi->getIncomingValue(0);

1334 }

1335

1336 BinaryOperator *BOp = dyn_cast(BEValue);

1337 if (!BOp)

1338 return false;

1339

1340 Value *Addend = nullptr;

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

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

1349

1350 if (!Addend)

1351 return false;

1352

1353

1354 if (auto *I = dyn_cast(Addend))

1356 return false;

1357

1358

1361 return true;

1362}

1363

1364

1365

1366

1367

1368

1369

1370

1371

1372

1373

1374

1375

1376

1377

1378

1379

1380

1381

1382

1383

1384

1385

1386

1387

1388

1389

1390

1391

1392

1393

1394

1395

1400

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

1402 auto *PN = cast(PhiScev->getValue());

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

1405

1406

1407

1408

1409

1410

1411

1412

1413

1414 auto getDef = [&](const Value *Val) -> Value * {

1415 const BinaryOperator *BinOp = dyn_cast(Val);

1416 if (!BinOp)

1417 return nullptr;

1420 Value *Def = nullptr;

1421 if (L->isLoopInvariant(Op0))

1422 Def = Op1;

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

1424 Def = Op0;

1425 return Def;

1426 };

1427

1428

1429

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

1431 if (!Latch)

1432 return false;

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

1434 if (!Val)

1435 return false;

1436

1437

1438

1439

1440

1441 bool InCastSequence = false;

1442 auto *Inst = dyn_cast(Val);

1443 while (Val != PN) {

1444

1445

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

1447 return false;

1448 }

1449 auto *AddRec = dyn_cast(PSE.getSCEV(Val));

1451 InCastSequence = true;

1452 if (InCastSequence) {

1453

1454

1455 if (!CastInsts.empty())

1456 if (!Inst->hasOneUse())

1457 return false;

1459 }

1460 Val = getDef(Val);

1461 if (!Val)

1462 return false;

1463 Inst = dyn_cast(Val);

1464 }

1465

1466 return InCastSequence;

1467}

1468

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

1473

1474

1475

1476

1477

1480 return false;

1481

1484

1486 const auto *AR = dyn_cast(PhiScev);

1487

1488

1489 if (Assume && !AR)

1491

1492 if (!AR) {

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

1494 return false;

1495 }

1496

1497

1498 const auto *SymbolicPhi = dyn_cast(PhiScev);

1499

1500

1501

1502

1503

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

1508 }

1509

1511}

1512

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

1518

1520 return false;

1521

1522

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

1524 const SCEVAddRecExpr *AR = dyn_cast(PhiScev);

1525

1526 if (!AR) {

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

1528 return false;

1529 }

1530

1531 if (AR->getLoop() != TheLoop) {

1532

1533

1535 dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");

1536 return false;

1537 }

1538

1539

1540

1541

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

1544

1545 Value *StartValue =

1547

1549 if (!Latch)

1550 return false;

1551

1553

1554

1555 const SCEVConstant *ConstStep = dyn_cast(Step);

1557 return false;

1558

1561 dyn_cast(Phi->getIncomingValueForBlock(Latch));

1563 CastsToIgnore);

1564 return true;

1565 }

1566

1568

1569

1571 return true;

1572}

AMDGPU Register Bank Select

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

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

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

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

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

Determines if Phi may have been type-promoted.

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

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

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

Class for arbitrary precision integers.

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 class is the base class for the comparison instructions.

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

This is the shared class of boolean and integer constants.

This class represents a range of values.

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.

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 setNoSignedZeros(bool B=true)

void setNoNaNs(bool B=true)

static FastMathFlags getFast()

A struct for saving information about induction variables.

@ IK_FpInduction

Floating point induction variable.

@ IK_PtrInduction

Pointer induction var. Step = C.

@ IK_IntInduction

Integer induction variable. Step = C.

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

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

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

InductionDescriptor()=default

Default constructor - creates an invalid induction.

ConstantInt * getConstIntStepValue() const

bool isCommutative() const LLVM_READONLY

Return true if the instruction is commutative:

FastMathFlags getFastMathFlags() const LLVM_READONLY

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

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

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

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

const SCEVAddRecExpr * getAsAddRec(Value *V)

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

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 isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, DominatorTree *DT)

Returns true if Phi is a fixed-order recurrence.

unsigned getOpcode() const

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

Returns true if instruction I has multiple uses in Insts.

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

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

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

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

static bool isAnyOfRecurrenceKind(RecurKind Kind)

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

static InstDesc isFindLastIVPattern(Loop *TheLoop, PHINode *OrigPhi, Instruction *I, ScalarEvolution &SE)

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

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

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

static bool isFindLastIVRecurrenceKind(RecurKind Kind)

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

static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I)

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

RecurKind getRecurrenceKind() const

StoreInst * IntermediateStore

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

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

static bool isFloatingPointRecurrenceKind(RecurKind Kind)

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

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

Returns a struct describing if the instruction is a llvm.

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

static bool isIntegerRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is an integer kind.

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 SCEV * getStepRecurrence(ScalarEvolution &SE) const

Constructs and returns the recurrence indicating how much this expression steps by.

const Loop * getLoop() const

This class represents a constant integer value.

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.

Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

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.

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

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

bool isKnownPositive(const SCEV *S)

Test if the given expression is known to be positive.

bool isSCEVable(Type *Ty) const

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

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.

Value * getValueOperand()

Value * getPointerOperand()

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

unsigned getIntegerBitWidth() const

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.

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

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.

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

Value * getOperand(unsigned i) const

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

bool hasOneUse() const

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

iterator_range< user_iterator > users()

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.

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)

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.

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

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

Matches SelectInst.

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)

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)

OneUse_match< T > m_OneUse(const T &SubPattern)

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.

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)

apint_match m_APInt(const APInt *&Res)

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

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

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.

This is an optimization pass for GlobalISel generic memory operations.

T bit_ceil(T Value)

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

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

raw_ostream & dbgs()

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

RecurKind

These are the kinds of recurrences that we support.

@ UMin

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

@ IFindLastIV

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

@ FAnyOf

Any_of reduction with select(fcmp(),x,y) where one of (x,y) is loop invariant, and both x and y are i...

@ Or

Bitwise or logical OR of integers.

@ FMinimum

FP min with llvm.minimum semantics.

@ Mul

Product of integers.

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

@ FFindLastIV

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

@ SMin

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

@ FMin

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

@ IAnyOf

Any_of reduction with select(icmp(),x,y) where one of (x,y) is loop invariant, and both x and y are i...

@ UMax

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

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

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

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

Returns true if Element is found in Range.

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

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

static bool isMinOrMax(SelectPatternFlavor SPF)

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