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

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