This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Extend CSE to use constant anchors


Eric Botcazou writes:
> OK for mainline with the additional simplification in insert_const_anchor.

This is what I've committed after boostrapping and regtesting on
mips64octeon-linux.

2009-05-28  Adam Nemet  <anemet@caviumnetworks.com>

	PR middle-end/33699
	* target.h (struct gcc_target): Fix indentation.  Add
	const_anchor.
	* target-def.h (TARGET_CONST_ANCHOR): New macro.
	(TARGET_INITIALIZER): Use it.
	* cse.c (CHEAPER): Move it up to the other macros.
	(insert): Rename this ...
	(insert_with_costs): ... to this.  Add cost parameters.  Update
	function comment.
	(insert): New function.  Call insert_with_costs.
	(compute_const_anchors, insert_const_anchor, insert_const_anchors,
	find_reg_offset_for_const, try_const_anchors): New functions.
	(cse_insn): Call try_const_anchors.  Adjust cost of src_related
	when using a const-anchor.  Call insert_const_anchors.
	* config/mips/mips.c (mips_set_mips16_mode): Set
	targetm.const_anchor.
	* doc/tm.texi (Misc): Document TARGET_CONST_ANCHOR.

2009-05-28  Adam Nemet  <anemet@caviumnetworks.com>

	PR middle-end/33699
	* gcc.target/mips/const-anchor-1.c: New test.
	* gcc.target/mips/const-anchor-2.c: New test.

Index: target.h
===================================================================
--- target.h	(revision 147942)
+++ target.h	(working copy)
@@ -481,7 +481,7 @@ struct gcc_target
 
     /* Target builtin that implements vector permute.  */
     tree (* builtin_vec_perm) (tree, tree*);
-} vectorize;
+  } vectorize;
 
   /* The initial value of target_flags.  */
   int default_target_flags;
@@ -825,6 +825,10 @@ struct gcc_target
      checks to  handle_dll_attribute ().  */
   bool (* valid_dllimport_attribute_p) (const_tree decl);
 
+  /* If non-zero, align constant anchors in CSE to a multiple of this
+     value.  */
+  unsigned HOST_WIDE_INT const_anchor;
+
   /* Functions relating to calls - argument passing, returns, etc.  */
   struct calls {
     bool (*promote_function_args) (const_tree fntype);
Index: target-def.h
===================================================================
--- target-def.h	(revision 147942)
+++ target-def.h	(working copy)
@@ -423,6 +423,7 @@
 
 /* In cse.c.  */
 #define TARGET_ADDRESS_COST default_address_cost
+#define TARGET_CONST_ANCHOR 0
 
 /* In builtins.c.  */
 #define TARGET_INIT_BUILTINS hook_void_void
@@ -922,6 +923,7 @@
   TARGET_STACK_PROTECT_FAIL,			\
   TARGET_INVALID_WITHIN_DOLOOP,			\
   TARGET_VALID_DLLIMPORT_ATTRIBUTE_P,		\
+  TARGET_CONST_ANCHOR,				\
   TARGET_CALLS,					\
   TARGET_INVALID_CONVERSION,			\
   TARGET_INVALID_UNARY_OP,			\
Index: cse.c
===================================================================
--- cse.c	(revision 147538)
+++ cse.c	(working copy)
@@ -502,6 +502,11 @@ struct table_elt
 
 #define REGNO_QTY_VALID_P(N) (REG_QTY (N) >= 0)
 
+/* Compare table_elt X and Y and return true iff X is cheaper than Y.  */
+
+#define CHEAPER(X, Y) \
+ (preferable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
+
 static struct table_elt *table[HASH_SIZE];
 
 /* Chain of `struct table_elt's made so far for this function
@@ -563,6 +568,8 @@ static void remove_pseudo_from_table (rt
 static struct table_elt *lookup (rtx, unsigned, enum machine_mode);
 static struct table_elt *lookup_for_remove (rtx, unsigned, enum machine_mode);
 static rtx lookup_as_function (rtx, enum rtx_code);
+static struct table_elt *insert_with_costs (rtx, struct table_elt *, unsigned,
+					    enum machine_mode, int, int);
 static struct table_elt *insert (rtx, struct table_elt *, unsigned,
 				 enum machine_mode);
 static void merge_equiv_classes (struct table_elt *, struct table_elt *);
@@ -1213,6 +1220,174 @@ insert_regs (rtx x, struct table_elt *cl
     return mention_regs (x);
 }
 
+
+/* Compute upper and lower anchors for CST.  Also compute the offset of CST
+   from these anchors/bases such that *_BASE + *_OFFS = CST.  Return false iff
+   CST is equal to an anchor.  */
+
+static bool
+compute_const_anchors (rtx cst,
+		       HOST_WIDE_INT *lower_base, HOST_WIDE_INT *lower_offs,
+		       HOST_WIDE_INT *upper_base, HOST_WIDE_INT *upper_offs)
+{
+  HOST_WIDE_INT n = INTVAL (cst);
+
+  *lower_base = n & ~(targetm.const_anchor - 1);
+  if (*lower_base == n)
+    return false;
+
+  *upper_base =
+    (n + (targetm.const_anchor - 1)) & ~(targetm.const_anchor - 1);
+  *upper_offs = n - *upper_base;
+  *lower_offs = n - *lower_base;
+  return true;
+}
+
+/* Insert the equivalence between ANCHOR and (REG + OFF) in mode MODE.  */
+
+static void
+insert_const_anchor (HOST_WIDE_INT anchor, rtx reg, HOST_WIDE_INT offs,
+		     enum machine_mode mode)
+{
+  struct table_elt *elt;
+  unsigned hash;
+  rtx anchor_exp;
+  rtx exp;
+
+  anchor_exp = GEN_INT (anchor);
+  hash = HASH (anchor_exp, mode);
+  elt = lookup (anchor_exp, hash, mode);
+  if (!elt)
+    elt = insert (anchor_exp, NULL, hash, mode);
+
+  exp = plus_constant (reg, offs);
+  /* REG has just been inserted and the hash codes recomputed.  */
+  mention_regs (exp);
+  hash = HASH (exp, mode);
+
+  /* Use the cost of the register rather than the whole expression.  When
+     looking up constant anchors we will further offset the corresponding
+     expression therefore it does not make sense to prefer REGs over
+     reg-immediate additions.  Prefer instead the oldest expression.  Also
+     don't prefer pseudos over hard regs so that we derive constants in
+     argument registers from other argument registers rather than from the
+     original pseudo that was used to synthesize the constant.  */
+  insert_with_costs (exp, elt, hash, mode, COST (reg), 1);
+}
+
+/* The constant CST is equivalent to the register REG.  Create
+   equivalences between the two anchors of CST and the corresponding
+   register-offset expressions using REG.  */
+
+static void
+insert_const_anchors (rtx reg, rtx cst, enum machine_mode mode)
+{
+  HOST_WIDE_INT lower_base, lower_offs, upper_base, upper_offs;
+
+  if (!compute_const_anchors (cst, &lower_base, &lower_offs,
+			      &upper_base, &upper_offs))
+      return;
+
+  /* Ignore anchors of value 0.  Constants accessible from zero are
+     simple.  */
+  if (lower_base != 0)
+    insert_const_anchor (lower_base, reg, -lower_offs, mode);
+
+  if (upper_base != 0)
+    insert_const_anchor (upper_base, reg, -upper_offs, mode);
+}
+
+/* We need to express ANCHOR_ELT->exp + OFFS.  Walk the equivalence list of
+   ANCHOR_ELT and see if offsetting any of the entries by OFFS would create a
+   valid expression.  Return the cheapest and oldest of such expressions.  In
+   *OLD, return how old the resulting expression is compared to the other
+   equivalent expressions.  */
+
+static rtx
+find_reg_offset_for_const (struct table_elt *anchor_elt, HOST_WIDE_INT offs,
+			   unsigned *old)
+{
+  struct table_elt *elt;
+  unsigned idx;
+  struct table_elt *match_elt;
+  rtx match;
+
+  /* Find the cheapest and *oldest* expression to maximize the chance of
+     reusing the same pseudo.  */
+
+  match_elt = NULL;
+  match = NULL_RTX;
+  for (elt = anchor_elt->first_same_value, idx = 0;
+       elt;
+       elt = elt->next_same_value, idx++)
+    {
+      if (match_elt && CHEAPER (match_elt, elt))
+	return match;
+
+      if (REG_P (elt->exp)
+	  || (GET_CODE (elt->exp) == PLUS
+	      && REG_P (XEXP (elt->exp, 0))
+	      && GET_CODE (XEXP (elt->exp, 1)) == CONST_INT))
+	{
+	  rtx x;
+
+	  /* Ignore expressions that are no longer valid.  */
+	  if (!REG_P (elt->exp) && !exp_equiv_p (elt->exp, elt->exp, 1, false))
+	    continue;
+
+	  x = plus_constant (elt->exp, offs);
+	  if (REG_P (x)
+	      || (GET_CODE (x) == PLUS
+		  && IN_RANGE (INTVAL (XEXP (x, 1)),
+			       -targetm.const_anchor,
+			       targetm.const_anchor - 1)))
+	    {
+	      match = x;
+	      match_elt = elt;
+	      *old = idx;
+	    }
+	}
+    }
+
+  return match;
+}
+
+/* Try to express the constant SRC_CONST using a register+offset expression
+   derived from a constant anchor.  Return it if successful or NULL_RTX,
+   otherwise.  */
+
+static rtx
+try_const_anchors (rtx src_const, enum machine_mode mode)
+{
+  struct table_elt *lower_elt, *upper_elt;
+  HOST_WIDE_INT lower_base, lower_offs, upper_base, upper_offs;
+  rtx lower_anchor_rtx, upper_anchor_rtx;
+  rtx lower_exp = NULL_RTX, upper_exp = NULL_RTX;
+  unsigned lower_old, upper_old;
+
+  if (!compute_const_anchors (src_const, &lower_base, &lower_offs,
+			      &upper_base, &upper_offs))
+    return NULL_RTX;
+
+  lower_anchor_rtx = GEN_INT (lower_base);
+  upper_anchor_rtx = GEN_INT (upper_base);
+  lower_elt = lookup (lower_anchor_rtx, HASH (lower_anchor_rtx, mode), mode);
+  upper_elt = lookup (upper_anchor_rtx, HASH (upper_anchor_rtx, mode), mode);
+
+  if (lower_elt)
+    lower_exp = find_reg_offset_for_const (lower_elt, lower_offs, &lower_old);
+  if (upper_elt)
+    upper_exp = find_reg_offset_for_const (upper_elt, upper_offs, &upper_old);
+
+  if (!lower_exp)
+    return upper_exp;
+  if (!upper_exp)
+    return lower_exp;
+
+  /* Return the older expression.  */
+  return (upper_old > lower_old ? upper_exp : lower_exp);
+}
+
 /* Look in or update the hash table.  */
 
 /* Remove table element ELT from use in the table.
@@ -1380,11 +1555,11 @@ lookup_as_function (rtx x, enum rtx_code
   return 0;
 }
 
-/* Insert X in the hash table, assuming HASH is its hash code
-   and CLASSP is an element of the class it should go in
-   (or 0 if a new class should be made).
-   It is inserted at the proper position to keep the class in
-   the order cheapest first.
+/* Insert X in the hash table, assuming HASH is its hash code and
+   CLASSP is an element of the class it should go in (or 0 if a new
+   class should be made).  COST is the code of X and reg_cost is the
+   cost of registers in X.  It is inserted at the proper position to
+   keep the class in the order cheapest first.
 
    MODE is the machine-mode of X, or if X is an integer constant
    with VOIDmode then MODE is the mode with which X will be used.
@@ -1404,11 +1579,9 @@ lookup_as_function (rtx x, enum rtx_code
 
    If necessary, update table showing constant values of quantities.  */
 
-#define CHEAPER(X, Y) \
- (preferable ((X)->cost, (X)->regcost, (Y)->cost, (Y)->regcost) < 0)
-
 static struct table_elt *
-insert (rtx x, struct table_elt *classp, unsigned int hash, enum machine_mode mode)
+insert_with_costs (rtx x, struct table_elt *classp, unsigned int hash,
+		   enum machine_mode mode, int cost, int reg_cost)
 {
   struct table_elt *elt;
 
@@ -1430,8 +1603,8 @@ insert (rtx x, struct table_elt *classp,
 
   elt->exp = x;
   elt->canon_exp = NULL_RTX;
-  elt->cost = COST (x);
-  elt->regcost = approx_reg_cost (x);
+  elt->cost = cost;
+  elt->regcost = reg_cost;
   elt->next_same_value = 0;
   elt->prev_same_value = 0;
   elt->next_same_hash = table[hash];
@@ -1566,6 +1739,17 @@ insert (rtx x, struct table_elt *classp,
 
   return elt;
 }
+
+/* Wrap insert_with_costs by passing the default costs.  */
+
+static struct table_elt *
+insert (rtx x, struct table_elt *classp, unsigned int hash,
+	enum machine_mode mode)
+{
+  return
+    insert_with_costs (x, classp, hash, mode, COST (x), approx_reg_cost (x));
+}
+
 
 /* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
    CLASS2 into CLASS1.  This is done when we have reached an insn which makes
@@ -4253,6 +4437,7 @@ cse_insn (rtx insn)
       rtx src_eqv_here;
       rtx src_const = 0;
       rtx src_related = 0;
+      bool src_related_is_const_anchor = false;
       struct table_elt *src_const_elt = 0;
       int src_cost = MAX_COST;
       int src_eqv_cost = MAX_COST;
@@ -4602,6 +4787,19 @@ cse_insn (rtx insn)
 	}
 #endif /* LOAD_EXTEND_OP */
 
+      /* Try to express the constant using a register+offset expression
+	 derived from a constant anchor.  */
+
+      if (targetm.const_anchor
+	  && !src_related
+	  && src_const
+	  && GET_CODE (src_const) == CONST_INT)
+	{
+	  src_related = try_const_anchors (src_const, mode);
+	  src_related_is_const_anchor = src_related != NULL_RTX;
+	}
+
+
       if (src == src_folded)
 	src_folded = 0;
 
@@ -4706,6 +4904,18 @@ cse_insn (rtx insn)
 	    {
 	      src_related_cost = COST (src_related);
 	      src_related_regcost = approx_reg_cost (src_related);
+
+	      /* If a const-anchor is used to synthesize a constant that
+		 normally requires multiple instructions then slightly prefer
+		 it over the original sequence.  These instructions are likely
+		 to become redundant now.  We can't compare against the cost
+		 of src_eqv_here because, on MIPS for example, multi-insn
+		 constants have zero cost; they are assumed to be hoisted from
+		 loops.  */
+	      if (src_related_is_const_anchor
+		  && src_related_cost == src_cost
+		  && src_eqv_here)
+		src_related_cost--;
 	    }
 	}
 
@@ -5440,6 +5650,14 @@ cse_insn (rtx insn)
 	elt = insert (dest, sets[i].src_elt,
 		      sets[i].dest_hash, GET_MODE (dest));
 
+	/* If this is a constant, insert the constant anchors with the
+	   equivalent register-offset expressions using register DEST.  */
+	if (targetm.const_anchor
+	    && REG_P (dest)
+	    && SCALAR_INT_MODE_P (GET_MODE (dest))
+	    && GET_CODE (sets[i].src_elt->exp) == CONST_INT)
+	  insert_const_anchors (dest, sets[i].src_elt->exp, GET_MODE (dest));
+
 	elt->in_memory = (MEM_P (sets[i].inner_dest)
 			  && !MEM_READONLY_P (sets[i].inner_dest));
 
Index: config/mips/mips.c
===================================================================
--- config/mips/mips.c	(revision 147942)
+++ config/mips/mips.c	(working copy)
@@ -13928,6 +13928,8 @@ mips_set_mips16_mode (int mips16_p)
       targetm.min_anchor_offset = 0;
       targetm.max_anchor_offset = 127;
 
+      targetm.const_anchor = 0;
+
       if (flag_pic && !TARGET_OLDABI)
 	sorry ("MIPS16 PIC for ABIs other than o32 and o64");
 
@@ -13955,6 +13957,8 @@ mips_set_mips16_mode (int mips16_p)
 
       targetm.min_anchor_offset = -32768;
       targetm.max_anchor_offset = 32767;
+
+      targetm.const_anchor = 0x8000;
     }
 
   /* (Re)initialize MIPS target internals for new ISA.  */
Index: doc/tm.texi
===================================================================
--- doc/tm.texi	(revision 147942)
+++ doc/tm.texi	(working copy)
@@ -10852,3 +10852,21 @@ cannot safely move arguments from the re
 to the stack.  Therefore, this hook should return true in general, but
 false for naked functions.  The default implementation always returns true.
 @end deftypefn
+
+
+@deftypevr {Target Hook} {unsigned HOST_WIDE_INT} TARGET_CONST_ANCHOR
+On some architectures it can take multiple instructions to synthesize
+a constant.  If there is another constant already in a register that
+is close enough in value then it is preferable that the new constant
+is computed from this register using immediate addition or
+substraction.  We accomplish this through CSE.  Besides the value of
+the constant we also add a lower and an upper constant anchor to the
+available expressions.  These are then queried when encountering new
+constants.  The anchors are computed by rounding the constant up and
+down to a multiple of the value of @code{TARGET_CONST_ANCHOR}.
+@code{TARGET_CONST_ANCHOR} should be the maximum positive value
+accepted by immediate-add plus one.  We currently assume that the
+value of @code{TARGET_CONST_ANCHOR} is a power of 2.  For example, on
+MIPS, where add-immediate takes a 16-bit signed value,
+@code{TARGET_CONST_ANCHOR} is set to @samp{0x8000}.  The default value
+is zero, which disables this optimization.  @end deftypevr
Index: testsuite/gcc.target/mips/const-anchor-1.c
===================================================================
--- testsuite/gcc.target/mips/const-anchor-1.c	(revision 0)
+++ testsuite/gcc.target/mips/const-anchor-1.c	(revision 0)
@@ -0,0 +1,10 @@
+/* Derive a constant (0x1233ffff) from an intermediate value
+   (0x1234000) used to build another constant.  */
+/* { dg-options "-O" } */
+/* { dg-final { scan-assembler-not "0x12330000|305332224" } } */
+/* { dg-final { scan-assembler "addiu\t\\\$5,\\\$\[0-9\]*,-1" } } */
+
+NOMIPS16 void f ()
+{
+  g (0x12340001, 0x1233ffff);
+}
Index: testsuite/gcc.target/mips/const-anchor-2.c
===================================================================
--- testsuite/gcc.target/mips/const-anchor-2.c	(revision 0)
+++ testsuite/gcc.target/mips/const-anchor-2.c	(revision 0)
@@ -0,0 +1,9 @@
+/* Derive a constant (0x30001) from another constant.  */
+/* { dg-options "-O" } */
+/* { dg-final { scan-assembler-not "0x300000|196608" } } */
+/* { dg-final { scan-assembler "addiu\t\\\$5,\\\$\[0-9\]*,32763" } } */
+
+NOMIPS16 void f ()
+{
+  g (0x28006, 0x30001);
+}


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]