ScalarEvolutionExpander.h Source File (original) (raw)

13#ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H

14#define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H

29namespace llvm {

71 const char *IVName;

74 bool PreserveLCSSA;

78 InsertedExpressions;

100

101

102

104

105

106

107 const Loop *IVIncInsertLoop;

108

109

110

112

113

115

116

117

118

119

120

121

122

123 bool CanonicalMode;

124

125

126

127

128 bool LSRMode;

129

130

131

132

133 bool SafeUDivMode = false;

134

136 BuilderType Builder;

137

138

139

140

141

142

143 class SCEVInsertPointGuard {

149

150 SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;

151 SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;

152

153 public:

155 : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),

157 SE->InsertPointGuards.push_back(this);

158 }

159

160 ~SCEVInsertPointGuard() {

161

162

163

164 assert(SE->InsertPointGuards.back() == this);

165 SE->InsertPointGuards.pop_back();

167 Builder.SetCurrentDebugLocation(DbgLoc);

168 }

169

172 };

173

174

175

177

178#if LLVM_ENABLE_ABI_BREAKING_CHECKS

179 const char *DebugType;

180#endif

181

183

184public:

185

187 const char *name, bool PreserveLCSSA = true)

188 : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),

189 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),

193 [this](Instruction *I) { rememberInstruction(I); })) {

194#if LLVM_ENABLE_ABI_BREAKING_CHECKS

195 DebugType = "";

196#endif

197 }

198

200

201 assert(InsertPointGuards.empty());

202 }

203

204#if LLVM_ENABLE_ABI_BREAKING_CHECKS

205 void setDebugType(const char *s) { DebugType = s; }

206#endif

207

208

209

210

212 InsertedExpressions.clear();

213 InsertedValues.clear();

214 InsertedPostIncValues.clear();

215 ReusedValues.clear();

216 OrigFlags.clear();

217 ChainedPhis.clear();

218 InsertedIVs.clear();

219 }

220

223

224

227 for (const auto &VH : InsertedValues) {

229 if (ReusedValues.contains(V))

230 continue;

232 Result.push_back(Inst);

233 }

234 for (const auto &VH : InsertedPostIncValues) {

236 if (ReusedValues.contains(V))

237 continue;

239 Result.push_back(Inst);

240 }

241

242 return Result;

243 }

244

245

246

247

248

249

250

254 assert(TTI && "This function requires TTI to be provided.");

255 assert(At && "This function requires At instruction to be provided.");

256 if ( TTI )

257 return true;

262 for (auto *Expr : Exprs)

264 while (!Worklist.empty()) {

266 if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI,

267 Processed, Worklist))

268 return true;

269 }

270 assert(Cost <= ScaledBudget && "Should have returned from inner loop.");

271 return false;

272 }

273

274

277

278

279

280

281

282

283

285 bool RecomputePoisonFlags = false);

286

287

288

289

290

295

296

297

302

303

304

305

307

308

309

310

313

314

315

321

322

323

324

325

327

328

329

330

333

334

335

338

339

342

343

344

347

348

349

352

353

355 assert(!CanonicalMode &&

356 "IV increment positions are not supported in CanonicalMode");

357 IVIncInsertLoop = L;

358 IVIncInsertPos = Pos;

359 }

360

361

362

364 assert(!CanonicalMode &&

365 "Post-inc expansion is not supported in CanonicalMode");

366 PostIncLoops = L;

367 }

368

369

371 PostIncLoops.clear();

372

373

374

375 InsertedPostIncValues.clear();

376 }

377

378

379

380

382

384

385

386

387

388

391 Builder.SetInsertPoint(IP);

392 }

393

395 Builder.SetInsertPoint(IP->getParent(), IP);

396 }

397

398

399

401

402

404 Builder.SetCurrentDebugLocation(std::move(L));

405 }

406

407

409 return Builder.getCurrentDebugLocation();

410 }

411

412

413

414

416 return InsertedValues.count(I) || InsertedPostIncValues.count(I);

417 }

418

420

421

422

423

424

425

426

427

430

431

432

435

436

437

439

440private:

441 LLVMContext &getContext() const { return SE.getContext(); }

442

443

445 isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,

447 unsigned Budget, const TargetTransformInfo &TTI,

448 SmallPtrSetImpl<const SCEV *> &Processed,

449 SmallVectorImpl &Worklist);

450

451

452

453

456

457

459

460

461

462

465

466

467

468 Value *InsertNoopCastOfTo(Value *V, Type *Ty);

469

470

471

472 Value *expandAddToGEP(const SCEV *Op, Value *V, SCEV::NoWrapFlags Flags);

473

474

475

476

477 Value *FindValueInExprValueMap(

478 const SCEV *S, const Instruction *InsertPt,

479 SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts);

480

485 }

486 Value *expand(const SCEV *S, Instruction *I) {

489 }

490

491

492 const Loop *getRelevantLoop(const SCEV *);

493

494 Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,

495 Twine Name, bool IsSequential = false);

496

497 Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }

498

499 Value *visitVScale(const SCEVVScale *S);

500

501 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);

502

503 Value *visitTruncateExpr(const SCEVTruncateExpr *S);

504

505 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);

506

507 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);

508

509 Value *visitAddExpr(const SCEVAddExpr *S);

510

511 Value *visitMulExpr(const SCEVMulExpr *S);

512

513 Value *visitUDivExpr(const SCEVUDivExpr *S);

514

515 Value *visitAddRecExpr(const SCEVAddRecExpr *S);

516

517 Value *visitSMaxExpr(const SCEVSMaxExpr *S);

518

519 Value *visitUMaxExpr(const SCEVUMaxExpr *S);

520

521 Value *visitSMinExpr(const SCEVSMinExpr *S);

522

523 Value *visitUMinExpr(const SCEVUMinExpr *S);

524

525 Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);

526

527 Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }

528

530

531 void rememberFlags(Instruction *I);

532

533 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);

534

535 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);

536

537 Value *tryToReuseLCSSAPhi(const SCEVAddRecExpr *S);

538 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);

539 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,

540 const Loop *L, Type *&TruncTy,

541 bool &InvertStep);

542 Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,

543 bool useSubtract);

544

545 void fixupInsertPoints(Instruction *I);

546

547

548

550

551

552

553

554 void replaceCongruentIVInc(PHINode *&Phi, PHINode *&OrigPhi, Loop *L,

555 const DominatorTree *DT,

556 SmallVectorImpl &DeadInsts);

557};

558

559

560

563

564

565

566 bool ResultUsed;

567

568public:

570 : Expander(Expander), ResultUsed(false) {}

571

573

574

576

578};

579}

580

581#endif

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

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

This file defines the DenseMap class.

This file defines the DenseSet and SmallDenseSet classes.

static Expected< BitVector > expand(StringRef S, StringRef Original)

This file defines an InstructionCost class that is used when calculating the cost of an instruction,...

This file defines the SmallVector class.

This pass exposes codegen information to IR-level passes.

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

Value handle that asserts if the Value is deleted.

InstListType::iterator iterator

Instruction iterators...

A parsed version of the target data layout string in and methods for querying it.

Implements a dense probed hash-table based set.

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

Represents flags for the getelementptr instruction/expression.

InsertPoint - A saved insertion point.

Common base class shared among various IRBuilders.

Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.

This is an important class for using LLVM in a threaded context.

Represents a single loop in the control flow graph.

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

This class represents an assumption that the expression LHS Pred RHS evaluates to true,...

SCEVExpanderCleaner(SCEVExpander &Expander)

Definition ScalarEvolutionExpander.h:569

~SCEVExpanderCleaner()

Definition ScalarEvolutionExpander.h:572

void markResultUsed()

Indicate that the result of the expansion is used.

Definition ScalarEvolutionExpander.h:575

This class uses information about analyze scalars to rewrite expressions in canonical form.

Definition ScalarEvolutionExpander.h:64

LLVM_ABI Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)

Generates code that evaluates if the AR expression will overflow.

LLVM_ABI bool hasRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)

Determine whether there is an existing expansion of S that can be reused.

SmallVector< Instruction *, 32 > getAllInsertedInstructions() const

Return a vector containing all instructions inserted during expansion.

Definition ScalarEvolutionExpander.h:225

friend class SCEVExpanderCleaner

Definition ScalarEvolutionExpander.h:65

void setChainedPhi(PHINode *PN)

Definition ScalarEvolutionExpander.h:419

LLVM_ABI bool isSafeToExpand(const SCEV *S) const

Return true if the given expression is safe to expand in the sense that all materialized values are s...

void enableLSRMode()

Definition ScalarEvolutionExpander.h:383

void setInsertPoint(BasicBlock::iterator IP)

Definition ScalarEvolutionExpander.h:394

bool isHighCostExpansion(ArrayRef< const SCEV * > Exprs, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)

Return true for expressions that can't be evaluated at runtime within given Budget.

Definition ScalarEvolutionExpander.h:251

LLVM_ABI bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const

Return true if the given expression is safe to expand in the sense that all materialized values are d...

ScalarEvolution * getSE()

Definition ScalarEvolutionExpander.h:221

LLVM_ABI unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)

replace congruent phis with their most canonical representative.

void clearInsertPoint()

Clear the current insertion point.

Definition ScalarEvolutionExpander.h:400

~SCEVExpander()

Definition ScalarEvolutionExpander.h:199

void clearPostInc()

Disable all post-inc expansion.

Definition ScalarEvolutionExpander.h:370

SCEVExpander(ScalarEvolution &se, const DataLayout &DL, const char *name, bool PreserveLCSSA=true)

Construct a SCEVExpander in "canonical" mode.

Definition ScalarEvolutionExpander.h:186

LLVM_ABI Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)

A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...

LLVM_ABI bool hoistIVInc(Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false)

Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos.

void clear()

Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...

Definition ScalarEvolutionExpander.h:211

bool isInsertedInstruction(Instruction *I) const

Return true if the specified instruction was inserted by the code rewriter.

Definition ScalarEvolutionExpander.h:415

LLVM_ABI Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)

Generates a code sequence that evaluates this predicate.

void setPostInc(const PostIncLoopSet &L)

Enable post-inc expansion for addrecs referring to the given loops.

Definition ScalarEvolutionExpander.h:363

static LLVM_ABI bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi, Instruction *OrigInc, Instruction *WideInc)

Return true if both increments directly increment the corresponding IV PHI nodes and have the same op...

DebugLoc getCurrentDebugLocation() const

Get location information used by debugging information.

Definition ScalarEvolutionExpander.h:408

void SetCurrentDebugLocation(DebugLoc L)

Set location information used by debugging information.

Definition ScalarEvolutionExpander.h:403

LLVM_ABI Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)

A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...

void setIVIncInsertPos(const Loop *L, Instruction *Pos)

Set the current IV increment loop and position.

Definition ScalarEvolutionExpander.h:354

const SmallVectorImpl< WeakVH > & getInsertedIVs() const

Definition ScalarEvolutionExpander.h:222

LLVM_ABI Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)

Insert code to directly compute the specified SCEV expression into the program.

void disableCanonicalMode()

Disable the behavior of expanding expressions in canonical form rather than in a more literal form.

Definition ScalarEvolutionExpander.h:381

LLVM_ABI Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)

A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...

Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)

Definition ScalarEvolutionExpander.h:318

LLVM_ABI Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)

Return the induction variable increment's IV operand.

void eraseDeadInstructions(Value *Root)

Remove inserted instructions that are dead, e.g.

LLVM_ABI BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const

Returns a suitable insert point after I, that dominates MustDominate.

void setInsertPoint(Instruction *IP)

Set the current insertion point.

Definition ScalarEvolutionExpander.h:389

This class represents an assumption made using SCEV expressions which can be checked at run-time.

This class represents a composition of other SCEV predicates, and is the class that most clients will...

This class represents an assumption made on an AddRec expression.

This class represents an analyzed expression in the program.

NoWrapFlags

NoWrapFlags are bitfield indices into SubclassData.

The main scalar evolution driver.

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

reference emplace_back(ArgTypes &&... Args)

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

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

@ TCC_Basic

The cost of a typical 'add' instruction.

Value handle that tracks a Value across RAUW.

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

LLVM Value Representation.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget

DWARFExpression::Operation Op

SmallPtrSet< const Loop *, 2 > PostIncLoopSet

unsigned NUW

Definition ScalarEvolutionExpander.h:46

unsigned Disjoint

Definition ScalarEvolutionExpander.h:49

unsigned NNeg

Definition ScalarEvolutionExpander.h:50

LLVM_ABI void apply(Instruction *I)

LLVM_ABI PoisonFlags(const Instruction *I)

GEPNoWrapFlags GEPNW

Definition ScalarEvolutionExpander.h:52

unsigned NSW

Definition ScalarEvolutionExpander.h:47

unsigned SameSign

Definition ScalarEvolutionExpander.h:51

unsigned Exact

Definition ScalarEvolutionExpander.h:48

struct for holding enough information to help calculate the cost of the given SCEV when expanded into...

Definition ScalarEvolutionExpander.h:34

const SCEV * S

The SCEV operand to be costed.

Definition ScalarEvolutionExpander.h:42

unsigned ParentOpcode

LLVM instruction opcode that uses the operand.

Definition ScalarEvolutionExpander.h:38

SCEVOperand(unsigned Opc, int Idx, const SCEV *S)

Definition ScalarEvolutionExpander.h:35

int OperandIdx

The use index of an expanded instruction.

Definition ScalarEvolutionExpander.h:40

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