Patchwork increase call_saved_regs[] in caller-save.c

login
register
mail settings
Submitter DJ Delorie
Date Nov. 3, 2011, 3:21 a.m.
Message ID <201111030321.pA33LdBb029373@greed.delorie.com>
Download mbox | patch
Permalink /patch/123388/
State New
Headers show

Comments

DJ Delorie - Nov. 3, 2011, 3:21 a.m.
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.
Jeff Law - Nov. 3, 2011, 3:32 a.m.
-----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-----
DJ Delorie - Nov. 3, 2011, 4:21 p.m.
> 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.
Jeff Law - Nov. 3, 2011, 4:26 p.m.
-----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-----
DJ Delorie - Nov. 3, 2011, 7:13 p.m.
> 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?
Jeff Law - Nov. 4, 2011, 6:25 p.m.
-----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-----
Peter Bergner - Nov. 4, 2011, 8:23 p.m.
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
DJ Delorie - Nov. 4, 2011, 11:37 p.m.
> 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.
Jeff Law - Nov. 7, 2011, 4:46 a.m.
-----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-----
Jeff Law - Nov. 7, 2011, 4:49 a.m.
-----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-----
Michael Matz - Nov. 7, 2011, 8:27 a.m.
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.
Peter Bergner - Jan. 8, 2012, 4:58 a.m.
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
Michael Matz - Jan. 9, 2012, 12:42 p.m.
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.

Patch

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);