LoopBoundSplit.cpp Source File (original) (raw)

22#define DEBUG_TYPE "loop-bound-split"

24namespace llvm {

26using namespace PatternMatch;

28namespace {

29struct ConditionInfo {

31 BranchInst *BI = nullptr;

33 ICmpInst *ICmp = nullptr;

37 Value *AddRecValue = nullptr;

39 Value *NonPHIAddRecValue;

41 Value *BoundValue = nullptr;

43 const SCEVAddRecExpr *AddRecSCEV = nullptr;

45 const SCEV *BoundSCEV = nullptr;

47 ConditionInfo() = default;

48};

49}

52 ConditionInfo &Cond, const Loop &L) {

53 Cond.ICmp = ICmp;

58 const SCEVAddRecExpr *LHSAddRecSCEV = dyn_cast(AddRecSCEV);

59 const SCEVAddRecExpr *RHSAddRecSCEV = dyn_cast(BoundSCEV);

61 if (!LHSAddRecSCEV && RHSAddRecSCEV) {

65 }

67 Cond.AddRecSCEV = dyn_cast(AddRecSCEV);

68 Cond.BoundSCEV = BoundSCEV;

69 Cond.NonPHIAddRecValue = Cond.AddRecValue;

73 if (Cond.AddRecSCEV && isa(Cond.AddRecValue)) {

74 PHINode *PN = cast(Cond.AddRecValue);

76 }

77 }

78}

81 ConditionInfo &Cond, bool IsExitCond) {

82 if (IsExitCond) {

84 if (isa(ExitCount))

85 return false;

87 Cond.BoundSCEV = ExitCount;

88 return true;

89 }

93 return true;

99 return false;

100

102 dyn_cast(Cond.BoundSCEV->getType())) {

103 unsigned BitWidth = BoundSCEVIntType->getBitWidth();

108

112 const SCEV *BoundPlusOneSCEV =

114 Cond.BoundSCEV = BoundPlusOneSCEV;

115 Cond.Pred = Pred;

116 return true;

117 }

118 }

119

120

121

122 return false;

123}

124

127 bool IsExitCond) {

129

130

132 return false;

133

134

135 if ( Cond .AddRecSCEV)

136 return false;

137

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

139 return false;

140

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

142

143 if (!isa(StepRecSCEV))

144 return false;

145

147

148

150 return false;

151

152

154 return false;

155

156 return true;

157}

158

166 return false;

167

169 return false;

171

172 if (TrueSucc == FalseSucc)

173 return false;

174

175 return true;

176}

177

180

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

182 return false;

183

184

185 if (!L.isInnermost())

186 return false;

187

188

189 if (!L.isLoopSimplifyForm())

190 return false;

191

192

193 if (!L.isLCSSAForm(DT))

194 return false;

195

196

197 if (!L.isSafeToClone())

198 return false;

199

200 BasicBlock *ExitingBB = L.getExitingBlock();

201

202 if (!ExitingBB)

203 return false;

204

206 if (!ExitingBI)

207 return false;

208

209

211 return false;

212

213

216 return false;

217

218 Cond.BI = ExitingBI;

219 return true;

220}

221

223

224

225

226

227

228

231

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

235 return false;

236

237

238

239 return true;

240}

241

243 ConditionInfo &ExitingCond,

244 ConditionInfo &SplitCandidateCond) {

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

246

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

248 continue;

249

250 auto *BI = dyn_cast(BB->getTerminator());

251 if (!BI)

252 continue;

253

254

256 continue;

257

258

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

260 continue;

261

262

263 ICmpInst *ICmp = cast(BI->getCondition());

265 false))

266 continue;

267

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

269 SplitCandidateCond.BoundSCEV->getType())

270 continue;

271

272

273

274

276 SplitCandidateCond.AddRecSCEV->getStart(),

277 SplitCandidateCond.BoundSCEV))

278 continue;

279

280 SplitCandidateCond.BI = BI;

281 return BI;

282 }

283

284 return nullptr;

285}

286

289 ConditionInfo SplitCandidateCond;

290 ConditionInfo ExitingCond;

291

292

294 return false;

295

297 return false;

298

300 return false;

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

347

349 Loop *PostLoop;

351 BasicBlock *PreHeader = L.getLoopPreheader();

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

356

359

360

361 bool isExitingLatch =

362 (L.getExitingBlock() == L.getLoopLatch()) ? true : false;

363 Value *ExitingCondLCSSAPhi = nullptr;

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

365

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

369

370

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

373 L.getExitingBlock());

374

375

376 PHINode *PostLoopPN = cast(VMap[&PN]);

378

379

380

381

383 continue;

384

386 if (PhiSCEV && ExitingCond.NonPHIAddRecValue ==

387 PN.getIncomingValueForBlock(L.getLoopLatch()))

388 ExitingCondLCSSAPhi = LCSSAPhi;

389 }

390

391

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

398

399

400 const SCEV *NewBoundSCEV = ExitingCond.BoundSCEV;

401 const SCEV *SplitBoundSCEV = SplitCandidateCond.BoundSCEV;

403 ? SE.getSMinExpr(NewBoundSCEV, SplitBoundSCEV)

404 : SE.getUMinExpr(NewBoundSCEV, SplitBoundSCEV);

405

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

409 Value *NewBoundValue =

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

412

413

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

415

416

419

420

422 cast(VMap[SplitCandidateCond.BI]);

424

425

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

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

428 else

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

430

431

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

435

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

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

438

439

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

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

444

445

446 PN.setIncomingBlock(i, PostLoopPreHeader);

447

448 PN.setIncomingValue(i, LCSSAPhi);

449

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

451 }

452 }

453 }

454

455

458

459

461

462

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

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

465

466

467 U.addSiblingLoops(PostLoop);

468

469 return true;

470}

471

475 Function &F = *L.getHeader()->getParent();

476 (void)F;

477

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

479 << "\n");

480

483

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

486

488}

489

490}

This header provides classes for managing per-loop analyses.

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

const SmallVectorImpl< MachineOperand > & Cond

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

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.

A container for analyses that lazily runs them and caches their results.

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

const BasicBlock * getSingleSuccessor() const

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

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

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.

This is the shared class of boolean and integer constants.

static ConstantInt * getTrue(LLVMContext &Context)

bool isZero() const

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

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

PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")

BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)

Create a conditional 'br Cond, TrueDest, FalseDest' instruction.

void SetInsertPoint(BasicBlock *TheBB)

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

Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")

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

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)

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.

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

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.

Type * getType() const

Return the LLVM type of this SCEV expression.

The main scalar evolution driver.

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.

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

const SCEV * getConstant(ConstantInt *V)

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.

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

bool isSCEVable(Type *Ty) const

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

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

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

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

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

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.

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.

LLVM Value Representation.

Type * getType() const

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

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.

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

Simplify each loop in a loop nest recursively.

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

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

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

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

Clones a loop OrigLoop.

raw_ostream & dbgs()

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

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

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

Remaps instructions in Blocks using the mapping in VMap.

constexpr unsigned BitWidth

PreservedAnalyses getLoopPassPreservedAnalyses()

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

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

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

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

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

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

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