[llvm-dev] LoopDeletion / removal of empty loops.

[Jonas Paulsson via llvm-dev]

Hi Atmn,


> We've also had this discussion about removing dead loops, and we've 
> introduced two attributes based on which LoopDeletion should know 
> whether or not to remove C/C++ loops. The final patch that modifies 
> LoopDeletion is under review at https://reviews.llvm.org/D86844 
> <https://reviews.llvm.org/D86844>. I still haven't had time to 
> properly address the errors in this patch (it was failing a two stage 
> build), but I hope to get back to it at some point over the next few 
> weeks.
>
Nice - this was just what I was looking for :-)

I tried it on my test case but to my surprise it did not handle it. It 
seems like it has a condition that actually cannot be hoisted out of the 
loop, so loop unswitching cannot get to work and produce the empty loop.

However, while the condition is not loop-invariant in the entire loop, 
it is in fact constant if it the first time enters the dead path of the 
loop. In other words, the loop has a check inside the loop that may 
simply skip the significant part of the loop by jumping directly from 
the header to the latch. If it does so, it can do an early exit instead 
if there is a forward progress guarantee, I would hope.

I have experimented with a patch for this: 
https://reviews.llvm.org/D93734, please take a look.

Thanks,

Jonas


> Atmn
>
> On Sat, Dec 19, 2020, 3:12 PM Jonas Paulsson via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
>     Hi,
>
>     It seems that omnetpp runs ~10% faster with gcc than with clang on
>     SystemZ. This is due to the small function printAddressTable which
>     contains a loop with a single statement. It is run in "express-mode",
>     which means that the function will contain mainly an empty loop,
>     which
>     GCC removes (or at least makes an early exit) while clang emits
>     the loop
>     to be iterated over.
>
>     The loop is iterating with an std::iterator over an std::map. GCC has
>     recently changed behavior to remove most (but not intentional ones)
>     empty loops, and I wonder if clang should do the same? There was a
>     discussion in the GCC community
>     (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89713
>     <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89713>) which
>     resulted in
>     this change to assume that loops are finite based on the "forward
>     progress guarantee" of the standard, IIUC.
>
>     For instance, this function:
>
>     #include <map>
>     void fun(std::map<int, int> &M) {
>        for (std::map<int, int>::iterator I = M.begin(); I != M.end(); I++)
>          ;
>     }
>
>     will result in an empty function by GCC, while clang generates the
>     empty
>     loop to be iterated over.
>
>     I see a comment in LoopDeletion.cpp:
>
>     /// A loop is considered dead if it does not impact the observable
>     behavior of
>     /// the program other than finite running time. This never removes a
>     loop that
>     /// might be infinite (unless it is never executed), as doing so
>     could
>     change
>     /// the halting/non-halting nature of a program.
>
>     This loop does pass the isLoopDead() check in
>     LoopDeletion.cpp:204, but
>     the loop is not deleted since ScalarEvolution cannot resolve the trip
>     count.
>
>     This is of course very important for performance in general and in
>     particular for the profits of loop unswitching and other passes
>     producing empty loops. So I wonder if it is the case that we could
>     start
>     doing this as well in llvm?
>
>     /Jonas
>
>
>     _______________________________________________
>     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>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201222/eb8a4885/attachment.html>