1 //===- LoopVersioningLICM.cpp - LICM Loop Versioning ----------------------===//
12 // use loop versioning as an alternative.
14 // Loop Versioning will create a version of the loop with aggressive aliasing
16 // assumptions. The version of the loop making aggressive aliasing assumptions
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
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
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
34 // It transforms loop as shown below:
43 //    |Orig Loop Preheader |               |Cloned Loop Preheader |
47 //    |Orig Loop Body      |               |Cloned Loop Body      |
51 //    |Orig Loop Exit Block|               |Cloned Loop Exit Block|
92 #define DEBUG_TYPE "loop-versioning-licm"
94 static const char *LICMVersioningMetaData = "llvm.loop.licm_versioning.disable";
97 /// invariant instructions in a loop.
101                               "of possible invariant instructions per loop"),
104 /// Threshold for maximum allowed loop nest/depth
108         "LoopVersioningLICM's threshold for maximum allowed loop nest/depth"),
115   // loop versioning might return early due to instructions that are not safe
121                      Loop *CurLoop)  in LoopVersioningLICM()
135   // Current Loop's LoopAccessInfo
143   // The current loop we are working on.
144   Loop *CurLoop;
146   // Maximum loop nest threshold
158   // Read only loop marker.
169   void setNoAliasToLoop(Loop *VerLoop);
175 /// Check loop structure and confirms it's good for LoopVersioningLICM.
177   // Loop must be in loop simplify form.  in legalLoopStructure()
179     LLVM_DEBUG(dbgs() << "    loop is not in loop-simplify form.\n");  in legalLoopStructure()
182   // Loop should be innermost loop, if not return false.  in legalLoopStructure()
184     LLVM_DEBUG(dbgs() << "    loop is not innermost\n");  in legalLoopStructure()
187   // Loop should have a single backedge, if not return false.  in legalLoopStructure()
189     LLVM_DEBUG(dbgs() << "    loop has multiple backedges\n");  in legalLoopStructure()
192   // Loop must have a single exiting block, if not return false.  in legalLoopStructure()
194     LLVM_DEBUG(dbgs() << "    loop has multiple exiting block\n");  in legalLoopStructure()
197   // We only handle bottom-tested loop, i.e. loop in which the condition is  in legalLoopStructure()
199   // instructions in the loop are executed the same number of times.  in legalLoopStructure()
201     LLVM_DEBUG(dbgs() << "    loop is not bottom tested\n");  in legalLoopStructure()
204   // Parallel loops must not have aliasing loop-invariant memory accesses.  in legalLoopStructure()
207     LLVM_DEBUG(dbgs() << "    Parallel loop is not worth versioning\n");  in legalLoopStructure()
210   // Loop depth more then LoopDepthThreshold are not allowed  in legalLoopStructure()
212     LLVM_DEBUG(dbgs() << "    loop depth is more then threshold\n");  in legalLoopStructure()
215   // We need to be able to compute the loop trip count in order  in legalLoopStructure()
219     LLVM_DEBUG(dbgs() << "    loop does not has trip count\n");  in legalLoopStructure()
225 /// Check memory accesses in loop and confirms it's good for
228   // Loop over the body of this loop, construct AST.  in legalLoopMemoryAccesses()
238   // Transform phase will generate a versioned loop and also a runtime check to  in legalLoopMemoryAccesses()
240   // In version variant of loop, alias meta data asserts that all access are  in legalLoopMemoryAccesses()
244   // aliasing domains we may not be able to hoist potential loop invariant  in legalLoopMemoryAccesses()
245   // access out of the loop.  in legalLoopMemoryAccesses()
284   // Ensure loop body shouldn't be read only.  in legalLoopMemoryAccesses()
286     LLVM_DEBUG(dbgs() << "    No memory modified in loop body\n");  in legalLoopMemoryAccesses()
298 /// Check loop instructions safe for Loop versioning.
301 /// 1) Check all load store in loop body are non atomic & non volatile.
303 /// 3) Loop body shouldn't have any may throw instruction.
304 /// 4) Loop body shouldn't have any convergent or noduplicate instructions.
322     LLVM_DEBUG(dbgs() << "    May throw instruction found in loop body\n");  in instructionSafeForVersioning()
335     // Check loop invariant.  in instructionSafeForVersioning()
349     // Check loop invariant.  in instructionSafeForVersioning()
358 /// Check loop instructions and confirms it's good for
366   // Iterate over loop blocks and instructions of each block and check  in legalLoopInstructions()
374                  << " Unsafe Loop Instruction";  in legalLoopInstructions()
379   // Get LoopAccessInfo from current loop via the proxy.  in legalLoopInstructions()
402   // Loop should have at least one invariant load or store instruction.  in legalLoopInstructions()
407   // Read only loop not allowed.  in legalLoopInstructions()
409     LLVM_DEBUG(dbgs() << "    Found a read-only loop!\n");  in legalLoopInstructions()
438 /// It checks loop is already visited or not.
439 /// check loop meta data, if loop revisited return true
442   // Check LoopVersioningLICM metadata into loop  in isLoopAlreadyVisited()
450 /// a) loop structure legality   b) loop instruction legality
451 /// c) loop memory access legality.
455   LLVM_DEBUG(dbgs() << "Loop: " << *CurLoop);  in isLegalForVersioning()
456   // Make sure not re-visiting same loop again.  in isLegalForVersioning()
459         dbgs() << "    Revisiting loop in LoopVersioningLICM not allowed.\n\n");  in isLegalForVersioning()
462   // Check loop structure leagality.  in isLegalForVersioning()
465         dbgs() << "    Loop structure not suitable for LoopVersioningLICM\n\n");  in isLegalForVersioning()
470              << " Unsafe Loop structure";  in isLegalForVersioning()
474   // Check loop instruction leagality.  in isLegalForVersioning()
478         << "    Loop instructions not suitable for LoopVersioningLICM\n\n");  in isLegalForVersioning()
481   // Check loop memory access leagality.  in isLegalForVersioning()
485         << "    Loop memory access not suitable for LoopVersioningLICM\n\n");  in isLegalForVersioning()
490              << " Unsafe Loop memory access";  in isLegalForVersioning()
494   // Loop versioning is feasible, return true.  in isLegalForVersioning()
495   LLVM_DEBUG(dbgs() << "    Loop Versioning found to be beneficial\n\n");  in isLegalForVersioning()
499            << " Versioned loop for LICM."  in isLegalForVersioning()
506 /// Update loop with aggressive aliasing assumptions.
508 /// loop should not have any must-alias memory accesses pairs.
511 void LoopVersioningLICM::setNoAliasToLoop(Loop *VerLoop) {  in setNoAliasToLoop()
520   // Iterate over each instruction of loop.  in setNoAliasToLoop()
552     // Do loop versioning.  in run()
553     // Create memcheck for memory accessed inside loop.  in run()
554     // Clone original loop, and set blocks properly.  in run()
558     // Set Loop Versioning metaData for original loop.  in run()
560     // Set Loop Versioning metaData for version loop.  in run()
562     // Set "llvm.mem.parallel_loop_access" metaData to versioned loop.  in run()
567     // Update version loop with aggressive aliasing assumption.  in run()
576 PreservedAnalyses LoopVersioningLICMPass::run(Loop &L, LoopAnalysisManager &AM,  in run()