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. > 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. Ciao, Michael.
