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

[Sheng Zhou]

>
>
> 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 :-)