From: Al Viro <viro@ftp.linux.org.uk>
Newsgroups: fa.linux.kernel
Subject: Re: sparse -Wptr-subtraction-blows: still needed?
Date: Wed, 02 May 2007 00:03:07 UTC
Message-ID: <fa.1BLfWzNlfA1glN73XzWvvUrjL4c@ifi.uio.no>

On Tue, May 01, 2007 at 02:43:30PM -0700, Linus Torvalds wrote:
>
>
> On Tue, 1 May 2007, Josh Triplett wrote:
> >
> > Does this still apply?  Do current versions of GCC still have this problem?
> > If not, can the option and warning go away?
>
> Even if current versions of gcc don't triple the build time (and for the
> kernel, I suspect it doesn't, because we've tried to clean up our header
> files), the generated _code_ will invariably suck.
>
> So I'd not want to remove the warning.

Note that code *will* blow: in effect, when we have a*2^b as object size,
we have to choose between
	* generic division by a*2^b (dog-slow pretty much on anything)
	* multiplication by such c that a*c == 1 (mod 2^word_size-b), then
shift down by b.
	* shift down by b, then multiplication by such c that a*c == 1
(mod 2^word_size).
And c in the above won't be small or pretty, so doing multiplication as
series of additions won't be short.

FWIW, I've seen very nasty cases (in userland code) where hot path got blown
by factor of 5 or so in size due to that; basically, it started with
#define INDEX(p) ((p)-array)
and that sucker got used a lot in other macros, so it wasn't immediately
obvious what had been going on.  So yes, we do want to be able to see
such cases.

From: Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups: fa.linux.kernel
Subject: Re: sparse -Wptr-subtraction-blows: still needed?
Date: Wed, 02 May 2007 00:25:56 UTC
Message-ID: <fa.A66IA8WNfEwLrJ2RmrA2lf1IyZg@ifi.uio.no>

On Tue, 1 May 2007, Josh Triplett wrote:
>
> Do you know whether the current version of GCC generates poor code for pointer
> subtraction?

You _cannot_ generate good code.

When you subtract two pointers, the C definition means that you first
subtract the values (cheap), and then you *divide* the result by the size
of the object the pointer points to (expensive!).

So pointer subtraction is by definition expensive, if the size of the
object is not some kind of nice power-of-two or similar.

Of course, modern CPU's are getting better at divides.

> Has anyone reported this poor code generation to the GCC bugzilla?  If so, I
> can add a reference to the bug in any (hypothetical) documentation for
> -Wptr-subtraction-blows.

The only thing that was gcc-specific about it is that gcc goes to some
extreme lengths to turn the constant-sized division into a sequence of
shifts/multiples/subtracts, and can often turn a division into something
like ten cheaper operations instead.

But that optimization was also what made gcc take such a long time if the
constant division is very common (ie a header file with an inline
function, whether that function is actually _used_ or not apparently
didn't matter to gcc)

So gcc does pretty well on these divisions, and makes them cheaper (except
on CPU's where divides are really fast and possibly even cheaper than the
combination of shifts/subtracts, but afaik, that probably won't be until
the next-generation Intel Core 2 45nm "Penryn" thing)

			Linus

From: Al Viro <viro@ftp.linux.org.uk>
Newsgroups: fa.linux.kernel
Subject: Re: sparse -Wptr-subtraction-blows: still needed?
Date: Wed, 02 May 2007 00:36:32 UTC
Message-ID: <fa.QgYJl1WoqiyRDaq6dQQ75kUXTgQ@ifi.uio.no>

On Tue, May 01, 2007 at 05:24:54PM -0700, Linus Torvalds wrote:
> The only thing that was gcc-specific about it is that gcc goes to some
> extreme lengths to turn the constant-sized division into a sequence of
> shifts/multiples/subtracts, and can often turn a division into something
> like ten cheaper operations instead.
>
> But that optimization was also what made gcc take such a long time if the
> constant division is very common (ie a header file with an inline
> function, whether that function is actually _used_ or not apparently
> didn't matter to gcc)

There used to be a Dumb Algorithm(tm) in there - basically, gcc went through
all decompositions of constant it was multiplying at and it did it in the
dumbest way possible (== without keeping track of the things like "oh, we'd
already looked at the best way to multiply by 69, no need to redo that
again and again)").  _That_ is what blew the build time to hell for a while.
And yes, that particular idiocy got fixed (they added a moderately-sized
LRU of triplets <constant, price, best way to multiply on it>, which killed
recalculation from scratch for each pointer subtraction and got complexity
of dealing with individual subtraction into tolerable range).

That's separate from runtime issues, of course.