[committed] [PR target/93062] RISC-V: Handle long conditional branches for RISC-V

[committed] [PR target/93062] RISC-V: Handle long conditional branches for RISC-V

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 2034 bytes --]


Ventana has had a variant of this patch from Andrew W. in its tree for 
at least a year.   I'm dusting it off and submitting it on Andrew's behalf.

There's multiple approaches we could be using here.

First we could make $ra fixed and use it as the scratch register for the 
long branch sequences.

Second, we could add a match_scratch to all the conditional branch 
patterns and allow the register allocator to assign the scratch register 
from the pool of GPRs.

Third we could do register scavenging.  This can usually work, though it 
can get complex in some scenarios.

Forth we could use trampolines for extended reach.

Andrew's original patch did a bit of the first approach (make $ra fixed) 
and mostly the second approach.  The net is it was probably the worst in 
terms of impacting code generation -- we lost a register *and* forced 
every branch instruction to get a scratch register allocated.

I had expected the second approach to produce better code than the 
first, but that wasn't actually the case in practice.  It's probably a 
combination of allocating a GPR at every branch point (even with a life 
of a single insn, there's a cost) and perhaps the additional operands on 
conditional branches spoiling simplistic pattern matching in one or more 
passes.

In addition to performing better based on dynamic instruction counts, 
the first approach is significantly simpler to implement.  Given those 
two positives, that's what I've chosen to go with.  Yes it does remove 
$ra from the set of registers available, but the impact of that is *tiny*.

If someone wanted to dive into one of the other approaches to address a 
real world impact, that's great.  If that happens I would strongly 
suggest also evaluating perlbench from spec2017.  It seems particularly 
sensitive to this issue in terms of approach #2's impact on code generation.

I've built & regression tested this variant on the vt1 configuration 
without regressions.  Earlier versions have been bootstrapped as well.

Pushed to the trunk,

Jeff


[-- Attachment #2: P --]
[-- Type: text/plain, Size: 12433 bytes --]

commit 71f906498ada9ec2780660b03bd6e27a93ad350c
Author: Andrew Waterman <andrew@sifive.com>
Date:   Tue Oct 10 12:34:04 2023 -0600

    RISC-V: far-branch: Handle far jumps and branches for functions larger than 1MB
    
    On RISC-V, branches further than +/-1MB require a longer instruction
    sequence (3 instructions): we can reuse the jump-construction in the
    assmbler (which clobbers $ra) and a temporary to set up the jump
    destination.
    
    gcc/ChangeLog:
    
            * config/riscv/riscv.cc (struct machine_function): Track if a
            far-branch/jump is used within a function (and $ra needs to be
            saved).
            (riscv_print_operand): Implement 'N' (inverse integer branch).
            (riscv_far_jump_used_p): Implement.
            (riscv_save_return_addr_reg_p): New function.
            (riscv_save_reg_p): Use riscv_save_return_addr_reg_p.
            * config/riscv/riscv.h (FIXED_REGISTERS): Update $ra.
            (CALL_USED_REGISTERS): Update $ra.
            * config/riscv/riscv.md: Add new types "ret" and "jalr".
            (length attribute): Handle long conditional and unconditional
            branches.
            (conditional branch pattern): Handle case where jump can not
            reach the intended target.
            (indirect_jump, tablejump): Use new "jalr" type.
            (simple_return): Use new "ret" type.
            (simple_return_internal, eh_return_internal): Likewise.
            (gpr_restore_return, riscv_mret): Likewise.
            (riscv_uret, riscv_sret): Likewise.
            * config/riscv/generic.md (generic_branch): Also recognize jalr & ret
            types.
            * config/riscv/sifive-7.md (sifive_7_jump): Likewise.
    
    Co-authored-by: Philipp Tomsich <philipp.tomsich@vrull.eu>
    Co-authored-by: Jeff Law <jlaw@ventanamicro.com>

diff --git a/gcc/config/riscv/generic.md b/gcc/config/riscv/generic.md
index 57d3c3b4adc..88940483829 100644
--- a/gcc/config/riscv/generic.md
+++ b/gcc/config/riscv/generic.md
@@ -47,7 +47,7 @@ (define_insn_reservation "generic_xfer" 3
 
 (define_insn_reservation "generic_branch" 1
   (and (eq_attr "tune" "generic")
-       (eq_attr "type" "branch,jump,call"))
+       (eq_attr "type" "branch,jump,call,jalr"))
   "alu")
 
 (define_insn_reservation "generic_imul" 10
diff --git a/gcc/config/riscv/riscv.cc b/gcc/config/riscv/riscv.cc
index b7acf836d02..d17139e945e 100644
--- a/gcc/config/riscv/riscv.cc
+++ b/gcc/config/riscv/riscv.cc
@@ -183,6 +183,9 @@ struct GTY(())  machine_function {
   /* True if attributes on current function have been checked.  */
   bool attributes_checked_p;
 
+  /* True if RA must be saved because of a far jump.  */
+  bool far_jump_used;
+
   /* The current frame information, calculated by riscv_compute_frame_info.  */
   struct riscv_frame_info frame;
 
@@ -5448,6 +5451,7 @@ riscv_get_v_regno_alignment (machine_mode mode)
 	  any outermost HIGH.
    'R'	Print the low-part relocation associated with OP.
    'C'	Print the integer branch condition for comparison OP.
+   'N'	Print the inverse of the integer branch condition for comparison OP.
    'A'	Print the atomic operation suffix for memory model OP.
    'I'	Print the LR suffix for memory model OP.
    'J'	Print the SC suffix for memory model OP.
@@ -5604,6 +5608,11 @@ riscv_print_operand (FILE *file, rtx op, int letter)
       fputs (GET_RTX_NAME (code), file);
       break;
 
+    case 'N':
+      /* The RTL names match the instruction names. */
+      fputs (GET_RTX_NAME (reverse_condition (code)), file);
+      break;
+
     case 'A': {
       const enum memmodel model = memmodel_base (INTVAL (op));
       if (riscv_memmodel_needs_amo_acquire (model)
@@ -5873,6 +5882,64 @@ riscv_frame_set (rtx mem, rtx reg)
   return set;
 }
 
+/* Returns true if the current function might contain a far jump.  */
+
+static bool
+riscv_far_jump_used_p ()
+{
+  size_t func_size = 0;
+
+  if (cfun->machine->far_jump_used)
+    return true;
+
+  /* We can't change far_jump_used during or after reload, as there is
+     no chance to change stack frame layout.  So we must rely on the
+     conservative heuristic below having done the right thing.  */
+  if (reload_in_progress || reload_completed)
+    return false;
+
+  /* Estimate the function length.  */
+  for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
+    func_size += get_attr_length (insn);
+
+  /* Conservatively determine whether some jump might exceed 1 MiB
+     displacement.  */
+  if (func_size * 2 >= 0x100000)
+    cfun->machine->far_jump_used = true;
+
+  return cfun->machine->far_jump_used;
+}
+
+/* Return true, if the current function must save the incoming return
+   address.  */
+
+static bool
+riscv_save_return_addr_reg_p (void)
+{
+  /* The $ra register is call-clobbered: if this is not a leaf function,
+     save it.  */
+  if (!crtl->is_leaf)
+    return true;
+
+  /* We need to save the incoming return address if __builtin_eh_return
+     is being used to set a different return address.  */
+  if (crtl->calls_eh_return)
+    return true;
+
+  /* Far jumps/branches use $ra as a temporary to set up the target jump
+     location (clobbering the incoming return address).  */
+  if (riscv_far_jump_used_p ())
+    return true;
+
+  /* Need not to use ra for leaf when frame pointer is turned off by
+     option whatever the omit-leaf-frame's value.  */
+  if (frame_pointer_needed && crtl->is_leaf
+      && !TARGET_OMIT_LEAF_FRAME_POINTER)
+    return true;
+
+  return false;
+}
+
 /* Return true if the current function must save register REGNO.  */
 
 static bool
@@ -5893,11 +5960,7 @@ riscv_save_reg_p (unsigned int regno)
   if (regno == HARD_FRAME_POINTER_REGNUM && frame_pointer_needed)
     return true;
 
-  /* Need not to use ra for leaf when frame pointer is turned off by option
-     whatever the omit-leaf-frame's value.  */
-  bool keep_leaf_ra = frame_pointer_needed && crtl->is_leaf
-    && !TARGET_OMIT_LEAF_FRAME_POINTER;
-  if (regno == RETURN_ADDR_REGNUM && (crtl->calls_eh_return || keep_leaf_ra))
+  if (regno == RETURN_ADDR_REGNUM && riscv_save_return_addr_reg_p ())
     return true;
 
   /* If this is an interrupt handler, then must save extra registers.  */
diff --git a/gcc/config/riscv/riscv.h b/gcc/config/riscv/riscv.h
index 7ac78847b3a..f43ff10bc83 100644
--- a/gcc/config/riscv/riscv.h
+++ b/gcc/config/riscv/riscv.h
@@ -310,7 +310,7 @@ ASM_MISA_SPEC
 
 #define FIXED_REGISTERS							\
 { /* General registers.  */						\
-  1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,			\
+  1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,			\
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,			\
   /* Floating-point registers.  */					\
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,			\
@@ -328,7 +328,7 @@ ASM_MISA_SPEC
 
 #define CALL_USED_REGISTERS						\
 { /* General registers.  */						\
-  1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1,			\
+  1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1,			\
   1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1,			\
   /* Floating-point registers.  */					\
   1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1,			\
diff --git a/gcc/config/riscv/riscv.md b/gcc/config/riscv/riscv.md
index 307d4310dba..76bc4e760ff 100644
--- a/gcc/config/riscv/riscv.md
+++ b/gcc/config/riscv/riscv.md
@@ -282,7 +282,9 @@ (define_attr "ext_enabled" "no,yes"
 
 ;; Classification of each insn.
 ;; branch	conditional branch
-;; jump		unconditional jump
+;; jump		unconditional direct jump
+;; jalr		unconditional indirect jump
+;; ret		various returns, no arguments
 ;; call		unconditional call
 ;; load		load instruction(s)
 ;; fpload	floating point load
@@ -427,7 +429,7 @@ (define_attr "ext_enabled" "no,yes"
 ;; vmov         whole vector register move
 ;; vector       unknown vector instruction
 (define_attr "type"
-  "unknown,branch,jump,call,load,fpload,store,fpstore,
+  "unknown,branch,jump,jalr,ret,call,load,fpload,store,fpstore,
    mtc,mfc,const,arith,logical,shift,slt,imul,idiv,move,fmove,fadd,fmul,
    fmadd,fdiv,fcmp,fcvt,fsqrt,multi,auipc,sfb_alu,nop,trap,ghost,bitmanip,
    rotate,clmul,min,max,minu,maxu,clz,ctz,cpop,
@@ -513,11 +515,22 @@ (define_attr "enabled" "no,yes"
 ;; Length of instruction in bytes.
 (define_attr "length" ""
    (cond [
+	  ;; Branches further than +/- 1 MiB require three instructions.
 	  ;; Branches further than +/- 4 KiB require two instructions.
 	  (eq_attr "type" "branch")
 	  (if_then_else (and (le (minus (match_dup 0) (pc)) (const_int 4088))
 				  (le (minus (pc) (match_dup 0)) (const_int 4092)))
 	  (const_int 4)
+	  (if_then_else (and (le (minus (match_dup 0) (pc)) (const_int 1048568))
+				  (le (minus (pc) (match_dup 0)) (const_int 1048572)))
+	  (const_int 8)
+	  (const_int 12)))
+
+	  ;; Jumps further than +/- 1 MiB require two instructions.
+	  (eq_attr "type" "jump")
+	  (if_then_else (and (le (minus (match_dup 0) (pc)) (const_int 1048568))
+				  (le (minus (pc) (match_dup 0)) (const_int 1048572)))
+	  (const_int 4)
 	  (const_int 8))
 
 	  ;; Conservatively assume calls take two instructions (AUIPC + JALR).
@@ -2615,7 +2628,12 @@ (define_insn "*branch<mode>"
 	 (label_ref (match_operand 0 "" ""))
 	 (pc)))]
   ""
-  "b%C1\t%2,%z3,%0"
+{
+  if (get_attr_length (insn) == 12)
+    return "b%N1\t%2,%z3,1f; jump\t%l0,ra; 1:";
+
+  return "b%C1\t%2,%z3,%l0";
+}
   [(set_attr "type" "branch")
    (set_attr "mode" "none")])
 
@@ -2900,10 +2918,16 @@ (define_insn "*sle<u>_<X:mode><GPR:mode>"
 ;; Unconditional branches.
 
 (define_insn "jump"
-  [(set (pc)
-	(label_ref (match_operand 0 "" "")))]
+  [(set (pc) (label_ref (match_operand 0 "" "")))]
   ""
-  "j\t%l0"
+{
+  /* Hopefully this does not happen often as this is going
+     to clobber $ra and muck up the return stack predictors.  */
+  if (get_attr_length (insn) == 8)
+    return "call\t%l0";
+
+  return "j\t%l0";
+}
   [(set_attr "type"	"jump")
    (set_attr "mode"	"none")])
 
@@ -2923,7 +2947,7 @@ (define_insn "indirect_jump<mode>"
   [(set (pc) (match_operand:P 0 "register_operand" "l"))]
   ""
   "jr\t%0"
-  [(set_attr "type" "jump")
+  [(set_attr "type" "jalr")
    (set_attr "mode" "none")])
 
 (define_expand "tablejump"
@@ -2948,7 +2972,7 @@ (define_insn "tablejump<mode>"
    (use (label_ref (match_operand 1 "" "")))]
   ""
   "jr\t%0"
-  [(set_attr "type" "jump")
+  [(set_attr "type" "jalr")
    (set_attr "mode" "none")])
 
 ;;
@@ -3008,7 +3032,7 @@ (define_insn "simple_return"
 {
   return riscv_output_return ();
 }
-  [(set_attr "type"	"jump")
+  [(set_attr "type"	"jalr")
    (set_attr "mode"	"none")])
 
 ;; Normal return.
@@ -3018,7 +3042,7 @@ (define_insn "simple_return_internal"
    (use (match_operand 0 "pmode_register_operand" ""))]
   ""
   "jr\t%0"
-  [(set_attr "type"	"jump")
+  [(set_attr "type"	"jalr")
    (set_attr "mode"	"none")])
 
 ;; This is used in compiling the unwind routines.
@@ -3072,7 +3096,7 @@ (define_insn_and_split "eh_return_internal"
   "epilogue_completed"
   [(const_int 0)]
   "riscv_expand_epilogue (EXCEPTION_RETURN); DONE;"
-  [(set_attr "type" "jump")])
+  [(set_attr "type" "ret")])
 
 ;;
 ;;  ....................
@@ -3255,7 +3279,7 @@ (define_insn "gpr_restore_return"
    (const_int 0)]
   ""
   ""
-  [(set_attr "type" "jump")])
+  [(set_attr "type" "ret")])
 
 (define_insn "riscv_frcsr"
   [(set (match_operand:SI 0 "register_operand" "=r")
@@ -3297,21 +3321,21 @@ (define_insn "riscv_mret"
    (unspec_volatile [(const_int 0)] UNSPECV_MRET)]
   ""
   "mret"
-  [(set_attr "type" "jump")])
+  [(set_attr "type" "ret")])
 
 (define_insn "riscv_sret"
   [(return)
    (unspec_volatile [(const_int 0)] UNSPECV_SRET)]
   ""
   "sret"
-  [(set_attr "type" "jump")])
+  [(set_attr "type" "ret")])
 
 (define_insn "riscv_uret"
   [(return)
    (unspec_volatile [(const_int 0)] UNSPECV_URET)]
   ""
   "uret"
-  [(set_attr "type" "jump")])
+  [(set_attr "type" "ret")])
 
 (define_insn "stack_tie<mode>"
   [(set (mem:BLK (scratch))
diff --git a/gcc/config/riscv/sifive-7.md b/gcc/config/riscv/sifive-7.md
index 526278e46d4..a63394c8c58 100644
--- a/gcc/config/riscv/sifive-7.md
+++ b/gcc/config/riscv/sifive-7.md
@@ -44,7 +44,7 @@ (define_insn_reservation "sifive_7_sfb_alu" 2
 
 (define_insn_reservation "sifive_7_jump" 1
   (and (eq_attr "tune" "sifive_7")
-       (eq_attr "type" "jump,call"))
+       (eq_attr "type" "jump,call,jalr"))
   "sifive_7_B")
 
 (define_insn_reservation "sifive_7_mul" 3

Re: [committed] [PR target/93062] RISC-V: Handle long conditional branches for RISC-V

[Andrew Waterman]

I remembered another concern since we discussed this patch privately.
Using ra for long calls results in a sequence that will corrupt the
return-address stack.  Corrupting the RAS is potentially more costly
than mispredicting a branch, since it can result in a cascading
sequence of mispredictions as the program returns up the stack.  Of
course, if these long calls are dynamically quite rare, this isn't the
end of the world.  But it's always preferable to use a register other
than ra or t0 to avoid this performance reduction.  I know nothing
about the complexity of register scavenging, but it would be nice to
opportunistically use a scratch register (other than t0), falling back
to ra only when necessary.

Tangentially, I noticed the patch uses `jump label, ra' for far
branches but uses `call label' for far jumps.  These corrupt the RAS
in opposite ways (the former pops the RAS and the latter pushes it.
Any reason for using a different sequence in one than the other?



On Tue, Oct 10, 2023 at 3:11 PM Jeff Law <jlaw@ventanamicro.com> wrote:
>
>
> Ventana has had a variant of this patch from Andrew W. in its tree for
> at least a year.   I'm dusting it off and submitting it on Andrew's behalf.
>
> There's multiple approaches we could be using here.
>
> First we could make $ra fixed and use it as the scratch register for the
> long branch sequences.
>
> Second, we could add a match_scratch to all the conditional branch
> patterns and allow the register allocator to assign the scratch register
> from the pool of GPRs.
>
> Third we could do register scavenging.  This can usually work, though it
> can get complex in some scenarios.
>
> Forth we could use trampolines for extended reach.
>
> Andrew's original patch did a bit of the first approach (make $ra fixed)
> and mostly the second approach.  The net is it was probably the worst in
> terms of impacting code generation -- we lost a register *and* forced
> every branch instruction to get a scratch register allocated.
>
> I had expected the second approach to produce better code than the
> first, but that wasn't actually the case in practice.  It's probably a
> combination of allocating a GPR at every branch point (even with a life
> of a single insn, there's a cost) and perhaps the additional operands on
> conditional branches spoiling simplistic pattern matching in one or more
> passes.
>
> In addition to performing better based on dynamic instruction counts,
> the first approach is significantly simpler to implement.  Given those
> two positives, that's what I've chosen to go with.  Yes it does remove
> $ra from the set of registers available, but the impact of that is *tiny*.
>
> If someone wanted to dive into one of the other approaches to address a
> real world impact, that's great.  If that happens I would strongly
> suggest also evaluating perlbench from spec2017.  It seems particularly
> sensitive to this issue in terms of approach #2's impact on code generation.
>
> I've built & regression tested this variant on the vt1 configuration
> without regressions.  Earlier versions have been bootstrapped as well.
>
> Pushed to the trunk,
>
> Jeff
>

Re: [committed] [PR target/93062] RISC-V: Handle long conditional branches for RISC-V

[Jeff Law]

On 10/10/23 18:24, Andrew Waterman wrote:
> I remembered another concern since we discussed this patch privately.
> Using ra for long calls results in a sequence that will corrupt the
> return-address stack.
Yup.  We've actually got data on that internally, it's not showing up in 
a significant way in practice.


   I know nothing
> about the complexity of register scavenging, but it would be nice to
> opportunistically use a scratch register (other than t0), falling back
> to ra only when necessary.
The nice thing about making $ra fixed is some can add a register 
scavenging approach, then fall back to $ra if they're unable to find a 
register to reuse.

> 
> Tangentially, I noticed the patch uses `jump label, ra' for far
> branches but uses `call label' for far jumps.  These corrupt the RAS
> in opposite ways (the former pops the RAS and the latter pushes it.
> Any reason for using a different sequence in one than the other?
I'd noticed it as well -- that's the way it was in the patch that was 
already in Ventana's tree ;-)  My plan was to address that separately 
after dropping in enough infrastructure to allow me to force everything 
to be far branches for testing purposes.

jeff

Re: [committed] [PR target/93062] RISC-V: Handle long conditional branches for RISC-V

[Andrew Waterman]

On Tue, Oct 10, 2023 at 8:26 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 10/10/23 18:24, Andrew Waterman wrote:
> > I remembered another concern since we discussed this patch privately.
> > Using ra for long calls results in a sequence that will corrupt the
> > return-address stack.
> Yup.  We've actually got data on that internally, it's not showing up in
> a significant way in practice.
>
>
>    I know nothing
> > about the complexity of register scavenging, but it would be nice to
> > opportunistically use a scratch register (other than t0), falling back
> > to ra only when necessary.
> The nice thing about making $ra fixed is some can add a register
> scavenging approach, then fall back to $ra if they're unable to find a
> register to reuse.
>
> >
> > Tangentially, I noticed the patch uses `jump label, ra' for far
> > branches but uses `call label' for far jumps.  These corrupt the RAS
> > in opposite ways (the former pops the RAS and the latter pushes it.
> > Any reason for using a different sequence in one than the other?
> I'd noticed it as well -- that's the way it was in the patch that was
> already in Ventana's tree ;-)  My plan was to address that separately
> after dropping in enough infrastructure to allow me to force everything
> to be far branches for testing purposes.

Sounds like we're thinking many of the same thoughts... thanks for
dragging this patch towards the finish line!

>
> jeff