LoopInfo.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_LOOPINFO_H

14#define LLVM_ANALYSIS_LOOPINFO_H

21#include

22#include

24namespace llvm {

26class DominatorTree;

27class InductionDescriptor;

28class LoopInfo;

29class Loop;

30class MemorySSAUpdater;

31class ScalarEvolution;

32class raw_ostream;

35extern template class LoopBase<BasicBlock, Loop>;

40public:

46 public:

57 explicit operator bool() const { return Start && End; }

58 };

61 bool isLoopInvariant(const Value *V) const;

65 bool hasLoopInvariantOperands(const Instruction *I) const;

77 bool makeLoopInvariant(Value *V, bool &Changed,

92 bool makeLoopInvariant(Instruction *I, bool &Changed,

100

101

102

103

104 PHINode *getCanonicalInductionVariable() const;

105

106

107 ICmpInst *getLatchCmpInst() const;

108

109

110

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

153

154

155

156

157

158

159

160 static std::optionalLoop::LoopBounds

162

163

165

166

168

169

170

172

173

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

210

211

212

213

214

216

217

219

220 private:

223 : L(Loop), InitialIVValue(I), StepInst(SI), StepValue(SV),

224 FinalIVValue(F), SE(SE) {}

225

226 const Loop &L;

227

228

229 Value &InitialIVValue;

230

231

233

234

235

236 Value *StepValue;

237

238

239 Value &FinalIVValue;

240

242 };

243

244

245

246 std::optional getBounds(ScalarEvolution &SE) const;

247

248

249

250

251

252

253

254

255 PHINode *getInductionVariable(ScalarEvolution &SE) const;

256

257

258

259 bool getInductionDescriptor(ScalarEvolution &SE,

260 InductionDescriptor &IndDesc) const;

261

262

263

264

265

266

267

268

269 bool isAuxiliaryInductionVariable(PHINode &AuxIndVar,

270 ScalarEvolution &SE) const;

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290 BranchInst *getLoopGuardBranch() const;

291

292

293

294

295 bool isGuarded() const { return (getLoopGuardBranch() != nullptr); }

296

297

298

299

300

301

303 assert(!isInvalid() && "Loop not in a valid state!");

305 return Latch && isLoopExiting(Latch);

306 }

307

308

309

311

312

313

314 bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens = true) const;

315

316

317

318

320 bool IgnoreTokens = true) const;

321

322

323

324 bool isLoopSimplifyForm() const;

325

326

327 bool isSafeToClone() const;

328

329

330

331

332

333

334

335

336

337

338

339

340

341 bool isAnnotatedParallel() const;

342

343

344

345

346

347

348

349 MDNode *getLoopID() const;

350

351

352

353

354

355

356

357 void setLoopID(MDNode *LoopID) const;

358

359

360

361

362

363

364

365 void setLoopAlreadyUnrolled();

366

367

368 void setLoopMustProgress();

369

370 void dump() const;

371 void dumpVerbose() const;

372

373

374

375

376

377

378 DebugLoc getStartLoc() const;

379

380

381 LocRange getLocRange() const;

382

383

384

385

386 std::string getLocStr() const;

387

389 if (BasicBlock *Header = getHeader())

390 if (Header->hasName())

391 return Header->getName();

392 return "";

393 }

394

395private:

397

401 ~Loop() = default;

402};

403

404

405extern template class LoopInfoBase<BasicBlock, Loop>;

406

409

411

412 void operator=(const LoopInfo &) = delete;

414

415public:

418

421 BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));

422 return *this;

423 }

424

425

428

429

430

431

432

433

434

436

437

438

440

441

443 if ()

444 return true;

445

446

447 if (I->getParent() == From->getParent())

448 return true;

449

450

451 Loop *ToLoop = getLoopFor(I->getParent());

452 if (!ToLoop)

453 return true;

454

455

456

457 return ToLoop->contains(getLoopFor(From->getParent()));

458 }

459

460

461

462

463

464

467 "Can't reason about IPO!");

468

470 auto *NewBB = NewLoc->getParent();

471

472

473

474 if (OldBB == NewBB)

475 return true;

476

477 auto *OldLoop = getLoopFor(OldBB);

478 auto *NewLoop = getLoopFor(NewBB);

479

480 if (OldLoop == NewLoop)

481 return true;

482

483

484

485 auto Contains = [](const Loop *Outer, const Loop *Inner) {

486 return !Outer || Outer->contains(Inner);

487 };

488

489

490

491

492

493

494

495

496 if (!Contains(NewLoop, OldLoop)) {

497 for (Use &U : Inst->uses()) {

498 auto *UI = cast(U.getUser());

499 auto *UBB = isa(UI) ? cast(UI)->getIncomingBlock(U)

500 : UI->getParent();

501 if (UBB != NewBB && getLoopFor(UBB) != NewLoop)

502 return false;

503 }

504 }

505

506

507

508

509 if (!Contains(OldLoop, NewLoop)) {

510

511 if (isa(Inst))

512 return false;

513

515 auto *DefI = dyn_cast(U.get());

516 if (!DefI)

517 return false;

518

519

520

521

522 auto *DefBlock = DefI->getParent();

523 if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop)

524 return false;

525 }

526 }

527

528 return true;

529 }

530

531

532

533

534

535 bool wouldBeOutOfLoopUseRequiringLCSSA(const Value *V,

537};

538

539

540

541

542

543

545

546

550

554};

555

559

563};

564

565

569

570public:

572

574};

575

576

579

580public:

584};

585

586

590};

591

592

595

596public:

597 static char ID;

598

600

603

604

606

607 void verifyAnalysis() const override;

608

610

612

613 void getAnalysisUsage(AnalysisUsage &AU) const override;

614};

615

616

617void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner = "");

618

619

620

622

623

624

625

626

627

629

631 StringRef Name);

632

633

635

636

638 StringRef Name);

639

640

641

643

644

645

646

647

648

650 StringRef Name);

651

652

654

655

656

657

659

660

661

663

664

665

667

668

669

670

671

672

673

674

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

696}

697

698#endif

BlockVerifier::State From

static bool runOnFunction(Function &F, bool PostInlining)

This file defines the little GraphTraits template class that should be specialized by classes that...

This header defines various interfaces for pass management in LLVM.

Loop::LoopBounds::Direction Direction

StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)

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

API to communicate dependencies between analyses during invalidation.

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

Represent the analysis usage information of a pass.

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

LLVM Basic Block Representation.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

Core dominator tree base class.

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

FunctionPass class - This class is used to implement most global optimizations.

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

const Function * getFunction() const

Return the function this instruction belongs to.

This is an important class for using LLVM in a threaded context.

Analysis pass that exposes the LoopInfo for a function.

Instances of this class are used to represent loops that are detected in the flow graph.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

This class builds and contains all of the top-level loop structures in the specified function.

std::vector< Loop * >::const_iterator iterator

iterator/begin/end - The interface to the top-level loops in the current function.

The legacy pass manager's analysis pass to compute loop information.

const LoopInfo & getLoopInfo() const

void releaseMemory() override

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

LoopInfo & operator=(LoopInfo &&RHS)

LoopInfo(const DominatorTreeBase< BasicBlock, false > &DomTree)

bool replacementPreservesLCSSAForm(Instruction *From, Value *To)

Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.

bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc)

Checks if moving a specific instruction can break LCSSA in any loop.

Printer pass for the LoopAnalysis results.

LoopPrinterPass(raw_ostream &OS)

A range representing the start and end location of a loop.

LocRange(DebugLoc Start, DebugLoc End)

const DebugLoc & getStart() const

const DebugLoc & getEnd() const

Represents a single loop in the control flow graph.

bool isGuarded() const

Return true iff the loop is.

StringRef getName() const

bool isRotatedForm() const

Return true if the loop is in rotated form.

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

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

The main scalar evolution driver.

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

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

LLVM Value Representation.

iterator_range< use_iterator > uses()

const ParentTy * getParent() const

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.

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

bool getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name)

Returns true if Name is applied to TheLoop and enabled.

std::optional< bool > getOptionalBoolLoopAttribute(const Loop *TheLoop, StringRef Name)

int getIntLoopAttribute(const Loop *TheLoop, StringRef Name, int Default=0)

Find named metadata for a loop with an integer value.

std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)

Find string metadata for loop.

MDNode * findOptionMDForLoop(const Loop *TheLoop, StringRef Name)

Find string metadata for a loop.

bool hasMustProgress(const Loop *L)

Look for the loop attribute that requires progress within the loop.

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)

void erase(Container &C, ValueType V)

Wrapper function to remove a value from a container:

bool isMustProgress(const Loop *L)

Return true if this loop can be assumed to make progress.

CallBase * getLoopConvergenceHeart(const Loop *TheLoop)

Find the convergence heart of the loop.

bool isFinite(const Loop *L)

Return true if this loop can be assumed to run for a finite number of iterations.

bool VerifyLoopInfo

Enable verification of loop info.

std::optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)

Find named metadata for a loop with an integer value.

bool isValidAsAccessGroup(MDNode *AccGroup)

Return whether an MDNode might represent an access group.

OutputIt move(R &&Range, OutputIt Out)

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

llvm::MDNode * makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID, llvm::ArrayRef< llvm::StringRef > RemovePrefixes, llvm::ArrayRef< llvm::MDNode * > AddAttrs)

Create a new LoopID after the loop has been transformed.

@ Default

The result values are uniform if and only if all operands are uniform.

void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")

Function to print a loop's contents as LLVM's text IR assembly.

MDNode * findOptionMDForLoopID(MDNode *LoopID, StringRef Name)

Find and return the loop attribute node for the attribute Name in LoopID.

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

A CRTP mix-in that provides informational APIs needed for analysis passes.

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

static NodeRef getEntryNode(Loop *L)

LoopInfo::iterator ChildIteratorType

static ChildIteratorType child_begin(NodeRef N)

static ChildIteratorType child_end(NodeRef N)

static ChildIteratorType child_begin(NodeRef N)

static ChildIteratorType child_end(NodeRef N)

static NodeRef getEntryNode(const Loop *L)

LoopInfo::iterator ChildIteratorType

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

Verifier pass for the LoopAnalysis results.

Below are some utilities to get the loop guard, loop bounds and induction variable,...

Direction

An enum for the direction of the loop.

Value & getFinalIVValue() const

Get the final value of the loop induction variable.

Value * getStepValue() const

Get the step that the loop induction variable gets updated by in each loop iteration.

Instruction & getStepInst() const

Get the instruction that updates the loop induction variable.

Value & getInitialIVValue() const

Get the initial value of the loop induction variable.

A CRTP mix-in to automatically provide informational APIs needed for passes.