IVDescriptors.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H

14#define LLVM_ANALYSIS_IVDESCRIPTORS_H

21namespace llvm {

23class AssumptionCache;

24class DemandedBits;

25class DominatorTree;

26class Loop;

27class PredicatedScalarEvolution;

28class ScalarEvolution;

29class SCEV;

30class StoreInst;

34 None,

35 Add,

36 Mul,

37 Or,

38 And,

39 Xor,

40 SMin,

41 SMax,

42 UMin,

43 UMax,

44 FAdd,

45 FMul,

46 FMin,

47 FMax,

48 FMinimum,

49 FMaximum,

50 FMulAdd,

51 IAnyOf,

53 FAnyOf,

55 IFindLastIV,

58 FFindLastIV

63};

78public:

85 unsigned MinWidthCastToRecurTy)

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

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

88 IsSigned(Signed), IsOrdered(Ordered),

89 MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) {

90 CastInsts.insert(CI.begin(), CI.end());

91 }

95 public:

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

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

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

102 ExactFPMathInst(ExactFP) {}

103

105

107

109

111

113

114 private:

115

116 bool IsRecurrence;

117

118

120

122

124 };

125

126

127

128

129

130

131

135

136

139 unsigned MaxNumUses);

140

141

143

144

145

146

147

148

150 const InstDesc &Prev);

151

152

153

154

155

156

157

159 InstDesc &Prev);

160

161

162

163

164

165

166

167

170

171

172

174

175

177

178

179

180

181

182 static bool

187

188

189

190

191

192

193 static bool

197

198

199

200

201

202

203

204

205

206

209

211

213

215

217

219

220

221

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

223

224

226

227

229

230

232

233

237 }

238

239

243 }

244

245

248 }

249

250

251

254 }

255

256

257

260 }

261

262

263

265

266

267

271 return ConstantInt::get(Ty,

273 }

274

275

276

278

279

281 return MinWidthCastToRecurrenceType;

282 }

283

284

285 bool isSigned() const { return IsSigned; }

286

287

289

290

291

293 Loop *L) const;

294

295

297 return isa(I) &&

298 cast(I)->getIntrinsicID() == Intrinsic::fmuladd;

299 }

300

301

302

303

305

306private:

307

308

310

312

314

315

317

319

320 Type *RecurrenceType = nullptr;

321

322 bool IsSigned = false;

323

324

325

326 bool IsOrdered = false;

327

329

330 unsigned MinWidthCastToRecurrenceType;

331};

332

333

335public:

336

341 IK_FpInduction

343

344public:

345

347

353

354

355

356

357

358

359

360

361

362

363 static bool

367

368

369

370

373

374

375

376

377

378

379

383

384

385

386

390 return InductionBinOp;

391 return nullptr;

392 }

393

394

396 return InductionBinOp ? InductionBinOp->getOpcode()

397 : Instruction::BinaryOpsEnd;

398 }

399

400

401

402

404 return RedundantCasts;

405 }

406

407private:

408

412

413

415

417

418 const SCEV *Step = nullptr;

419

421

422

424};

425

426}

427

428#endif

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

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

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

static APInt getSignedMinValue(unsigned numBits)

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

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

BinaryOps getOpcode() const

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.

BinaryOperator * getInductionBinOp() const

InductionKind getKind() const

const SCEV * getStep() const

InductionKind

This enum represents the kinds of inductions that we support.

@ IK_NoInduction

Not an induction variable.

@ IK_FpInduction

Floating point induction variable.

@ IK_PtrInduction

Pointer induction var. Step = C.

@ IK_IntInduction

Integer induction variable. Step = C.

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

const SmallVectorImpl< Instruction * > & getCastInsts() const

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

Value * getStartValue() const

Instruction * getExactFPMathInst()

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

InductionDescriptor()=default

Default constructor - creates an invalid induction.

ConstantInt * getConstIntStepValue() const

bool hasAllowReassoc() const LLVM_READONLY

Determine whether the allow-reassociation flag is set.

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

This POD struct holds information about a potential recurrence operation.

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

RecurKind getRecKind() const

Instruction * getPatternInst() const

bool isRecurrence() const

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

Instruction * getExactFPMathInst() const

bool needsExactFPMath() const

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

static bool isFPMinMaxRecurrenceKind(RecurKind Kind)

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

Instruction * getExactFPMathInst() const

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

static bool isFMulAddIntrinsic(Instruction *I)

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

FastMathFlags getFastMathFlags() const

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

Returns true if Phi is a fixed-order recurrence.

bool hasExactFPMath() const

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

Instruction * getLoopExitInstr() const

unsigned getOpcode() const

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

Returns true if instruction I has multiple uses in Insts.

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

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

Type * getRecurrenceType() const

Returns the type of the recurrence.

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

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

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

TrackingVH< Value > getRecurrenceStartValue() const

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

static InstDesc isFindLastIVPattern(Loop *TheLoop, PHINode *OrigPhi, Instruction *I, ScalarEvolution &SE)

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

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

bool isSigned() const

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

static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I)

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

RecurKind getRecurrenceKind() const

bool isOrdered() const

Expose an ordered FP reduction to the instance users.

StoreInst * IntermediateStore

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

static 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 bool isFloatingPointRecurrenceKind(RecurKind Kind)

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

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

Returns a struct describing if the instruction is a llvm.

static 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 bool isIntegerRecurrenceKind(RecurKind Kind)

Returns true if the recurrence kind is an integer kind.

Value * getSentinelValue() const

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

static bool isIntMinMaxRecurrenceKind(RecurKind Kind)

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

static bool isMinMaxRecurrenceKind(RecurKind Kind)

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

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.

unsigned getIntegerBitWidth() const

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

This is an optimization pass for GlobalISel generic memory operations.

RecurKind

These are the kinds of recurrences that we support.

@ UMin

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

@ IFindLastIV

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

@ FAnyOf

Any_of reduction with select(fcmp(),x,y) where one of (x,y) is loop invariant, and both x and y are i...

@ Or

Bitwise or logical OR of integers.

@ FMinimum

FP min with llvm.minimum semantics.

@ Mul

Product of integers.

@ Xor

Bitwise or logical XOR of integers.

@ FMax

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

@ FMaximum

FP max with llvm.maximum semantics.

@ FMulAdd

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

@ SMax

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

@ And

Bitwise or logical AND of integers.

@ FFindLastIV

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

@ SMin

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

@ FMin

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

@ IAnyOf

Any_of reduction with select(icmp(),x,y) where one of (x,y) is loop invariant, and both x and y are i...

@ UMax

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