pointer arithmetics and casts

pointer arithmetics and casts

[Al Viro]

	Looking through the old problems: pointer addition is not done
right.  What happens is simple - p + i turns into

	BINOP[+]
		<tree for p>
		BINOP[*]
			<tree for i>
			VAL[sizeof(*p)]

and we end up multiplying i and sizeof(*p) in wrong type.  On 64bit host
we _must_ expand i to 64 bits before we multiply; otherwise we get
wraparounds.

The question is, what do we do about that?  The obvious way would be
to do cast_to(), i.e. turn the above into

	BINOP[+]
		<tree for p>
		BINOP[*]
			IMPLICIEDT_CAST[ptrdiff_t]
				<tree for i>
			VAL[sizeof(*p)]

But that means a fsckload of extra nodes allocated on pretty much any
program - use of arrays is not rare and indices tend to be int, so we
hit an extra allocated node on each such place.

Another possible solution is to add a primitive for combined conversion
and multiplication - basically, convert the first argument to the type of
the second one and multiply.  We would actually need it only for ptrdiff_t;
sizeof(*p) is going to fit into the range anyway (it has to - the difference
between (char *)(p+1) and (char *)p must fit into it, or we couldn't do any
arithmetics on that pointer type at all; as soon as product overflows
ptrdiff_t we are free to do whatever the hell we like, since that's an
undefined behaviour and "multiply as ptrdiff_t values" gives an reasonable
result even in such cases).

That would cut down on extra nodes, but we pay for that by getting an
extra node type for linearizer, etc. to deal with.  Not sure how nasty
that's going to be...

Comments?

Re: pointer arithmetics and casts

[Al Viro]

On Fri, May 25, 2007 at 10:23:00PM +0100, Al Viro wrote:
> 	BINOP[+]
> 		<tree for p>
> 		BINOP[*]
> 			IMPLICIEDT_CAST[ptrdiff_t]
> 				<tree for i>
> 			VAL[sizeof(*p)]
> 
> But that means a fsckload of extra nodes allocated on pretty much any
> program - use of arrays is not rare and indices tend to be int, so we
> hit an extra allocated node on each such place.

Argh...  Question: how much do we care if we see BINOP[+] with 64bit
type as result and 32bit type in one of the arguments?  That's what
we get when we have
	char *p;
	int i;

	p + i

with -m64.  IOW, how much does it violate the assumptions outside of
frontend?  We do not allocate any new nodes if sizeof(*p) is 1...

Re: pointer arithmetics and casts

[Morten Welinder]

>         BINOP[+]
>                 <tree for p>
>                 BINOP[*]
>                         IMPLICIEDT_CAST[ptrdiff_t]
>                                 <tree for i>
>                         VAL[sizeof(*p)]

I don't think you want ptrdiff_t there.  It isn't guaranteed to
be big enough.

size_t should do, though.

M.

Re: pointer arithmetics and casts

[Derek M Jones]

Morten,

>>         BINOP[+]
>>                 <tree for p>
>>                 BINOP[*]
>>                         IMPLICIEDT_CAST[ptrdiff_t]
>>                                 <tree for i>
>>                         VAL[sizeof(*p)]
> 
> I don't think you want ptrdiff_t there.  It isn't guaranteed to
> be big enough.

It is also a signed type.

> size_t should do, though.

This is an unsigned type, so the wrap around behavior is defined.
But do you really want to map a small negative index into a large 
positive one?

You probably have to use intptr_t and uintptr_t.

On the other hand if sizeof(size_t) == sizeof(type_of(tree for i))
is an implicit cast needed?

-- 
Derek M. Jones                              tel: +44 (0) 1252 520 667
Knowledge Software Ltd                      mailto:derek@knosof.co.uk
Applications Standards Conformance Testing    http://www.knosof.co.uk

Re: pointer arithmetics and casts

[Al Viro]

On Fri, May 25, 2007 at 09:14:33PM -0400, Morten Welinder wrote:
> >        BINOP[+]
> >                <tree for p>
> >                BINOP[*]
> >                        IMPLICIEDT_CAST[ptrdiff_t]
> >                                <tree for i>
> >                        VAL[sizeof(*p)]
> 
> I don't think you want ptrdiff_t there.  It isn't guaranteed to
> be big enough.

Only if you are allowed to have an array object with elements too far
for their addresses to be subtracted...
 
> size_t should do, though.

size_t is an unsigned type, so by definition it won't do...

Re: pointer arithmetics and casts

[Neil Booth]

Al Viro wrote:-

> But that means a fsckload of extra nodes allocated on pretty much any
> program - use of arrays is not rare and indices tend to be int, so we
> hit an extra allocated node on each such place.
> 
> Another possible solution is to add a primitive for combined conversion
> and multiplication - basically, convert the first argument to the type of
> the second one and multiply.  We would actually need it only for ptrdiff_t;
> sizeof(*p) is going to fit into the range anyway (it has to - the difference
> between (char *)(p+1) and (char *)p must fit into it, or we couldn't do any
> arithmetics on that pointer type at all; as soon as product overflows
> ptrdiff_t we are free to do whatever the hell we like, since that's an
> undefined behaviour and "multiply as ptrdiff_t values" gives an reasonable
> result even in such cases).

Perhaps not overloading the "+" node; reserve that for arithmetic types.
Have a ptr_add, (maybe) ptr_sub, and ptr_diff operations.

GCC's moved to having at least a ptr_add recently.

Neil.

Re: pointer arithmetics and casts

[Al Viro]

On Sat, May 26, 2007 at 04:32:47AM +0100, Derek M Jones wrote:
> This is an unsigned type, so the wrap around behavior is defined.
> But do you really want to map a small negative index into a large 
> positive one?
> 
> You probably have to use intptr_t and uintptr_t.
> 
> On the other hand if sizeof(size_t) == sizeof(type_of(tree for i))
> is an implicit cast needed?

It is not; however, on a lot of targets that doesn't really help since
the typical situation will have i smaller than p (any 64bit target with
32bit int).  So the problem of having to allocate a lot of extra nodes
remains...

FWIW, I don't think that asking which of the target's integer types is
suitable is really relevant; assuming that such type exists at all,
we can make it a parameter of target and be done with that (BTW, we
are not guaranteed that there is an integer type capable of holding
a pointer - see 7.18.1.4, it's an optional type).

Re: pointer arithmetics and casts

[Al Viro]

On Sat, May 26, 2007 at 12:44:09PM +0900, Neil Booth wrote:
 
> Perhaps not overloading the "+" node; reserve that for arithmetic types.
> Have a ptr_add, (maybe) ptr_sub, and ptr_diff operations.

Making the scaling a part of operation?  It means interesting logics
at later stages, though...

Re: pointer arithmetics and casts

[Neil Booth]

Al Viro wrote:-

> On Sat, May 26, 2007 at 12:44:09PM +0900, Neil Booth wrote:
>  
> > Perhaps not overloading the "+" node; reserve that for arithmetic types.
> > Have a ptr_add, (maybe) ptr_sub, and ptr_diff operations.
> 
> Making the scaling a part of operation?  It means interesting logics
> at later stages, though...

Yes.  Should be handlable in one place during the lowering phase
(linearize? - I'm not too familiar with what sparse does after
parsing).

If you do make the scaling explicit in the IR, then in-line with
my belief that the IR should make all implicit operations explicit,
the multiplication would be on two operands of the same type, with
explicit casts wherever necessary.  I think having the extra nodes
and a sane IR is much better to having a non-orthogonal IR of fewer
nodes full of special cases (look at the mess GCC has with the latter).

Neil.

Re: pointer arithmetics and casts

[Al Viro]

On Fri, May 25, 2007 at 11:00:51PM +0100, Al Viro wrote:
> > But that means a fsckload of extra nodes allocated on pretty much any
> > program - use of arrays is not rare and indices tend to be int, so we
> > hit an extra allocated node on each such place.
> 
> Argh...  Question: how much do we care if we see BINOP[+] with 64bit
> type as result and 32bit type in one of the arguments?  That's what
> we get when we have
> 	char *p;
> 	int i;
> 
> 	p + i
> 
> with -m64.  IOW, how much does it violate the assumptions outside of
> frontend?  We do not allocate any new nodes if sizeof(*p) is 1...

Actually, turns out that at least on the kernel builds a straightforward
variant (IMPLIED_CAST when width of i is smaller than bits_in_pointer,
whatever sizeof(*p) might be) isn't visibly smaller...  It would need
more profiling, but there's a chance that nothing trickier would be
needed.

BTW, _Bool is seriously mishandled - for one thing, some places treat it 
as one-bit unsigned integer (i.e. (_Bool)2 becomes 0 with a warning, while
it should yield 1).  For another, sizeof(_Bool) becomes 0, with all obvious
breakage.  And finally, assignment of pointer to _Bool generates a warning
and cast.1 in linearizer.  Correct behaviour is (a) no warning whatsoever
and (b) replacement with b = (p != NULL).  The same thing applies in
passing arguments and in return statement, of course...

Oh, and type of comparison result is int, not _Bool...  It rarely matters,
but sometimes it does - e.g. sizeof(0 == 0) should evaluate to sizeof(int),
not sizeof(_Bool) (which basically casts the damn thing in stone - changing
the type of == result on valid C90 arguments would break existing programs).

I agree that use of bool_ctype in evaluate_compare() is very natural, but
we should at least take care interaction with sizeof ;-/