Use-Def Chains and ambiguous definitions/uses

I'm trying to reduce the memory requirements of my optimizer's Use-Def
chains, and I've run into an interesting problem involving representation
of ambiguous uses/definitions (loads/stores of potentially aliased
variables)


In my original implementation, for each pointer-load/pointer-store I would
generate a unique (ambiguous) use/def for each potentially aliased
variable. I've found that in certain programs which have lots of aliased
variables this causes an incredible explosion in the dataflow sets. (One
example program generates more than 100,000 uses and 100,000 defs)


After re-reading some of the literature, I discovered that one technique
is to have unique resources which represent sets of potentially aliased
variables, so that a single use/def can reference this resource and
represent an ambiguous use/definition of any element in the set.


This seemed to work pretty well for ambiguous definitions, but I've run
across a problem in computing the local dataflow sets for (ambiguous)
upwards exposed uses. Consider the following code:


        extern int *p;
        extern int x, y, z;


B1: y = *p; // this might use x, y, or z
        ...
B2: x = 5; // this definitely defines x
        z = *p; // this might use x, y, or z
        ...


The uses of x, y, and z are upwards exposed at B1, i.e. any definition of
any of these in B1's predecessors may reach B1. If I have a single use u:
{x,y,z} which represents the ambiguous use of any of these 3 variables,
the dataflow information will still be precise, just as if I had
represented them as 3 separate uses u1:x, u2:y, u3:z.


However, since B2 has a definition of x which precedes the potential use
of x at *p, only the uses of y and x are upwards exposed at B2. If I still
use a single use to represent the set {x,y,z} then the dataflow
information will be too conservative. (For example, it might inhibit
moving a store outside a loop)


Has anyone else encountered this situation, and how did you resolve it?
(One possibility is to have much better alias information so that the
dataflow sets do not explode so rapidly in the presence of
pointer-loads/pointer-stores, but I was looking for a simpler solution)


I'd be particularly interested in the opinions of anyone who has worked on
the HP global optimizer described in "Effectiveness of a machine-level
global optimizer" from the SIGPLAN '86 Symposium on Compiler Construction,
since that paper was the inspiration for my dataflow sets.


--
John McEnerney (mcenerney@metrowerks.com)
Metrowerks PowerPC Compiler Architect
--

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