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#ifndef NDEBUG

82 for (auto &Row : DepMatrix) {

83 for (auto D : Row)

86 }

87}

88#endif

96 ValueVector MemInstr;

100

102 if (!isa(I))

103 return false;

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

105 if (!Ld->isSimple())

106 return false;

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

109 if (!St->isSimple())

110 return false;

111 MemInstr.push_back(&I);

112 }

113 }

114 }

115

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

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

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

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

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

125 "can be increased with option "

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

127 });

128 return false;

129 }

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

132

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

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

135 std::vector Dep;

137 Instruction *Dst = cast(*J);

138

139 if (isa(Src) && isa(Dst))

140 continue;

141

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

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

144

145

146 if (D->normalize(SE))

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

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

150 dbgs() << "Found " << DepType

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

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

153 unsigned Levels = D->getLevels();

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

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

164 else

167 }

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

169 Dep.push_back('I');

170 }

171

172

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

174 DepMatrix.push_back(Dep);

175 }

176 }

177 }

178

179 return true;

180}

181

182

183

185 unsigned ToIndx) {

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

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

188}

189

190

191

192

193

195 for (unsigned char Direction : DV) {

197 return true;

199 return false;

200 }

201 return true;

202}

203

204

206 unsigned InnerLoopId,

207 unsigned OuterLoopId) {

208 unsigned NumRows = DepMatrix.size();

209 std::vector Cur;

210

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

212

213

214 Cur = DepMatrix[Row];

216 return false;

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

219 return false;

220 }

221 return true;

222}

223

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

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

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

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

229 Loop *CurrentLoop = &L;

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

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

232

233

234

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

236 LoopList = {};

237 return;

238 }

239

240 LoopList.push_back(CurrentLoop);

241 CurrentLoop = Vec->front();

243 }

244 LoopList.push_back(CurrentLoop);

245}

246

248 unsigned LoopNestDepth = LoopList.size();

249 if (LoopNestDepth < 2) {

250 LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");

251 return false;

252 }

253 return true;

254}

255namespace {

256

257

258class LoopInterchangeLegality {

259public:

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

263

264

265 bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,

266 CharMatrix &DepMatrix);

267

268

269

271

272

273

274 bool isLoopStructureUnderstood();

275

276 bool currentLimitations();

277

279 return OuterInnerReductions;

280 }

281

283 return InnerLoopInductions;

284 }

285

286private:

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

288 bool containsUnsafeInstructions(BasicBlock *BB);

289

290

291

292

293

294 bool findInductionAndReductions(Loop *L,

296 Loop *InnerLoop);

297

298 Loop *OuterLoop;

299 Loop *InnerLoop;

300

302

303

305

306

307

309

310

312};

313

314

315

316class LoopInterchangeProfitability {

317public:

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

321

322

324 unsigned InnerLoopId, unsigned OuterLoopId,

325 CharMatrix &DepMatrix,

327 std::unique_ptr &CC);

328

329private:

330 int getInstrOrderCost();

331 std::optional isProfitablePerLoopCacheAnalysis(

333 std::unique_ptr &CC);

334 std::optional isProfitablePerInstrOrderCost();

335 std::optional isProfitableForVectorization(unsigned InnerLoopId,

336 unsigned OuterLoopId,

337 CharMatrix &DepMatrix);

338 Loop *OuterLoop;

339 Loop *InnerLoop;

340

341

343

344

346};

347

348

349class LoopInterchangeTransform {

350public:

353 const LoopInterchangeLegality &LIL)

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

355

356

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

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

362

363private:

364 bool adjustLoopLinks();

365 bool adjustLoopBranches();

366

367 Loop *OuterLoop;

368 Loop *InnerLoop;

369

370

372

375

376 const LoopInterchangeLegality &LIL;

377};

378

379struct LoopInterchange {

384 std::unique_ptr CC = nullptr;

385

386

388

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

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

393

395 if (L->getParentLoop())

396 return false;

399 return processLoopList(LoopList);

400 }

401

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

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

406 return false;

407 return processLoopList(LoopList);

408 }

409

411 for (Loop *L : LoopList) {

413 if (isa(ExitCountOuter)) {

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

415 return false;

416 }

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

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

419 return false;

420 }

421 if (->getExitingBlock()) {

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

423 return false;

424 }

425 }

426 return true;

427 }

428

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

430

431

432 return LoopList.size() - 1;

433 }

434

436 bool Changed = false;

437

438

440

441 unsigned LoopNestDepth = LoopList.size();

443 LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "

445 return false;

446 }

447 if (!isComputableLoopNest(LoopList)) {

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

449 return false;

450 }

451

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

453 << "\n");

454

455 CharMatrix DependencyMatrix;

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

458 OuterMostLoop, DI, SE, ORE)) {

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

460 return false;

461 }

462

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

465

466

468 if (!LoopNestExit) {

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

470 return false;

471 }

472

473 unsigned SelecLoopId = selectLoopForInterchange(LoopList);

474

475

476

477

478

479

480

481

483 if (CC != nullptr) {

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

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

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

487 }

488 }

489

490

491

492

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

494 bool ChangedPerIter = false;

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

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

497 DependencyMatrix, CostMap);

498 if (!Interchanged)

499 continue;

500

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

502

504

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

507

508 ChangedPerIter |= Interchanged;

509 Changed |= Interchanged;

510 }

511

512

513 if (!ChangedPerIter)

514 break;

515 }

516 return Changed;

517 }

518

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

520 unsigned OuterLoopId,

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

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

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

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

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

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

528 return false;

529 }

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

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

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

533 DependencyMatrix, CostMap, CC)) {

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

535 return false;

536 }

537

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

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

543 });

544

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

546 LIT.transform();

548 LoopsInterchanged++;

549

551 return true;

552 }

553};

554

555}

556

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

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

560 });

561}

562

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

567

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

569

570

571

572

574 dyn_cast(OuterLoopHeader->getTerminator());

575 if (!OuterLoopHeaderBI)

576 return false;

577

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

580 Succ != OuterLoopLatch)

581 return false;

582

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

584

585

586 if (containsUnsafeInstructions(OuterLoopHeader) ||

587 containsUnsafeInstructions(OuterLoopLatch))

588 return false;

589

590

591

592

593 if (InnerLoopPreHeader != OuterLoopHeader &&

594 containsUnsafeInstructions(InnerLoopPreHeader))

595 return false;

596

598

599

602 if (&SuccInner != OuterLoopLatch) {

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

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

605 return false;

606 }

607

608

609

610 if (containsUnsafeInstructions(InnerLoopExit))

611 return false;

612

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

614

615 return true;

616}

617

618bool LoopInterchangeLegality::isLoopStructureUnderstood() {

620 for (PHINode *InnerInduction : InnerLoopInductions) {

621 unsigned Num = InnerInduction->getNumOperands();

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

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

624 if (isa(Val))

625 continue;

627 if ()

628 return false;

629

630

631

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

634 InnerLoopPreheader &&

636 return false;

637 }

638 }

639 }

640

641

642

643

644

645

646

649 dyn_cast(InnerLoopLatch->getTerminator());

651 return false;

652 if (CmpInst *InnerLoopCmp =

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

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

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

656

657

658

661

662

663

664

665

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

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

669 return true;

670 if (isa(V))

671 return true;

672 const Instruction *I = dyn_cast(V);

673 if ()

674 return false;

675 if (isa(I))

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

677 if (isa(I))

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

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

680 return false;

681 };

682

683

684

685 if (IsPathToInnerIndVar(Op0) && IsPathToInnerIndVar(Op1))

686 return true;

687

688

689

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

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

696 }

697

698 if (Left == nullptr)

699 return false;

700

703 return false;

704 }

705

706 return true;

707}

708

709

710

712 PHINode *PHI = dyn_cast(SV);

713 if ( PHI )

714 return SV;

715

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

717 return SV;

719}

720

721

723

724 if (isa(V))

725 return nullptr;

726

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

730 continue;

733

735 return nullptr;

736 return PHI;

737 }

738 return nullptr;

739 }

740 }

741

742 return nullptr;

743}

744

745bool LoopInterchangeLegality::findInductionAndReductions(

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

748 return false;

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

753 else {

754

755

756 if (!InnerLoop) {

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

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

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

760 return false;

761 }

762 } else {

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

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

765

766

769 if (!InnerRedPhi ||

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

774 return false;

775 }

776 OuterInnerReductions.insert(&PHI);

777 OuterInnerReductions.insert(InnerRedPhi);

778 }

779 }

780 }

781 return true;

782}

783

784

785

786bool LoopInterchangeLegality::currentLimitations() {

788

789

790

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

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

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

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

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

803 " interchange currently.";

804 });

805 return true;

806 }

807

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

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

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

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

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

818 " interchanged currently.";

819 });

820 return true;

821 }

822

823 Inductions.clear();

824

825

826

827 Loop *CurLevelLoop = OuterLoop;

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

829

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

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

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

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

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

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

840 " interchange currently.";

841 });

842 return true;

843 }

844 }

845

846

847 if (!isLoopStructureUnderstood()) {

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

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

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

854 });

855 return true;

856 }

857

858 return false;

859}

860

861bool LoopInterchangeLegality::findInductions(

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

867 }

868 return !Inductions.empty();

869}

870

871

872

873

874static bool

879

880 if (PHI.getNumIncomingValues() > 1)

881 return false;

883 PHINode *PN = dyn_cast(U);

884 return !PN ||

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

886 })) {

887 return false;

888 }

889 }

890 return true;

891}

892

893

894

895

896

897

898

899

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

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

906 continue;

907

908

909

910

911

912

913

914

915

916

917

919 return false;

920 }

921 }

922 return true;

923}

924

925

926

927

928

929

930

931

932

935 return true;

936

937

938

940 return true;

941

942

943

944

945

946

947

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

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

953 return false;

954 }

955 }

956 return true;

957}

958

959bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,

960 unsigned OuterLoopId,

961 CharMatrix &DepMatrix) {

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

964 << " and OuterLoopId = " << OuterLoopId

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

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

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

971 });

972 return false;

973 }

974

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

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

978

979 if (CI->onlyWritesMemory())

980 continue;

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

983 << "safely.");

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

986 CI->getDebugLoc(),

987 CI->getParent())

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

989 });

990

991 return false;

992 }

993

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

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

996 return false;

997 }

998

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

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

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

1006 "in inner loop latch.";

1007 });

1008 return false;

1009 }

1010

1011

1012

1013 if (currentLimitations()) {

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

1015 return false;

1016 }

1017

1018

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

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

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

1026 "nested.";

1027 });

1028 return false;

1029 }

1030

1032 OuterInnerReductions)) {

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

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

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

1039 });

1040 return false;

1041 }

1042

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

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

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

1050 });

1051 return false;

1052 }

1053

1054 return true;

1055}

1056

1057int LoopInterchangeProfitability::getInstrOrderCost() {

1058 unsigned GoodOrder, BadOrder;

1059 BadOrder = GoodOrder = 0;

1063 unsigned NumOp = GEP->getNumOperands();

1064 bool FoundInnerInduction = false;

1065 bool FoundOuterInduction = false;

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

1067

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

1069 continue;

1070

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

1072 const SCEVAddRecExpr *AR = dyn_cast(OperandVal);

1073 if (!AR)

1074 continue;

1075

1076

1077

1078

1079

1080

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

1082

1083

1084 FoundInnerInduction = true;

1085 if (FoundOuterInduction) {

1086 GoodOrder++;

1087 break;

1088 }

1089 }

1090

1091

1092

1093

1094

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

1096

1097

1098 FoundOuterInduction = true;

1099 if (FoundInnerInduction) {

1100 BadOrder++;

1101 break;

1102 }

1103 }

1104 }

1105 }

1106 }

1107 }

1108 return GoodOrder - BadOrder;

1109}

1110

1111std::optional

1112LoopInterchangeProfitability::isProfitablePerLoopCacheAnalysis(

1114 std::unique_ptr &CC) {

1115

1116

1117

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

1119 unsigned InnerIndex = 0, OuterIndex = 0;

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

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

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

1124 if (InnerIndex < OuterIndex)

1125 return std::optional(true);

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

1127 "numbers to each loop");

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

1129 return std::nullopt;

1130 return std::optional(false);

1131 }

1132 return std::nullopt;

1133}

1134

1135std::optional

1136LoopInterchangeProfitability::isProfitablePerInstrOrderCost() {

1137

1138

1139

1140 int Cost = getInstrOrderCost();

1143 return std::optional(true);

1144

1145 return std::nullopt;

1146}

1147

1148std::optional LoopInterchangeProfitability::isProfitableForVectorization(

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

1150 for (auto &Row : DepMatrix) {

1151

1152

1153

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

1155 return std::optional(false);

1156

1157

1158

1159

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

1161 return std::optional(false);

1162 }

1163

1164

1165

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

1167}

1168

1169bool LoopInterchangeProfitability::isProfitable(

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

1171 unsigned OuterLoopId, CharMatrix &DepMatrix,

1173 std::unique_ptr &CC) {

1174

1175

1176

1177

1178

1179

1180

1181

1182 std::optional shouldInterchange =

1183 isProfitablePerLoopCacheAnalysis(CostMap, CC);

1184 if (!shouldInterchange.has_value()) {

1185 shouldInterchange = isProfitablePerInstrOrderCost();

1186 if (!shouldInterchange.has_value())

1187 shouldInterchange =

1188 isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix);

1189 }

1190 if (!shouldInterchange.has_value()) {

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

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

1196 "interchange.";

1197 });

1198 return false;

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

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

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

1205 "locality nor vectorization.";

1206 });

1207 return false;

1208 }

1209 return true;

1210}

1211

1212void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,

1213 Loop *InnerLoop) {

1214 for (Loop *L : *OuterLoop)

1215 if (L == InnerLoop) {

1216 OuterLoop->removeChildLoop(L);

1217 return;

1218 }

1220}

1221

1222

1223

1224

1225

1226

1227

1228

1229

1230

1231

1232

1233

1234

1235

1236

1237

1238

1239

1240

1241

1242

1243

1244

1245void LoopInterchangeTransform::restructureLoops(

1249

1250

1252 LI->changeLoopFor(OrigInnerPreHeader, OuterLoopParent);

1253

1254

1255 if (OuterLoopParent) {

1256

1257 removeChildLoop(OuterLoopParent, NewInner);

1258 removeChildLoop(NewInner, NewOuter);

1260 } else {

1261 removeChildLoop(NewInner, NewOuter);

1263 }

1267

1268

1270

1271

1272

1276

1277

1278

1281 for (BasicBlock *BB : OrigInnerBBs) {

1282

1284 continue;

1285

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

1288 else

1290 }

1291

1292

1293

1295 LI->changeLoopFor(OrigOuterPreHeader, NewOuter);

1296

1297

1299}

1300

1301bool LoopInterchangeTransform::transform() {

1302 bool Transformed = false;

1303

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

1307 auto &InductionPHIs = LIL.getInnerLoopInductions();

1308 if (InductionPHIs.empty()) {

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

1310 return false;

1311 }

1312

1314 for (PHINode *CurInductionPHI : InductionPHIs) {

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

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

1318 else

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

1321 }

1322

1323

1324

1325

1326

1330

1332 unsigned i = 0;

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

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

1335

1336

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

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

1341 "the loop nest!");

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

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

1347 U.set(NewI);

1348 }

1349

1350

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

1353 if (!OpI ||

1356 continue;

1357 WorkList.insert(OpI);

1358 }

1359 }

1360 };

1361

1362

1363 Instruction *CondI = dyn_cast(

1365 ->getCondition());

1366 if (CondI)

1367 WorkList.insert(CondI);

1368 MoveInstructions();

1369 for (Instruction *InnerIndexVar : InnerIndexVarList)

1370 WorkList.insert(cast(InnerIndexVar));

1371 MoveInstructions();

1372 }

1373

1374

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

1379 }

1380

1381

1382

1383

1384

1385

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

1388 if (InnerLoopPreHeader != OuterLoopHeader) {

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

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

1394 }

1395

1396 Transformed |= adjustLoopLinks();

1397 if (!Transformed) {

1399 return false;

1400 }

1401

1402 return true;

1403}

1404

1405

1406

1409

1412}

1413

1414

1416

1417

1421 I->removeFromParent();

1422

1423

1425

1426

1429}

1430

1431

1432

1433

1436 std::vectorDominatorTree::UpdateType &DTUpdates,

1437 bool MustUpdateOnce = true) {

1438 assert((!MustUpdateOnce ||

1441 return BB == OldBB;

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

1443 bool Changed = false;

1445 if (Op == OldBB) {

1446 Op.set(NewBB);

1447 Changed = true;

1448 }

1449

1450 if (Changed) {

1451 DTUpdates.push_back(

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

1453 DTUpdates.push_back(

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

1455 }

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

1457}

1458

1459

1464

1465

1466

1467

1468

1469

1470

1471

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

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

1475

1476

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

1478

1479

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

1481

1482

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

1484 IncIInnerMost->getParent() != InnerHeader)

1485 continue;

1486

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

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

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

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

1492 }) &&

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

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

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

1496 P.replaceAllUsesWith(IncI);

1497 P.eraseFromParent();

1498 }

1499

1503

1507

1508

1509

1510

1511

1512

1513 for (PHINode *P : LcssaInnerExit)

1515

1516

1517

1518 for (PHINode *P : LcssaInnerLatch)

1520

1521

1522

1523

1524

1525 if (OuterExit) {

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

1528 continue;

1529

1530

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

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

1533 continue;

1534

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

1538

1539

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

1541 if (Pred == OuterLatch)

1542 continue;

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

1544 }

1546 P.setIncomingValue(0, NewPhi);

1547 }

1548 }

1549

1550

1551

1552

1554}

1555

1556bool LoopInterchangeTransform::adjustLoopBranches() {

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

1558 std::vectorDominatorTree::UpdateType DTUpdates;

1559

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

1562

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

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

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

1566

1567

1568

1569

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

1572 OuterLoopPreHeader =

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

1575 InnerLoopPreHeader =

1577

1578

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

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

1584 BasicBlock *InnerLoopLatchPredecessor =

1586 BasicBlock *InnerLoopLatchSuccessor;

1587 BasicBlock *OuterLoopLatchSuccessor;

1588

1590 dyn_cast(OuterLoopLatch->getTerminator());

1592 dyn_cast(InnerLoopLatch->getTerminator());

1594 dyn_cast(OuterLoopHeader->getTerminator());

1596 dyn_cast(InnerLoopHeader->getTerminator());

1597

1598 if (!OuterLoopPredecessor || !InnerLoopLatchPredecessor ||

1599 !OuterLoopLatchBI || !InnerLoopLatchBI || !OuterLoopHeaderBI ||

1600 !InnerLoopHeaderBI)

1601 return false;

1602

1603 BranchInst *InnerLoopLatchPredecessorBI =

1604 dyn_cast(InnerLoopLatchPredecessor->getTerminator());

1605 BranchInst *OuterLoopPredecessorBI =

1606 dyn_cast(OuterLoopPredecessor->getTerminator());

1607

1608 if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)

1609 return false;

1611 if (!InnerLoopHeaderSuccessor)

1612 return false;

1613

1614

1615

1616

1617

1618 updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,

1619 InnerLoopPreHeader, DTUpdates, false);

1620

1621

1623

1624 updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, InnerLoopLatch,

1625 DTUpdates,

1626 false);

1627 }

1629 InnerLoopHeaderSuccessor, DTUpdates,

1630 false);

1631

1632

1634 OuterLoopHeader);

1635

1636 updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,

1637 OuterLoopPreHeader, DTUpdates);

1638

1639

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

1641 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);

1642 else

1643 InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);

1644

1645 updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,

1646 InnerLoopLatchSuccessor, DTUpdates);

1647

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

1649 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);

1650 else

1651 OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);

1652

1653 updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,

1654 OuterLoopLatchSuccessor, DTUpdates);

1655 updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,

1656 DTUpdates);

1657

1659 restructureLoops(OuterLoop, InnerLoop, InnerLoopPreHeader,

1660 OuterLoopPreHeader);

1661

1662 moveLCSSAPhis(InnerLoopLatchSuccessor, InnerLoopHeader, InnerLoopLatch,

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

1664 InnerLoop, LI);

1665

1666

1667 OuterLoopLatchSuccessor->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);

1668

1669 auto &OuterInnerReductions = LIL.getOuterInnerReductions();

1670

1673 if (OuterInnerReductions.contains(&PHI))

1675

1677 if (OuterInnerReductions.contains(&PHI))

1679

1680

1681

1682

1683 for (PHINode *PHI : OuterLoopPHIs) {

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

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

1687 }

1688 for (PHINode *PHI : InnerLoopPHIs) {

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

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

1692 }

1693

1694

1695 OuterLoopHeader->replacePhiUsesWith(InnerLoopPreHeader, OuterLoopPreHeader);

1696 OuterLoopHeader->replacePhiUsesWith(InnerLoopLatch, OuterLoopLatch);

1697 InnerLoopHeader->replacePhiUsesWith(OuterLoopPreHeader, InnerLoopPreHeader);

1698 InnerLoopHeader->replacePhiUsesWith(OuterLoopLatch, InnerLoopLatch);

1699

1700

1701

1702

1703

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

1709

1710 return true;

1711}

1712

1713bool LoopInterchangeTransform::adjustLoopLinks() {

1714

1715 bool Changed = adjustLoopBranches();

1716 if (Changed) {

1717

1718

1719

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

1722 swapBBContents(OuterLoopPreHeader, InnerLoopPreHeader);

1723 }

1724 return Changed;

1725}

1726

1733

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

1737 }

1738

1739

1743 std::unique_ptr CC =

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

1748 U.markLoopNestChanged(true);

1750}

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 bool hasMinimumLoopDepth(SmallVectorImpl< Loop * > &LoopList)

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 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 const unsigned MaxLoopNestDepth

static void printDepMatrix(CharMatrix &DepMatrix)

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

Swap instructions between BB1 and BB2 but keep terminators intact.

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.