On Sat, Mar 1, 2008 at 2:46 PM, Paolo Bonzini <[EMAIL PROTECTED]> wrote: > > > By the way, I still don't understand how birth points would work. Can > > someone give an example of what the insn stream would look like with > > birth points, and what the DU/UD chains would look like? > > With a big IIUC, and using a high-level IR for simplicity > > if (a < 5) goto BB1; else goto BB2; > BB1: b = 3; goto BB3; > BB2: b = c; goto BB3; > BB3: return b * b; > > DF info for b: > insn <b = 3> has def D1 > insn <b = c> has def D2 > insn <b * b> has use U1 (use-def chain [D1,D2]) and > use U2 (use-def chain [D1,D2]) > > becomes > > if (a < 5) goto BB1; else goto BB2; > BB1: b = 3; goto BB2; > BB2: b = c; goto BB3; > BB3: b = b; return b * b; > > DF info for b: > insn <b = 3> has def D1 > insn <b = c> has def D2 > birthpoint <b = b> has use U1 (use-def chain [D1,D2]) > and def D3 > insn <b * b> has use U2 (use-def chain [D3]) > and use U3 (use-def chain [D3]) > > Basically the only non-singleton UD chains are for a birthpoint's RHS, > and the UD chains of birthpoints correspond to PHI operands. The > singleton UD chains correspond to subscripted SSA variables. I think > this is isomorphic to FUD chains.
Thanks for this explanation! I had the feeling that FUD chains and birth points are just different names for basically the same thing. That also seems to be your interpretation. So, from an implementation, would we make PHI-like UD-chains to nop insns that represent the birth points, or would we actually add PHI functions and let the "normal" UD-chains point to the PHI function arguments? What about keeping things up-to-date after applying some transformations? It is already hard to keep UD/DU chains up-to-date now (I don't think any pass successfully does so right now). This should be a lot easier if you fully factorize your UD chains, right? Gr. Steven
