ScalarEvolutionExpander.h Source File (original) (raw)

13#ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H

14#define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H

28namespace llvm {

42};

55};

70 const char *IVName;

73 bool PreserveLCSSA;

77 InsertedExpressions;

100

101

103

104

105

106 const Loop *IVIncInsertLoop;

107

108

109

111

112

114

115

116

117

118

119

120

121

122 bool CanonicalMode;

123

124

125

126

127 bool LSRMode;

128

129

130

131

132 bool SafeUDivMode = false;

133

136

137

138

139

140

141

142 class SCEVInsertPointGuard {

148

149 SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;

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

151

152 public:

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

156 SE->InsertPointGuards.push_back(this);

157 }

158

159 ~SCEVInsertPointGuard() {

160

161

162

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

164 SE->InsertPointGuards.pop_back();

167 }

168

171 };

172

173

174

176

177#if LLVM_ENABLE_ABI_BREAKING_CHECKS

178 const char *DebugType;

179#endif

180

182

183public:

184

186 const char *name, bool PreserveLCSSA = true)

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

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

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

193#if LLVM_ENABLE_ABI_BREAKING_CHECKS

194 DebugType = "";

195#endif

196 }

197

199

201 }

202

203#if LLVM_ENABLE_ABI_BREAKING_CHECKS

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

205#endif

206

207

208

209

211 InsertedExpressions.clear();

212 InsertedValues.clear();

213 InsertedPostIncValues.clear();

214 ReusedValues.clear();

215 OrigFlags.clear();

216 ChainedPhis.clear();

217 InsertedIVs.clear();

218 }

219

222

223

226 for (const auto &VH : InsertedValues) {

228 if (ReusedValues.contains(V))

229 continue;

230 if (auto *Inst = dyn_cast(V))

231 Result.push_back(Inst);

232 }

233 for (const auto &VH : InsertedPostIncValues) {

235 if (ReusedValues.contains(V))

236 continue;

237 if (auto *Inst = dyn_cast(V))

238 Result.push_back(Inst);

239 }

240

241 return Result;

242 }

243

244

245

246

247

248

249

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

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

255 if ( TTI )

256 return true;

261 for (auto *Expr : Exprs)

263 while (!Worklist.empty()) {

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

266 Processed, Worklist))

267 return true;

268 }

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

270 return false;

271 }

272

273

275 bool allowScale);

276

277

278

279

280

281

282

284 bool RecomputePoisonFlags = false);

285

286

287

288

289

293

294

295

299

300

301

302

304

305

306

307

309

310

311

315 }

316

317

318

319

320

322

323

324

325

327

328

329

332

333

336

337

338

340

341

342

344

345

347 assert(!CanonicalMode &&

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

349 IVIncInsertLoop = L;

350 IVIncInsertPos = Pos;

351 }

352

353

354

356 assert(!CanonicalMode &&

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

358 PostIncLoops = L;

359 }

360

361

363 PostIncLoops.clear();

364

365

366

367 InsertedPostIncValues.clear();

368 }

369

370

371

372

374

376

377

378

379

380

384 }

385

388 }

389

390

391

393

394

397 }

398

399

402 }

403

404

405

406

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

409 }

410

412

413

414

415

416

417

418

419

422

423

424

427

428private:

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

430

431

432 bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,

433 const Instruction &At, InstructionCost &Cost,

434 unsigned Budget,

435 const TargetTransformInfo &TTI,

436 SmallPtrSetImpl<const SCEV *> &Processed,

437 SmallVectorImpl &Worklist);

438

439

440

441

444

445

447

448

449

450

453

454

455

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

457

458

459

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

461

462

463

464

465 Value *FindValueInExprValueMap(

466 const SCEV *S, const Instruction *InsertPt,

467 SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts);

468

469 Value *expand(const SCEV *S);

473 }

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

477 }

478

479

480 const Loop *getRelevantLoop(const SCEV *);

481

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

483 Twine Name, bool IsSequential = false);

484

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

486

487 Value *visitVScale(const SCEVVScale *S);

488

489 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);

490

491 Value *visitTruncateExpr(const SCEVTruncateExpr *S);

492

493 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);

494

495 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);

496

497 Value *visitAddExpr(const SCEVAddExpr *S);

498

499 Value *visitMulExpr(const SCEVMulExpr *S);

500

501 Value *visitUDivExpr(const SCEVUDivExpr *S);

502

503 Value *visitAddRecExpr(const SCEVAddRecExpr *S);

504

505 Value *visitSMaxExpr(const SCEVSMaxExpr *S);

506

507 Value *visitUMaxExpr(const SCEVUMaxExpr *S);

508

509 Value *visitSMinExpr(const SCEVSMinExpr *S);

510

511 Value *visitUMinExpr(const SCEVUMinExpr *S);

512

513 Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);

514

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

516

517 void rememberInstruction(Value *I);

518

519 void rememberFlags(Instruction *I);

520

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

522

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

524

525 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);

526 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,

527 const Loop *L, Type *&TruncTy,

528 bool &InvertStep);

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

530 bool useSubtract);

531

532 void fixupInsertPoints(Instruction *I);

533

534

535

536 Value *fixupLCSSAFormFor(Value *V);

537

538

539

540

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

542 const DominatorTree *DT,

543 SmallVectorImpl &DeadInsts);

544};

545

546

547

550

551

552

553 bool ResultUsed;

554

555public:

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

558

560

561

563

565};

566}

567

568#endif

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

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

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

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.

void SetCurrentDebugLocation(DebugLoc L)

Set location information used by debugging information.

DebugLoc getCurrentDebugLocation() const

Get location information used by debugging information.

void ClearInsertionPoint()

Clear the insertion point: created instructions will not be inserted into a block.

void restoreIP(InsertPoint IP)

Sets the current insert point to a previously-saved location.

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

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

Helper to remove instructions inserted during SCEV expansion, unless they are marked as used.

SCEVExpanderCleaner(SCEVExpander &Expander)

void markResultUsed()

Indicate that the result of the expansion is used.

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

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

Generates code that evaluates if the AR expression will overflow.

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.

void setChainedPhi(PHINode *PN)

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 setInsertPoint(BasicBlock::iterator IP)

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.

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()

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.

void clearPostInc()

Disable all post-inc expansion.

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

Construct a SCEVExpander in "canonical" mode.

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

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

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

bool isInsertedInstruction(Instruction *I) const

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

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.

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

void SetCurrentDebugLocation(DebugLoc L)

Set location information used by debugging information.

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.

const SmallVectorImpl< WeakVH > & getInsertedIVs() const

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.

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)

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

Return the induction variable increment's IV operand.

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.

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.

bool contains(ConstPtrType Ptr) const

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)

void push_back(const T &Elt)

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.

std::pair< iterator, bool > insert(const ValueT &V)

size_type count(const_arg_type_t< ValueT > V) const

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

This is an optimization pass for GlobalISel generic memory operations.

cl::opt< unsigned > SCEVCheapExpansionBudget

DWARFExpression::Operation Op

void apply(Instruction *I)

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

const SCEV * S

The SCEV operand to be costed.

unsigned ParentOpcode

LLVM instruction opcode that uses the operand.

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

int OperandIdx

The use index of an expanded instruction.

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