This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Extend CSE to use constant anchors
- From: Adam Nemet <anemet at caviumnetworks dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 22 Apr 2009 14:13:57 -0700
- Subject: [PATCH] Extend CSE to use constant anchors
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));
+}
+
/* 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;
+}
/* 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);
+}