* config/tc-mips.c (HAVE_IN_PLACE_ADDENDS): New macro.

	(reloc_needs_lo_p): Only return true if HAVE_IN_PLACE_ADDENDS.
	(mips_frob_file): Rework so that only a single pass through the
	relocs is needed.  Allow %lo()s to have higher offsets than their
	corresponding %hi()s or %got()s.

testsuite/
	* gas/mips/elf{,el}-rel.d: Adjust so that the earliest %hi() matches
	the earliest %lo().
	* gas/mips/elf-rel11.d: Don't expect the relocs to be reordered.
	* gas/mips/elf-rel20.[sd]: New test.
	* gas/mips/mips.exp: Run it.

9 files changed, 170 insertions, 80 deletions

diff --git a/gas/ChangeLog b/gas/ChangeLog
index 42968c0..50a3ac4 100644
--- a/gas/ChangeLog
+++ b/gas/ChangeLog
@@ -1,3 +1,11 @@
+2004-07-03  Richard Sandiford  <rsandifo@redhat.com>
+
+	* config/tc-mips.c (HAVE_IN_PLACE_ADDENDS): New macro.
+	(reloc_needs_lo_p): Only return true if HAVE_IN_PLACE_ADDENDS.
+	(mips_frob_file): Rework so that only a single pass through the
+	relocs is needed.  Allow %lo()s to have higher offsets than their
+	corresponding %hi()s or %got()s.
+
 2004-07-02  Nick Clifton  <nickc@redhat.com>
 
 	* config/tc-arm.c (md_apply_fix3:BFD_RELOC_ARM_IMMEDIATE): Do not
diff --git a/gas/config/tc-mips.c b/gas/config/tc-mips.c
index b7a6081..c554ba1 100644
--- a/gas/config/tc-mips.c
+++ b/gas/config/tc-mips.c
@@ -279,6 +279,9 @@ static int mips_32bitmode = 0;
 
 #define HAVE_64BIT_OBJECTS (mips_abi == N64_ABI)
 
+/* True if relocations are stored in-place.  */
+#define HAVE_IN_PLACE_ADDENDS (!HAVE_NEWABI)
+
 /* We can only have 64bit addresses if the object file format supports it.  */
 #define HAVE_32BIT_ADDRESSES                           \
    (HAVE_32BIT_GPRS                                    \
@@ -1398,8 +1401,9 @@ md_assemble (char *str)
 static inline bfd_boolean
 reloc_needs_lo_p (bfd_reloc_code_real_type reloc)
 {
-  return (reloc == BFD_RELOC_HI16_S
-	  || reloc == BFD_RELOC_MIPS_GOT16);
+  return (HAVE_IN_PLACE_ADDENDS
+	  && (reloc == BFD_RELOC_HI16_S
+	      || reloc == BFD_RELOC_MIPS_GOT16));
 }
 
 /* Return true if the given fixup is followed by a matching R_MIPS_LO16
@@ -10670,10 +10674,53 @@ mips_frob_file_before_adjust (void)
 #endif
 }
 
-/* Sort any unmatched HI16_S relocs so that they immediately precede
-   the corresponding LO reloc.  This is called before md_apply_fix3 and
-   tc_gen_reloc.  Unmatched HI16_S relocs can only be generated by
-   explicit use of the %hi modifier.  */
+/* Sort any unmatched HI16 and GOT16 relocs so that they immediately precede
+   the corresponding LO16 reloc.  This is called before md_apply_fix3 and
+   tc_gen_reloc.  Unmatched relocs can only be generated by use of explicit
+   relocation operators.
+
+   For our purposes, a %lo() expression matches a %got() or %hi()
+   expression if:
+
+      (a) it refers to the same symbol; and
+      (b) the offset applied in the %lo() expression is no lower than
+	  the offset applied in the %got() or %hi().
+
+   (b) allows us to cope with code like:
+
+	lui	$4,%hi(foo)
+	lh	$4,%lo(foo+2)($4)
+
+   ...which is legal on RELA targets, and has a well-defined behaviour
+   if the user knows that adding 2 to "foo" will not induce a carry to
+   the high 16 bits.
+
+   When several %lo()s match a particular %got() or %hi(), we use the
+   following rules to distinguish them:
+
+     (1) %lo()s with smaller offsets are a better match than %lo()s with
+         higher offsets.
+
+     (2) %lo()s with no matching %got() or %hi() are better than those
+         that already have a matching %got() or %hi().
+
+     (3) later %lo()s are better than earlier %lo()s.
+
+   These rules are applied in order.
+
+   (1) means, among other things, that %lo()s with identical offsets are
+   chosen if they exist.
+
+   (2) means that we won't associate several high-part relocations with
+   the same low-part relocation unless there's no alternative.  Having
+   several high parts for the same low part is a GNU extension; this rule
+   allows careful users to avoid it.
+
+   (3) is purely cosmetic.  mips_hi_fixup_list is is in reverse order,
+   with the last high-part relocation being at the front of the list.
+   It therefore makes sense to choose the last matching low-part
+   relocation, all other things being equal.  It's also easier
+   to code that way.  */
 
 void
 mips_frob_file (void)
@@ -10683,7 +10730,8 @@ mips_frob_file (void)
   for (l = mips_hi_fixup_list; l != NULL; l = l->next)
     {
       segment_info_type *seginfo;
-      int pass;
+      bfd_boolean matched_lo_p;
+      fixS **hi_pos, **lo_pos, **pos;
 
       assert (reloc_needs_lo_p (l->fixp->fx_r_type));
 
@@ -10697,59 +10745,51 @@ mips_frob_file (void)
       if (fixup_has_matching_lo_p (l->fixp))
 	continue;
 
-      /* Look through the fixups for this segment for a matching %lo.
-         When we find one, move the %hi just in front of it.  We do
-         this in two passes.  In the first pass, we try to find a
-         unique %lo.  In the second pass, we permit multiple %hi
-         relocs for a single %lo (this is a GNU extension).  */
       seginfo = seg_info (l->seg);
-      for (pass = 0; pass < 2; pass++)
-	{
-	  fixS *f, *prev;
 
-	  prev = NULL;
-	  for (f = seginfo->fix_root; f != NULL; f = f->fx_next)
+      /* Set HI_POS to the position of this relocation in the chain.
+	 Set LO_POS to the position of the chosen low-part relocation.
+	 MATCHED_LO_P is true on entry to the loop if *POS is a low-part
+	 relocation that matches an immediately-preceding high-part
+	 relocation.  */
+      hi_pos = NULL;
+      lo_pos = NULL;
+      matched_lo_p = FALSE;
+      for (pos = &seginfo->fix_root; *pos != NULL; pos = &(*pos)->fx_next)
+	{
+	  if (*pos == l->fixp)
+	    hi_pos = pos;
+
+	  if ((*pos)->fx_r_type == BFD_RELOC_LO16
+	      && (*pos)->fx_addsy == l->fixp->fx_addsy
+	      && (*pos)->fx_offset >= l->fixp->fx_offset
+	      && (lo_pos == NULL
+		  || (*pos)->fx_offset < (*lo_pos)->fx_offset
+		  || (!matched_lo_p
+		      && (*pos)->fx_offset == (*lo_pos)->fx_offset)))
+	    lo_pos = pos;
+
+	  matched_lo_p = (reloc_needs_lo_p ((*pos)->fx_r_type)
+			  && fixup_has_matching_lo_p (*pos));
+	}
+
+      /* If we found a match, remove the high-part relocation from its
+	 current position and insert it before the low-part relocation.
+	 Make the offsets match so that fixup_has_matching_lo_p()
+	 will return true.
+
+	 We don't warn about unmatched high-part relocations since some
+	 versions of gcc have been known to emit dead "lui ...%hi(...)"
+	 instructions.  */
+      if (lo_pos != NULL)
+	{
+	  l->fixp->fx_offset = (*lo_pos)->fx_offset;
+	  if (l->fixp->fx_next != *lo_pos)
 	    {
-	      /* Check whether this is a %lo fixup which matches l->fixp.  */
-	      if (f->fx_r_type == BFD_RELOC_LO16
-		  && f->fx_addsy == l->fixp->fx_addsy
-		  && f->fx_offset == l->fixp->fx_offset
-		  && (pass == 1
-		      || prev == NULL
-		      || !reloc_needs_lo_p (prev->fx_r_type)
-		      || !fixup_has_matching_lo_p (prev)))
-		{
-		  fixS **pf;
-
-		  /* Move l->fixp before f.  */
-		  for (pf = &seginfo->fix_root;
-		       *pf != l->fixp;
-		       pf = &(*pf)->fx_next)
-		    assert (*pf != NULL);
-
-		  *pf = l->fixp->fx_next;
-
-		  l->fixp->fx_next = f;
-		  if (prev == NULL)
-		    seginfo->fix_root = l->fixp;
-		  else
-		    prev->fx_next = l->fixp;
-
-		  break;
-		}
-
-	      prev = f;
+	      *hi_pos = l->fixp->fx_next;
+	      l->fixp->fx_next = *lo_pos;
+	      *lo_pos = l->fixp;
 	    }
-
-	  if (f != NULL)
-	    break;
-
-#if 0 /* GCC code motion plus incomplete dead code elimination
-	 can leave a %hi without a %lo.  */
-	  if (pass == 1)
-	    as_warn_where (l->fixp->fx_file, l->fixp->fx_line,
-			   _("Unmatched %%hi reloc"));
-#endif
 	}
     }
 }
diff --git a/gas/testsuite/ChangeLog b/gas/testsuite/ChangeLog
index 0633e8e..206b718 100644
--- a/gas/testsuite/ChangeLog
+++ b/gas/testsuite/ChangeLog
@@ -1,3 +1,18 @@
+2004-07-03  Richard Sandiford  <rsandifo@redhat.com>
+
+	* config/tc-mips.c (HAVE_IN_PLACE_ADDENDS): New macro.
+	(reloc_needs_lo_p): Only return true if HAVE_IN_PLACE_ADDENDS.
+	(mips_frob_file): Rework so that only a single pass through the
+	relocs is needed.  Allow %lo()s to have higher offsets than their
+	corresponding %hi()s or %got()s.
+
+testsuite/
+	* gas/mips/elf{,el}-rel.d: Adjust so that the earliest %hi() matches
+	the earliest %lo().
+	* gas/mips/elf-rel11.d: Don't expect the relocs to be reordered.
+	* gas/mips/elf-rel20.[sd]: New test.
+	* gas/mips/mips.exp: Run it.
+
 2004-07-03  Maciej W. Rozycki  <macro@linux-mips.org>
 
 	* gas/mips/elf-rel9.[sd]: Fix typo in %lo() expression.
diff --git a/gas/testsuite/gas/mips/elf-rel.d b/gas/testsuite/gas/mips/elf-rel.d
index ebc30a0..d6cee3c 100644
--- a/gas/testsuite/gas/mips/elf-rel.d
+++ b/gas/testsuite/gas/mips/elf-rel.d
@@ -22,27 +22,27 @@ OFFSET [ ]+ TYPE              VALUE
 0+000002c R_MIPS_LO16       \.text
 0+0000030 R_MIPS_HI16       \.text
 0+0000048 R_MIPS_LO16       \.text
-0+0000064 R_MIPS_HI16       \.text
+0+0000034 R_MIPS_HI16       \.text
 0+000004c R_MIPS_LO16       \.text
-0+0000068 R_MIPS_HI16       \.text
+0+0000038 R_MIPS_HI16       \.text
 0+0000050 R_MIPS_LO16       \.text
-0+000006c R_MIPS_HI16       \.text
+0+000003c R_MIPS_HI16       \.text
 0+0000054 R_MIPS_LO16       \.text
-0+0000074 R_MIPS_HI16       \.text
+0+0000044 R_MIPS_HI16       \.text
 0+0000058 R_MIPS_LO16       \.text
-0+0000070 R_MIPS_HI16       \.text
+0+0000040 R_MIPS_HI16       \.text
 0+000005c R_MIPS_LO16       \.text
 0+0000060 R_MIPS_HI16       \.text
 0+0000078 R_MIPS_LO16       \.text
-0+0000034 R_MIPS_HI16       \.text
+0+0000064 R_MIPS_HI16       \.text
 0+000007c R_MIPS_LO16       \.text
-0+0000038 R_MIPS_HI16       \.text
+0+0000068 R_MIPS_HI16       \.text
 0+0000080 R_MIPS_LO16       \.text
-0+000003c R_MIPS_HI16       \.text
+0+000006c R_MIPS_HI16       \.text
 0+0000084 R_MIPS_LO16       \.text
-0+0000044 R_MIPS_HI16       \.text
+0+0000074 R_MIPS_HI16       \.text
 0+0000088 R_MIPS_LO16       \.text
-0+0000040 R_MIPS_HI16       \.text
+0+0000070 R_MIPS_HI16       \.text
 0+000008c R_MIPS_LO16       \.text
 
 
diff --git a/gas/testsuite/gas/mips/elf-rel11.d b/gas/testsuite/gas/mips/elf-rel11.d
index 408795d..f776a8e 100644
--- a/gas/testsuite/gas/mips/elf-rel11.d
+++ b/gas/testsuite/gas/mips/elf-rel11.d
@@ -7,10 +7,10 @@ Relocation section '\.rela\.text' at offset .* contains 12 entries:
 0+0000 * 0+..0000001d * R_MIPS_HIGHEST * 0+0000 * bar \+ 0
  * Type2: R_MIPS_NONE *
  * Type3: R_MIPS_NONE *
-0+0008 * 0+..0000001c * R_MIPS_HIGHER * 0+0000 * bar \+ 0
+0+0004 * 0+..00000005 * R_MIPS_HI16 * 0+0000 * bar \+ 0
  * Type2: R_MIPS_NONE *
  * Type3: R_MIPS_NONE *
-0+0004 * 0+..00000005 * R_MIPS_HI16 * 0+0000 * bar \+ 0
+0+0008 * 0+..0000001c * R_MIPS_HIGHER * 0+0000 * bar \+ 0
  * Type2: R_MIPS_NONE *
  * Type3: R_MIPS_NONE *
 0+000c * 0+..00000006 * R_MIPS_LO16 * 0+0000 * bar \+ 0
@@ -19,10 +19,10 @@ Relocation section '\.rela\.text' at offset .* contains 12 entries:
 0+0018 * 0+..0000001d * R_MIPS_HIGHEST * 0+0000 * bar \+ 12345678
  * Type2: R_MIPS_NONE *
  * Type3: R_MIPS_NONE *
-0+0020 * 0+..0000001c * R_MIPS_HIGHER * 0+0000 * bar \+ 12345678
+0+001c * 0+..00000005 * R_MIPS_HI16 * 0+0000 * bar \+ 12345678
  * Type2: R_MIPS_NONE *
  * Type3: R_MIPS_NONE *
-0+001c * 0+..00000005 * R_MIPS_HI16 * 0+0000 * bar \+ 12345678
+0+0020 * 0+..0000001c * R_MIPS_HIGHER * 0+0000 * bar \+ 12345678
  * Type2: R_MIPS_NONE *
  * Type3: R_MIPS_NONE *
 0+0024 * 0+..00000006 * R_MIPS_LO16 * 0+0000 * bar \+ 12345678
diff --git a/gas/testsuite/gas/mips/elf-rel20.d b/gas/testsuite/gas/mips/elf-rel20.d
new file mode 100644
index 0000000..81129e3
--- /dev/null
+++ b/gas/testsuite/gas/mips/elf-rel20.d
@@ -0,0 +1,15 @@
+#as: -march=mips2 -mabi=32 -KPIC
+#readelf: --relocs
+#name: MIPS ELF reloc 20
+
+Relocation section '\.rel\.text' at offset .* contains 8 entries:
+ *Offset * Info * Type * Sym\.Value * Sym\. Name
+0+0000 * 0+..05 * R_MIPS_HI16 * 0+0000 * foo
+0+0010 * 0+..06 * R_MIPS_LO16 * 0+0000 * foo
+0+0004 * 0+..05 * R_MIPS_HI16 * 0+0000 * foo
+0+0014 * 0+..06 * R_MIPS_LO16 * 0+0000 * foo
+0+000c * 0+..05 * R_MIPS_HI16 * 0+0000 * \.bss
+0+0018 * 0+..06 * R_MIPS_LO16 * 0+0000 * \.bss
+0+0008 * 0+..05 * R_MIPS_HI16 * 0+0000 * \.bss
+0+001c * 0+..06 * R_MIPS_LO16 * 0+0000 * \.bss
+#pass
diff --git a/gas/testsuite/gas/mips/elf-rel20.s b/gas/testsuite/gas/mips/elf-rel20.s
new file mode 100644
index 0000000..799156d
--- /dev/null
+++ b/gas/testsuite/gas/mips/elf-rel20.s
@@ -0,0 +1,11 @@
+	lui	$4,%hi(foo)
+	lui	$5,%hi(foo + 0x80000)
+	lui	$7,%hi(bar + 0x80000)
+	lui	$6,%hi(bar)
+	addiu	$4,$4,%lo(foo + 2)
+	addiu	$5,$5,%lo(foo + 0x80004)
+	addiu	$6,$6,%lo(bar + 2)
+	addiu	$7,$7,%lo(bar + 0x80004)
+	.section .bss
+bar:
+	.space	0x80010
diff --git a/gas/testsuite/gas/mips/elfel-rel.d b/gas/testsuite/gas/mips/elfel-rel.d
index c9671f5..a597212 100644
--- a/gas/testsuite/gas/mips/elfel-rel.d
+++ b/gas/testsuite/gas/mips/elfel-rel.d
@@ -23,27 +23,27 @@ OFFSET [ ]+ TYPE              VALUE
 0+000002c R_MIPS_LO16       \.text
 0+0000030 R_MIPS_HI16       \.text
 0+0000048 R_MIPS_LO16       \.text
-0+0000064 R_MIPS_HI16       \.text
+0+0000034 R_MIPS_HI16       \.text
 0+000004c R_MIPS_LO16       \.text
-0+0000068 R_MIPS_HI16       \.text
+0+0000038 R_MIPS_HI16       \.text
 0+0000050 R_MIPS_LO16       \.text
-0+000006c R_MIPS_HI16       \.text
+0+000003c R_MIPS_HI16       \.text
 0+0000054 R_MIPS_LO16       \.text
-0+0000074 R_MIPS_HI16       \.text
+0+0000044 R_MIPS_HI16       \.text
 0+0000058 R_MIPS_LO16       \.text
-0+0000070 R_MIPS_HI16       \.text
+0+0000040 R_MIPS_HI16       \.text
 0+000005c R_MIPS_LO16       \.text
 0+0000060 R_MIPS_HI16       \.text
 0+0000078 R_MIPS_LO16       \.text
-0+0000034 R_MIPS_HI16       \.text
+0+0000064 R_MIPS_HI16       \.text
 0+000007c R_MIPS_LO16       \.text
-0+0000038 R_MIPS_HI16       \.text
+0+0000068 R_MIPS_HI16       \.text
 0+0000080 R_MIPS_LO16       \.text
-0+000003c R_MIPS_HI16       \.text
+0+000006c R_MIPS_HI16       \.text
 0+0000084 R_MIPS_LO16       \.text
-0+0000044 R_MIPS_HI16       \.text
+0+0000074 R_MIPS_HI16       \.text
 0+0000088 R_MIPS_LO16       \.text
-0+0000040 R_MIPS_HI16       \.text
+0+0000070 R_MIPS_HI16       \.text
 0+000008c R_MIPS_LO16       \.text
 
 
diff --git a/gas/testsuite/gas/mips/mips.exp b/gas/testsuite/gas/mips/mips.exp
index ef26fe1..311f152 100644
--- a/gas/testsuite/gas/mips/mips.exp
+++ b/gas/testsuite/gas/mips/mips.exp
@@ -660,6 +660,7 @@ if { [istarget mips*-*-*] } then {
 	    run_dump_test "elf-rel18"
 	}
 	run_dump_test "elf-rel19"
+	run_dump_test "elf-rel20"
 
 	if { !$no_mips16 } {
 	    run_dump_test "${tmips}mips${el}16-e"