[LLVMdev] scalar-evolution + indvars fail to get the loop trip count?
zhousheng at autoesl.com
Tue Dec 9 03:43:39 CST 2008
> 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).
>> > 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 :-)
More information about the LLVMdev