LoopNestAnalysis.cpp Source File (original) (raw)

19using namespace llvm;

21#define DEBUG_TYPE "loopnest"

22#ifndef NDEBUG

24#endif

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

45}

49 return std::make_unique(Root, SE);

50}

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

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

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

65 << "\n";

66 });

67 return OuterLoopLatchCmp;

68}

73 CmpInst *InnerLoopGuardCmp =

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

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

79 << "\n";

80 });

81 return InnerLoopGuardCmp;

82}

85 const CmpInst *InnerLoopGuardCmp,

86 const CmpInst *OuterLoopLatchCmp,

87 std::optionalLoop::LoopBounds OuterLoopLB) {

89 bool IsAllowed =

91 if (!IsAllowed)

92 return false;

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

97 (isa(I) && &I != OuterLoopLatchCmp && &I != InnerLoopGuardCmp)) {

98 return false;

99 }

100 return true;

101}

102

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

106 PerfectLoopNest);

107}

108

109LoopNest::LoopNestEnum LoopNest::analyzeLoopNestForPerfectNest(

111

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

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

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

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

117

118

119

120

121

122

123

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

126 return InvalidLoopStructure;

127 }

128

129

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

139

140

141

142

143

144

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

148 OuterLoopLatchCmp, OuterLoopLB);

149 if (IsSafeInstr) {

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

152 << "is unsafe.\n";

153 });

154 }

155 return IsSafeInstr;

156 });

157 };

158

159

160

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

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

177

178 return PerfectLoopNest;

179}

180

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

205 auto OuterLoopLB = OuterLoop.getBounds(SE);

206

209

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

213 OuterLoopLB)) {

214 Instr.push_back(&I);

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

217 << "is unsafe.\n";

218 });

219 }

220 }

221 };

222

223

224

229

230 GetUnsafeInstructions(*OuterLoopHeader);

231 GetUnsafeInstructions(*OuterLoopLatch);

232 GetUnsafeInstructions(*InnerLoopExitBlock);

233

234 if (InnerLoopPreHeader != OuterLoopHeader) {

235 GetUnsafeInstructions(*InnerLoopPreHeader);

236 }

237 return Instr;

238}

239

244

246 if (PerfectNest.empty())

248

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

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

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

252 } else {

254 PerfectNest.clear();

255 }

256 }

257

258 return LV;

259}

260

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();

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;

282 ++CurrentDepth;

283 }

284

285 return CurrentDepth;

286}

287

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

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

308 PredBB = BB;

310 }

311

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

313}

314

317

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

320 return false;

321

322

324 return false;

325

331

332

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

335 return false;

336

337

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

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

340 return PN.getNumIncomingValues() == 1;

341 });

342 };

343

344

345

346

347

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

349 return BB.getFirstNonPHI() == BB.getTerminator() &&

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

360

361 if (OuterLoopHeader != InnerLoopPreHeader) {

364

365

366 if (&SingleSucc != InnerLoopPreHeader) {

368

370 return false;

371

372 bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);

373

374

375

377 const BasicBlock *PotentialInnerPreHeader = Succ;

378 const BasicBlock *PotentialOuterLatch = Succ;

379

380

381

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

383 PotentialInnerPreHeader =

385 PotentialOuterLatch =

387 }

388

389 if (PotentialInnerPreHeader == InnerLoopPreHeader)

390 continue;

391 if (PotentialOuterLatch == OuterLoopLatch)

392 continue;

393

394

395

396

397

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

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

400

401

402

403

404 ExtraPhiBlock = Succ;

405 continue;

406 }

407

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

419

420 if ((!ExtraPhiBlock ||

422 ExtraPhiBlock) != ExtraPhiBlock) &&

424 OuterLoopLatch) != OuterLoopLatch)) {

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

436

438 OS << "IsPerfect=";

440 OS << "true";

441 else

442 OS << "false";

445 OS << ", Loops: ( ";

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

448 OS << ")";

449

450 return OS;

451}

452

453

454

455

456

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

462

464}

BlockVerifier::State From

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

#define DEBUG_WITH_TYPE(TYPE,...)

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

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

static CmpInst * getOuterLoopLatchCmp(const Loop &OuterLoop)

static CmpInst * getInnerLoopGuardCmp(const Loop &InnerLoop)

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

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

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

static const char * VerboseDebug

This file defines the interface for the loop nest analysis.

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

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

LLVM Basic Block Representation.

const BasicBlock * getUniqueSuccessor() const

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

const BasicBlock * getUniquePredecessor() const

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

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Conditional or Unconditional Branch instruction.

iterator_range< succ_op_iterator > successors()

bool isConditional() const

Value * getCondition() const

This class is the base class for the comparison instructions.

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

bool isOutermost() const

Return true if the loop does not have a parent (natural) 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.

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

Return the loops contained entirely within this loop.

BlockT * getHeader() const

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.

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

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.

unsigned getNestDepth() const

Return the loop nest depth (i.e.

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

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

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

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

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

Construct a LoopNest object.

unsigned getMaxPerfectDepth() const

Return the maximum perfect nesting depth.

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

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

Loop & getOutermostLoop() const

Return the outermost loop in the loop nest.

Represents a single loop in the control flow graph.

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

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

BranchInst * getLoopGuardBranch() const

Return the loop guard branch, if it exists.

StringRef getName() const

bool isLoopSimplifyForm() const

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

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 main scalar evolution driver.

size_type count(ConstPtrType Ptr) const

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

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

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

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

void push_back(const T &Elt)

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

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

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

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

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

Wrapper function to append range R to container C.

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.

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

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

iterator_range< bf_iterator< T > > breadth_first(const T &G)

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

iterator_range< df_iterator< T > > depth_first(const T &G)

A special type used by analysis passes to provide an address that identifies that particular analysis...

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