bpf: gas: support relaxation of V4 jump instructions

The BPF jump-always instruction (JA), like all other jump instructions
in the ISA, get a signed 16-bit displacement target argument denoted
in number of 64-bit words minus one.  This can sometimes be overflown.

The BPF V4 ISA thus introduced support for a jump-always
instruction (JAL) that gets a signed 32-bit displacement instead.

This patch makes the BPF assembler to perform the following
relaxations when the disp16 field gets overflown, unless the option
-mno-relax is specified:

  JA disp16  -> JAL disp32
  Jxx disp16 -> Jxx +1; JA +1; JAL disp32

Documentation and tests added.
Tested in bpf-unknown-none.

gas/ChangeLog:

2023-07-28  Jose E. Marchesi  <jose.marchesi@oracle.com>

	PR gas/30690
	* config/tc-bpf.c (struct bpf_insn): Add fields is_relaxable and
	relaxed_exp.
	(enum options): Add OPTION_NO_RELAX.
	(md_longopts): Likewise for -mno-relax.
	(do_relax): New global.
	(md_parse_option): Handle OPTION_NO_RELAX.
	(RELAX_BRANCH_ENCODE): Define.
	(RELAX_BRANCH_P): Likewise.
	(RELAX_BRANCH_LENGTH): Likewise.
	(RELAX_BRANCH_CONST): Likewise.
	(RELAX_BRANCH_UNCOND): Likewise.
	(relaxed_branch_length): New function.
	(md_estimate_size_before_relax): Likewise.
	(read_insn_word): Likewise.
	(encode_int16): Likewise.
	(encode_int32): Likewise.
	(write_insn_bytes): Likewise.
	(md_convert_frag): Likewise.
	(encode_insn): Likewise.
	(install_insn_fixups): Likewise.
	(add_fixed_insn): Likewise.
	(add_relaxed_insn): Likewise.
	(md_assemble): Move instruction encoding logic to the above
	new functions.
	* testsuite/gas/bpf/jump-relax-ja.d: New test.
	* testsuite/gas/bpf/jump-relax-ja-be.d: Likewise.
	* testsuite/gas/bpf/jump-relax-ja.s: And corresponding source.
	* testsuite/gas/bpf/jump-relax-jump.d: New test.
	* testsuite/gas/bpf/jump-relax-jump-be.d: Likewise.
	* testsuite/gas/bpf/jump-relax-jump.s: And corresponding source.
	* testsuite/gas/bpf/bpf.exp: Run new tests.
	* doc/c-bpf.texi (BPF Options): Document -mno-relax.

1 files changed, 712 insertions, 308 deletions

diff --git a/gas/config/tc-bpf.c b/gas/config/tc-bpf.c
index faa809c..969116b 100644
--- a/gas/config/tc-bpf.c
+++ b/gas/config/tc-bpf.c
@@ -51,6 +51,9 @@ struct bpf_insn
   unsigned int has_disp32 : 1;
   unsigned int has_imm32 : 1;
   unsigned int has_imm64 : 1;
+
+  unsigned int is_relaxable : 1;
+  expressionS *relaxed_exp;
 };
 
 const char comment_chars[]        = ";#";
@@ -120,6 +123,7 @@ enum options
   OPTION_XBPF,
   OPTION_DIALECT,
   OPTION_ISA_SPEC,
+  OPTION_NO_RELAX,
 };
 
 struct option md_longopts[] =
@@ -129,6 +133,7 @@ struct option md_longopts[] =
   { "mxbpf", no_argument, NULL, OPTION_XBPF },
   { "mdialect", required_argument, NULL, OPTION_DIALECT},
   { "misa-spec", required_argument, NULL, OPTION_ISA_SPEC},
+  { "mno-relax", no_argument, NULL, OPTION_NO_RELAX},
   { NULL,          no_argument, NULL, 0 },
 };
 
@@ -144,6 +149,11 @@ const char * md_shortopts = "";
 static int set_target_endian = 0;
 extern int target_big_endian;
 
+/* Whether to relax branch instructions.  Default is yes.  Can be
+   changed using the -mno-relax command line option.  */
+
+static int do_relax = 1;
+
 /* The ISA specification can be one of BPF_V1, BPF_V2, BPF_V3, BPF_V4
    or BPF_XPBF.  The ISA spec to use can be configured using
    command-line options.  It defaults to the latest BPF spec.  */
@@ -203,6 +213,9 @@ md_parse_option (int c, const char * arg)
       /* This is an alias for -misa-spec=xbpf.  */
       isa_spec = BPF_XBPF;
       break;
+    case OPTION_NO_RELAX:
+      do_relax = 0;
+      break;
     default:
       return 0;
     }
@@ -337,6 +350,151 @@ tc_gen_reloc (asection *sec ATTRIBUTE_UNUSED, fixS *fixP)
 }
 
 
+/* Relaxations supported by this assembler.  */
+
+#define RELAX_BRANCH_ENCODE(uncond, constant, length)    \
+  ((relax_substateT)                                     \
+   (0xc0000000                                           \
+    | ((uncond) ? 1 : 0)                                 \
+    | ((constant) ? 2 : 0)                               \
+    | ((length) << 2)))
+
+#define RELAX_BRANCH_P(i) (((i) & 0xf0000000) == 0xc0000000)
+#define RELAX_BRANCH_LENGTH(i) (((i) >> 2) & 0xff)
+#define RELAX_BRANCH_CONST(i) (((i) & 2) != 0)
+#define RELAX_BRANCH_UNCOND(i) (((i) & 1) != 0)
+
+
+/* Compute the length of a branch seuqence, and adjust the stored
+   length accordingly.  If FRAG is NULL, the worst-case length is
+   returned.  */
+
+static unsigned
+relaxed_branch_length (fragS *fragp, asection *sec, int update)
+{
+  int length, uncond;
+
+  if (!fragp)
+    return 8 * 3;
+
+  uncond = RELAX_BRANCH_UNCOND (fragp->fr_subtype);
+  length = RELAX_BRANCH_LENGTH (fragp->fr_subtype);
+
+  if (uncond)
+    /* Length is the same for both JA and JAL.  */
+    length = 8;
+  else
+    {
+      if (RELAX_BRANCH_CONST (fragp->fr_subtype))
+        {
+          int64_t val = fragp->fr_offset;
+
+          if (val < -32768 || val > 32767)
+            length =  8 * 3;
+          else
+            length = 8;
+        }
+      else if (fragp->fr_symbol != NULL
+          && S_IS_DEFINED (fragp->fr_symbol)
+          && !S_IS_WEAK (fragp->fr_symbol)
+          && sec == S_GET_SEGMENT (fragp->fr_symbol))
+        {
+          offsetT val = S_GET_VALUE (fragp->fr_symbol) + fragp->fr_offset;
+
+          /* Convert to 64-bit words, minus one.  */
+          val = (val - 8) / 8;
+
+          /* See if it fits in the signed 16-bits field.  */
+          if (val < -32768 || val > 32767)
+            length = 8 * 3;
+          else
+            length = 8;
+        }
+      else
+        /* Use short version, and let the linker relax instead, if
+           appropriate and if supported.  */
+        length = 8;
+    }
+
+  if (update)
+    fragp->fr_subtype = RELAX_BRANCH_ENCODE (uncond,
+                                             RELAX_BRANCH_CONST (fragp->fr_subtype),
+                                             length);
+
+  return length;
+}
+
+/* Estimate the size of a variant frag before relaxing.  */
+
+int
+md_estimate_size_before_relax (fragS *fragp, asection *sec)
+{
+  return (fragp->fr_var = relaxed_branch_length (fragp, sec, true));
+}
+
+/* Read a BPF instruction word from BUF.  */
+
+static uint64_t
+read_insn_word (bfd_byte *buf)
+{
+  return bfd_getb64 (buf);
+}
+
+/* Write the given signed 16-bit value in the given BUFFER using the
+   target endianness.  */
+
+static void
+encode_int16 (int16_t value, char *buffer)
+{
+  uint16_t val = value;
+
+  if (target_big_endian)
+    {
+      buffer[0] = (val >> 8) & 0xff;
+      buffer[1] = val & 0xff;
+    }
+  else
+    {
+      buffer[1] = (val >> 8) & 0xff;
+      buffer[0] = val & 0xff;
+    }
+}
+
+/* Write the given signed 32-bit value in the given BUFFER using the
+   target endianness.  */
+
+static void
+encode_int32 (int32_t value, char *buffer)
+{
+  uint32_t val = value;
+
+  if (target_big_endian)
+    {
+      buffer[0] = (val >> 24) & 0xff;
+      buffer[1] = (val >> 16) & 0xff;
+      buffer[2] = (val >> 8) & 0xff;
+      buffer[3] = val & 0xff;
+    }
+  else
+    {
+      buffer[3] = (val >> 24) & 0xff;
+      buffer[2] = (val >> 16) & 0xff;
+      buffer[1] = (val >> 8) & 0xff;
+      buffer[0] = value & 0xff;
+    }
+}
+
+/* Write a BPF instruction to BUF.  */
+
+static void
+write_insn_bytes (bfd_byte *buf, char *bytes)
+{
+  int i;
+
+  for (i = 0; i < 8; ++i)
+    md_number_to_chars ((char *) buf + i, (valueT) bytes[i], 1);
+}
+
 /* *FRAGP has been relaxed to its final size, and now needs to have
    the bytes inside it modified to conform to the new size.
 
@@ -347,17 +505,229 @@ tc_gen_reloc (asection *sec ATTRIBUTE_UNUSED, fixS *fixP)
 void
 md_convert_frag (bfd *abfd ATTRIBUTE_UNUSED,
 		 segT sec ATTRIBUTE_UNUSED,
-		 fragS *fragP ATTRIBUTE_UNUSED)
+		 fragS *fragp ATTRIBUTE_UNUSED)
 {
-  as_fatal (_("convert_frag called"));
-}
+  bfd_byte *buf = (bfd_byte *) fragp->fr_literal + fragp->fr_fix;
+  expressionS exp;
+  fixS *fixp;
+  bpf_insn_word word;
+  int disp_is_known = 0;
+  int64_t disp_to_target = 0;
 
-int
-md_estimate_size_before_relax (fragS *fragP ATTRIBUTE_UNUSED,
-                               segT segment ATTRIBUTE_UNUSED)
-{
-  as_fatal (_("estimate_size_before_relax called"));
-  return 0;
+  uint64_t code;
+
+  gas_assert (RELAX_BRANCH_P (fragp->fr_subtype));
+
+  /* Expression to be used in any resulting relocation in the relaxed
+     instructions.  */
+  exp.X_op = O_symbol;
+  exp.X_add_symbol = fragp->fr_symbol;
+  exp.X_add_number = fragp->fr_offset;
+
+  gas_assert (fragp->fr_var == RELAX_BRANCH_LENGTH (fragp->fr_subtype));
+
+  /* Read an instruction word from the instruction to be relaxed, and
+     get the code.  */
+  word = read_insn_word (buf);
+  code = (word >> 60) & 0xf;
+
+  /* Determine whether the 16-bit displacement to the target is known
+     at this point.  */
+  if (RELAX_BRANCH_CONST (fragp->fr_subtype))
+    {
+      /* XXX this loses the 32-bit value if the constant was
+         overflown! */
+      disp_to_target = fragp->fr_offset;
+      disp_is_known = 1;
+    }
+  else if (fragp->fr_symbol != NULL
+           && S_IS_DEFINED (fragp->fr_symbol)
+           && !S_IS_WEAK (fragp->fr_symbol)
+           && sec == S_GET_SEGMENT (fragp->fr_symbol))
+    {
+      offsetT val = S_GET_VALUE (fragp->fr_symbol) + fragp->fr_offset;
+      /* Convert to 64-bit blocks minus one.  */
+      disp_to_target = (val - 8) / 8;
+      disp_is_known = 1;
+    }
+
+  /* Now relax particular jump instructions.  */
+  if (code == BPF_CODE_JA)
+    {
+      /* Unconditional jump.
+         JA d16 -> JAL d32  */
+
+      gas_assert (RELAX_BRANCH_UNCOND (fragp->fr_subtype));
+
+      if (disp_is_known)
+        {
+          if (disp_to_target >= -32768 && disp_to_target <= 32767)
+            {
+              /* 16-bit disp is known and in range.  Install a fixup
+                 for the disp16 if the branch value is not constant.
+                 This will be resolved by the assembler and units
+                 converted.  */
+
+              if (!RELAX_BRANCH_CONST (fragp->fr_subtype))
+                {
+                  /* Install fixup for the JA.  */
+                  reloc_howto_type *reloc_howto
+                    = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_DISP16);
+                  if (!reloc_howto)
+                    abort();
+
+                  fixp = fix_new_exp (fragp, buf - (bfd_byte *) fragp->fr_literal,
+                                      bfd_get_reloc_size (reloc_howto),
+                                      &exp,
+                                      reloc_howto->pc_relative,
+                                      BFD_RELOC_BPF_DISP16);
+                  fixp->fx_file = fragp->fr_file;
+                  fixp->fx_line = fragp->fr_line;
+                }
+            }
+          else
+            {
+              /* 16-bit disp is known and not in range.  Turn the JA
+                 into a JAL with a 32-bit displacement.  */
+              char bytes[8];
+
+              bytes[0] = ((BPF_CLASS_JMP32|BPF_CODE_JA|BPF_SRC_K) >> 56) & 0xff;
+              bytes[1] = (word >> 48) & 0xff;
+              bytes[2] = 0; /* disp16 high */
+              bytes[3] = 0; /* disp16 lo */
+              encode_int32 ((int32_t) disp_to_target, bytes + 4);
+
+              write_insn_bytes (buf, bytes);
+            }
+        }
+      else
+        {
+          /* The displacement to the target is not known.  Do not
+             relax.  The linker will maybe do it if it chooses to.  */
+
+          reloc_howto_type *reloc_howto = NULL;
+
+          gas_assert (!RELAX_BRANCH_CONST (fragp->fr_subtype));
+
+          /* Install fixup for the JA.  */
+          reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_DISP16);
+          if (!reloc_howto)
+            abort ();
+
+          fixp = fix_new_exp (fragp, buf - (bfd_byte *) fragp->fr_literal,
+                              bfd_get_reloc_size (reloc_howto),
+                              &exp,
+                              reloc_howto->pc_relative,
+                              BFD_RELOC_BPF_DISP16);
+          fixp->fx_file = fragp->fr_file;
+          fixp->fx_line = fragp->fr_line;
+        }
+
+      buf += 8;
+    }
+  else
+    {
+      /* Conditional jump.
+         JXX d16 -> JXX +1; JA +1; JAL d32 */
+
+      gas_assert (!RELAX_BRANCH_UNCOND (fragp->fr_subtype));
+
+      if (disp_is_known)
+        {
+          if (disp_to_target >= -32768 && disp_to_target <= 32767)
+            {
+              /* 16-bit disp is known and in range.  Install a fixup
+                 for the disp16 if the branch value is not constant.
+                 This will be resolved by the assembler and units
+                 converted.  */
+
+              if (!RELAX_BRANCH_CONST (fragp->fr_subtype))
+                {
+                  /* Install fixup for the branch.  */
+                  reloc_howto_type *reloc_howto
+                    = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_DISP16);
+                  if (!reloc_howto)
+                    abort();
+
+                  fixp = fix_new_exp (fragp, buf - (bfd_byte *) fragp->fr_literal,
+                                      bfd_get_reloc_size (reloc_howto),
+                                      &exp,
+                                      reloc_howto->pc_relative,
+                                      BFD_RELOC_BPF_DISP16);
+                  fixp->fx_file = fragp->fr_file;
+                  fixp->fx_line = fragp->fr_line;
+                }
+
+              buf += 8;
+            }
+          else
+            {
+              /* 16-bit disp is known and not in range.  Turn the JXX
+                 into a sequence JXX +1; JA +1; JAL d32.  */
+
+              char bytes[8];
+
+              /* First, set the 16-bit offset in the current
+                 instruction to 1.  */
+
+              if (target_big_endian)
+                bfd_putb16 (1, buf + 2);
+              else
+                bfd_putl16 (1, buf + 2);
+              buf += 8;
+
+              /* Then, write the JA + 1  */
+
+              bytes[0] = 0x05; /* JA */
+              bytes[1] = 0x0;
+              encode_int16 (1, bytes + 2);
+              bytes[4] = 0x0;
+              bytes[5] = 0x0;
+              bytes[6] = 0x0;
+              bytes[7] = 0x0;
+              write_insn_bytes (buf, bytes);
+              buf += 8;
+
+              /* Finally, write the JAL to the target. */
+
+              bytes[0] = ((BPF_CLASS_JMP32|BPF_CODE_JA|BPF_SRC_K) >> 56) & 0xff;
+              bytes[1] = 0;
+              bytes[2] = 0;
+              bytes[3] = 0;
+              encode_int32 ((int32_t) disp_to_target, bytes + 4);
+              write_insn_bytes (buf, bytes);
+              buf += 8;
+            }
+        }
+      else
+        {
+          /* The displacement to the target is not known.  Do not
+             relax.  The linker will maybe do it if it chooses to.  */
+
+          reloc_howto_type *reloc_howto = NULL;
+
+          gas_assert (!RELAX_BRANCH_CONST (fragp->fr_subtype));
+
+          /* Install fixup for the conditional jump.  */
+          reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_DISP16);
+          if (!reloc_howto)
+            abort ();
+
+          fixp = fix_new_exp (fragp, buf - (bfd_byte *) fragp->fr_literal,
+                              bfd_get_reloc_size (reloc_howto),
+                              &exp,
+                              reloc_howto->pc_relative,
+                              BFD_RELOC_BPF_DISP16);
+          fixp->fx_file = fragp->fr_file;
+          fixp->fx_line = fragp->fr_line;
+          buf += 8;
+        }
+    }
+
+  gas_assert (buf == (bfd_byte *)fragp->fr_literal
+              + fragp->fr_fix + fragp->fr_var);
+
+  fragp->fr_fix += fragp->fr_var;
 }
 
 
@@ -460,6 +830,327 @@ md_apply_fix (fixS *fixP, valueT *valP, segT seg ATTRIBUTE_UNUSED)
   fixP->fx_addnumber = *valP;
 }
 
+
+/* Instruction writing routines.  */
+
+/* Encode a BPF instruction in the given buffer BYTES.  Non-constant
+   immediates are encoded as zeroes.  */
+
+static void
+encode_insn (struct bpf_insn *insn, char *bytes)
+{
+  uint8_t src, dst;
+
+  /* Zero all the bytes.  */
+  memset (bytes, 0, 16);
+
+  /* First encode the opcodes.  Note that we have to handle the
+     endianness groups of the BPF instructions: 8 | 4 | 4 | 16 |
+     32. */
+  if (target_big_endian)
+    {
+      /* code */
+      bytes[0] = (insn->opcode >> 56) & 0xff;
+      /* regs */
+      bytes[1] = (insn->opcode >> 48) & 0xff;
+      /* offset16 */
+      bytes[2] = (insn->opcode >> 40) & 0xff;
+      bytes[3] = (insn->opcode >> 32) & 0xff;
+      /* imm32 */
+      bytes[4] = (insn->opcode >> 24) & 0xff;
+      bytes[5] = (insn->opcode >> 16) & 0xff;
+      bytes[6] = (insn->opcode >> 8) & 0xff;
+      bytes[7] = insn->opcode & 0xff;
+    }
+  else
+    {
+      /* code */
+      bytes[0] = (insn->opcode >> 56) & 0xff;
+      /* regs */
+      bytes[1] = (((((insn->opcode >> 48) & 0xff) & 0xf) << 4)
+                  | (((insn->opcode >> 48) & 0xff) & 0xf));
+      /* offset16 */
+      bytes[3] = (insn->opcode >> 40) & 0xff;
+      bytes[2] = (insn->opcode >> 32) & 0xff;
+      /* imm32 */
+      bytes[7] = (insn->opcode >> 24) & 0xff;
+      bytes[6] = (insn->opcode >> 16) & 0xff;
+      bytes[5] = (insn->opcode >> 8) & 0xff;
+      bytes[4] = insn->opcode & 0xff;
+    }
+
+  /* Now the registers.  */
+  src = insn->has_src ? insn->src : 0;
+  dst = insn->has_dst ? insn->dst : 0;
+
+  if (target_big_endian)
+    bytes[1] = ((dst & 0xf) << 4) | (src & 0xf);
+  else
+    bytes[1] = ((src & 0xf) << 4) | (dst & 0xf);
+
+  /* Now the immediates that are known to be constant.  */
+
+  if (insn->has_imm32 && insn->imm32.X_op == O_constant)
+    encode_int32 (insn->imm32.X_add_number, bytes + 4);
+
+  if (insn->has_disp32 && insn->disp32.X_op == O_constant)
+    encode_int32 (insn->disp32.X_add_number, bytes + 4);
+
+  if (insn->has_offset16 && insn->offset16.X_op == O_constant)
+    encode_int16 (insn->offset16.X_add_number, bytes + 2);
+
+  if (insn->has_disp16 && insn->disp16.X_op == O_constant)
+    encode_int16 (insn->disp16.X_add_number, bytes + 2);
+
+  if (insn->has_imm64 && insn->imm64.X_op == O_constant)
+    {
+      uint64_t imm64 = insn->imm64.X_add_number;
+
+      if (target_big_endian)
+        {
+          bytes[12] = (imm64 >> 56) & 0xff;
+          bytes[13] = (imm64 >> 48) & 0xff;
+          bytes[14] = (imm64 >> 40) & 0xff;
+          bytes[15] = (imm64 >> 32) & 0xff;
+          bytes[4] = (imm64 >> 24) & 0xff;
+          bytes[5] = (imm64 >> 16) & 0xff;
+          bytes[6] = (imm64 >> 8) & 0xff;
+          bytes[7] = imm64 & 0xff;
+        }
+      else
+        {
+          bytes[15] = (imm64 >> 56) & 0xff;
+          bytes[14] = (imm64 >> 48) & 0xff;
+          bytes[13] = (imm64 >> 40) & 0xff;
+          bytes[12] = (imm64 >> 32) & 0xff;
+          bytes[7] = (imm64 >> 24) & 0xff;
+          bytes[6] = (imm64 >> 16) & 0xff;
+          bytes[5] = (imm64 >> 8) & 0xff;
+          bytes[4] = imm64 & 0xff;
+        }
+    }
+}
+
+/* Install the fixups in INSN in their proper location in the
+   specified FRAG at the location pointed by WHERE.  */
+
+static void
+install_insn_fixups (struct bpf_insn *insn, fragS *frag, long where)
+{
+  if (insn->has_imm64)
+    {
+      switch (insn->imm64.X_op)
+        {
+        case O_symbol:
+        case O_subtract:
+        case O_add:
+          {
+            reloc_howto_type *reloc_howto;
+            int size;
+
+            reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_64);
+            if (!reloc_howto)
+              abort ();
+
+            size = bfd_get_reloc_size (reloc_howto);
+
+            fix_new_exp (frag, where,
+                         size, &insn->imm64, reloc_howto->pc_relative,
+                         BFD_RELOC_BPF_64);
+            break;
+          }
+        case O_constant:
+          /* Already handled in encode_insn.  */
+          break;
+        default:
+          abort ();
+        }
+    }
+
+  if (insn->has_imm32)
+    {
+      switch (insn->imm32.X_op)
+        {
+        case O_symbol:
+        case O_subtract:
+        case O_add:
+        case O_uminus:
+          {
+            reloc_howto_type *reloc_howto;
+            int size;
+
+            reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_32);
+            if (!reloc_howto)
+              abort ();
+
+            size = bfd_get_reloc_size (reloc_howto);
+
+            fix_new_exp (frag, where + 4,
+                         size, &insn->imm32, reloc_howto->pc_relative,
+                         BFD_RELOC_32);
+            break;
+          }
+        case O_constant:
+          /* Already handled in encode_insn.  */
+          break;
+        default:
+          abort ();
+        }
+    }
+
+  if (insn->has_disp32)
+    {
+      switch (insn->disp32.X_op)
+        {
+        case O_symbol:
+        case O_subtract:
+        case O_add:
+          {
+            reloc_howto_type *reloc_howto;
+            int size;
+            unsigned int bfd_reloc
+              = (insn->id == BPF_INSN_CALL
+                 ? BFD_RELOC_BPF_DISPCALL32
+                 : BFD_RELOC_BPF_DISP32);
+
+            reloc_howto = bfd_reloc_type_lookup (stdoutput, bfd_reloc);
+            if (!reloc_howto)
+              abort ();
+
+            size = bfd_get_reloc_size (reloc_howto);
+
+            fix_new_exp (frag, where,
+                         size, &insn->disp32, reloc_howto->pc_relative,
+                         bfd_reloc);
+            break;
+          }
+        case O_constant:
+          /* Already handled in encode_insn.  */
+          break;
+        default:
+          abort ();
+        }
+    }
+
+  if (insn->has_offset16)
+    {
+      switch (insn->offset16.X_op)
+        {
+        case O_symbol:
+        case O_subtract:
+        case O_add:
+          {
+            reloc_howto_type *reloc_howto;
+            int size;
+
+            /* XXX we really need a new pc-rel offset in bytes
+               relocation for this.  */
+            reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_DISP16);
+            if (!reloc_howto)
+              abort ();
+
+            size = bfd_get_reloc_size (reloc_howto);
+
+            fix_new_exp (frag, where,
+                         size, &insn->offset16, reloc_howto->pc_relative,
+                         BFD_RELOC_BPF_DISP16);
+            break;
+          }
+        case O_constant:
+          /* Already handled in encode_insn.  */
+          break;
+        default:
+          abort ();
+        }
+    }
+
+  if (insn->has_disp16)
+    {
+      switch (insn->disp16.X_op)
+        {
+        case O_symbol:
+        case O_subtract:
+        case O_add:
+          {
+            reloc_howto_type *reloc_howto;
+            int size;
+
+            reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_DISP16);
+            if (!reloc_howto)
+              abort ();
+
+            size = bfd_get_reloc_size (reloc_howto);
+
+            fix_new_exp (frag, where,
+                         size, &insn->disp16, reloc_howto->pc_relative,
+                         BFD_RELOC_BPF_DISP16);
+            break;
+          }
+        case O_constant:
+          /* Already handled in encode_insn.  */
+          break;
+        default:
+          abort ();
+        }
+    }
+
+}
+
+/* Add a new insn to the list of instructions.  */
+
+static void
+add_fixed_insn (struct bpf_insn *insn)
+{
+  char *this_frag = frag_more (insn->size);
+  char bytes[16];
+  int i;
+
+  /* First encode the known parts of the instruction, including
+     opcodes and constant immediates, and write them to the frag.  */
+  encode_insn (insn, bytes);
+  for (i = 0; i < insn->size; ++i)
+    md_number_to_chars (this_frag + i, (valueT) bytes[i], 1);
+
+  /* Now install the instruction fixups.  */
+  install_insn_fixups (insn, frag_now,
+                       this_frag - frag_now->fr_literal);
+}
+
+/* Add a new relaxable to the list of instructions.  */
+
+static void
+add_relaxed_insn (struct bpf_insn *insn, expressionS *exp)
+{
+  char bytes[16];
+  int i;
+  char *this_frag;
+  unsigned worst_case = relaxed_branch_length (NULL, NULL, 0);
+  unsigned best_case = insn->size;
+
+  /* We only support relaxing branches, for the moment.  */
+  relax_substateT subtype
+    = RELAX_BRANCH_ENCODE (insn->id == BPF_INSN_JAR,
+                           exp->X_op == O_constant,
+                           worst_case);
+
+  frag_grow (worst_case);
+  this_frag = frag_more (0);
+
+  /* First encode the known parts of the instruction, including
+     opcodes and constant immediates, and write them to the frag.  */
+  encode_insn (insn, bytes);
+  for (i = 0; i < insn->size; ++i)
+    md_number_to_chars (this_frag + i, (valueT) bytes[i], 1);
+
+  /* Note that instruction fixups will be applied once the frag is
+     relaxed, in md_convert_frag.  */
+  frag_var (rs_machine_dependent,
+            worst_case, best_case,
+            subtype, exp->X_add_symbol, exp->X_add_number /* offset */,
+            NULL);
+}
+
+
 /* Parse an operand expression.  Returns the first character that is
    not part of the expression, or NULL in case of parse error.
 
@@ -781,6 +1472,7 @@ md_assemble (char *str ATTRIBUTE_UNUSED)
                       break;
                     }
                   insn.has_disp16 = 1;
+                  insn.is_relaxable = 1;
                   p += 4;
                 }
               else if (strncmp (p, "%d32", 4) == 0)
@@ -865,307 +1557,19 @@ md_assemble (char *str ATTRIBUTE_UNUSED)
 #undef PARSE_ERROR
 
   /* Generate the frags and fixups for the parsed instruction.  */
-  {
-    char *this_frag = frag_more (insn.size);
-    char bytes[16];
-    uint8_t src, dst;
-    int i;
-
-    /* Zero all the bytes.  */
-    memset (bytes, 0, 16);
-
-    /* First encode the opcodes.  Note that we have to handle the
-       endianness groups of the BPF instructions: 8 | 4 | 4 | 16 |
-       32. */
-    if (target_big_endian)
-      {
-        /* code */
-        bytes[0] = (insn.opcode >> 56) & 0xff;
-        /* regs */
-        bytes[1] = (insn.opcode >> 48) & 0xff;
-        /* offset16 */
-        bytes[2] = (insn.opcode >> 40) & 0xff;
-        bytes[3] = (insn.opcode >> 32) & 0xff;
-        /* imm32 */
-        bytes[4] = (insn.opcode >> 24) & 0xff;
-        bytes[5] = (insn.opcode >> 16) & 0xff;
-        bytes[6] = (insn.opcode >> 8) & 0xff;
-        bytes[7] = insn.opcode & 0xff;
-      }
-    else
-      {
-        /* code */
-        bytes[0] = (insn.opcode >> 56) & 0xff;
-        /* regs */
-        bytes[1] = (((((insn.opcode >> 48) & 0xff) & 0xf) << 4)
-                    | (((insn.opcode >> 48) & 0xff) & 0xf));
-        /* offset16 */
-        bytes[3] = (insn.opcode >> 40) & 0xff;
-        bytes[2] = (insn.opcode >> 32) & 0xff;
-        /* imm32 */
-        bytes[7] = (insn.opcode >> 24) & 0xff;
-        bytes[6] = (insn.opcode >> 16) & 0xff;
-        bytes[5] = (insn.opcode >> 8) & 0xff;
-        bytes[4] = insn.opcode & 0xff;
-      }
-
-    /* Now the registers.  */
-    src = insn.has_src ? insn.src : 0;
-    dst = insn.has_dst ? insn.dst : 0;
-
-    if (target_big_endian)
-      bytes[1] = ((dst & 0xf) << 4) | (src & 0xf);
-    else
-      bytes[1] = ((src & 0xf) << 4) | (dst & 0xf);
-
-    /* Now the immediates.  */
-    if (insn.has_imm64)
-      {
-        switch (insn.imm64.X_op)
-          {
-          case O_constant:
-            {
-              uint64_t imm64 = insn.imm64.X_add_number;
-
-              if (target_big_endian)
-                {
-                  bytes[12] = (imm64 >> 56) & 0xff;
-                  bytes[13] = (imm64 >> 48) & 0xff;
-                  bytes[14] = (imm64 >> 40) & 0xff;
-                  bytes[15] = (imm64 >> 32) & 0xff;
-                  bytes[4] = (imm64 >> 24) & 0xff;
-                  bytes[5] = (imm64 >> 16) & 0xff;
-                  bytes[6] = (imm64 >> 8) & 0xff;
-                  bytes[7] = imm64 & 0xff;
-                }
-              else
-                {
-                  bytes[15] = (imm64 >> 56) & 0xff;
-                  bytes[14] = (imm64 >> 48) & 0xff;
-                  bytes[13] = (imm64 >> 40) & 0xff;
-                  bytes[12] = (imm64 >> 32) & 0xff;
-                  bytes[7] = (imm64 >> 24) & 0xff;
-                  bytes[6] = (imm64 >> 16) & 0xff;
-                  bytes[5] = (imm64 >> 8) & 0xff;
-                  bytes[4] = imm64 & 0xff;
-                }
-              break;
-            }
-          case O_symbol:
-          case O_subtract:
-          case O_add:
-            {
-              reloc_howto_type *reloc_howto;
-              int size;
-
-              reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_64);
-              if (!reloc_howto)
-                abort ();
-
-              size = bfd_get_reloc_size (reloc_howto);
-
-              fix_new_exp (frag_now, this_frag - frag_now->fr_literal,
-                           size, &insn.imm64, reloc_howto->pc_relative,
-                           BFD_RELOC_BPF_64);
-              break;
-            }
-          default:
-            abort ();
-          }
-      }
-
-    if (insn.has_imm32)
-      {
-        switch (insn.imm32.X_op)
-          {
-          case O_constant:
-            {
-              uint32_t imm32 = insn.imm32.X_add_number;
-
-              if (target_big_endian)
-                {
-                  bytes[4] = (imm32 >> 24) & 0xff;
-                  bytes[5] = (imm32 >> 16) & 0xff;
-                  bytes[6] = (imm32 >> 8) & 0xff;
-                  bytes[7] = imm32 & 0xff;
-                }
-              else
-                {
-                  bytes[7] = (imm32 >> 24) & 0xff;
-                  bytes[6] = (imm32 >> 16) & 0xff;
-                  bytes[5] = (imm32 >> 8) & 0xff;
-                  bytes[4] = imm32 & 0xff;
-                }
-              break;
-            }
-          case O_symbol:
-          case O_subtract:
-          case O_add:
-          case O_uminus:
-            {
-              reloc_howto_type *reloc_howto;
-              int size;
-
-              reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_32);
-              if (!reloc_howto)
-                abort ();
-
-              size = bfd_get_reloc_size (reloc_howto);
-
-              fix_new_exp (frag_now, this_frag - frag_now->fr_literal + 4,
-                           size, &insn.imm32, reloc_howto->pc_relative,
-                           BFD_RELOC_32);
-              break;
-            }
-          default:
-            abort ();
-          }
-      }
-
-    if (insn.has_disp32)
-      {
-        switch (insn.disp32.X_op)
-          {
-          case O_constant:
-            {
-              uint32_t disp32 = insn.disp32.X_add_number;
-
-              if (target_big_endian)
-                {
-                  bytes[4] = (disp32 >> 24) & 0xff;
-                  bytes[5] = (disp32 >> 16) & 0xff;
-                  bytes[6] = (disp32 >> 8) & 0xff;
-                  bytes[7] = disp32 & 0xff;
-                }
-              else
-                {
-                  bytes[7] = (disp32 >> 24) & 0xff;
-                  bytes[6] = (disp32 >> 16) & 0xff;
-                  bytes[5] = (disp32 >> 8) & 0xff;
-                  bytes[4] = disp32 & 0xff;
-                }
-              break;
-            }
-          case O_symbol:
-          case O_subtract:
-          case O_add:
-            {
-              reloc_howto_type *reloc_howto;
-              int size;
-              unsigned int bfd_reloc
-                = (insn.id == BPF_INSN_CALL
-                   ? BFD_RELOC_BPF_DISPCALL32
-                   : BFD_RELOC_BPF_DISP32);
-
-              reloc_howto = bfd_reloc_type_lookup (stdoutput, bfd_reloc);
-              if (!reloc_howto)
-                abort ();
-
-              size = bfd_get_reloc_size (reloc_howto);
-
-              fix_new_exp (frag_now, this_frag - frag_now->fr_literal,
-                           size, &insn.disp32, reloc_howto->pc_relative,
-                           bfd_reloc);
-              break;
-            }
-          default:
-            abort ();
-          }
-      }
-
-    if (insn.has_offset16)
-      {
-        switch (insn.offset16.X_op)
-          {
-          case O_constant:
-            {
-              uint32_t offset16 = insn.offset16.X_add_number;
-
-              if (target_big_endian)
-                {
-                  bytes[2] = (offset16 >> 8) & 0xff;
-                  bytes[3] = offset16 & 0xff;
-                }
-              else
-                {
-                  bytes[3] = (offset16 >> 8) & 0xff;
-                  bytes[2] = offset16 & 0xff;
-                }
-              break;
-            }
-          case O_symbol:
-          case O_subtract:
-          case O_add:
-            {
-              reloc_howto_type *reloc_howto;
-              int size;
-
-              reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_DISP16);
-              if (!reloc_howto)
-                abort ();
-
-              size = bfd_get_reloc_size (reloc_howto);
-
-              fix_new_exp (frag_now, this_frag - frag_now->fr_literal,
-                           size, &insn.offset16, reloc_howto->pc_relative,
-                           BFD_RELOC_BPF_DISP16);
-              break;
-            }
-          default:
-            abort ();
-          }
-      }
-
-    if (insn.has_disp16)
-      {
-        switch (insn.disp16.X_op)
-          {
-          case O_constant:
-            {
-              uint32_t disp16 = insn.disp16.X_add_number;
-
-              if (target_big_endian)
-                {
-                  bytes[2] = (disp16 >> 8) & 0xff;
-                  bytes[3] = disp16 & 0xff;
-                }
-              else
-                {
-                  bytes[3] = (disp16 >> 8) & 0xff;
-                  bytes[2] = disp16 & 0xff;
-                }
-              break;
-            }
-          case O_symbol:
-          case O_subtract:
-          case O_add:
-            {
-              reloc_howto_type *reloc_howto;
-              int size;
-
-              reloc_howto = bfd_reloc_type_lookup (stdoutput, BFD_RELOC_BPF_DISP16);
-              if (!reloc_howto)
-                abort ();
+  if (do_relax && insn.is_relaxable)
+    {
+      expressionS *relaxable_exp = NULL;
 
-              size = bfd_get_reloc_size (reloc_howto);
+      if (insn.has_disp16)
+        relaxable_exp = &insn.disp16;
+      else
+        abort ();
 
-              fix_new_exp (frag_now, this_frag - frag_now->fr_literal,
-                           size, &insn.disp16, reloc_howto->pc_relative,
-                           BFD_RELOC_BPF_DISP16);
-              break;
-            }
-          default:
-            abort ();
-          }
-      }
-
-    /* Emit bytes.  */
-    for (i = 0; i < insn.size; ++i)
-      {
-        md_number_to_chars (this_frag, (valueT) bytes[i], 1);
-        this_frag += 1;
-      }
-  }
+      add_relaxed_insn (&insn, relaxable_exp);
+    }
+  else
+    add_fixed_insn (&insn);
 
   /* Emit DWARF2 debugging information.  */
   dwarf2_emit_insn (insn.size);