LoopFlatten.cpp Source File (original) (raw)

76#include

78using namespace llvm;

81#define DEBUG_TYPE "loop-flatten"

83 STATISTIC(NumFlattened, "Number of loops flattened");

87 cl::desc("Limit on the cost of instructions that can be repeated due to "

88 "loop flattening"));

93 cl::desc("Assume that the product of the two iteration "

94 "trip counts will never overflow"));

98 cl::desc("Widen the loop induction variables, if possible, so "

99 "overflow checks won't reject flattening"));

100

103 cl::desc("Version loops if flattened loop could overflow"));

104

105namespace {

106

107

108

109

110

111

112

113

114struct FlattenInfo {

115 Loop *OuterLoop = nullptr;

116 Loop *InnerLoop = nullptr;

117

118 PHINode *InnerInductionPHI = nullptr;

119 PHINode *OuterInductionPHI = nullptr;

120

121

122

123 Value *InnerTripCount = nullptr;

124 Value *OuterTripCount = nullptr;

125

126

127

129

130

131

132 BinaryOperator *InnerIncrement = nullptr;

133 BinaryOperator *OuterIncrement = nullptr;

134 BranchInst *InnerBranch = nullptr;

135

136 BranchInst *OuterBranch = nullptr;

137

138

140

141 bool Widened = false;

142

143

144 PHINode *NarrowInnerInductionPHI = nullptr;

145 PHINode *NarrowOuterInductionPHI = nullptr;

146

147

148

149 Value *NewTripCount = nullptr;

150

151 FlattenInfo(Loop *OL, Loop *IL) : OuterLoop(OL), InnerLoop(IL){};

152

153 bool isNarrowInductionPhi(PHINode *Phi) {

154

155 if (!Widened)

156 return false;

157 return NarrowInnerInductionPHI == Phi || NarrowOuterInductionPHI == Phi;

158 }

159 bool isInnerLoopIncrement(User *U) {

160 return InnerIncrement == U;

161 }

162 bool isOuterLoopIncrement(User *U) {

163 return OuterIncrement == U;

164 }

165 bool isInnerLoopTest(User *U) {

167 }

168

170 for (User *U : OuterInductionPHI->users()) {

171 if (isOuterLoopIncrement(U))

172 continue;

173

174 auto IsValidOuterPHIUses = [&] (User *U) -> bool {

175 LLVM_DEBUG(dbgs() << "Found use of outer induction variable: "; U->dump());

176 if (!ValidOuterPHIUses.count(U)) {

177 LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");

178 return false;

179 }

181 return true;

182 };

183

184 if (auto *V = dyn_cast(U)) {

185 for (auto *K : V->users()) {

186 if (!IsValidOuterPHIUses(K))

187 return false;

188 }

189 continue;

190 }

191

192 if (!IsValidOuterPHIUses(U))

193 return false;

194 }

195 return true;

196 }

197

198 bool matchLinearIVUser(User *U, Value *InnerTripCount,

200 LLVM_DEBUG(dbgs() << "Checking linear i*M+j expression for: "; U->dump());

201 Value *MatchedMul = nullptr;

202 Value *MatchedItCount = nullptr;

203

207 m_Value(MatchedItCount)));

208

209

210

211 bool IsAddTrunc =

215 m_Value(MatchedItCount)));

216

217

221 m_Value(MatchedItCount)));

222

223 if (!MatchedItCount)

224 return false;

225

226 LLVM_DEBUG(dbgs() << "Matched multiplication: "; MatchedMul->dump());

227 LLVM_DEBUG(dbgs() << "Matched iteration count: "; MatchedItCount->dump());

228

229

230

232 return !isInstructionTriviallyDead(cast(U));

233 }) > 1) {

234 LLVM_DEBUG(dbgs() << "Multiply has more than one use\n");

235 return false;

236 }

237

238

239

240 if (Widened && (IsAdd || IsGEP) &&

241 (isa(MatchedItCount) || isa(MatchedItCount))) {

243 "Unexpected type mismatch in types after widening");

244 MatchedItCount = isa(MatchedItCount)

245 ? dyn_cast(MatchedItCount)->getOperand(0)

246 : dyn_cast(MatchedItCount)->getOperand(0);

247 }

248

249 LLVM_DEBUG(dbgs() << "Looking for inner trip count: ";

250 InnerTripCount->dump());

251

252 if ((IsAdd || IsAddTrunc || IsGEP) && MatchedItCount == InnerTripCount) {

253 LLVM_DEBUG(dbgs() << "Found. This sse is optimisable\n");

254 ValidOuterPHIUses.insert(MatchedMul);

255 LinearIVUses.insert(U);

256 return true;

257 }

258

259 LLVM_DEBUG(dbgs() << "Did not match expected pattern, bailing\n");

260 return false;

261 }

262

264 Value *SExtInnerTripCount = InnerTripCount;

265 if (Widened &&

266 (isa(InnerTripCount) || isa(InnerTripCount)))

267 SExtInnerTripCount = cast(InnerTripCount)->getOperand(0);

268

269 for (User *U : InnerInductionPHI->users()) {

271 if (isInnerLoopIncrement(U)) {

272 LLVM_DEBUG(dbgs() << "Use is inner loop increment, continuing\n");

273 continue;

274 }

275

276

277

278 if (isa(U)) {

279 if (->hasOneUse())

280 return false;

281 U = *U->user_begin();

282 }

283

284

285

286

287

288 if (isInnerLoopTest(U)) {

289 LLVM_DEBUG(dbgs() << "Use is the inner loop test, continuing\n");

290 continue;

291 }

292

293 if (!matchLinearIVUser(U, SExtInnerTripCount, ValidOuterPHIUses)) {

295 return false;

296 }

298 }

299 return true;

300 }

301};

302}

303

304static bool

307 TripCount = TC;

308 IterationInstructions.insert(Increment);

309 LLVM_DEBUG(dbgs() << "Found Increment: "; Increment->dump());

311 LLVM_DEBUG(dbgs() << "Successfully found all loop components\n");

312 return true;

313}

314

315

316

317

318

319

320

326 if (isa(BackedgeTakenCount)) {

327 LLVM_DEBUG(dbgs() << "Backedge-taken count is not predictable\n");

328 return false;

329 }

330

331

332

333

334 const SCEV *SCEVTripCount =

336 BackedgeTakenCount->getType(), L);

337

339 if (SCEVRHS == SCEVTripCount)

341 ConstantInt *ConstantRHS = dyn_cast(RHS);

342 if (ConstantRHS) {

343 const SCEV *BackedgeTCExt = nullptr;

344 if (IsWidened) {

345 const SCEV *SCEVTripCountExt;

346

347

351 if (SCEVRHS != BackedgeTCExt && SCEVRHS != SCEVTripCountExt) {

352 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");

353 return false;

354 }

355 }

356

357

358 if (SCEVRHS == BackedgeTCExt || SCEVRHS == BackedgeTakenCount) {

359 Value *NewRHS = ConstantInt::get(ConstantRHS->getContext(),

360 ConstantRHS->getValue() + 1);

362 IterationInstructions);

363 }

365 }

366

367

368

369 if (!IsWidened) {

370 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");

371 return false;

372 }

373 auto *TripCountInst = dyn_cast(RHS);

374 if (!TripCountInst) {

375 LLVM_DEBUG(dbgs() << "Could not find valid trip count\n");

376 return false;

377 }

378 if ((!isa(TripCountInst) && !isa(TripCountInst)) ||

379 SE->getSCEV(TripCountInst->getOperand(0)) != SCEVTripCount) {

380 LLVM_DEBUG(dbgs() << "Could not find valid extended trip count\n");

381 return false;

382 }

384}

385

386

387

392 LLVM_DEBUG(dbgs() << "Finding components of loop: " << L->getName() << "\n");

393

394 if (!L->isLoopSimplifyForm()) {

395 LLVM_DEBUG(dbgs() << "Loop is not in normal form\n");

396 return false;

397 }

398

399

400

401 if (!L->isCanonical(*SE)) {

403 return false;

404 }

405

406

407

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

409 if (L->getExitingBlock() != Latch) {

410 LLVM_DEBUG(dbgs() << "Exiting and latch block are different\n");

411 return false;

412 }

413

414

415

416

417 InductionPHI = L->getInductionVariable(*SE);

418 if (!InductionPHI) {

419 LLVM_DEBUG(dbgs() << "Could not find induction PHI\n");

420 return false;

421 }

423

426 if (ContinueOnTrue)

428 else

430 };

431

432

433

434 ICmpInst *Compare = L->getLatchCmpInst();

435 if (!Compare || !IsValidPredicate(Compare->getUnsignedPredicate()) ||

436 Compare->hasNUsesOrMore(2)) {

437 LLVM_DEBUG(dbgs() << "Could not find valid comparison\n");

438 return false;

439 }

440 BackBranch = cast(Latch->getTerminator());

441 IterationInstructions.insert(BackBranch);

443 IterationInstructions.insert(Compare);

444 LLVM_DEBUG(dbgs() << "Found comparison: "; Compare->dump());

445

446

447

448

449

450 Increment =

452 if ((Compare->getOperand(0) != Increment || !Increment->hasNUses(2)) &&

453 !Increment->hasNUses(1)) {

454 LLVM_DEBUG(dbgs() << "Could not find valid increment\n");

455 return false;

456 }

457

458

459

460

461

462 Value *RHS = Compare->getOperand(1);

463

464 return verifyTripCount(RHS, L, IterationInstructions, InductionPHI, TripCount,

465 Increment, BackBranch, SE, IsWidened);

466}

467

469

470

471

472

473

474

475

476

477

478

479

480

481

482

484 SafeOuterPHIs.insert(FI.OuterInductionPHI);

485

486

487

488 for (PHINode &InnerPHI : FI.InnerLoop->getHeader()->phis()) {

489

490

491 if (&InnerPHI == FI.InnerInductionPHI)

492 continue;

493 if (FI.isNarrowInductionPhi(&InnerPHI))

494 continue;

495

496

497

498 assert(InnerPHI.getNumIncomingValues() == 2);

499 Value *PreHeaderValue =

500 InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopPreheader());

501 Value *LatchValue =

502 InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopLatch());

503

504

505

506

507 PHINode *OuterPHI = dyn_cast(PreHeaderValue);

508 if (!OuterPHI || OuterPHI->getParent() != FI.OuterLoop->getHeader()) {

509 LLVM_DEBUG(dbgs() << "value modified in top of outer loop\n");

510 return false;

511 }

512

513

514

515

516

517 PHINode *LCSSAPHI = dyn_cast(

519 if (!LCSSAPHI) {

521 return false;

522 }

523

524

525

528 dbgs() << "LCSSA PHI incoming value does not match latch value\n");

529 return false;

530 }

531

535 SafeOuterPHIs.insert(OuterPHI);

536 FI.InnerPHIsToTransform.insert(&InnerPHI);

537 }

538

539 for (PHINode &OuterPHI : FI.OuterLoop->getHeader()->phis()) {

540 if (FI.isNarrowInductionPhi(&OuterPHI))

541 continue;

542 if (!SafeOuterPHIs.count(&OuterPHI)) {

543 LLVM_DEBUG(dbgs() << "found unsafe PHI in outer loop: "; OuterPHI.dump());

544 return false;

545 }

546 }

547

549 return true;

550}

551

552static bool

556

557

558

559

560

562 for (auto *B : FI.OuterLoop->getBlocks()) {

563 if (FI.InnerLoop->contains(B))

564 continue;

565

566 for (auto &I : *B) {

567 if (!isa(&I) && .isTerminator() &&

569 LLVM_DEBUG(dbgs() << "Cannot flatten because instruction may have "

570 "side effects: ";

571 I.dump());

572 return false;

573 }

574

575

576

577

578 if (IterationInstructions.count(&I))

579 continue;

580

581

582 BranchInst *Br = dyn_cast(&I);

584 Br->getSuccessor(0) == FI.InnerLoop->getHeader())

585 continue;

586

587

590 continue;

594 RepeatedInstrCost += Cost;

595 }

596 }

597

598 LLVM_DEBUG(dbgs() << "Cost of instructions that will be repeated: "

599 << RepeatedInstrCost << "\n");

600

601

603 LLVM_DEBUG(dbgs() << "checkOuterLoopInsts: not profitable, bailing.\n");

604 return false;

605 }

606

608 return true;

609}

610

611

612

613

614

615

616

617

618

619

621

622

624 if (!FI.checkInnerInductionPhiUsers(ValidOuterPHIUses))

625 return false;

626

627

628

629 if (!FI.checkOuterInductionPhiUsers(ValidOuterPHIUses))

630 return false;

631

633 dbgs() << "Found " << FI.LinearIVUses.size()

634 << " value(s) that can be replaced:\n";

635 for (Value *V : FI.LinearIVUses) {

636 dbgs() << " ";

637 V->dump();

638 });

639 return true;

640}

641

642

643

646 Function *F = FI.OuterLoop->getHeader()->getParent();

648

649

651 return OverflowResult::NeverOverflows;

652

653

654

656 FI.InnerTripCount, FI.OuterTripCount,

658 FI.OuterLoop->getLoopPreheader()->getTerminator()));

659 if (OR != OverflowResult::MayOverflow)

660 return OR;

661

663 for (Value *GEPUser : GEP->users()) {

664 auto *GEPUserInst = cast(GEPUser);

665 if (!isa(GEPUserInst) &&

666 !(isa(GEPUserInst) && GEP == GEPUserInst->getOperand(1)))

667 continue;

669 continue;

670

671

672

673

674 if (GEP->isInBounds() &&

675 GEPOperand->getType()->getIntegerBitWidth() >=

676 DL.getPointerTypeSizeInBits(GEP->getType())) {

678 dbgs() << "use of linear IV would be UB if overflow occurred: ";

679 GEP->dump());

680 return true;

681 }

682 }

683 return false;

684 };

685

686

687

688 for (Value *V : FI.LinearIVUses) {

689 if (auto *GEP = dyn_cast(V))

690 if (GEP->getNumIndices() == 1 && CheckGEP(GEP, GEP->getOperand(1)))

691 return OverflowResult::NeverOverflows;

692 for (Value *U : V->users())

693 if (auto *GEP = dyn_cast(U))

694 if (CheckGEP(GEP, V))

695 return OverflowResult::NeverOverflows;

696 }

697

698 return OverflowResult::MayOverflow;

699}

700

706 FI.InnerInductionPHI, FI.InnerTripCount,

707 FI.InnerIncrement, FI.InnerBranch, SE, FI.Widened))

708 return false;

710 FI.OuterInductionPHI, FI.OuterTripCount,

711 FI.OuterIncrement, FI.OuterBranch, SE, FI.Widened))

712 return false;

713

714

715

716 if (!FI.OuterLoop->isLoopInvariant(FI.InnerTripCount)) {

717 LLVM_DEBUG(dbgs() << "inner loop trip count not invariant\n");

718 return false;

719 }

720 if (!FI.OuterLoop->isLoopInvariant(FI.OuterTripCount)) {

721 LLVM_DEBUG(dbgs() << "outer loop trip count not invariant\n");

722 return false;

723 }

724

726 return false;

727

728

729 if (FI.InnerInductionPHI->getType() != FI.OuterInductionPHI->getType())

730 return false;

731

733 return false;

734

735

736

737

738

739

741 return false;

742

744 return true;

745}

746

751 Function *F = FI.OuterLoop->getHeader()->getParent();

752 LLVM_DEBUG(dbgs() << "Checks all passed, doing the transformation\n");

753 {

754 using namespace ore;

756 FI.InnerLoop->getHeader());

758 Remark << "Flattened into outer loop";

760 }

761

762 if (!FI.NewTripCount) {

763 FI.NewTripCount = BinaryOperator::CreateMul(

764 FI.InnerTripCount, FI.OuterTripCount, "flatten.tripcount",

765 FI.OuterLoop->getLoopPreheader()->getTerminator()->getIterator());

766 LLVM_DEBUG(dbgs() << "Created new trip count in preheader: ";

767 FI.NewTripCount->dump());

768 }

769

770

771

772 FI.InnerInductionPHI->removeIncomingValue(FI.InnerLoop->getLoopLatch());

773

774

775

776 for (PHINode *PHI : FI.InnerPHIsToTransform)

777 PHI->removeIncomingValue(FI.InnerLoop->getLoopLatch());

778

779

780

781 cast(FI.OuterBranch->getCondition())->setOperand(1, FI.NewTripCount);

782

783

784 BasicBlock *InnerExitBlock = FI.InnerLoop->getExitBlock();

785 BasicBlock *InnerExitingBlock = FI.InnerLoop->getExitingBlock();

789 Term->eraseFromParent();

790

791

792 DT->deleteEdge(InnerExitingBlock, FI.InnerLoop->getHeader());

793 if (MSSAU)

794 MSSAU->removeEdge(InnerExitingBlock, FI.InnerLoop->getHeader());

795

796

797

798 IRBuilder<> Builder(FI.OuterInductionPHI->getParent()->getTerminator());

799 for (Value *V : FI.LinearIVUses) {

800 Value *OuterValue = FI.OuterInductionPHI;

801 if (FI.Widened)

802 OuterValue = Builder.CreateTrunc(FI.OuterInductionPHI, V->getType(),

803 "flatten.trunciv");

804

805 if (auto *GEP = dyn_cast(V)) {

806

807 auto *InnerGEP = cast(GEP->getOperand(0));

808 Value *Base = InnerGEP->getOperand(0);

809

810

813 OuterValue =

814 Builder.CreateGEP(GEP->getSourceElementType(), Base, OuterValue,

815 "flatten." + V->getName(),

816 GEP->isInBounds() && InnerGEP->isInBounds());

817 }

818

820 OuterValue->dump());

821 V->replaceAllUsesWith(OuterValue);

822 }

823

824

825

828 if (U)

829 U->markLoopAsDeleted(*FI.InnerLoop, FI.InnerLoop->getName());

830 LI->erase(FI.InnerLoop);

831

832

833 NumFlattened++;

834

835 return true;

836}

837

842 LLVM_DEBUG(dbgs() << "Widening the IVs is disabled\n");

843 return false;

844 }

845

847 Module *M = FI.InnerLoop->getHeader()->getParent()->getParent();

848 auto &DL = M->getDataLayout();

849 auto *InnerType = FI.InnerInductionPHI->getType();

850 auto *OuterType = FI.OuterInductionPHI->getType();

851 unsigned MaxLegalSize = DL.getLargestLegalIntTypeSizeInBits();

852 auto *MaxLegalType = DL.getLargestLegalIntType(M->getContext());

853

854

855

856

857 if (InnerType != OuterType ||

858 InnerType->getScalarSizeInBits() >= MaxLegalSize ||

859 MaxLegalType->getScalarSizeInBits() <

860 InnerType->getScalarSizeInBits() * 2) {

862 return false;

863 }

864

867 unsigned ElimExt = 0;

868 unsigned Widened = 0;

869

870 auto CreateWideIV = [&](WideIVInfo WideIV, bool &Deleted) -> bool {

873 true , true );

874 if (!WidePhi)

875 return false;

879 return true;

880 };

881

883 if (!CreateWideIV({FI.InnerInductionPHI, MaxLegalType, false}, Deleted))

884 return false;

885

886

888 FI.InnerPHIsToTransform.insert(FI.InnerInductionPHI);

889

890 if (!CreateWideIV({FI.OuterInductionPHI, MaxLegalType, false}, Deleted))

891 return false;

892

893 assert(Widened && "Widened IV expected");

894 FI.Widened = true;

895

896

897 FI.NarrowInnerInductionPHI = FI.InnerInductionPHI;

898 FI.NarrowOuterInductionPHI = FI.OuterInductionPHI;

899

900

902}

903

910 dbgs() << "Loop flattening running on outer loop "

911 << FI.OuterLoop->getHeader()->getName() << " and inner loop "

912 << FI.InnerLoop->getHeader()->getName() << " in "

913 << FI.OuterLoop->getHeader()->getParent()->getName() << "\n");

914

916 return false;

917

918

919 bool CanFlatten = CanWidenIV(FI, DT, LI, SE, AC, TTI);

920

921

922

923

924

925

926

927

928

929

930

931

932 if (FI.Widened && !CanFlatten)

933 return true;

934

935

936 if (CanFlatten)

938

939

940

941

942

944 if (OR == OverflowResult::AlwaysOverflowsHigh ||

945 OR == OverflowResult::AlwaysOverflowsLow) {

946 LLVM_DEBUG(dbgs() << "Multiply would always overflow, so not profitable\n");

947 return false;

948 } else if (OR == OverflowResult::MayOverflow) {

949 Module *M = FI.OuterLoop->getHeader()->getParent()->getParent();

952 LLVM_DEBUG(dbgs() << "Multiply might overflow, not flattening\n");

953 return false;

954 } else if (.isLegalInteger(

955 FI.OuterTripCount->getType()->getScalarSizeInBits())) {

956

957

958

960 dbgs() << "Can't check overflow efficiently, not flattening\n");

961 return false;

962 }

963 LLVM_DEBUG(dbgs() << "Multiply might overflow, versioning loop\n");

964

965

966

967

968 BasicBlock *CheckBlock = FI.OuterLoop->getLoopPreheader();

970 LoopVersioning LVer(LAI, Checks, FI.OuterLoop, LI, DT, SE);

972

973

974

977 "Expected LoopVersioning to generate a conditional branch");

979 "Expected branch condition to be false");

982 Intrinsic::umul_with_overflow, FI.OuterTripCount->getType(),

983 {FI.OuterTripCount, FI.InnerTripCount},

984 nullptr, "flatten.mul");

985 FI.NewTripCount = Builder.CreateExtractValue(Call, 0, "flatten.tripcount");

988 } else {

989 LLVM_DEBUG(dbgs() << "Multiply cannot overflow, modifying loop in-place\n");

990 }

991

993}

994

998

999 bool Changed = false;

1000

1001 std::optional MSSAU;

1002 if (AR.MSSA) {

1006 }

1007

1008

1009

1010

1011

1015 if (!OuterLoop)

1016 continue;

1017 FlattenInfo FI(OuterLoop, InnerLoop);

1018 Changed |=

1020 MSSAU ? &*MSSAU : nullptr, LAIM.getInfo(*OuterLoop));

1021 }

1022

1023 if (!Changed)

1025

1028

1030 if (AR.MSSA)

1032 return PA;

1033}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

Module.h This file contains the declarations for the Module class.

static bool CanWidenIV(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)

static bool verifyTripCount(Value *RHS, Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)

static cl::opt< bool > WidenIV("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))

static bool setLoopComponents(Value *&TC, Value *&TripCount, BinaryOperator *&Increment, SmallPtrSetImpl< Instruction * > &IterationInstructions)

static bool DoFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)

static bool FlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU, const LoopAccessInfo &LAI)

static bool checkIVUsers(FlattenInfo &FI)

static bool CanFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)

static cl::opt< bool > VersionLoops("loop-flatten-version-loops", cl::Hidden, cl::init(true), cl::desc("Version loops if flattened loop could overflow"))

static bool findLoopComponents(Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)

static OverflowResult checkOverflow(FlattenInfo &FI, DominatorTree *DT, AssumptionCache *AC)

static bool checkPHIs(FlattenInfo &FI, const TargetTransformInfo *TTI)

static cl::opt< unsigned > RepeatedInstructionThreshold("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening"))

static cl::opt< bool > AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow"))

static bool checkOuterLoopInsts(FlattenInfo &FI, SmallPtrSetImpl< Instruction * > &IterationInstructions, const TargetTransformInfo *TTI)

This file defines the interface for the loop nest analysis.

This header provides classes for managing a pipeline of passes over loops in LLVM IR.

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

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

This pass exposes codegen information to IR-level passes.

Virtual Register Rewriter

A container for analyses that lazily runs them and caches their results.

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

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

LLVM Basic Block Representation.

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

Conditional or Unconditional Branch instruction.

void setCondition(Value *V)

bool isConditional() const

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

Value * getCondition() const

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_ULT

unsigned less than

This is the shared class of boolean and integer constants.

const APInt & getValue() const

Return the constant as an APInt value reference.

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

void deleteEdge(NodeT *From, NodeT *To)

Inform the dominator tree about a CFG edge deletion and update the tree.

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.

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

This instruction compares its operands according to the predicate given to the constructor.

Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")

BasicBlock::iterator GetInsertPoint() const

Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())

CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")

Create a call to intrinsic ID with Args, mangled using Types.

Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

const LoopAccessInfo & getInfo(Loop &L)

Drive the analysis of memory accesses in the loop.

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

PreservedAnalyses run(LoopNest &LN, LoopAnalysisManager &LAM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

This class represents a loop nest and can be used to query its properties.

ArrayRef< Loop * > getLoops() const

Get the loops in the nest.

This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...

void versionLoop()

Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

void removeEdge(BasicBlock *From, BasicBlock *To)

Update the MemoryPhi in To following an edge deletion between From and To.

void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const

Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...

A Module instance is used to store all the information related to an LLVM module.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

Value * hasConstantValue() const

If the specified PHI node always merges together the same value, return the value,...

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 uses information about analyze scalars to rewrite expressions in canonical form.

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 * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)

If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...

const SCEV * getSCEV(Value *V)

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

const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)

A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...

void forgetLoop(const Loop *L)

This method should be called by the client when it has changed a loop in a way that may effect Scalar...

const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

void forgetBlockAndLoopDispositions(Value *V=nullptr)

Called when the client has changed the disposition of values in a loop or block.

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 is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

@ TCK_SizeAndLatency

The weighted sum of size and latency.

InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const

Estimate the cost of a given IR user when lowered.

LLVM Value Representation.

Type * getType() const

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

iterator_range< user_iterator > users()

LLVMContext & getContext() const

All values hold a context through their type.

void dump() const

Support for debugging, callable in GDB: V->dump()

const ParentTy * getParent() const

CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)

Matches Trunc.

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

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

auto m_GEP(const OperandTypes &...Ops)

Matches GetElementPtrInst.

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

Matches a Add with LHS and RHS in either order.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

is_zero m_Zero()

Match any null constant or a vector with all elements equal to 0.

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

Matches a Mul with LHS and RHS in either order.

initializer< Ty > init(const Ty &Val)

NodeAddr< PhiNode * > Phi

This is an optimization pass for GlobalISel generic memory operations.

PHINode * createWideIV(const WideIVInfo &WI, LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter, DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, unsigned &NumElimExt, unsigned &NumWidened, bool HasGuards, bool UsePostIncrementRanges)

Widen Induction Variables - Extend the width of an IV to cover its widest uses.

bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)

Return true if this function can prove that the instruction I is executed for every iteration of the ...

OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ, bool IsNSW=false)

raw_ostream & dbgs()

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

bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

bool VerifyMemorySSA

Enables verification of MemorySSA.

auto count_if(R &&Range, UnaryPredicate P)

Wrapper function around std::count_if to count the number of times an element satisfying a given pred...

PreservedAnalyses getLoopPassPreservedAnalyses()

Returns the minimum set of Analyses that all loop passes must preserve.

bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)

If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...

TargetTransformInfo & TTI

Collect information about induction variables that are used by sign/zero extend operations.