LoopNestAnalysis.cpp

1//===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8///

9/// \file

10/// The implementation for the loop nest analysis.

11///

12//===----------------------------------------------------------------------===//

13

14#include "llvm/Analysis/LoopNestAnalysis.h"

15#include "llvm/ADT/BreadthFirstIterator.h"

16#include "llvm/ADT/DepthFirstIterator.h"

17#include "llvm/Analysis/ValueTracking.h"

18

19using namespace llvm;

20

21 #define DEBUG_TYPE "loopnest"

22#ifndef NDEBUG

23 static const char *VerboseDebug = DEBUG_TYPE "-verbose";

24#endif

25

26/// Determine whether the loops structure violates basic requirements for

27/// perfect nesting:

28/// - the inner loop should be the outer loop's only child

29/// - the outer loop header should 'flow' into the inner loop preheader

30/// or jump around the inner loop to the outer loop latch

31/// - if the inner loop latch exits the inner loop, it should 'flow' into

32/// the outer loop latch.

33/// Returns true if the loop structure satisfies the basic requirements and

34/// false otherwise.

35static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,

36 ScalarEvolution &SE);

37

38//===----------------------------------------------------------------------===//

39// LoopNest implementation

40//

41

42 LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)

43 : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {

44 append_range(Loops, breadth_first(&Root));

45}

46

47 std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,

48 ScalarEvolution &SE) {

49 return std::make_unique<LoopNest>(Root, SE);

50}

51

52 static CmpInst *getOuterLoopLatchCmp(const Loop &OuterLoop) {

53

54 const BasicBlock *Latch = OuterLoop.getLoopLatch();

55 assert(Latch && "Expecting a valid loop latch");

56

57 const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());

58 assert(BI && BI->isConditional() &&

59 "Expecting loop latch terminator to be a branch instruction");

60

61 CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());

62 DEBUG_WITH_TYPE(

63 VerboseDebug, if (OuterLoopLatchCmp) {

64 dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp

65 << "\n";

66 });

67 return OuterLoopLatchCmp;

68}

69

70 static CmpInst *getInnerLoopGuardCmp(const Loop &InnerLoop) {

71

72 BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch();

73 CmpInst *InnerLoopGuardCmp =

74 (InnerGuard) ? dyn_cast<CmpInst>(InnerGuard->getCondition()) : nullptr;

75

76 DEBUG_WITH_TYPE(

77 VerboseDebug, if (InnerLoopGuardCmp) {

78 dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp

79 << "\n";

80 });

81 return InnerLoopGuardCmp;

82}

83

84 static bool checkSafeInstruction(const Instruction &I,

85 const CmpInst *InnerLoopGuardCmp,

86 const CmpInst *OuterLoopLatchCmp,

87 std::optional<Loop::LoopBounds> OuterLoopLB) {

88

89 bool IsAllowed =

90 isSafeToSpeculativelyExecute(&I) || isa<PHINode>(I) || isa<BranchInst>(I);

91 if (!IsAllowed)

92 return false;

93 // The only binary instruction allowed is the outer loop step instruction,

94 // the only comparison instructions allowed are the inner loop guard

95 // compare instruction and the outer loop latch compare instruction.

96 if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||

97 (isa<CmpInst>(I) && &I != OuterLoopLatchCmp && &I != InnerLoopGuardCmp)) {

98 return false;

99 }

100 return true;

101}

102

103 bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,

104 ScalarEvolution &SE) {

105 return (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE) ==

106 PerfectLoopNest);

107}

108

109LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest(

110 const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {

111

112 assert(!OuterLoop.isInnermost() && "Outer loop should have subloops");

113 assert(!InnerLoop.isOutermost() && "Inner loop should have a parent");

114 LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName()

115 << "' and '" << InnerLoop.getName()

116 << "' are perfectly nested.\n");

117

118 // Determine whether the loops structure satisfies the following requirements:

119 // - the inner loop should be the outer loop's only child

120 // - the outer loop header should 'flow' into the inner loop preheader

121 // or jump around the inner loop to the outer loop latch

122 // - if the inner loop latch exits the inner loop, it should 'flow' into

123 // the outer loop latch.

124 if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {

125 LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");

126 return InvalidLoopStructure;

127 }

128

129 // Bail out if we cannot retrieve the outer loop bounds.

130 auto OuterLoopLB = OuterLoop.getBounds(SE);

131 if (OuterLoopLB == std::nullopt) {

132 LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "

133 << OuterLoop << "\n";);

134 return OuterLoopLowerBoundUnknown;

135 }

136

137 CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);

138 CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);

139

140 // Determine whether instructions in a basic block are one of:

141 // - the inner loop guard comparison

142 // - the outer loop latch comparison

143 // - the outer loop induction variable increment

144 // - a phi node, a cast or a branch

145 auto containsOnlySafeInstructions = [&](const BasicBlock &BB) {

146 return llvm::all_of(BB, [&](const Instruction &I) {

147 bool IsSafeInstr = checkSafeInstruction(I, InnerLoopGuardCmp,

148 OuterLoopLatchCmp, OuterLoopLB);

149 if (IsSafeInstr) {

150 DEBUG_WITH_TYPE(VerboseDebug, {

151 dbgs() << "Instruction: " << I << "\nin basic block:" << BB

152 << "is unsafe.\n";

153 });

154 }

155 return IsSafeInstr;

156 });

157 };

158

159 // Check the code surrounding the inner loop for instructions that are deemed

160 // unsafe.

161 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();

162 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();

163 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();

164

165 if (!containsOnlySafeInstructions(*OuterLoopHeader) ||

166 !containsOnlySafeInstructions(*OuterLoopLatch) ||

167 (InnerLoopPreHeader != OuterLoopHeader &&

168 !containsOnlySafeInstructions(*InnerLoopPreHeader)) ||

169 !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) {

170 LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is "

171 "unsafe\n";);

172 return ImperfectLoopNest;

173 }

174

175 LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '"

176 << InnerLoop.getName() << "' are perfectly nested.\n");

177

178 return PerfectLoopNest;

179}

180

181 LoopNest::InstrVectorTy LoopNest::getInterveningInstructions(

182 const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) {

183 InstrVectorTy Instr;

184 switch (analyzeLoopNestForPerfectNest(OuterLoop, InnerLoop, SE)) {

185 case PerfectLoopNest:

186 LLVM_DEBUG(dbgs() << "The loop Nest is Perfect, returning empty "

187 "instruction vector. \n";);

188 return Instr;

189

190 case InvalidLoopStructure:

191 LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure. "

192 "Instruction vector is empty.\n";);

193 return Instr;

194

195 case OuterLoopLowerBoundUnknown:

196 LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "

197 << OuterLoop << "\nInstruction vector is empty.\n";);

198 return Instr;

199

200 case ImperfectLoopNest:

201 break;

202 }

203

204 // Identify the outer loop latch comparison instruction.

205 auto OuterLoopLB = OuterLoop.getBounds(SE);

206

207 CmpInst *OuterLoopLatchCmp = getOuterLoopLatchCmp(OuterLoop);

208 CmpInst *InnerLoopGuardCmp = getInnerLoopGuardCmp(InnerLoop);

209

210 auto GetUnsafeInstructions = [&](const BasicBlock &BB) {

211 for (const Instruction &I : BB) {

212 if (!checkSafeInstruction(I, InnerLoopGuardCmp, OuterLoopLatchCmp,

213 OuterLoopLB)) {

214 Instr.push_back(&I);

215 DEBUG_WITH_TYPE(VerboseDebug, {

216 dbgs() << "Instruction: " << I << "\nin basic block:" << BB

217 << "is unsafe.\n";

218 });

219 }

220 }

221 };

222

223 // Check the code surrounding the inner loop for instructions that are deemed

224 // unsafe.

225 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();

226 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();

227 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();

228 const BasicBlock *InnerLoopExitBlock = InnerLoop.getExitBlock();

229

230 GetUnsafeInstructions(*OuterLoopHeader);

231 GetUnsafeInstructions(*OuterLoopLatch);

232 GetUnsafeInstructions(*InnerLoopExitBlock);

233

234 if (InnerLoopPreHeader != OuterLoopHeader) {

235 GetUnsafeInstructions(*InnerLoopPreHeader);

236 }

237 return Instr;

238}

239

240SmallVector<LoopVectorTy, 4>

241 LoopNest::getPerfectLoops(ScalarEvolution &SE) const {

242 SmallVector<LoopVectorTy, 4> LV;

243 LoopVectorTy PerfectNest;

244

245 for (Loop *L : depth_first(const_cast<Loop *>(Loops.front()))) {

246 if (PerfectNest.empty())

247 PerfectNest.push_back(L);

248

249 auto &SubLoops = L->getSubLoops();

250 if (SubLoops.size() == 1 && arePerfectlyNested(*L, *SubLoops.front(), SE)) {

251 PerfectNest.push_back(SubLoops.front());

252 } else {

253 LV.push_back(PerfectNest);

254 PerfectNest.clear();

255 }

256 }

257

258 return LV;

259}

260

261 unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) {

262 LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '"

263 << Root.getName() << "'\n");

264

265 const Loop *CurrentLoop = &Root;

266 const auto *SubLoops = &CurrentLoop->getSubLoops();

267 unsigned CurrentDepth = 1;

268

269 while (SubLoops->size() == 1) {

270 const Loop *InnerLoop = SubLoops->front();

271 if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) {

272 LLVM_DEBUG({

273 dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName()

274 << "' is not perfectly nested with loop '"

275 << InnerLoop->getName() << "'\n";

276 });

277 break;

278 }

279

280 CurrentLoop = InnerLoop;

281 SubLoops = &CurrentLoop->getSubLoops();

282 ++CurrentDepth;

283 }

284

285 return CurrentDepth;

286}

287

288 const BasicBlock &LoopNest::skipEmptyBlockUntil(const BasicBlock *From,

289 const BasicBlock *End,

290 bool CheckUniquePred) {

291 assert(From && "Expecting valid From");

292 assert(End && "Expecting valid End");

293

294 if (From == End || !From->getUniqueSuccessor())

295 return *From;

296

297 auto IsEmpty = [](const BasicBlock *BB) {

298 return (BB->size() == 1);

299 };

300

301 // Visited is used to avoid running into an infinite loop.

302 SmallPtrSet<const BasicBlock *, 4> Visited;

303 const BasicBlock *BB = From->getUniqueSuccessor();

304 const BasicBlock *PredBB = From;

305 while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB) &&

306 (!CheckUniquePred || BB->getUniquePredecessor())) {

307 Visited.insert(BB);

308 PredBB = BB;

309 BB = BB->getUniqueSuccessor();

310 }

311

312 return (BB == End) ? *End : *PredBB;

313}

314

315 static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,

316 ScalarEvolution &SE) {

317 // The inner loop must be the only outer loop's child.

318 if ((OuterLoop.getSubLoops().size() != 1) ||

319 (InnerLoop.getParentLoop() != &OuterLoop))

320 return false;

321

322 // We expect loops in normal form which have a preheader, header, latch...

323 if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())

324 return false;

325

326 const BasicBlock *OuterLoopHeader = OuterLoop.getHeader();

327 const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch();

328 const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader();

329 const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch();

330 const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock();

331

332 // We expect rotated loops. The inner loop should have a single exit block.

333 if (OuterLoop.getExitingBlock() != OuterLoopLatch ||

334 InnerLoop.getExitingBlock() != InnerLoopLatch || !InnerLoopExit)

335 return false;

336

337 // Returns whether the block `ExitBlock` contains at least one LCSSA Phi node.

338 auto ContainsLCSSAPhi = [](const BasicBlock &ExitBlock) {

339 return any_of(ExitBlock.phis(), [](const PHINode &PN) {

340 return PN.getNumIncomingValues() == 1;

341 });

342 };

343

344 // Returns whether the block `BB` qualifies for being an extra Phi block. The

345 // extra Phi block is the additional block inserted after the exit block of an

346 // "guarded" inner loop which contains "only" Phi nodes corresponding to the

347 // LCSSA Phi nodes in the exit block.

348 auto IsExtraPhiBlock = [&](const BasicBlock &BB) {

349 return &*BB.getFirstNonPHIIt() == BB.getTerminator() &&

350 all_of(BB.phis(), [&](const PHINode &PN) {

351 return all_of(PN.blocks(), [&](const BasicBlock *IncomingBlock) {

352 return IncomingBlock == InnerLoopExit ||

353 IncomingBlock == OuterLoopHeader;

354 });

355 });

356 };

357

358 const BasicBlock *ExtraPhiBlock = nullptr;

359 // Ensure the only branch that may exist between the loops is the inner loop

360 // guard.

361 if (OuterLoopHeader != InnerLoopPreHeader) {

362 const BasicBlock &SingleSucc =

363 LoopNest::skipEmptyBlockUntil(OuterLoopHeader, InnerLoopPreHeader);

364

365 // no conditional branch present

366 if (&SingleSucc != InnerLoopPreHeader) {

367 const BranchInst *BI = dyn_cast<BranchInst>(SingleSucc.getTerminator());

368

369 if (!BI || BI != InnerLoop.getLoopGuardBranch())

370 return false;

371

372 bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);

373

374 // The successors of the inner loop guard should be the inner loop

375 // preheader or the outer loop latch possibly through empty blocks.

376 for (const BasicBlock *Succ : BI->successors()) {

377 const BasicBlock *PotentialInnerPreHeader = Succ;

378 const BasicBlock *PotentialOuterLatch = Succ;

379

380 // Ensure the inner loop guard successor is empty before skipping

381 // blocks.

382 if (Succ->size() == 1) {

383 PotentialInnerPreHeader =

384 &LoopNest::skipEmptyBlockUntil(Succ, InnerLoopPreHeader);

385 PotentialOuterLatch =

386 &LoopNest::skipEmptyBlockUntil(Succ, OuterLoopLatch);

387 }

388

389 if (PotentialInnerPreHeader == InnerLoopPreHeader)

390 continue;

391 if (PotentialOuterLatch == OuterLoopLatch)

392 continue;

393

394 // If `InnerLoopExit` contains LCSSA Phi instructions, additional block

395 // may be inserted before the `OuterLoopLatch` to which `BI` jumps. The

396 // loops are still considered perfectly nested if the extra block only

397 // contains Phi instructions from InnerLoopExit and OuterLoopHeader.

398 if (InnerLoopExitContainsLCSSA && IsExtraPhiBlock(*Succ) &&

399 Succ->getSingleSuccessor() == OuterLoopLatch) {

400 // Points to the extra block so that we can reference it later in the

401 // final check. We can also conclude that the inner loop is

402 // guarded and there exists LCSSA Phi node in the exit block later if

403 // we see a non-null `ExtraPhiBlock`.

404 ExtraPhiBlock = Succ;

405 continue;

406 }

407

408 DEBUG_WITH_TYPE(VerboseDebug, {

409 dbgs() << "Inner loop guard successor " << Succ->getName()

410 << " doesn't lead to inner loop preheader or "

411 "outer loop latch.\n";

412 });

413 return false;

414 }

415 }

416 }

417

418 // Ensure the inner loop exit block lead to the outer loop latch possibly

419 // through empty blocks.

420 if ((!ExtraPhiBlock ||

421 &LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(),

422 ExtraPhiBlock) != ExtraPhiBlock) &&

423 (&LoopNest::skipEmptyBlockUntil(InnerLoop.getExitBlock(),

424 OuterLoopLatch) != OuterLoopLatch)) {

425 DEBUG_WITH_TYPE(

426 VerboseDebug,

427 dbgs() << "Inner loop exit block " << *InnerLoopExit

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

429 return false;

430 }

431

432 return true;

433}

434

435AnalysisKey LoopNestAnalysis::Key;

436

437 raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {

438 OS << "IsPerfect=";

439 if (LN.getMaxPerfectDepth() == LN.getNestDepth())

440 OS << "true";

441 else

442 OS << "false";

443 OS << ", Depth=" << LN.getNestDepth();

444 OS << ", OutermostLoop: " << LN.getOutermostLoop().getName();

445 OS << ", Loops: ( ";

446 for (const Loop *L : LN.getLoops())

447 OS << L->getName() << " ";

448 OS << ")";

449

450 return OS;

451}

452

453//===----------------------------------------------------------------------===//

454// LoopNestPrinterPass implementation

455//

456

457 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,

458 LoopStandardAnalysisResults &AR,

459 LPMUpdater &U) {

460 if (auto LN = LoopNest::getLoopNest(L, AR.SE))

461 OS << *LN << "\n";

462

463 return PreservedAnalyses::all();

464}

assert

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

BreadthFirstIterator.h

This file builds on the ADT/GraphTraits.h file to build a generic breadth first graph iterator.

DepthFirstIterator.h

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

DEBUG_TYPE

#define DEBUG_TYPE

Definition GenericCycleImpl.h:31

getOuterLoopLatchCmp

static CmpInst * getOuterLoopLatchCmp(const Loop &OuterLoop)

Definition LoopNestAnalysis.cpp:52

getInnerLoopGuardCmp

static CmpInst * getInnerLoopGuardCmp(const Loop &InnerLoop)

Definition LoopNestAnalysis.cpp:70

checkSafeInstruction

static bool checkSafeInstruction(const Instruction &I, const CmpInst *InnerLoopGuardCmp, const CmpInst *OuterLoopLatchCmp, std::optional< Loop::LoopBounds > OuterLoopLB)

Definition LoopNestAnalysis.cpp:84

checkLoopsStructure

static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)

Determine whether the loops structure violates basic requirements for perfect nesting:

Definition LoopNestAnalysis.cpp:315

VerboseDebug

static const char * VerboseDebug

Definition LoopNestAnalysis.cpp:23

LoopNestAnalysis.h

This file defines the interface for the loop nest analysis.

I

#define I(x, y, z)

Definition MD5.cpp:58

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition Debug.h:114

DEBUG_WITH_TYPE

#define DEBUG_WITH_TYPE(TYPE,...)

DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug information.

Definition Debug.h:72

ValueTracking.h

llvm::BasicBlock

LLVM Basic Block Representation.

Definition BasicBlock.h:62

llvm::BasicBlock::getUniqueSuccessor

LLVM_ABI const BasicBlock * getUniqueSuccessor() const

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

Definition BasicBlock.cpp:475

llvm::BasicBlock::getUniquePredecessor

LLVM_ABI const BasicBlock * getUniquePredecessor() const

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

Definition BasicBlock.cpp:445

llvm::BasicBlock::getTerminator

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

Definition BasicBlock.h:233

llvm::BranchInst

Conditional or Unconditional Branch instruction.

Definition Instructions.h:3058

llvm::BranchInst::successors

iterator_range< succ_op_iterator > successors()

Definition Instructions.h:3163

llvm::BranchInst::isConditional

bool isConditional() const

Definition Instructions.h:3132

llvm::BranchInst::getCondition

Value * getCondition() const

Definition Instructions.h:3134

llvm::CmpInst

This class is the base class for the comparison instructions.

Definition InstrTypes.h:664

llvm::Instruction

Definition Instruction.h:69

llvm::LPMUpdater

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

Definition LoopPassManager.h:226

llvm::LoopBase::isOutermost

bool isOutermost() const

Return true if the loop does not have a parent (natural) loop.

Definition GenericLoopInfo.h:170

llvm::LoopBase::getLoopLatch

BlockT * getLoopLatch() const

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

Definition GenericLoopInfoImpl.h:256

llvm::LoopBase::isInnermost

bool isInnermost() const

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

Definition GenericLoopInfo.h:167

llvm::LoopBase::getSubLoops

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

Return the loops contained entirely within this loop.

Definition GenericLoopInfo.h:145

llvm::LoopBase::getHeader

BlockT * getHeader() const

Definition GenericLoopInfo.h:90

llvm::LoopBase::getExitBlock

BlockT * getExitBlock() const

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

Definition GenericLoopInfoImpl.h:107

llvm::LoopBase::getLoopPreheader

BlockT * getLoopPreheader() const

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

Definition GenericLoopInfoImpl.h:210

llvm::LoopBase::getExitingBlock

BlockT * getExitingBlock() const

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

Definition GenericLoopInfoImpl.h:48

llvm::LoopBase::getParentLoop

LoopT * getParentLoop() const

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

Definition GenericLoopInfo.h:99

llvm::LoopNestPrinterPass::run

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

Definition LoopNestAnalysis.cpp:457

llvm::LoopNest

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

Definition LoopNestAnalysis.h:29

llvm::LoopNest::skipEmptyBlockUntil

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

Definition LoopNestAnalysis.cpp:288

llvm::LoopNest::getLoops

ArrayRef< Loop * > getLoops() const

Get the loops in the nest.

Definition LoopNestAnalysis.h:118

llvm::LoopNest::getNestDepth

unsigned getNestDepth() const

Return the loop nest depth (i.e.

Definition LoopNestAnalysis.h:156

llvm::LoopNest::Loops

LoopVectorTy Loops

Definition LoopNestAnalysis.h:185

llvm::LoopNest::LoopNest

LoopNest()=delete

llvm::LoopNest::getPerfectLoops

SmallVector< LoopVectorTy, 4 > getPerfectLoops(ScalarEvolution &SE) const

Retrieve a vector of perfect loop nests contained in the current loop nest.

Definition LoopNestAnalysis.cpp:241

llvm::LoopNest::arePerfectlyNested

static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)

Return true if the given loops OuterLoop and InnerLoop are perfectly nested with respect to each othe...

Definition LoopNestAnalysis.cpp:103

llvm::LoopNest::getInterveningInstructions

static InstrVectorTy getInterveningInstructions(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE)

Return a vector of instructions that prevent the LoopNest given by loops OuterLoop and InnerLoop from...

Definition LoopNestAnalysis.cpp:181

llvm::LoopNest::MaxPerfectDepth

const unsigned MaxPerfectDepth

Definition LoopNestAnalysis.h:184

llvm::LoopNest::getLoopNest

static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)

Construct a LoopNest object.

Definition LoopNestAnalysis.cpp:47

llvm::LoopNest::InstrVectorTy

SmallVector< const Instruction * > InstrVectorTy

Definition LoopNestAnalysis.h:31

llvm::LoopNest::getMaxPerfectDepth

unsigned getMaxPerfectDepth() const

Return the maximum perfect nesting depth.

Definition LoopNestAnalysis.h:164

llvm::LoopNest::getMaxPerfectDepth

static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE)

Return the maximum nesting depth of the loop nest rooted by loop Root.

Definition LoopNestAnalysis.cpp:261

llvm::LoopNest::getOutermostLoop

Loop & getOutermostLoop() const

Return the outermost loop in the loop nest.

Definition LoopNestAnalysis.h:81

llvm::Loop

Represents a single loop in the control flow graph.

Definition LoopInfo.h:40

llvm::Loop::getBounds

std::optional< LoopBounds > getBounds(ScalarEvolution &SE) const

Return the struct LoopBounds collected if all struct members are found, else std::nullopt.

Definition LoopInfo.cpp:288

llvm::Loop::getLoopGuardBranch

BranchInst * getLoopGuardBranch() const

Return the loop guard branch, if it exists.

Definition LoopInfo.cpp:368

llvm::Loop::getName

StringRef getName() const

Definition LoopInfo.h:389

llvm::Loop::isLoopSimplifyForm

bool isLoopSimplifyForm() const

Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...

Definition LoopInfo.cpp:480

llvm::PHINode

Definition Instructions.h:2639

llvm::PreservedAnalyses

A set of analyses that are preserved following a run of a transformation pass.

Definition Analysis.h:112

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition Analysis.h:118

llvm::ScalarEvolution

The main scalar evolution driver.

Definition ScalarEvolution.h:448

llvm::SmallPtrSetImpl::count

size_type count(ConstPtrType Ptr) const

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

Definition SmallPtrSet.h:455

llvm::SmallPtrSetImpl::insert

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

Definition SmallPtrSet.h:389

llvm::SmallPtrSet

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

Definition SmallPtrSet.h:527

llvm::SmallVectorImpl::clear

void clear()

Definition SmallVector.h:611

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition SmallVector.h:417

llvm::SmallVectorTemplateCommon::empty

bool empty() const

Definition SmallVector.h:83

llvm::SmallVector

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

Definition SmallVector.h:1203

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition raw_ostream.h:53

llvm::ISD::BasicBlock

@ BasicBlock

Various leaf nodes.

Definition ISDOpcodes.h:81

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition AddressRanges.h:18

llvm::all_of

bool all_of(R &&range, UnaryPredicate P)

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

Definition STLExtras.h:1725

llvm::dyn_cast

decltype(auto) dyn_cast(const From &Val)

dyn_cast<X> - Return the argument parameter cast to the specified type.

Definition Casting.h:643

llvm::append_range

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

Wrapper function to append range R to container C.

Definition STLExtras.h:2136

llvm::isSafeToSpeculativelyExecute

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

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

Definition ValueTracking.cpp:6958

llvm::LoopAnalysisManager

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

Definition LoopAnalysisManager.h:75

llvm::any_of

bool any_of(R &&range, UnaryPredicate P)

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

Definition STLExtras.h:1732

llvm::LoopVectorTy

SmallVector< Loop *, 8 > LoopVectorTy