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

[Matthijs Kooijman]

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?

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?

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.

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've also tried to minimize the includes required in both cpp files, seems like
there were quite some unused ones present.

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 :-)

Gr.

Matthijs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: unroll-split.diff
Type: text/x-diff
Size: 31752 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080509/2312c080/attachment.diff>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080509/2312c080/attachment.sig>