LoopBoundSplit.cpp Source File (original) (raw)

22#define DEBUG_TYPE "loop-bound-split"

24using namespace llvm;

27namespace {

28struct ConditionInfo {

36 Value *AddRecValue = nullptr;

38 Value *NonPHIAddRecValue;

40 Value *BoundValue = nullptr;

44 const SCEV *BoundSCEV = nullptr;

46 ConditionInfo() = default;

47};

48}

51 ConditionInfo &Cond, const Loop &L) {

52 Cond.ICmp = ICmp;

60 if (!LHSAddRecSCEV && RHSAddRecSCEV) {

64 }

67 Cond.BoundSCEV = BoundSCEV;

68 Cond.NonPHIAddRecValue = Cond.AddRecValue;

75 }

76 }

77}

80 ConditionInfo &Cond, bool IsExitCond) {

81 if (IsExitCond) {

84 return false;

86 Cond.BoundSCEV = ExitCount;

87 return true;

88 }

92 return true;

98 return false;

102 unsigned BitWidth = BoundSCEVIntType->getBitWidth();

107

111 const SCEV *BoundPlusOneSCEV =

113 Cond.BoundSCEV = BoundPlusOneSCEV;

114 Cond.Pred = Pred;

115 return true;

116 }

117 }

118

119

120

121 return false;

122}

123

126 bool IsExitCond) {

128

129

131 return false;

132

133

134 if ( Cond .AddRecSCEV)

135 return false;

136

137 if ( Cond .AddRecSCEV->isAffine())

138 return false;

139

140 const SCEV *StepRecSCEV = Cond.AddRecSCEV->getStepRecurrence(SE);

141

143 return false;

144

146

147

149 return false;

150

151

153 return false;

154

155 return true;

156}

157

165 return false;

166

168 return false;

169 assert(SE.isSCEVable(RHS->getType()) && "Expected RHS's type is SCEVable");

170

171 if (TrueSucc == FalseSucc)

172 return false;

173

174 return true;

175}

176

179

180 if (L.getHeader()->getParent()->hasOptSize())

181 return false;

182

183

184 if (!L.isInnermost())

185 return false;

186

187

188 if (!L.isLoopSimplifyForm())

189 return false;

190

191

192 if (!L.isLCSSAForm(DT))

193 return false;

194

195

196 if (!L.isSafeToClone())

197 return false;

198

199 BasicBlock *ExitingBB = L.getExitingBlock();

200

201 if (!ExitingBB)

202 return false;

203

205 if (!ExitingBI)

206 return false;

207

208

210 return false;

211

212

215 return false;

216

217 Cond.BI = ExitingBI;

218 return true;

219}

220

222

223

224

225

226

227

230

233 if (!Succ0Succ || !Succ1Succ || Succ0Succ != Succ1Succ)

234 return false;

235

236

237

238 return true;

239}

240

242 ConditionInfo &ExitingCond,

243 ConditionInfo &SplitCandidateCond) {

244 for (auto *BB : L.blocks()) {

245

246 if (L.getLoopLatch() == BB)

247 continue;

248

250 if (!BI)

251 continue;

252

253

255 continue;

256

257

258 if (L.isLoopInvariant(BI->getCondition()))

259 continue;

260

261

264 false))

265 continue;

266

267 if (ExitingCond.BoundSCEV->getType() !=

268 SplitCandidateCond.BoundSCEV->getType())

269 continue;

270

271

272

273

275 SplitCandidateCond.AddRecSCEV->getStart(),

276 SplitCandidateCond.BoundSCEV))

277 continue;

278

279 SplitCandidateCond.BI = BI;

280 return BI;

281 }

282

283 return nullptr;

284}

285

288 ConditionInfo SplitCandidateCond;

289 ConditionInfo ExitingCond;

290

291

293 return false;

294

296 return false;

297

299 return false;

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

348 Loop *PostLoop;

350 BasicBlock *PreHeader = L.getLoopPreheader();

353 ".split", &LI, &DT, PostLoopBlocks);

355

358

359

360 bool isExitingLatch = L.getExitingBlock() == L.getLoopLatch();

361 Value *ExitingCondLCSSAPhi = nullptr;

362 for (PHINode &PN : L.getHeader()->phis()) {

363

365 Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");

367

368

370 isExitingLatch ? PN.getIncomingValueForBlock(L.getLoopLatch()) : &PN,

371 L.getExitingBlock());

372

373

376

377

378

379

381 continue;

382

384 if (PhiSCEV && ExitingCond.NonPHIAddRecValue ==

385 PN.getIncomingValueForBlock(L.getLoopLatch()))

386 ExitingCondLCSSAPhi = LCSSAPhi;

387 }

388

389

393 Builder.CreateICmp(Pred, ExitingCondLCSSAPhi, ExitingCond.BoundValue);

396

397

398 const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;

399 const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;

401 ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV)

402 : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV);

403

405 SE, L.getHeader()->getDataLayout(), "split");

407 Value *NewBoundValue =

409 NewBoundValue->setName("new.bound");

410

411

412 ExitingCond.ICmp->setOperand(1, NewBoundValue);

413

414

417

418

422

423

424 if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))

425 ExitingCond.BI->setSuccessor(0, PostLoopPreHeader);

426 else

427 ExitingCond.BI->setSuccessor(1, PostLoopPreHeader);

428

429

430 Builder.SetInsertPoint(PostLoopPreHeader, PostLoopPreHeader->begin());

432 for (auto i : seq(0, PN.getNumOperands())) {

433

434 if (PN.getIncomingBlock(i) == L.getExitingBlock()) {

435 Value *IncomingValue = PN.getIncomingValue(i);

436

437

439 Builder.CreatePHI(PN.getType(), 1, PN.getName() + ".lcssa");

441 LCSSAPhi->addIncoming(IncomingValue, PN.getIncomingBlock(i));

442

443

444 PN.setIncomingBlock(i, PostLoopPreHeader);

445

446 PN.setIncomingValue(i, LCSSAPhi);

447

448 PN.addIncoming(VMap[IncomingValue], PostLoop->getExitingBlock());

449 }

450 }

451 }

452

453

456

457

459

460

461 simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true);

462 simplifyLoop(PostLoop, &DT, &LI, &SE, nullptr, nullptr, true);

463

464

465 U.addSiblingLoops(PostLoop);

466

467 return true;

468}

469

473 [[maybe_unused]] Function &F = *L.getHeader()->getParent();

474

475 LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L

476 << "\n");

477

480

481 assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));

483

485}

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

This header provides classes for managing per-loop analyses.

static BranchInst * findSplitCandidate(const Loop &L, ScalarEvolution &SE, ConditionInfo &ExitingCond, ConditionInfo &SplitCandidateCond)

Definition LoopBoundSplit.cpp:241

static bool canSplitLoopBound(const Loop &L, const DominatorTree &DT, ScalarEvolution &SE, ConditionInfo &Cond)

Definition LoopBoundSplit.cpp:177

static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, const Loop &L)

Definition LoopBoundSplit.cpp:50

static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, LPMUpdater &U)

Definition LoopBoundSplit.cpp:286

static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE, ICmpInst *ICmp, ConditionInfo &Cond, bool IsExitCond)

Definition LoopBoundSplit.cpp:124

static bool isProcessableCondBI(const ScalarEvolution &SE, const BranchInst *BI)

Definition LoopBoundSplit.cpp:158

static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE, ConditionInfo &Cond, bool IsExitCond)

Definition LoopBoundSplit.cpp:79

static bool isProfitableToTransform(const Loop &L, const BranchInst *BI)

Definition LoopBoundSplit.cpp:221

This header provides classes for managing a pipeline of passes over loops in LLVM IR.

const SmallVectorImpl< MachineOperand > & Cond

Provides some synthesis utilities to produce sequences of values.

Class for arbitrary precision integers.

static APInt getMaxValue(unsigned numBits)

Gets maximum unsigned value of APInt for specific bit width.

static APInt getSignedMaxValue(unsigned numBits)

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

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

const Instruction & front() const

LLVM_ABI const BasicBlock * getSingleSuccessor() const

Return the successor of this block if it has a single successor.

LLVM_ABI LLVMContext & getContext() const

Get the context in which this basic block lives.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Conditional or Unconditional Branch instruction.

void setCondition(Value *V)

BasicBlock * getSuccessor(unsigned i) const

void setSuccessor(unsigned idx, BasicBlock *NewSucc)

Value * getCondition() const

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ ICMP_SLT

signed less than

@ ICMP_SLE

signed less or equal

@ ICMP_ULT

unsigned less than

@ ICMP_ULE

unsigned less or equal

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...

This is the shared class of boolean and integer constants.

static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

bool isZero() const

This is just a convenience method to make client code smaller for a common code.

static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)

const APInt & getValue() const

Return the constant as an APInt value reference.

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)

changeImmediateDominator - This method is used to update the dominator tree information when a node's...

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

This instruction compares its operands according to the predicate given to the constructor.

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

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

Class to represent integer types.

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

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

BlockT * getHeader() const

BlockT * getExitBlock() const

If getExitBlocks would return exactly one block, return that block.

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

BlockT * getExitingBlock() const

If getExitingBlocks would return exactly one block, return that block.

PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Definition LoopBoundSplit.cpp:470

void verify(const DominatorTreeBase< BlockT, false > &DomTree) const

Represents a single loop in the control flow graph.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

void setIncomingValueForBlock(const BasicBlock *BB, Value *V)

Set every incoming value(s) for block BB to V.

Value * getIncomingValueForBlock(const BasicBlock *BB) const

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

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

const SCEV * getStart() const

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

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

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

This class represents an analyzed expression in the program.

LLVM_ABI Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test whether entry to the loop is protected by a conditional between LHS and RHS.

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

LLVM_ABI const SCEV * getConstant(ConstantInt *V)

LLVM_ABI const SCEV * getSCEV(Value *V)

Return a SCEV expression for the full generality of the specified expression.

const SCEV * getOne(Type *Ty)

Return a SCEV for the constant 1 of a specific type.

LLVM_ABI void forgetLoop(const Loop *L)

This method should be called by the client when it has changed a loop in a way that may effect Scalar...

LLVM_ABI bool isSCEVable(Type *Ty) const

Test if values of the given type are analyzable within the SCEV framework.

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

LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)

Determine if the SCEV can be evaluated at loop's entry.

LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)

Return the number of times the backedge executes before the given exit would be taken; if not exactly...

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

LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)

Test if the given expression is known to satisfy the condition described by Pred, LHS,...

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

void setOperand(unsigned i, Value *Val)

LLVM Value Representation.

LLVM_ABI void setName(const Twine &Name)

Change the name of the value.

bool match(Val *V, const Pattern &P)

brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)

class_match< BasicBlock > m_BasicBlock()

Match an arbitrary basic block value and ignore it.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

Simplify each loop in a loop nest recursively.

decltype(auto) dyn_cast(const From &Val)

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

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

LLVM_ABI Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)

Clones a loop OrigLoop.

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ABI void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)

Remaps instructions in Blocks using the mapping in VMap.

constexpr unsigned BitWidth

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

decltype(auto) cast(const From &Val)

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

LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()

Returns the minimum set of Analyses that all loop passes must preserve.

auto seq(T Begin, T End)

Iterate over an integral type from Begin up to - but not including - End.

LLVM_ABI BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")

Split the edge connecting the specified blocks, and return the newly created basic block between From...

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...