llvm dev - Jun 2017 - LoopSimplify pass prevents loop unrolling

On 6/30/2017 7:48 AM, Balaram Makam via llvm-dev wrote:
>
> Edit. Predecessor -> successor.
>
> *From:* llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] *On Behalf 
> Of *Balaram Makam via llvm-dev
> *Sent:* Friday, June 30, 2017 10:47 AM
> *To:* llvm-dev at lists.llvm.org
> *Subject:* [llvm-dev] LoopSimplify pass prevents loop unrolling
>
> Hi All,
>
> In the attached test case there, is an unnested loop with 2 
> iterations. The loop latch block is terminated by an unconditional 
> branch, so simplifycfg folds the almost empty latch block into its 
> *successor* which is the loop header. This results in an additional 
> backedge in the CFG, so when LoopRotate pass is called it 
> canonicalizes the loop into a nested loop. However, now the loop trip 
> count is unpredictable as the BackedgeTakenCount for the outer loop is 
> not loop invariant. As a result the loop cannot be unrolled. Is this 
> the intended canonicalization for this loop or is the loopsimplify 
> canonicalizing incorrectly? Should simplifycfg skip folding the latch 
> block into the loop header if this results in additional backedges and 
> let the empty blocks be folded during CGP? More details in 
> https://bugs.llvm.org/show_bug.cgi?id=33605.
>
We have code that's supposed to prevent this from happening; see 
https://reviews.llvm.org/rL264697 .  Maybe it also needs to check 
whether the destination of the branch is a loop header?

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/d9a33d10/attachment.html>

Thanks Eli,

 

I was looking at this code which keeps track of loop headers but is checking
if the destination of branch is a loop header sufficient? This prevents
merging empty preheaders into the loop headers as well. Is that reasonable
approach or do we need to skip only if the original unconditional branch was
a backedge and folding this branch might result in additional backedges? I
made a quick hack to find the function backedges and skip simplifycfg to
merge the latch block into the loop header when it results in an additional
backedge. Although it solves my purpose I am not sure if this the right
approach, as finding the backedges looks expensive. I also found a
regression with this patch where a huge switch statement with multiple empty
blocks have been skipped from merging resulting in bad code. Instead, should
loopsimplify try to unify multiple exit blocks and collapse multiple
backedges whenever possible instead of splitting it out into a nested loop?

 

-Balaram

From: Friedman, Eli [mailto:efriedma at codeaurora.org] 
Sent: Friday, June 30, 2017 1:59 PM
To: Balaram Makam <bmakam at codeaurora.org>; llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] LoopSimplify pass prevents loop unrolling

 

On 6/30/2017 7:48 AM, Balaram Makam via llvm-dev wrote:

Edit. Predecessor -> successor.

 

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Balaram
Makam via llvm-dev
Sent: Friday, June 30, 2017 10:47 AM
To: llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> 
Subject: [llvm-dev] LoopSimplify pass prevents loop unrolling

 

Hi All,

 

In the attached test case there, is an unnested loop with 2 iterations. The
loop latch block is terminated by an unconditional branch, so simplifycfg
folds the almost empty latch block into its successor which is the loop
header. This results in an additional backedge in the CFG, so when
LoopRotate pass is called it canonicalizes the loop into a nested loop.
However, now the loop trip count is unpredictable as the BackedgeTakenCount
for the outer loop is not loop invariant. As a result the loop cannot be
unrolled. Is this the intended canonicalization for this loop or is the
loopsimplify canonicalizing incorrectly? Should simplifycfg skip folding the
latch block into the loop header if this results in additional backedges and
let the empty blocks be folded during CGP? More details in
https://bugs.llvm.org/show_bug.cgi?id=33605.

 


We have code that's supposed to prevent this from happening; see
<https://reviews.llvm.org/rL264697> https://reviews.llvm.org/rL264697 .
Maybe it also needs to check whether the destination of the branch is a loop
header?

-Eli 

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/d05ff162/attachment.html>

On 6/30/2017 11:38 AM, Balaram Makam wrote:
>
> Thanks Eli,
>
> I was looking at this code which keeps track of loop headers but is 
> checking if the destination of branch is a loop header sufficient? 
> This prevents merging empty preheaders into the loop headers as well.
>
There isn't really any reason to collapse preheaders anyway; 
LoopSimplify will recreate them, and they don't really block other 
optimizations as far as I know.
> Is that reasonable approach or do we need to skip only if the original 
> unconditional branch was a backedge and folding this branch might 
> result in additional backedges? I made a quick hack to find the 
> function backedges and skip simplifycfg to merge the latch block into 
> the loop header when it results in an additional backedge. Although it 
> solves my purpose I am not sure if this the right approach, as finding 
> the backedges looks expensive.
>
Well, not that expensive to calculate if you cache it, but probably 
tricky to keep the cache up-to-date, yes.
> I also found a regression with this patch where a huge switch 
> statement with multiple empty blocks have been skipped from merging 
> resulting in bad code. Instead, should loopsimplify try to unify 
> multiple exit blocks and collapse multiple backedges whenever possible 
> instead of splitting it out into a nested loop?
>
I'm not sure I follow the issue here.  Could you give an example?

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/ddaa931d/attachment.html>