llvm dev - Apr 2010 - [LLVMdev] SCEV expression for ICmpInst

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 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?

any comment is appreciated.

--best regards
ether
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100417/78cb10aa/attachment.html>

On Sat, Apr 17, 2010 at 10:17 PM, ether zhhb <etherzhhb at gmail.com>
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 :)
>
oh, by the way, it seems that llvm neither optimize

(2 * a + 5 * c + 2) > (4 * d - 3*b +3 + 2 * a)

to

(5 * c + 2) > (4 * d - 3*b + 3)

nor

(5 * c) > (4 * d - 3*b + 1)

This kind of optimization maybe preform by SCEV for integer conditions ;)

here is the original c source code:

int f(int a, int b, int c, int d) {
  return (2 * a + 5 * c + 2) > (4 * d - 3*b +3 + 2 * a);
}

and here is the .ll file generate from the online demo (
http://llvm.org/demo/index.cgi):

define i32 @f(i32 %a, i32 %b, i32 %c, i32 %d) nounwind readnone {
entry:
  %0 = shl i32 %a, 1                              ; <i32> [#uses=2] <-
this is 2 * a, used twice
  %1 = mul i32 %c, 5                              ; <i32> [#uses=1]
  %2 = add nsw i32 %0, 2                          ; <i32> [#uses=1]
  %3 = add nsw i32 %2, %1                         ; <i32> [#uses=1] <-
2 * a used here for the left hand side expression
  %4 = shl i32 %d, 2                              ; <i32> [#uses=1]
  %5 = mul i32 %b, 3                              ; <i32> [#uses=1]
  %6 = add i32 %0, 3                              ; <i32> [#uses=1] <-
2 * a used here for the right hand side expression
  %7 = sub i32 %6, %5                             ; <i32> [#uses=1]
  %8 = add nsw i32 %7, %4                         ; <i32> [#uses=1]
  %9 = icmp sgt i32 %3, %8                        ; <i1> [#uses=1]
  %10 = zext i1 %9 to i32                         ; <i32> [#uses=1]
  ret i32 %10
}


>
> 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 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?
>
> any comment is appreciated.
>
> --best regards
> ether
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100417/427e27f2/attachment.html>

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