On Mon, 7 Jul 2014, Jeff Law wrote:
On 07/06/14 08:23, Marc Glisse wrote:
What is the lifetime of an SSA_NAME with a default definition? The way
we handle it now, we start from the uses and go back to all blocks that
can reach one of the uses, since there is no defining statement where we
could stop
Right, that's exactly what I would expect given the typical definition of
liveness.
(intuitively we should stop where the clobber was, if not
earlier). This huge lifetime makes it very likely for such an SSA_NAME
to conflict with others. And if an abnormal phi is involved, and thus we
must coalesce, there is a problem.
So this suggests another approach. Could we just assume that it's always
safe to coalesce with a default definition?
The patch attached (it should probably use ssa_undefined_value_p with a
new extra argument to say whether we care about partially-undefined)
makes the lifetime of undefined local variables empty and lets the
original patch work with:
def = get_or_create_ssa_default_def (cfun, sym);
instead of creating a new variable.
Not a terrible suggestion either and accomplishes the same thing as the
mental model I had of special casing this stuff in the coalescing code.
I guess this is the first thing we probably should sort out. Do we want to
handle this is the conflict, coalescing or lifetime analysis.
We've certainly had similar hacks in the code which built the conflict matrix
for the register allocator in the past (old local-alloc/global variant, pre
IRA). By not recoding those conflicts, coalescing just magically works.
By handling it when we build the lifetimes, they'll magically coalesce
because there's no conflicts as well. It may help other code which utilizes
lifetimes as well. But a part of me doesn't like it because it is different
than the traditionally formulated life analysis.
Those variables don't have a birth time so their lifetime is quite
ill-defined in any case. I first tried to force coalesce for those
variables, but it is not very convenient. We do want to consider them
for coalescing, we can't just ignore them. But when we coalesce them
with a first variable, we want to mark it somehow so we don't later
coalesce them with a second variable that conflicts with the first. The
way we do that normally is by computing the union of the lifetimes, but
if we ignore the lifetime for this variable... It isn't just a matter of
adding || ssa_undefined_value_p (var) in the conflict test. Giving them
an empty lifetime to begin with seems to do the right thing. If we don't
modify the lifetime computation, we would have in coalesce to pass only
the "defined" variables to calculate_live_ranges and re-add the
undefined variables afterwards with an empty range.
The question I havent thought much about is would the coalescing code
do the right thing if we have one of these undefined SSA_NAMEs that
coalesce into two different partitions.
ie, let's say we have two PHI nodes in different blocks. Each PHI has
one or more source/dest operations that are marked as
SSA_NAME_OCCURS_IN_ABNORMAL_PHI. Furthermore, they all reference a
single RHS undefined SSA_NAME.
When we coalesce the undefined SSA_NAME with all the others in the
first PHI, doesn't that mean that we then have to coalesce all the
SSA_NAMES in both PHIs together (because that undefined SSA_NAME
appears on the RHS on the 2nd PHI too).
Does this then argue that each use of an undefined SSA_NAME should be
a unique SSA_NAME?
I did wonder about the same thing. But without the patch, there were only
2 files in the whole gcc+testsuite that had an issue (in the ada
front-end), and with the patch they were fine, so if the situation you
describe is possible, at least it is very uncommon.
Creating a new variable instead of reusing the old one may be less
likely to cause this kind of trouble. At least at creation time we know
there is no conflict since it is coming from a variable by an operation
that is the reverse of coalescing.
Ugh, I wonder if I just opened a can of worms here...
However, I am not convinced reusing the same variable is necessarily the
best thing. For warnings, we can create a new variable with the same
name (with .1 added by gcc at the end) and copy the location info (I am
not doing that yet), so little is lost. A new variable expresses more
clearly that the value it holds is random crap. If I reuse the same
variable, the SRA patch doesn't warn because SRA explicitly sets
TREE_NO_WARNING (this can probably be changed, but that's starting to be
a lot of changes). Creating a new variable is also more general. When
reading *ssa_name after *ssa_name={v}{CLOBBER}; or after free(ssa_name);
we have no variable to reuse so we will need to create a new undefined
variable, and if a variable is global or a PARM_DECL, its default
definition is not an undefined value (though it will probably happen in
a different pass, so it doesn't have to behave the same).
My concern about using another variable was primarily that it was being used
to hide a deeper issue.
(Side note: we don't seem to have any code to notice that:
a=phi<undef,b>
b=phi<undef,a>
means both phis can be replaced with undefined variables.)
Various passes will consider the undef value to be whatever value is
convenient for optimization. So for the first, we'd consider the undef value
to be the same as "b" because that allows the PHI to be propagated away.
Considering that a is the same as b and b is the same as a is not as good
as knowing that a and b are both undefined. I don't know if CCP is clever
enough to still optimize if b is used in a further PHI, but it would have
an easier time (and coalesce and the uninit warning as well) if a=undef;
b=undef; were forwarded into their uses instead. Not a priority though.
Obviously when there are many different values in the RHS, it's a lot less
likely that we'll be able to propagate away the PHI.
On Mon, 7 Jul 2014, Richard Biener wrote:
On Sun, Jul 6, 2014 at 4:23 PM, Marc Glisse <marc.gli...@inria.fr> wrote:
On Mon, 30 Jun 2014, Jeff Law wrote:
On 06/28/14 16:33, Marc Glisse wrote:
In an earlier version of the patch, I was using
get_or_create_ssa_default_def (cfun, sym);
(I was reusing the same variable). This passed bootstrap+testsuite on
all languages except for ada. Indeed, the compiler wanted to coalesce
several SSA_NAMEs, including those new ones, in out-of-ssa, but
couldn't.
And that's what you need to delve deeper into. Why did it refuse to
coalesce?
As long as the lifetimes do not overlap, then coalescing should have
worked.
What is the lifetime of an SSA_NAME with a default definition? The way we
handle it now, we start from the uses and go back to all blocks that can
reach one of the uses, since there is no defining statement where we could
stop (intuitively we should stop where the clobber was, if not earlier).
This huge lifetime makes it very likely for such an SSA_NAME to conflict
with others. And if an abnormal phi is involved, and thus we must coalesce,
there is a problem.
The patch attached (it should probably use ssa_undefined_value_p with a new
extra argument to say whether we care about partially-undefined) makes the
lifetime of undefined local variables empty and lets the original patch work
with:
def = get_or_create_ssa_default_def (cfun, sym);
instead of creating a new variable.
However, I am not convinced reusing the same variable is necessarily the
best thing. For warnings, we can create a new variable with the same name
(with .1 added by gcc at the end) and copy the location info (I am not doing
that yet), so little is lost. A new variable expresses more clearly that the
value it holds is random crap. If I reuse the same variable, the SRA patch
doesn't warn because SRA explicitly sets TREE_NO_WARNING (this can probably
be changed, but that's starting to be a lot of changes). Creating a new
variable is also more general. When reading *ssa_name after
*ssa_name={v}{CLOBBER}; or after free(ssa_name); we have no variable to
reuse so we will need to create a new undefined variable, and if a variable
is global or a PARM_DECL, its default definition is not an undefined value
(though it will probably happen in a different pass, so it doesn't have to
behave the same).
(Side note: we don't seem to have any code to notice that:
a=phi<undef,b>
b=phi<undef,a>
means both phis can be replaced with undefined variables.)
Propagators will never replace sth with unefined but they will exploit
the undefinedness. Constant propagation is even a bit more aggressive.
Do you have any advice on the right direction?
The patch below would work (btw, please use ssa_undefined_value_p),
but I wonder if it's the conflict code that should get adjustments
rather than the lifeness computation (lifeness of undefined values
shouldn't be needed at all).
Also depends on how we expand an undefined value of course.
I didn't really look at the expansion part.
--
Marc Glisse
