llvm dev - Jul 2017 - LoopSimplify pass prevents loop unrolling

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>

I will try to reduce a test case for the regression I found and will update.

 

Thanks,

Balaram

 

From: Friedman, Eli [mailto:efriedma at codeaurora.org] 
Sent: Friday, June 30, 2017 2:54 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 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?



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

Sorry for long trip time on this. The issue I was seeing when we defer
simplifying unconditional branches to later passes in backend was due to a
heuristic in CGP:: isMergingEmptyBlockProfitable where we assumed cost of
branch is same as cost of copy. However, if the destination block is almost
empty latch block, then we can hoist the jump through the backedge, so it is
profitable to eliminate the branch. I have posted a patch for review here:
https://reviews.llvm.org/D35411.

Please take a look and let me know your comments/suggestions.

 

Thanks,

Balaram

 

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Balaram
Makam via llvm-dev
Sent: Friday, June 30, 2017 3:11 PM
To: 'Friedman, Eli' <efriedma at codeaurora.org>; llvm-dev at
lists.llvm.org
Subject: Re: [llvm-dev] LoopSimplify pass prevents loop unrolling

 

I will try to reduce a test case for the regression I found and will update.

 

Thanks,

Balaram

 

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

 

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?

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