[LLVMdev] ScalarEvolution, HowManyLessThans question for step > 1

[Andrew Trick]

On Nov 16, 2012, at 10:56 AM, Brendon Cahoon <bcahoon at codeaurora.org> wrote:

> Hi,
>  
> I have a question about some code in ScalarEvolution.cpp, in the function HowManyLessThans.  Specifically, this function returns CouldNotCompute if the iteration step is greater than one even when the NoWrap flags are set (if the step goes past the limit and wraps).    Here’s the comment:
>  
>    } else if (isKnownPositive(Step)) {
>       // Test whether a positive iteration can step past the limit
>       // value and past the maximum value for its type in a single step.
>       // Note that it's not sufficient to check NoWrap here, because even
>       // though the value after a wrap is undefined, it's not undefined
>       // behavior, so if wrap does occur, the loop could either terminate or
>       // loop infinitely, but in either case, the loop is guaranteed to
>       // iterate at least until the iteration where the wrapping occurs.
>      
> I have no doubt that there is a good reason for this code to work this way (there is a specific check in trip-count9.ll).  I’m just trying to understand it better.  I’m assuming that when the previous version of this code checked the NoWrap flag, that it caused a problem with some optimization pass?  If so, does anyone recall the pass.
>  
> I’m also curious if the –f[no]-strict-overflow flag has any impact on the assumptions?  Or, could the function check NoWrap for the unsigned case only?
>  
> The motivating example for this question occurs because we’re not unrolling loops with a run-time trip count when the loop induction variable is a pointer and the loop end check is another pointer.  For example,
>  
>   void ex( int n, int* a, int* c ) {
>    int b  = 1; int *ae = a + n;
>     while ( a < ae) {
>       c ++; b += *c; *a++ = b;
>     }
>   }
>  
> Thanks,
> Brendon

Someone pointed me to this message that lacked a response. Sorry for not reading llvmdev that week in the distant past, but for the record...

‘a’ can exceed ‘ae’ without undefined behavior if the pointers were somehow misaligned. Then hypothetically ‘a’ can step off the end of the address space (unsigned wrap).

The key to understanding the problem is that SCEV NoWrap flag guarantees that ‘a’ can never surpass its original value, regardless of signed or unsigned wrapping. It’s doesn’t mean that signed/unsigned wrap can’t occur.

SCEV’s thinking here is that the loop may continue to iterate at this point, modifying program state in some valid way, then later terminate via some other mechanism. Then there’s the whole issue of what undefined behavior means in LLVM. Are we beholden to execute all well-defined loop iterations even if we can prove that undefined behavior will eventually occur?

What SCEV doesn’t realize is: comparing a < ae is already undefined if ‘a’ just unsigned-wrapped since it’s a pointer comparison and the step was positive (pointers unsigned-wrap all the time with negative steps). It also can’t see that dereferencing ‘a’ would result in undefined behavior if a positive step led to unsigned wrap (I guess I’m assuming that a single object can’t span more than half the address space).

SCEV also has no way to communicate to a client, like unrolling, that if the loop test is the only possible way for the loop to terminate in a well-defined way, then the trip count can be guaranteed.

So, I *do* think we could handle this case. But to do it we need to either add intelligence to SCEV (which is tricky to reason about) or add some knowledge about the whole loop when asking for the trip count (which is tricky to engineer).

It wouldn’t hurt to file a bug. I don’t see a lot of people hacking on SCEV, but you never know.

-Andy

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130722/f3584bf1/attachment.html>