Re: Death by pointers. (David Chase)
Tue, 12 Sep 1995 15:12:45 GMT

          From comp.compilers

Related articles
Order of argument evaluation in C++, etc. (1995-07-08)
Death by pointers. (Was: order of argument evaluation in C++, etc.) (1995-08-30)
Re: Death by pointers. (1995-09-05)
Re: Death by pointers. (1995-09-05)
Re: Death by pointers. (1995-09-06)
Re: Death by pointers. (1995-09-11)
Re: Death by pointers. (1995-09-12)
Re: Death by pointers. (1995-09-12)
Re: Death by pointers. (1995-09-13)
Re: Death by pointers. (John Carter) (1995-09-23)
Re: Death by pointers. (Stefan Monnier) (1995-09-25)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (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 (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

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.