Re: Inefficient loop unrolling.

["Richard Guenther" <richard dot guenther at gmail dot com>]

On Wed, Jul 2, 2008 at 1:13 PM, Bingfeng Mei <bmei@broadcom.com> wrote:
> Hello,
> I am looking at GCC's loop unrolling and find it quite inefficient
> compared with manually unrolled loop even for very simple loop. The
> followings are a simple loop and its manually unrolled version. I didn't
> apply any trick on manually unrolled one as it is exact replications of
> original loop body. I have expected by -funroll-loops the first version
> should produce code of similar quality as the second one. However,
> compiled with ARM target of mainline GCC, both functions produce very
> different results.
>
> GCC-unrolled version mainly suffers from two issues. First, the
> load/store offsets are registers. Extra ADD instructions are needed to
> increase offset over iteration. In the contrast, manually unrolled code
> makes use of immediate offset efficiently and only need one ADD to
> adjust base register in the end. Second, the alias (dependence) analysis
> is over conservative. The LOAD instruction of next unrolled iteration
> cannot be moved beyond previous STORE instruction even they are clearly
> not aliased. I suspect the failure of alias analysis is related to the
> first issue of handling base and offset address. The .sched2 file shows
> that the first loop body requires 57 cycles whereas the second one takes
> 50 cycles for arm9 (56 cycles vs 34 cycles for Xscale).  It become even
> worse for our VLIW porting due to longer latency of MUL and Load
> instructions and incapability of filling all slots (120 cycles vs. 20
> cycles)
>
> By analyzing compilation phases, I believe if the loop unrolling happens
> at the tree-level, or if we have an optimizing pass like "ivopts" after
> loop unrolling in RTL level, GCC can produce far more efficient
> loop-unrolled code.  "ivopts" pass really does a wonderful job in
> optimizing induction variables. Strangely, I found some unrolling
> functions at tree-level, but there is no independent tree-level loop
> unrolling pass except "cunroll", which is complete unrolling.  What
> prevents such a tree-level unrolling pass? Or is there any suggestion to
> improve existing RTL level unrolling? Thanks in advance.

On the tree level only complete unrolling is done.  The reason for this
was the difficulty (or our unwillingness) to properly tune this for the
target (loop unrolling is not a generally profitable optimization, unless
complete unrolling for small loops).

I would suggest to look into doing also partial unrolling on the tree level.

Richard.