LoopVersioningLICM.cpp Source File (original) (raw)

86#include

88using namespace llvm;

90#define DEBUG_TYPE "loop-versioning-licm"

98 cl::desc("LoopVersioningLICM's minimum allowed percentage "

99 "of possible invariant instructions per loop"),

101

102

104 "licm-versioning-max-depth-threshold",

106 "LoopVersioningLICM's threshold for maximum allowed loop nest/depth"),

108

109namespace {

110

111struct LoopVersioningLICM {

112

113

114

115

119 Loop *CurLoop)

120 : AA(AA), SE(SE), LAIs(LAIs), LI(LI), CurLoop(CurLoop),

123

124 bool run(DominatorTree *DT);

125

126private:

127

129

130

131 ScalarEvolution *SE;

132

133

134 const LoopAccessInfo *LAI = nullptr;

135

136

137 LoopAccessInfoManager &LAIs;

138

139 LoopInfo &LI;

140

141

142 Loop *CurLoop;

143

144

145 unsigned LoopDepthThreshold;

146

147

148 float InvariantThreshold;

149

150

151 unsigned LoadAndStoreCounter = 0;

152

153

154 unsigned InvariantCounter = 0;

155

156

157 bool IsReadOnlyLoop = true;

158

159

160 OptimizationRemarkEmitter *ORE;

161

162 bool isLegalForVersioning();

163 bool legalLoopStructure();

164 bool legalLoopInstructions();

165 bool legalLoopMemoryAccesses();

166 bool isLoopAlreadyVisited();

167 bool instructionSafeForVersioning(Instruction *I);

168};

169

170}

171

172

173bool LoopVersioningLICM::legalLoopStructure() {

174

176 LLVM_DEBUG(dbgs() << " loop is not in loop-simplify form.\n");

177 return false;

178 }

179

182 return false;

183 }

184

186 LLVM_DEBUG(dbgs() << " loop has multiple backedges\n");

187 return false;

188 }

189

191 LLVM_DEBUG(dbgs() << " loop has multiple exiting block\n");

192 return false;

193 }

194

195

196

198 LLVM_DEBUG(dbgs() << " loop is not bottom tested\n");

199 return false;

200 }

201

202

204 LLVM_DEBUG(dbgs() << " Parallel loop is not worth versioning\n");

205 return false;

206 }

207

208 if (CurLoop->getLoopDepth() > LoopDepthThreshold) {

209 LLVM_DEBUG(dbgs() << " loop depth is more than threshold\n");

210 return false;

211 }

212

213

216 LLVM_DEBUG(dbgs() << " loop does not have trip count\n");

217 return false;

218 }

219 return true;

220}

221

222

223

224bool LoopVersioningLICM::legalLoopMemoryAccesses() {

225

226 BatchAAResults BAA(*AA);

227 AliasSetTracker AST(BAA);

229

232 }

233

234

235

236

237

238

239

240

241

242

243

244

245

246 bool HasMayAlias = false;

247 bool TypeSafety = false;

248 bool HasMod = false;

249 for (const auto &I : AST) {

250 const AliasSet &AS = I;

251

252

254 continue;

255

257 return false;

258 const Value *SomePtr = AS.begin()->Ptr;

259 bool TypeCheck = true;

260

262 HasMod |= AS.isMod();

263 for (const auto &MemLoc : AS) {

264 const Value *Ptr = MemLoc.Ptr;

265

266

267

268

269

270

271 TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));

272 }

273

274 TypeSafety |= TypeCheck;

275 }

276

277 if (!TypeSafety) {

278 LLVM_DEBUG(dbgs() << " Alias tracker type safety failed!\n");

279 return false;

280 }

281

282 if (!HasMod) {

283 LLVM_DEBUG(dbgs() << " No memory modified in loop body\n");

284 return false;

285 }

286

287

288 if (!HasMayAlias) {

289 LLVM_DEBUG(dbgs() << " No ambiguity in memory access.\n");

290 return false;

291 }

292 return true;

293}

294

295

296

297

298

299

300

301

302bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {

303 assert(I != nullptr && "Null instruction found!");

304

307 LLVM_DEBUG(dbgs() << " Convergent call site found.\n");

308 return false;

309 }

310

313 return false;

314 }

315 }

316

317

318 if (I->mayThrow()) {

319 LLVM_DEBUG(dbgs() << " May throw instruction found in loop body\n");

320 return false;

321 }

322

323

324 if (I->mayReadFromMemory()) {

326 if (!Ld || !Ld->isSimple()) {

328 return false;

329 }

330 LoadAndStoreCounter++;

332

334 InvariantCounter++;

335 }

336

337

338 else if (I->mayWriteToMemory()) {

340 if (!St || !St->isSimple()) {

341 LLVM_DEBUG(dbgs() << " Found a non-simple store.\n");

342 return false;

343 }

344 LoadAndStoreCounter++;

346

347

349 if ( $any\_of$ (Pointers, [&](auto &P) { return P.PointerValue == Ptr; })) {

350 LLVM_DEBUG(dbgs() << " Found a store without a runtime check.\n");

351 return false;

352 }

353

355 InvariantCounter++;

356

357 IsReadOnlyLoop = false;

358 }

359 return true;

360}

361

362

363

364bool LoopVersioningLICM::legalLoopInstructions() {

365

366 LoadAndStoreCounter = 0;

367 InvariantCounter = 0;

368 IsReadOnlyLoop = true;

369 using namespace ore;

370

371 LAI = &LAIs.getInfo(*CurLoop, true);

372

374 LLVM_DEBUG(dbgs() << " LAA: Runtime check not found !!\n");

375 return false;

376 }

377

378

380 for (auto &Inst : *Block) {

381

382 if (!instructionSafeForVersioning(&Inst)) {

383 ORE->emit([&]() {

384 return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)

385 << " Unsafe Loop Instruction";

386 });

387 return false;

388 }

389 }

390

394 dbgs() << " LAA: Runtime checks are more than threshold !!\n");

395 ORE->emit([&]() {

396 return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",

399 << "Number of runtime checks "

401 << " exceeds threshold "

403 });

404 return false;

405 }

406

407 if (!InvariantCounter) {

409 return false;

410 }

411

412 if (IsReadOnlyLoop) {

414 return false;

415 }

416

417

418 if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {

421 << " Invariant load & store are less then defined threshold\n");

423 << ((InvariantCounter * 100) / LoadAndStoreCounter)

424 << "%\n");

425 LLVM_DEBUG(dbgs() << " Invariant loads & store threshold: "

426 << InvariantThreshold << "%\n");

427 ORE->emit([&]() {

428 return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",

431 << "Invariant load & store "

432 << NV("LoadAndStoreCounter",

433 ((InvariantCounter * 100) / LoadAndStoreCounter))

434 << " are less then defined threshold "

435 << NV("Threshold", InvariantThreshold);

436 });

437 return false;

438 }

439 return true;

440}

441

442

443

444

445bool LoopVersioningLICM::isLoopAlreadyVisited() {

446

448 return true;

449 }

450 return false;

451}

452

453

454

455

456

457bool LoopVersioningLICM::isLegalForVersioning() {

458 using namespace ore;

460

461 if (isLoopAlreadyVisited()) {

463 dbgs() << " Revisiting loop in LoopVersioningLICM not allowed.\n\n");

464 return false;

465 }

466

467 if (!legalLoopStructure()) {

469 dbgs() << " Loop structure not suitable for LoopVersioningLICM\n\n");

470 ORE->emit([&]() {

471 return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",

474 << " Unsafe Loop structure";

475 });

476 return false;

477 }

478

479 if (!legalLoopInstructions()) {

482 << " Loop instructions not suitable for LoopVersioningLICM\n\n");

483 return false;

484 }

485

486 if (!legalLoopMemoryAccesses()) {

489 << " Loop memory access not suitable for LoopVersioningLICM\n\n");

490 ORE->emit([&]() {

491 return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",

494 << " Unsafe Loop memory access";

495 });

496 return false;

497 }

498

499 LLVM_DEBUG(dbgs() << " Loop Versioning found to be beneficial\n\n");

500 ORE->emit([&]() {

501 return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",

503 << " Versioned loop for LICM."

504 << " Number of runtime checks we had to insert "

506 });

507 return true;

508}

509

510bool LoopVersioningLICM::run(DominatorTree *DT) {

511

513 return false;

514

516

517

518

519

520 if (isLegalForVersioning()) {

521

522

523

525 CurLoop, &LI, DT, SE);

526 LVer.versionLoop();

527

529

531

532

533

535 "llvm.mem.parallel_loop_access");

536

537 LVer.annotateLoopWithNoAlias();

539 }

541}

542

549 const Function *F = L.getHeader()->getParent();

551

553 if (!LoopVersioningLICM(AA, SE, &ORE, LAIs, LAR.LI, &L).run(DT))

556}

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

This is the interface for a simple mod/ref and alias analysis over globals.

static const char * LICMVersioningMetaData

Definition LoopVersioningLICM.cpp:92

static cl::opt< unsigned > LVLoopDepthThreshold("licm-versioning-max-depth-threshold", cl::desc("LoopVersioningLICM's threshold for maximum allowed loop nest/depth"), cl::init(2), cl::Hidden)

Threshold for maximum allowed loop nest/depth.

static cl::opt< float > LVInvarThreshold("licm-versioning-invariant-threshold", cl::desc("LoopVersioningLICM's minimum allowed percentage " "of possible invariant instructions per loop"), cl::init(25), cl::Hidden)

Threshold minimum allowed percentage for possible invariant instructions in a loop.

This file defines the SmallVector class.

bool doesNotAccessMemory(const CallBase *Call)

Checks if the specified call is known to never read or write memory.

bool isForwardingAliasSet() const

Return true if this alias set should be ignored as part of the AliasSetTracker object.

bool cannotDuplicate() const

Determine if the invoke cannot be duplicated.

bool isConvergent() const

Determine if the invoke is convergent.

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

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

Value * getPointerOperand()

LLVM_ABI const LoopAccessInfo & getInfo(Loop &L, bool AllowPartial=false)

const RuntimePointerChecking * getRuntimePointerChecking() const

unsigned getNumRuntimePointerChecks() const

Number of memchecks required to prove independence of otherwise may-alias pointers.

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

unsigned getNumBackEdges() const

Calculate the number of back edges to the loop header.

const std::vector< LoopT * > & getSubLoops() const

Return the loops contained entirely within this loop.

BlockT * getHeader() const

unsigned getLoopDepth() const

Return the nesting level of this loop.

ArrayRef< BlockT * > getBlocks() const

Get a list of the basic blocks which make up this loop.

BlockT * getExitingBlock() const

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

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

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

Definition LoopVersioningLICM.cpp:543

Represents a single loop in the control flow graph.

bool isAnnotatedParallel() const

Returns true if the loop is annotated parallel.

DebugLoc getStartLoc() const

Return the debug location of the start of this loop.

bool isLoopSimplifyForm() const

Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...

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.

SmallVector< PointerInfo, 2 > Pointers

Information about the pointers that may require checking.

const SmallVectorImpl< RuntimePointerCheck > & getChecks() const

Returns the checks that generateChecks created.

The main scalar evolution driver.

LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)

If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...

LLVM_ABI const SCEV * getSCEV(Value *V)

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

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

Return true if the value of the given SCEV is unchanging in the specified loop.

Value * getPointerOperand()

Type * getType() const

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

Abstract Attribute helper functions.

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

DiagnosticInfoOptimizationBase::Argument NV

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 std::optional< const MDOperand * > findStringMetadataForLoop(const Loop *TheLoop, StringRef Name)

Find string metadata for loop.

LLVM_ABI void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)

Set input string into loop metadata by keeping other values intact.

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

bool any_of(R &&range, UnaryPredicate P)

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

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 TransformationMode hasLICMVersioningTransformation(const Loop *L)

@ TM_Disable

The transformation should not be applied.

LLVM_ABI PreservedAnalyses getLoopPassPreservedAnalyses()

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

AAResults AliasAnalysis

Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.

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

static LLVM_ABI unsigned RuntimeMemoryCheckThreshold

\When performing memory disambiguation checks at runtime do not make more than this number of compari...