[LLVMdev] SCEV expression for ICmpInst

[Dan Gohman]

On Apr 17, 2010, at 7:17 AM, ether zhhb wrote:

> Hi,
>
> i am playing the ScalarEvolution these days. i found the the  
> ScalarEvolution will simply return a SCEVUnknow for a ICmpInst, so i  
> think maybe great to add a new kind of SCEV to the ScalarEvolution  
> framework.
>
>
> for example, if i run  ScalarEvolution on the bc file generate from  
> the following C source file:
>
> int f(int a, int b, int c, int d) {
>     return (2 * a + 5 * c + 2) > (4 * d - 3*b +3);
> }
>
> i will get a SCEVUnknow for the compare instruction, but it's great  
> if i could get something like 2 * a + 5 * c - 4 * d - 3*b - 1 > 0  
> for the compare instruction :)
>
>
> In my opinion, we need only 3 kind of SCEV expression to express the  
> ICmpInst: SCEVEqCond for equal condition,  SCEVNeCond for not equal  
> condition and SCEVGtCond for others. Because we can always transform  
> A < B to B > A, and transform A >= B to A > B - 1 (or A + 1> B), and  
> A <= B to A < B + 1 (or A - 1 < B). Furthermore, we can transform A  
> > B to A - B > 0 and A != B to A - B != 0, so the SCEV for  
> conditions will be very simple.

As was already pointed out, several of these replacement are not valid  
due to
overflow conditions.  LLVM now has flags to track when addition  
overflow can
be considered undefined, and this makes more things possible, though not
everything, and it still requires careful overflow-aware reasoning.

>
> As there are already some functions such as "isKnownNonZero" in  
> ScalarEvolution, so we can compute these condition easily.
>
> With the SCEV for conditions, we may write more meaningful code:
>
> SCEVEQCond *S = SE.getCondition(some_icmp_instruction);
>
> if (some_cond.isAlwaysTrue(SE))
>   ... do some thing ...
> else
>   ... do some others thing ...
>
> Dose this make sense? or i just make things unnecessarily complex?

I think it's unnecessarily complex :-).

If you want to simplify ICmp instructions, you can just call getSCEV  
on both of the
ICmp's operands and go from there.  If you're writing a lot of code to  
do this, factoring
it out into utility routines would be natural.  I don't think an ICmp  
expression would be
significantly more useful, because I expect all you'd do with it is  
just grab the
operands.

Dan