1//===- LoopVersioningLICM.cpp - LICM Loop Versioning ----------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// When alias analysis is uncertain about the aliasing between any two accesses,
10// it will return MayAlias. This uncertainty from alias analysis restricts LICM
11// from proceeding further. In cases where alias analysis is uncertain we might
12// use loop versioning as an alternative.
13//
14// Loop Versioning will create a version of the loop with aggressive aliasing
15// assumptions in addition to the original with conservative (default) aliasing
16// assumptions. The version of the loop making aggressive aliasing assumptions
17// will have all the memory accesses marked as no-alias. These two versions of
18// loop will be preceded by a memory runtime check. This runtime check consists
19// of bound checks for all unique memory accessed in loop, and it ensures the
20// lack of memory aliasing. The result of the runtime check determines which of
21// the loop versions is executed: If the runtime check detects any memory
22// aliasing, then the original loop is executed. Otherwise, the version with
23// aggressive aliasing assumptions is used.
24//
25// Following are the top level steps:
26//
27// a) Perform LoopVersioningLICM's feasibility check.
28// b) If loop is a candidate for versioning then create a memory bound check,
29// by considering all the memory accesses in loop body.
30// c) Clone original loop and set all memory accesses as no-alias in new loop.
31// d) Set original loop & versioned loop as a branch target of the runtime check
32// result.
33//
34// It transforms loop as shown below:
35//
36// +----------------+
37// |Runtime Memcheck|
38// +----------------+
39// |
40// +----------+----------------+----------+
41// | |
42// +---------+----------+ +-----------+----------+
43// |Orig Loop Preheader | |Cloned Loop Preheader |
44// +--------------------+ +----------------------+
45// | |
46// +--------------------+ +----------------------+
47// |Orig Loop Body | |Cloned Loop Body |
48// +--------------------+ +----------------------+
49// | |
50// +--------------------+ +----------------------+
51// |Orig Loop Exit Block| |Cloned Loop Exit Block|
52// +--------------------+ +-----------+----------+
53// | |
54// +----------+--------------+-----------+
55// |
56// +-----+----+
57// |Join Block|
58// +----------+
59//
60//===----------------------------------------------------------------------===//
61
62#include "llvm/Transforms/Scalar/LoopVersioningLICM.h"
63#include "ScalarOptions.h"
64#include "llvm/ADT/SmallVector.h"
65#include "llvm/ADT/StringRef.h"
66#include "llvm/Analysis/AliasAnalysis.h"
67#include "llvm/Analysis/AliasSetTracker.h"
68#include "llvm/Analysis/GlobalsModRef.h"
69#include "llvm/Analysis/LoopAccessAnalysis.h"
70#include "llvm/Analysis/LoopInfo.h"
71#include "llvm/Analysis/LoopPass.h"
72#include "llvm/Analysis/OptimizationRemarkEmitter.h"
73#include "llvm/Analysis/ScalarEvolution.h"
74#include "llvm/IR/Dominators.h"
75#include "llvm/IR/Instruction.h"
76#include "llvm/IR/Instructions.h"
77#include "llvm/IR/LLVMContext.h"
78#include "llvm/IR/MDBuilder.h"
79#include "llvm/IR/Metadata.h"
80#include "llvm/IR/Value.h"
81#include "llvm/Support/Casting.h"
82#include "llvm/Support/Debug.h"
83#include "llvm/Support/raw_ostream.h"
84#include "llvm/Transforms/Utils/LoopUtils.h"
85#include "llvm/Transforms/Utils/LoopVersioning.h"
86#include <cassert>
87
88using namespace llvm;
89
90#define DEBUG_TYPE "loop-versioning-licm"
91
92static const char *LICMVersioningMetaData = "llvm.loop.licm_versioning.disable";
93
94namespace {
95
96struct LoopVersioningLICM {
97 // We don't explicitly pass in LoopAccessInfo to the constructor since the
98 // loop versioning might return early due to instructions that are not safe
99 // for versioning. By passing the proxy instead the construction of
100 // LoopAccessInfo will take place only when it's necessary.
101 LoopVersioningLICM(const ScalarOptions &Opts, AliasAnalysis *AA,
102 ScalarEvolution *SE, OptimizationRemarkEmitter *ORE,
103 LoopAccessInfoManager &LAIs, LoopInfo &LI, Loop *CurLoop)
104 : AA(AA), SE(SE), LAIs(LAIs), LI(LI), CurLoop(CurLoop),
105 LoopDepthThreshold(Opts.licm_versioning_max_depth_threshold),
106 InvariantThreshold(Opts.licm_versioning_invariant_threshold), ORE(ORE) {
107 }
108
109 bool run(DominatorTree *DT);
110
111private:
112 // Current AliasAnalysis information
113 AliasAnalysis *AA;
114
115 // Current ScalarEvolution
116 ScalarEvolution *SE;
117
118 // Current Loop's LoopAccessInfo
119 const LoopAccessInfo *LAI = nullptr;
120
121 // Proxy for retrieving LoopAccessInfo.
122 LoopAccessInfoManager &LAIs;
123
124 LoopInfo &LI;
125
126 // The current loop we are working on.
127 Loop *CurLoop;
128
129 // Maximum loop nest threshold
130 unsigned LoopDepthThreshold;
131
132 // Minimum invariant threshold
133 float InvariantThreshold;
134
135 // Counter to track num of load & store
136 unsigned LoadAndStoreCounter = 0;
137
138 // Counter to track num of invariant
139 unsigned InvariantCounter = 0;
140
141 // Read only loop marker.
142 bool IsReadOnlyLoop = true;
143
144 // OptimizationRemarkEmitter
145 OptimizationRemarkEmitter *ORE;
146
147 bool isLegalForVersioning();
148 bool legalLoopStructure();
149 bool legalLoopInstructions();
150 bool legalLoopMemoryAccesses();
151 bool isLoopAlreadyVisited();
152 bool instructionSafeForVersioning(Instruction *I);
153};
154
155} // end anonymous namespace
156
157/// Check loop structure and confirms it's good for LoopVersioningLICM.
158bool LoopVersioningLICM::legalLoopStructure() {
159 // Loop must be in loop simplify form.
160 if (!CurLoop->isLoopSimplifyForm()) {
161 LLVM_DEBUG(dbgs() << " loop is not in loop-simplify form.\n");
162 return false;
163 }
164 // Loop should be innermost loop, if not return false.
165 if (!CurLoop->getSubLoops().empty()) {
166 LLVM_DEBUG(dbgs() << " loop is not innermost\n");
167 return false;
168 }
169 // Loop should have a single backedge, if not return false.
170 if (CurLoop->getNumBackEdges() != 1) {
171 LLVM_DEBUG(dbgs() << " loop has multiple backedges\n");
172 return false;
173 }
174 // Loop must have a single exiting block, if not return false.
175 if (!CurLoop->getExitingBlock()) {
176 LLVM_DEBUG(dbgs() << " loop has multiple exiting block\n");
177 return false;
178 }
179 // We only handle bottom-tested loop, i.e. loop in which the condition is
180 // checked at the end of each iteration. With that we can assume that all
181 // instructions in the loop are executed the same number of times.
182 if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
183 LLVM_DEBUG(dbgs() << " loop is not bottom tested\n");
184 return false;
185 }
186 // Parallel loops must not have aliasing loop-invariant memory accesses.
187 // Hence we don't need to version anything in this case.
188 if (CurLoop->isAnnotatedParallel()) {
189 LLVM_DEBUG(dbgs() << " Parallel loop is not worth versioning\n");
190 return false;
191 }
192 // Loop depth more then LoopDepthThreshold are not allowed
193 if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
194 LLVM_DEBUG(dbgs() << " loop depth is more than threshold\n");
195 return false;
196 }
197 // We need to be able to compute the loop trip count in order
198 // to generate the bound checks.
199 const SCEV *ExitCount = SE->getBackedgeTakenCount(L: CurLoop);
200 if (isa<SCEVCouldNotCompute>(Val: ExitCount)) {
201 LLVM_DEBUG(dbgs() << " loop does not have trip count\n");
202 return false;
203 }
204 return true;
205}
206
207/// Check memory accesses in loop and confirms it's good for
208/// LoopVersioningLICM.
209bool LoopVersioningLICM::legalLoopMemoryAccesses() {
210 // Loop over the body of this loop, construct AST.
211 BatchAAResults BAA(*AA);
212 AliasSetTracker AST(BAA);
213 for (auto *Block : CurLoop->getBlocks()) {
214 // Ignore blocks in subloops.
215 if (LI.getLoopFor(BB: Block) == CurLoop)
216 AST.add(BB&: *Block);
217 }
218
219 // Memory check:
220 // Transform phase will generate a versioned loop and also a runtime check to
221 // ensure the pointers are independent and they don’t alias.
222 // In version variant of loop, alias meta data asserts that all access are
223 // mutually independent.
224 //
225 // Pointers aliasing in alias domain are avoided because with multiple
226 // aliasing domains we may not be able to hoist potential loop invariant
227 // access out of the loop.
228 //
229 // Iterate over alias tracker sets, and confirm AliasSets doesn't have any
230 // must alias set.
231 bool HasMayAlias = false;
232 bool TypeSafety = false;
233 bool HasMod = false;
234 for (const auto &I : AST) {
235 const AliasSet &AS = I;
236 // Skip Forward Alias Sets, as this should be ignored as part of
237 // the AliasSetTracker object.
238 if (AS.isForwardingAliasSet())
239 continue;
240 // With MustAlias its not worth adding runtime bound check.
241 if (AS.isMustAlias())
242 return false;
243 const Value *SomePtr = AS.begin()->Ptr;
244 bool TypeCheck = true;
245 // Check for Mod & MayAlias
246 HasMayAlias |= AS.isMayAlias();
247 HasMod |= AS.isMod();
248 for (const auto &MemLoc : AS) {
249 const Value *Ptr = MemLoc.Ptr;
250 // Alias tracker should have pointers of same data type.
251 //
252 // FIXME: check no longer effective since opaque pointers?
253 // If the intent is to check that the memory accesses use the
254 // same data type (such that LICM can promote them), then we
255 // can no longer see this from the pointer value types.
256 TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));
257 }
258 // At least one alias tracker should have pointers of same data type.
259 TypeSafety |= TypeCheck;
260 }
261 // Ensure types should be of same type.
262 if (!TypeSafety) {
263 LLVM_DEBUG(dbgs() << " Alias tracker type safety failed!\n");
264 return false;
265 }
266 // Ensure loop body shouldn't be read only.
267 if (!HasMod) {
268 LLVM_DEBUG(dbgs() << " No memory modified in loop body\n");
269 return false;
270 }
271 // Make sure alias set has may alias case.
272 // If there no alias memory ambiguity, return false.
273 if (!HasMayAlias) {
274 LLVM_DEBUG(dbgs() << " No ambiguity in memory access.\n");
275 return false;
276 }
277 return true;
278}
279
280/// Check loop instructions safe for Loop versioning.
281/// It returns true if it's safe else returns false.
282/// Consider following:
283/// 1) Check all load store in loop body are non atomic & non volatile.
284/// 2) Check function call safety, by ensuring its not accessing memory.
285/// 3) Loop body shouldn't have any may throw instruction.
286/// 4) Loop body shouldn't have any convergent or noduplicate instructions.
287bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
288 assert(I != nullptr && "Null instruction found!");
289 // Check function call safety
290 if (auto *Call = dyn_cast<CallBase>(Val: I)) {
291 if (Call->isConvergent() || Call->cannotDuplicate()) {
292 LLVM_DEBUG(dbgs() << " Convergent call site found.\n");
293 return false;
294 }
295 if (!Call->willReturn()) {
296 LLVM_DEBUG(dbgs() << " Call site that may not return found.\n");
297 return false;
298 }
299
300 // Calls that only access inaccessible memory cannot alias loop memory and
301 // are safe to duplicate during loop versioning. This covers
302 // llvm.pseudoprobe (used for sample-based profiling under
303 // -fpseudo-probe-for-profiling).
304 if (Call->mayThrow() ||
305 !AA->getMemoryEffects(Call).onlyAccessesInaccessibleMem()) {
306 LLVM_DEBUG(dbgs() << " Unsafe call site found.\n");
307 return false;
308 }
309 return true;
310 }
311
312 // Avoid loops with possiblity of throw
313 if (I->mayThrow()) {
314 LLVM_DEBUG(dbgs() << " May throw instruction found in loop body\n");
315 return false;
316 }
317 // If current instruction is load instructions
318 // make sure it's a simple load (non atomic & non volatile)
319 if (I->mayReadFromMemory()) {
320 LoadInst *Ld = dyn_cast<LoadInst>(Val: I);
321 if (!Ld || !Ld->isSimple()) {
322 LLVM_DEBUG(dbgs() << " Found a non-simple load.\n");
323 return false;
324 }
325 LoadAndStoreCounter++;
326 Value *Ptr = Ld->getPointerOperand();
327 // Check loop invariant.
328 if (SE->isLoopInvariant(S: SE->getSCEV(V: Ptr), L: CurLoop))
329 InvariantCounter++;
330 }
331 // If current instruction is store instruction
332 // make sure it's a simple store (non atomic & non volatile)
333 else if (I->mayWriteToMemory()) {
334 StoreInst *St = dyn_cast<StoreInst>(Val: I);
335 if (!St || !St->isSimple()) {
336 LLVM_DEBUG(dbgs() << " Found a non-simple store.\n");
337 return false;
338 }
339 LoadAndStoreCounter++;
340 Value *Ptr = St->getPointerOperand();
341 // Don't allow stores that we don't have runtime checks for, as we won't be
342 // able to mark them noalias meaning they would prevent any code motion.
343 auto &Pointers = LAI->getRuntimePointerChecking()->Pointers;
344 if (!any_of(Range: Pointers, P: [&](auto &P) { return P.PointerValue == Ptr; })) {
345 LLVM_DEBUG(dbgs() << " Found a store without a runtime check.\n");
346 return false;
347 }
348 // Check loop invariant.
349 if (SE->isLoopInvariant(S: SE->getSCEV(V: Ptr), L: CurLoop))
350 InvariantCounter++;
351
352 IsReadOnlyLoop = false;
353 }
354 return true;
355}
356
357/// Check loop instructions and confirms it's good for
358/// LoopVersioningLICM.
359bool LoopVersioningLICM::legalLoopInstructions() {
360 // Resetting counters.
361 LoadAndStoreCounter = 0;
362 InvariantCounter = 0;
363 IsReadOnlyLoop = true;
364 using namespace ore;
365 // Get LoopAccessInfo from current loop via the proxy.
366 LAI = &LAIs.getInfo(L&: *CurLoop, /*AllowPartial=*/true);
367 // Check LoopAccessInfo for need of runtime check.
368 if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
369 LLVM_DEBUG(dbgs() << " LAA: Runtime check not found !!\n");
370 return false;
371 }
372 // Iterate over loop blocks and instructions of each block and check
373 // instruction safety.
374 for (auto *Block : CurLoop->getBlocks())
375 for (auto &Inst : *Block) {
376 // If instruction is unsafe just return false.
377 if (!instructionSafeForVersioning(I: &Inst)) {
378 ORE->emit(RemarkBuilder: [&]() {
379 return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
380 << " Unsafe Loop Instruction";
381 });
382 return false;
383 }
384 }
385 // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
386 if (LAI->getNumRuntimePointerChecks() >
387 VectorizerParams::RuntimeMemoryCheckThreshold) {
388 LLVM_DEBUG(
389 dbgs() << " LAA: Runtime checks are more than threshold !!\n");
390 ORE->emit(RemarkBuilder: [&]() {
391 return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",
392 CurLoop->getStartLoc(),
393 CurLoop->getHeader())
394 << "Number of runtime checks "
395 << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks())
396 << " exceeds threshold "
397 << NV("Threshold", VectorizerParams::RuntimeMemoryCheckThreshold);
398 });
399 return false;
400 }
401 // Loop should have at least one invariant load or store instruction.
402 if (!InvariantCounter) {
403 LLVM_DEBUG(dbgs() << " Invariant not found !!\n");
404 return false;
405 }
406 // Read only loop not allowed.
407 if (IsReadOnlyLoop) {
408 LLVM_DEBUG(dbgs() << " Found a read-only loop!\n");
409 return false;
410 }
411 // Profitability check:
412 // Check invariant threshold, should be in limit.
413 if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
414 LLVM_DEBUG(
415 dbgs()
416 << " Invariant load & store are less then defined threshold\n");
417 LLVM_DEBUG(dbgs() << " Invariant loads & stores: "
418 << ((InvariantCounter * 100) / LoadAndStoreCounter)
419 << "%\n");
420 LLVM_DEBUG(dbgs() << " Invariant loads & store threshold: "
421 << InvariantThreshold << "%\n");
422 ORE->emit(RemarkBuilder: [&]() {
423 return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",
424 CurLoop->getStartLoc(),
425 CurLoop->getHeader())
426 << "Invariant load & store "
427 << NV("LoadAndStoreCounter",
428 ((InvariantCounter * 100) / LoadAndStoreCounter))
429 << " are less then defined threshold "
430 << NV("Threshold", InvariantThreshold);
431 });
432 return false;
433 }
434 return true;
435}
436
437/// It checks loop is already visited or not.
438/// check loop meta data, if loop revisited return true
439/// else false.
440bool LoopVersioningLICM::isLoopAlreadyVisited() {
441 // Check LoopVersioningLICM metadata into loop
442 if (findStringMetadataForLoop(TheLoop: CurLoop, Name: LICMVersioningMetaData)) {
443 return true;
444 }
445 return false;
446}
447
448/// Checks legality for LoopVersioningLICM by considering following:
449/// a) loop structure legality b) loop instruction legality
450/// c) loop memory access legality.
451/// Return true if legal else returns false.
452bool LoopVersioningLICM::isLegalForVersioning() {
453 using namespace ore;
454 LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);
455 // Make sure not re-visiting same loop again.
456 if (isLoopAlreadyVisited()) {
457 LLVM_DEBUG(
458 dbgs() << " Revisiting loop in LoopVersioningLICM not allowed.\n\n");
459 return false;
460 }
461 // Check loop structure leagality.
462 if (!legalLoopStructure()) {
463 LLVM_DEBUG(
464 dbgs() << " Loop structure not suitable for LoopVersioningLICM\n\n");
465 ORE->emit(RemarkBuilder: [&]() {
466 return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",
467 CurLoop->getStartLoc(),
468 CurLoop->getHeader())
469 << " Unsafe Loop structure";
470 });
471 return false;
472 }
473 // Check loop instruction leagality.
474 if (!legalLoopInstructions()) {
475 LLVM_DEBUG(
476 dbgs()
477 << " Loop instructions not suitable for LoopVersioningLICM\n\n");
478 return false;
479 }
480 // Check loop memory access leagality.
481 if (!legalLoopMemoryAccesses()) {
482 LLVM_DEBUG(
483 dbgs()
484 << " Loop memory access not suitable for LoopVersioningLICM\n\n");
485 ORE->emit(RemarkBuilder: [&]() {
486 return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",
487 CurLoop->getStartLoc(),
488 CurLoop->getHeader())
489 << " Unsafe Loop memory access";
490 });
491 return false;
492 }
493 // Loop versioning is feasible, return true.
494 LLVM_DEBUG(dbgs() << " Loop Versioning found to be beneficial\n\n");
495 ORE->emit(RemarkBuilder: [&]() {
496 return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",
497 CurLoop->getStartLoc(), CurLoop->getHeader())
498 << " Versioned loop for LICM."
499 << " Number of runtime checks we had to insert "
500 << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks());
501 });
502 return true;
503}
504
505bool LoopVersioningLICM::run(DominatorTree *DT) {
506 // Do not do the transformation if disabled by metadata.
507 if (hasLICMVersioningTransformation(L: CurLoop) & TM_Disable)
508 return false;
509
510 bool Changed = false;
511
512 // Check feasiblity of LoopVersioningLICM.
513 // If versioning found to be feasible and beneficial then proceed
514 // else simply return, by cleaning up memory.
515 if (isLegalForVersioning()) {
516 // Do loop versioning.
517 // Create memcheck for memory accessed inside loop.
518 // Clone original loop, and set blocks properly.
519 LoopVersioning LVer(*LAI, LAI->getRuntimePointerChecking()->getChecks(),
520 CurLoop, &LI, DT, SE);
521 LVer.versionLoop();
522 // Set Loop Versioning metaData for original loop.
523 addStringMetadataToLoop(TheLoop: LVer.getNonVersionedLoop(), MDString: LICMVersioningMetaData);
524 // Set Loop Versioning metaData for version loop.
525 addStringMetadataToLoop(TheLoop: LVer.getVersionedLoop(), MDString: LICMVersioningMetaData);
526 // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
527 // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
528 // instructions, not loops.
529 addStringMetadataToLoop(TheLoop: LVer.getVersionedLoop(),
530 MDString: "llvm.mem.parallel_loop_access");
531 // Update version loop with aggressive aliasing assumption.
532 LVer.annotateLoopWithNoAlias();
533 Changed = true;
534 }
535 return Changed;
536}
537
538PreservedAnalyses LoopVersioningLICMPass::run(Loop &L, LoopAnalysisManager &AM,
539 LoopStandardAnalysisResults &LAR,
540 LPMUpdater &U) {
541 AliasAnalysis *AA = &LAR.AA;
542 ScalarEvolution *SE = &LAR.SE;
543 DominatorTree *DT = &LAR.DT;
544 const Function *F = L.getHeader()->getParent();
545 OptimizationRemarkEmitter ORE(F);
546
547 LoopAccessInfoManager LAIs(*SE, *AA, *DT, LAR.LI, nullptr, nullptr, &LAR.AC);
548 if (!LoopVersioningLICM(ScalarOptions::Global, AA, SE, &ORE, LAIs, LAR.LI, &L)
549 .run(DT))
550 return PreservedAnalyses::all();
551 return getLoopPassPreservedAnalyses();
552}
553