| Message ID | 201111030321.pA33LdBb029373@greed.delorie.com |
|---|---|
| State | New |
| Headers | show |
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 11/02/11 21:21, DJ Delorie wrote: > I found this with the rl78-elf port... can't guarantee it's not > the rl78 port itself, but the code does have two loops that fill > the array. > > * caller-save.c (setup_save_areas): Increase call_saved_regs[] size > to avoid writing beyond the end of the array. There are two loops > that iterate over hard regs and potentially add to this array, so > it must hold a max of 2x the hard regs. But doesn't that imply that a hard register is getting inserted into the array more than once. While I don't see explicit code to prevent this, I'm having a hard time seeing how that can actually happen. Jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJOsgtaAAoJEBRtltQi2kC7WkMH/219vPDA8LeuVS5AQe3auR4N OAI2Ect4yVVVJEUdeW2IfxzE8AnOiLrEAEWuEfUp0YY9/eTqKDorXis70obdyX3Z 9Jdsap06CAGBYuoRaVDYbBt08Lp9RXVOzHhzx8nmhD13Kco9P+IYaqkCS+l+faKJ pb/lNXCj+85NdnhpEUraBXY54n1RG8JIFNIhN/grtQDIKd1N25aDra3uGouEuqF7 52+sHTrWGdSreBz21xaAkQEw8Pfn2qUVNxkH1M54/m3tBdLDTiHYAzzxC+DDZWqY q/22Y002Mq5+jyDNt8drDbwOz+g6HLC2Dw3fbX1LOhIb7rpFMH4jDA+ae3KqC/M= =aLcP -----END PGP SIGNATURE-----
> But doesn't that imply that a hard register is getting inserted into > the array more than once. While I don't see explicit code to > prevent this, I'm having a hard time seeing how that can actually > happen. It made no sense to me, but the array overflowed for my RL78 port, and less than half the registers are allocatable. Normally I'd point a finger at the port, but it works just fine with the bigger buffer.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 11/03/11 10:21, DJ Delorie wrote: >> But doesn't that imply that a hard register is getting inserted >> into the array more than once. While I don't see explicit code >> to prevent this, I'm having a hard time seeing how that can >> actually happen. > > It made no sense to me, but the array overflowed for my RL78 port, > and less than half the registers are allocatable. Normally I'd > point a finger at the port, but it works just fine with the bigger > buffer. But again, I'd like to why duplicates ended up in the array; that's the fundamental question. jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJOssDTAAoJEBRtltQi2kC7dFIH/3FQi2wwb6jt9F5eHNp+hIMF HUILE2p/lGgoKhPdUkFVQ1eUjPph5lqJfcxXwPhyN/tewg8gFRLuS0PXJwgDkSRS ue/hLtNcx60BoQ7/Gd9OFxOm0LOe3yHCg6H4lJXzZqzcjMJkYdeMXdkiPAEnuNBh gu8VrSHZT3VXPbIIOgoqpeVY3DXlPUltWli9twUW9/anJY7U7/ger3zouSV4z1uW ogLgb3szc21ItpecQqpeMAm9O6FvxgUHT3Hb++wh/uEbVPtSR2PiaGyY1on8KFM0 hKA1ZnAhHti0fUfiWObZ8/sFo/hOdfr6oKkaOvOTDoR57vs8qljG2w/Q7r57hjc= =pLBf -----END PGP SIGNATURE-----
> But doesn't that imply that a hard register is getting inserted into > the array more than once. While I don't see explicit code to prevent > this, I'm having a hard time seeing how that can actually happen. The test case is qsort.c from newlib. I added some runtime checks to caller-saves and it looks like there are at least two pseudos assigned to the same hard reg, so the hard reg gets added more than once. Is this normal?
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 11/03/11 13:13, DJ Delorie wrote: >> But doesn't that imply that a hard register is getting inserted >> into the array more than once. While I don't see explicit code >> to prevent this, I'm having a hard time seeing how that can >> actually happen. > > The test case is qsort.c from newlib. I added some runtime checks > to caller-saves and it looks like there are at least two pseudos > assigned to the same hard reg, so the hard reg gets added more than > once. Is this normal? It's certainly normal to have multiple pseudos assigned to the same hard reg, but never at the same time. ie, the lifetimes of the pseudos must not overlap. The only way I can think of to have two pseudos assigned the same hard reg at the same point in the insn stream is if the two pseudos are known to have the same value. I'm don't think IRA implements this particular optimization -- I vaguely recall Vlad talking about it and mentioning that it wasn't worth the implementation effort. So I guess the first thing to do is see if you've got two pseudos in the same hard reg at a single point and then figure out how/why that happened. You ought to be able to detect this within the EXECUTE_IF_SET_IN_REG_SET loop. Jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJOtC38AAoJEBRtltQi2kC7lEgIAKeub93zP9QZ23d0oF/7ItPl GqmZk9kJhZKgBcnh6CbNIZaiDshEAPDtFInj/FrXAvbn/8bqdRr2GGALqxaoppeI zJiuydWNAcI2TjgEYb1+MxWfkyj03LYdDp44ivaDL6G7B2vCAi6ckVjUTG6XYDjV fcfXhBxFTfaIW4zl3RtuLo0fCDB3xjLFVLTrgKriRZuGifDNTNBcRormgG92PKd/ 8DpNwwH0EOtUkw7Xe881D8xXnFaTYzTkC4RtpMg4EtHEZPwDQzjGInO1utLYNAY1 OfmoVA1AXYoc9FQxkSlcw9oEUmY7kj3mqcX9oIh/9L4H75KFATkx3pthLcuZ7Sg= =MPlS -----END PGP SIGNATURE-----
On Fri, 2011-11-04 at 12:25 -0600, Jeff Law wrote: > The only way I can think of to have two pseudos assigned the same hard > reg at the same point in the insn stream is if the two pseudos are > known to have the same value. Having the same value is the more common way two overlapping pseudos don't conflict, but if one or both of the pseudos are undefined (ie, no definition point), then they won't conflict either. > I'm don't think IRA implements this particular optimization -- I vaguely > recall Vlad talking about it and mentioning that it wasn't worth the > implementation effort. I'm surprised and saddened to head we don't at least treat copies specially wrt computing conflicts. That said, if one or both of the pseudos are undefined, then that could explain why two pseudos are allocated to the same hard register at the same time even with the code we have now. Peter
> The only way I can think of to have two pseudos assigned the same > hard reg at the same point in the insn stream is if the two pseudos > are known to have the same value. Since all we're doing is figuring out which hard regs need to be saved in pro/epilogue, it could be that the two pseudos are not live at the same time, despite being live in the same function.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 11/04/11 17:37, DJ Delorie wrote: >> The only way I can think of to have two pseudos assigned the >> same hard reg at the same point in the insn stream is if the two >> pseudos are known to have the same value. > > Since all we're doing is figuring out which hard regs need to be > saved in pro/epilogue, it could be that the two pseudos are not > live at the same time, despite being live in the same function. ?!? caller-save emit saves/restores at call sites, not in the prologue/epilogue. It looks at the set of registers live, call-clobbered and not currently saved in the stack at each call site to make this determination. So the question I would still ask is precisely how multiple hard registers are being stored into that array. I don't think that's supposed to be happening, but I could be wrong. Knowing how this is happening is critical to determining if the patch is correct or just papering over a problem elsewhere. jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJOt2KPAAoJEBRtltQi2kC7PFYH/jXyJAjdc+X3slLuebXBP4ux ENcRFeQDIZh0P1+bqysd6WZ4eD3Wu93fkJjzqSXySI8MLQ60P9TGEzfGFjL7Sc+Z KMqytPC5dSZ8vJWXRHc7jI176gX00bc51G73CC/ETKMdJVxwv9j87Qs2V5eFahNM WE5YDM6Ghv/0YJgBs9gqgV4dOy7hd3go/TS5KgfT8n77VxdfrXeB4kD4sGM2vLez QRocJeOIhOx+fjwmBoNYIMnLkQuyVMNyrTXSP7T+X8ionPSGPxH/nk8tX4/2xHwp iR1dDh1vZczfvb8nUGris6TnYE/oJq3zKoCXiZffQlcENdvARf3nNDw6oeitWfg= =PPHL -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 11/04/11 14:23, Peter Bergner wrote: > On Fri, 2011-11-04 at 12:25 -0600, Jeff Law wrote: >> The only way I can think of to have two pseudos assigned the same >> hard reg at the same point in the insn stream is if the two >> pseudos are known to have the same value. > > Having the same value is the more common way two overlapping > pseudos don't conflict, but if one or both of the pseudos are > undefined (ie, no definition point), then they won't conflict > either. However, I'm pretty sure we do not take advantage of the fact that two pseudos with the same value with overlapping lifetimes do not conflict and thus can live in the same hard reg. In fact, if you try to implement that optimization, you'll find that reload chokes in fun and unpleasant ways. I actually tried this myself a while back ;-) Jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJOt2NYAAoJEBRtltQi2kC764cIAKvRkCrVtEjUfhZSg63dzkDp jbp9HObcAxT8I/vlDcgkftzx5xpQN4QpRRIN/cFcPdVcgsJHk97W/ZPo7Tnmwqkm DJRwNxCxrrSJ3xNiOdRZCJTomb/28K1nthJVpRin0i4QdHjvUP6Cs5NYQ4/Nuj+Z ponJRdldJYaAx7QFcb+4Z6R0e7mjaeQ8NUvs3SUkrmTeIn0JArZ9gkR1061Dv2KI Th3FPY9jnOHZw75Tmszt3DEKzXpwjA3NzFM919u3chrfDx21F2HqrycyLqECxylg fIyAFCPlMyj4Vhf07Nr59NId2j84bZy5KC2Zakvl0xYAIwyHZqqrpY0U7qQgr7Y= =59oA -----END PGP SIGNATURE-----
Hi, On Sun, 6 Nov 2011, Jeff Law wrote: > > On Fri, 2011-11-04 at 12:25 -0600, Jeff Law wrote: > >> The only way I can think of to have two pseudos assigned the same > >> hard reg at the same point in the insn stream is if the two > >> pseudos are known to have the same value. > > > > Having the same value is the more common way two overlapping > > pseudos don't conflict, but if one or both of the pseudos are > > undefined (ie, no definition point), then they won't conflict > > either. > However, I'm pretty sure we do not take advantage of the fact that two > pseudos with the same value with overlapping lifetimes do not conflict > and thus can live in the same hard reg. In fact, if you try to > implement that optimization, you'll find that reload chokes in fun and > unpleasant ways. I actually tried this myself a while back ;-) One source of same valued pseudos are copies, and copy coalescing we (of course) do implement. Peter: it's only other non-trivial sources of same-valued-ness that we don't use in the allocator, so don't be too sad ;-) Ciao, Michael.
On Mon, 2011-11-07 at 09:27 +0100, Michael Matz wrote: > One source of same valued pseudos are copies, and copy coalescing we (of > course) do implement. While digging through ira-color.c tracking down an IRA shuffle copy issue, I noticed we only seem to do real copy coalescing for spilled pseudos. It seems we rely on coloring to try and assign the same hard reg to pseudos connected by a copy so the copy can be removed as a nop. Looking at all the code used to do the cost preferencing to achieve that, I'm guessing just coalescing them would be a lot easier. Peter
Hi, On Sat, 7 Jan 2012, Peter Bergner wrote: > While digging through ira-color.c tracking down an IRA shuffle copy > issue, I noticed we only seem to do real copy coalescing for spilled > pseudos. It seems we rely on coloring to try and assign the same hard > reg to pseudos connected by a copy so the copy can be removed as a nop. > Looking at all the code used to do the cost preferencing to achieve > that, I'm guessing just coalescing them would be a lot easier. The complexity starts when you want to retroactively decide that a coalesce was not that worthwhile or even harmful. Copies sometimes are nice live-range split points (and sometimes not), so some copies you want to coalesce, others you don't want to. Deciding which ones to coalesce influences the others, spilling influences it too, and finally coloring decisions itself influence the optimality of coalescing retroactively. Past approaches to this included a host of things including the iterated approach, the coalesce-split approach and the like. When I still fiddled with all this in new-ra I found it most natural to just do coalescing while coloring (i.e. try to give same colors to copy-connected neighbors), including taking care not to take away colors from nodes that would prefer to get colors from a copy-neighbor. This way reverting a coalesce merely becomes a "oh well, so this color in the end wasn't really available", instead of an operation on the conflict/coalesce graph. I assume that Vlad does similar. Ciao, Michael.
Index: gcc/caller-save.c =================================================================== --- gcc/caller-save.c (revision 180758) +++ gcc/caller-save.c (working copy) @@ -494,13 +494,13 @@ setup_save_areas (void) { rtx slot; char *saved_reg_conflicts; int next_k; struct saved_hard_reg *saved_reg2, *saved_reg3; int call_saved_regs_num; - struct saved_hard_reg *call_saved_regs[FIRST_PSEUDO_REGISTER]; + struct saved_hard_reg *call_saved_regs[FIRST_PSEUDO_REGISTER*2]; int best_slot_num; int prev_save_slots_num; rtx prev_save_slots[FIRST_PSEUDO_REGISTER]; /* Find saved hard register conflicts. */ saved_reg_conflicts = (char *) xmalloc (saved_regs_num * saved_regs_num);