[PATCH v2 1/2] RISC-V: Add shorten_memrefs pass

[Craig Blackmore <craig.blackmore@embecosm.com>]

This patch aims to allow more load/store instructions to be compressed by
replacing a load/store of 'base register + large offset' with a new load/store
of 'new base + small offset'. If the new base gets stored in a compressed
register, then the new load/store can be compressed. Since there is an overhead
in creating the new base, this change is only attempted when 'base register' is
referenced in at least 4 load/stores in a basic block.

The optimization is implemented in a new RISC-V specific pass called
shorten_memrefs which is enabled for RVC targets. It has been developed for the
32-bit lw/sw instructions but could also be extended to 64-bit ld/sd in future.

Tested on bare metal rv32i, rv32iac, rv32im, rv32imac, rv32imafc, rv64imac,
rv64imafdc via QEMU. No regressions.

gcc/ChangeLog:

	* config.gcc: Add riscv-shorten-memrefs.o to extra_objs for riscv.
	* config/riscv/riscv-passes.def: New file.
	* config/riscv/riscv-protos.h (make_pass_shorten_memrefs): Declare.
	* config/riscv/riscv-shorten-memrefs.c: New file.
	* config/riscv/riscv.c (tree-pass.h): New include.
	(riscv_compressed_reg_p): New Function
	(riscv_compressed_lw_offset_p): Likewise.
	(riscv_compressed_lw_address_p): Likewise.
	(riscv_shorten_lw_offset): Likewise.
	(riscv_legitimize_address): Attempt to convert base + large_offset
        to compressible new_base + small_offset.
	(riscv_address_cost): Make anticipated compressed load/stores
        cheaper for code size than uncompressed load/stores.
	(riscv_register_priority): Move compressed register check to
        riscv_compressed_reg_p.
	* config/riscv/riscv.h (RISCV_MAX_COMPRESSED_LW_OFFSET): Define.
	* config/riscv/riscv.opt (mshorten-memefs): New option.
	* config/riscv/t-riscv (riscv-shorten-memrefs.o): New rule.
	(PASSES_EXTRA): Add riscv-passes.def.
	* doc/invoke.texi: Document -mshorten-memrefs.
---
 gcc/config.gcc                           |   2 +-
 gcc/config/riscv/riscv-passes.def        |  20 +++
 gcc/config/riscv/riscv-protos.h          |   2 +
 gcc/config/riscv/riscv-shorten-memrefs.c | 188 +++++++++++++++++++++++
 gcc/config/riscv/riscv.c                 |  86 ++++++++++-
 gcc/config/riscv/riscv.h                 |   5 +
 gcc/config/riscv/riscv.opt               |   6 +
 gcc/config/riscv/t-riscv                 |   5 +
 gcc/doc/invoke.texi                      |  10 ++
 9 files changed, 318 insertions(+), 6 deletions(-)
 create mode 100644 gcc/config/riscv/riscv-passes.def
 create mode 100644 gcc/config/riscv/riscv-shorten-memrefs.c

diff --git a/gcc/config.gcc b/gcc/config.gcc
index bdc2253f8ef..e617215314b 100644
--- a/gcc/config.gcc
+++ b/gcc/config.gcc
@@ -523,7 +523,7 @@ pru-*-*)
 	;;
 riscv*)
 	cpu_type=riscv
-	extra_objs="riscv-builtins.o riscv-c.o"
+	extra_objs="riscv-builtins.o riscv-c.o riscv-shorten-memrefs.o"
 	d_target_objs="riscv-d.o"
 	;;
 rs6000*-*-*)
diff --git a/gcc/config/riscv/riscv-passes.def b/gcc/config/riscv/riscv-passes.def
new file mode 100644
index 00000000000..8a4ea0918db
--- /dev/null
+++ b/gcc/config/riscv/riscv-passes.def
@@ -0,0 +1,20 @@
+/* Declaration of target-specific passes for RISC-V.
+   Copyright (C) 2019 Free Software Foundation, Inc.
+
+   This file is part of GCC.
+
+   GCC is free software; you can redistribute it and/or modify it
+   under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3, or (at your option)
+   any later version.
+
+   GCC is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with GCC; see the file COPYING3.  If not see
+   <http://www.gnu.org/licenses/>.  */
+
+INSERT_PASS_AFTER (pass_rtl_store_motion, 1, pass_shorten_memrefs);
diff --git a/gcc/config/riscv/riscv-protos.h b/gcc/config/riscv/riscv-protos.h
index 5092294803c..78008c28b75 100644
--- a/gcc/config/riscv/riscv-protos.h
+++ b/gcc/config/riscv/riscv-protos.h
@@ -89,4 +89,6 @@ extern void riscv_init_builtins (void);
 /* Routines implemented in riscv-common.c.  */
 extern std::string riscv_arch_str ();
 
+rtl_opt_pass * make_pass_shorten_memrefs (gcc::context *ctxt);
+
 #endif /* ! GCC_RISCV_PROTOS_H */
diff --git a/gcc/config/riscv/riscv-shorten-memrefs.c b/gcc/config/riscv/riscv-shorten-memrefs.c
new file mode 100644
index 00000000000..aed7ddb792e
--- /dev/null
+++ b/gcc/config/riscv/riscv-shorten-memrefs.c
@@ -0,0 +1,188 @@
+/* Shorten memrefs pass for RISC-V.
+   Copyright (C) 2018-2019 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#define IN_TARGET_CODE 1
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "backend.h"
+#include "regs.h"
+#include "target.h"
+#include "memmodel.h"
+#include "emit-rtl.h"
+#include "df.h"
+#include "predict.h"
+#include "tree-pass.h"
+
+/* Try to make more use of compressed load and store instructions by replacing
+   a load/store at address BASE + LARGE_OFFSET with a new load/store at address
+   NEW BASE + SMALL OFFSET.  If NEW BASE is stored in a compressed register, the
+   load/store can be compressed.  Since creating NEW BASE incurs an overhead,
+   the change is only attempted when BASE is referenced by at least four
+   load/stores in the same basic block.  */
+
+namespace {
+
+const pass_data pass_data_shorten_memrefs =
+{
+  RTL_PASS, /* type */
+  "shorten_memrefs", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_NONE, /* tv_id */
+  0, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_shorten_memrefs : public rtl_opt_pass
+{
+public:
+  pass_shorten_memrefs (gcc::context *ctxt)
+    : rtl_opt_pass (pass_data_shorten_memrefs, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *)
+    {
+      return TARGET_RVC && riscv_mshorten_memrefs && optimize > 0;
+    }
+  virtual unsigned int execute (function *);
+
+private:
+  typedef int_hash <HOST_WIDE_INT, 0> regno_hash;
+  typedef hash_map <regno_hash, int> regno_map;
+
+  regno_map * analyze (basic_block bb);
+  void transform (regno_map *m, basic_block bb);
+  bool get_si_mem_base_reg (rtx mem, rtx *addr);
+}; // class pass_shorten_memrefs
+
+bool
+pass_shorten_memrefs::get_si_mem_base_reg (rtx mem, rtx *addr)
+{
+  if (!MEM_P (mem) || GET_MODE (mem) != SImode)
+    return false;
+  *addr = XEXP (mem, 0);
+  return GET_CODE (*addr) == PLUS && REG_P (XEXP (*addr, 0));
+}
+
+/* Count how many times each regno is referenced as base address for a memory
+   access.  */
+
+pass_shorten_memrefs::regno_map *
+pass_shorten_memrefs::analyze (basic_block bb)
+{
+  regno_map *m = hash_map<regno_hash, int>::create_ggc (10);
+  rtx_insn *insn;
+
+  regstat_init_n_sets_and_refs ();
+
+  FOR_BB_INSNS (bb, insn)
+    {
+      if (!NONJUMP_INSN_P (insn))
+	continue;
+      rtx pat = PATTERN (insn);
+      if (GET_CODE (pat) != SET)
+	continue;
+      /* Analyze stores first then loads.  */
+      for (int i = 0; i < 2; i++)
+	{
+	  rtx mem = XEXP (pat, i);
+	  rtx addr;
+	  if (get_si_mem_base_reg (mem, &addr))
+	    {
+	      HOST_WIDE_INT regno = REGNO (XEXP (addr, 0));
+	      if (REG_N_REFS (regno) < 4)
+		continue;
+	      m->get_or_insert (regno)++;
+	    }
+	  }
+    }
+  regstat_free_n_sets_and_refs ();
+
+  return m;
+}
+
+/* Convert BASE + LARGE_OFFSET to NEW_BASE + SMALL_OFFSET for each load/store
+   with a base reg referenced at least 4 times.  */
+
+void
+pass_shorten_memrefs::transform (regno_map *m, basic_block bb)
+{
+  rtx_insn *insn;
+  FOR_BB_INSNS (bb, insn)
+    {
+      if (!NONJUMP_INSN_P (insn))
+	continue;
+      rtx pat = PATTERN (insn);
+      if (GET_CODE (pat) != SET)
+	continue;
+      start_sequence ();
+      /* Transform stores first then loads.  */
+      for (int i = 0; i < 2; i++)
+	{
+	  rtx mem = XEXP (pat, i);
+	  rtx addr;
+	  if (get_si_mem_base_reg (mem, &addr))
+	    {
+	      HOST_WIDE_INT regno = REGNO (XEXP (addr, 0));
+	      if (m->get_or_insert (regno) > 3)
+		{
+		  addr
+		    = targetm.legitimize_address (addr, addr, GET_MODE (mem));
+		  XEXP (pat, i) = replace_equiv_address (mem, addr);
+		  df_insn_rescan (insn);
+		}
+	    }
+	}
+      rtx_insn *seq = get_insns ();
+      end_sequence ();
+      emit_insn_before (seq, insn);
+    }
+}
+
+unsigned int
+pass_shorten_memrefs::execute (function *fn)
+{
+  basic_block bb;
+
+  FOR_ALL_BB_FN (bb, fn)
+  {
+    regno_map *m;
+    if (optimize_bb_for_speed_p (bb))
+      continue;
+    m = analyze (bb);
+    transform (m, bb);
+  }
+
+  return 0;
+}
+
+} // anon namespace
+
+rtl_opt_pass *
+make_pass_shorten_memrefs (gcc::context *ctxt)
+{
+  return new pass_shorten_memrefs (ctxt);
+}
diff --git a/gcc/config/riscv/riscv.c b/gcc/config/riscv/riscv.c
index 77a3ad94aa8..532eaa92632 100644
--- a/gcc/config/riscv/riscv.c
+++ b/gcc/config/riscv/riscv.c
@@ -55,6 +55,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "diagnostic.h"
 #include "builtins.h"
 #include "predict.h"
+#include "tree-pass.h"
 
 /* True if X is an UNSPEC wrapper around a SYMBOL_REF or LABEL_REF.  */
 #define UNSPEC_ADDRESS_P(X)					\
@@ -848,6 +849,52 @@ riscv_legitimate_address_p (machine_mode mode, rtx x, bool strict_p)
   return riscv_classify_address (&addr, x, mode, strict_p);
 }
 
+/* Return true if hard reg REGNO can be used in compressed instructions.  */
+
+static bool
+riscv_compressed_reg_p (int regno)
+{
+  /* x8-x15/f8-f15 are compressible registers.  */
+  return (TARGET_RVC && (IN_RANGE (regno, GP_REG_FIRST + 8, GP_REG_FIRST + 15)
+	  || IN_RANGE (regno, FP_REG_FIRST + 8, FP_REG_FIRST + 15)));
+}
+
+/* Return true if x is an unsigned 5-bit immediate scaled by 4.  */
+
+static bool
+riscv_compressed_lw_offset_p (rtx x)
+{
+  return CONST_INT_P (x)
+	 && (INTVAL (x) & 3) == 0
+	 && IN_RANGE (INTVAL (x), 0, RISCV_MAX_COMPRESSED_LW_OFFSET);
+}
+
+/* Return true if load/store from/to address x can be compressed.  */
+
+static bool
+riscv_compressed_lw_address_p (rtx x)
+{
+  struct riscv_address_info addr;
+  bool result = riscv_classify_address (&addr, x, GET_MODE (x),
+					reload_completed);
+
+  /* Before reload, assuming all load/stores of valid addresses get compressed
+     gives better code size than checking if the address is reg + small_offset
+     early on.  */
+  if (result && !reload_completed)
+    return true;
+
+  /* Return false if address is not compressed_reg + small_offset.  */
+  if (!result
+      || addr.type != ADDRESS_REG
+      || (!riscv_compressed_reg_p (REGNO (addr.reg))
+	    && addr.reg != stack_pointer_rtx)
+      || !riscv_compressed_lw_offset_p (addr.offset))
+    return false;
+
+  return result;
+}
+
 /* Return the number of instructions needed to load or store a value
    of mode MODE at address X.  Return 0 if X isn't valid for MODE.
    Assume that multiword moves may need to be split into word moves
@@ -1305,6 +1352,24 @@ riscv_force_address (rtx x, machine_mode mode)
   return x;
 }
 
+/* Modify base + offset so that offset fits within a compressed load/store insn
+   and the excess is added to base.  */
+
+static rtx
+riscv_shorten_lw_offset (rtx base, HOST_WIDE_INT offset)
+{
+  rtx addr, high;
+  /* Leave OFFSET as an unsigned 5-bit offset scaled by 4 and put the excess
+     into HIGH.  */
+  high = GEN_INT (offset & ~RISCV_MAX_COMPRESSED_LW_OFFSET);
+  offset &= RISCV_MAX_COMPRESSED_LW_OFFSET;
+  if (!SMALL_OPERAND (INTVAL (high)))
+    high = force_reg (Pmode, high);
+  base = force_reg (Pmode, gen_rtx_PLUS (Pmode, high, base));
+  addr = plus_constant (Pmode, base, offset);
+  return addr;
+}
+
 /* This function is used to implement LEGITIMIZE_ADDRESS.  If X can
    be legitimized in a way that the generic machinery might not expect,
    return a new address, otherwise return NULL.  MODE is the mode of
@@ -1323,7 +1388,7 @@ riscv_legitimize_address (rtx x, rtx oldx ATTRIBUTE_UNUSED,
   if (riscv_split_symbol (NULL, x, mode, &addr, FALSE))
     return riscv_force_address (addr, mode);
 
-  /* Handle BASE + OFFSET using riscv_add_offset.  */
+  /* Handle BASE + OFFSET.  */
   if (GET_CODE (x) == PLUS && CONST_INT_P (XEXP (x, 1))
       && INTVAL (XEXP (x, 1)) != 0)
     {
@@ -1332,7 +1397,14 @@ riscv_legitimize_address (rtx x, rtx oldx ATTRIBUTE_UNUSED,
 
       if (!riscv_valid_base_register_p (base, mode, false))
 	base = copy_to_mode_reg (Pmode, base);
-      addr = riscv_add_offset (NULL, base, offset);
+      if (optimize_function_for_size_p (cfun)
+	  && (strcmp (current_pass->name, "shorten_memrefs") == 0)
+	  && mode == SImode)
+	/* Convert BASE + LARGE_OFFSET into NEW_BASE + SMALL_OFFSET to allow
+	   possible compressed load/store.  */
+	addr = riscv_shorten_lw_offset (base, offset);
+      else
+	addr = riscv_add_offset (NULL, base, offset);
       return riscv_force_address (addr, mode);
     }
 
@@ -1822,6 +1894,9 @@ riscv_address_cost (rtx addr, machine_mode mode,
 		    addr_space_t as ATTRIBUTE_UNUSED,
 		    bool speed ATTRIBUTE_UNUSED)
 {
+  if (!speed && riscv_mshorten_memrefs && mode == SImode
+      && !riscv_compressed_lw_address_p (addr))
+    return riscv_address_insns (addr, mode, false) + 1;
   return riscv_address_insns (addr, mode, false);
 }
 
@@ -4647,6 +4722,7 @@ riscv_option_override (void)
     error ("%<-mriscv-attribute%> RISC-V ELF attribute requires GNU as 2.32"
 	   " [%<-mriscv-attribute%>]");
 #endif
+
 }
 
 /* Implement TARGET_CONDITIONAL_REGISTER_USAGE.  */
@@ -4686,9 +4762,9 @@ riscv_conditional_register_usage (void)
 static int
 riscv_register_priority (int regno)
 {
-  /* Favor x8-x15/f8-f15 to improve the odds of RVC instruction selection.  */
-  if (TARGET_RVC && (IN_RANGE (regno, GP_REG_FIRST + 8, GP_REG_FIRST + 15)
-		     || IN_RANGE (regno, FP_REG_FIRST + 8, FP_REG_FIRST + 15)))
+  /* Favor compressed registers to improve the odds of RVC instruction
+     selection.  */
+  if (riscv_compressed_reg_p (regno))
     return 1;
 
   return 0;
diff --git a/gcc/config/riscv/riscv.h b/gcc/config/riscv/riscv.h
index 246494663f6..36b84c7e8ef 100644
--- a/gcc/config/riscv/riscv.h
+++ b/gcc/config/riscv/riscv.h
@@ -876,6 +876,11 @@ while (0)
 
 #define SET_RATIO(speed) (CLEAR_RATIO (speed) - ((speed) ? 0 : 2))
 
+/* This is the maximum value that can be represented in a compressed load/store
+   offset (an unsigned 5-bit value scaled by 4).  */
+
+#define RISCV_MAX_COMPRESSED_LW_OFFSET 124
+
 #ifndef USED_FOR_TARGET
 extern const enum reg_class riscv_regno_to_class[];
 extern bool riscv_slow_unaligned_access_p;
diff --git a/gcc/config/riscv/riscv.opt b/gcc/config/riscv/riscv.opt
index 7f0c35e9e9c..138bddd369f 100644
--- a/gcc/config/riscv/riscv.opt
+++ b/gcc/config/riscv/riscv.opt
@@ -87,6 +87,12 @@ msave-restore
 Target Report Mask(SAVE_RESTORE)
 Use smaller but slower prologue and epilogue code.
 
+mshorten-memrefs
+Target Bool Var(riscv_mshorten_memrefs) Init(1)
+Convert BASE + LARGE_OFFSET addresses to NEW_BASE + SMALL_OFFSET to allow more
+memory accesses to be generated as compressed instructions.  Currently targets
+32-bit integer load/stores.
+
 mcmodel=
 Target Report RejectNegative Joined Enum(code_model) Var(riscv_cmodel) Init(TARGET_DEFAULT_CMODEL)
 Specify the code model.
diff --git a/gcc/config/riscv/t-riscv b/gcc/config/riscv/t-riscv
index ece3a75d512..1e31a49c9c5 100644
--- a/gcc/config/riscv/t-riscv
+++ b/gcc/config/riscv/t-riscv
@@ -14,3 +14,8 @@ riscv-d.o: $(srcdir)/config/riscv/riscv-d.c
 	$(COMPILE) $<
 	$(POSTCOMPILE)
 
+riscv-shorten-memrefs.o: $(srcdir)/config/riscv/riscv-shorten-memrefs.c
+	$(COMPILE) $<
+	$(POSTCOMPILE)
+
+PASSES_EXTRA += $(srcdir)/config/riscv/riscv-passes.def
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 1407d019d14..6de3e032447 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -1075,6 +1075,7 @@ See RS/6000 and PowerPC Options.
 -mpreferred-stack-boundary=@var{num} @gol
 -msmall-data-limit=@var{N-bytes} @gol
 -msave-restore  -mno-save-restore @gol
+-mshorten-memrefs  -mno-shorten-memrefs @gol
 -mstrict-align  -mno-strict-align @gol
 -mcmodel=medlow  -mcmodel=medany @gol
 -mexplicit-relocs  -mno-explicit-relocs @gol
@@ -24210,6 +24211,15 @@ Do or don't use smaller but slower prologue and epilogue code that uses
 library function calls.  The default is to use fast inline prologues and
 epilogues.
 
+@item -mshorten-memrefs
+@itemx -mno-shorten-memrefs
+@opindex mshorten-memrefs
+Do or do not attempt to make more use of compressed load/store instructions by
+replacing a load/store of 'base register + large offset' with a new load/store
+of 'new base + small offset'.  If the new base gets stored in a compressed
+register, then the new load/store can be compressed.  Currently targets 32-bit
+integer load/stores only.
+
 @item -mstrict-align
 @itemx -mno-strict-align
 @opindex mstrict-align
-- 
2.17.1