[LLVMdev] SCEV expression for ICmpInst

[ether zhhb]

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>