prefetch revisited

prefetch revisited

[Janis Johnson]

In April 2000, Jan Hubicka proposed adding prefetch support to GCC
( http://gcc.gnu.org/ml/gcc/2000-04/msg00194.html ).  This was met with
much excitement and discussion, and Jan sent a few versions of a
prefetch patch to gcc-patches.  The discussion died and Jan apparently
dropped work on the patch, although he added prefetch support for SSE
and 3dNOW! to config/i386.md.

I'd like to revisit prefetch support in GCC and start by defining an
infrastructure that can allow various optimizations to eventually take
advantage of the prefetch capabilities of multiple architectures.  I
hope to use it for greedy prefetching of memory referenced by pointers,
as described in the paper "Compiler- Based Prefetching for Recursive
Data Structures" by Chi-Keung Luk and Todd C. Mowry, available via
http:/www.cs.cmu.edu/~tcm/Papers.html.  Jan's patch used it in loop
optimizations; that area is apparently undergoing a lot of changes, so
perhaps the people working on that would like to revisit Jan's prefetch
work for loops.  In the meantime I'll be using his old loop optimizer
changes to generate prefetches to let me test the underlying prefetch
support, with machine-specific support for IA-64 and Pentium III.

A new prefetch instruction pattern can take an address operand and a
list of options or flags indicating which kinds of prefetch support to
use, depending on what the machine supports.  The rtl code for prefetch
can be recognized throughout the compiler and handled appropriately.  A
machine description will map the options and flags to the appropriate
instruction for that machine, ignoring the ones that aren't relevant for
its prefetch support.  Each architecture will also define a set of
parameters for prefetching, including the cache line size and the number
of prefetches that can be done in parallel (as in Jan's patches).

The earlier discussions mentioned the following machines as supporting
prefetch: Athlon, ia64, Pentium III, hppa, mips, 3dNOW!, Sparc, PowerPC,
and Alpha.  Some of the variations of prefetch support that might be
taken into consideration are read vs. write accesses, base update form,
spatial and temporal locality, single vs. multiple reads, and multiple
cache levels; some also support both faulting and non-faulting versions,
but I assume that we can limit support to non-faulting prefetches.  Are
there other capabilities of prefetch support to consider?  Which
prefetch attributes are likely to be useful within GCC?

Each prefetch optimization can be controlled by a separate flag.  For
example:

-fprefetch-loop-arrays
      If supported for the target machine, generate prefetch
      instructions to improve the performance of loops that access
      large arrays.

-fprefetch-pointers
      If supported for the target machine, generate prefetch
      instructions to improve the performance of accesses to recursive
      data structures.

Am I on the right track?  I'm working on a patch as I figure out how all
of this stuff works in GCC and I'll be asking for advice on
implementation details later, but first I'd like to settle the wider
issues.

Janis

Re: prefetch revisited

[Jan Hubicka]

> In April 2000, Jan Hubicka proposed adding prefetch support to GCC
> ( http://gcc.gnu.org/ml/gcc/2000-04/msg00194.html ).  This was met with
> much excitement and discussion, and Jan sent a few versions of a
> prefetch patch to gcc-patches.  The discussion died and Jan apparently
> dropped work on the patch, although he added prefetch support for SSE
> and 3dNOW! to config/i386.md.

I didn't dropped it completely and in fact I plan to return to it in resobale
future and I made some code already.  The loop optimizer needs to be revisited
and we do have new loop depdendency code in "depdendency.c" that may be used
for better prefetch used for more selective prefetch generation than my
original code did.  In meantime I made some non-loop prefetching work.
> 
> I'd like to revisit prefetch support in GCC and start by defining an
> infrastructure that can allow various optimizations to eventually take
> advantage of the prefetch capabilities of multiple architectures.  I
> hope to use it for greedy prefetching of memory referenced by pointers,
> as described in the paper "Compiler- Based Prefetching for Recursive
> Data Structures" by Chi-Keung Luk and Todd C. Mowry, available via
> http:/www.cs.cmu.edu/~tcm/Papers.html.  Jan's patch used it in loop

Yes, implementing the greedy prefetching described there should be easy
enought and effective too.  In fact I am having that article on my table
waiting in the "TODO" list :)

> optimizations; that area is apparently undergoing a lot of changes, so
> perhaps the people working on that would like to revisit Jan's prefetch
> work for loops.  In the meantime I'll be using his old loop optimizer
> changes to generate prefetches to let me test the underlying prefetch
> support, with machine-specific support for IA-64 and Pentium III.
> 
> A new prefetch instruction pattern can take an address operand and a
> list of options or flags indicating which kinds of prefetch support to
> use, depending on what the machine supports.  The rtl code for prefetch

As discussed it probably makes sense to introduce new RTL construct
"prefetch" with an memory operand and set of flags to distinguish
various types of prefetches various instructions do have.

> can be recognized throughout the compiler and handled appropriately.  A
> machine description will map the options and flags to the appropriate
> instruction for that machine, ignoring the ones that aren't relevant for
> its prefetch support.  Each architecture will also define a set of
> parameters for prefetching, including the cache line size and the number
> of prefetches that can be done in parallel (as in Jan's patches).
> 
> The earlier discussions mentioned the following machines as supporting
> prefetch: Athlon, ia64, Pentium III, hppa, mips, 3dNOW!, Sparc, PowerPC,
> and Alpha.  Some of the variations of prefetch support that might be
> taken into consideration are read vs. write accesses, base update form,
> spatial and temporal locality, single vs. multiple reads, and multiple
> cache levels; some also support both faulting and non-faulting versions,
> but I assume that we can limit support to non-faulting prefetches.  Are
> there other capabilities of prefetch support to consider?  Which
> prefetch attributes are likely to be useful within GCC?
> 
> Each prefetch optimization can be controlled by a separate flag.  For
> example:
> 
> -fprefetch-loop-arrays
>       If supported for the target machine, generate prefetch
>       instructions to improve the performance of loops that access
>       large arrays.
> 
> -fprefetch-pointers
>       If supported for the target machine, generate prefetch
>       instructions to improve the performance of accesses to recursive
>       data structures.

Mipspro defined more levels of the prefetching code generation, as compiler may
do wonderfully bad job in some examples, but basically I think this approach
makes is correct.

> 
> Am I on the right track?  I'm working on a patch as I figure out how all
> of this stuff works in GCC and I'll be asking for advice on
> implementation details later, but first I'd like to settle the wider

We can discuss it together, as I had also plans concerning this issue..

In fact I have implemented simple greedy prefetching pass that looks for loads
of pointer that are later used as in memory addresses and emits the prefetch
instructions.  This already works relativly well - only problem it has is the
fact that I can't figure out the size of object pointed to and thus I don't
know how much data to fetch, but this should be doable by Richard Kenner's
memory tracking code.

The pass is DU/DF chains based and do use profile information to avoid
unneeded prefetching.

On non-IA-64 macines one can still take a look of offsets used in memory
references to get idea about size.

Honza
> issues.
> 
> Janis

Re: prefetch revisited

[Joseph S. Myers]

Somewhere in here it may make sense to use the information provided by the
C99 use of [static expr] parameter array declarators - meaning that the
pointer passed as an argument points to an array with at least the given
number of elements on entry to the function.  At present GCC checks the
constraints on these declarators, then discards the information about
"static" and the expression.

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: prefetch revisited

[Janis Johnson]

On Tue, Oct 30, 2001 at 06:41:53PM +0100, Jan Hubicka wrote:
> 
> Just to be more specific, the code actually works and is about 2 weeks old.
> I just didn't get around to benchmark it and prepare for review.  Also some
> of my fixes to df.c are still pending as the bitmap issue and few other
> larger patches I would like to see in with higher priority.
> 
> Probably some tweaking of the decision heuristics will be needed and I am
> not quite sure how much benefit it will bring as the paper itself don't mention
> too much.

I'd like to help examine and benchmark various decision heuristics; I've
got access to IA-64 and Pentium III machines and can probably also find
a PowerPC platform to use.
> 
> In case you want to concerntrate on the prefetch instruction representation and
> how to describe those tons of various features various I guess our work don't
> conflict and I would really like to see it in.  In case you want to implement
> the greedy prefetching, we probably should work together.

Yes, I'd like to work together on this.  I'll start by gathering
information about the capabilities of prefetch support on various
kinds of hardware and which ones might be worth exploiting in GCC, and
define the RTL pattern from that, along with the instruction definitions
for ia64 and i386 variants.  This will let me learn a lot about how
these things work in GCC.  I'll also keep track of the suggestions that
come up in this thread, like the one from Joseph Myers about [static
expr] parameter array declarators in C99.

Janis

Re: prefetch revisited

[Jan Hubicka]

> 
> In fact I have implemented simple greedy prefetching pass that looks for loads
> of pointer that are later used as in memory addresses and emits the prefetch
> instructions.  This already works relativly well - only problem it has is the
> fact that I can't figure out the size of object pointed to and thus I don't
> know how much data to fetch, but this should be doable by Richard Kenner's
> memory tracking code.
> 
> The pass is DU/DF chains based and do use profile information to avoid
> unneeded prefetching.

Just to be more specific, the code actually works and is about 2 weeks old.
I just didn't get around to benchmark it and prepare for review.  Also some
of my fixes to df.c are still pending as the bitmap issue and few other
larger patches I would like to see in with higher priority.

Probably some tweaking of the decision heuristics will be needed and I am
not quite sure how much benefit it will bring as the paper itself don't mention
too much.

In case you want to concerntrate on the prefetch instruction representation and
how to describe those tons of various features various I guess our work don't
conflict and I would really like to see it in.  In case you want to implement
the greedy prefetching, we probably should work together.

Honza

Re: prefetch revisited

[Jan Hubicka]

> On Tue, Oct 30, 2001 at 06:41:53PM +0100, Jan Hubicka wrote:
> > 
> > Just to be more specific, the code actually works and is about 2 weeks old.
> > I just didn't get around to benchmark it and prepare for review.  Also some
> > of my fixes to df.c are still pending as the bitmap issue and few other
> > larger patches I would like to see in with higher priority.
> > 
> > Probably some tweaking of the decision heuristics will be needed and I am
> > not quite sure how much benefit it will bring as the paper itself don't mention
> > too much.
> 
> I'd like to help examine and benchmark various decision heuristics; I've
> got access to IA-64 and Pentium III machines and can probably also find
> a PowerPC platform to use.

Currently my heuristics is simple - the at least one of usages of load
has to have at least 1/2 of frequency of the load instruction and
they must not occur in same basic block (as prefetch is not going to bring
much then).

We can probably tweak this in presence of write prefetches and such.

Also currently I have no generic interface for expanding prefetch instructions
so I do use the i386.md prefetch pattern that has magic integer argument,
so we need to clean this up for IA-64/PPC testing.
> > 
> > In case you want to concerntrate on the prefetch instruction representation and
> > how to describe those tons of various features various I guess our work don't
> > conflict and I would really like to see it in.  In case you want to implement
> > the greedy prefetching, we probably should work together.
> 
> Yes, I'd like to work together on this.  I'll start by gathering
> information about the capabilities of prefetch support on various
> kinds of hardware and which ones might be worth exploiting in GCC, and
> define the RTL pattern from that, along with the instruction definitions
> for ia64 and i386 variants.  This will let me learn a lot about how
> these things work in GCC.  I'll also keep track of the suggestions that
> come up in this thread, like the one from Joseph Myers about [static
> expr] parameter array declarators in C99.

Great.
I will try to dig out and cleanup my code and send it to the list.

(note that another places where it is effective to add prefetches are memsets
and memory allocation routines.
I've made little experiment with adding it to few places in gcc's garbage
collector and I was about to cuts it's running time to 1/8th of original).

Honza
> 
> Janis

Re: prefetch revisited

[Jan Hubicka]

Hi,
I've digged out one copy of my prefetch.c file.  It should be basically working,
but no guarantees.

It is definitly stupid.  I will try to do some tweaking overnight.

Honza

Re: prefetch revisited

[Janis Johnson]

On Tue, Oct 30, 2001 at 08:38:50PM +0100, Jan Hubicka wrote:
> Hi,
> I've digged out one copy of my prefetch.c file.  It should be basically working,
> but no guarantees.

I'd like to concentrate on the prefetch infrastructure for now and not
look at specific uses of it yet; I already have a version of your loop
optimizer changes to generate prefetch instructions, and at this point
I don't care if it's optimal or not.  I would, however, greatly
appreciate your feedback about what capabilities of hardware prefetch
support you think would be useful within GCC.  Those can be represented
in the RTL pattern for prefetch, and specific optimizations can choose
to use them or just pass default values.

In your patch you pass an address, and offset, and an int to
gen_prefetch; how is the offset used, and what is the int?  IA-64 has a
base-update form of prefetch, which adds an offset value to the base
register.  Is your offset for something like that?  What do you do with
the offset on a machine that doesn't support a base-offset form of
prefetch?

I'm cleaning up my current changes so I can post a preliminary version
of the prefetch infrastructure patch for review, with support for ia64
and i386 (sse and 3dnow!).  I'll put the update of your loop
optimization prefetch support in a separate patch to show how it's used.

Here's a preliminary description of the prefetch RTL information, based
on support in IA-64 and i386 variants; there might be fewer if some of
these aren't practical to use, or more if other machines have nifty
capabilities that GCC can exploit.

  (prefetch addr off rw temploc cachelev)

    Represents prefetch of memory at address addr plus offset off.
    (Is the offset added before or after the prefetch?)
    The other operands specify which capabilities of the machine's
    prefetch support to use.

      rw is a value for one of the following:
        read or generic prefetch
        write prefetch if available else nop
        write prefetch if available else generic prefetch

      temploc is a flag that is 1 if the prefetch should specify
      temporal locality.

      cachelev is a value between 0 and 15, where 0 specifies the
      nearest cache level available and 15 specifies the farthest cache
      level; a machine description maps these to the cache levels
      supported by its prefetch instructions.

    This insn is used to improve memory access time when the address of
    memory that is likely to be accessed is known far enough ahead of
    time to make prefetching that memory worthwhile.

In the meantime, Jan, in between all of your other projects you can
continue to determine how to use prefetch in optimizations and provide
me with feedback, and eventually our work can converge.

Janis

Re: prefetch revisited

[Jan Hubicka]

> 
> In your patch you pass an address, and offset, and an int to

Note that the patch is really more a toy than real patch.
For greedy prefetching according to the article one needs to figure out
what type the memory reference fetch pointer to (this can be doable
with memref tracking) and prefetch all recursive pointers in the structure.

This is where I see problem.  I believe no one in C says me that I can access
all fields of the structure when I access one, but I need to check the
standard, so at the moment I do the one level in prefetching needed to get some
performance hit except for trivial testcases, such asunrolled memset.

> gen_prefetch; how is the offset used, and what is the int?  IA-64 has a

This is because the pattern is hardcoded for i386, where the integer is
used fo place in the cache hiearchy I want data to be loaded.
> base-update form of prefetch, which adds an offset value to the base
> register.  Is your offset for something like that?  What do you do with
> the offset on a machine that doesn't support a base-offset form of
> prefetch?

I am not passing offset itself, I am offsetting the memory address.  On IA-64
that can't offset the code will just abort, but it can be easilly fixed
by legitimizing the address and emitting the whole sequence.
> 
> I'm cleaning up my current changes so I can post a preliminary version
> of the prefetch infrastructure patch for review, with support for ia64
> and i386 (sse and 3dnow!).  I'll put the update of your loop
> optimization prefetch support in a separate patch to show how it's used.
> 
> Here's a preliminary description of the prefetch RTL information, based
> on support in IA-64 and i386 variants; there might be fewer if some of
> these aren't practical to use, or more if other machines have nifty
> capabilities that GCC can exploit.
> 
>   (prefetch addr off rw temploc cachelev)
> 
>     Represents prefetch of memory at address addr plus offset off.
I believe all you need is single address.  Gcc already knows how to offset
addresses when needed and I believe there is nothing that makes prefetch
special in this case.
>     (Is the offset added before or after the prefetch?)
>     The other operands specify which capabilities of the machine's
>     prefetch support to use.

One of problem is how to specify these flags properly in RTL.  RTL already
do have flag field in each construct, but this is, uhm, hackish.  Perhaps
adding them just ac const int in the pattern is easiest way to go.

Otherwise the proposal looks fine to me.

Honza

Re: prefetch revisited

[Janis Johnson]

On Mon, Oct 29, 2001 at 01:48:15PM -0800, Janis Johnson wrote:
> In April 2000, Jan Hubicka proposed adding prefetch support to GCC
> ( http://gcc.gnu.org/ml/gcc/2000-04/msg00194.html ).  This was met with
> much excitement and discussion, and Jan sent a few versions of a
> prefetch patch to gcc-patches.  The discussion died and Jan apparently
> dropped work on the patch, although he added prefetch support for SSE
> and 3dNOW! to config/i386.md.

Sorry for the duplicate mail.  I sent this one yesterday and it
apparently got hung up in an IBM server for 24 hours.  I had assumed
that it was lost forever and sent it again this morning.

Janis

prefetch revisited

[Janis Johnson]

In April 2000, Jan Hubicka proposed adding prefetch support to GCC
( http://gcc.gnu.org/ml/gcc/2000-04/msg00194.html ).  This was met with
much excitement and discussion, and Jan sent a few versions of a
prefetch patch to gcc-patches.  The discussion died and Jan apparently
dropped work on the patch, although he added prefetch support for SSE
and 3dNOW! to config/i386.md.

I'd like to revisit prefetch support in GCC and start by defining an
infrastructure that can allow various optimizations to eventually take
advantage of the prefetch capabilities of multiple architectures.  I
hope to use it for greedy prefetching of memory referenced by pointers,
as described in the paper "Compiler- Based Prefetching for Recursive
Data Structures" by Chi-Keung Luk and Todd C. Mowry, available via
http:/www.cs.cmu.edu/~tcm/Papers.html.  Jan's patch used it in loop
optimizations; that area is apparently undergoing a lot of changes, so
perhaps the people working on that would like to revisit Jan's prefetch
work for loops.  In the meantime I'll be using his old loop optimizer
changes to generate prefetches to let me test the underlying prefetch
support, with machine-specific support for IA-64 and Pentium III.

A new prefetch instruction pattern can take an address operand and a
list of options or flags indicating which kinds of prefetch support to
use, depending on what the machine supports.  The rtl code for prefetch
can be recognized throughout the compiler and handled appropriately.  A
machine description will map the options and flags to the appropriate
instruction for that machine, ignoring the ones that aren't relevant for
its prefetch support.  Each architecture will also define a set of
parameters for prefetching, including the cache line size and the number
of prefetches that can be done in parallel (as in Jan's patches).

The earlier discussions mentioned the following machines as supporting
prefetch: Athlon, ia64, Pentium III, hppa, mips, 3dNOW!, Sparc, PowerPC,
and Alpha.  Some of the variations of prefetch support that might be
taken into consideration are read vs. write accesses, base update form,
spatial and temporal locality, single vs. multiple reads, and multiple
cache levels; some also support both faulting and non-faulting versions,
but I assume that we can limit support to non-faulting prefetches.  Are
there other capabilities of prefetch support to consider?  Which
prefetch attributes are likely to be useful within GCC?

Each prefetch optimization can be controlled by a separate flag.  For
example:

-fprefetch-loop-arrays
      If supported for the target machine, generate prefetch
      instructions to improve the performance of loops that access
      large arrays.

-fprefetch-pointers
      If supported for the target machine, generate prefetch
      instructions to improve the performance of accesses to recursive
      data structures.

Am I on the right track?  I'll be asking for advice on implementation
details later, but first I'd like to concentrate on the wider issues.

Janis