Re: Death by pointers.

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
--

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