analyze <= and >= loops

[llvmbot]

Bugzilla Link	3328
Resolution	FIXED
Resolved on	May 03, 2010 09:50
Version	trunk
OS	All
Reporter	LLVM Bugzilla Contributor
CC	@sunfishcode,@nlewycky

Extended Description

#include <stdio.h>
#include <stdlib.h>
//
int TESTE ( int parami ,int paraml )
{
int varx=0;
int nI =0;

if( parami > 0 )
{
varx = parami;
}
else
{
varx = 1;
}

for( nI = 1 ; nI <= paraml; nI++) //here
{
varx = varx + parami+ 1;
}

return varx ;
}

int main(int argc, char **argv)
{
if( argc < 3 )
return 0;
return TESTE(atoi(argv[1]),atoi(argv[2]));
}

LLVM should eliminate the loop and do a direct calculation instead.
The MSVC is great in this example and gcc-4.3 also eliminates the loop entirely and directly calculates the value of varx.
It looks like LLVM's scalar evolution code isn't handling your testcase well.

[lattner]

There is no way for llvm to handle this currently. <= loops are evil (and you should not use them, use != or < instead) because they can be infinite loops if the RHS of the compare is MAXINT. GCC is able to handle this because it keeps track of the difference between signed and unsigned integer operations (the former are undefined on overflow) and uses this for trip count analysis. LLVM will need to keep track of the fact that an add is an "undefined on signed overflow" add instead of a "wraps with 2's complement arithmetic add".

[lattner]

We have NSW now, but we're apparently losing it in indvars, so we still miss this optimization

[sunfishcode]

The missing piece here is logic to handle >= and <= trip counts, which before NSW was prohibitively difficult, and so was never implemented. Now it should be fairly straight-forward.

[sunfishcode]

*** Bug llvm/llvm-bugzilla-archive#5256 has been marked as a duplicate of this bug. ***

[sunfishcode]

This is now fixed on trunk.

[sunfishcode]

mentioned in issue llvm/llvm-bugzilla-archive#5256