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

Hi Jonas,

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

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: , please take a look.

Thanks,

Jonas