LoopUtils.h Source File (original) (raw)

13#ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H

14#define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H

22namespace llvm {

24template class DomTreeNodeBase;

25using DomTreeNode = DomTreeNodeBase;

26class AssumptionCache;

27class StringRef;

28class AnalysisUsage;

29class TargetTransformInfo;

30class AAResults;

32class ICFLoopSafetyInfo;

33class IRBuilderBase;

34class Loop;

35class LoopInfo;

36class MemoryAccess;

38class MemorySSAUpdater;

39class OptimizationRemarkEmitter;

40class PredIteratorCache;

41class ScalarEvolution;

42class SCEV;

43class SCEVExpander;

44class TargetLibraryInfo;

45class LPPassManager;

46class Instruction;

47struct RuntimeCheckingPtrGroup;

48typedef std::pair<const RuntimeCheckingPtrGroup *,

49 const RuntimeCheckingPtrGroup *>

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

53template <typename T, unsigned N> class SmallPriorityWorklist;

56 MemorySSAUpdater *MSSAU, bool PreserveLCSSA);

64 MemorySSAUpdater *MSSAU, bool PreserveLCSSA);

85 SmallVectorImpl<Instruction *> &Worklist, const DominatorTree &DT,

86 const LoopInfo &LI, ScalarEvolution *SE,

87 SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr,

88 SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);

100

101

102bool formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,

103 ScalarEvolution *SE);

104

105

106

107

108

109

110

111

112

113

114bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI,

115 ScalarEvolution *SE);

116

117

118

119

121public:

122

126

128

134

135protected:

141};

142

143

144

145

146

147

148

149

150

151

152

157 Loop *OutermostLoop = nullptr);

158

159

160

166

167

168

169

170

171

172

173

174

175

176

181 bool AllowSpeculation);

182

183

184

185

187

188

189

190

191

192

193

194

195

196

197

198

201

202

203

204

207

208

209

210

211

212

213

214

215

216

217

224 bool AllowSpeculation, bool HasReadsOutsideSet);

225

226

227

230

231

233

234

235

236

237

238std::optional

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265std::optional<MDNode *>

267 const char *InheritOptionsAttrsPrefix = "",

268 bool AlwaysNew = false);

269

270

272

273

275

276

278

279

281

282

284

285

287

288

290

291

292

293

295

296

297

298

299

302

303

304

310

311

312

313

314

316 unsigned V = 0);

317

318

319

320

321

322

323std::optional

325 unsigned *EstimatedLoopInvocationWeight = nullptr);

326

327

328

329

330

331

333 unsigned EstimatedLoopInvocationWeight);

334

335

336

337

339

340

341

342

343

344

346

347

348

349

350

351

352

353

354

355

357 Loop *CurLoop, MemorySSAUpdater &MSSAU,

358 bool TargetExecutesOncePerLoop,

359 SinkAndHoistLICMFlags &LICMFlags,

360 OptimizationRemarkEmitter *ORE = nullptr);

361

362

363

365

366

368

369

371

372

374

375

377

378

380

381

382

384

385

386

388

389

390

393

394

395Value *getOrderedReduction(IRBuilderBase &Builder, Value *Acc, Value *Src,

397

398

399

403

404

405

406

407

410

411

413 const RecurrenceDescriptor &Desc);

414

415

416

417

419 const RecurrenceDescriptor &Desc,

420 PHINode *OrigPhi);

421

422

423

424

426 const RecurrenceDescriptor &Desc);

427

428

429

431 Value *Src, PHINode *OrigPhi = nullptr);

432

433

434

436 const RecurrenceDescriptor &Desc, Value *Src,

437 Value *Start);

438

439

441 const RecurrenceDescriptor &Desc, Value *Src,

442 Value *Start);

443

444

445

446

447

448

449

450void propagateIRFlags(Value *I, ArrayRef<Value *> VL, Value *OpValue = nullptr,

451 bool IncludeWrapFlags = true);

452

453

454

456

457

458

460 ScalarEvolution &SE);

461

462

464

465

466

468 ScalarEvolution &SE);

469

470

471bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,

473

474

475bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,

477

485

486

487

488

489

490

492 ScalarEvolution *SE, const TargetTransformInfo *TTI,

493 SCEVExpander &Rewriter, DominatorTree *DT,

495 SmallVector<WeakTrackingVH, 16> &DeadInsts);

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

512 Loop *RemainderLoop, uint64_t UF);

513

514

515

516

517

518

519template

521

522

523

524template

526 SmallPriorityWorklist<Loop *, 4> &);

527

528

529

530

531

532

533

534

535

536

538

539

540

542 LoopInfo *LI, LPPassManager *LPM);

543

544

545

546Value *

548 const SmallVectorImpl &PointerChecks,

550

552 Instruction *Loc, ArrayRef Checks, SCEVExpander &Expander,

553 function_ref<Value *(IRBuilderBase &, unsigned)> GetVF, unsigned IC);

554

555

557

558

560

561

563

564

565

567

568

569

571};

572

573

574

575

576

577

578

579

580

581

582

583

588

589}

590

591#endif

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

early cse Early CSE w MemorySSA

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

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)

This pass exposes codegen information to IR-level passes.

static const uint32_t IV[8]

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.

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

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.

The main scalar evolution driver.

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

void incrementClobberingCalls()

unsigned LicmMssaNoAccForPromotionCap

unsigned LicmMssaOptCounter

bool tooManyClobberingCalls()

bool tooManyMemoryAccesses()

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.

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.

@ BasicBlock

Various leaf nodes.

This is an optimization pass for GlobalISel generic memory operations.

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

Create a reduction of the given vector.

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

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

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.

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

Returns a loop's estimated trip count based on branch weight metadata.

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

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.

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

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.

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

Put a loop nest into LCSSA form.

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

Given information about an @llvm.vector.reduce.

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.

unsigned getArithmeticReductionInstruction(Intrinsic::ID RdxID)

Returns the arithmetic instruction opcode used when expanding a reduction.

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

Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.

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.

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

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

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.

Value * createAnyOfReduction(IRBuilderBase &B, Value *Src, const RecurrenceDescriptor &Desc, PHINode *OrigPhi)

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

TransformationMode hasVectorizeTransformation(const Loop *L)

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

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

Returns the instructions that use values defined in the loop.

constexpr Intrinsic::ID getReductionIntrinsicID(RecurKind RK)

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

TransformationMode hasUnrollAndJamTransformation(const Loop *L)

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

This function deletes dead loops.

bool hasDisableAllTransformsHint(const Loop *L)

Look for the loop attribute that disables all transformation heuristic.

Value * createOrderedReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, Value *Start)

Create an ordered reduction intrinsic using the given recurrence descriptor Desc.

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.

Value * createReduction(IRBuilderBase &B, const RecurrenceDescriptor &Desc, Value *Src, PHINode *OrigPhi=nullptr)

Create a generic reduction using a recurrence descriptor Desc Fast-math-flags are propagated using th...

TransformationMode hasUnrollTransformation(const Loop *L)

DomTreeNodeBase< BasicBlock > DomTreeNode

TransformationMode hasDistributeTransformation(const Loop *L)

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

Remove the backedge of the specified loop.

void getLoopAnalysisUsage(AnalysisUsage &AU)

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

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

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.

CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK)

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

TransformationMode hasLICMVersioningTransformation(const Loop *L)

Value * createFindLastIVReduction(IRBuilderBase &B, Value *Src, const RecurrenceDescriptor &Desc)

Create a reduction of the given vector Src for a reduction of the kind RecurKind::IFindLastIV or Recu...

TransformationMode

The mode sets how eager a transformation should be applied.

@ TM_Unspecified

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

@ TM_SuppressedByUser

The transformation must not be applied.

@ TM_ForcedByUser

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

@ TM_Disable

The transformation should not be applied.

@ TM_Force

Force is a flag and should not be used alone.

@ TM_Enable

The transformation should be applied without considering a cost model.

bool hasDisableLICMTransformsHint(const Loop *L)

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

RecurKind

These are the kinds of recurrences that we support.

bool setLoopEstimatedTripCount(Loop *L, unsigned EstimatedTripCount, unsigned EstimatedLoopInvocationWeight)

Set a loop's branch weight metadata to reflect that loop has EstimatedTripCount iterations and Estima...

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

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

void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, Loop *RemainderLoop, uint64_t UF)

Set weights for UnrolledLoop and RemainderLoop based on weights for OrigLoop and the following distri...

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

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

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

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

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.

bool hasIterationCountInvariantInParent(Loop *L, ScalarEvolution &SE)

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

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

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

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

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

RecurKind getMinMaxReductionRecurKind(Intrinsic::ID RdxID)

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

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

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

Put loop into LCSSA form.

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

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.

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.

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.

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.

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.

BasicBlock * ExitForPath

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

SmallVector< Instruction * > InstToDuplicate

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

Constant * KnownValue

Constant to indicate for which value the condition is invariant.

bool PathIsNoop

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