llvm dev - Dec 2008 - [LLVMdev] scalar-evolution + indvars fail to get the loop trip count?

>
>
> Having the final .ll file doesn't help debug this. If you run opt 
> -analyze -scalar-evolution on the .ll you pasted, it will correctly 
> print out the loop trip count.
>
> I've modified llvm-gcc to remove all the passes after indvars.
>
>   
I updated my llvm and now it works.
>> > Surely the loop trip count is 256, but the Loop::getTripCount()
will
>> > return NULL.
>> > This is due to the exit condition: 
>> > 
>> > %tmp16 = icmp slt i32 %tmp13, 0         ; <i1> [#uses=1]
>> > 
>> > pass indvars should transform it into a canonical exit condtion EQ
or
>> > NE, but as scalarevolution returned NonComputedItCount, it failed
to do
>> > that.
>> > 
>> > In pass ScalarEvolution three algorithms failed to compute the
trip count:
>> > 
>> > 1. In SCEVAddRecExpr::getNumIterationsInRange(), as the loop
stride is
>> > negative, the exit value expression will be zero: (Here A is the
stride
>> > value)
>> > 
>> >         // The exit value should be (End+A)/A.
>> >       APInt ExitVal = (End + A).udiv(A);
>> >       ConstantInt *ExitValue = ConstantInt::get(ExitVal);        
>>     
>
> Yes, that code path will fail for this example.
>   
Why not improve this? We can change it into :

APInt ExitVal = (End + A).sdiv(A);

Surely we should take care of the range of this expression, maybe need extend
the bitwidth of (End+A)


>   
>> > 2. In Line 1953,   the switch-case computes the trip count due to 
>> > different Cond code.
>> >     But in this case, as it exits on true, the slt is converted to
sge,
>> > not switch-case for this condtion.
>>     
>
> Not sure what you mean. The problem is that HowManyLessThans was 
> refusing to work on a signed less-than or equal to, even in the trivial 
> case (just because I haven't yet gotten around to working on the
complex
> case of a non-unit stride).
>
>   
Make sense.
>> > 3. As the loop count is over 100, the Brute-Force algorithm also
doent work
>> > 
>> > Can we improve this?
>>     
>
> Done. Committed in r60748.
>   
Thanks for your quick work, Nick :-)

On Tue, Dec 9, 2008 at 1:43 AM, Sheng Zhou <zhousheng at autoesl.com>
wrote:
>> Yes, that code path will fail for this example.
>>
> Why not improve this? We can change it into :
>
> APInt ExitVal = (End + A).sdiv(A);
>
> Surely we should take care of the range of this expression, maybe need
extend the bitwidth of (End+A)
That's not quite correct for cases where End is positive.  I'm pretty
sure the correct way to deal with this is that if A is less than zero,
it should negate both End and A.

-Eli