Movatterモバイル変換

Go to the documentation of this file.

1//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file defines the classes used to represent and build scalar expressions.

10//

11//===----------------------------------------------------------------------===//

13#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

14#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

16#include "llvm/ADT/DenseMap.h"

17#include "llvm/ADT/SmallPtrSet.h"

18#include "llvm/ADT/SmallVector.h"

19#include "llvm/Analysis/ScalarEvolution.h"

20#include "llvm/IR/Constants.h"

21#include "llvm/IR/ValueHandle.h"

22#include "llvm/Support/Casting.h"

23#include "llvm/Support/ErrorHandling.h"

24#include <cassert>

25#include <cstddef>

27namespacellvm {

29classAPInt;

30classConstant;

31classConstantInt;

32classConstantRange;

33classLoop;

34classType;

35classValue;

37enumSCEVTypes :unsignedshort {

38// These should be ordered in terms of increasing complexity to make the

39// folders simpler.

53scSequentialUMinExpr,

54scPtrToInt,

55scUnknown,

56scCouldNotCompute

57};

59/// This class represents a constant integer value.

60classSCEVConstant :publicSCEV {

61friendclassScalarEvolution;

63ConstantInt *V;

65SCEVConstant(constFoldingSetNodeIDRef ID,ConstantInt *v)

66 :SCEV(ID,scConstant, 1), V(v) {}

68public:

69ConstantInt *getValue() const{return V; }

70constAPInt &getAPInt() const{returngetValue()->getValue(); }

72Type *getType() const{return V->getType(); }

74 /// Methods for support type inquiry through isa, cast, and dyn_cast:

75staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scConstant; }

76};

78/// This class represents the value of vscale, as used when defining the length

79/// of a scalable vector or returned by the llvm.vscale() intrinsic.

80classSCEVVScale :publicSCEV {

81friendclassScalarEvolution;

83SCEVVScale(constFoldingSetNodeIDRef ID,Type *ty)

84 :SCEV(ID,scVScale, 0), Ty(ty) {}

86Type *Ty;

88public:

89Type *getType() const{return Ty; }

91 /// Methods for support type inquiry through isa, cast, and dyn_cast:

92staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scVScale; }

93};

95inlineunsignedshortcomputeExpressionSize(ArrayRef<const SCEV *> Args) {

96APInt Size(16, 1);

97for (constauto *Arg : Args)

98Size =Size.uadd_sat(APInt(16, Arg->getExpressionSize()));

99return (unsignedshort)Size.getZExtValue();

100}

101

102/// This is the base class for unary cast operator classes.

103classSCEVCastExpr :publicSCEV {

104protected:

105constSCEV *Op;

106Type *Ty;

107

108SCEVCastExpr(constFoldingSetNodeIDRef ID,SCEVTypes SCEVTy,constSCEV *op,

109Type *ty);

110

111public:

112constSCEV *getOperand() const{returnOp; }

113constSCEV *getOperand(unsigned i) const{

114assert(i == 0 &&"Operand index out of range!");

115returnOp;

116 }

117ArrayRef<const SCEV *>operands() const{returnOp; }

118size_tgetNumOperands() const{return 1; }

119Type *getType() const{returnTy; }

120

121 /// Methods for support type inquiry through isa, cast, and dyn_cast:

122staticboolclassof(constSCEV *S) {

123return S->getSCEVType() ==scPtrToInt || S->getSCEVType() ==scTruncate ||

124 S->getSCEVType() ==scZeroExtend || S->getSCEVType() ==scSignExtend;

125 }

126};

127

128/// This class represents a cast from a pointer to a pointer-sized integer

129/// value.

130classSCEVPtrToIntExpr :publicSCEVCastExpr {

131friendclassScalarEvolution;

132

133SCEVPtrToIntExpr(constFoldingSetNodeIDRef ID,constSCEV *Op,Type *ITy);

134

135public:

136 /// Methods for support type inquiry through isa, cast, and dyn_cast:

137staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scPtrToInt; }

138};

139

140/// This is the base class for unary integral cast operator classes.

141classSCEVIntegralCastExpr :publicSCEVCastExpr {

142protected:

143SCEVIntegralCastExpr(constFoldingSetNodeIDRef ID,SCEVTypes SCEVTy,

144constSCEV *op,Type *ty);

145

146public:

147 /// Methods for support type inquiry through isa, cast, and dyn_cast:

148staticboolclassof(constSCEV *S) {

149return S->getSCEVType() ==scTruncate || S->getSCEVType() ==scZeroExtend ||

150 S->getSCEVType() ==scSignExtend;

151 }

152};

153

154/// This class represents a truncation of an integer value to a

155/// smaller integer value.

156classSCEVTruncateExpr :publicSCEVIntegralCastExpr {

157friendclassScalarEvolution;

158

159SCEVTruncateExpr(constFoldingSetNodeIDRef ID,constSCEV *op,Type *ty);

160

161public:

162 /// Methods for support type inquiry through isa, cast, and dyn_cast:

163staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scTruncate; }

164};

165

166/// This class represents a zero extension of a small integer value

167/// to a larger integer value.

168classSCEVZeroExtendExpr :publicSCEVIntegralCastExpr {

169friendclassScalarEvolution;

170

171SCEVZeroExtendExpr(constFoldingSetNodeIDRef ID,constSCEV *op,Type *ty);

172

173public:

174 /// Methods for support type inquiry through isa, cast, and dyn_cast:

175staticboolclassof(constSCEV *S) {

176return S->getSCEVType() ==scZeroExtend;

177 }

178};

179

180/// This class represents a sign extension of a small integer value

181/// to a larger integer value.

182classSCEVSignExtendExpr :publicSCEVIntegralCastExpr {

183friendclassScalarEvolution;

184

185SCEVSignExtendExpr(constFoldingSetNodeIDRef ID,constSCEV *op,Type *ty);

186

187public:

188 /// Methods for support type inquiry through isa, cast, and dyn_cast:

189staticboolclassof(constSCEV *S) {

190return S->getSCEVType() ==scSignExtend;

191 }

192};

193

194/// This node is a base class providing common functionality for

195/// n'ary operators.

196classSCEVNAryExpr :publicSCEV {

197protected:

198// Since SCEVs are immutable, ScalarEvolution allocates operand

199// arrays with its SCEVAllocator, so this class just needs a simple

200// pointer rather than a more elaborate vector-like data structure.

201// This also avoids the need for a non-trivial destructor.

202constSCEV *const *Operands;

203size_tNumOperands;

204

205SCEVNAryExpr(constFoldingSetNodeIDRef ID,enumSCEVTypes T,

206constSCEV *const *O,size_tN)

207 :SCEV(ID,T,computeExpressionSize(ArrayRef(O,N))),Operands(O),

208NumOperands(N) {}

209

210public:

211size_tgetNumOperands() const{returnNumOperands; }

212

213constSCEV *getOperand(unsigned i) const{

214assert(i <NumOperands &&"Operand index out of range!");

215returnOperands[i];

216 }

217

218ArrayRef<const SCEV *>operands() const{

219returnArrayRef(Operands,NumOperands);

220 }

221

222NoWrapFlags getNoWrapFlags(NoWrapFlags Mask =NoWrapMask) const{

223return (NoWrapFlags)(SubclassData & Mask);

224 }

225

226boolhasNoUnsignedWrap() const{

227returngetNoWrapFlags(FlagNUW) !=FlagAnyWrap;

228 }

229

230boolhasNoSignedWrap() const{

231returngetNoWrapFlags(FlagNSW) !=FlagAnyWrap;

232 }

233

234boolhasNoSelfWrap() const{returngetNoWrapFlags(FlagNW) !=FlagAnyWrap; }

235

236 /// Methods for support type inquiry through isa, cast, and dyn_cast:

237staticboolclassof(constSCEV *S) {

238return S->getSCEVType() ==scAddExpr || S->getSCEVType() ==scMulExpr ||

239 S->getSCEVType() ==scSMaxExpr || S->getSCEVType() ==scUMaxExpr ||

240 S->getSCEVType() ==scSMinExpr || S->getSCEVType() ==scUMinExpr ||

241 S->getSCEVType() ==scSequentialUMinExpr ||

242 S->getSCEVType() ==scAddRecExpr;

243 }

244};

245

246/// This node is the base class for n'ary commutative operators.

247classSCEVCommutativeExpr :publicSCEVNAryExpr {

248protected:

249SCEVCommutativeExpr(constFoldingSetNodeIDRef ID,enumSCEVTypes T,

250constSCEV *const *O,size_tN)

251 :SCEVNAryExpr(ID,T, O,N) {}

252

253public:

254 /// Methods for support type inquiry through isa, cast, and dyn_cast:

255staticboolclassof(constSCEV *S) {

256return S->getSCEVType() ==scAddExpr || S->getSCEVType() ==scMulExpr ||

257 S->getSCEVType() ==scSMaxExpr || S->getSCEVType() ==scUMaxExpr ||

258 S->getSCEVType() ==scSMinExpr || S->getSCEVType() ==scUMinExpr;

259 }

260

261 /// Set flags for a non-recurrence without clearing previously set flags.

262voidsetNoWrapFlags(NoWrapFlags Flags) {SubclassData |= Flags; }

263};

264

265/// This node represents an addition of some number of SCEVs.

266classSCEVAddExpr :publicSCEVCommutativeExpr {

267friendclassScalarEvolution;

268

269Type *Ty;

270

271SCEVAddExpr(constFoldingSetNodeIDRef ID,constSCEV *const *O,size_tN)

272 :SCEVCommutativeExpr(ID,scAddExpr, O,N) {

273auto *FirstPointerTypedOp =find_if(operands(), [](constSCEV *Op) {

274returnOp->getType()->isPointerTy();

275 });

276if (FirstPointerTypedOp !=operands().end())

277 Ty = (*FirstPointerTypedOp)->getType();

278else

279 Ty =getOperand(0)->getType();

280 }

281

282public:

283Type *getType() const{return Ty; }

284

285 /// Methods for support type inquiry through isa, cast, and dyn_cast:

286staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scAddExpr; }

287};

288

289/// This node represents multiplication of some number of SCEVs.

290classSCEVMulExpr :publicSCEVCommutativeExpr {

291friendclassScalarEvolution;

292

293SCEVMulExpr(constFoldingSetNodeIDRef ID,constSCEV *const *O,size_tN)

294 :SCEVCommutativeExpr(ID,scMulExpr, O,N) {}

295

296public:

297Type *getType() const{returngetOperand(0)->getType(); }

298

299 /// Methods for support type inquiry through isa, cast, and dyn_cast:

300staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scMulExpr; }

301};

302

303/// This class represents a binary unsigned division operation.

304classSCEVUDivExpr :publicSCEV {

305friendclassScalarEvolution;

306

307 std::array<const SCEV *, 2>Operands;

308

309SCEVUDivExpr(constFoldingSetNodeIDRef ID,constSCEV *lhs,constSCEV *rhs)

310 :SCEV(ID,scUDivExpr,computeExpressionSize({lhs, rhs})) {

311Operands[0] = lhs;

312Operands[1] = rhs;

313 }

314

315public:

316constSCEV *getLHS() const{returnOperands[0]; }

317constSCEV *getRHS() const{returnOperands[1]; }

318size_tgetNumOperands() const{return 2; }

319constSCEV *getOperand(unsigned i) const{

320assert((i == 0 || i == 1) &&"Operand index out of range!");

321return i == 0 ?getLHS() :getRHS();

322 }

323

324ArrayRef<const SCEV *>operands() const{returnOperands; }

325

326Type *getType() const{

327// In most cases the types of LHS and RHS will be the same, but in some

328// crazy cases one or the other may be a pointer. ScalarEvolution doesn't

329// depend on the type for correctness, but handling types carefully can

330// avoid extra casts in the SCEVExpander. The LHS is more likely to be

331// a pointer type than the RHS, so use the RHS' type here.

332returngetRHS()->getType();

333 }

334

335 /// Methods for support type inquiry through isa, cast, and dyn_cast:

336staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scUDivExpr; }

337};

338

339/// This node represents a polynomial recurrence on the trip count

340/// of the specified loop. This is the primary focus of the

341/// ScalarEvolution framework; all the other SCEV subclasses are

342/// mostly just supporting infrastructure to allow SCEVAddRecExpr

343/// expressions to be created and analyzed.

344///

345/// All operands of an AddRec are required to be loop invariant.

346///

347classSCEVAddRecExpr :publicSCEVNAryExpr {

348friendclassScalarEvolution;

349

350constLoop *L;

351

352SCEVAddRecExpr(constFoldingSetNodeIDRef ID,constSCEV *const *O,size_tN,

353constLoop *l)

354 :SCEVNAryExpr(ID,scAddRecExpr, O,N), L(l) {}

355

356public:

357Type *getType() const{returngetStart()->getType(); }

358constSCEV *getStart() const{returnOperands[0]; }

359constLoop *getLoop() const{return L; }

360

361 /// Constructs and returns the recurrence indicating how much this

362 /// expression steps by. If this is a polynomial of degree N, it

363 /// returns a chrec of degree N-1. We cannot determine whether

364 /// the step recurrence has self-wraparound.

365constSCEV *getStepRecurrence(ScalarEvolution &SE) const{

366if (isAffine())

367returngetOperand(1);

368return SE.getAddRecExpr(

369SmallVector<const SCEV *, 3>(operands().drop_front()),getLoop(),

370FlagAnyWrap);

371 }

372

373 /// Return true if this represents an expression A + B*x where A

374 /// and B are loop invariant values.

375boolisAffine() const{

376// We know that the start value is invariant. This expression is thus

377// affine iff the step is also invariant.

378returngetNumOperands() == 2;

379 }

380

381 /// Return true if this represents an expression A + B*x + C*x^2

382 /// where A, B and C are loop invariant values. This corresponds

383 /// to an addrec of the form {L,+,M,+,N}

384boolisQuadratic() const{returngetNumOperands() == 3; }

385

386 /// Set flags for a recurrence without clearing any previously set flags.

387 /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here

388 /// to make it easier to propagate flags.

389voidsetNoWrapFlags(NoWrapFlags Flags) {

390if (Flags & (FlagNUW |FlagNSW))

391 Flags =ScalarEvolution::setFlags(Flags,FlagNW);

392SubclassData |= Flags;

393 }

394

395 /// Return the value of this chain of recurrences at the specified

396 /// iteration number.

397constSCEV *evaluateAtIteration(constSCEV *It,ScalarEvolution &SE)const;

398

399 /// Return the value of this chain of recurrences at the specified iteration

400 /// number. Takes an explicit list of operands to represent an AddRec.

401staticconstSCEV *evaluateAtIteration(ArrayRef<const SCEV *>Operands,

402constSCEV *It,ScalarEvolution &SE);

403

404 /// Return the number of iterations of this loop that produce

405 /// values in the specified constant range. Another way of

406 /// looking at this is that it returns the first iteration number

407 /// where the value is not in the condition, thus computing the

408 /// exit count. If the iteration count can't be computed, an

409 /// instance of SCEVCouldNotCompute is returned.

410constSCEV *getNumIterationsInRange(constConstantRange &Range,

411ScalarEvolution &SE)const;

412

413 /// Return an expression representing the value of this expression

414 /// one iteration of the loop ahead.

415constSCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE)const;

416

417 /// Methods for support type inquiry through isa, cast, and dyn_cast:

418staticboolclassof(constSCEV *S) {

419return S->getSCEVType() ==scAddRecExpr;

420 }

421};

422

423/// This node is the base class min/max selections.

424classSCEVMinMaxExpr :publicSCEVCommutativeExpr {

425friendclassScalarEvolution;

426

427staticbool isMinMaxType(enumSCEVTypes T) {

428returnT ==scSMaxExpr ||T ==scUMaxExpr ||T ==scSMinExpr ||

429T ==scUMinExpr;

430 }

431

432protected:

433 /// Note: Constructing subclasses via this constructor is allowed

434SCEVMinMaxExpr(constFoldingSetNodeIDRef ID,enumSCEVTypes T,

435constSCEV *const *O,size_tN)

436 :SCEVCommutativeExpr(ID,T, O,N) {

437assert(isMinMaxType(T));

438// Min and max never overflow

439setNoWrapFlags((NoWrapFlags)(FlagNUW |FlagNSW));

440 }

441

442public:

443Type *getType() const{returngetOperand(0)->getType(); }

444

445staticboolclassof(constSCEV *S) {return isMinMaxType(S->getSCEVType()); }

446

447staticenumSCEVTypes negate(enumSCEVTypes T) {

448switch (T) {

449casescSMaxExpr:

450returnscSMinExpr;

451casescSMinExpr:

452returnscSMaxExpr;

453casescUMaxExpr:

454returnscUMinExpr;

455casescUMinExpr:

456returnscUMaxExpr;

457default:

458llvm_unreachable("Not a min or max SCEV type!");

459 }

460 }

461};

462

463/// This class represents a signed maximum selection.

464classSCEVSMaxExpr :publicSCEVMinMaxExpr {

465friendclassScalarEvolution;

466

467SCEVSMaxExpr(constFoldingSetNodeIDRef ID,constSCEV *const *O,size_tN)

468 :SCEVMinMaxExpr(ID,scSMaxExpr, O,N) {}

469

470public:

471 /// Methods for support type inquiry through isa, cast, and dyn_cast:

472staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scSMaxExpr; }

473};

474

475/// This class represents an unsigned maximum selection.

476classSCEVUMaxExpr :publicSCEVMinMaxExpr {

477friendclassScalarEvolution;

478

479SCEVUMaxExpr(constFoldingSetNodeIDRef ID,constSCEV *const *O,size_tN)

480 :SCEVMinMaxExpr(ID,scUMaxExpr, O,N) {}

481

482public:

483 /// Methods for support type inquiry through isa, cast, and dyn_cast:

484staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scUMaxExpr; }

485};

486

487/// This class represents a signed minimum selection.

488classSCEVSMinExpr :publicSCEVMinMaxExpr {

489friendclassScalarEvolution;

490

491SCEVSMinExpr(constFoldingSetNodeIDRef ID,constSCEV *const *O,size_tN)

492 :SCEVMinMaxExpr(ID,scSMinExpr, O,N) {}

493

494public:

495 /// Methods for support type inquiry through isa, cast, and dyn_cast:

496staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scSMinExpr; }

497};

498

499/// This class represents an unsigned minimum selection.

500classSCEVUMinExpr :publicSCEVMinMaxExpr {

501friendclassScalarEvolution;

502

503SCEVUMinExpr(constFoldingSetNodeIDRef ID,constSCEV *const *O,size_tN)

504 :SCEVMinMaxExpr(ID,scUMinExpr, O,N) {}

505

506public:

507 /// Methods for support type inquiry through isa, cast, and dyn_cast:

508staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scUMinExpr; }

509};

510

511/// This node is the base class for sequential/in-order min/max selections.

512/// Note that their fundamental difference from SCEVMinMaxExpr's is that they

513/// are early-returning upon reaching saturation point.

514/// I.e. given `0 umin_seq poison`, the result will be `0`, while the result of

515/// `0 umin poison` is `poison`. When returning early, later expressions are not

516/// executed, so `0 umin_seq (%x u/ 0)` does not result in undefined behavior.

517classSCEVSequentialMinMaxExpr :publicSCEVNAryExpr {

518friendclassScalarEvolution;

519

520staticbool isSequentialMinMaxType(enumSCEVTypes T) {

521returnT ==scSequentialUMinExpr;

522 }

523

524 /// Set flags for a non-recurrence without clearing previously set flags.

525void setNoWrapFlags(NoWrapFlags Flags) {SubclassData |= Flags; }

526

527protected:

528 /// Note: Constructing subclasses via this constructor is allowed

529SCEVSequentialMinMaxExpr(constFoldingSetNodeIDRef ID,enumSCEVTypes T,

530constSCEV *const *O,size_tN)

531 :SCEVNAryExpr(ID,T, O,N) {

532assert(isSequentialMinMaxType(T));

533// Min and max never overflow

534 setNoWrapFlags((NoWrapFlags)(FlagNUW |FlagNSW));

535 }

536

537public:

538Type *getType() const{returngetOperand(0)->getType(); }

539

540staticSCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty) {

541assert(isSequentialMinMaxType(Ty));

542switch (Ty) {

543casescSequentialUMinExpr:

544returnscUMinExpr;

545default:

546llvm_unreachable("Not a sequential min/max type.");

547 }

548 }

549

550SCEVTypes getEquivalentNonSequentialSCEVType() const{

551returngetEquivalentNonSequentialSCEVType(getSCEVType());

552 }

553

554staticboolclassof(constSCEV *S) {

555return isSequentialMinMaxType(S->getSCEVType());

556 }

557};

558

559/// This class represents a sequential/in-order unsigned minimum selection.

560classSCEVSequentialUMinExpr :publicSCEVSequentialMinMaxExpr {

561friendclassScalarEvolution;

562

563SCEVSequentialUMinExpr(constFoldingSetNodeIDRef ID,constSCEV *const *O,

564size_tN)

565 :SCEVSequentialMinMaxExpr(ID,scSequentialUMinExpr, O,N) {}

566

567public:

568 /// Methods for support type inquiry through isa, cast, and dyn_cast:

569staticboolclassof(constSCEV *S) {

570return S->getSCEVType() ==scSequentialUMinExpr;

571 }

572};

573

574/// This means that we are dealing with an entirely unknown SCEV

575/// value, and only represent it as its LLVM Value. This is the

576/// "bottom" value for the analysis.

577classSCEVUnknown final :publicSCEV,privateCallbackVH {

578friendclassScalarEvolution;

579

580 /// The parent ScalarEvolution value. This is used to update the

581 /// parent's maps when the value associated with a SCEVUnknown is

582 /// deleted or RAUW'd.

583ScalarEvolution *SE;

584

585 /// The next pointer in the linked list of all SCEVUnknown

586 /// instances owned by a ScalarEvolution.

587SCEVUnknown *Next;

588

589SCEVUnknown(constFoldingSetNodeIDRef ID,Value *V,ScalarEvolution *se,

590SCEVUnknown *next)

591 :SCEV(ID,scUnknown, 1),CallbackVH(V), SE(se), Next(next) {}

592

593// Implement CallbackVH.

594void deleted()override;

595void allUsesReplacedWith(Value *New)override;

596

597public:

598Value *getValue() const{returngetValPtr(); }

599

600Type *getType() const{returngetValPtr()->getType(); }

601

602 /// Methods for support type inquiry through isa, cast, and dyn_cast:

603staticboolclassof(constSCEV *S) {return S->getSCEVType() ==scUnknown; }

604};

605

606/// This class defines a simple visitor class that may be used for

607/// various SCEV analysis purposes.

608template <typename SC,typename RetVal =void>structSCEVVisitor {

609 RetValvisit(constSCEV *S) {

610switch (S->getSCEVType()) {

611casescConstant:

612return ((SC *)this)->visitConstant((constSCEVConstant *)S);

613casescVScale:

614return ((SC *)this)->visitVScale((constSCEVVScale *)S);

615casescPtrToInt:

616return ((SC *)this)->visitPtrToIntExpr((constSCEVPtrToIntExpr *)S);

617casescTruncate:

618return ((SC *)this)->visitTruncateExpr((constSCEVTruncateExpr *)S);

619casescZeroExtend:

620return ((SC *)this)->visitZeroExtendExpr((constSCEVZeroExtendExpr *)S);

621casescSignExtend:

622return ((SC *)this)->visitSignExtendExpr((constSCEVSignExtendExpr *)S);

623casescAddExpr:

624return ((SC *)this)->visitAddExpr((constSCEVAddExpr *)S);

625casescMulExpr:

626return ((SC *)this)->visitMulExpr((constSCEVMulExpr *)S);

627casescUDivExpr:

628return ((SC *)this)->visitUDivExpr((constSCEVUDivExpr *)S);

629casescAddRecExpr:

630return ((SC *)this)->visitAddRecExpr((constSCEVAddRecExpr *)S);

631casescSMaxExpr:

632return ((SC *)this)->visitSMaxExpr((constSCEVSMaxExpr *)S);

633casescUMaxExpr:

634return ((SC *)this)->visitUMaxExpr((constSCEVUMaxExpr *)S);

635casescSMinExpr:

636return ((SC *)this)->visitSMinExpr((constSCEVSMinExpr *)S);

637casescUMinExpr:

638return ((SC *)this)->visitUMinExpr((constSCEVUMinExpr *)S);

639casescSequentialUMinExpr:

640return ((SC *)this)

641 ->visitSequentialUMinExpr((constSCEVSequentialUMinExpr *)S);

642casescUnknown:

643return ((SC *)this)->visitUnknown((constSCEVUnknown *)S);

644casescCouldNotCompute:

645return ((SC *)this)->visitCouldNotCompute((constSCEVCouldNotCompute *)S);

646 }

647llvm_unreachable("Unknown SCEV kind!");

648 }

649

650 RetValvisitCouldNotCompute(constSCEVCouldNotCompute *S) {

651llvm_unreachable("Invalid use of SCEVCouldNotCompute!");

652 }

653};

654

655/// Visit all nodes in the expression tree using worklist traversal.

656///

657/// Visitor implements:

658/// // return true to follow this node.

659/// bool follow(const SCEV *S);

660/// // return true to terminate the search.

661/// bool isDone();

662template <typename SV>classSCEVTraversal {

663 SV &Visitor;

664SmallVector<const SCEV *, 8> Worklist;

665SmallPtrSet<const SCEV *, 8> Visited;

666

667void push(constSCEV *S) {

668if (Visited.insert(S).second && Visitor.follow(S))

669 Worklist.push_back(S);

670 }

671

672public:

673SCEVTraversal(SV &V) : Visitor(V) {}

674

675voidvisitAll(constSCEV *Root) {

676 push(Root);

677while (!Worklist.empty() && !Visitor.isDone()) {

678constSCEV *S = Worklist.pop_back_val();

679

680switch (S->getSCEVType()) {

681casescConstant:

682casescVScale:

683casescUnknown:

684continue;

685casescPtrToInt:

686casescTruncate:

687casescZeroExtend:

688casescSignExtend:

689casescAddExpr:

690casescMulExpr:

691casescUDivExpr:

692casescSMaxExpr:

693casescUMaxExpr:

694casescSMinExpr:

695casescUMinExpr:

696casescSequentialUMinExpr:

697casescAddRecExpr:

698for (constauto *Op : S->operands()) {

699 push(Op);

700if (Visitor.isDone())

701break;

702 }

703continue;

704casescCouldNotCompute:

705llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");

706 }

707llvm_unreachable("Unknown SCEV kind!");

708 }

709 }

710};

711

712/// Use SCEVTraversal to visit all nodes in the given expression tree.

713template <typename SV>voidvisitAll(constSCEV *Root, SV &Visitor) {

714SCEVTraversal<SV>T(Visitor);

715T.visitAll(Root);

716}

717

718/// Return true if any node in \p Root satisfies the predicate \p Pred.

719template <typename PredTy>

720boolSCEVExprContains(constSCEV *Root, PredTy Pred) {

721structFindClosure {

722bool Found =false;

723 PredTy Pred;

724

725 FindClosure(PredTy Pred) : Pred(Pred) {}

726

727bool follow(constSCEV *S) {

728if (!Pred(S))

729returntrue;

730

731 Found =true;

732returnfalse;

733 }

734

735bool isDone() const{return Found; }

736 };

737

738 FindClosure FC(Pred);

739visitAll(Root, FC);

740return FC.Found;

741}

742

743/// This visitor recursively visits a SCEV expression and re-writes it.

744/// The result from each visit is cached, so it will return the same

745/// SCEV for the same input.

746template <typename SC>

747classSCEVRewriteVisitor :publicSCEVVisitor<SC, const SCEV *> {

748protected:

749ScalarEvolution &SE;

750// Memoize the result of each visit so that we only compute once for

751// the same input SCEV. This is to avoid redundant computations when

752// a SCEV is referenced by multiple SCEVs. Without memoization, this

753// visit algorithm would have exponential time complexity in the worst

754// case, causing the compiler to hang on certain tests.

755SmallDenseMap<const SCEV *, const SCEV *>RewriteResults;

756

757public:

758SCEVRewriteVisitor(ScalarEvolution &SE) :SE(SE) {}

759

760constSCEV *visit(constSCEV *S) {

761auto It =RewriteResults.find(S);

762if (It !=RewriteResults.end())

763return It->second;

764auto *Visited =SCEVVisitor<SC, const SCEV *>::visit(S);

765auto Result =RewriteResults.try_emplace(S, Visited);

766assert(Result.second &&"Should insert a new entry");

767return Result.first->second;

768 }

769

770constSCEV *visitConstant(constSCEVConstant *Constant) {returnConstant; }

771

772constSCEV *visitVScale(constSCEVVScale *VScale) {return VScale; }

773

774constSCEV *visitPtrToIntExpr(constSCEVPtrToIntExpr *Expr) {

775constSCEV *Operand = ((SC *)this)->visit(Expr->getOperand());

776return Operand == Expr->getOperand()

777 ? Expr

778 :SE.getPtrToIntExpr(Operand, Expr->getType());

779 }

780

781constSCEV *visitTruncateExpr(constSCEVTruncateExpr *Expr) {

782constSCEV *Operand = ((SC *)this)->visit(Expr->getOperand());

783return Operand == Expr->getOperand()

784 ? Expr

785 :SE.getTruncateExpr(Operand, Expr->getType());

786 }

787

788constSCEV *visitZeroExtendExpr(constSCEVZeroExtendExpr *Expr) {

789constSCEV *Operand = ((SC *)this)->visit(Expr->getOperand());

790return Operand == Expr->getOperand()

791 ? Expr

792 :SE.getZeroExtendExpr(Operand, Expr->getType());

793 }

794

795constSCEV *visitSignExtendExpr(constSCEVSignExtendExpr *Expr) {

796constSCEV *Operand = ((SC *)this)->visit(Expr->getOperand());

797return Operand == Expr->getOperand()

798 ? Expr

799 :SE.getSignExtendExpr(Operand, Expr->getType());

800 }

801

802constSCEV *visitAddExpr(constSCEVAddExpr *Expr) {

803SmallVector<const SCEV *, 2>Operands;

804bool Changed =false;

805for (constauto *Op : Expr->operands()) {

806Operands.push_back(((SC *)this)->visit(Op));

807 Changed |=Op !=Operands.back();

808 }

809return !Changed ? Expr :SE.getAddExpr(Operands);

810 }

811

812constSCEV *visitMulExpr(constSCEVMulExpr *Expr) {

813SmallVector<const SCEV *, 2>Operands;

814bool Changed =false;

815for (constauto *Op : Expr->operands()) {

816Operands.push_back(((SC *)this)->visit(Op));

817 Changed |=Op !=Operands.back();

818 }

819return !Changed ? Expr :SE.getMulExpr(Operands);

820 }

821

822constSCEV *visitUDivExpr(constSCEVUDivExpr *Expr) {

823auto *LHS = ((SC *)this)->visit(Expr->getLHS());

824auto *RHS = ((SC *)this)->visit(Expr->getRHS());

825bool Changed =LHS != Expr->getLHS() ||RHS != Expr->getRHS();

826return !Changed ? Expr :SE.getUDivExpr(LHS,RHS);

827 }

828

829constSCEV *visitAddRecExpr(constSCEVAddRecExpr *Expr) {

830SmallVector<const SCEV *, 2>Operands;

831bool Changed =false;

832for (constauto *Op : Expr->operands()) {

833Operands.push_back(((SC *)this)->visit(Op));

834 Changed |=Op !=Operands.back();

835 }

836return !Changed ? Expr

837 :SE.getAddRecExpr(Operands, Expr->getLoop(),

838 Expr->getNoWrapFlags());

839 }

840

841constSCEV *visitSMaxExpr(constSCEVSMaxExpr *Expr) {

842SmallVector<const SCEV *, 2>Operands;

843bool Changed =false;

844for (constauto *Op : Expr->operands()) {

845Operands.push_back(((SC *)this)->visit(Op));

846 Changed |=Op !=Operands.back();

847 }

848return !Changed ? Expr :SE.getSMaxExpr(Operands);

849 }

850

851constSCEV *visitUMaxExpr(constSCEVUMaxExpr *Expr) {

852SmallVector<const SCEV *, 2>Operands;

853bool Changed =false;

854for (constauto *Op : Expr->operands()) {

855Operands.push_back(((SC *)this)->visit(Op));

856 Changed |=Op !=Operands.back();

857 }

858return !Changed ? Expr :SE.getUMaxExpr(Operands);

859 }

860

861constSCEV *visitSMinExpr(constSCEVSMinExpr *Expr) {

862SmallVector<const SCEV *, 2>Operands;

863bool Changed =false;

864for (constauto *Op : Expr->operands()) {

865Operands.push_back(((SC *)this)->visit(Op));

866 Changed |=Op !=Operands.back();

867 }

868return !Changed ? Expr :SE.getSMinExpr(Operands);

869 }

870

871constSCEV *visitUMinExpr(constSCEVUMinExpr *Expr) {

872SmallVector<const SCEV *, 2>Operands;

873bool Changed =false;

874for (constauto *Op : Expr->operands()) {

875Operands.push_back(((SC *)this)->visit(Op));

876 Changed |=Op !=Operands.back();

877 }

878return !Changed ? Expr :SE.getUMinExpr(Operands);

879 }

880

881constSCEV *visitSequentialUMinExpr(constSCEVSequentialUMinExpr *Expr) {

882SmallVector<const SCEV *, 2>Operands;

883bool Changed =false;

884for (constauto *Op : Expr->operands()) {

885Operands.push_back(((SC *)this)->visit(Op));

886 Changed |=Op !=Operands.back();

887 }

888return !Changed ? Expr :SE.getUMinExpr(Operands,/*Sequential=*/true);

889 }

890

891constSCEV *visitUnknown(constSCEVUnknown *Expr) {return Expr; }

892

893constSCEV *visitCouldNotCompute(constSCEVCouldNotCompute *Expr) {

894return Expr;

895 }

896};

897

898usingValueToValueMap =DenseMap<const Value *, Value *>;

899usingValueToSCEVMapTy =DenseMap<const Value *, const SCEV *>;

900

901/// The SCEVParameterRewriter takes a scalar evolution expression and updates

902/// the SCEVUnknown components following the Map (Value -> SCEV).

903classSCEVParameterRewriter :publicSCEVRewriteVisitor<SCEVParameterRewriter> {

904public:

905staticconstSCEV *rewrite(constSCEV *Scev,ScalarEvolution &SE,

906ValueToSCEVMapTy &Map) {

907SCEVParameterRewriter Rewriter(SE, Map);

908returnRewriter.visit(Scev);

909 }

910

911SCEVParameterRewriter(ScalarEvolution &SE,ValueToSCEVMapTy &M)

912 :SCEVRewriteVisitor(SE), Map(M) {}

913

914constSCEV *visitUnknown(constSCEVUnknown *Expr) {

915autoI = Map.find(Expr->getValue());

916if (I == Map.end())

917return Expr;

918returnI->second;

919 }

920

921private:

922ValueToSCEVMapTy &Map;

923};

924

925usingLoopToScevMapT =DenseMap<const Loop *, const SCEV *>;

926

927/// The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies

928/// the Map (Loop -> SCEV) to all AddRecExprs.

929classSCEVLoopAddRecRewriter

930 :publicSCEVRewriteVisitor<SCEVLoopAddRecRewriter> {

931public:

932SCEVLoopAddRecRewriter(ScalarEvolution &SE,LoopToScevMapT &M)

933 :SCEVRewriteVisitor(SE), Map(M) {}

934

935staticconstSCEV *rewrite(constSCEV *Scev,LoopToScevMapT &Map,

936ScalarEvolution &SE) {

937SCEVLoopAddRecRewriter Rewriter(SE, Map);

938returnRewriter.visit(Scev);

939 }

940

941constSCEV *visitAddRecExpr(constSCEVAddRecExpr *Expr) {

942SmallVector<const SCEV *, 2>Operands;

943for (constSCEV *Op : Expr->operands())

944Operands.push_back(visit(Op));

945

946constLoop *L = Expr->getLoop();

947if (0 == Map.count(L))

948returnSE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());

949

950returnSCEVAddRecExpr::evaluateAtIteration(Operands, Map[L],SE);

951 }

952

953private:

954LoopToScevMapT &Map;

955};

956

957}// end namespace llvm

958

959#endif// LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

Type

RelocType Type

Definition:COFFYAML.cpp:410

Casting.h

Constants.h

This file contains the declarations for the subclasses of Constant, which represent the different fla...

DenseMap.h

This file defines the DenseMap class.

Size

uint64_t Size

Definition:ELFObjHandler.cpp:81

#define op(i)

#define I(x, y, z)

Definition:MD5.cpp:58

Operands

mir Rename Register Operands

Definition:MIRNamerPass.cpp:74

#define T

Definition:Mips16ISelLowering.cpp:341

Range

ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))

assert

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

ScalarEvolution.h

SmallPtrSet.h

This file defines the SmallPtrSet class.

SmallVector.h

This file defines the SmallVector class.

ValueHandle.h

Rewriter

Virtual Register Rewriter

Definition:VirtRegMap.cpp:261

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

llvm::APInt

Class for arbitrary precision integers.

Definition:APInt.h:78

llvm::ArrayRef

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

Definition:ArrayRef.h:41

llvm::CallbackVH

Value handle with callbacks on RAUW and destruction.

Definition:ValueHandle.h:383

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition:Constants.h:83

llvm::ConstantInt::getValue

const APInt & getValue() const

Return the constant as an APInt value reference.

Definition:Constants.h:148

llvm::ConstantRange

This class represents a range of values.

Definition:ConstantRange.h:47

llvm::Constant

This is an important base class in LLVM.

Definition:Constant.h:42

llvm::DWARFExpression::Operation

This class represents an Operation in the Expression.

Definition:DWARFExpression.h:32

llvm::DenseMapBase::find

iterator find(const_arg_type_t< KeyT > Val)

Definition:DenseMap.h:156

llvm::DenseMapBase::count

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

Definition:DenseMap.h:152

llvm::DenseMapBase::end

iterator end()

Definition:DenseMap.h:84

llvm::DenseMap

Definition:DenseMap.h:727

llvm::FoldingSetNodeIDRef

FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...

Definition:FoldingSet.h:290

llvm::Loop

Represents a single loop in the control flow graph.

Definition:LoopInfo.h:39

llvm::SCEVAddExpr

This node represents an addition of some number of SCEVs.

Definition:ScalarEvolutionExpressions.h:266

llvm::SCEVAddExpr::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:283

llvm::SCEVAddExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:286

llvm::SCEVAddRecExpr

This node represents a polynomial recurrence on the trip count of the specified loop.

Definition:ScalarEvolutionExpressions.h:347

llvm::SCEVAddRecExpr::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:357

llvm::SCEVAddRecExpr::getStart

const SCEV * getStart() const

Definition:ScalarEvolutionExpressions.h:358

llvm::SCEVAddRecExpr::evaluateAtIteration

const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const

Return the value of this chain of recurrences at the specified iteration number.

Definition:ScalarEvolution.cpp:989

llvm::SCEVAddRecExpr::getStepRecurrence

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

Constructs and returns the recurrence indicating how much this expression steps by.

Definition:ScalarEvolutionExpressions.h:365

llvm::SCEVAddRecExpr::setNoWrapFlags

void setNoWrapFlags(NoWrapFlags Flags)

Set flags for a recurrence without clearing any previously set flags.

Definition:ScalarEvolutionExpressions.h:389

llvm::SCEVAddRecExpr::isAffine

bool isAffine() const

Return true if this represents an expression A + B*x where A and B are loop invariant values.

Definition:ScalarEvolutionExpressions.h:375

llvm::SCEVAddRecExpr::isQuadratic

bool isQuadratic() const

Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...

Definition:ScalarEvolutionExpressions.h:384

llvm::SCEVAddRecExpr::getNumIterationsInRange

const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const

Return the number of iterations of this loop that produce values in the specified constant range.

Definition:ScalarEvolution.cpp:13480

llvm::SCEVAddRecExpr::getPostIncExpr

const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const

Return an expression representing the value of this expression one iteration of the loop ahead.

Definition:ScalarEvolution.cpp:13552

llvm::SCEVAddRecExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:418

llvm::SCEVAddRecExpr::getLoop

const Loop * getLoop() const

Definition:ScalarEvolutionExpressions.h:359

llvm::SCEVCastExpr

This is the base class for unary cast operator classes.

Definition:ScalarEvolutionExpressions.h:103

llvm::SCEVCastExpr::Ty

Type * Ty

Definition:ScalarEvolutionExpressions.h:106

llvm::SCEVCastExpr::getOperand

const SCEV * getOperand(unsigned i) const

Definition:ScalarEvolutionExpressions.h:113

llvm::SCEVCastExpr::Op

const SCEV * Op

Definition:ScalarEvolutionExpressions.h:105

llvm::SCEVCastExpr::operands

ArrayRef< const SCEV * > operands() const

Definition:ScalarEvolutionExpressions.h:117

llvm::SCEVCastExpr::getNumOperands

size_t getNumOperands() const

Definition:ScalarEvolutionExpressions.h:118

llvm::SCEVCastExpr::getOperand

const SCEV * getOperand() const

Definition:ScalarEvolutionExpressions.h:112

llvm::SCEVCastExpr::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:119

llvm::SCEVCastExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:122

llvm::SCEVCommutativeExpr

This node is the base class for n'ary commutative operators.

Definition:ScalarEvolutionExpressions.h:247

llvm::SCEVCommutativeExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:255

llvm::SCEVCommutativeExpr::setNoWrapFlags

void setNoWrapFlags(NoWrapFlags Flags)

Set flags for a non-recurrence without clearing previously set flags.

Definition:ScalarEvolutionExpressions.h:262

llvm::SCEVCommutativeExpr::SCEVCommutativeExpr

SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)

Definition:ScalarEvolutionExpressions.h:249

llvm::SCEVConstant

This class represents a constant integer value.

Definition:ScalarEvolutionExpressions.h:60

llvm::SCEVConstant::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:72

llvm::SCEVConstant::getValue

ConstantInt * getValue() const

Definition:ScalarEvolutionExpressions.h:69

llvm::SCEVConstant::getAPInt

const APInt & getAPInt() const

Definition:ScalarEvolutionExpressions.h:70

llvm::SCEVConstant::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:75

llvm::SCEVIntegralCastExpr

This is the base class for unary integral cast operator classes.

Definition:ScalarEvolutionExpressions.h:141

llvm::SCEVIntegralCastExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:148

llvm::SCEVLoopAddRecRewriter

The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies the Map (Loop -> SCEV) to ...

Definition:ScalarEvolutionExpressions.h:930

llvm::SCEVLoopAddRecRewriter::rewrite

static const SCEV * rewrite(const SCEV *Scev, LoopToScevMapT &Map, ScalarEvolution &SE)

Definition:ScalarEvolutionExpressions.h:935

llvm::SCEVLoopAddRecRewriter::visitAddRecExpr

const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)

Definition:ScalarEvolutionExpressions.h:941

llvm::SCEVLoopAddRecRewriter::SCEVLoopAddRecRewriter

SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)

Definition:ScalarEvolutionExpressions.h:932

llvm::SCEVMinMaxExpr

This node is the base class min/max selections.

Definition:ScalarEvolutionExpressions.h:424

llvm::SCEVMinMaxExpr::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:443

llvm::SCEVMinMaxExpr::negate

static enum SCEVTypes negate(enum SCEVTypes T)

Definition:ScalarEvolutionExpressions.h:447

llvm::SCEVMinMaxExpr::SCEVMinMaxExpr

SCEVMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)

Note: Constructing subclasses via this constructor is allowed.

Definition:ScalarEvolutionExpressions.h:434

llvm::SCEVMinMaxExpr::classof

static bool classof(const SCEV *S)

Definition:ScalarEvolutionExpressions.h:445

llvm::SCEVMulExpr

This node represents multiplication of some number of SCEVs.

Definition:ScalarEvolutionExpressions.h:290

llvm::SCEVMulExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:300

llvm::SCEVMulExpr::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:297

llvm::SCEVNAryExpr

This node is a base class providing common functionality for n'ary operators.

Definition:ScalarEvolutionExpressions.h:196

llvm::SCEVNAryExpr::hasNoUnsignedWrap

bool hasNoUnsignedWrap() const

Definition:ScalarEvolutionExpressions.h:226

llvm::SCEVNAryExpr::NumOperands

size_t NumOperands

Definition:ScalarEvolutionExpressions.h:203

llvm::SCEVNAryExpr::hasNoSelfWrap

bool hasNoSelfWrap() const

Definition:ScalarEvolutionExpressions.h:234

llvm::SCEVNAryExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:237

llvm::SCEVNAryExpr::getNumOperands

size_t getNumOperands() const

Definition:ScalarEvolutionExpressions.h:211

llvm::SCEVNAryExpr::hasNoSignedWrap

bool hasNoSignedWrap() const

Definition:ScalarEvolutionExpressions.h:230

llvm::SCEVNAryExpr::getNoWrapFlags

NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const

Definition:ScalarEvolutionExpressions.h:222

llvm::SCEVNAryExpr::SCEVNAryExpr

SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)

Definition:ScalarEvolutionExpressions.h:205

llvm::SCEVNAryExpr::getOperand

const SCEV * getOperand(unsigned i) const

Definition:ScalarEvolutionExpressions.h:213

llvm::SCEVNAryExpr::Operands

const SCEV *const * Operands

Definition:ScalarEvolutionExpressions.h:202

llvm::SCEVNAryExpr::operands

ArrayRef< const SCEV * > operands() const

Definition:ScalarEvolutionExpressions.h:218

llvm::SCEVParameterRewriter

The SCEVParameterRewriter takes a scalar evolution expression and updates the SCEVUnknown components ...

Definition:ScalarEvolutionExpressions.h:903

llvm::SCEVParameterRewriter::visitUnknown

const SCEV * visitUnknown(const SCEVUnknown *Expr)

Definition:ScalarEvolutionExpressions.h:914

llvm::SCEVParameterRewriter::rewrite

static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)

Definition:ScalarEvolutionExpressions.h:905

llvm::SCEVParameterRewriter::SCEVParameterRewriter

SCEVParameterRewriter(ScalarEvolution &SE, ValueToSCEVMapTy &M)

Definition:ScalarEvolutionExpressions.h:911

llvm::SCEVPtrToIntExpr

This class represents a cast from a pointer to a pointer-sized integer value.

Definition:ScalarEvolutionExpressions.h:130

llvm::SCEVPtrToIntExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:137

llvm::SCEVRewriteVisitor

This visitor recursively visits a SCEV expression and re-writes it.

Definition:ScalarEvolutionExpressions.h:747

llvm::SCEVRewriteVisitor::visitSignExtendExpr

const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)

Definition:ScalarEvolutionExpressions.h:795

llvm::SCEVRewriteVisitor::visitPtrToIntExpr

const SCEV * visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr)

Definition:ScalarEvolutionExpressions.h:774

llvm::SCEVRewriteVisitor::SE

ScalarEvolution & SE

Definition:ScalarEvolutionExpressions.h:749

llvm::SCEVRewriteVisitor::visit

const SCEV * visit(const SCEV *S)

Definition:ScalarEvolutionExpressions.h:760

llvm::SCEVRewriteVisitor::visitZeroExtendExpr

const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)

Definition:ScalarEvolutionExpressions.h:788

llvm::SCEVRewriteVisitor::visitUnknown

const SCEV * visitUnknown(const SCEVUnknown *Expr)

Definition:ScalarEvolutionExpressions.h:891

llvm::SCEVRewriteVisitor::visitSMinExpr

const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)

Definition:ScalarEvolutionExpressions.h:861

llvm::SCEVRewriteVisitor::SCEVRewriteVisitor

SCEVRewriteVisitor(ScalarEvolution &SE)

Definition:ScalarEvolutionExpressions.h:758

llvm::SCEVRewriteVisitor::visitSequentialUMinExpr

const SCEV * visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr)

Definition:ScalarEvolutionExpressions.h:881

llvm::SCEVRewriteVisitor::visitAddExpr

const SCEV * visitAddExpr(const SCEVAddExpr *Expr)

Definition:ScalarEvolutionExpressions.h:802

llvm::SCEVRewriteVisitor::visitUMinExpr

const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)

Definition:ScalarEvolutionExpressions.h:871

llvm::SCEVRewriteVisitor::visitMulExpr

const SCEV * visitMulExpr(const SCEVMulExpr *Expr)

Definition:ScalarEvolutionExpressions.h:812

llvm::SCEVRewriteVisitor::RewriteResults

SmallDenseMap< const SCEV *, const SCEV * > RewriteResults

Definition:ScalarEvolutionExpressions.h:755

llvm::SCEVRewriteVisitor::visitTruncateExpr

const SCEV * visitTruncateExpr(const SCEVTruncateExpr *Expr)

Definition:ScalarEvolutionExpressions.h:781

llvm::SCEVRewriteVisitor::visitUMaxExpr

const SCEV * visitUMaxExpr(const SCEVUMaxExpr *Expr)

Definition:ScalarEvolutionExpressions.h:851

llvm::SCEVRewriteVisitor::visitSMaxExpr

const SCEV * visitSMaxExpr(const SCEVSMaxExpr *Expr)

Definition:ScalarEvolutionExpressions.h:841

llvm::SCEVRewriteVisitor::visitUDivExpr

const SCEV * visitUDivExpr(const SCEVUDivExpr *Expr)

Definition:ScalarEvolutionExpressions.h:822

llvm::SCEVRewriteVisitor::visitCouldNotCompute

const SCEV * visitCouldNotCompute(const SCEVCouldNotCompute *Expr)

Definition:ScalarEvolutionExpressions.h:893

llvm::SCEVRewriteVisitor::visitVScale

const SCEV * visitVScale(const SCEVVScale *VScale)

Definition:ScalarEvolutionExpressions.h:772

llvm::SCEVRewriteVisitor::visitAddRecExpr

const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)

Definition:ScalarEvolutionExpressions.h:829

llvm::SCEVRewriteVisitor::visitConstant

const SCEV * visitConstant(const SCEVConstant *Constant)

Definition:ScalarEvolutionExpressions.h:770

llvm::SCEVSMaxExpr

This class represents a signed maximum selection.

Definition:ScalarEvolutionExpressions.h:464

llvm::SCEVSMaxExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:472

llvm::SCEVSMinExpr

This class represents a signed minimum selection.

Definition:ScalarEvolutionExpressions.h:488

llvm::SCEVSMinExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:496

llvm::SCEVSequentialMinMaxExpr

This node is the base class for sequential/in-order min/max selections.

Definition:ScalarEvolutionExpressions.h:517

llvm::SCEVSequentialMinMaxExpr::SCEVSequentialMinMaxExpr

SCEVSequentialMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)

Note: Constructing subclasses via this constructor is allowed.

Definition:ScalarEvolutionExpressions.h:529

llvm::SCEVSequentialMinMaxExpr::classof

static bool classof(const SCEV *S)

Definition:ScalarEvolutionExpressions.h:554

llvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType

static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)

Definition:ScalarEvolutionExpressions.h:540

llvm::SCEVSequentialMinMaxExpr::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:538

llvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType

SCEVTypes getEquivalentNonSequentialSCEVType() const

Definition:ScalarEvolutionExpressions.h:550

llvm::SCEVSequentialUMinExpr

This class represents a sequential/in-order unsigned minimum selection.

Definition:ScalarEvolutionExpressions.h:560

llvm::SCEVSequentialUMinExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:569

llvm::SCEVSignExtendExpr

This class represents a sign extension of a small integer value to a larger integer value.

Definition:ScalarEvolutionExpressions.h:182

llvm::SCEVSignExtendExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:189

llvm::SCEVTraversal

Visit all nodes in the expression tree using worklist traversal.

Definition:ScalarEvolutionExpressions.h:662

llvm::SCEVTraversal::visitAll

void visitAll(const SCEV *Root)

Definition:ScalarEvolutionExpressions.h:675

llvm::SCEVTraversal::SCEVTraversal

SCEVTraversal(SV &V)

Definition:ScalarEvolutionExpressions.h:673

llvm::SCEVTruncateExpr

This class represents a truncation of an integer value to a smaller integer value.

Definition:ScalarEvolutionExpressions.h:156

llvm::SCEVTruncateExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:163

llvm::SCEVUDivExpr

This class represents a binary unsigned division operation.

Definition:ScalarEvolutionExpressions.h:304

llvm::SCEVUDivExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:336

llvm::SCEVUDivExpr::operands

ArrayRef< const SCEV * > operands() const

Definition:ScalarEvolutionExpressions.h:324

llvm::SCEVUDivExpr::getOperand

const SCEV * getOperand(unsigned i) const

Definition:ScalarEvolutionExpressions.h:319

llvm::SCEVUDivExpr::getLHS

const SCEV * getLHS() const

Definition:ScalarEvolutionExpressions.h:316

llvm::SCEVUDivExpr::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:326

llvm::SCEVUDivExpr::getNumOperands

size_t getNumOperands() const

Definition:ScalarEvolutionExpressions.h:318

llvm::SCEVUDivExpr::getRHS

const SCEV * getRHS() const

Definition:ScalarEvolutionExpressions.h:317

llvm::SCEVUMaxExpr

This class represents an unsigned maximum selection.

Definition:ScalarEvolutionExpressions.h:476

llvm::SCEVUMaxExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:484

llvm::SCEVUMinExpr

This class represents an unsigned minimum selection.

Definition:ScalarEvolutionExpressions.h:500

llvm::SCEVUMinExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:508

llvm::SCEVUnknown

This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...

Definition:ScalarEvolutionExpressions.h:577

llvm::SCEVUnknown::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:603

llvm::SCEVUnknown::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:600

llvm::SCEVUnknown::getValue

Value * getValue() const

Definition:ScalarEvolutionExpressions.h:598

llvm::SCEVVScale

This class represents the value of vscale, as used when defining the length of a scalable vector or r...

Definition:ScalarEvolutionExpressions.h:80

llvm::SCEVVScale::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:92

llvm::SCEVVScale::getType

Type * getType() const

Definition:ScalarEvolutionExpressions.h:89

llvm::SCEVZeroExtendExpr

This class represents a zero extension of a small integer value to a larger integer value.

Definition:ScalarEvolutionExpressions.h:168

llvm::SCEVZeroExtendExpr::classof

static bool classof(const SCEV *S)

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition:ScalarEvolutionExpressions.h:175

llvm::SCEV

This class represents an analyzed expression in the program.

Definition:ScalarEvolution.h:71

llvm::SCEV::operands

ArrayRef< const SCEV * > operands() const

Return operands of this SCEV expression.

Definition:ScalarEvolution.cpp:420

llvm::SCEV::getSCEVType

SCEVTypes getSCEVType() const

Definition:ScalarEvolution.h:140

llvm::SCEV::SubclassData

unsigned short SubclassData

This field is initialized to zero and may be used in subclasses to store miscellaneous information.

Definition:ScalarEvolution.h:87

llvm::SCEV::getType

Type * getType() const

Return the LLVM type of this SCEV expression.

Definition:ScalarEvolution.cpp:386

llvm::SCEV::NoWrapFlags

NoWrapFlags

NoWrapFlags are bitfield indices into SubclassData.

Definition:ScalarEvolution.h:126

llvm::SCEV::FlagAnyWrap

@ FlagAnyWrap

Definition:ScalarEvolution.h:127

llvm::SCEV::FlagNSW

@ FlagNSW

Definition:ScalarEvolution.h:130

llvm::SCEV::FlagNUW

@ FlagNUW

Definition:ScalarEvolution.h:129

llvm::SCEV::NoWrapMask

@ NoWrapMask

Definition:ScalarEvolution.h:131

llvm::SCEV::FlagNW

@ FlagNW

Definition:ScalarEvolution.h:128

llvm::ScalarEvolution

The main scalar evolution driver.

Definition:ScalarEvolution.h:447

llvm::ScalarEvolution::getSMaxExpr

const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)

Definition:ScalarEvolution.cpp:4343

llvm::ScalarEvolution::getSMinExpr

const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)

Definition:ScalarEvolution.cpp:4361

llvm::ScalarEvolution::getUMaxExpr

const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)

Definition:ScalarEvolution.cpp:4352

llvm::ScalarEvolution::getPtrToIntExpr

const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)

Definition:ScalarEvolution.cpp:1140

llvm::ScalarEvolution::getAddRecExpr

const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)

Get an add recurrence expression for the specified loop.

Definition:ScalarEvolution.cpp:3641

llvm::ScalarEvolution::getUDivExpr

const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)

Get a canonical unsigned division expression, or something simpler if possible.

Definition:ScalarEvolution.cpp:3400

llvm::ScalarEvolution::getZeroExtendExpr

const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

Definition:ScalarEvolution.cpp:1565

llvm::ScalarEvolution::getUMinExpr

const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)

Definition:ScalarEvolution.cpp:4371

llvm::ScalarEvolution::getTruncateExpr

const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

Definition:ScalarEvolution.cpp:1150

llvm::ScalarEvolution::setFlags

static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)

Definition:ScalarEvolution.h:471

llvm::ScalarEvolution::getSignExtendExpr

const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)

Definition:ScalarEvolution.cpp:1900

llvm::ScalarEvolution::getMulExpr

const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Get a canonical multiply expression, or something simpler if possible.

Definition:ScalarEvolution.cpp:3106

llvm::ScalarEvolution::getAddExpr

const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)

Get a canonical add expression, or something simpler if possible.

Definition:ScalarEvolution.cpp:2526

llvm::SmallDenseMap

Definition:DenseMap.h:883

llvm::SmallPtrSetImpl::insert

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

Definition:SmallPtrSet.h:384

llvm::SmallPtrSet

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

Definition:SmallPtrSet.h:519

llvm::SmallVectorBase::empty

bool empty() const

Definition:SmallVector.h:81

llvm::SmallVectorImpl::pop_back_val

T pop_back_val()

Definition:SmallVector.h:673

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVector

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Definition:SmallVector.h:1196

llvm::Type

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

Definition:Type.h:45

llvm::ValueHandleBase::getValPtr

Value * getValPtr() const

Definition:ValueHandle.h:99

llvm::Value

LLVM Value Representation.

Definition:Value.h:74

llvm::Value::getType

Type * getType() const

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

Definition:Value.h:255

unsigned

ErrorHandling.h

llvm_unreachable

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Definition:ErrorHandling.h:143

llvm::ISD::Constant

@ Constant

Definition:ISDOpcodes.h:76

llvm::TargetStackID::Value

Value

Definition:TargetFrameLowering.h:29

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::visitAll

void visitAll(const SCEV *Root, SV &Visitor)

Use SCEVTraversal to visit all nodes in the given expression tree.

Definition:ScalarEvolutionExpressions.h:713

llvm::computeExpressionSize

unsigned short computeExpressionSize(ArrayRef< const SCEV * > Args)

Definition:ScalarEvolutionExpressions.h:95

llvm::isPointerTy

bool isPointerTy(const Type *T)

Definition:SPIRVUtils.h:256

llvm::find_if

auto find_if(R &&Range, UnaryPredicate P)

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

Definition:STLExtras.h:1766

llvm::SCEVTypes

SCEVTypes

Definition:ScalarEvolutionExpressions.h:37

llvm::scUMinExpr

@ scUMinExpr

Definition:ScalarEvolutionExpressions.h:51

llvm::scAddRecExpr

@ scAddRecExpr

Definition:ScalarEvolutionExpressions.h:48

llvm::scSequentialUMinExpr

@ scSequentialUMinExpr

Definition:ScalarEvolutionExpressions.h:53

llvm::scAddExpr

@ scAddExpr

Definition:ScalarEvolutionExpressions.h:45

llvm::scVScale

@ scVScale

Definition:ScalarEvolutionExpressions.h:41

llvm::scSMaxExpr

@ scSMaxExpr

Definition:ScalarEvolutionExpressions.h:50

llvm::scUnknown

@ scUnknown

Definition:ScalarEvolutionExpressions.h:55

llvm::scSMinExpr

@ scSMinExpr

Definition:ScalarEvolutionExpressions.h:52

llvm::scCouldNotCompute

@ scCouldNotCompute

Definition:ScalarEvolutionExpressions.h:56

llvm::scConstant

@ scConstant

Definition:ScalarEvolutionExpressions.h:40

llvm::scSignExtend

@ scSignExtend

Definition:ScalarEvolutionExpressions.h:44

llvm::scTruncate

@ scTruncate

Definition:ScalarEvolutionExpressions.h:42

llvm::scUMaxExpr

@ scUMaxExpr

Definition:ScalarEvolutionExpressions.h:49

llvm::scZeroExtend

@ scZeroExtend

Definition:ScalarEvolutionExpressions.h:43

llvm::scPtrToInt

@ scPtrToInt

Definition:ScalarEvolutionExpressions.h:54

llvm::scUDivExpr

@ scUDivExpr

Definition:ScalarEvolutionExpressions.h:47

llvm::scMulExpr

@ scMulExpr

Definition:ScalarEvolutionExpressions.h:46

llvm::SCEVExprContains

bool SCEVExprContains(const SCEV *Root, PredTy Pred)

Return true if any node in Root satisfies the predicate Pred.

Definition:ScalarEvolutionExpressions.h:720

#define N

llvm::SCEVCouldNotCompute

An object of this class is returned by queries that could not be answered.

Definition:ScalarEvolution.h:205

llvm::SCEVVisitor

This class defines a simple visitor class that may be used for various SCEV analysis purposes.

Definition:ScalarEvolutionExpressions.h:608

llvm::SCEVVisitor::visit

RetVal visit(const SCEV *S)

Definition:ScalarEvolutionExpressions.h:609

llvm::SCEVVisitor::visitCouldNotCompute

RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S)

Definition:ScalarEvolutionExpressions.h:650