[LLVMdev] [PATCH] Split LoopUnroll pass into mechanism and policy

[Dan Gohman]

Hello Matthijs,

On May 9, 2008, at 3:47 AM, Matthijs Kooijman wrote:

> Hi All,
>
> the attached patch performs the splitting in the proposed manner.
> before applying the patch, please execute
> 	svn cp lib/Transforms/Scalar/LoopUnroll.cpp lib/Transforms/Utils/ 
> UnrollLoop.cpp
> to make the patch apply and preserve proper history.
>
> Transforms/Utils/UnrollLoop.cpp contains the unrollLoop function,  
> which is now
> used by the LoopUnroll pass. I've also moved the RemapInstruction and
> FoldBlockIntoPredecessor support functions there.
>
> Additionally, I've also moved the loop unrolling statistics into the  
> Utils file. Is
> that a good idea?
>
> I've added two new methods to Loop (or LoopBase<> really):
> getSmallConstantTripCount() and getSmallConstantTripMultiple(),  
> which return
> the trip count and multiple as a normal unsigned value.
>
> There are a number of remaining issues, though. Firstly, I observe  
> some code
> duplication. Every pass that performs loop unrolling, should depend  
> on the
> LoopSimplify, LCSSA and LoopInfo passes. Also, the UnrollLoop code  
> always
> preservers the latter two passes. This means a large part of the
> getAnalysisUsage for every unroll pass will be copy-pasted. This  
> could be
> solved by adding an extra "defaultAnalysisUsage()" function to
> Utils/UnrollLoop.cpp or something similar, but I'm not sure that's  
> very pretty.
> Any suggestions?

I'm not sure that's very pretty either :-}. My sense is that it's
better to just duplicate those few lines. The unrollLoop function
verifies isLCSSAForm with an assert, and LoopSimplify and LoopInfo
are required by pretty much every loop pass. For the addPreserved
lines, I guess unrollLoop should just have documented the passes
it preserves. An assert at the end that checks that if the loop
wasn't completely unrolled that it's still isLCSSAForm would be a
good addition in any case.

>
>
> Additionally, after loop unrolling, the following check is made:
>  // Update the loop information for this loop.
>  // If we completely unrolled the loop, remove it from the parent.
>  if (L->getNumBackEdges() == 0)
>    LPM.deleteLoopFromQueue(L);
>
> This check probably needs to happen in every unroll pass that use  
> loopUnroll.
> We could move this check into the loopUnroll function, but that  
> requires
> passing in the LoopPassManager (LPM) to loopUnroll as well. Is that  
> wanted?

I don't think it's desirable to require a LoopPassManager object,
but I think it would be fine to have an optional LoopPassManager
parameter which can be null for this purpose. If a LoopPassManager
object is provided and the loop is completely unrolled, the
loop is removed from the LoopPassManager.

>
>
> Overall, I've really only moved code, so behaviour should be  
> unchanged. The
> only functional change I think I made, was that the old code checked  
> to see if
> the terminator instruction of the latch block was a conditional  
> branch first,
> before looking at the trip count and the treshold. Since that check  
> moved
> together with unrollLoop, it is done a bit later. However, AFAICS,  
> none of the
> code (getTripCount, code size estimation) actually depends on this  
> check, so it
> shouldn't change anything in the end.

Ok.

>
>
> Lastly, the (original comments) say "This pass will multi-block  
> loops only if they
> contain no non-unrolled subloops". I can't really find what this is  
> supposed to
> mean, in particular I can't find any explicit check for subloops  
> anywhere.
> Anyone know what this means?

I don't.

>
> I've also tried to minimize the includes required in both cpp files,  
> seems like
> there were quite some unused ones present.

Yep, it's not uncommon for unused includes to accumulate
as the code evolves. Thanks for cleaning that up.

>
>
> The new code seems to work on an adhoc test case, but there seems to  
> be a
> problem with one of the standard testcases. I'll solve that later  
> today. For
> now, please review the patch :-)

+  /// getSmallConstantTripCount - Returns the trip count of this loop  
as a
+  /// normal unsigned value, if possible. Returns 0 if the trip count  
is unknown
+  /// of not constant. Will also return 0 if the trip count is very  
large
+  /// (> 2^32)

This should say (>= 2^32).

+  inline unsigned getSmallConstantTripCount() const {
+    Value* TripCount = this->getTripCount();
+    if (TripCount) {
+      if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) {
+        // Guard against huge trip counts. This also guards against  
assertions in
+        // APInt from the use of getZExtValue, below.

This comment is a little stale now. Just say it guards against huge
trip counts.

+        if (TripCountC->getValue().getActiveBits() <= 32) {
+          return (unsigned)TripCountC->getZExtValue();
+        }
+      }
+    }
+    return 0;
+  }

+  /// getSmallConstantTripMultiple - Returns the largest constant  
divisor of the
+  /// trip count of this loop as a normal unsigned value, if  
possible. This
+  /// means that the actual trip count is always a multiple of the  
returned
+  /// value (don't forget it could very well be zero as well!).

I know you corrected this elsewhere, but this comment still says the
multiple could be zero.

+  /// Returns 1 if the trip count is unknown or not guaranteed to be  
the
+  /// multiple of a constant (which is also the case if the trip  
count is simply
+  /// constant, use getSmallConstantTripCount for that case), Will  
also return 1
+  /// if the trip count is very large (> 2^32).

I know you're just refactoring existing code, but as a standalone  
utility
getSmallConstantTripMultiple should really handle the case where the  
trip
count is constant. Eventually, it should be taught a few more operators
than just Mul too, such as Shl and And, but you don't need to worry
about that now.

And again >= instead of >.

--- include/llvm/Transforms/Utils/UnrollLoop.h  (revision 0)
+++ include/llvm/Transforms/Utils/UnrollLoop.h  (revision 0)

This file misses the comments that all LLVM headers have.

We may someday add more loop utilities, in which case we may want
to rename this header and add other stuff to it, but we can worry
about that when the need arrises. This is fine for now.

+bool unrollLoop(Loop *L, unsigned Count, LoopInfo* LI);

Please capitalize this to UnrollLoop. LLVM is a little inconsistent
about capitalization in some ways, but standalone transforming
utility functions are pretty consistently capitalized.

Thanks!

Dan