xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp (revision e6bfd18d21b225af6a0ed67ceeaf1293b7b9eba5)
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 "llvm/ADT/SmallVector.h"
64 #include "llvm/ADT/StringRef.h"
65 #include "llvm/Analysis/AliasAnalysis.h"
66 #include "llvm/Analysis/AliasSetTracker.h"
67 #include "llvm/Analysis/GlobalsModRef.h"
68 #include "llvm/Analysis/LoopAccessAnalysis.h"
69 #include "llvm/Analysis/LoopInfo.h"
70 #include "llvm/Analysis/LoopPass.h"
71 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
72 #include "llvm/Analysis/ScalarEvolution.h"
73 #include "llvm/IR/Dominators.h"
74 #include "llvm/IR/Instruction.h"
75 #include "llvm/IR/Instructions.h"
76 #include "llvm/IR/LLVMContext.h"
77 #include "llvm/IR/MDBuilder.h"
78 #include "llvm/IR/Metadata.h"
79 #include "llvm/IR/Value.h"
80 #include "llvm/InitializePasses.h"
81 #include "llvm/Pass.h"
82 #include "llvm/Support/Casting.h"
83 #include "llvm/Support/CommandLine.h"
84 #include "llvm/Support/Debug.h"
85 #include "llvm/Support/raw_ostream.h"
86 #include "llvm/Transforms/Scalar.h"
87 #include "llvm/Transforms/Utils.h"
88 #include "llvm/Transforms/Utils/LoopUtils.h"
89 #include "llvm/Transforms/Utils/LoopVersioning.h"
90 #include <cassert>
91 #include <memory>
92 
93 using namespace llvm;
94 
95 #define DEBUG_TYPE "loop-versioning-licm"
96 
97 static const char *LICMVersioningMetaData = "llvm.loop.licm_versioning.disable";
98 
99 /// Threshold minimum allowed percentage for possible
100 /// invariant instructions in a loop.
101 static cl::opt<float>
102     LVInvarThreshold("licm-versioning-invariant-threshold",
103                      cl::desc("LoopVersioningLICM's minimum allowed percentage"
104                               "of possible invariant instructions per loop"),
105                      cl::init(25), cl::Hidden);
106 
107 /// Threshold for maximum allowed loop nest/depth
108 static cl::opt<unsigned> LVLoopDepthThreshold(
109     "licm-versioning-max-depth-threshold",
110     cl::desc(
111         "LoopVersioningLICM's threshold for maximum allowed loop nest/depth"),
112     cl::init(2), cl::Hidden);
113 
114 namespace {
115 
116 struct LoopVersioningLICMLegacyPass : public LoopPass {
117   static char ID;
118 
119   LoopVersioningLICMLegacyPass() : LoopPass(ID) {
120     initializeLoopVersioningLICMLegacyPassPass(
121         *PassRegistry::getPassRegistry());
122   }
123 
124   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
125 
126   StringRef getPassName() const override { return "Loop Versioning for LICM"; }
127 
128   void getAnalysisUsage(AnalysisUsage &AU) const override {
129     AU.setPreservesCFG();
130     AU.addRequired<AAResultsWrapperPass>();
131     AU.addRequired<DominatorTreeWrapperPass>();
132     AU.addRequiredID(LCSSAID);
133     AU.addRequired<LoopAccessLegacyAnalysis>();
134     AU.addRequired<LoopInfoWrapperPass>();
135     AU.addRequiredID(LoopSimplifyID);
136     AU.addRequired<ScalarEvolutionWrapperPass>();
137     AU.addPreserved<AAResultsWrapperPass>();
138     AU.addPreserved<GlobalsAAWrapperPass>();
139     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
140   }
141 };
142 
143 struct LoopVersioningLICM {
144   // We don't explicitly pass in LoopAccessInfo to the constructor since the
145   // loop versioning might return early due to instructions that are not safe
146   // for versioning. By passing the proxy instead the construction of
147   // LoopAccessInfo will take place only when it's necessary.
148   LoopVersioningLICM(AliasAnalysis *AA, ScalarEvolution *SE,
149                      OptimizationRemarkEmitter *ORE,
150                      function_ref<const LoopAccessInfo &(Loop *)> GetLAI)
151       : AA(AA), SE(SE), GetLAI(GetLAI),
152         LoopDepthThreshold(LVLoopDepthThreshold),
153         InvariantThreshold(LVInvarThreshold), ORE(ORE) {}
154 
155   bool runOnLoop(Loop *L, LoopInfo *LI, DominatorTree *DT);
156 
157   void reset() {
158     AA = nullptr;
159     SE = nullptr;
160     CurLoop = nullptr;
161     LoadAndStoreCounter = 0;
162     InvariantCounter = 0;
163     IsReadOnlyLoop = true;
164     ORE = nullptr;
165     CurAST.reset();
166   }
167 
168   class AutoResetter {
169   public:
170     AutoResetter(LoopVersioningLICM &LVLICM) : LVLICM(LVLICM) {}
171     ~AutoResetter() { LVLICM.reset(); }
172 
173   private:
174     LoopVersioningLICM &LVLICM;
175   };
176 
177 private:
178   // Current AliasAnalysis information
179   AliasAnalysis *AA = nullptr;
180 
181   // Current ScalarEvolution
182   ScalarEvolution *SE = nullptr;
183 
184   // Current Loop's LoopAccessInfo
185   const LoopAccessInfo *LAI = nullptr;
186 
187   // Proxy for retrieving LoopAccessInfo.
188   function_ref<const LoopAccessInfo &(Loop *)> GetLAI;
189 
190   // The current loop we are working on.
191   Loop *CurLoop = nullptr;
192 
193   // AliasSet information for the current loop.
194   std::unique_ptr<AliasSetTracker> CurAST;
195 
196   // Maximum loop nest threshold
197   unsigned LoopDepthThreshold;
198 
199   // Minimum invariant threshold
200   float InvariantThreshold;
201 
202   // Counter to track num of load & store
203   unsigned LoadAndStoreCounter = 0;
204 
205   // Counter to track num of invariant
206   unsigned InvariantCounter = 0;
207 
208   // Read only loop marker.
209   bool IsReadOnlyLoop = true;
210 
211   // OptimizationRemarkEmitter
212   OptimizationRemarkEmitter *ORE;
213 
214   bool isLegalForVersioning();
215   bool legalLoopStructure();
216   bool legalLoopInstructions();
217   bool legalLoopMemoryAccesses();
218   bool isLoopAlreadyVisited();
219   void setNoAliasToLoop(Loop *VerLoop);
220   bool instructionSafeForVersioning(Instruction *I);
221 };
222 
223 } // end anonymous namespace
224 
225 /// Check loop structure and confirms it's good for LoopVersioningLICM.
226 bool LoopVersioningLICM::legalLoopStructure() {
227   // Loop must be in loop simplify form.
228   if (!CurLoop->isLoopSimplifyForm()) {
229     LLVM_DEBUG(dbgs() << "    loop is not in loop-simplify form.\n");
230     return false;
231   }
232   // Loop should be innermost loop, if not return false.
233   if (!CurLoop->getSubLoops().empty()) {
234     LLVM_DEBUG(dbgs() << "    loop is not innermost\n");
235     return false;
236   }
237   // Loop should have a single backedge, if not return false.
238   if (CurLoop->getNumBackEdges() != 1) {
239     LLVM_DEBUG(dbgs() << "    loop has multiple backedges\n");
240     return false;
241   }
242   // Loop must have a single exiting block, if not return false.
243   if (!CurLoop->getExitingBlock()) {
244     LLVM_DEBUG(dbgs() << "    loop has multiple exiting block\n");
245     return false;
246   }
247   // We only handle bottom-tested loop, i.e. loop in which the condition is
248   // checked at the end of each iteration. With that we can assume that all
249   // instructions in the loop are executed the same number of times.
250   if (CurLoop->getExitingBlock() != CurLoop->getLoopLatch()) {
251     LLVM_DEBUG(dbgs() << "    loop is not bottom tested\n");
252     return false;
253   }
254   // Parallel loops must not have aliasing loop-invariant memory accesses.
255   // Hence we don't need to version anything in this case.
256   if (CurLoop->isAnnotatedParallel()) {
257     LLVM_DEBUG(dbgs() << "    Parallel loop is not worth versioning\n");
258     return false;
259   }
260   // Loop depth more then LoopDepthThreshold are not allowed
261   if (CurLoop->getLoopDepth() > LoopDepthThreshold) {
262     LLVM_DEBUG(dbgs() << "    loop depth is more then threshold\n");
263     return false;
264   }
265   // We need to be able to compute the loop trip count in order
266   // to generate the bound checks.
267   const SCEV *ExitCount = SE->getBackedgeTakenCount(CurLoop);
268   if (isa<SCEVCouldNotCompute>(ExitCount)) {
269     LLVM_DEBUG(dbgs() << "    loop does not has trip count\n");
270     return false;
271   }
272   return true;
273 }
274 
275 /// Check memory accesses in loop and confirms it's good for
276 /// LoopVersioningLICM.
277 bool LoopVersioningLICM::legalLoopMemoryAccesses() {
278   bool HasMayAlias = false;
279   bool TypeSafety = false;
280   bool HasMod = false;
281   // Memory check:
282   // Transform phase will generate a versioned loop and also a runtime check to
283   // ensure the pointers are independent and they don’t alias.
284   // In version variant of loop, alias meta data asserts that all access are
285   // mutually independent.
286   //
287   // Pointers aliasing in alias domain are avoided because with multiple
288   // aliasing domains we may not be able to hoist potential loop invariant
289   // access out of the loop.
290   //
291   // Iterate over alias tracker sets, and confirm AliasSets doesn't have any
292   // must alias set.
293   for (const auto &I : *CurAST) {
294     const AliasSet &AS = I;
295     // Skip Forward Alias Sets, as this should be ignored as part of
296     // the AliasSetTracker object.
297     if (AS.isForwardingAliasSet())
298       continue;
299     // With MustAlias its not worth adding runtime bound check.
300     if (AS.isMustAlias())
301       return false;
302     Value *SomePtr = AS.begin()->getValue();
303     bool TypeCheck = true;
304     // Check for Mod & MayAlias
305     HasMayAlias |= AS.isMayAlias();
306     HasMod |= AS.isMod();
307     for (const auto &A : AS) {
308       Value *Ptr = A.getValue();
309       // Alias tracker should have pointers of same data type.
310       TypeCheck = (TypeCheck && (SomePtr->getType() == Ptr->getType()));
311     }
312     // At least one alias tracker should have pointers of same data type.
313     TypeSafety |= TypeCheck;
314   }
315   // Ensure types should be of same type.
316   if (!TypeSafety) {
317     LLVM_DEBUG(dbgs() << "    Alias tracker type safety failed!\n");
318     return false;
319   }
320   // Ensure loop body shouldn't be read only.
321   if (!HasMod) {
322     LLVM_DEBUG(dbgs() << "    No memory modified in loop body\n");
323     return false;
324   }
325   // Make sure alias set has may alias case.
326   // If there no alias memory ambiguity, return false.
327   if (!HasMayAlias) {
328     LLVM_DEBUG(dbgs() << "    No ambiguity in memory access.\n");
329     return false;
330   }
331   return true;
332 }
333 
334 /// Check loop instructions safe for Loop versioning.
335 /// It returns true if it's safe else returns false.
336 /// Consider following:
337 /// 1) Check all load store in loop body are non atomic & non volatile.
338 /// 2) Check function call safety, by ensuring its not accessing memory.
339 /// 3) Loop body shouldn't have any may throw instruction.
340 /// 4) Loop body shouldn't have any convergent or noduplicate instructions.
341 bool LoopVersioningLICM::instructionSafeForVersioning(Instruction *I) {
342   assert(I != nullptr && "Null instruction found!");
343   // Check function call safety
344   if (auto *Call = dyn_cast<CallBase>(I)) {
345     if (Call->isConvergent() || Call->cannotDuplicate()) {
346       LLVM_DEBUG(dbgs() << "    Convergent call site found.\n");
347       return false;
348     }
349 
350     if (!AA->doesNotAccessMemory(Call)) {
351       LLVM_DEBUG(dbgs() << "    Unsafe call site found.\n");
352       return false;
353     }
354   }
355 
356   // Avoid loops with possiblity of throw
357   if (I->mayThrow()) {
358     LLVM_DEBUG(dbgs() << "    May throw instruction found in loop body\n");
359     return false;
360   }
361   // If current instruction is load instructions
362   // make sure it's a simple load (non atomic & non volatile)
363   if (I->mayReadFromMemory()) {
364     LoadInst *Ld = dyn_cast<LoadInst>(I);
365     if (!Ld || !Ld->isSimple()) {
366       LLVM_DEBUG(dbgs() << "    Found a non-simple load.\n");
367       return false;
368     }
369     LoadAndStoreCounter++;
370     Value *Ptr = Ld->getPointerOperand();
371     // Check loop invariant.
372     if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
373       InvariantCounter++;
374   }
375   // If current instruction is store instruction
376   // make sure it's a simple store (non atomic & non volatile)
377   else if (I->mayWriteToMemory()) {
378     StoreInst *St = dyn_cast<StoreInst>(I);
379     if (!St || !St->isSimple()) {
380       LLVM_DEBUG(dbgs() << "    Found a non-simple store.\n");
381       return false;
382     }
383     LoadAndStoreCounter++;
384     Value *Ptr = St->getPointerOperand();
385     // Check loop invariant.
386     if (SE->isLoopInvariant(SE->getSCEV(Ptr), CurLoop))
387       InvariantCounter++;
388 
389     IsReadOnlyLoop = false;
390   }
391   return true;
392 }
393 
394 /// Check loop instructions and confirms it's good for
395 /// LoopVersioningLICM.
396 bool LoopVersioningLICM::legalLoopInstructions() {
397   // Resetting counters.
398   LoadAndStoreCounter = 0;
399   InvariantCounter = 0;
400   IsReadOnlyLoop = true;
401   using namespace ore;
402   // Iterate over loop blocks and instructions of each block and check
403   // instruction safety.
404   for (auto *Block : CurLoop->getBlocks())
405     for (auto &Inst : *Block) {
406       // If instruction is unsafe just return false.
407       if (!instructionSafeForVersioning(&Inst)) {
408         ORE->emit([&]() {
409           return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopInst", &Inst)
410                  << " Unsafe Loop Instruction";
411         });
412         return false;
413       }
414     }
415   // Get LoopAccessInfo from current loop via the proxy.
416   LAI = &GetLAI(CurLoop);
417   // Check LoopAccessInfo for need of runtime check.
418   if (LAI->getRuntimePointerChecking()->getChecks().empty()) {
419     LLVM_DEBUG(dbgs() << "    LAA: Runtime check not found !!\n");
420     return false;
421   }
422   // Number of runtime-checks should be less then RuntimeMemoryCheckThreshold
423   if (LAI->getNumRuntimePointerChecks() >
424       VectorizerParams::RuntimeMemoryCheckThreshold) {
425     LLVM_DEBUG(
426         dbgs() << "    LAA: Runtime checks are more than threshold !!\n");
427     ORE->emit([&]() {
428       return OptimizationRemarkMissed(DEBUG_TYPE, "RuntimeCheck",
429                                       CurLoop->getStartLoc(),
430                                       CurLoop->getHeader())
431              << "Number of runtime checks "
432              << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks())
433              << " exceeds threshold "
434              << NV("Threshold", VectorizerParams::RuntimeMemoryCheckThreshold);
435     });
436     return false;
437   }
438   // Loop should have at least one invariant load or store instruction.
439   if (!InvariantCounter) {
440     LLVM_DEBUG(dbgs() << "    Invariant not found !!\n");
441     return false;
442   }
443   // Read only loop not allowed.
444   if (IsReadOnlyLoop) {
445     LLVM_DEBUG(dbgs() << "    Found a read-only loop!\n");
446     return false;
447   }
448   // Profitablity check:
449   // Check invariant threshold, should be in limit.
450   if (InvariantCounter * 100 < InvariantThreshold * LoadAndStoreCounter) {
451     LLVM_DEBUG(
452         dbgs()
453         << "    Invariant load & store are less then defined threshold\n");
454     LLVM_DEBUG(dbgs() << "    Invariant loads & stores: "
455                       << ((InvariantCounter * 100) / LoadAndStoreCounter)
456                       << "%\n");
457     LLVM_DEBUG(dbgs() << "    Invariant loads & store threshold: "
458                       << InvariantThreshold << "%\n");
459     ORE->emit([&]() {
460       return OptimizationRemarkMissed(DEBUG_TYPE, "InvariantThreshold",
461                                       CurLoop->getStartLoc(),
462                                       CurLoop->getHeader())
463              << "Invariant load & store "
464              << NV("LoadAndStoreCounter",
465                    ((InvariantCounter * 100) / LoadAndStoreCounter))
466              << " are less then defined threshold "
467              << NV("Threshold", InvariantThreshold);
468     });
469     return false;
470   }
471   return true;
472 }
473 
474 /// It checks loop is already visited or not.
475 /// check loop meta data, if loop revisited return true
476 /// else false.
477 bool LoopVersioningLICM::isLoopAlreadyVisited() {
478   // Check LoopVersioningLICM metadata into loop
479   if (findStringMetadataForLoop(CurLoop, LICMVersioningMetaData)) {
480     return true;
481   }
482   return false;
483 }
484 
485 /// Checks legality for LoopVersioningLICM by considering following:
486 /// a) loop structure legality   b) loop instruction legality
487 /// c) loop memory access legality.
488 /// Return true if legal else returns false.
489 bool LoopVersioningLICM::isLegalForVersioning() {
490   using namespace ore;
491   LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);
492   // Make sure not re-visiting same loop again.
493   if (isLoopAlreadyVisited()) {
494     LLVM_DEBUG(
495         dbgs() << "    Revisiting loop in LoopVersioningLICM not allowed.\n\n");
496     return false;
497   }
498   // Check loop structure leagality.
499   if (!legalLoopStructure()) {
500     LLVM_DEBUG(
501         dbgs() << "    Loop structure not suitable for LoopVersioningLICM\n\n");
502     ORE->emit([&]() {
503       return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopStruct",
504                                       CurLoop->getStartLoc(),
505                                       CurLoop->getHeader())
506              << " Unsafe Loop structure";
507     });
508     return false;
509   }
510   // Check loop instruction leagality.
511   if (!legalLoopInstructions()) {
512     LLVM_DEBUG(
513         dbgs()
514         << "    Loop instructions not suitable for LoopVersioningLICM\n\n");
515     return false;
516   }
517   // Check loop memory access leagality.
518   if (!legalLoopMemoryAccesses()) {
519     LLVM_DEBUG(
520         dbgs()
521         << "    Loop memory access not suitable for LoopVersioningLICM\n\n");
522     ORE->emit([&]() {
523       return OptimizationRemarkMissed(DEBUG_TYPE, "IllegalLoopMemoryAccess",
524                                       CurLoop->getStartLoc(),
525                                       CurLoop->getHeader())
526              << " Unsafe Loop memory access";
527     });
528     return false;
529   }
530   // Loop versioning is feasible, return true.
531   LLVM_DEBUG(dbgs() << "    Loop Versioning found to be beneficial\n\n");
532   ORE->emit([&]() {
533     return OptimizationRemark(DEBUG_TYPE, "IsLegalForVersioning",
534                               CurLoop->getStartLoc(), CurLoop->getHeader())
535            << " Versioned loop for LICM."
536            << " Number of runtime checks we had to insert "
537            << NV("RuntimeChecks", LAI->getNumRuntimePointerChecks());
538   });
539   return true;
540 }
541 
542 /// Update loop with aggressive aliasing assumptions.
543 /// It marks no-alias to any pairs of memory operations by assuming
544 /// loop should not have any must-alias memory accesses pairs.
545 /// During LoopVersioningLICM legality we ignore loops having must
546 /// aliasing memory accesses.
547 void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {
548   // Get latch terminator instruction.
549   Instruction *I = VerLoop->getLoopLatch()->getTerminator();
550   // Create alias scope domain.
551   MDBuilder MDB(I->getContext());
552   MDNode *NewDomain = MDB.createAnonymousAliasScopeDomain("LVDomain");
553   StringRef Name = "LVAliasScope";
554   MDNode *NewScope = MDB.createAnonymousAliasScope(NewDomain, Name);
555   SmallVector<Metadata *, 4> Scopes{NewScope}, NoAliases{NewScope};
556   // Iterate over each instruction of loop.
557   // set no-alias for all load & store instructions.
558   for (auto *Block : CurLoop->getBlocks()) {
559     for (auto &Inst : *Block) {
560       // Only interested in instruction that may modify or read memory.
561       if (!Inst.mayReadFromMemory() && !Inst.mayWriteToMemory())
562         continue;
563       // Set no-alias for current instruction.
564       Inst.setMetadata(
565           LLVMContext::MD_noalias,
566           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_noalias),
567                               MDNode::get(Inst.getContext(), NoAliases)));
568       // set alias-scope for current instruction.
569       Inst.setMetadata(
570           LLVMContext::MD_alias_scope,
571           MDNode::concatenate(Inst.getMetadata(LLVMContext::MD_alias_scope),
572                               MDNode::get(Inst.getContext(), Scopes)));
573     }
574   }
575 }
576 
577 bool LoopVersioningLICMLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
578   if (skipLoop(L))
579     return false;
580 
581   AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
582   ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
583   OptimizationRemarkEmitter *ORE =
584       &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
585   LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
586   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
587 
588   auto GetLAI = [&](Loop *L) -> const LoopAccessInfo & {
589     return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(L);
590   };
591 
592   return LoopVersioningLICM(AA, SE, ORE, GetLAI).runOnLoop(L, LI, DT);
593 }
594 
595 bool LoopVersioningLICM::runOnLoop(Loop *L, LoopInfo *LI, DominatorTree *DT) {
596   // This will automatically release all resources hold by the current
597   // LoopVersioningLICM object.
598   AutoResetter Resetter(*this);
599 
600   // Do not do the transformation if disabled by metadata.
601   if (hasLICMVersioningTransformation(L) & TM_Disable)
602     return false;
603 
604   // Set Current Loop
605   CurLoop = L;
606   CurAST.reset(new AliasSetTracker(*AA));
607 
608   // Loop over the body of this loop, construct AST.
609   for (auto *Block : L->getBlocks()) {
610     if (LI->getLoopFor(Block) == L) // Ignore blocks in subloop.
611       CurAST->add(*Block);          // Incorporate the specified basic block
612   }
613 
614   bool Changed = false;
615 
616   // Check feasiblity of LoopVersioningLICM.
617   // If versioning found to be feasible and beneficial then proceed
618   // else simply return, by cleaning up memory.
619   if (isLegalForVersioning()) {
620     // Do loop versioning.
621     // Create memcheck for memory accessed inside loop.
622     // Clone original loop, and set blocks properly.
623     LoopVersioning LVer(*LAI, LAI->getRuntimePointerChecking()->getChecks(),
624                         CurLoop, LI, DT, SE);
625     LVer.versionLoop();
626     // Set Loop Versioning metaData for original loop.
627     addStringMetadataToLoop(LVer.getNonVersionedLoop(), LICMVersioningMetaData);
628     // Set Loop Versioning metaData for version loop.
629     addStringMetadataToLoop(LVer.getVersionedLoop(), LICMVersioningMetaData);
630     // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.
631     // FIXME: "llvm.mem.parallel_loop_access" annotates memory access
632     // instructions, not loops.
633     addStringMetadataToLoop(LVer.getVersionedLoop(),
634                             "llvm.mem.parallel_loop_access");
635     // Update version loop with aggressive aliasing assumption.
636     setNoAliasToLoop(LVer.getVersionedLoop());
637     Changed = true;
638   }
639   return Changed;
640 }
641 
642 char LoopVersioningLICMLegacyPass::ID = 0;
643 
644 INITIALIZE_PASS_BEGIN(LoopVersioningLICMLegacyPass, "loop-versioning-licm",
645                       "Loop Versioning For LICM", false, false)
646 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
647 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
648 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
649 INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
650 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
651 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
652 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
653 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
654 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
655 INITIALIZE_PASS_END(LoopVersioningLICMLegacyPass, "loop-versioning-licm",
656                     "Loop Versioning For LICM", false, false)
657 
658 Pass *llvm::createLoopVersioningLICMPass() {
659   return new LoopVersioningLICMLegacyPass();
660 }
661 
662 namespace llvm {
663 
664 PreservedAnalyses LoopVersioningLICMPass::run(Loop &L, LoopAnalysisManager &AM,
665                                               LoopStandardAnalysisResults &LAR,
666                                               LPMUpdater &U) {
667   AliasAnalysis *AA = &LAR.AA;
668   ScalarEvolution *SE = &LAR.SE;
669   DominatorTree *DT = &LAR.DT;
670   LoopInfo *LI = &LAR.LI;
671   const Function *F = L.getHeader()->getParent();
672   OptimizationRemarkEmitter ORE(F);
673 
674   auto GetLAI = [&](Loop *L) -> const LoopAccessInfo & {
675     return AM.getResult<LoopAccessAnalysis>(*L, LAR);
676   };
677 
678   if (!LoopVersioningLICM(AA, SE, &ORE, GetLAI).runOnLoop(&L, LI, DT))
679     return PreservedAnalyses::all();
680   return getLoopPassPreservedAnalyses();
681 }
682 } // namespace llvm
683