[patch] tree-ssa-ccp.c: Fold references into constant aggregates.
Kazu Hirata
kazu@cs.umass.edu
Sat May 7 21:35:00 GMT 2005
Hi,
Attached is a patch to fold references into constant aggregates.
An example says probably says it all. With this patch, we can fold an
aggregate reference like this into a constant, where the definition of
CARS is given in the attached testcase.
void
foo (void)
{
if (cars[1].tire_pressure[2] != 56)
link_error ();
}
This patch is based on the patch that Steven Bosscher generated last
year, which only handled a reference into a single-dimentional
constant array.
Here are some reactions to Richard Henderson's comments back in last
August.
http://gcc.gnu.org/ml/gcc-patches/2004-08/msg02646.html
Check targetm.binds_local_p
---------------------------
Done.
Check TREE_STATIC
-----------------
Done on DECL_INITIAL. I don't think he meant on VAR_DECL, but if I
am mistaken, please let me know.
Richard Henderson said that the TREE_SIDE_EFFECTS check in Steven's
original patch was useless, but expr.c:6945 checks
TREE_SIDE_EFFECTS. Could that be a problem?
Handle nested components/arrays
-------------------------------
Done.
Should be done in fold or fold_stmt
-----------------------------------
Not done. The reason is that I want to use constants associated
with lattice values in CCP. If this were done in fold or fold_stmt,
and we have cars[X].tire_pressure[Y], where X and Y are SSA_NAMEs
that are known to be constants according to their lattice values,
then I would have to
1. replace X and Y with constants.
2. pass the expression to fold or fold_stmt
3. if folding is unsuccessful, put X and Y back.
I felt this was a bit tedious. I guess one could use
FOR_EACH_SSA_USE_OPERAND and SET_USE.
According to -fdump-tree-store_ccp-stats, without this patch, CCP
propagates constants 1841 times while compiling cc1-i files with
checking enabled. With this patch, it propagates constants 2006
times. A 9% improvement. Unfortunately, the number of predicates
folded does not increase very much with this patch, but once this
patch goes in, we can visit PR 14840 to improve GCC itself by folding
things like tree_code_length[CST] and tree_code_type[CST] that appear
a lot in GCC with --enable-checking.
Once this patch goes in, we should be able to simplify the ARRAY_REF
and COMPONENT_REF cases of expr.c:expand_expr_real_1. With this
patch, the ARRAY_REF cases only triggers 2 times while compiling cc1-i
files, whereas it triggers 56 times without my patch.
Tested on i686-pc-linux-gnu. OK to apply?
Kazu Hirata
2005-05-07 Steven Bosscher <stevenb@suse.de>
Kazu Hirata <kazu@cs.umass.edu>
PR tree-optimization/14841, tree-optimization/15838
* tree-ssa-ccp.c (fold_const_aggregate_ref): New.
(evaluate_stmt): Call it.
2005-05-07 Steven Bosscher <stevenb@suse.de>
Kazu Hirata <kazu@cs.umass.edu>
PR tree-optimization/14841, tree-optimization/15838
* gcc.dg/tree-ssa/pr14841.c: New.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1479
diff -u -d -p -r1.1479 Makefile.in
--- Makefile.in 7 May 2005 16:56:28 -0000 1.1479
+++ Makefile.in 7 May 2005 21:13:21 -0000
@@ -2015,7 +2015,7 @@ tree-ssa-ccp.o : tree-ssa-ccp.c $(TREE_F
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h \
$(DIAGNOSTIC_H) errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
$(TREE_DUMP_H) $(BASIC_BLOCK_H) tree-pass.h langhooks.h \
- tree-ssa-propagate.h
+ tree-ssa-propagate.h $(TARGET_H)
tree-sra.o : tree-sra.c $(CONFIG_H) $(SYSTEM_H) errors.h $(TREE_H) $(RTL_H) \
$(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) tree-inline.h \
$(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_GIMPLE_H) \
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-ccp.c,v
retrieving revision 2.69
diff -u -d -p -r2.69 tree-ssa-ccp.c
--- tree-ssa-ccp.c 3 May 2005 14:14:19 -0000 2.69
+++ tree-ssa-ccp.c 7 May 2005 21:13:21 -0000
@@ -209,6 +209,7 @@ Software Foundation, 59 Temple Place - S
#include "tree-pass.h"
#include "tree-ssa-propagate.h"
#include "langhooks.h"
+#include "target.h"
/* Possible lattice values. */
@@ -970,6 +971,134 @@ ccp_fold (tree stmt)
}
+/* Return the tree representing the element referenced by T if T is an
+ ARRAY_REF or COMPONENT_REF into constant aggregates. Return
+ NULL_TREE otherwise. */
+
+static tree
+fold_const_aggregate_ref (tree t)
+{
+ prop_value_t *value;
+ tree base, ctor, idx, field, elt;
+
+ switch (TREE_CODE (t))
+ {
+ case ARRAY_REF:
+ /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
+ DECL_INITIAL. If BASE is a nested reference into another
+ ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
+ the inner reference. */
+ base = TREE_OPERAND (t, 0);
+ switch (TREE_CODE (base))
+ {
+ case VAR_DECL:
+ if (!TREE_READONLY (base)
+ || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE
+ || !targetm.binds_local_p (base))
+ return NULL_TREE;
+
+ ctor = DECL_INITIAL (base);
+ break;
+
+ case ARRAY_REF:
+ case COMPONENT_REF:
+ ctor = fold_const_aggregate_ref (base);
+ break;
+
+ default:
+ return NULL_TREE;
+ }
+
+ if (ctor == NULL_TREE
+ || TREE_CODE (ctor) != CONSTRUCTOR
+ || TREE_SIDE_EFFECTS (ctor)
+ || !TREE_STATIC (ctor))
+ return NULL_TREE;
+
+ /* Get the index. If we have an SSA_NAME, try to resolve it
+ with the current lattice value for the SSA_NAME. */
+ idx = TREE_OPERAND (t, 1);
+ switch (TREE_CODE (idx))
+ {
+ case SSA_NAME:
+ if ((value = get_value (idx, true))
+ && value->lattice_val == CONSTANT
+ && TREE_CODE (value->value) == INTEGER_CST)
+ idx = value->value;
+ else
+ return NULL_TREE;
+ break;
+
+ case INTEGER_CST:
+ break;
+
+ default:
+ return NULL_TREE;
+ }
+
+ if (compare_tree_int (idx, list_length (CONSTRUCTOR_ELTS (ctor))) < 0)
+ {
+ /* Whoo-hoo! I'll fold ya baby. Yeah! */
+ HOST_WIDE_INT i;
+
+ for (elt = CONSTRUCTOR_ELTS (ctor), i = TREE_INT_CST_LOW (idx);
+ elt != 0 && i != 0;
+ i--, elt = TREE_CHAIN (elt))
+ /* Find that element. */
+ ;
+
+ if (elt)
+ return TREE_VALUE (elt);
+ }
+ break;
+
+ case COMPONENT_REF:
+ /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
+ DECL_INITIAL. If BASE is a nested reference into another
+ ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
+ the inner reference. */
+ base = TREE_OPERAND (t, 0);
+ switch (TREE_CODE (base))
+ {
+ case VAR_DECL:
+ if (!TREE_READONLY (base)
+ || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE
+ || !targetm.binds_local_p (base))
+ return NULL_TREE;
+
+ ctor = DECL_INITIAL (base);
+ break;
+
+ case ARRAY_REF:
+ case COMPONENT_REF:
+ ctor = fold_const_aggregate_ref (base);
+ break;
+
+ default:
+ return NULL_TREE;
+ }
+
+ if (ctor == NULL_TREE
+ || TREE_CODE (ctor) != CONSTRUCTOR
+ || !TREE_STATIC (ctor))
+ return NULL_TREE;
+
+ field = TREE_OPERAND (t, 1);
+
+ for (elt = CONSTRUCTOR_ELTS (ctor); elt; elt = TREE_CHAIN (elt))
+ if (TREE_PURPOSE (elt) == field
+ /* FIXME: Handle bit-fields. */
+ && ! DECL_BIT_FIELD (TREE_PURPOSE (elt)))
+ return TREE_VALUE (elt);
+ break;
+
+ default:
+ break;
+ }
+
+ return NULL_TREE;
+}
+
/* Evaluate statement STMT. */
static prop_value_t
@@ -989,10 +1118,13 @@ evaluate_stmt (tree stmt)
bother folding the statement. */
else if (likelyvalue == VARYING)
simplified = get_rhs (stmt);
- /* Otherwise the statement is likely to have an UNDEFINED value and
- there will be nothing to do. */
+ /* If the statement is an ARRAY_REF or COMPONENT_REF into constant
+ aggregates, extract the referenced constant. Otherwise the
+ statement is likely to have an UNDEFINED value, and there will be
+ nothing to do. Note that fold_const_aggregate_ref returns
+ NULL_TREE if the first case does not match. */
else
- simplified = NULL_TREE;
+ simplified = fold_const_aggregate_ref (get_rhs (stmt));
if (simplified && is_gimple_min_invariant (simplified))
{
--- /dev/null 2005-05-05 09:22:29.000000000 -0400
+++ testsuite/gcc.dg/tree-ssa/pr14841.c 2005-05-07 17:11:55.000000000 -0400
@@ -0,0 +1,29 @@
+/* PR tree-optimization/14841
+ Make sure that we can fold a possible nested reference into a
+ constant aggregate. */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-store_ccp-details" } */
+
+struct car {
+ int speed;
+ int tire_pressure[4];
+};
+
+const struct car cars[] = {
+ { 75, { 10, 20, 30, 40 } },
+ { 35, { 12, 34, 56, 78 } },
+ { 40, { 19, 28, 37, 46 } }
+};
+
+extern void link_error (void);
+
+void
+foo (void)
+{
+ if (cars[1].tire_pressure[2] != 56)
+ link_error ();
+}
+
+/* { dg-final { scan-tree-dump-times "with if \\(0\\)" 1 "store_ccp"} } */
+/* { dg-final { cleanup-tree-dump "store_ccp" } } */
More information about the Gcc-patches
mailing list