Re: Death by pointers.

chase@centerline.com (David Chase)
Tue, 12 Sep 1995 15:12:45 GMT

          From comp.compilers

Related articles
Order of argument evaluation in C++, etc. hbaker@netcom.com (1995-07-08)
Death by pointers. (Was: order of argument evaluation in C++, etc.) johnston@imec.be (1995-08-30)
Re: Death by pointers. jhallen@world.std.com (1995-09-05)
Re: Death by pointers. whitten@netcom.com (1995-09-05)
Re: Death by pointers. chase@centerline.com (1995-09-06)
Re: Death by pointers. hbaker@netcom.com (1995-09-11)
Re: Death by pointers. graham.matthews@pell.anu.edu.au (1995-09-12)
Re: Death by pointers. chase@centerline.com (1995-09-12)
Re: Death by pointers. preston@tera.com (1995-09-13)
Re: Death by pointers. ECE@dwaf-hri.pwv.gov.za (John Carter) (1995-09-23)
Re: Death by pointers. stefan.monnier@epfl.ch (Stefan Monnier) (1995-09-25)
| List of all articles for this month |

Newsgroups: comp.compilers
From: chase@centerline.com (David Chase)
Keywords: C, optimize
Organization: CenterLine Software
References: 95-07-068 95-09-030 95-09-061
Date: Tue, 12 Sep 1995 15:12:45 GMT

jhallen@world.std.com (Joseph H Allen) writes:


> Anyway, there is a solution to this problem [alias detection],
> although I'm not sure if it's
> worthwhile. You just completely skip alias detection in the compiler.
> Assume that there is no alias to your pointer and load it into a register if
> doing so will help optimize the code. The trick is to also load an
> extension to the register with the address of the origin of the pointer.
> Now whenever the CPU does a store, it checks the address of each loaded
> pointer. If any registers have the pointer, the register gets an update.
> Basically the registers act like a sort of mini-cache.


(I've seen this "solution" proposed before.)


This doesn't really work. I mean, it works, but it doesn't work
well enough. The amount of reordering you can do is basically
limited by the number of registers you have, because spilling a
register doesn't spill the register extension. In the case of
really interesting loop-rearrangement optimizations (the kind
that get you integer-factor speed improvements) this doesn't help
you at all.


It would benefit many people very much to study Fortran semantics,
analysis, and optimization.


for instance, this loop


    global = 0;
    for (j = 0; j < n; j++)
          for (i = 0; i < m; i++)
                global += some_array_ptr[i][j];


should be rewritten as


    global = 0;
    for (i = 0; i < m; i++)
          for (j = 0; j < n; j++)
                global += some_array_ptr[i][j];


to ensure better use of cache lines, but in C, it cannot be, because
some_array_ptr MIGHT be aliased to global. For large enough values of
m, the transformed piece of code is at least 3 times faster on a
high-performance workstation. Fortran rules usually allow this
transformation.


Entertainingly enough, if "global" were really a local, then the
transformation would be legal, and I know of at least one workstation
vendor's compiler that is within a stone's throw of doing this.


speaking for myself,


David Chase
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.