LoopUtils.h Source File (original) (raw)

13#ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H

14#define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H

22namespace llvm {

52template <typename T, unsigned N> class SmallSetVector;

58 bool PreserveLCSSA);

67 bool PreserveLCSSA);

100

101

102

103

104

105

108

109

110

111

112

113

114

115

116

117

120

121

122

123

125public:

126

130

132

138

139protected:

145};

146

147

148

149

150

151

152

153

154

155

156

162 Loop *OutermostLoop = nullptr);

163

164

165

172

173

174

175

176

177

178

179

180

181

182

188 bool, bool AllowSpeculation);

189

190

191

192

194

195

196

197

198

199

200

201

202

203

204

205

208

209

210

211

214

215

216

217

218

219

220

221

222

223

224

231 bool AllowSpeculation, bool HasReadsOutsideSet);

232

233

234

237

238

240

241

242

243

244

245LLVM_ABI std::optional

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272LLVM_ABI std::optional<MDNode *>

274 const char *InheritOptionsAttrsPrefix = "",

275 bool AlwaysNew = false);

276

277

279

280

282

283

285

286

288

289

291

292

294

295

297

298

299

300

302

303

304

305

306

308};

309

310

311

317

318

319

320

321

323 unsigned V = 0);

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350LLVM_ABI std::optional

352 unsigned *EstimatedLoopInvocationWeight = nullptr);

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

369 Loop *L, unsigned EstimatedTripCount,

370 std::optional EstimatedLoopInvocationWeight = std::nullopt);

371

372

373

374

375

376

377

378

380

381

382

383

384

385

387

388

389

390

391

392

393

394

396

397

398

399

400

401

402

404 bool ForFirstTarget);

405

406

407

408

410

411

412

413

414

415

417

418

419

420

421

422

423

424

425

426

428 DominatorTree *DT, Loop *CurLoop,

429 MemorySSAUpdater &MSSAU,

430 bool TargetExecutesOncePerLoop,

431 SinkAndHoistLICMFlags &LICMFlags,

432 OptimizationRemarkEmitter *ORE = nullptr);

433

434

435

437

438

440

441

443

445

446

448

449

451

452

454

455

457

458

459

461 FastMathFlags FMF);

462

463

464

466

467

468

471

472

474 Value *Src, unsigned Op,

476

477

478

480 unsigned Op,

483

484

485

486

487

489 RecurKind RdxKind);

490

491

493 RecurKind RdxKind, Value *Mask,

494 Value *EVL);

495

496

497

499 Value *InitVal, PHINode *OrigPhi);

500

501

502

504 RecurKind RdxKind, Value *Start,

506

507

508

510 Value *Src, Value *Start);

511

512

514 Value *Src, Value *Start, Value *Mask,

515 Value *EVL);

516

517

518

519

520

521

522

524 Value *OpValue = nullptr,

525 bool IncludeWrapFlags = true);

526

527

528

530 ScalarEvolution &SE);

531

532

533

535 ScalarEvolution &SE);

536

537

539 ScalarEvolution &SE);

540

541

542

544 ScalarEvolution &SE);

545

546

548 ScalarEvolution &SE, bool Signed);

549

550

552 ScalarEvolution &SE, bool Signed);

553

561

562

563

564

565

566

568 TargetLibraryInfo *TLI, ScalarEvolution *SE,

569 const TargetTransformInfo *TTI,

570 SCEVExpander &Rewriter, DominatorTree *DT,

573

574

575

576

577

578

579template

582

583

584

585template

588

592

596

597

598

599

600

601

602

603

604

605

608

609

610

613

614

615

620

624

625

627

628

630

631

633

634

635

637

638

639

641};

642

643

644

645

646

647

648

649

650

651

652

653

654LLVM_ABI std::optional

657

658}

659

660#endif

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

#define LLVM_TEMPLATE_ABI

static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))

static cl::opt< bool, true > HoistRuntimeChecks("hoist-runtime-checks", cl::Hidden, cl::desc("Hoist inner loop runtime memory checks to outer loop if possible"), cl::location(VectorizerParams::HoistRuntimeChecks), cl::init(true))

const SmallVectorImpl< MachineOperand > & Cond

This pass exposes codegen information to IR-level passes.

static const uint32_t IV[8]

Represent the analysis usage information of a pass.

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

A cache of @llvm.assume calls within a function.

LLVM Basic Block Representation.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

This is an important base class in LLVM.

Base class for the actual dominator tree node.

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

This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to give precise answers on "may...

Common base class shared among various IRBuilders.

Represents a single loop in the control flow graph.

Encapsulates MemorySSA, including all data associated with memory accesses.

PredIteratorCache - This class is an extremely trivial cache for predecessor iterator queries.

This class uses information about analyze scalars to rewrite expressions in canonical form.

This class represents an analyzed expression in the program.

The main scalar evolution driver.

Flags controlling how much is checked when sinking or hoisting instructions.

Definition LoopUtils.h:124

bool NoOfMemAccTooLarge

Definition LoopUtils.h:140

LLVM_ABI SinkAndHoistLICMFlags(unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap, bool IsSink, Loop &L, MemorySSA &MSSA)

void incrementClobberingCalls()

Definition LoopUtils.h:137

bool IsSink

Definition LoopUtils.h:144

void setIsSink(bool B)

Definition LoopUtils.h:133

unsigned LicmMssaNoAccForPromotionCap

Definition LoopUtils.h:143

unsigned LicmMssaOptCap

Definition LoopUtils.h:142

unsigned LicmMssaOptCounter

Definition LoopUtils.h:141

bool getIsSink()

Definition LoopUtils.h:134

bool tooManyClobberingCalls()

Definition LoopUtils.h:136

bool tooManyMemoryAccesses()

Definition LoopUtils.h:135

A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...

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

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.

Provides information about what library functions are available for the current target.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

LLVM Value Representation.

An efficient, type-erasing, non-owning reference to a callable.

Abstract Attribute helper functions.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI Value * createSimpleReduction(IRBuilderBase &B, Value *Src, RecurKind RdxKind)

Create a reduction of the given vector.

LLVM_ABI std::optional< ElementCount > getOptionalElementCountLoopAttribute(const Loop *TheLoop)

Find a combination of metadata ("llvm.loop.vectorize.width" and "llvm.loop.vectorize....

LLVM_ABI Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander, bool HoistRuntimeChecks=false)

Add code that checks at runtime if the accessed arrays in PointerChecks overlap.

LLVM_ABI Value * createFindLastIVReduction(IRBuilderBase &B, Value *Src, RecurKind RdxKind, Value *Start, Value *Sentinel)

Create a reduction of the given vector Src for a reduction of the kind RecurKind::FindLastIV.

LLVM_ABI std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)

Return either:

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

LLVM_ABI Intrinsic::ID getMinMaxReductionIntrinsicOp(Intrinsic::ID RdxID)

Returns the min/max intrinsic used when expanding a min/max reduction.

std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck

A memcheck which made up of a pair of grouped pointers.

LLVM_ABI bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, MemorySSAUpdater &MSSAU, bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags &LICMFlags, OptimizationRemarkEmitter *ORE=nullptr)

Returns true if is legal to hoist or sink this instruction disregarding the possible introduction of ...

LLVM_ABI bool isKnownNonPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)

Returns true if we can prove that S is defined and always non-positive in loop L.

void appendReversedLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)

Utility that implements appending of loops onto a worklist given a range.

BranchProbability getBranchProbability(BranchInst *B, bool ForFirstTarget)

Based on branch weight metadata, return either:

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

Put a loop nest into LCSSA form.

LLVM_ABI Value * getReductionIdentity(Intrinsic::ID RdxID, Type *Ty, FastMathFlags FMF)

Given information about an @llvm.vector.reduce.

LLVM_ABI std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)

Create a new loop identifier for a loop created from a loop transformation.

LLVM_ABI unsigned getArithmeticReductionInstruction(Intrinsic::ID RdxID)

Returns the arithmetic instruction opcode used when expanding a reduction.

LLVM_ABI Value * createMinMaxOp(IRBuilderBase &Builder, RecurKind RK, Value *Left, Value *Right)

Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.

LLVM_ABI SmallVector< BasicBlock *, 16 > collectChildrenInLoop(DominatorTree *DT, DomTreeNode *N, const Loop *CurLoop)

Does a BFS from a given node to all of its children inside a given loop.

LLVM_ABI void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)

Set input string into loop metadata by keeping other values intact.

LLVM_ABI bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)

Returns true if S is defined and never is equal to signed/unsigned max.

DomTreeNodeBase< BasicBlock > DomTreeNode

LLVM_ABI TransformationMode hasVectorizeTransformation(const Loop *L)

bool setBranchProbability(BranchInst *B, BranchProbability P, bool ForFirstTarget)

Set branch weight metadata for B to indicate that P and 1 - P are the probabilities of control flowin...

LLVM_ABI bool hoistRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, AssumptionCache *, TargetLibraryInfo *, Loop *, MemorySSAUpdater &, ScalarEvolution *, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, bool, bool AllowSpeculation)

Walk the specified region of the CFG (defined by all blocks dominated by the specified block,...

LLVM_ABI SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)

Returns the instructions that use values defined in the loop.

LLVM_ABI constexpr Intrinsic::ID getReductionIntrinsicID(RecurKind RK)

Returns the llvm.vector.reduce intrinsic that corresponds to the recurrence kind.

LLVM_ABI TransformationMode hasUnrollAndJamTransformation(const Loop *L)

LLVM_ABI void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)

This function deletes dead loops.

LLVM_ABI bool hasDisableAllTransformsHint(const Loop *L)

Look for the loop attribute that disables all transformation heuristic.

LLVM_TEMPLATE_ABI void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)

Utility that implements appending of loops onto a worklist given a range.

LLVM_ABI Value * getShuffleReduction(IRBuilderBase &Builder, Value *Src, unsigned Op, TargetTransformInfo::ReductionShuffle RS, RecurKind MinMaxKind=RecurKind::None)

Generates a vector reduction using shufflevectors to reduce the value.

LLVM_ABI TransformationMode hasUnrollTransformation(const Loop *L)

BranchProbability getLoopProbability(Loop *L)

Based on branch weight metadata, return either:

LLVM_ABI TransformationMode hasDistributeTransformation(const Loop *L)

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

LLVM_ABI void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)

Remove the backedge of the specified loop.

LLVM_ABI void getLoopAnalysisUsage(AnalysisUsage &AU)

Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.

LLVM_ABI void propagateIRFlags(Value *I, ArrayRef< Value * > VL, Value *OpValue=nullptr, bool IncludeWrapFlags=true)

Get the intersection (logical and) of all of the potential IR flags of each scalar operation (VL) tha...

LLVM_ABI bool isKnownPositiveInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)

Returns true if we can prove that S is defined and always positive in loop L.

bool setLoopProbability(Loop *L, BranchProbability P)

Set branch weight metadata for the latch of L to indicate that, at the end of any iteration,...

LLVM_ABI CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)

Returns the comparison predicate used when expanding a min/max reduction.

LLVM_ABI TransformationMode hasLICMVersioningTransformation(const Loop *L)

TransformationMode

The mode sets how eager a transformation should be applied.

Definition LoopUtils.h:284

@ TM_Unspecified

The pass can use heuristics to determine whether a transformation should be applied.

Definition LoopUtils.h:287

@ TM_SuppressedByUser

The transformation must not be applied.

Definition LoopUtils.h:307

@ TM_ForcedByUser

The transformation was directed by the user, e.g.

Definition LoopUtils.h:301

@ TM_Disable

The transformation should not be applied.

Definition LoopUtils.h:293

@ TM_Force

Force is a flag and should not be used alone.

Definition LoopUtils.h:296

@ TM_Enable

The transformation should be applied without considering a cost model.

Definition LoopUtils.h:290

LLVM_ABI bool hasDisableLICMTransformsHint(const Loop *L)

Look for the loop attribute that disables the LICM transformation heuristics.

template LLVM_TEMPLATE_ABI void appendLoopsToWorklist< Loop & >(Loop &L, SmallPriorityWorklist< Loop *, 4 > &Worklist)

LLVM_ABI Intrinsic::ID getReductionForBinop(Instruction::BinaryOps Opc)

Returns the reduction intrinsic id corresponding to the binary operation.

LLVM_ABI Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF)

Given information about an recurrence kind, return the identity for the @llvm.vector....

LLVM_ABI bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

Ensure that all exit blocks of the loop are dedicated exits.

DWARFExpression::Operation Op

ArrayRef(const T &OneElt) -> ArrayRef< T >

LLVM_ABI bool isKnownNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)

Returns true if we can prove that S is defined and always negative in loop L.

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

LLVM_ABI bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, std::optional< unsigned > EstimatedLoopInvocationWeight=std::nullopt)

Set llvm.loop.estimated_trip_count with the value EstimatedTripCount in the loop metadata of L.

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

LLVM_ABI bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)

Check inner loop (L) backedge count is known to be invariant on all iterations of its outer loop.

static cl::opt< unsigned > MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden)

LLVM_ABI bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)

Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...

LLVM_ABI int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)

If the final value of any expressions that are recurrent in the loop can be computed,...

LLVM_ABI Value * createOrderedReduction(IRBuilderBase &B, RecurKind RdxKind, Value *Src, Value *Start)

Create an ordered reduction intrinsic using the given recurrence kind RdxKind.

LLVM_ABI bool sinkRegion(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *CurLoop, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *, Loop *OutermostLoop=nullptr)

Walk the specified region of the CFG (defined by all blocks dominated by the specified block,...

LLVM_ABI Value * addDiffRuntimeChecks(Instruction *Loc, ArrayRef< PointerDiffInfo > Checks, SCEVExpander &Expander, function_ref< Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC)

LLVM_ABI RecurKind getMinMaxReductionRecurKind(Intrinsic::ID RdxID)

Returns the recurence kind used when expanding a min/max reduction.

ReplaceExitVal

Definition LoopUtils.h:554

@ UnusedIndVarInLoop

Definition LoopUtils.h:558

@ OnlyCheapRepl

Definition LoopUtils.h:556

@ NeverRepl

Definition LoopUtils.h:555

@ NoHardUse

Definition LoopUtils.h:557

@ AlwaysRepl

Definition LoopUtils.h:559

LLVM_ABI std::optional< IVConditionInfo > hasPartialIVCondition(const Loop &L, unsigned MSSAThreshold, const MemorySSA &MSSA, AAResults &AA)

Check if the loop header has a conditional branch that is not loop-invariant, because it involves loa...

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

Put loop into LCSSA form.

LLVM_ABI bool promoteLoopAccessesToScalars(const SmallSetVector< Value *, 8 > &, SmallVectorImpl< BasicBlock * > &, SmallVectorImpl< BasicBlock::iterator > &, SmallVectorImpl< MemoryAccess * > &, PredIteratorCache &, LoopInfo *, DominatorTree *, AssumptionCache *AC, const TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, OptimizationRemarkEmitter *, bool AllowSpeculation, bool HasReadsOutsideSet)

Try to promote memory values to scalars by sinking stores out of the loop and moving loads to before ...

LLVM_ABI Value * createAnyOfReduction(IRBuilderBase &B, Value *Src, Value *InitVal, PHINode *OrigPhi)

Create a reduction of the given vector Src for a reduction of kind RecurKind::AnyOf.

LLVM_ABI bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE, bool Signed)

Returns true if S is defined and never is equal to signed/unsigned min.

LLVM_ABI bool isKnownNonNegativeInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE)

Returns true if we can prove that S is defined and always non-negative in loop L.

LLVM_ABI bool sinkRegionForLoopNest(DomTreeNode *, AAResults *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, MemorySSAUpdater &, ICFLoopSafetyInfo *, SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *)

Call sinkRegion on loops contained within the specified loop in order from innermost to outermost.

LLVM_ABI Value * getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src, unsigned Op, RecurKind MinMaxKind=RecurKind::None)

Generates an ordered vector reduction using extracts to reduce the value.

LLVM_ABI Intrinsic::ID getMinMaxReductionIntrinsicID(Intrinsic::ID IID)

Returns the llvm.vector.reduce min/max intrinsic that corresponds to the intrinsic op.

LLVM_ABI Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)

Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...

Struct to hold information about a partially invariant condition.

Definition LoopUtils.h:626

BasicBlock * ExitForPath

If the partially invariant path reaches a single exit block, ExitForPath is set to that block.

Definition LoopUtils.h:640

SmallVector< Instruction * > InstToDuplicate

Instructions that need to be duplicated and checked for the unswitching condition.

Definition LoopUtils.h:629

Constant * KnownValue

Constant to indicate for which value the condition is invariant.

Definition LoopUtils.h:632

bool PathIsNoop

True if the partially invariant path is no-op (=does not have any side-effects and no loop value is u...

Definition LoopUtils.h:636