On 11/30/20 5:03 PM, Michael Matz wrote:
> Hello,
>
> On Mon, 30 Nov 2020, Jeff Law wrote:
>
>>>> So, then let's start with one of
>>>> the prime examples of SSA deconstruction problems, the lost swap, and how
>>>> it comes to be: we start with a swap:
>>>>
>>>> x = ..., y = ...
>>>> if (cond)
>>>> tmp=x, x=y, y=tmp
>>>>
>>>> (1) into SSA:
>>>>
>>>> x0 = ..., y0 = ...
>>>> if (cond)
>>>> tmp = x0, x1=y0, y1=tmp;
>>>> x2 = PHI(x0,x1), y2 = PHI(y0,y1)
>>>>
>>>> (2) copy-prop:
>>>>
>>>> x0 = ..., y0 = ...
>>>> if (cond)
>>>> ;
>>>> x2 = PHI(x0,y0), y2 = PHI(y0,x0)
>>> So the point is that this isn't what the RTL would look like even
>>> when using RTL SSA. Putting y0 in x2 PHI and x0 in the y2 PHI is
>>> representationally invalid.
>>>
>>> Like I say, this isn't a “native” SSA form: it's just using SSA
>>> constructs to represent dataflow in normal RTL.
>> It appears that the PHI arguments have to be different instances of the
>> result. So the case above can't happen, which helps, but I'm not sure
>> it's necessarily sufficient to avoid all the problems in this space.
>> IIRC you can get into a similar scenario by transformations that result
>> in overlapping lifetimes for different instances of the same object.
>> They didn't necessarily overlap when the SSA form was created, but may
>> after things like CSE or copy propagation.
> I think the reasoning why this can't (or should not) happen is the
> following: if different instances of the same objects (say, one before,
> one after a modification) exist, they must necessarily be stored in
> different pseudos (otherwise the RTL transformation itself was already
> invalid), and that causes them to be invalid operands of the same PHI
> node. Ala:
>
> input:
>
> regA = .... /1
> use1(regA) /2
> regA += ... /3
> use2(regA) /4
>
> let's try creating different instances of regA (from point 2 and 4) that
> overlap, e.g. by swapping insns 2 and 3. We _have_ to rename regA from
> insn 3 into a new pseudo, otherwise the uses of 2 and 4 can't be
> differentiated anymore, so:
>
> regA = .... /1
> regA' = regA
> regA' += .... /3'
> use1(regA) /2
> use2(regA') /4'
>
> So if Richards model constrains the pseudo PHI nodes such that regA and
> regA' can't be operands of one, that might solve the issue, as both the
> lost copy and the swap problem need overlaps of different values to occur.
Right. I was thinking about cases where something like CSE on this form
transforms the RHS of some operation into an instance of a pseudo. That
insn is now a copy and we propagate the RHS into the uses of the LHS.
That extends the lifetime of the pseudo's instance. The question is
whether or not those actions either create a lost copy/swap problem or
not within the on-the-side SSA representation and whether or not there
could be implications if that happens.
>
>> The fact that passes don't directly manipulate the PHIs definitely helps
>> as well. But I've still got some reading to do in this space to refresh
>> my memory of the issues.
> AFAIU Richards approach is more comparable to factored def-use chains than
> to real SSA, which might indeed have no issues, though I then think the
> problem moves into keeping _those_ consistent with the real instruction
> stream as it changes.
To some degree, the change in model moves where we have to tackle these
issues. Instead of tackling them in the out-of-ssa phase, we instead
have to think more about them in the analysis/optimization phases. We
already do that to some degree in the gimple SSA representation (for
things like SSA_NAMEs associated with abnormal edges).
jeff
