* [PATCH] Extend CSE to use constant anchors
@ 2009-04-22 21:21 Adam Nemet
2009-05-23 9:10 ` Eric Botcazou
0 siblings, 1 reply; 5+ messages in thread
From: Adam Nemet @ 2009-04-22 21:21 UTC (permalink / raw)
To: gcc-patches
I've completed the patch that was RFCed (and explained) here:
http://gcc.gnu.org/ml/gcc-patches/2009-03/msg00158.html
There was a separate discussion later with RichardS on the cost model changes
for this feature. The consensus was to implement the "alternative solution"
from here: http://gcc.gnu.org/ml/gcc/2009-04/msg00176.html.
The patch also enables this optimization for MIPS. For now, I disabled it for
MIPS16. I need to see if it makes sense for MIPS16 at all.
The patch does not directly fix PR/33699 anymore. That will require further
modifications in the cost model and possibly fwprop. Should I still put the
PR number in the changelog?
Cross compilation time on cc1files for MIPS is in the noise (especially after
I removed 0 as a valid anchor).
Regtested and bootstrapped on mips64octeon-linux-gnu.
OK to install?
Adam
* target.h (struct gcc_target): Fix indentation. Add
const_anchor.
* target-def.h (TARGET_CONST_ANCHOR): New macro.
(TARGET_INITIALIZER): Use it.
* cse.c (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.
testsuite/
* gcc.target/mips/const-anchor-1.c: New test.
* gcc.target/mips/const-anchor-2.c: New test.
Index: target.h
===================================================================
--- target.h (revision 146303)
+++ target.h (working copy)
@@ -475,7 +475,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;
@@ -810,6 +810,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 146303)
+++ 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
@@ -909,6 +910,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 146303)
+++ cse.c (working copy)
@@ -559,6 +559,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 *);
@@ -1376,11 +1378,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,7 +1406,8 @@ lookup_as_function (rtx x, enum rtx_code
(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;
@@ -1426,8 +1429,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];
@@ -1562,6 +1565,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));
+}
+
\f
/* 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
@@ -3964,6 +3978,172 @@ record_jump_cond (enum rtx_code code, en
merge_equiv_classes (op0_elt, op1_elt);
}
+
+/* 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 EXP in mode MODE. REG is
+ the register in EXP. */
+
+static void
+insert_const_anchor (HOST_WIDE_INT anchor, rtx exp, enum machine_mode mode,
+ rtx reg)
+{
+ struct table_elt *elt;
+ unsigned hash;
+ rtx anchor_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);
+
+ hash = HASH (exp, mode);
+ if (insert_regs (exp, elt, 0))
+ {
+ rehash_using_reg (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. Instead prefer the
+ oldest expression. Also don't prefer pseudos over hard regs. */
+ 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, plus_constant (reg, -lower_offs), mode,
+ reg);
+
+ if (upper_base != 0)
+ insert_const_anchor (upper_base, plus_constant (reg, -upper_offs), mode,
+ reg);
+}
+
+/* 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. */
+
+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. */
+
+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. */
+ if (lower_old < upper_old)
+ return upper_exp;
+ return lower_exp;
+}
\f
/* CSE processing for one instruction.
First simplify sources and addresses of all assignments
@@ -4249,6 +4429,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;
@@ -4598,6 +4779,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;
@@ -4702,6 +4896,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--;
}
}
@@ -5436,6 +5642,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 146360)
+++ config/mips/mips.c (working copy)
@@ -13919,6 +13919,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");
@@ -13946,6 +13948,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 146303)
+++ doc/tm.texi (working copy)
@@ -10715,3 +10715,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. 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);
+}
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Extend CSE to use constant anchors
2009-04-22 21:21 [PATCH] Extend CSE to use constant anchors Adam Nemet
@ 2009-05-23 9:10 ` Eric Botcazou
2009-05-26 15:01 ` anemet
0 siblings, 1 reply; 5+ messages in thread
From: Eric Botcazou @ 2009-05-23 9:10 UTC (permalink / raw)
To: Adam Nemet; +Cc: gcc-patches
> The patch does not directly fix PR/33699 anymore. That will require
> further modifications in the cost model and possibly fwprop. Should I
> still put the PR number in the changelog?
I think so.
> * target.h (struct gcc_target): Fix indentation. Add
> const_anchor.
> * target-def.h (TARGET_CONST_ANCHOR): New macro.
> (TARGET_INITIALIZER): Use it.
> * cse.c (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.
Looks good, but see the nits below:
> +/* 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);
This requires targetm.const_anchor to be a power of 2.
> + *upper_offs = n - *upper_base;
> + *lower_offs = n - *lower_base;
> + return true;
> +}
> +
> +/* Insert the equivalence between ANCHOR and EXP in mode MODE. REG is
> + the register in EXP. */
> +
> +static void
> +insert_const_anchor (HOST_WIDE_INT anchor, rtx exp, enum machine_mode
> mode, + rtx reg)
> +{
> + struct table_elt *elt;
> + unsigned hash;
> + rtx anchor_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);
> +
> + hash = HASH (exp, mode);
> + if (insert_regs (exp, elt, 0))
> + {
> + rehash_using_reg (exp);
> + hash = HASH (exp, mode);
> + }
exp is a plus_constant (reg, xxx) so rehash_using_reg (exp) is a no-op.
You don't need to call insert_regs since it's done just before the call to
insert_const_anchors in cse_insn.
> + /* 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. Instead prefer the
> + oldest expression. Also don't prefer pseudos over hard regs. */
> + insert_with_costs (exp, elt, hash, mode, COST (reg), 1);
Why the last sentence?
> +
> +/* 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, plus_constant (reg, -lower_offs),
> mode, + reg);
> +
> + if (upper_base != 0)
> + insert_const_anchor (upper_base, plus_constant (reg, -upper_offs),
> mode, + reg);
> +}
I would pass the naked offset to insert_const_anchor:
insert_const_anchor (upper_base, mode, reg, -offset);
> +/* 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. */
Missing comment about the return value.
> +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;
Why excluding REGs from the validity check?
> + 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. */
register+offset :-) "Return it on success and NULL_RTX on failure".
> +
> +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. */
> + if (lower_old < upper_old)
> + return upper_exp;
> + return lower_exp;
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);
> \f
> /* CSE processing for one instruction.
> First simplify sources and addresses of all assignments
> @@ -4249,6 +4429,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;
> @@ -4598,6 +4779,19 @@ cse_insn (rtx insn)
> }
> #endif /* LOAD_EXTEND_OP */
>
> + /* Try to express the constant using a register-offset expression
> + derived from a constant anchor. */
register+offset :-)
> @@ -5436,6 +5642,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));
Why not do that in insert instead? It does similar special processing already
--
Eric Botcazou
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Extend CSE to use constant anchors
2009-05-23 9:10 ` Eric Botcazou
@ 2009-05-26 15:01 ` anemet
2009-05-27 8:36 ` Eric Botcazou
0 siblings, 1 reply; 5+ messages in thread
From: anemet @ 2009-05-26 15:01 UTC (permalink / raw)
To: Eric Botcazou; +Cc: gcc-patches
Thanks very much for reviewing the patch, Eric!
Eric Botcazou writes:
> > The patch does not directly fix PR/33699 anymore. That will require
> > further modifications in the cost model and possibly fwprop. Should I
> > still put the PR number in the changelog?
>
> I think so.
Done.
> > +/* 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);
>
> This requires targetm.const_anchor to be a power of 2.
Added that to the docs.
> > +static void
> > +insert_const_anchor (HOST_WIDE_INT anchor, rtx exp, enum machine_mode
> > mode, + rtx reg)
> > +{
> > + struct table_elt *elt;
> > + unsigned hash;
> > + rtx anchor_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);
> > +
> > + hash = HASH (exp, mode);
> > + if (insert_regs (exp, elt, 0))
> > + {
> > + rehash_using_reg (exp);
> > + hash = HASH (exp, mode);
> > + }
>
> exp is a plus_constant (reg, xxx) so rehash_using_reg (exp) is a no-op.
>
> You don't need to call insert_regs since it's done just before the call to
> insert_const_anchors in cse_insn.
No, you do. insert_regs is really just short for
update_state_when_inserting_exp_with_reg. The available expression code
requires different bookkeeping when inserting a general expression as opposed
to a simple register expression.
Here we call it with a general expression so it needs to prune the table from
expressions referring to stale values of the registers mentioned in the new
expression. Previously in cse_insn we invoked it with a register expression
so it didn't the prune the table. (The tick in REG_IN_TABLE is not used with
register expressions; they are removed as soon as their value changes (see
invalidate()).) (Also remember this point for the exp_equiv_p code later.)
I could have used mention_regs here but I prefer the more widely used API of
insert_regs/insert.
I did however remove the call to rehash_using_reg.
> > + /* 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. Instead prefer the
> > + oldest expression. Also don't prefer pseudos over hard regs. */
> > + insert_with_costs (exp, elt, hash, mode, COST (reg), 1);
>
> Why the last sentence?
Does the updated comment answer your question? The second testcase is an
example for this.:
/* 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. */
> > +/* 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, plus_constant (reg, -lower_offs),
> > mode, + reg);
> > +
> > + if (upper_base != 0)
> > + insert_const_anchor (upper_base, plus_constant (reg, -upper_offs),
> > mode, + reg);
> > +}
>
> I would pass the naked offset to insert_const_anchor:
>
> insert_const_anchor (upper_base, mode, reg, -offset);
Agreed, done.
> > +/* 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. */
>
> Missing comment about the return value.
Done.
> > +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;
>
> Why excluding REGs from the validity check?
As discussed above, there is no need to check the validity of register
expressions as those are removed as soon as they become invalid. (In fact,
exp_equiv_p would deem register expressions invalid even though they are not.)
This is BTW how exp_equiv_p is used in other places so I don't think it
requires a comment.
> > + 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. */
>
> register+offset :-) "Return it on success and NULL_RTX on failure".
Done.
> > +
> > +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. */
> > + if (lower_old < upper_old)
> > + return upper_exp;
> > + return lower_exp;
>
> 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);
Done.
> > \f
> > /* CSE processing for one instruction.
> > First simplify sources and addresses of all assignments
> > @@ -4249,6 +4429,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;
> > @@ -4598,6 +4779,19 @@ cse_insn (rtx insn)
> > }
> > #endif /* LOAD_EXTEND_OP */
> >
> > + /* Try to express the constant using a register-offset expression
> > + derived from a constant anchor. */
>
> register+offset :-)
Done.
> > @@ -5436,6 +5642,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));
>
> Why not do that in insert instead? It does similar special processing already
I think you're referring to how related values are updated in insert. If yes,
then I don't think that's similar. insert() is also used in
merge_equiv_classes to merge two equivalence classes. In this case, for
related values you need to update the related_value link in the new entry so
you *have to* do the processing in insert, which is not the case for constant
anchors.
Also note that because it's in insert, which can be called more than once for
an expression, you have to do a lookup before you insert the related value.
We can save this lookup for constant anchors.
Here is the updated patch. Let me know if you want me to make further
modifications or my answers are satisfactory.
Bootstrapped and regstested on mips64octeon-linux.
Adam
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.
testsuite/
PR middle-end/33699
* gcc.target/mips/const-anchor-1.c: New test.
* gcc.target/mips/const-anchor-2.c: New test.
Index: gcc/target.h
===================================================================
--- gcc.orig/target.h 2009-05-24 16:00:48.000000000 -0700
+++ gcc/target.h 2009-05-24 16:01:54.000000000 -0700
@@ -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;
@@ -822,6 +822,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: gcc/target-def.h
===================================================================
--- gcc.orig/target-def.h 2009-05-24 16:00:48.000000000 -0700
+++ gcc/target-def.h 2009-05-24 16:01:54.000000000 -0700
@@ -423,6 +423,7 @@ #define TARGET_ATTRIBUTE_TABLE NULL
/* 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
@@ -916,6 +917,7 @@ #define TARGET_INITIALIZER \
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: gcc/cse.c
===================================================================
--- gcc.orig/cse.c 2009-05-24 16:00:17.000000000 -0700
+++ gcc/cse.c 2009-05-25 11:02:57.000000000 -0700
@@ -502,6 +502,11 @@ #define REG_QTY(N) (get_cse_reg_info (N)
#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);
}
\f
+
+/* 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;
+
+ exp = plus_constant (reg, offs);
+ 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);
+
+ hash = HASH (exp, mode);
+ if (insert_regs (exp, elt, 0))
+ 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);
+}
+\f
/* 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));
+}
+
\f
/* 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: gcc/config/mips/mips.c
===================================================================
--- gcc.orig/config/mips/mips.c 2009-05-24 16:00:54.000000000 -0700
+++ gcc/config/mips/mips.c 2009-05-24 16:01:54.000000000 -0700
@@ -13923,6 +13923,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");
@@ -13950,6 +13952,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: gcc/doc/tm.texi
===================================================================
--- gcc.orig/doc/tm.texi 2009-05-24 16:00:54.000000000 -0700
+++ gcc/doc/tm.texi 2009-05-24 16:01:54.000000000 -0700
@@ -10813,3 +10813,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: gcc/testsuite/gcc.target/mips/const-anchor-1.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gcc/testsuite/gcc.target/mips/const-anchor-1.c 2009-05-24 16:01:54.000000000 -0700
@@ -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: gcc/testsuite/gcc.target/mips/const-anchor-2.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ gcc/testsuite/gcc.target/mips/const-anchor-2.c 2009-05-24 16:01:54.000000000 -0700
@@ -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);
+}
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Extend CSE to use constant anchors
2009-05-26 15:01 ` anemet
@ 2009-05-27 8:36 ` Eric Botcazou
2009-05-28 8:10 ` Adam Nemet
0 siblings, 1 reply; 5+ messages in thread
From: Eric Botcazou @ 2009-05-27 8:36 UTC (permalink / raw)
To: anemet; +Cc: gcc-patches
> Here we call it with a general expression so it needs to prune the table
> from expressions referring to stale values of the registers mentioned in
> the new expression. Previously in cse_insn we invoked it with a register
> expression so it didn't the prune the table.
You're right, I forgot about this strategy.
> I could have used mention_regs here but I prefer the more widely used API
> of insert_regs/insert.
>
> I did however remove the call to rehash_using_reg.
Yes, but the second call to HASH is useless too, so I'd just do:
+ 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);
+
+ /* REG has just been inserted and the hash codes recomputed. */
+ exp = plus_constant (reg, offs);
+ mention_regs (exp);
+ hash = HASH (exp, mode);
> Does the updated comment answer your question? The second testcase is an
> example for this.:
>
> /* 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. */
OK.
> This is BTW how exp_equiv_p is used in other places so I don't think it
> requires a comment.
OK.
> I think you're referring to how related values are updated in insert. If
> yes, then I don't think that's similar. insert() is also used in
> merge_equiv_classes to merge two equivalence classes. In this case, for
> related values you need to update the related_value link in the new entry
> so you *have to* do the processing in insert, which is not the case for
> constant anchors.
>
> Also note that because it's in insert, which can be called more than once
> for an expression, you have to do a lookup before you insert the related
> value. We can save this lookup for constant anchors.
OK.
> Here is the updated patch. Let me know if you want me to make further
> modifications or my answers are satisfactory.
OK for mainline with the additional simplification in insert_const_anchor.
Thanks for your patience.
--
Eric Botcazou
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Extend CSE to use constant anchors
2009-05-27 8:36 ` Eric Botcazou
@ 2009-05-28 8:10 ` Adam Nemet
0 siblings, 0 replies; 5+ messages in thread
From: Adam Nemet @ 2009-05-28 8:10 UTC (permalink / raw)
To: Eric Botcazou; +Cc: gcc-patches
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);
}
\f
+
+/* 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);
+}
+\f
/* 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));
+}
+
\f
/* 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);
+}
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2009-05-28 8:10 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-04-22 21:21 [PATCH] Extend CSE to use constant anchors Adam Nemet
2009-05-23 9:10 ` Eric Botcazou
2009-05-26 15:01 ` anemet
2009-05-27 8:36 ` Eric Botcazou
2009-05-28 8:10 ` Adam Nemet
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).