On Thu, Aug 11, 2011 at 6:05 PM, Florian Merz <florian.m...@kit.edu> wrote: > Thanks for your reply Richard, but I'm not satisfied with your answer, yet. > :-) > If I'm right, then the problem I'm refering to doesn't require large objects. > > See below for more. > > Am Thursday, 11. August 2011, 17:48:26 schrieb Richard Guenther: >> On Thu, Aug 11, 2011 at 5:15 PM, Florian Merz <florian.m...@kit.edu> wrote: >> > 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? >> >> GCC restricts objects to the size of half of the address-space thus >> a valid pointer subtraction in C cannot overflow. > > Consider an array containing 8 bytes starting at 0x7FFFFFFC. This array would > go up to one less than 0x80000004. > > If I remember the standard correctly, pointer subtraction is valid if both > pointers point to elements of the same array or to one past the last element > of the array. According to this 0x80000000 - 0x7FFFFFFF should be a valid > pointer subtraction with the result 0x00000001. > > But if the subtraction is treated as a signed, this would be an signed integer > overflow, as we subtract INT_MAX from INT_MIN, which surely must overflow, and > the result therefore would be undefined.
int x,y; int main () { char *a, *b; __INTPTR_TYPE__ w; if (x) a = 0x7ffffffe; else a = 0x7fffffff; if (y) b = 0x80000001; else b = 0x80000000; w = b - a; return w; } indeed traps with -ftrapv for me which suggests you are right. Joseph? Richard. >> Richard. >> >> > 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 <howa...@bromo.med.uc.edu> >> > An: Duncan Sands <baldr...@free.fr> >> > Kopie: llvm...@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. >