Fwd: Re: [LLVMdev] Handling of pointer difference in llvm-gcc and clang

[Florian Merz <florian dot merz at kit dot edu>]

Dear gcc developers,

this is about an issue that popped up in a verification project [1] based on 
LLVM, but it seems to be already present in the gimple code, before llvm-gcc 
transforms the gimple code to LLVM-IR.

In short:
Calculating the difference of two pointers seems to be treated by gcc as a 
signed integer subtraction. While the result should be of type ptrdiff_t and 
therefore signed, we believe the subtraction itself should not be signed.

Signed subtraction might overflow if a large positive number is subtracted from 
a large negative number. So subtracting for example from the pointer value 
0x80...0 (a large negative signed integer) the pointer value 0x7F...F (a large 
positive signed integer) should in theory be perfectly fine, but trating this 
as a signed subtraction causes an overflow and therefore undefined behaviour.

Can someone explain why this is treated as a signed subtraction?

Thanks a lot and regards,
 Florian

P.S: It seems like clang does not treat this subtraction as signed.

[1] http://baldur.iti.kit.edu/llbmc/

----------  Weitergeleitete Nachricht  ----------

Betreff: Re: [LLVMdev] Handling of pointer difference in llvm-gcc and clang
Datum: Wednesday, 10. August 2011, 19:12:43
Von: Jack Howarth <howarth@bromo.med.uc.edu>
An: Duncan Sands <baldrick@free.fr>
Kopie: llvmdev@cs.uiuc.edu

On Wed, Aug 10, 2011 at 06:13:16PM +0200, Duncan Sands wrote:
> Hi Stephan,
> 
> > We are developing a bounded model checker for C/C++ programs
> > (http://baldur.iti.kit.edu/llbmc/) that operates on LLVM's intermediate
> > representation.  While checking a C++ program that uses STL containers
> > we noticed that llvm-gcc and clang handle pointer differences in
> > disagreeing ways.
> >
> > Consider the following C function:
> > int f(int *p, int *q)
> > {
> >       return q - p;
> > }
> >
> > Here's the LLVM code generated by llvm-gcc (2.9):
> > define i32 @f(i32* %p, i32* %q) nounwind readnone {
> > entry:
> >     %0 = ptrtoint i32* %q to i32
> >     %1 = ptrtoint i32* %p to i32
> >     %2 = sub nsw i32 %0, %1
> >     %3 = ashr exact i32 %2, 2
> >     ret i32 %3
> > }
> >
> > And here is what clang (2.9) produces:
> > define i32 @f(i32* %p, i32* %q) nounwind readnone {
> >     %1 = ptrtoint i32* %q to i32
> >     %2 = ptrtoint i32* %p to i32
> >     %3 = sub i32 %1, %2
> >     %4 = ashr exact i32 %3, 2
> >     ret i32 %4
> > }
> >
> > Thus, llvm-gcc added the nsw flag to the sub, whereas clang didn't.
> >
> > We think that clang is right and llvm-gcc is wrong:  it could be the
> > case that p and q point into the same array, that q is 0x80000000, and
> > that p is 0x7FFFFFFE.  Then the sub results in a signed overflow, i.e.,
> > sub with nsw is a trap value.
> >
> > Is this a bug in llvm-gcc?
> 
> in llvm-gcc (and dragonegg) this is coming directly from GCC's gimple:
> 
> f (int * p, int * q)
> {
>    long int D.2718;
>    long int D.2717;
>    long int p.1;
>    long int q.0;
>    int D.2714;
> 
> <bb 2>:
>    q.0_2 = (long int) q_1(D);
>    p.1_4 = (long int) p_3(D);
>    D.2717_5 = q.0_2 - p.1_4;
>    D.2718_6 = D.2717_5 /[ex] 4;
>    D.2714_7 = (int) D.2718_6;
>    return D.2714_7;
> 
> }
> 
> Signed overflow in the difference of two long int (ptrdiff_t) values results in
> undefined behaviour according to the GCC type system, which is where the nsw
> flag comes from.
> 
> The C front-end generates this gimple in the pointer_diff routine.  The above 
is
> basically a direct transcription of what pointer_diff does.
> 
> In short, I don't know if this is right or wrong; but if it is wrong it 
seems
> to be a bug in GCC's C frontend.

Shouldn't we cc this over to the gcc mailing list for clarification then?
             Jack

> 
> Ciao, Duncan.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev@cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------------------------------------------------------