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

Be careful about oversimplifying signed integer comparisons -- integer
arithmetic can easily overflow, so you cannot transform A > B to A - B >
0.  The compare instructions in most processors do not simply subtract and test
the most significant bit; they compute what the sign of the difference would be
in extended precision.

On Apr 17, 2010, at 1:00 PM, llvmdev-request at cs.uiuc.edu wrote:
> Message: 13
> Date: Sat, 17 Apr 2010 22:17:54 +0800
> From: ether zhhb <etherzhhb at gmail.com>
> Subject: [LLVMdev] SCEV expression for ICmpInst
> To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
> Message-ID:
> 	<s2w5f72161f1004170717re1325ffdr53b6b7308215b3fa at mail.gmail.com>
> Content-Type: text/plain; charset="iso-8859-1"
> 
> 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

hi Jud,

thanks very much for this. i completely forgot the overflow stuff ... so
turn the compare instruction to subtract is a bad idea.

--best regards
ether

On Sun, Apr 18, 2010 at 2:35 AM, Jud Leonard <jud.leonard at gmail.com>
wrote:
> Be careful about oversimplifying signed integer comparisons -- integer
> arithmetic can easily overflow, so you cannot transform A > B to A - B
> 0.
>  The compare instructions in most processors do not simply subtract and
test
> the most significant bit; they compute what the sign of the difference
would
> be in extended precision.
>
> On Apr 17, 2010, at 1:00 PM, llvmdev-request at cs.uiuc.edu wrote:
>
> > Message: 13
> > Date: Sat, 17 Apr 2010 22:17:54 +0800
> > From: ether zhhb <etherzhhb at gmail.com>
> > Subject: [LLVMdev] SCEV expression for ICmpInst
> > To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
> > Message-ID:
> >       <s2w5f72161f1004170717re1325ffdr53b6b7308215b3fa at
mail.gmail.com>
> > Content-Type: text/plain; charset="iso-8859-1"
> >
> > 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
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100418/fee1285f/attachment.html>