[tree-ssa]: Easy way to get default def of a variable?

[Daniel Berlin]

On Thu, 5 Jun 2003, Diego Novillo wrote:

> On Thu, 2003-06-05 at 12:49, Daniel Berlin wrote:
>
> > I don't know it's a_5, that's the problem.
> > Let me be more concrete:
> > In this case, we generate saves where we see expression phi operands
> > that have no actual occurrence associated with them yet (IE they need a
> > real expression save to back them up, but a usable one isn't there
> > already).
> > Thus, I need to figure out what version to use in the save.
> > We do this by walking up the dominator tree, looking for the closest
> > reaching def of the variable.
> > If there is none, after hitting the entry block, it must be live on
> > entry, and i need the default def.
> >
> Sorry Dan, I'm totally lost.  Could you show the code for the actual
> test case you're talking about?

Sure.

The code is a bit complicated, so i'll simplify it.
Given:
<BLOCK 0>

while (1)
{
	<BLOCK 1>
	a_5 = PHI <a_4 (0) <<<<< The default def, a_7 (13)>
        b_9 = a_5 + 3;
	... (More uses of a_5 + 3)
	<BLOCK 13>
	a_7 = 7;
}

To do this optimally, we do four things:

1. Insert a save at the end of the loop
2. Insert a save before the loop
3. Insert reloads in place of all the redundant expressions.
4. Insert a phi for the two saves we made.

So that the end code looks like:
<BLOCK 0>
pretmp_1 = a_4  + 3;
while (1)
{
<BLOCK 1>
	pretmp_2 = PHI<pretmp_1 (0), pretmp_3 (13)>
	b_9 = pretmp_2;
	.... (uses of a_5 + 3 replaced with pretmp_2)
	<BLOCK 13>
	a_7 = 7;
	pretmp_3 = a_7 + 3;
}


When we go to generate the save at pretmp_1, the only thing we have to
work with is the block we are in.  We don't have a handle to any "a_5 + 3"'s or
anything, because none *exist at that point yet*.

This is also true of the save at pretmp_3.

So what we do to make a correct expression is as follows:
1. Make a copy of the expression we are optimizing (a_<something> + 3).
2. Go walking up the dominator tree, looking at each statement to find
the closest definition of a_<something>, and use that.
3. Repeat for each variable that occurs in the expression.

For the save of pretmp_3, we find a_7 pretty quickly, since it's in the
same block.
For the save at pretmp_1, we won't find *anything*, because it needs the
default def of a, and that doesn't actually exist in the instruction
stream.  There are also no definitions of a before our insertion at all in
the instruction stream, so we still have nothing to start our default def
search from.
So to go find the name of the default def of a (in this case, a_4), we
first have to go looking for *some* definition of a again, in any block.
Then we have to walk the entire chain of defs back till we find the one
defined by the empty statement.

This is costly.


> I just don't see what problem you're trying to solve.
The problem is that getting the default def requires hunting down *some*
definition of the variable, and walking it's entire chain to find the one
whose defining statement is an empty statement.

This is a bit expensive.

If i had a table telling me what the default def of the variable was, i
wouldn't have to do this.


Make any more sense now?
 >
>
> Thanks.  Diego.
>
>