llvm dev - Dec 2020 - LoopDeletion / removal of empty loops.

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) 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

Hi Jonas,

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. 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.

Atmn

On Sat, Dec 19, 2020, 3:12 PM Jonas Paulsson via llvm-dev <
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) 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
> 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/20201219/045fe463/attachment.html>

Hi Jonas,
> On Dec 19, 2020, at 20:11, Jonas Paulsson via llvm-dev <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) 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?

Thanks for sharing this case! I am also looking into this, as we are seeing
similar differences on other platforms.

Atmn’s patch gets us a little closer by lifting the restriction you mentioned.
But there are a few other problems to tackle, including allowing deletion of
loops with sub-loops (https://reviews.llvm.org/D93716
<https://reviews.llvm.org/D93716>) and changes to hoist a loop-invariant
condition out the the loop (currently it appears LLVM fails to determine that
the location the condition value is loaded from does not alias any operations in
the loop).

Cheers,
Florian 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201222/d7dd5f5a/attachment-0001.html>