Michael Matz <m...@suse.de> writes: > 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. This isn't conceptually different from the way that virtual operands work in gimple. It's just that rather than having one vop for memory (as in gimple), we have one vop for memory, one vop for each individual hard register, and one vop for each individual pseudo register. FWIW, there's also a routine (rtl_ssa::restrict_movement) that takes the changes that a pass wants to make to an instruction and finds a range of locations that satisfy all the constraints. Thanks, Richard
