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 :slight_smile:

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

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 :slight_smile:

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 :wink:

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
}

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 :slight_smile:

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