llvm dev - Nov 2012 - [LLVMdev] ScalarEvolution, HowManyLessThans question for step > 1

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

 

--

Qualcomm Innovation Center, Inc is a member of Code Aurora Forum, hosted by
The Linux Foundation

 

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

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>