llvm dev - Apr 2021 - Question about Traversing Loops in forward or reverse program order on new pass manager

Ping on loop traversal order. Does anybody have any intuition about which
way to traverse loops in a function?

On Wed, Apr 7, 2021 at 12:36 PM Jingu Kang via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi All,
>
>
>
> I have seen performance regressions from new pass manager against legacy
> pass manager. One of the issues is the order of populating loops on pass
> manager. The legacy pass manager is traversing loops in reverse program
> order but the new pass manager is traversing in forward program order. It
> sometimes causes different output. I have created a review
> https://reviews.llvm.org/D99774 for reverse program order on new pass
> manager and had short discussion with Arthur on it. It is not easy to say
> the reverse order is better than the forward one or vice versa. I would
> like to share this issue with more people on llvm-dev. If you have idea or
> experience about this issue, please share it.
>
>
>
> Thanks
>
> JinGu Kang
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210415/4a609f99/attachment-0001.html>

I think the traversal order may depend on the optimization.  I would actually
propose to get rid of those fine-grained pass managers altogether.  I think they
are abstractions taken too far, to the point of being counter-productive. 
Instead, loop passes should visit a function at a time, and use utility
functions (like iterators of various kinds) to visit loops in the order they
want.

On the actual issue here, I think we should stick to the old traversal order for
the time being.  This would reduce the potential for regressions and make it
easier to fully transition to the NPM for everyone.

--
Krzysztof Parzyszek  kparzysz at quicinc.com<mailto:kparzysz at
quicinc.com>   AI tools development

From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Arthur
Eubanks via llvm-dev
Sent: Thursday, April 15, 2021 11:59 AM
To: Jingu Kang <Jingu.Kang at arm.com>
Cc: llvm-dev at lists.llvm.org
Subject: [EXT] Re: [llvm-dev] Question about Traversing Loops in forward or
reverse program order on new pass manager

Ping on loop traversal order. Does anybody have any intuition about which way to
traverse loops in a function?

On Wed, Apr 7, 2021 at 12:36 PM Jingu Kang via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hi All,

I have seen performance regressions from new pass manager against legacy pass
manager. One of the issues is the order of populating loops on pass manager. The
legacy pass manager is traversing loops in reverse program order but the new
pass manager is traversing in forward program order. It sometimes causes
different output. I have created a review https://reviews.llvm.org/D99774 for
reverse program order on new pass manager and had short discussion with Arthur
on it. It is not easy to say the reverse order is better than the forward one or
vice versa. I would like to share this issue with more people on llvm-dev. If
you have idea or experience about this issue, please share it.

Thanks
JinGu Kang
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210415/68315f34/attachment.html>

I know of no reason to have a strong preference.  Assuming the change 
wasn't made intentionally - might be good to check with Chandler - I'd 
default to using the same order from the old pass manager.

One argument in favor of the forward order is that if determine a loop 
exit is dead, we might be able to avoid visiting a large portion of the 
function.  Just an observation, not an argument in favor per se.

Philip

On 4/15/21 9:59 AM, Arthur Eubanks via llvm-dev wrote:
> Ping on loop traversal order. Does anybody have any intuition about 
> which way to traverse loops in a function?
>
> On Wed, Apr 7, 2021 at 12:36 PM Jingu Kang via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>
>     Hi All,
>
>     I have seen performance regressions from new pass manager against
>     legacy pass manager. One of the issues is the order of populating
>     loops on pass manager. The legacy pass manager is traversing loops
>     in reverse program order but the new pass manager is traversing in
>     forward program order. It sometimes causes different output. I
>     have created a review https://reviews.llvm.org/D99774
>     <https://reviews.llvm.org/D99774> for reverse program order on
new
>     pass manager and had short discussion with Arthur on it. It is not
>     easy to say the reverse order is better than the forward one or
>     vice versa. I would like to share this issue with more people on
>     llvm-dev. If you have idea or experience about this issue, please
>     share it.
>
>     Thanks
>
>     JinGu Kang
>
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     <https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210416/3006eadf/attachment.html>