PATCH: Support more than 2 relaxation passes

PATCH: Support more than 2 relaxation passes

[H. J. Lu]

I need to run more than 2 relaxation passes. This patch allows a
backend to have more than 2 relaxation passes.


H.J.
----
bfd/

2006-03-08  H.J. Lu  <hongjiu.lu@intel.com>

	* elfxx-ia64.c (elfNN_ia64_relax_section): Check relax_pass
	instead of need_relax_finalize.

include/

2006-03-08  H.J. Lu  <hongjiu.lu@intel.com>

	* bfdlink.h (bfd_link_info): Replace need_relax_finalize with
	relax_pass.

ld/

2006-03-08  H.J. Lu  <hongjiu.lu@intel.com>

	* emultempl/ia64elf.em: Set link_info.relax_pass to 2. Remove
	link_info.need_relax_finalize.

	* ldlang.c (relax_sections): New.
	(lang_process): Use. Call relax_sections link_info.relax_pass
	times.

	* ldmain.c (main): Set link_info.relax_pass to 1. Remove
	link_info.need_relax_finalize.

--- binutils/bfd/elfxx-ia64.c.relax	2006-03-08 09:54:49.000000000 -0800
+++ binutils/bfd/elfxx-ia64.c	2006-03-08 10:55:34.000000000 -0800
@@ -894,7 +894,7 @@ elfNN_ia64_relax_section (abfd, sec, lin
      the relax finalize pass.  */
   if ((sec->flags & SEC_RELOC) == 0
       || sec->reloc_count == 0
-      || (!link_info->need_relax_finalize
+      || (link_info->relax_pass == 1
 	  && sec->need_finalize_relax == 0))
     return TRUE;
 
@@ -938,7 +938,7 @@ elfNN_ia64_relax_section (abfd, sec, lin
 	case R_IA64_PCREL21F:
 	  /* In the finalize pass, all br relaxations are done. We can
 	     skip it. */
-	  if (!link_info->need_relax_finalize)
+	  if (link_info->relax_pass == 1)
 	    continue;
 	  is_branch = TRUE;
 	  break;
@@ -947,7 +947,7 @@ elfNN_ia64_relax_section (abfd, sec, lin
 	  /* We can't optimize brl to br before the finalize pass since
 	     br relaxations will increase the code size. Defer it to
 	     the finalize pass.  */
-	  if (link_info->need_relax_finalize)
+	  if (link_info->relax_pass == 0)
 	    {
 	      sec->need_finalize_relax = 1;
 	      continue;
@@ -960,7 +960,7 @@ elfNN_ia64_relax_section (abfd, sec, lin
 	  /* We can't relax ldx/mov before the finalize pass since
 	     br relaxations will increase the code size. Defer it to
 	     the finalize pass.  */
-	  if (link_info->need_relax_finalize)
+	  if (link_info->relax_pass == 0)
 	    {
 	      sec->need_finalize_relax = 1;
 	      continue;
@@ -1352,7 +1352,7 @@ elfNN_ia64_relax_section (abfd, sec, lin
 	}
     }
 
-  if (!link_info->need_relax_finalize)
+  if (link_info->relax_pass == 1)
     sec->need_finalize_relax = 0;
 
   *again = changed_contents || changed_relocs;
--- binutils/include/bfdlink.h.relax	2005-11-04 11:38:00.000000000 -0800
+++ binutils/include/bfdlink.h	2006-03-08 10:54:01.000000000 -0800
@@ -301,9 +301,6 @@ struct bfd_link_info
   /* TRUE if global symbols in discarded sections should be stripped.  */
   unsigned int strip_discarded: 1;
 
-  /* TRUE if the final relax pass is needed.  */
-  unsigned int need_relax_finalize: 1;
-
   /* TRUE if generating a position independent executable.  */
   unsigned int pie: 1;
 
@@ -398,6 +395,9 @@ struct bfd_link_info
      unloaded.  */
   const char *fini_function;
 
+  /* Number of relaxation passes.  */
+  int relax_pass;
+
   /* Non-zero if auto-import thunks for DATA items in pei386 DLLs
      should be generated/linked against.  Set to 1 if this feature
      is explicitly requested by the user, -1 if enabled by default.  */
--- binutils/ld/emultempl/ia64elf.em.relax	2005-05-16 11:04:41.000000000 -0700
+++ binutils/ld/emultempl/ia64elf.em	2006-03-08 10:54:09.000000000 -0800
@@ -32,7 +32,7 @@ static int itanium = 0;
 static void
 gld${EMULATION_NAME}_after_parse (void)
 {
-  link_info.need_relax_finalize = TRUE;
+  link_info.relax_pass = 2;
   bfd_elf${ELFSIZE}_ia64_after_parse (itanium);
 }
 
--- binutils/ld/ldlang.c.relax	2005-12-24 08:17:33.000000000 -0800
+++ binutils/ld/ldlang.c	2006-03-08 11:22:28.000000000 -0800
@@ -5384,6 +5384,35 @@ lang_gc_sections (void)
     bfd_gc_sections (output_bfd, &link_info);
 }
 
+static void
+relax_sections (void)
+{
+  /* Keep relaxing until bfd_relax_section gives up.  */
+  bfd_boolean relax_again;
+
+  do
+    {
+      relax_again = FALSE; 
+
+      /* Note: pe-dll.c does something like this also.  If you find
+	 you need to change this code, you probably need to change
+	 pe-dll.c also.  DJ  */
+
+      /* Do all the assignments with our current guesses as to
+	 section sizes.  */
+      lang_do_assignments ();
+
+      /* We must do this after lang_do_assignments, because it uses
+	 size.  */
+      lang_reset_memory_regions ();
+
+      /* Perform another relax pass - this time we know where the
+	 globals are, so can make a better guess.  */
+      lang_size_sections (&relax_again, FALSE);
+    }
+  while (relax_again);
+}
+
 void
 lang_process (void)
 {
@@ -5480,38 +5509,17 @@ lang_process (void)
   /* Now run around and relax if we can.  */
   if (command_line.relax)
     {
-      /* Keep relaxing until bfd_relax_section gives up.  */
-      bfd_boolean relax_again;
+      /* We may need more than one relaxation pass.  */
+      int i = link_info.relax_pass;
 
-      do
-	{
-	  relax_again = FALSE;
+      /* The backend can use it to determine the current pass.  */
+      link_info.relax_pass = 0;
 
-	  /* Note: pe-dll.c does something like this also.  If you find
-	     you need to change this code, you probably need to change
-	     pe-dll.c also.  DJ  */
-
-	  /* Do all the assignments with our current guesses as to
-	     section sizes.  */
-	  lang_do_assignments ();
-
-	  /* We must do this after lang_do_assignments, because it uses
-	     size.  */
-	  lang_reset_memory_regions ();
-
-	  /* Perform another relax pass - this time we know where the
-	     globals are, so can make a better guess.  */
-	  lang_size_sections (&relax_again, FALSE);
-
-	  /* If the normal relax is done and the relax finalize pass
-	     is not performed yet, we perform another relax pass.  */
-	  if (!relax_again && link_info.need_relax_finalize)
-	    {
-	      link_info.need_relax_finalize = FALSE;
-	      relax_again = TRUE;
-	    }
+      while (i--)
+	{
+	  relax_sections ();
+	  link_info.relax_pass++;
 	}
-      while (relax_again);
 
       /* Final extra sizing to report errors.  */
       lang_do_assignments ();
--- binutils/ld/ldmain.c.relax	2005-11-11 10:48:53.000000000 -0800
+++ binutils/ld/ldmain.c	2006-03-08 10:56:54.000000000 -0800
@@ -313,7 +313,7 @@ main (int argc, char **argv)
   link_info.spare_dynamic_tags = 5;
   link_info.flags = 0;
   link_info.flags_1 = 0;
-  link_info.need_relax_finalize = FALSE;
+  link_info.relax_pass = 1;
   link_info.warn_shared_textrel = FALSE;
   link_info.gc_sections = FALSE;
 

Re: PATCH: Support more than 2 relaxation passes

[James E Wilson]

On Wed, 2006-03-08 at 11:38, H. J. Lu wrote:
> I need to run more than 2 relaxation passes. This patch allows a
> backend to have more than 2 relaxation passes.

Why?
-- 
Jim Wilson, GNU Tools Support, http://www.specifix.com

RE: PATCH: Support more than 2 relaxation passes

[Dave Korn]

On 08 March 2006 20:09, James E Wilson wrote:

> On Wed, 2006-03-08 at 11:38, H. J. Lu wrote:
>> I need to run more than 2 relaxation passes. This patch allows a
>> backend to have more than 2 relaxation passes.
> 
> Why?


  I can't see any line of reasoning that suggests that the iterative process
of relaxation would necessarily converge after no more than two passes, so why
not?  Am I missing something that makes for a proof?


    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

Re: PATCH: Support more than 2 relaxation passes

[H. J. Lu]

On Wed, Mar 08, 2006 at 12:08:49PM -0800, James E Wilson wrote:
> On Wed, 2006-03-08 at 11:38, H. J. Lu wrote:
> > I need to run more than 2 relaxation passes. This patch allows a
> > backend to have more than 2 relaxation passes.
> 
> Why?

We like to relax "addl r1=@gpel(foo),gp" from GPREL22 to GPREL64I,
similar to br relaxation. We have 2 passes now, one for PCRELXXX
and the other for LOTFF22X, which may turn into GPREL22. We can't do
GPREL relaxation during PCRELXXX pass since gp may change due to
code increase. I am not sure if we can do GPREL relaxation with
LOTFF22X relaxation together since LOTFF22X may turn into GPREL
and GPREL relaxation will also increase code size. We are thinking
to add a 3rd optional pass for GPREL relaxation. Even if the code
size does increase, gp should be adjusted to compensate that without
GPREL overflow.


H.J.

RE: PATCH: Support more than 2 relaxation passes

[James E Wilson]

On Wed, 2006-03-08 at 12:22, Dave Korn wrote:
>   I can't see any line of reasoning that suggests that the iterative process
> of relaxation would necessarily converge after no more than two passes, so why
> not?  Am I missing something that makes for a proof?

There is the general principle here that we should never change the code
without a good reason, and HJ provided none.  I am not even going to
bother to look at a patch that contains no justification.

Also, there is the issue of why we need this change now, when apparently
it has never been a problem before.

Linker relaxation works differently than gcc/gas relaxation.  In gas,
relaxing means converting a long instruction into a shorter one, which
may in turn allow additional relaxing opportunities.  In gas, yes,
convergence may take multiple passes.  Same for gcc.

However, in the linker, we normally don't change code size when
relaxing.  That would require redoing many relocations.  It would also
mean that gas can't resolve many relocations, since the linker would
need to redo them.  This would be a mess.  There is also the additional
complication on IA-64 that we have 3-instruction bundles, which means we
would have to reschedule and rebundle the code if we deleted an
instruction.  This would be a very complicated mess.

So lets look at what the IA-64 linker can do.  We can convert br
instructions into brl if they are out of range.  This involves adding a
trampoline outside the current code section.  There is no change to the
size of the current code section; we just have a new code section
appended at the end.  Hence there is no need for multiple passes.

So maybe you are wondering why we need two.  This is because we can also
do something else.  We can convert some two-instruction gp-relative load
sequences into single instruction sequences.  This requires knowing the
offset between the code and the got, which is affected by the above br
to brl conversion, so it must be done in a second separate pass.  There
is no code size or got size change here, so everything can be done in a
single pass.  The conversion involves changing a load/move into a
load/nop, since we can't actually delete any instructions at this point.

So there is no reason for more than 2 relaxation passes for the IA-64
linker, and all other linkers only need 1 relaxation pass.
-- 
Jim Wilson, GNU Tools Support, http://www.specifix.com

RE: PATCH: Support more than 2 relaxation passes

[James E Wilson]

On Wed, 2006-03-08 at 12:48, James E Wilson wrote:
> So there is no reason for more than 2 relaxation passes for the IA-64
> linker, and all other linkers only need 1 relaxation pass.

Oops, I was too hasty.  It is possible that there might be multiple
iterations within a single relaxation pass.  I didn't check that. 
However, IA-64 needs two distinct and different relaxation passes, for
doing two different kinds of relaxation which can not be done at the
same time.
-- 
Jim Wilson, GNU Tools Support, http://www.specifix.com

PATCH: Optimize relaxation passes

[H. J. Lu]

On Wed, Mar 08, 2006 at 12:48:54PM -0800, James E Wilson wrote:
> On Wed, 2006-03-08 at 12:22, Dave Korn wrote:
> >   I can't see any line of reasoning that suggests that the iterative process
> > of relaxation would necessarily converge after no more than two passes, so why
> > not?  Am I missing something that makes for a proof?
> 
> There is the general principle here that we should never change the code
> without a good reason, and HJ provided none.  I am not even going to
> bother to look at a patch that contains no justification.
> 

This patch optimizes the relaxation passes for ia64. We don't need
to relax sections which don't have any R_IA64_PCREL21 relocations in
pass 0.


H.J.
----
bfd/

2006-03-10  H.J. Lu  <hongjiu.lu@intel.com>

	* elfxx-ia64.c (elfNN_ia64_relax_section): Skip unneeded pass
	with the skip_relax_pass_0 and need_relax_pass_1 bits in the
	section structure.

include/

2006-03-10  H.J. Lu  <hongjiu.lu@intel.com>

	* bfdlink.h (bfd_link_info): Replace need_relax_finalize with
	relax_pass.

ld/

2006-03-10  H.J. Lu  <hongjiu.lu@intel.com>

	* emultempl/ia64elf.em: Set link_info.relax_pass to 2. Remove
	link_info.need_relax_finalize.

	* ldlang.c (relax_sections): New.
	(lang_process): Use. Call relax_sections link_info.relax_pass
	times.

	* ldmain.c (main): Set link_info.relax_pass to 1. Remove
	link_info.need_relax_finalize.

--- binutils/bfd/elfxx-ia64.c.relax	2006-03-08 17:28:24.000000000 -0800
+++ binutils/bfd/elfxx-ia64.c	2006-03-10 11:17:50.000000000 -0800
@@ -852,6 +852,12 @@ elfNN_ia64_relax_brl (bfd_byte *contents
   bfd_putl64 (t0, hit_addr);
   bfd_putl64 (t1, hit_addr + 8);
 }
+
+/* Rename some of the generic section flags to better document how they
+   are used here.  */
+#define skip_relax_pass_0 need_finalize_relax
+#define need_relax_pass_1 has_gp_reloc
+
 \f
 /* These functions do relaxation for IA-64 ELF.  */
 
@@ -880,6 +886,8 @@ elfNN_ia64_relax_section (abfd, sec, lin
   bfd_boolean changed_contents = FALSE;
   bfd_boolean changed_relocs = FALSE;
   bfd_boolean changed_got = FALSE;
+  bfd_boolean skip_relax_pass_0 = TRUE;
+  bfd_boolean need_relax_pass_1 = FALSE;
   bfd_vma gp = 0;
 
   /* Assume we're not going to change any sizes, and we'll only need
@@ -894,8 +902,10 @@ elfNN_ia64_relax_section (abfd, sec, lin
      the relax finalize pass.  */
   if ((sec->flags & SEC_RELOC) == 0
       || sec->reloc_count == 0
-      || (!link_info->need_relax_finalize
-	  && sec->need_finalize_relax == 0))
+      || (link_info->relax_pass == 0
+	  && sec->skip_relax_pass_0 == 1)
+      || (link_info->relax_pass == 1
+	  && sec->need_relax_pass_1 == 0))
     return TRUE;
 
   symtab_hdr = &elf_tdata (abfd)->symtab_hdr;
@@ -938,8 +948,9 @@ elfNN_ia64_relax_section (abfd, sec, lin
 	case R_IA64_PCREL21F:
 	  /* In the finalize pass, all br relaxations are done. We can
 	     skip it. */
-	  if (!link_info->need_relax_finalize)
+	  if (link_info->relax_pass == 1)
 	    continue;
+	  skip_relax_pass_0 = FALSE;
 	  is_branch = TRUE;
 	  break;
 
@@ -947,9 +958,9 @@ elfNN_ia64_relax_section (abfd, sec, lin
 	  /* We can't optimize brl to br before the finalize pass since
 	     br relaxations will increase the code size. Defer it to
 	     the finalize pass.  */
-	  if (link_info->need_relax_finalize)
+	  if (link_info->relax_pass == 0)
 	    {
-	      sec->need_finalize_relax = 1;
+	      need_relax_pass_1 = TRUE;
 	      continue;
 	    }
 	  is_branch = TRUE;
@@ -960,9 +971,9 @@ elfNN_ia64_relax_section (abfd, sec, lin
 	  /* We can't relax ldx/mov before the finalize pass since
 	     br relaxations will increase the code size. Defer it to
 	     the finalize pass.  */
-	  if (link_info->need_relax_finalize)
+	  if (link_info->relax_pass == 0)
 	    {
-	      sec->need_finalize_relax = 1;
+	      need_relax_pass_1 = TRUE;
 	      continue;
 	    }
 	  is_branch = FALSE;
@@ -1352,8 +1363,12 @@ elfNN_ia64_relax_section (abfd, sec, lin
 	}
     }
 
-  if (!link_info->need_relax_finalize)
-    sec->need_finalize_relax = 0;
+  if (link_info->relax_pass == 0)
+    {
+      /* Pass 0 is only needed to relax br.  */
+      sec->skip_relax_pass_0 = skip_relax_pass_0;
+      sec->need_relax_pass_1 = need_relax_pass_1;
+    }
 
   *again = changed_contents || changed_relocs;
   return TRUE;
@@ -1369,6 +1384,8 @@ elfNN_ia64_relax_section (abfd, sec, lin
     free (internal_relocs);
   return FALSE;
 }
+#undef skip_relax_pass_0
+#undef need_relax_pass_1
 
 static void
 elfNN_ia64_relax_ldxmov (contents, off)
--- binutils/include/bfdlink.h.relax	2005-11-04 11:38:00.000000000 -0800
+++ binutils/include/bfdlink.h	2006-03-10 10:16:53.000000000 -0800
@@ -301,9 +301,6 @@ struct bfd_link_info
   /* TRUE if global symbols in discarded sections should be stripped.  */
   unsigned int strip_discarded: 1;
 
-  /* TRUE if the final relax pass is needed.  */
-  unsigned int need_relax_finalize: 1;
-
   /* TRUE if generating a position independent executable.  */
   unsigned int pie: 1;
 
@@ -398,6 +395,9 @@ struct bfd_link_info
      unloaded.  */
   const char *fini_function;
 
+  /* Number of relaxation passes.  */
+  int relax_pass;
+
   /* Non-zero if auto-import thunks for DATA items in pei386 DLLs
      should be generated/linked against.  Set to 1 if this feature
      is explicitly requested by the user, -1 if enabled by default.  */
--- binutils/ld/emultempl/ia64elf.em.relax	2005-05-16 11:04:41.000000000 -0700
+++ binutils/ld/emultempl/ia64elf.em	2006-03-10 10:16:53.000000000 -0800
@@ -32,7 +32,7 @@ static int itanium = 0;
 static void
 gld${EMULATION_NAME}_after_parse (void)
 {
-  link_info.need_relax_finalize = TRUE;
+  link_info.relax_pass = 2;
   bfd_elf${ELFSIZE}_ia64_after_parse (itanium);
 }
 
--- binutils/ld/ldlang.c.relax	2005-12-24 08:17:33.000000000 -0800
+++ binutils/ld/ldlang.c	2006-03-10 10:16:53.000000000 -0800
@@ -5384,6 +5384,35 @@ lang_gc_sections (void)
     bfd_gc_sections (output_bfd, &link_info);
 }
 
+static void
+relax_sections (void)
+{
+  /* Keep relaxing until bfd_relax_section gives up.  */
+  bfd_boolean relax_again;
+
+  do
+    {
+      relax_again = FALSE; 
+
+      /* Note: pe-dll.c does something like this also.  If you find
+	 you need to change this code, you probably need to change
+	 pe-dll.c also.  DJ  */
+
+      /* Do all the assignments with our current guesses as to
+	 section sizes.  */
+      lang_do_assignments ();
+
+      /* We must do this after lang_do_assignments, because it uses
+	 size.  */
+      lang_reset_memory_regions ();
+
+      /* Perform another relax pass - this time we know where the
+	 globals are, so can make a better guess.  */
+      lang_size_sections (&relax_again, FALSE);
+    }
+  while (relax_again);
+}
+
 void
 lang_process (void)
 {
@@ -5480,38 +5509,17 @@ lang_process (void)
   /* Now run around and relax if we can.  */
   if (command_line.relax)
     {
-      /* Keep relaxing until bfd_relax_section gives up.  */
-      bfd_boolean relax_again;
+      /* We may need more than one relaxation pass.  */
+      int i = link_info.relax_pass;
 
-      do
-	{
-	  relax_again = FALSE;
+      /* The backend can use it to determine the current pass.  */
+      link_info.relax_pass = 0;
 
-	  /* Note: pe-dll.c does something like this also.  If you find
-	     you need to change this code, you probably need to change
-	     pe-dll.c also.  DJ  */
-
-	  /* Do all the assignments with our current guesses as to
-	     section sizes.  */
-	  lang_do_assignments ();
-
-	  /* We must do this after lang_do_assignments, because it uses
-	     size.  */
-	  lang_reset_memory_regions ();
-
-	  /* Perform another relax pass - this time we know where the
-	     globals are, so can make a better guess.  */
-	  lang_size_sections (&relax_again, FALSE);
-
-	  /* If the normal relax is done and the relax finalize pass
-	     is not performed yet, we perform another relax pass.  */
-	  if (!relax_again && link_info.need_relax_finalize)
-	    {
-	      link_info.need_relax_finalize = FALSE;
-	      relax_again = TRUE;
-	    }
+      while (i--)
+	{
+	  relax_sections ();
+	  link_info.relax_pass++;
 	}
-      while (relax_again);
 
       /* Final extra sizing to report errors.  */
       lang_do_assignments ();
--- binutils/ld/ldmain.c.relax	2005-11-11 10:48:53.000000000 -0800
+++ binutils/ld/ldmain.c	2006-03-10 10:16:53.000000000 -0800
@@ -313,7 +313,7 @@ main (int argc, char **argv)
   link_info.spare_dynamic_tags = 5;
   link_info.flags = 0;
   link_info.flags_1 = 0;
-  link_info.need_relax_finalize = FALSE;
+  link_info.relax_pass = 1;
   link_info.warn_shared_textrel = FALSE;
   link_info.gc_sections = FALSE;
 

Re: PATCH: Support more than 2 relaxation passes

[James E Wilson]

On Wed, 2006-03-08 at 12:36, H. J. Lu wrote:
> We like to relax "addl r1=@gpel(foo),gp" from GPREL22 to GPREL64I,
> similar to br relaxation.

It isn't clear to me what you are suggesting here.  You want to convert
an addl to a movl?  How can that work, and what benefit do we get from
it?  Or maybe you meant this the other way around?

Anyways, it is clear that you want a new kind of relaxation that may
conflict with the existing ones, but ...

> code increase. I am not sure if we can do GPREL relaxation with
> LOTFF22X relaxation together since LOTFF22X may turn into GPREL
> and GPREL relaxation will also increase code size.

So you don't actually know if the 3rd pass is necessary.  Perhaps you
should resubmit the patch when you do know for sure whether it is
necessary.
-- 
Jim Wilson, GNU Tools Support, http://www.specifix.com