IVDescriptors.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H

14#define LLVM_ANALYSIS_IVDESCRIPTORS_H

22namespace llvm {

36 None,

37 Add,

38 Sub,

40 Mul,

41 Or,

42 And,

43 Xor,

44 SMin,

45 SMax,

46 UMin,

47 UMax,

48 FAdd,

49 FMul,

50 FMin,

51 FMax,

59 AnyOf,

76};

91public:

98 unsigned MinWidthCastToRecurTy,

99 bool PhiHasUsesOutsideReductionChain = false)

100 : IntermediateStore(Store), StartValue(Start), LoopExitInstr(Exit),

101 Kind(K), FMF(FMF), ExactFPMathInst(ExactFP), RecurrenceType(RT),

102 IsSigned(Signed), IsOrdered(Ordered),

103 PhiHasUsesOutsideReductionChain(PhiHasUsesOutsideReductionChain),

104 MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) {

105 CastInsts.insert_range(CI);

108 "Only min/max recurrences are allowed to have multiple uses currently");

109 }

110

111

113 public:

115 : IsRecurrence(IsRecur), PatternLastInst(I),

116 RecKind(RecurKind::None), ExactFPMathInst(ExactFP) {}

117

119 : IsRecurrence(true), PatternLastInst(I), RecKind(K),

120 ExactFPMathInst(ExactFP) {}

121

123

125

127

129

131

132 private:

133

134 bool IsRecurrence;

135

136

138

140

142 };

143

144

145

146

147

148

149

153

154

157 unsigned MaxNumUses);

158

159

162

163

164

165

166

167

169 const InstDesc &Prev);

170

171

172

173

174

175

176

179

180

181

182

183

184

185

186

190

191

192

194

195

197

198

199

200

201

207

208

209

210

211

212

217

218

219

220

221

222

223

224

225

226

229

231

233

235

237

239

240

241

242 bool hasExactFPMath() const { return ExactFPMathInst != nullptr; }

243

244

246

247

249

250

252

253

258

259

260

264

265

272

273

277

278

279

283

284

285

290

291

292

297

298

304

305

306

307

312

313

314

316

317

318

320 Type *Ty = StartValue->getType();

326 }

330 }

331

332

333

335

336

338 return MinWidthCastToRecurrenceType;

339 }

340

341

342 bool isSigned() const { return IsSigned; }

343

344

346

347

348

349

351 return PhiHasUsesOutsideReductionChain;

352 }

353

354

355

357 Loop *L) const;

358

359

364

365

366

367

369

370private:

371

372

374

376

378

379

381

383

384 Type *RecurrenceType = nullptr;

385

386 bool IsSigned = false;

387

388

389

390 bool IsOrdered = false;

391

392

393

394 bool PhiHasUsesOutsideReductionChain = false;

395

397

398 unsigned MinWidthCastToRecurrenceType;

399};

400

401

403public:

404

411

412public:

413

415

421

422

423

424

425

426

427

428

429

430

435

436

437

438

442

443

444

445

446

447

448

452 bool Assume = false);

453

454

455

456

459 !InductionBinOp->hasAllowReassoc())

460 return InductionBinOp;

461 return nullptr;

462 }

463

464

466 return InductionBinOp ? InductionBinOp->getOpcode()

467 : Instruction::BinaryOpsEnd;

468 }

469

470

471

472

474

475private:

476

480

481

483

485

486 const SCEV *Step = nullptr;

487

489

490

492};

493

494}

495

496#endif

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

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

static APInt getMaxValue(unsigned numBits)

Gets maximum unsigned value of APInt for specific bit width.

static APInt getSignedMaxValue(unsigned numBits)

Gets maximum signed value of APInt for a specific bit width.

static APInt getMinValue(unsigned numBits)

Gets minimum unsigned value of APInt for a specific bit width.

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

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

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

This is the shared class of boolean and integer constants.

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

Convenience struct for specifying and reasoning about fast-math flags.

A struct for saving information about induction variables.

Definition IVDescriptors.h:402

BinaryOperator * getInductionBinOp() const

Definition IVDescriptors.h:419

InductionKind getKind() const

Definition IVDescriptors.h:417

const SCEV * getStep() const

Definition IVDescriptors.h:418

ArrayRef< Instruction * > getCastInsts() const

Returns an ArrayRef to the type cast instructions in the induction update chain, that are redundant w...

Definition IVDescriptors.h:473

InductionKind

This enum represents the kinds of inductions that we support.

Definition IVDescriptors.h:405

@ IK_NoInduction

Not an induction variable.

Definition IVDescriptors.h:406

@ IK_FpInduction

Floating point induction variable.

Definition IVDescriptors.h:409

@ IK_PtrInduction

Pointer induction var. Step = C.

Definition IVDescriptors.h:408

@ IK_IntInduction

Integer induction variable. Step = C.

Definition IVDescriptors.h:407

static LLVM_ABI bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)

Returns true if Phi is an induction in the loop L.

static LLVM_ABI bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D)

Returns true if Phi is a floating point induction in the loop L.

Instruction::BinaryOps getInductionOpcode() const

Returns binary opcode of the induction operator.

Definition IVDescriptors.h:465

Value * getStartValue() const

Definition IVDescriptors.h:416

Instruction * getExactFPMathInst()

Returns floating-point induction operator that does not allow reassociation (transforming the inducti...

Definition IVDescriptors.h:457

InductionDescriptor()=default

Default constructor - creates an invalid induction.

LLVM_ABI ConstantInt * getConstIntStepValue() const

Represents a single loop in the control flow graph.

An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...

InstDesc(bool IsRecur, Instruction *I, Instruction *ExactFP=nullptr)

Definition IVDescriptors.h:114

RecurKind getRecKind() const

Definition IVDescriptors.h:128

Instruction * getPatternInst() const

Definition IVDescriptors.h:130

bool isRecurrence() const

Definition IVDescriptors.h:122

InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP=nullptr)

Definition IVDescriptors.h:118

Instruction * getExactFPMathInst() const

Definition IVDescriptors.h:126

bool needsExactFPMath() const

Definition IVDescriptors.h:124

The RecurrenceDescriptor is used to identify recurrences variables in a loop.

Definition IVDescriptors.h:90

static bool isFPMinMaxRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is a floating-point min/max kind.

Definition IVDescriptors.h:266

Instruction * getExactFPMathInst() const

Returns 1st non-reassociative FP instruction in the PHI node's use-chain.

Definition IVDescriptors.h:245

static bool isFMulAddIntrinsic(Instruction *I)

Returns true if the instruction is a call to the llvm.fmuladd intrinsic.

Definition IVDescriptors.h:360

FastMathFlags getFastMathFlags() const

Definition IVDescriptors.h:234

static bool isFindFirstIVRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

Definition IVDescriptors.h:286

static bool isFPMinMaxNumRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is a floating-point minnum/maxnum kind.

Definition IVDescriptors.h:261

static LLVM_ABI bool isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, DominatorTree *DT)

Returns true if Phi is a fixed-order recurrence.

static bool isSignedRecurrenceKind(RecurKind Kind)

Returns true if recurrece kind is a signed redux kind.

Definition IVDescriptors.h:299

bool hasExactFPMath() const

Returns true if the recurrence has floating-point math that requires precise (ordered) operations.

Definition IVDescriptors.h:242

Instruction * getLoopExitInstr() const

Definition IVDescriptors.h:238

unsigned getOpcode() const

Definition IVDescriptors.h:232

static LLVM_ABI InstDesc isConditionalRdxPattern(Instruction *I)

Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode),...

static LLVM_ABI bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction * > &Insts, unsigned MaxNumUses)

Returns true if instruction I has multiple uses in Insts.

static LLVM_ABI bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)

Returns true if Phi is a reduction in TheLoop.

Type * getRecurrenceType() const

Returns the type of the recurrence.

Definition IVDescriptors.h:315

bool hasUsesOutsideReductionChain() const

Returns true if the reduction PHI has any uses outside the reduction chain.

Definition IVDescriptors.h:350

const SmallPtrSet< Instruction *, 8 > & getCastInsts() const

Returns a reference to the instructions used for type-promoting the recurrence.

Definition IVDescriptors.h:334

static LLVM_ABI bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction * > &Set)

Returns true if all uses of the instruction I is within the Set.

RecurrenceDescriptor()=default

unsigned getMinWidthCastToRecurrenceTypeInBits() const

Returns the minimum width used by the recurrence in bits.

Definition IVDescriptors.h:337

TrackingVH< Value > getRecurrenceStartValue() const

Definition IVDescriptors.h:236

LLVM_ABI SmallVector< Instruction *, 4 > getReductionOpChain(PHINode *Phi, Loop *L) const

Attempts to find a chain of operations from Phi to LoopExitInst that can be treated as a set of reduc...

static bool isAnyOfRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

Definition IVDescriptors.h:280

static LLVM_ABI InstDesc isAnyOfPattern(Loop *Loop, PHINode *OrigPhi, Instruction *I, InstDesc &Prev)

Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...

static bool isFindLastIVRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

Definition IVDescriptors.h:293

bool isSigned() const

Returns true if all source operands of the recurrence are SExtInsts.

Definition IVDescriptors.h:342

RecurKind getRecurrenceKind() const

Definition IVDescriptors.h:230

bool isOrdered() const

Expose an ordered FP reduction to the instance users.

Definition IVDescriptors.h:345

StoreInst * IntermediateStore

Reductions may store temporary or final result to an invariant address.

Definition IVDescriptors.h:368

static LLVM_ABI InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I, RecurKind Kind, InstDesc &Prev, FastMathFlags FuncFMF, ScalarEvolution *SE)

Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a ...

static LLVM_ABI InstDesc isFindIVPattern(RecurKind Kind, Loop *TheLoop, PHINode *OrigPhi, Instruction *I, ScalarEvolution &SE)

Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...

static LLVM_ABI bool isFloatingPointRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is a floating point kind.

static bool isFindIVRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...

Definition IVDescriptors.h:308

static LLVM_ABI InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind, const InstDesc &Prev)

Returns a struct describing if the instruction is a llvm.

static LLVM_ABI bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)

Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.

static LLVM_ABI bool isIntegerRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is an integer kind.

Value * getSentinelValue() const

Returns the sentinel value for FindFirstIV & FindLastIV recurrences to replace the start value.

Definition IVDescriptors.h:319

RecurrenceDescriptor(Value *Start, Instruction *Exit, StoreInst *Store, RecurKind K, FastMathFlags FMF, Instruction *ExactFP, Type *RT, bool Signed, bool Ordered, SmallPtrSetImpl< Instruction * > &CI, unsigned MinWidthCastToRecurTy, bool PhiHasUsesOutsideReductionChain=false)

Definition IVDescriptors.h:94

static bool isIntMinMaxRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is an integer min/max kind.

Definition IVDescriptors.h:254

static bool isMinMaxRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is any min/max kind.

Definition IVDescriptors.h:274

This class represents an analyzed expression in the program.

The main scalar evolution driver.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

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

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.

An instruction for storing to memory.

Value handle that tracks a Value across RAUW.

The instances of the Type class are immutable: once they are created, they are never changed.

LLVM_ABI unsigned getIntegerBitWidth() const

LLVM Value Representation.

This is an optimization pass for GlobalISel generic memory operations.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

RecurKind

These are the kinds of recurrences that we support.

Definition IVDescriptors.h:34

@ UMin

Unsigned integer min implemented in terms of select(cmp()).

Definition IVDescriptors.h:46

@ FMinimumNum

FP min with llvm.minimumnum semantics.

Definition IVDescriptors.h:56

@ FindLastIVUMax

FindLast reduction with select(cmp(),x,y) where one of (x,y) is increasing loop induction,...

Definition IVDescriptors.h:70

@ FindFirstIVUMin

FindFirst reduction with select(icmp(),x,y) where one of (x,y) is a decreasing loop induction,...

Definition IVDescriptors.h:64

@ FindFirstIVSMin

Definition IVDescriptors.h:61

@ FMinimum

FP min with llvm.minimum semantics.

Definition IVDescriptors.h:54

@ FMaxNum

FP max with llvm.maxnum semantics including NaNs.

Definition IVDescriptors.h:53

@ FindLastIVSMax

FindFirst reduction with select(icmp(),x,y) where one of (x,y) is a decreasing loop induction,...

Definition IVDescriptors.h:67

@ Mul

Product of integers.

Definition IVDescriptors.h:40

@ None

Not a recurrence.

Definition IVDescriptors.h:36

@ AnyOf

AnyOf reduction with select(cmp(),x,y) where one of (x,y) is loop invariant, and both x and y are int...

Definition IVDescriptors.h:59

@ Xor

Bitwise or logical XOR of integers.

Definition IVDescriptors.h:43

@ FMax

FP max implemented in terms of select(cmp()).

Definition IVDescriptors.h:51

@ FMaximum

FP max with llvm.maximum semantics.

Definition IVDescriptors.h:55

@ FMulAdd

Sum of float products with llvm.fmuladd(a * b + sum).

Definition IVDescriptors.h:58

@ FMul

Product of floats.

Definition IVDescriptors.h:49

@ SMax

Signed integer max implemented in terms of select(cmp()).

Definition IVDescriptors.h:45

@ SMin

Signed integer min implemented in terms of select(cmp()).

Definition IVDescriptors.h:44

@ FMin

FP min implemented in terms of select(cmp()).

Definition IVDescriptors.h:50

@ FMinNum

FP min with llvm.minnum semantics including NaNs.

Definition IVDescriptors.h:52

@ Sub

Subtraction of integers.

Definition IVDescriptors.h:38

@ Add

Sum of integers.

Definition IVDescriptors.h:37

@ AddChainWithSubs

A chain of adds and subs.

Definition IVDescriptors.h:39

@ FAdd

Sum of floats.

Definition IVDescriptors.h:48

@ FMaximumNum

FP max with llvm.maximumnum semantics.

Definition IVDescriptors.h:57

@ UMax

Unsigned integer max implemented in terms of select(cmp()).

Definition IVDescriptors.h:47

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.