sparse -Wptr-subtraction-blows: still needed?

sparse -Wptr-subtraction-blows: still needed?

[Josh Triplett]

[-- Attachment #1: Type: text/plain, Size: 931 bytes --]


Sparse has a warning -Wptr-subtraction-blows (off by default) which generates
a warning for any pointer subtractions.  This warning relates to GCC
shortcomings observed in 2005; the original log message:

> commit 6889bd0f84939675c743229d6fe623513b95e057
> Author: Linus Torvalds <torvalds@ppc970.osdl.org>
> Date:   Fri Jan 7 15:06:24 2005 -0700
>
>     Add option "-Wptr-subtraction-blows" to warn about expensive
>     pointer subtractions.
>     
>     Not only does it generate bad code (that can often be rewritten
>     to not do that), it also causes gcc to go into horrible contortions,
>     and Al Viro reports that it can make a factor of 2.5 difference in
>     kernel build times to have just a few of these in common header
>     file inline functions.

Does this still apply?  Do current versions of GCC still have this problem?
If not, can the option and warning go away?

- Josh Triplett


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: sparse -Wptr-subtraction-blows: still needed?

[Linus Torvalds]

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.

		Linus

Re: sparse -Wptr-subtraction-blows: still needed?

[Josh Triplett]

[-- Attachment #1: Type: text/plain, Size: 1010 bytes --]

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.

"invariably"?

Do you know whether the current version of GCC generates poor code for pointer
subtraction?

If so, does anything in particular make this an unfixable problem?

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.

> So I'd not want to remove the warning.

Regardless of whether it addresses a current GCC issue or not, I have no
problem leaving the warning in if people want it, given that it requires an
explicit switch.

- Josh Triplett



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: sparse -Wptr-subtraction-blows: still needed?

[Al Viro]

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.

Re: sparse -Wptr-subtraction-blows: still needed?

[Linus Torvalds]

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

Re: sparse -Wptr-subtraction-blows: still needed?

[Al Viro]

On Tue, May 01, 2007 at 04:59:57PM -0700, Josh Triplett wrote:
> 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.
> 
> "invariably"?
> 
> Do you know whether the current version of GCC generates poor code for pointer
> subtraction?
> 
> If so, does anything in particular make this an unfixable problem?

Just the fact that calculation itself is nasty.  In the best case you
get (on x86) something like
        sarl    $2, %eax
        imull   $-1431655765, %eax, %eax
(that one is with object size equal to 12).  On other targets it can get
considerably uglier - e.g. on alpha with -O2 the same will result in
        sra $17,2,$17
        s4subq $17,$17,$0
        s8subq $0,$0,$0
        s4addq $0,$17,$0
        sll $0,8,$1
        addq $0,$1,$0
        sll $0,16,$2
        addq $0,$2,$0
        sll $0,32,$1
        addq $0,$1,$0
        addq $0,$0,$0
        addl $0,$17,$0
With -Os it's
        ldah $1,$LC0($29)               !gprelhigh
        sra $0,2,$0
        ldq $1,$LC0($1)         !gprellow
        mull $0,$1,$0
with LC0 in rodata:
$LC0:
        .quad   -6148914691236517205

Now imagine the joy of having a bunch of such wonders in a hot path...

Re: sparse -Wptr-subtraction-blows: still needed?

[Al Viro]

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.

Re: sparse -Wptr-subtraction-blows: still needed?

[Dave Jones]

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.

FWIW, I do sparse runs on the fedora development kernels as part of
our daily builds now, and of the latest ones at
http://people.redhat.com/davej/kernels/Fedora/fc7/warnings.txt
(concatenated warning logs from i586/i686/x86_64/ppc/ppc64/s390 builds)
that 'expensive pointer subtraction' turns up 3705 times.
Interestingly, 1873 of those instances are from include/linux/mm.h
on the x86-64 build.

It's complaining about this line...

static __always_inline void *lowmem_page_address(struct page *page)
{
        return __va(page_to_pfn(page) << PAGE_SHIFT);
}

...

unsigned long page_to_pfn(struct page *page)
{
        return __page_to_pfn(page);
}

...

#define __page_to_pfn(page)     ((unsigned long)((page) - mem_map) + \
                                 ARCH_PFN_OFFSET)

looks like the other two variants of __page_to_pfn also use similar arithmatic.

	Dave

-- 
http://www.codemonkey.org.uk

Re: sparse -Wptr-subtraction-blows: still needed?

[Alan Cox]

On Tue, 1 May 2007 17:24:54 -0700 (PDT)
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> 
> 
> 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!).

Good compilers even in the 1990's would defer the divide and try and
propogate it out as a multiply the other side for constants, and they'll
also use shifts when possible.

Thus they'll turn

	(ptr.element - base.element) < NELEM

into
	(ptr.char - base.char) < (constant) [NELEM *sizeof(element) ]


at least for constant operations. Dunno if gcc is that clever

Alan

Re: sparse -Wptr-subtraction-blows: still needed?

[Andi Kleen]

Dave Jones <davej@redhat.com> writes:
> 
> #define __page_to_pfn(page)     ((unsigned long)((page) - mem_map) + \
>                                  ARCH_PFN_OFFSET)
> 
> looks like the other two variants of __page_to_pfn also use similar arithmatic.

No way around this. The only way to turn a page into a pfn is to do 
a constant division.  Should be fairly cheap here though.

-Andi (who thinks the sparse warning is dumb; better to look at oprofiles
of hot paths)

Re: sparse -Wptr-subtraction-blows: still needed?

[Andi Kleen]

Alan Cox <alan@lxorguk.ukuu.org.uk> writes:
> 
> Good compilers even in the 1990's would defer the divide and try and
> propogate it out as a multiply the other side for constants, and they'll
> also use shifts when possible.

gcc has an algorithm that tends to generate a near perfect shift/add etc.
code sequence and also knows the obvious x / y ==> x*1/y

However it doesn't do that with -Os, prefering smaller code on x86
(idiv is fairly small compared to the expanded sequences for non power
of two dividends) and kernels are usually compiled with -Os these
days.

We've had a few cases in the past where this showed up as regression
against older kernels that still used -O2.
 
> Thus they'll turn
> 
> 	(ptr.element - base.element) < NELEM
> 
> into
> 	(ptr.char - base.char) < (constant) [NELEM *sizeof(element) ]
> 
> 
> at least for constant operations. Dunno if gcc is that clever

It is. However a few more complex transformations I would have liked
in the past are missing -- in particular 

x / (cond ? const1 : const2) ==> cond ? (x / const1) : (x / const2)

-Andi