RISC-V: Add R_RISCV_DELETE, which marks bytes for deletion

We currently delete bytes by shifting an entire BFD backwards to
overwrite the bytes we no longer need.  The result is that relaxing a
BFD is quadratic time.

This patch adds an additional relocation that specifies a byte range
that will be deleted from the final object file, and adds a relaxation
pass (between the existing passes that delete bytes and the alignment
pass) that actually deletes the bytes.  Note that deletion is still
quadratic time, and nothing uses R_RISCV_DELETE yet.

I've been meaning to go convert all the other relaxations to use
R_RISCV_DELETE and then make it faster, but this patch has been sitting
around for months so it looks like that won't happen for a bit.  The
PCREL->GPREL relaxation that comes next uses this, and since we've been
using these two patches out of tree since I wrote them months ago I
figure it's better to just get them in now.  I (or someone else :)) can
convert all the relocations later...

R_RISCV_DELETE will never be emitted into ELF objects, so therefor isn't
exposed to the rest of binutils.  As such, we're not considering this as
part of the ABI.

bfd/ChangeLog

2017-10-19  Palmer Dabbelt  <palmer@dabbelt.com>

        * elfnn-riscv (R_RISCV_DELETE): New define.
        (_bfd_riscv_relax_delete): New function.
        (perform_relocation): Handle R_RISCV_DELETE.
        (_bfd_riscv_relax_section): Likewise.

ld/ChangeLog

2017-10-19  Palmer Dabbelt  <palmer@dabbelt.com>

        * emultempl/riscvelf.em (riscv_elf_before_allocation): Add a
        third relaxation pass.

4 files changed, 46 insertions, 4 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index 959cf06..772f526 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,10 @@
+2017-10-19  Palmer Dabbelt  <palmer@dabbelt.com>
+
+	* elfnn-riscv.c (R_RISCV_DELETE): New define.
+	(_bfd_riscv_relax_delete): New function.
+	(perform_relocation): Handle R_RISCV_DELETE.
+	(_bfd_riscv_relax_section): Likewise.
+
 2017-10-19  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR ld/22263
diff --git a/bfd/elfnn-riscv.c b/bfd/elfnn-riscv.c
index d28cabd..bd88ed7 100644
--- a/bfd/elfnn-riscv.c
+++ b/bfd/elfnn-riscv.c
@@ -32,6 +32,9 @@
 #include "elf/riscv.h"
 #include "opcode/riscv.h"
 
+/* Internal relocations used exclusively by the relaxation pass.  */
+#define R_RISCV_DELETE (R_RISCV_max + 1)
+
 #define ARCH_SIZE NN
 
 #define MINUS_ONE ((bfd_vma)0 - 1)
@@ -1483,6 +1486,9 @@ perform_relocation (const reloc_howto_type *howto,
     case R_RISCV_TLS_DTPREL64:
       break;
 
+    case R_RISCV_DELETE:
+      return bfd_reloc_ok;
+
     default:
       return bfd_reloc_notsupported;
     }
@@ -1805,6 +1811,7 @@ riscv_elf_relocate_section (bfd *output_bfd,
 	case R_RISCV_SET16:
 	case R_RISCV_SET32:
 	case R_RISCV_32_PCREL:
+	case R_RISCV_DELETE:
 	  /* These require no special handling beyond perform_relocation.  */
 	  break;
 
@@ -2947,8 +2954,28 @@ _bfd_riscv_relax_align (bfd *abfd, asection *sec,
 				   rel->r_addend - nop_bytes);
 }
 
-/* Relax a section.  Pass 0 shortens code sequences unless disabled.
-   Pass 1, which cannot be disabled, handles code alignment directives.  */
+/* Relax PC-relative references to GP-relative references.  */
+
+static bfd_boolean
+_bfd_riscv_relax_delete (bfd *abfd,
+			 asection *sec,
+			 asection *sym_sec ATTRIBUTE_UNUSED,
+			 struct bfd_link_info *link_info ATTRIBUTE_UNUSED,
+			 Elf_Internal_Rela *rel,
+			 bfd_vma symval ATTRIBUTE_UNUSED,
+			 bfd_vma max_alignment ATTRIBUTE_UNUSED,
+			 bfd_vma reserve_size ATTRIBUTE_UNUSED,
+			 bfd_boolean *again ATTRIBUTE_UNUSED)
+{
+  if (!riscv_relax_delete_bytes(abfd, sec, rel->r_offset, rel->r_addend))
+    return FALSE;
+  rel->r_info = ELFNN_R_INFO(0, R_RISCV_NONE);
+  return TRUE;
+}
+
+/* Relax a section.  Pass 0 shortens code sequences unless disabled.  Pass 1
+   deletes the bytes that pass 0 made obselete.  Pass 2, which cannot be
+   disabled, handles code alignment directives.  */
 
 static bfd_boolean
 _bfd_riscv_relax_section (bfd *abfd, asection *sec,
@@ -3001,6 +3028,7 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
       int type = ELFNN_R_TYPE (rel->r_info);
       bfd_vma symval;
 
+      relax_func = NULL;
       if (info->relax_pass == 0)
 	{
 	  if (type == R_RISCV_CALL || type == R_RISCV_CALL_PLT)
@@ -3026,7 +3054,9 @@ _bfd_riscv_relax_section (bfd *abfd, asection *sec,
 	  /* Skip over the R_RISCV_RELAX.  */
 	  i++;
 	}
-      else if (type == R_RISCV_ALIGN)
+      else if (info->relax_pass == 1 && type == R_RISCV_DELETE)
+        relax_func = _bfd_riscv_relax_delete;
+      else if (info->relax_pass == 2 && type == R_RISCV_ALIGN)
 	relax_func = _bfd_riscv_relax_align;
       else
 	continue;
diff --git a/ld/ChangeLog b/ld/ChangeLog
index 7745a9c..586420a 100644
--- a/ld/ChangeLog
+++ b/ld/ChangeLog
@@ -1,3 +1,8 @@
+2017-10-19  Palmer Dabbelt  <palmer@dabbelt.com>
+
+	* emultempl/riscvelf.em (riscv_elf_before_allocation): Add a
+	third relaxation pass.
+
 2017-10-17  Alan Modra  <amodra@gmail.com>
 
 	* ld.texinfo (-z): Combine negative options with corresponding
diff --git a/ld/emultempl/riscvelf.em b/ld/emultempl/riscvelf.em
index 5fe93c2..3aa82da 100644
--- a/ld/emultempl/riscvelf.em
+++ b/ld/emultempl/riscvelf.em
@@ -39,7 +39,7 @@ riscv_elf_before_allocation (void)
   else
     ENABLE_RELAXATION;
 
-  link_info.relax_pass = 2;
+  link_info.relax_pass = 3;
 }
 
 static void