RFA: fix breakage in broken-.word machinery

[Hans-Peter Nilsson <hans-peter dot nilsson at axis dot com>]

NB: I'm quite aware that a superior fix is to not use this
misfeature and to #define WORKING_DOT_WORD, thank you. ;)

Two bugs here, that are only apparent for case-tables that look
like ".word sym1-sym2" where the sym2 are not all the same.  As
broken-.word bugs go, no normal code trigs them.  For example, I
instrumented the code at the patch and found that the bugs did
not trig for cris-axis-linux-gnu for neither of a gcc regtest,
(e)glibc (2.9-ish) build and test-suite run nor a Linux build
(2.6.26-ish) nor anything else comprising the code in one of
Axis' middle-end products.  Machine-generated code from e.g. a
Soap description trigged this bug (no details available).

Anyway, about the first bug: in relax_segment while iterating on
a .word case-table containing multiple references to the same
symbol (from e.g. "case 7: case 8: case 42: <code>; break") in
one iteration, the offset at (say) the "case 8" entry may
overflow while the "case 42" entry doesn't, but then in a later
iteration, the "case 42" offset is also found to overflow.  When
the "case 42" entry overflows, all earlier entries (case 7 and
8) aiming at the same code are redirected to use the same
md_long_jump as the overflowing one (if the code is located
after the overflowing entry, they'll overflow too) *but keeping
the relaxation-size adjustment for earlier overflows*.  The most
prominent effect of this bug is that the in-code location of
every relocation after the jump-table is off by a multiple of
md_long_jump_size (but most likely just 1) causing e.g. an
invalid instruction (relocations applied to the wrong
instruction), or a "valid" instruction that jump to address 0
(missing absolute relocation), or a jump to itself or not at all
(missing pc-relative relocation).

I fixed this bug by redirecting *all* same-target entries when
any of them overflow, so there'd be no overflows at later
rounds.  Arguably, some of those entries may not have overflowed
(for higher case numbers and forward offsets) and in the odd
case where gcc has laid out code for entries *before* the jump
(backward offsets), it can cause the broken-.word machinery to
overflow for a slightly smaller case-table.  (The broken-.word
machinery can "only" handle tables where a 16-bit offset, when
overflowing for the actual code, can still reach the entry in a
secondary jump table.  For "typical use", when all offsets are
positive i.e. the case-code is located after the base symbol
sym1 below, for a case-table where the first entry overflows,
it'll overflow when the table has at most 16383 entries.  This
overflow can be detected, but *not* worked around by
TC_CHECK_ADJUSTED_BROKEN_DOT_WORD).  The patch also about
doubles the constant for this O(n**2)-complexity code, now
re-scanning from the beginning of the case-table.  Still, this
is the smallest safe improvement I could think of, it has no
code-changing effect on the few targets using this misfeature
and where sym1 in a case-table ".word sym2-sym1" is constant,
and I'd rather not spend time trying to optimize this severely
limited machinery that I presume everybody agrees should be
removed sooner rather than later (hope I'm preaching to the
choir here, sorry about the duckspeak).  But the bug should
first be fixed.

There's another bug when writing out the offsets.  The broken
.word-machinery pretends to handle all ".word sym1-sym2" usage.
But, when writing out offsets for overflowing cases for the same
sym1 (that may or may not have overflowed at the same iteration
as per the bug above), all offsets are assumed to have the same
"sym2".  See the test-case, where the base symbol is "."; the
address of the entry, instead of the typical "x" at the start of
the table.  Easy enough to fix to handle sym2 being different
rather than removing the reuse-same-case machinery.

I find myself giving in to the sin of submitting a fix for both
bugs in the same patch (or else I'd have to submit a half-way
incorrect fix and a patch for the test-case).  The test-case
covers both bugs.

Ok to commit?

gas:
	* write.c (write_object_file) [!WORKING_DOT_WORD]: When patching
	the jump table for multiple overflowing entries with the same
	target, handle base symbols being different.
	(relax_segment) <case rs_broken_word, second loop>: Whenever a
	single entry overflows, arrange to redirect all entries with the
	same target.

gas/testsuite:
	* gas/cris/rd-bkw4.d, gas/cris/rd-bkw4v32.d, gas/cris/rd-bkw4.s:
	New test.

Index: write.c
===================================================================
RCS file: /cvs/src/src/gas/write.c,v
retrieving revision 1.121
diff -p -u -r1.121 write.c
--- write.c	19 Sep 2008 10:00:40 -0000	1.121
+++ write.c	10 Mar 2009 04:20:51 -0000
@@ -1671,18 +1671,22 @@ write_object_file (void)
 	    if (lie->added == 2)
 	      continue;
 	    /* Patch the jump table.  */
-	    /* This is the offset from ??? to table_ptr+0.  */
-	    to_addr = table_addr - S_GET_VALUE (lie->sub);
-#ifdef TC_CHECK_ADJUSTED_BROKEN_DOT_WORD
-	    TC_CHECK_ADJUSTED_BROKEN_DOT_WORD (to_addr, lie);
-#endif
-	    md_number_to_chars (lie->word_goes_here, to_addr, 2);
-	    for (untruth = lie->next_broken_word;
+	    for (untruth = (struct broken_word *) (fragP->fr_symbol);
 		 untruth && untruth->dispfrag == fragP;
 		 untruth = untruth->next_broken_word)
 	      {
 		if (untruth->use_jump == lie)
-		  md_number_to_chars (untruth->word_goes_here, to_addr, 2);
+		  {
+		    /* This is the offset from ??? to table_ptr+0.
+		       The target is the same for all users of this
+		       md_long_jump, but the "sub" bases (and hence the
+		       offsets) may be different.  */
+		    addressT to_word = table_addr - S_GET_VALUE (untruth->sub);
+#ifdef TC_CHECK_ADJUSTED_BROKEN_DOT_WORD
+		    TC_CHECK_ADJUSTED_BROKEN_DOT_WORD (to_word, untruth);
+#endif
+		    md_number_to_chars (untruth->word_goes_here, to_word, 2);
+		  }
 	      }
 
 	    /* Install the long jump.  */
@@ -2226,13 +2230,17 @@ relax_segment (struct frag *segment_frag
 					     S_GET_NAME (lie->sub),
 					     buf);
 			    }
-			  lie->added = 1;
 			  if (fragP->fr_subtype == 0)
 			    {
 			      fragP->fr_subtype++;
 			      growth += md_short_jump_size;
 			    }
-			  for (untruth = lie->next_broken_word;
+
+			  /* Redirect *all* words of this table with the same
+			     target, lest we have to handle the case where the
+			     same target but with a offset that fits on this
+			     round overflows at the next relaxation round.  */
+			  for (untruth = (struct broken_word *) (fragP->fr_symbol);
 			       untruth && untruth->dispfrag == lie->dispfrag;
 			       untruth = untruth->next_broken_word)
 			    if ((symbol_get_frag (untruth->add)
@@ -2243,6 +2251,8 @@ relax_segment (struct frag *segment_frag
 				untruth->added = 2;
 				untruth->use_jump = lie;
 			      }
+
+			  lie->added = 1;
 			  growth += md_long_jump_size;
 			}
 		    }
Index: testsuite/gas/cris/rd-bkw4.s
===================================================================
RCS file: testsuite/gas/cris/rd-bkw4.s
diff -N testsuite/gas/cris/rd-bkw4.s
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gas/cris/rd-bkw4.s	10 Mar 2009 04:20:51 -0000
@@ -0,0 +1,45 @@
+	.text
+	.align 1
+	.global x
+	.type	x,@function
+x:
+	.word .L1820-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L2617-.
+	.word .L2617-.
+	.word .L2617-.
+	.word .L2617-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L2617-.
+	.word .L2617-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L2617-.
+	.word .L2617-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L2617-.
+	.word .L2617-.
+	.word .L1820-.
+	.word .L1820-.
+	.word .L2617-.
+	.word .L1820-.
+	.word .L2617-.
+
+	.fill 19086
+.L2617:
+	move.d x336,$r9
+	jsr y
+
+	.fill 13618
+.L1820:
+	nop
+	.size	x,.-x
+	.align 1
Index: testsuite/gas/cris/rd-bkw4.d
===================================================================
RCS file: testsuite/gas/cris/rd-bkw4.d
diff -N testsuite/gas/cris/rd-bkw4.d
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gas/cris/rd-bkw4.d	10 Mar 2009 04:20:51 -0000
@@ -0,0 +1,51 @@
+#as: --underscore --em=criself
+#objdump: -dr
+
+.*:     file format .*-cris
+
+Disassembly of section \.text:
+
+0+ <x>:
+       0:	ce4a .*
+       2:	cc4a .*
+       4:	ca4a .*
+       6:	c84a .*
+       8:	c64a .*
+       a:	c44a .*
+       c:	c24a .*
+       e:	c04a .*
+      10:	c44a .*
+      12:	c24a .*
+      14:	c04a .*
+      16:	be4a .*
+      18:	b64a .*
+      1a:	b44a .*
+      1c:	b84a .*
+      1e:	b64a .*
+      20:	ae4a .*
+      22:	ac4a .*
+      24:	b04a .*
+      26:	ae4a .*
+      28:	a64a .*
+      2a:	a44a .*
+      2c:	a84a .*
+      2e:	a64a .*
+      30:	9e4a .*
+      32:	9c4a .*
+      34:	a04a .*
+      36:	984a .*
+      38:	9c4a .*
+	\.\.\.
+    4ac6:	0000                	bcc \.\+2
+    4ac8:	0ae0                	ba 4ad4 <x\+0x4ad4>
+    4aca:	0f05                	nop 
+    4acc:	0f05                	nop 
+    4ace:	ffed 4035           	ba 8012 <x\+0x8012>
+    4ad2:	0f05                	nop 
+    4ad4:	6f9e 0000 0000      	move\.d 0 <x>,r9
+			4ad6: R_CRIS_32	x336
+    4ada:	3fbd 0000 0000      	jsr 0 <x>
+			4adc: R_CRIS_32	y
+	\.\.\.
+    8010:	0000                	bcc \.\+2
+    8012:	0f05                	nop 
Index: testsuite/gas/cris/rd-bkw4v32.d
===================================================================
RCS file: testsuite/gas/cris/rd-bkw4v32.d
diff -N testsuite/gas/cris/rd-bkw4v32.d
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gas/cris/rd-bkw4v32.d	10 Mar 2009 04:20:51 -0000
@@ -0,0 +1,54 @@
+#as: --underscore --em=criself --march=v32
+#source: rd-bkw4.s
+#objdump: -dr
+
+.*:     file format .*-cris
+
+Disassembly of section \.text:
+
+0+ <x>:
+       0:	ce4a .*
+       2:	cc4a .*
+       4:	ca4a .*
+       6:	c84a .*
+       8:	c64a .*
+       a:	c44a .*
+       c:	c24a .*
+       e:	c04a .*
+      10:	c64a .*
+      12:	c44a .*
+      14:	c24a .*
+      16:	c04a .*
+      18:	b64a .*
+      1a:	b44a .*
+      1c:	ba4a .*
+      1e:	b84a .*
+      20:	ae4a .*
+      22:	ac4a .*
+      24:	b24a .*
+      26:	b04a .*
+      28:	a64a .*
+      2a:	a44a .*
+      2c:	aa4a .*
+      2e:	a84a .*
+      30:	9e4a .*
+      32:	9c4a .*
+      34:	a24a .*
+      36:	984a .*
+      38:	9e4a .*
+	\.\.\.
+    4ac6:	0000                	bcc \.
+    4ac8:	0ee0                	ba 4ad6 <x\+0x4ad6>
+    4aca:	b005                	nop 
+    4acc:	b005                	nop 
+    4ace:	ffed 4635           	ba 8014 <x\+0x8014>
+    4ad2:	b005                	nop 
+    4ad4:	0000                	bcc \.
+    4ad6:	6f9e 0000 0000      	move.d 0 <x>,r9
+			4ad8: R_CRIS_32	x336
+    4adc:	bfbd 0000 0000      	jsr 0 <x>
+			4ade: R_CRIS_32	y
+	\.\.\.
+    8012:	0000                	bcc \.
+    8014:	b005                	nop 
+	\.\.\.

brgds, H-P