ScalarEvolutionExpressions.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

14#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H

24#include

25#include

27namespace llvm {

29class APInt;

31class ConstantInt;

32class ConstantRange;

33class Loop;

68public:

76};

88public:

93};

97 for (const auto *Arg : Args)

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

99 return (unsigned short)Size.getZExtValue();

100}

101

102

104protected:

107

110

111public:

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

115 return Op;

116 }

120

121

125 }

126};

127

128

129

132

134

135public:

136

138};

139

140

142protected:

145

146public:

147

151 }

152};

153

154

155

158

160

161public:

162

164};

165

166

167

170

172

173public:

174

177 }

178};

179

180

181

184

186

187public:

188

191 }

192};

193

194

195

197protected:

198

199

200

201

204

206 const SCEV *const *O, size_t N)

209

210public:

212

216 }

217

220 }

221

224 }

225

228 }

229

232 }

233

235

236

243 }

244};

245

246

248protected:

250 const SCEV *const *O, size_t N)

252

253public:

254

259 }

260

261

263};

264

265

268

270

275 });

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

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

278 else

280 }

281

282public:

284

285

287};

288

289

292

295

296public:

298

299

301};

302

303

306

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

308

313 }

314

315public:

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

322 }

323

325

327

328

329

330

331

333 }

334

335

337};

338

339

340

341

342

343

344

345

346

349

350 const Loop *L;

351

353 const Loop *l)

355

356public:

360

361

362

363

364

371 }

372

373

374

376

377

379 }

380

381

382

383

385

386

387

388

393 }

394

395

396

398

399

400

403

404

405

406

407

408

409

412

413

414

416

417

420 }

421};

422

423

426

427 static bool isMinMaxType(enum SCEVTypes T) {

430 }

431

432protected:

433

435 const SCEV *const *O, size_t N)

438

440 }

441

442public:

444

446

448 switch (T) {

457 default:

459 }

460 }

461};

462

463

466

469

470public:

471

473};

474

475

478

481

482public:

483

485};

486

487

490

493

494public:

495

497};

498

499

502

505

506public:

507

509};

510

511

512

513

514

515

516

519

520 static bool isSequentialMinMaxType(enum SCEVTypes T) {

522 }

523

524

526

527protected:

528

530 const SCEV *const *O, size_t N)

532 assert(isSequentialMinMaxType(T));

533

535 }

536

537public:

539

541 assert(isSequentialMinMaxType(Ty));

542 switch (Ty) {

545 default:

547 }

548 }

549

552 }

553

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

556 }

557};

558

559

562

564 size_t N)

566

567public:

568

571 }

572};

573

574

575

576

579

580

581

582

584

585

586

588

592

593

594 void deleted() override;

595 void allUsesReplacedWith(Value *New) override;

596

597public:

599

601

602

604};

605

606

607

608template <typename SC, typename RetVal = void> struct SCEVVisitor {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

640 return ((SC *)this)

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

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

646 }

648 }

649

652 }

653};

654

655

656

657

658

659

660

661

663 SV &Visitor;

666

667 void push(const SCEV *S) {

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

670 }

671

672public:

674

676 push(Root);

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

679

684 continue;

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

699 push(Op);

700 if (Visitor.isDone())

701 break;

702 }

703 continue;

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

706 }

708 }

709 }

710};

711

712

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

715 T.visitAll(Root);

716}

717

718

719template

721 struct FindClosure {

722 bool Found = false;

723 PredTy Pred;

724

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

726

727 bool follow(const SCEV *S) {

728 if (!Pred(S))

729 return true;

730

731 Found = true;

732 return false;

733 }

734

735 bool isDone() const { return Found; }

736 };

737

738 FindClosure FC(Pred);

740 return FC.Found;

741}

742

743

744

745

746template

748protected:

750

751

752

753

754

756

757public:

759

763 return It->second;

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

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

767 return Result.first->second;

768 }

769

771

773

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

777 ? Expr

779 }

780

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

784 ? Expr

786 }

787

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

791 ? Expr

793 }

794

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

798 ? Expr

800 }

801

804 bool Changed = false;

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

808 }

810 }

811

814 bool Changed = false;

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

818 }

820 }

821

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

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

827 }

828

831 bool Changed = false;

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

835 }

836 return !Changed ? Expr

839 }

840

843 bool Changed = false;

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

847 }

849 }

850

853 bool Changed = false;

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

857 }

859 }

860

863 bool Changed = false;

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

867 }

869 }

870

873 bool Changed = false;

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

877 }

879 }

880

883 bool Changed = false;

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

887 }

889 }

890

892

894 return Expr;

895 }

896};

897

900

901

902

904public:

909 }

910

913

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

917 return Expr;

918 return I->second;

919 }

920

921private:

923};

924

926

927

928

931public:

934

939 }

940

945

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

949

951 }

952

953private:

955};

956

957}

958

959#endif

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

This file defines the DenseMap class.

mir Rename Register Operands

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

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

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

Virtual Register Rewriter

Class for arbitrary precision integers.

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

Value handle with callbacks on RAUW and destruction.

This is the shared class of boolean and integer constants.

const APInt & getValue() const

Return the constant as an APInt value reference.

This class represents a range of values.

This is an important base class in LLVM.

This class represents an Operation in the Expression.

iterator find(const_arg_type_t< KeyT > Val)

size_type count(const_arg_type_t< KeyT > Val) const

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

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

Represents a single loop in the control flow graph.

This node represents an addition of some number of SCEVs.

static bool classof(const SCEV *S)

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

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

const SCEV * getStart() const

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

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

const SCEV * getStepRecurrence(ScalarEvolution &SE) const

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

void setNoWrapFlags(NoWrapFlags Flags)

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

bool isAffine() const

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

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

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.

const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const

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

static bool classof(const SCEV *S)

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

const Loop * getLoop() const

This is the base class for unary cast operator classes.

const SCEV * getOperand(unsigned i) const

ArrayRef< const SCEV * > operands() const

size_t getNumOperands() const

const SCEV * getOperand() const

static bool classof(const SCEV *S)

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

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

static bool classof(const SCEV *S)

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

void setNoWrapFlags(NoWrapFlags Flags)

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

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

This class represents a constant integer value.

ConstantInt * getValue() const

const APInt & getAPInt() const

static bool classof(const SCEV *S)

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

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

static bool classof(const SCEV *S)

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

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

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

const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)

SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)

This node is the base class min/max selections.

static enum SCEVTypes negate(enum SCEVTypes T)

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

Note: Constructing subclasses via this constructor is allowed.

static bool classof(const SCEV *S)

This node represents multiplication of some number of SCEVs.

static bool classof(const SCEV *S)

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

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

bool hasNoUnsignedWrap() const

bool hasNoSelfWrap() const

static bool classof(const SCEV *S)

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

size_t getNumOperands() const

bool hasNoSignedWrap() const

NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const

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

const SCEV * getOperand(unsigned i) const

const SCEV *const * Operands

ArrayRef< const SCEV * > operands() const

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

const SCEV * visitUnknown(const SCEVUnknown *Expr)

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

SCEVParameterRewriter(ScalarEvolution &SE, ValueToSCEVMapTy &M)

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

static bool classof(const SCEV *S)

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

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

const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)

const SCEV * visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr)

const SCEV * visit(const SCEV *S)

const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)

const SCEV * visitUnknown(const SCEVUnknown *Expr)

const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)

SCEVRewriteVisitor(ScalarEvolution &SE)

const SCEV * visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr)

const SCEV * visitAddExpr(const SCEVAddExpr *Expr)

const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)

const SCEV * visitMulExpr(const SCEVMulExpr *Expr)

SmallDenseMap< const SCEV *, const SCEV * > RewriteResults

const SCEV * visitTruncateExpr(const SCEVTruncateExpr *Expr)

const SCEV * visitUMaxExpr(const SCEVUMaxExpr *Expr)

const SCEV * visitSMaxExpr(const SCEVSMaxExpr *Expr)

const SCEV * visitUDivExpr(const SCEVUDivExpr *Expr)

const SCEV * visitCouldNotCompute(const SCEVCouldNotCompute *Expr)

const SCEV * visitVScale(const SCEVVScale *VScale)

const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)

const SCEV * visitConstant(const SCEVConstant *Constant)

This class represents a signed maximum selection.

static bool classof(const SCEV *S)

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

This class represents a signed minimum selection.

static bool classof(const SCEV *S)

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

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

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

Note: Constructing subclasses via this constructor is allowed.

static bool classof(const SCEV *S)

static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)

SCEVTypes getEquivalentNonSequentialSCEVType() const

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

static bool classof(const SCEV *S)

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

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

static bool classof(const SCEV *S)

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

Visit all nodes in the expression tree using worklist traversal.

void visitAll(const SCEV *Root)

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

static bool classof(const SCEV *S)

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

This class represents a binary unsigned division operation.

static bool classof(const SCEV *S)

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

ArrayRef< const SCEV * > operands() const

const SCEV * getOperand(unsigned i) const

const SCEV * getLHS() const

size_t getNumOperands() const

const SCEV * getRHS() const

This class represents an unsigned maximum selection.

static bool classof(const SCEV *S)

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

This class represents an unsigned minimum selection.

static bool classof(const SCEV *S)

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

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

static bool classof(const SCEV *S)

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

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

static bool classof(const SCEV *S)

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

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

static bool classof(const SCEV *S)

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

This class represents an analyzed expression in the program.

ArrayRef< const SCEV * > operands() const

Return operands of this SCEV expression.

SCEVTypes getSCEVType() const

unsigned short SubclassData

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

Type * getType() const

Return the LLVM type of this SCEV expression.

NoWrapFlags

NoWrapFlags are bitfield indices into SubclassData.

The main scalar evolution driver.

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

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

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

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

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

Get an add recurrence expression for the specified loop.

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

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

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

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

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

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

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

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.

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.

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

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

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

void push_back(const T &Elt)

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

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

Value * getValPtr() const

LLVM Value Representation.

Type * getType() const

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

#define llvm_unreachable(msg)

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

This is an optimization pass for GlobalISel generic memory operations.

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

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

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

bool isPointerTy(const Type *T)

auto find_if(R &&Range, UnaryPredicate P)

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

bool SCEVExprContains(const SCEV *Root, PredTy Pred)

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

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

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

RetVal visit(const SCEV *S)

RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S)