1 //===- LoopUnrollAndJam.cpp - Loop unroll and jam pass --------------------===//
54 #define DEBUG_TYPE "loop-unroll-and-jam"
59     "llvm.loop.unroll_and_jam.followup_all";
61     "llvm.loop.unroll_and_jam.followup_inner";
63     "llvm.loop.unroll_and_jam.followup_outer";
65     "llvm.loop.unroll_and_jam.followup_remainder_inner";
67     "llvm.loop.unroll_and_jam.followup_remainder_outer";
81     cl::desc("Threshold to use for inner loop when doing unroll and jam."));
88 // Returns the loop hint metadata node with the given name (for example,
89 // "llvm.loop.unroll.count").  If no such metadata node exists, then nullptr is
91 static MDNode *getUnrollMetadataForLoop(const Loop *L, StringRef Name) {  in getUnrollMetadataForLoop()
97 // Returns true if the loop has any metadata starting with Prefix. For example a
98 // Prefix of "llvm.loop.unroll." returns true if we have any unroll metadata.
99 static bool hasAnyUnrollPragma(const Loop *L, StringRef Prefix) {  in hasAnyUnrollPragma()
101     // First operand should refer to the loop id itself.  in hasAnyUnrollPragma()
103     assert(LoopID->getOperand(0) == LoopID && "invalid loop id");  in hasAnyUnrollPragma()
121 // Returns true if the loop has an unroll_and_jam(enable) pragma.
122 static bool hasUnrollAndJamEnablePragma(const Loop *L) {  in hasUnrollAndJamEnablePragma()
123   return getUnrollMetadataForLoop(L, "llvm.loop.unroll_and_jam.enable");  in hasUnrollAndJamEnablePragma()
126 // If loop has an unroll_and_jam_count pragma return the (necessarily
128 static unsigned unrollAndJamCountPragmaValue(const Loop *L) {  in unrollAndJamCountPragmaValue()
129   MDNode *MD = getUnrollMetadataForLoop(L, "llvm.loop.unroll_and_jam.count");  in unrollAndJamCountPragmaValue()
141 // Returns loop size estimation for unrolled loop.
152     Loop *L, Loop *SubLoop, const TargetTransformInfo &TTI, DominatorTree &DT,  in computeUnrollAndJamCount()
161   // First up use computeUnrollCount from the loop unroller to get a count  in computeUnrollAndJamCount()
162   // for unrolling the outer loop, plus any loops requiring explicit  in computeUnrollAndJamCount()
164   // UP.PartialThreshold / UP.MaxCount to come up with sensible loop values.  in computeUnrollAndJamCount()
165   // We have already checked that the loop has no unroll.* pragmas.  in computeUnrollAndJamCount()
173     // If the user explicitly set the loop as unrolled, dont UnJ it. Leave it  in computeUnrollAndJamCount()
210   // If the loop has an unrolling pragma, we want to be more aggressive with  in computeUnrollAndJamCount()
218                          "inner loop too large\n");  in computeUnrollAndJamCount()
223   // We have a sensible limit for the outer loop, now adjust it for the inner  in computeUnrollAndJamCount()
224   // loop and UP.UnrollAndJamInnerLoopThreshold. If the outer limit was set  in computeUnrollAndJamCount()
237   // If the inner loop count is known and small, leave the entire loop nest to  in computeUnrollAndJamCount()
240     LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; small inner loop count is "  in computeUnrollAndJamCount()
250         dbgs() << "Won't unroll-and-jam; More than one inner loop block\n");  in computeUnrollAndJamCount()
256   // jamming the loop. In this case, look for loads that are invariant in the  in computeUnrollAndJamCount()
257   // outer loop and can become shared.  in computeUnrollAndJamCount()
270     LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; No loop invariant loads\n");  in computeUnrollAndJamCount()
279 tryToUnrollAndJamLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,  in tryToUnrollAndJamLoop()
303   LLVM_DEBUG(dbgs() << "Loop Unroll and Jam: F["  in tryToUnrollAndJamLoop()
304                     << L->getHeader()->getParent()->getName() << "] Loop %"  in tryToUnrollAndJamLoop()
307   // A loop with any unroll pragma (enabling/disabling/count/etc) is left for  in tryToUnrollAndJamLoop()
311   if (hasAnyUnrollPragma(L, "llvm.loop.unroll.") &&  in tryToUnrollAndJamLoop()
312       !hasAnyUnrollPragma(L, "llvm.loop.unroll_and_jam.")) {  in tryToUnrollAndJamLoop()
322   // Approximate the loop size and collect useful info  in tryToUnrollAndJamLoop()
325   Loop *SubLoop = L->getSubLoops()[0];  in tryToUnrollAndJamLoop()
330     LLVM_DEBUG(dbgs() << "  Loop not considered unrollable\n");  in tryToUnrollAndJamLoop()
335   LLVM_DEBUG(dbgs() << "  Outer Loop Size: " << OuterUCE.getRolledLoopSize()  in tryToUnrollAndJamLoop()
337   LLVM_DEBUG(dbgs() << "  Inner Loop Size: " << InnerLoopSize << "\n");  in tryToUnrollAndJamLoop()
340     LLVM_DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");  in tryToUnrollAndJamLoop()
348         dbgs() << "  Not unrolling loop with convergent instructions.\n");  in tryToUnrollAndJamLoop()
352   // Save original loop IDs for after the transformation.  in tryToUnrollAndJamLoop()
356   // To assign the loop id of the epilogue, assign it before unrolling it so it  in tryToUnrollAndJamLoop()
357   // is applied to every inner loop of the epilogue. We later apply the loop ID  in tryToUnrollAndJamLoop()
358   // for the jammed inner loop.  in tryToUnrollAndJamLoop()
382   Loop *EpilogueOuterLoop = nullptr;  in tryToUnrollAndJamLoop()
387   // Assign new loop attributes.  in tryToUnrollAndJamLoop()
416   // If loop has an unroll count pragma or unrolled by explicitly set count  in tryToUnrollAndJamLoop()
417   // mark loop as unrolled to prevent unrolling beyond that requested.  in tryToUnrollAndJamLoop()
431   ArrayRef<Loop *> Loops = LN.getLoops();  in tryToUnrollAndJamLoop()
432   Loop *OutmostLoop = &LN.getOutermostLoop();  in tryToUnrollAndJamLoop()
434   // Add the loop nests in the reverse order of LN. See method  in tryToUnrollAndJamLoop()
436   SmallPriorityWorklist<Loop *, 4> Worklist;  in tryToUnrollAndJamLoop()
439     Loop *L = Worklist.pop_back_val();  in tryToUnrollAndJamLoop()