LoopInterchange.cpp Source File (original) (raw)

46#include

47#include

48#include

50using namespace llvm;

52#define DEBUG_TYPE "loop-interchange"

54 STATISTIC(LoopsInterchanged, "Number of loops interchanged");

58 cl::desc("Interchange if you gain more than this number"));

64 "Maximum number of load-store instructions that should be handled "

65 "in the dependency matrix. Higher value may lead to more interchanges "

66 "at the cost of compile-time"));

68namespace {

73using CharMatrix = std::vector<std::vector>;

75}

80 cl::desc("Minimum depth of loop nest considered for the transform"));

85 cl::desc("Maximum depth of loop nest considered for the transform"));

87#ifndef NDEBUG

89 for (auto &Row : DepMatrix) {

90 for (auto D : Row)

93 }

94}

95#endif

102

103 ValueVector MemInstr;

104

105

107

109 if (!isa(I))

110 return false;

111 if (auto *Ld = dyn_cast(&I)) {

112 if (!Ld->isSimple())

113 return false;

115 } else if (auto *St = dyn_cast(&I)) {

116 if (!St->isSimple())

117 return false;

118 MemInstr.push_back(&I);

119 }

120 }

121 }

122

124 << " Loads and Stores to analyze\n");

126 LLVM_DEBUG(dbgs() << "The transform doesn't support more than "

128 ORE->emit([&]() {

130 L->getStartLoc(), L->getHeader())

131 << "Number of loads/stores exceeded, the supported maximum "

132 "can be increased with option "

133 "-loop-interchange-maxmeminstr-count.";

134 });

135 return false;

136 }

137 ValueVector::iterator I, IE, J, JE;

139

140 for (I = MemInstr.begin(), IE = MemInstr.end(); I != IE; ++I) {

141 for (J = I, JE = MemInstr.end(); J != JE; ++J) {

142 std::vector Dep;

144 Instruction *Dst = cast(*J);

145

146 if (isa(Src) && isa(Dst))

147 continue;

148

149 if (auto D = DI->depends(Src, Dst, true)) {

150 assert(D->isOrdered() && "Expected an output, flow or anti dep.");

151

152

153 if (D->normalize(SE))

154 LLVM_DEBUG(dbgs() << "Negative dependence vector normalized.\n");

156 D->isFlow() ? "flow" : D->isAnti() ? "anti" : "output";

157 dbgs() << "Found " << DepType

158 << " dependency between Src and Dst\n"

159 << " Src:" << *Src << "\n Dst:" << *Dst << '\n');

160 unsigned Levels = D->getLevels();

162 for (unsigned II = 1; II <= Levels; ++II) {

163 unsigned Dir = D->getDirection(II);

171 else

174 }

175 while (Dep.size() != Level) {

176 Dep.push_back('I');

177 }

178

179

180 if (Seen.insert(StringRef(Dep.data(), Dep.size())).second)

181 DepMatrix.push_back(Dep);

182 }

183 }

184 }

185

186 return true;

187}

188

189

190

192 unsigned ToIndx) {

193 for (unsigned I = 0, E = DepMatrix.size(); I < E; ++I)

194 std::swap(DepMatrix[I][ToIndx], DepMatrix[I][FromIndx]);

195}

196

197

198

199

200

202 for (unsigned char Direction : DV) {

204 return true;

206 return false;

207 }

208 return true;

209}

210

211

213 unsigned InnerLoopId,

214 unsigned OuterLoopId) {

215 unsigned NumRows = DepMatrix.size();

216 std::vector Cur;

217

218 for (unsigned Row = 0; Row < NumRows; ++Row) {

219

220

221 Cur = DepMatrix[Row];

223 return false;

224 std::swap(Cur[InnerLoopId], Cur[OuterLoopId]);

226 return false;

227 }

228 return true;

229}

230

232 LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "

233 << L.getHeader()->getParent()->getName() << " Loop: %"

234 << L.getHeader()->getName() << '\n');

235 assert(LoopList.empty() && "LoopList should initially be empty!");

236 Loop *CurrentLoop = &L;

237 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();

238 while (!Vec->empty()) {

239

240

241

242 if (Vec->size() != 1) {

243 LoopList = {};

244 return;

245 }

246

247 LoopList.push_back(CurrentLoop);

248 CurrentLoop = Vec->front();

250 }

251 LoopList.push_back(CurrentLoop);

252}

253

256 unsigned LoopNestDepth = LoopList.size();

257 if (LoopNestDepth < MinLoopNestDepth || LoopNestDepth > MaxLoopNestDepth) {

258 LLVM_DEBUG(dbgs() << "Unsupported depth of loop nest " << LoopNestDepth

261 Loop **OuterLoop = LoopList.begin();

262 ORE.emit([&]() {

264 (*OuterLoop)->getStartLoc(),

265 (*OuterLoop)->getHeader())

266 << "Unsupported depth of loop nest, the supported range is ["

269 });

270 return false;

271 }

272 return true;

273}

274namespace {

275

276

277class LoopInterchangeLegality {

278public:

281 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}

282

283

284 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,

285 CharMatrix &DepMatrix);

286

287

288

290

291

292

293 bool isLoopStructureUnderstood();

294

295 bool currentLimitations();

296

298 return OuterInnerReductions;

299 }

300

302 return InnerLoopInductions;

303 }

304

305private:

306 bool tightlyNested(Loop *Outer, Loop *Inner);

307 bool containsUnsafeInstructions(BasicBlock *BB);

308

309

310

311

312

313 bool findInductionAndReductions(Loop *L,

315 Loop *InnerLoop);

316

317 Loop *OuterLoop;

318 Loop *InnerLoop;

319

321

322

324

325

326

328

329

331};

332

333

334

335class LoopInterchangeProfitability {

336public:

339 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}

340

341

343 unsigned InnerLoopId, unsigned OuterLoopId,

344 CharMatrix &DepMatrix,

346 std::unique_ptr &CC);

347

348private:

349 int getInstrOrderCost();

350 std::optional isProfitablePerLoopCacheAnalysis(

352 std::unique_ptr &CC);

353 std::optional isProfitablePerInstrOrderCost();

354 std::optional isProfitableForVectorization(unsigned InnerLoopId,

355 unsigned OuterLoopId,

356 CharMatrix &DepMatrix);

357 Loop *OuterLoop;

358 Loop *InnerLoop;

359

360

362

363

365};

366

367

368class LoopInterchangeTransform {

369public:

372 const LoopInterchangeLegality &LIL)

373 : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), LIL(LIL) {}

374

375

377 void restructureLoops(Loop *NewInner, Loop *NewOuter,

380 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);

381

382private:

383 bool adjustLoopLinks();

384 bool adjustLoopBranches();

385

386 Loop *OuterLoop;

387 Loop *InnerLoop;

388

389

391

394

395 const LoopInterchangeLegality &LIL;

396};

397

398struct LoopInterchange {

403 std::unique_ptr CC = nullptr;

404

405

407

409 DominatorTree *DT, std::unique_ptr &CC,

411 : SE(SE), LI(LI), DI(DI), DT(DT), CC(std::move(CC)), ORE(ORE) {}

412

414 if (L->getParentLoop())

415 return false;

418 return processLoopList(LoopList);

419 }

420

423 for (unsigned I = 1; I < LoopList.size(); ++I)

424 if (LoopList[I]->getParentLoop() != LoopList[I - 1])

425 return false;

426 return processLoopList(LoopList);

427 }

428

430 for (Loop *L : LoopList) {

432 if (isa(ExitCountOuter)) {

433 LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");

434 return false;

435 }

436 if (L->getNumBackEdges() != 1) {

437 LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");

438 return false;

439 }

440 if (->getExitingBlock()) {

441 LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");

442 return false;

443 }

444 }

445 return true;

446 }

447

448 unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {

449

450

451 return LoopList.size() - 1;

452 }

453

455 bool Changed = false;

456

457

459 "Unsupported depth of loop nest.");

460

461 unsigned LoopNestDepth = LoopList.size();

462 if (!isComputableLoopNest(LoopList)) {

463 LLVM_DEBUG(dbgs() << "Not valid loop candidate for interchange\n");

464 return false;

465 }

466

467 LLVM_DEBUG(dbgs() << "Processing LoopList of size = " << LoopNestDepth

468 << "\n");

469

470 CharMatrix DependencyMatrix;

471 Loop *OuterMostLoop = *(LoopList.begin());

473 OuterMostLoop, DI, SE, ORE)) {

474 LLVM_DEBUG(dbgs() << "Populating dependency matrix failed\n");

475 return false;

476 }

477

478 LLVM_DEBUG(dbgs() << "Dependency matrix before interchange:\n";

480

481

483 if (!LoopNestExit) {

484 LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");

485 return false;

486 }

487

488 unsigned SelecLoopId = selectLoopForInterchange(LoopList);

489

490

491

492

493

494

495

496

498 if (CC != nullptr) {

499 const auto &LoopCosts = CC->getLoopCosts();

500 for (unsigned i = 0; i < LoopCosts.size(); i++) {

501 CostMap[LoopCosts[i].first] = i;

502 }

503 }

504

505

506

507

508 for (unsigned j = SelecLoopId; j > 0; j--) {

509 bool ChangedPerIter = false;

510 for (unsigned i = SelecLoopId; i > SelecLoopId - j; i--) {

511 bool Interchanged = processLoop(LoopList[i], LoopList[i - 1], i, i - 1,

512 DependencyMatrix, CostMap);

513 if (!Interchanged)

514 continue;

515

516 std::swap(LoopList[i - 1], LoopList[i]);

517

519

520 LLVM_DEBUG(dbgs() << "Dependency matrix after interchange:\n";

522

523 ChangedPerIter |= Interchanged;

524 Changed |= Interchanged;

525 }

526

527

528 if (!ChangedPerIter)

529 break;

530 }

531 return Changed;

532 }

533

534 bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,

535 unsigned OuterLoopId,

536 std::vector<std::vector> &DependencyMatrix,

538 LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId

539 << " and OuterLoopId = " << OuterLoopId << "\n");

540 LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);

541 if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {

542 LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");

543 return false;

544 }

545 LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");

546 LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);

547 if (!LIP.isProfitable(InnerLoop, OuterLoop, InnerLoopId, OuterLoopId,

548 DependencyMatrix, CostMap, CC)) {

549 LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");

550 return false;

551 }

552

553 ORE->emit([&]() {

557 << "Loop interchanged with enclosing loop.";

558 });

559

560 LoopInterchangeTransform LIT(OuterLoop, InnerLoop, SE, LI, DT, LIL);

561 LIT.transform();

563 LoopsInterchanged++;

564

566 return true;

567 }

568};

569

570}

571

572bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {

574 return I.mayHaveSideEffects() || I.mayReadFromMemory();

575 });

576}

577

578bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {

582

583 LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");

584

585

586

587

589 dyn_cast(OuterLoopHeader->getTerminator());

590 if (!OuterLoopHeaderBI)

591 return false;

592

594 if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&

595 Succ != OuterLoopLatch)

596 return false;

597

598 LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");

599

600

601 if (containsUnsafeInstructions(OuterLoopHeader) ||

602 containsUnsafeInstructions(OuterLoopLatch))

603 return false;

604

605

606

607

608 if (InnerLoopPreHeader != OuterLoopHeader &&

609 containsUnsafeInstructions(InnerLoopPreHeader))

610 return false;

611

613

614

617 if (&SuccInner != OuterLoopLatch) {

618 LLVM_DEBUG(dbgs() << "Inner loop exit block " << *InnerLoopExit

619 << " does not lead to the outer loop latch.\n";);

620 return false;

621 }

622

623

624

625 if (containsUnsafeInstructions(InnerLoopExit))

626 return false;

627

628 LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");

629

630 return true;

631}

632

633bool LoopInterchangeLegality::isLoopStructureUnderstood() {

635 for (PHINode *InnerInduction : InnerLoopInductions) {

636 unsigned Num = InnerInduction->getNumOperands();

637 for (unsigned i = 0; i < Num; ++i) {

638 Value *Val = InnerInduction->getOperand(i);

639 if (isa(Val))

640 continue;

642 if ()

643 return false;

644

645

646

648 if (InnerInduction->getIncomingBlock(IncomBlockIndx) ==

649 InnerLoopPreheader &&

651 return false;

652 }

653 }

654 }

655

656

657

658

659

660

661

664 dyn_cast(InnerLoopLatch->getTerminator());

666 return false;

667 if (CmpInst *InnerLoopCmp =

668 dyn_cast(InnerLoopLatchBI->getCondition())) {

669 Value *Op0 = InnerLoopCmp->getOperand(0);

670 Value *Op1 = InnerLoopCmp->getOperand(1);

671

672

673

676

677

678

679

680

681 std::function<bool(Value *)> IsPathToInnerIndVar;

682 IsPathToInnerIndVar = [this, &IsPathToInnerIndVar](const Value *V) -> bool {

684 return true;

685 if (isa(V))

686 return true;

687 const Instruction *I = dyn_cast(V);

688 if ()

689 return false;

690 if (isa(I))

691 return IsPathToInnerIndVar(I->getOperand(0));

692 if (isa(I))

693 return IsPathToInnerIndVar(I->getOperand(0)) &&

694 IsPathToInnerIndVar(I->getOperand(1));

695 return false;

696 };

697

698

699

700 if (IsPathToInnerIndVar(Op0) && IsPathToInnerIndVar(Op1))

701 return true;

702

703

704

705 if (IsPathToInnerIndVar(Op0) && !isa(Op0)) {

708 } else if (IsPathToInnerIndVar(Op1) && !isa(Op1)) {

711 }

712

713 if (Left == nullptr)

714 return false;

715

718 return false;

719 }

720

721 return true;

722}

723

724

725

727 PHINode *PHI = dyn_cast(SV);

728 if ( PHI )

729 return SV;

730

731 if (PHI->getNumIncomingValues() != 1)

732 return SV;

734}

735

736

738

739 if (isa(V))

740 return nullptr;

741

744 if (PHI->getNumIncomingValues() == 1)

745 continue;

748

750 return nullptr;

751 return PHI;

752 }

753 return nullptr;

754 }

755 }

756

757 return nullptr;

758}

759

760bool LoopInterchangeLegality::findInductionAndReductions(

762 if (->getLoopLatch() || ->getLoopPredecessor())

763 return false;

764 for (PHINode &PHI : L->getHeader()->phis()) {

768 else {

769

770

771 if (!InnerLoop) {

772 if (!OuterInnerReductions.count(&PHI)) {

773 LLVM_DEBUG(dbgs() << "Inner loop PHI is not part of reductions "

774 "across the outer loop.\n");

775 return false;

776 }

777 } else {

778 assert(PHI.getNumIncomingValues() == 2 &&

779 "Phis in loop header should have exactly 2 incoming values");

780

781

784 if (!InnerRedPhi ||

788 << "Failed to recognize PHI as an induction or reduction.\n");

789 return false;

790 }

791 OuterInnerReductions.insert(&PHI);

792 OuterInnerReductions.insert(InnerRedPhi);

793 }

794 }

795 }

796 return true;

797}

798

799

800

801bool LoopInterchangeLegality::currentLimitations() {

803

804

805

808 !isa(InnerLoopLatch->getTerminator()) ||

811 dbgs() << "Loops where the latch is not the exiting block are not"

812 << " supported currently.\n");

813 ORE->emit([&]() {

817 << "Loops where the latch is not the exiting block cannot be"

818 " interchange currently.";

819 });

820 return true;

821 }

822

824 if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) {

826 dbgs() << "Only outer loops with induction or reduction PHI nodes "

827 << "are supported currently.\n");

828 ORE->emit([&]() {

832 << "Only outer loops with induction or reduction PHI nodes can be"

833 " interchanged currently.";

834 });

835 return true;

836 }

837

838 Inductions.clear();

839

840

841

842 Loop *CurLevelLoop = OuterLoop;

843 while (!CurLevelLoop->getSubLoops().empty()) {

844

845 CurLevelLoop = CurLevelLoop->getSubLoops().front();

846 if (!findInductionAndReductions(CurLevelLoop, Inductions, nullptr)) {

848 dbgs() << "Only inner loops with induction or reduction PHI nodes "

849 << "are supported currently.\n");

850 ORE->emit([&]() {

854 << "Only inner loops with induction or reduction PHI nodes can be"

855 " interchange currently.";

856 });

857 return true;

858 }

859 }

860

861

862 if (!isLoopStructureUnderstood()) {

863 LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n");

864 ORE->emit([&]() {

868 << "Inner loop structure not understood currently.";

869 });

870 return true;

871 }

872

873 return false;

874}

875

876bool LoopInterchangeLegality::findInductions(

878 for (PHINode &PHI : L->getHeader()->phis()) {

882 }

883 return !Inductions.empty();

884}

885

886

887

888

889static bool

894

895 if (PHI.getNumIncomingValues() > 1)

896 return false;

898 PHINode *PN = dyn_cast(U);

899 return !PN ||

900 (!Reductions.count(PN) && OuterL->contains(PN->getParent()));

901 })) {

902 return false;

903 }

904 }

905 return true;

906}

907

908

909

910

911

912

913

914

918 for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {

919 Instruction *IncomingI = dyn_cast(PHI.getIncomingValue(i));

921 continue;

922

923

924

925

926

927

928

929

930

931

932

934 return false;

935 }

936 }

937 return true;

938}

939

940

941

942

943

944

945

946

947

950 return true;

951

952

953

955 return true;

956

957

958

959

960

961

962

965 for (auto *U : PHI.users()) {

967 if (InnerLoopLatch == UI->getParent())

968 return false;

969 }

970 }

971 return true;

972}

973

974bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,

975 unsigned OuterLoopId,

976 CharMatrix &DepMatrix) {

978 LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId

979 << " and OuterLoopId = " << OuterLoopId

980 << " due to dependence\n");

981 ORE->emit([&]() {

985 << "Cannot interchange loops due to dependences.";

986 });

987 return false;

988 }

989

990 for (auto *BB : OuterLoop->blocks())

992 if (CallInst *CI = dyn_cast(&I)) {

993

994 if (CI->onlyWritesMemory())

995 continue;

997 dbgs() << "Loops with call instructions cannot be interchanged "

998 << "safely.");

999 ORE->emit([&]() {

1001 CI->getDebugLoc(),

1002 CI->getParent())

1003 << "Cannot interchange loops due to call instruction.";

1004 });

1005

1006 return false;

1007 }

1008

1009 if (!findInductions(InnerLoop, InnerLoopInductions)) {

1010 LLVM_DEBUG(dbgs() << "Could not find inner loop induction variables.\n");

1011 return false;

1012 }

1013

1015 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop latch.\n");

1016 ORE->emit([&]() {

1020 << "Cannot interchange loops because unsupported PHI nodes found "

1021 "in inner loop latch.";

1022 });

1023 return false;

1024 }

1025

1026

1027

1028 if (currentLimitations()) {

1029 LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");

1030 return false;

1031 }

1032

1033

1034 if (!tightlyNested(OuterLoop, InnerLoop)) {

1036 ORE->emit([&]() {

1040 << "Cannot interchange loops because they are not tightly "

1041 "nested.";

1042 });

1043 return false;

1044 }

1045

1047 OuterInnerReductions)) {

1048 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n");

1049 ORE->emit([&]() {

1053 << "Found unsupported PHI node in loop exit.";

1054 });

1055 return false;

1056 }

1057

1059 LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in outer loop exit.\n");

1060 ORE->emit([&]() {

1064 << "Found unsupported PHI node in loop exit.";

1065 });

1066 return false;

1067 }

1068

1069 return true;

1070}

1071

1072int LoopInterchangeProfitability::getInstrOrderCost() {

1073 unsigned GoodOrder, BadOrder;

1074 BadOrder = GoodOrder = 0;

1078 unsigned NumOp = GEP->getNumOperands();

1079 bool FoundInnerInduction = false;

1080 bool FoundOuterInduction = false;

1081 for (unsigned i = 0; i < NumOp; ++i) {

1082

1083 if (!SE->isSCEVable(GEP->getOperand(i)->getType()))

1084 continue;

1085

1086 const SCEV *OperandVal = SE->getSCEV(GEP->getOperand(i));

1087 const SCEVAddRecExpr *AR = dyn_cast(OperandVal);

1088 if (!AR)

1089 continue;

1090

1091

1092

1093

1094

1095

1096 if (AR->getLoop() == InnerLoop) {

1097

1098

1099 FoundInnerInduction = true;

1100 if (FoundOuterInduction) {

1101 GoodOrder++;

1102 break;

1103 }

1104 }

1105

1106

1107

1108

1109

1110 if (AR->getLoop() == OuterLoop) {

1111

1112

1113 FoundOuterInduction = true;

1114 if (FoundInnerInduction) {

1115 BadOrder++;

1116 break;

1117 }

1118 }

1119 }

1120 }

1121 }

1122 }

1123 return GoodOrder - BadOrder;

1124}

1125

1126std::optional

1127LoopInterchangeProfitability::isProfitablePerLoopCacheAnalysis(

1129 std::unique_ptr &CC) {

1130

1131

1132

1133 if (CostMap.contains(InnerLoop) && CostMap.contains(OuterLoop)) {

1134 unsigned InnerIndex = 0, OuterIndex = 0;

1135 InnerIndex = CostMap.find(InnerLoop)->second;

1136 OuterIndex = CostMap.find(OuterLoop)->second;

1138 << ", OuterIndex = " << OuterIndex << "\n");

1139 if (InnerIndex < OuterIndex)

1140 return std::optional(true);

1141 assert(InnerIndex != OuterIndex && "CostMap should assign unique "

1142 "numbers to each loop");

1143 if (CC->getLoopCost(*OuterLoop) == CC->getLoopCost(*InnerLoop))

1144 return std::nullopt;

1145 return std::optional(false);

1146 }

1147 return std::nullopt;

1148}

1149

1150std::optional

1151LoopInterchangeProfitability::isProfitablePerInstrOrderCost() {

1152

1153

1154

1155 int Cost = getInstrOrderCost();

1158 return std::optional(true);

1159

1160 return std::nullopt;

1161}

1162

1163std::optional LoopInterchangeProfitability::isProfitableForVectorization(

1164 unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix) {

1165 for (auto &Row : DepMatrix) {

1166

1167

1168

1169 if (Row[InnerLoopId] == 'I' || Row[InnerLoopId] == '=')

1170 return std::optional(false);

1171

1172

1173

1174

1175 if (Row[OuterLoopId] != 'I' && Row[OuterLoopId] != '=')

1176 return std::optional(false);

1177 }

1178

1179

1180

1181 return std::optional(!DepMatrix.empty());

1182}

1183

1184bool LoopInterchangeProfitability::isProfitable(

1185 const Loop *InnerLoop, const Loop *OuterLoop, unsigned InnerLoopId,

1186 unsigned OuterLoopId, CharMatrix &DepMatrix,

1188 std::unique_ptr &CC) {

1189

1190

1191

1192

1193

1194

1195

1196

1197 std::optional shouldInterchange =

1198 isProfitablePerLoopCacheAnalysis(CostMap, CC);

1199 if (!shouldInterchange.has_value()) {

1200 shouldInterchange = isProfitablePerInstrOrderCost();

1201 if (!shouldInterchange.has_value())

1202 shouldInterchange =

1203 isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix);

1204 }

1205 if (!shouldInterchange.has_value()) {

1206 ORE->emit([&]() {

1210 << "Insufficient information to calculate the cost of loop for "

1211 "interchange.";

1212 });

1213 return false;

1214 } else if (!shouldInterchange.value()) {

1215 ORE->emit([&]() {

1219 << "Interchanging loops is not considered to improve cache "

1220 "locality nor vectorization.";

1221 });

1222 return false;

1223 }

1224 return true;

1225}

1226

1227void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,

1228 Loop *InnerLoop) {

1229 for (Loop *L : *OuterLoop)

1230 if (L == InnerLoop) {

1231 OuterLoop->removeChildLoop(L);

1232 return;

1233 }

1235}

1236

1237

1238

1239

1240

1241

1242

1243

1244

1245

1246

1247

1248

1249

1250

1251

1252

1253

1254

1255

1256

1257

1258

1259

1260void LoopInterchangeTransform::restructureLoops(

1264

1265

1267 LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);

1268

1269

1270 if (OuterLoopParent) {

1271

1272 removeChildLoop(OuterLoopParent, NewInner);

1273 removeChildLoop(NewInner, NewOuter);

1275 } else {

1276 removeChildLoop(NewInner, NewOuter);

1278 }

1282

1283

1285

1286

1287

1291

1292

1293

1296 for (BasicBlock *BB : OrigInnerBBs) {

1297

1299 continue;

1300

1301 if (BB == OuterHeader || BB == OuterLatch)

1303 else

1305 }

1306

1307

1308

1310 LI->changeLoopFor(OrigOuterPreHeader, NewOuter);

1311

1312

1314}

1315

1316bool LoopInterchangeTransform::transform() {

1317 bool Transformed = false;

1318

1321 LLVM_DEBUG(dbgs() << "Splitting the inner loop latch\n");

1322 auto &InductionPHIs = LIL.getInnerLoopInductions();

1323 if (InductionPHIs.empty()) {

1324 LLVM_DEBUG(dbgs() << "Failed to find the point to split loop latch \n");

1325 return false;

1326 }

1327

1329 for (PHINode *CurInductionPHI : InductionPHIs) {

1330 if (CurInductionPHI->getIncomingBlock(0) == InnerLoopPreHeader)

1332 dyn_cast(CurInductionPHI->getIncomingValue(1)));

1333 else

1335 dyn_cast(CurInductionPHI->getIncomingValue(0)));

1336 }

1337

1338

1339

1340

1341

1345

1347 unsigned i = 0;

1348 auto MoveInstructions = [&i, &WorkList, this, &InductionPHIs, NewLatch]() {

1349 for (; i < WorkList.size(); i++) {

1350

1351

1352 Instruction *NewI = WorkList[i]->clone();

1355 "Moving instructions with side-effects may change behavior of "

1356 "the loop nest!");

1358 Instruction *UserI = cast(U.getUser());

1360 UserI->getParent() == NewLatch ||

1362 U.set(NewI);

1363 }

1364

1365

1366 for (Value *Op : WorkList[i]->operands()) {

1368 if (!OpI ||

1371 continue;

1372 WorkList.insert(OpI);

1373 }

1374 }

1375 };

1376

1377

1378 Instruction *CondI = dyn_cast(

1380 ->getCondition());

1381 if (CondI)

1382 WorkList.insert(CondI);

1383 MoveInstructions();

1384 for (Instruction *InnerIndexVar : InnerIndexVarList)

1385 WorkList.insert(cast(InnerIndexVar));

1386 MoveInstructions();

1387 }

1388

1389

1393 LLVM_DEBUG(dbgs() << "splitting InnerLoopHeader done\n");

1394 }

1395

1396

1397

1398

1399

1400

1402 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();

1403 if (InnerLoopPreHeader != OuterLoopHeader) {

1407 std::prev(InnerLoopPreHeader->end()))))

1408 I.moveBeforePreserving(OuterLoopHeader->getTerminator());

1409 }

1410

1411 Transformed |= adjustLoopLinks();

1412 if (!Transformed) {

1414 return false;

1415 }

1416

1417 return true;

1418}

1419

1420

1421

1424

1427}

1428

1429

1431

1432

1436 I->removeFromParent();

1437

1438

1440

1441

1444}

1445

1446

1447

1448

1451 std::vectorDominatorTree::UpdateType &DTUpdates,

1452 bool MustUpdateOnce = true) {

1453 assert((!MustUpdateOnce ||

1456 return BB == OldBB;

1457 }) == 1) && "BI must jump to OldBB exactly once.");

1458 bool Changed = false;

1460 if (Op == OldBB) {

1461 Op.set(NewBB);

1462 Changed = true;

1463 }

1464

1465 if (Changed) {

1466 DTUpdates.push_back(

1467 {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});

1468 DTUpdates.push_back(

1469 {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});

1470 }

1471 assert(Changed && "Expected a successor to be updated");

1472}

1473

1474

1479

1480

1481

1482

1483

1484

1485

1486

1488 assert(P.getNumIncomingValues() == 1 &&

1489 "Only loops with a single exit are supported!");

1490

1491

1492 auto IncI = cast(P.getIncomingValueForBlock(InnerLatch));

1493

1494

1495 auto IncIInnerMost = cast(followLCSSA(IncI));

1496

1497

1498 if (IncIInnerMost->getParent() != InnerLatch &&

1499 IncIInnerMost->getParent() != InnerHeader)

1500 continue;

1501

1503 [OuterHeader, OuterExit, IncI, InnerHeader](User *U) {

1504 return (cast(U)->getParent() == OuterHeader &&

1505 IncI->getParent() == InnerHeader) ||

1506 cast(U)->getParent() == OuterExit;

1507 }) &&

1508 "Can only replace phis iff the uses are in the loop nest exit or "

1509 "the incoming value is defined in the inner header (it will "

1510 "dominate all loop blocks after interchanging)");

1511 P.replaceAllUsesWith(IncI);

1512 P.eraseFromParent();

1513 }

1514

1518

1522

1523

1524

1525

1526

1527

1528 for (PHINode *P : LcssaInnerExit)

1530

1531

1532

1533 for (PHINode *P : LcssaInnerLatch)

1535

1536

1537

1538

1539

1540 if (OuterExit) {

1542 if (P.getNumIncomingValues() != 1)

1543 continue;

1544

1545

1546 auto I = dyn_cast(P.getIncomingValue(0));

1547 if ( || LI->getLoopFor(I->getParent()) == InnerLoop)

1548 continue;

1549

1550 PHINode *NewPhi = dyn_cast(P.clone());

1553

1554

1555 for (auto *Pred : predecessors(InnerLatch)) {

1556 if (Pred == OuterLatch)

1557 continue;

1558 NewPhi->addIncoming(P.getIncomingValue(0), Pred);

1559 }

1561 P.setIncomingValue(0, NewPhi);

1562 }

1563 }

1564

1565

1566

1567

1569}

1570

1571bool LoopInterchangeTransform::adjustLoopBranches() {

1572 LLVM_DEBUG(dbgs() << "adjustLoopBranches called\n");

1573 std::vectorDominatorTree::UpdateType DTUpdates;

1574

1575 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();

1577

1578 assert(OuterLoopPreHeader != OuterLoop->getHeader() &&

1579 InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&

1580 InnerLoopPreHeader && "Guaranteed by loop-simplify form");

1581

1582

1583

1584

1585 if (isa(OuterLoopPreHeader->begin()) ||

1587 OuterLoopPreHeader =

1589 if (InnerLoopPreHeader == OuterLoop->getHeader())

1590 InnerLoopPreHeader =

1592

1593

1595 BasicBlock *OuterLoopHeader = OuterLoop->getHeader();

1597 BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();

1599 BasicBlock *InnerLoopLatchPredecessor =

1601 BasicBlock *InnerLoopLatchSuccessor;

1602 BasicBlock *OuterLoopLatchSuccessor;

1603

1605 dyn_cast(OuterLoopLatch->getTerminator());

1607 dyn_cast(InnerLoopLatch->getTerminator());

1609 dyn_cast(OuterLoopHeader->getTerminator());

1611 dyn_cast(InnerLoopHeader->getTerminator());

1612

1613 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||

1614 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||

1615 !InnerLoopHeaderBI)

1616 return false;

1617

1618 BranchInst *InnerLoopLatchPredecessorBI =

1619 dyn_cast(InnerLoopLatchPredecessor->getTerminator());

1620 BranchInst *OuterLoopPredecessorBI =

1621 dyn_cast(OuterLoopPredecessor->getTerminator());

1622

1623 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)

1624 return false;

1626 if (!InnerLoopHeaderSuccessor)

1627 return false;

1628

1629

1630

1631

1632

1633 updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,

1634 InnerLoopPreHeader, DTUpdates, false);

1635

1636

1638

1639 updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, InnerLoopLatch,

1640 DTUpdates,

1641 false);

1642 }

1644 InnerLoopHeaderSuccessor, DTUpdates,

1645 false);

1646

1647

1649 OuterLoopHeader);

1650

1651 updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,

1652 OuterLoopPreHeader, DTUpdates);

1653

1654

1655 if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)

1656 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);

1657 else

1658 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);

1659

1660 updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,

1661 InnerLoopLatchSuccessor, DTUpdates);

1662

1663 if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)

1664 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);

1665 else

1666 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);

1667

1668 updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,

1669 OuterLoopLatchSuccessor, DTUpdates);

1670 updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,

1671 DTUpdates);

1672

1674 restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,

1675 OuterLoopPreHeader);

1676

1677 moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,

1678 OuterLoopHeader, OuterLoopLatch, InnerLoop->getExitBlock(),

1679 InnerLoop, LI);

1680

1681

1682 OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);

1683

1684 auto &OuterInnerReductions = LIL.getOuterInnerReductions();

1685

1688 if (OuterInnerReductions.contains(&PHI))

1690

1692 if (OuterInnerReductions.contains(&PHI))

1694

1695

1696

1697

1698 for (PHINode *PHI : OuterLoopPHIs) {

1699 LLVM_DEBUG(dbgs() << "Outer loop reduction PHIs:\n"; PHI->dump(););

1701 assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");

1702 }

1703 for (PHINode *PHI : InnerLoopPHIs) {

1704 LLVM_DEBUG(dbgs() << "Inner loop reduction PHIs:\n"; PHI->dump(););

1706 assert(OuterInnerReductions.count(PHI) && "Expected a reduction PHI node");

1707 }

1708

1709

1710 OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);

1711 OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);

1712 InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);

1713 InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);

1714

1715

1716

1717

1718

1721 make_range(OuterLoopHeader->begin(), std::prev(OuterLoopHeader->end())))

1724

1725 return true;

1726}

1727

1728bool LoopInterchangeTransform::adjustLoopLinks() {

1729

1730 bool Changed = adjustLoopBranches();

1731 if (Changed) {

1732

1733

1734

1735 BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();

1737 swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader);

1738 }

1739 return Changed;

1740}

1741

1748

1750 LLVM_DEBUG(dbgs() << "MaxMemInstrCount should be at least 1");

1752 }

1754

1755

1759 std::unique_ptr CC =

1761

1762 if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, CC, &ORE).run(LN))

1764 U.markLoopNestChanged(true);

1766}

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

Given that RA is a live propagate it s liveness to any other values it uses(according to Uses). void DeadArgumentEliminationPass

This file defines the interface for the loop cache analysis.

static cl::opt< unsigned int > MaxMemInstrCount("loop-interchange-max-meminstr-count", cl::init(64), cl::Hidden, cl::desc("Maximum number of load-store instructions that should be handled " "in the dependency matrix. Higher value may lead to more interchanges " "at the cost of compile-time"))

static cl::opt< int > LoopInterchangeCostThreshold("loop-interchange-threshold", cl::init(0), cl::Hidden, cl::desc("Interchange if you gain more than this number"))

static PHINode * findInnerReductionPhi(Loop *L, Value *V)

static cl::opt< unsigned int > MinLoopNestDepth("loop-interchange-min-loop-nest-depth", cl::init(2), cl::Hidden, cl::desc("Minimum depth of loop nest considered for the transform"))

static bool hasSupportedLoopDepth(SmallVectorImpl< Loop * > &LoopList, OptimizationRemarkEmitter &ORE)

static bool areOuterLoopExitPHIsSupported(Loop *OuterLoop, Loop *InnerLoop)

static void moveBBContents(BasicBlock *FromBB, Instruction *InsertBefore)

Move all instructions except the terminator from FromBB right before InsertBefore.

static void interChangeDependencies(CharMatrix &DepMatrix, unsigned FromIndx, unsigned ToIndx)

static void moveLCSSAPhis(BasicBlock *InnerExit, BasicBlock *InnerHeader, BasicBlock *InnerLatch, BasicBlock *OuterHeader, BasicBlock *OuterLatch, BasicBlock *OuterExit, Loop *InnerLoop, LoopInfo *LI)

static void printDepMatrix(CharMatrix &DepMatrix)

static void swapBBContents(BasicBlock *BB1, BasicBlock *BB2)

Swap instructions between BB1 and BB2 but keep terminators intact.

static cl::opt< unsigned int > MaxLoopNestDepth("loop-interchange-max-loop-nest-depth", cl::init(10), cl::Hidden, cl::desc("Maximum depth of loop nest considered for the transform"))

static bool areInnerLoopLatchPHIsSupported(Loop *OuterLoop, Loop *InnerLoop)

static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix, unsigned InnerLoopId, unsigned OuterLoopId)

static bool areInnerLoopExitPHIsSupported(Loop *InnerL, Loop *OuterL, SmallPtrSetImpl< PHINode * > &Reductions)

static Value * followLCSSA(Value *SV)

static void populateWorklist(Loop &L, LoopVector &LoopList)

static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, Loop *L, DependenceInfo *DI, ScalarEvolution *SE, OptimizationRemarkEmitter *ORE)

static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB, BasicBlock *NewBB, std::vector< DominatorTree::UpdateType > &DTUpdates, bool MustUpdateOnce=true)

static bool isLexicographicallyPositive(std::vector< char > &DV)

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.

uint64_t IntrinsicInst * II

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

This file defines the SmallVector class.

static bool isProfitable(const SmallVector< std::unique_ptr< StableFunctionMap::StableFunctionEntry > > &SFS)

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

#define STATISTIC(VARNAME, DESC)

StringSet - A set-like wrapper for the StringMap.

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

size_t size() const

size - Get the array size.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const

Return a const iterator range over the instructions in the block, skipping any debug instructions.

const Instruction * getFirstNonPHI() const

Returns a pointer to the first instruction in this block that is not a PHINode instruction.

const BasicBlock * getUniqueSuccessor() const

Return the successor of this block if it has a unique successor.

void replacePhiUsesWith(BasicBlock *Old, BasicBlock *New)

Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.

const BasicBlock * getUniquePredecessor() const

Return the predecessor of this block if it has a unique predecessor block.

const Function * getParent() const

Return the enclosing method, or null if none.

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

void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)

Transfer all instructions from FromBB to this basic block at ToIt.

Conditional or Unconditional Branch instruction.

iterator_range< succ_op_iterator > successors()

bool isConditional() const

BasicBlock * getSuccessor(unsigned i) const

Value * getCondition() const

static std::unique_ptr< CacheCost > getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI, std::optional< unsigned > TRT=std::nullopt)

Create a CacheCost for the loop nest rooted by Root.

This class represents a function call, abstracting a target machine's calling convention.

This class is the base class for the comparison instructions.

This class represents an Operation in the Expression.

iterator find(const_arg_type_t< KeyT > Val)

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

DependenceInfo - This class is the main dependence-analysis driver.

std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)

depends - Tests for a dependence between the Src and Dst instructions.

void applyUpdates(ArrayRef< UpdateType > Updates)

Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...

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

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

A struct for saving information about induction variables.

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.

void insertBefore(Instruction *InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified instruction.

bool mayHaveSideEffects() const LLVM_READONLY

Return true if the instruction may have side effects.

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

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.

bool isInnermost() const

Return true if the loop does not contain any (natural) loops.

void removeBlockFromLoop(BlockT *BB)

This removes the specified basic block from the current loop, updating the Blocks as appropriate.

const std::vector< LoopT * > & getSubLoops() const

Return the loops contained entirely within this loop.

BlockT * getHeader() const

iterator_range< block_iterator > blocks() const

void addChildLoop(LoopT *NewChild)

Add the specified loop to be a child of this loop.

void addBlockEntry(BlockT *BB)

This adds a basic block directly to the basic block list.

BlockT * getExitBlock() const

If getExitBlocks would return exactly one block, return that block.

BlockT * getLoopPreheader() const

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

BlockT * getExitingBlock() const

If getExitingBlocks would return exactly one block, return that block.

LoopT * getParentLoop() const

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

BlockT * getUniqueExitBlock() const

If getUniqueExitBlocks would return exactly one block, return that block.

LoopT * removeChildLoop(iterator I)

This removes the specified child from being a subloop of this loop.

void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)

Replace the specified loop in the top-level loops list with the indicated loop.

void changeLoopFor(BlockT *BB, LoopT *L)

Change the top-level loop that contains BB to the specified loop.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

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

static const BasicBlock & skipEmptyBlockUntil(const BasicBlock *From, const BasicBlock *End, bool CheckUniquePred=false)

Recursivelly traverse all empty 'single successor' basic blocks of From (if there are any).

ArrayRef< Loop * > getLoops() const

Get the loops in the nest.

Function * getParent() const

Return the function to which the loop-nest belongs.

Loop & getOutermostLoop() const

Return the outermost loop in the loop nest.

Represents a single loop in the control flow graph.

DebugLoc getStartLoc() const

Return the debug location of the start of this loop.

bool isLoopInvariant(const Value *V) const

Return true if the specified value is loop invariant.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

op_range incoming_values()

void setIncomingBlock(unsigned i, BasicBlock *BB)

void setIncomingValue(unsigned i, Value *V)

static unsigned getIncomingValueNumForOperand(unsigned i)

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.

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

Instruction * getExactFPMathInst() const

Returns 1st non-reassociative FP instruction in the PHI node's use-chain.

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.

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

const Loop * getLoop() const

This class represents an analyzed expression in the program.

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.

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

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

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

bool isSCEVable(Type *Ty) const

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

size_type size() const

Determine the number of elements in the SetVector.

bool insert(const value_type &X)

Insert a new element into the SetVector.

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

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

A SetVector that performs no allocations if smaller than a certain size.

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

void push_back(const T &Elt)

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

StringRef - Represent a constant reference to a string, i.e.

StringSet - A wrapper for StringMap that provides set-like functionality.

std::pair< typename Base::iterator, bool > insert(StringRef key)

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

LLVM Value Representation.

const ParentTy * getParent() const

self_iterator getIterator()

#define llvm_unreachable(msg)

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

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

This is an optimization pass for GlobalISel generic memory operations.

BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

InsertPreheaderForLoop - Once we discover that a loop doesn't have a preheader, this method is called...

bool all_of(R &&range, UnaryPredicate P)

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

auto successors(const MachineBasicBlock *BB)

bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)

Put a loop nest into LCSSA form.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

auto map_range(ContainerTy &&C, FuncTy F)

OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)

Wrapper function around std::transform to apply a function to a range and store the result elsewhere.

bool any_of(R &&range, UnaryPredicate P)

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

raw_ostream & dbgs()

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

OutputIt move(R &&Range, OutputIt Out)

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

bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)

Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.

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

BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

PreservedAnalyses getLoopPassPreservedAnalyses()

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

auto predecessors(const MachineBasicBlock *BB)

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

Returns true if Element is found in Range.

Implement std::hash so that hash_code can be used in STL containers.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

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

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

Direction

An enum for the direction of the loop.