Noticed via code inspection. We changed the semantics of the IR when we added mustprogress, and we appear to have not updated this location.
Details
Details
Diff Detail
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
Comment Actions
Hi @reames,
We've seen some regressions after this patch, with SCEV not being able to calculate the backedge taken counts for a loop.
Although I guess the idea here is to make the code more restrictive in some way (so maybe that should be expected).
One thing that might cause problems here is that it seems like getting the MustProgress attribute on a Function is quite hard. It is basically inferred by having WillReturn on the Function, and afaict the WillReturn attribute is never inferred if the Functions contain loops.
In the godbolt example above the Function has no MustProgress attribute, however the loop has a MustProgress attribute. So maybe loopIsFiniteByAssumption should check if the loop has MustProgress as well?
That wouldn't however help for the regressions we see downstream, because we do not get any MustProgress attributes on the loops either in that case. No idea why really, but I figure those depend on the C-standard in some way. But aren't the loops in my example finite? So why is MustProgress attributes important here?
Comment Actions
Yes, it should be checking hasMustProgress(L) as well.
That wouldn't however help for the regressions we see downstream, because we do not get any MustProgress attributes on the loops either in that case. No idea why really, but I figure those depend on the C-standard in some way. But aren't the loops in my example finite? So why is MustProgress attributes important here?
Consider your example with n = 1:
long foo(long A[]) {
long x = 0;
for (long j = 0; j < 1; ++j)
for (long i = j; i < 1; i += 1/2)
x += A[i];
return x;
}Note that thus j == 0, and 1/2 == 0:
long foo(long A[]) {
long x = 0;
for (long i = 0; i < 1; i += 0)
x += A[i];
return x;
}This is an infinite loop.
Comment Actions
Sorry, I used wrong example in the link. I've changed it to something where I do "i += n" instead of "i += n/2".
Is perhaps the problem that "i += n" might overflow (UB) and thereby we can't guarantee "must progress"?
Comment Actions
For the updated example it should be technically fine, but SCEV is not strong enough to figure out that n != 0 at that point. Possibly performing an additional isLoopEntryGuardedByCond() check for != 0 would help.
Comment Actions
JFYI, C and C++ apparently have different rules here. For c++ your example function is mustprogress, for C only the loop is. (Based on a quick skim of checkIfLoopMustProgress clang's CodeGenFunction.h) I have no idea if the C rules could be more aggressive here or not, you'd be best taking that up with a clang developer.
It does look like checking the loop mustprogress flag would be sufficient to address the specific regression seen here. I'll see if that's easy to implement quickly.
For the weakness being discussed, feel free to file a bug. I'm currently working through a collection of missing cases in SCEV's trip count logic and having an example to come back to would help.
Comment Actions
Thanks a lot for all the follow up on the problem I had noticed!
Seems like clang won't add the mustprogress attribute to loops when using C99, so I think we would need to use -ffinite-loops to get any help from aaaeb4b16.
After examining a bunch of application code I found two cases for which vectorization disappeared when adding this patch, and another case when hwloop analysis failed to derive the trip count by using SCEV.
I will however try D104066 , which looks a bit more promising to avoid the regressions I've seen with C99.
(I'll make sure to write some PR:s if something remains also when having applied D104066.)