This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[Bug c++/12747][tree-ssa] SRA part 2.
- From: Diego Novillo <dnovillo at redhat dot com>
- To: "gcc-patches at gcc dot gnu dot org" <gcc-patches at gcc dot gnu dot org>
- Cc: "gcc-bugzilla at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>
- Date: Mon, 15 Dec 2003 11:49:59 -0500
- Subject: [Bug c++/12747][tree-ssa] SRA part 2.
- Organization: Red Hat Canada
This patch should finally fix PR 12747 for good. With it, we get this
out for the abstract copy version:
void copy(BitVector&, BitVector&) (dest, src)
{
bool T.3;
int <D1624>;
unsigned int i;
unsigned int <D1593>;
<D1593> = dest->m_size;
i = 0;
goto <bb 4>;
<L3>:;
T.3 = getBit (src, i);
<D1624> = (int)T.3;
<L4>:;
setBit (dest, i, (int)(bool)<D1624>);
<L5>:;
i = i + 1;
<L6>:;
if (i < <D1593>) goto <L3>; else goto <L7>;
<L7>:;
<L8>:;
return;
}
Which is almost identical to the direct copy version:
void copy_2(BitVector&, BitVector&) (dest, src)
{
unsigned int i;
unsigned int <D1586>;
bool T.14;
<D1586> = dest->m_size;
i = 0;
goto <bb 2>;
<L1>:;
T.14 = getBit (src, i);
setBit (dest, i, (int)T.14);
i = i + 1;
<L2>:;
if (i < <D1586>) goto <L1>; else goto <L3>;
<L3>:;
<L4>:;
return;
}
Other related PRs should be fixed similarly. The main changes are:
1. In must-alias we now remove the addressable bit from *every*
promotable variable.
2. There is a new predicate, needs_to_live_in_memory(), which does
the obvious thing and also analyses structure types recursively,
looking for array fields. The results of the type check are
cached to avoid costly repeated calls when dealing with large
structures.
3. In the SRA pass we were mishandling structures with __complex__
types. SRA still does not understand __complex__, so I just
added code to not accept structures for scalarization if they
contain such fields. Brian Booth is working on handling
__complex__ in SRA, so this should be fixed soon.
The patch has very little effect on a typical bootstrap cycle. It does
reduce the size of generated code somewhat, but nothing significant.
It has some effect on PR8361. It shaves a couple of megabytes from the
total allocated memory. User and system time are down about 5%. Mostly
due to the reduction in virtual operands after scalarization.
Bootstrapped and tested on x86, amd64 and ia64.
Diego.
2003-12-15 Diego Novillo <dnovillo@redhat.com>
PR optimization/12747
* tree-cfg.c (verify_addr_expr): Simplify predicates.
* tree-must-alias.c (addresses_needed): Declare as file local.
(can_be_promoted): New.
(tree_compute_must_alias): Call it.
Remove promoted variables from call_clobbered_vars.
(find_addressable_vars): Update comment.
Remove argument. Update callers.
(promote_var): Always clear TREE_ADDRESSABLE.
Don't remove promoted variables from call_clobbered_vars.
If the promoted variable is in the may-alias set of a
non-promotable variable, copy its alias set into the alias set of
the non-promotable variable.
(find_variable_in): Update comment.
* tree-sra.c (can_be_scalarized_p): Reject structures with
__complex__ fields in them.
2003-12-15 Diego Novillo <dnovillo@redhat.com>
Jason Merrill <jason@redhat.com>
PR optimization/12747
* Makefile.in (tree-simple.o): Add dependency on bitmap.h and
$(GGC_H).
(GTFILES): Add tree-simple.c.
* tree-simple.c: Include ggc.h and bitmap.h.
(is_gimple_non_addressable_1): Remove. Update all callers.
(types_checked): New local variable.
(types_in_memory): New local variable.
(struct_needs_to_live_in_memory): New.
(needs_to_live_in_memory): New.
(is_gimple_reg): Call it.
(is_gimple_non_addressable): Call it.
(is_gimple_call_clobbered): Call it.
* tree-simple.h (needs_to_live_in_memory): Declare.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.155
diff -d -c -p -r1.903.2.155 Makefile.in
*** Makefile.in 14 Dec 2003 12:16:20 -0000 1.903.2.155
--- Makefile.in 15 Dec 2003 03:21:21 -0000
*************** c-call-graph.o : c-call-graph.c $(CONFIG
*** 1617,1623 ****
$(C_COMMON_H) diagnostic.h hard-reg-set.h $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
$(TM_H) coretypes.h
tree-simple.o : tree-simple.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(EXPR_H) \
! $(RTL_H) $(TREE_SIMPLE_H) $(TM_H) coretypes.h
tree-mudflap.o : $(CONFIG_H) errors.h $(SYSTEM_H) $(TREE_H) tree-inline.h \
$(C_TREE_H) $(C_COMMON_H) $(TREE_SIMPLE_H) diagnostic.h $(HASHTAB_H) \
output.h varray.h langhooks.h tree-mudflap.h $(TM_H) coretypes.h \
--- 1617,1623 ----
$(C_COMMON_H) diagnostic.h hard-reg-set.h $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
$(TM_H) coretypes.h
tree-simple.o : tree-simple.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(EXPR_H) \
! $(RTL_H) $(TREE_SIMPLE_H) $(TM_H) coretypes.h bitmap.h $(GGC_H)
tree-mudflap.o : $(CONFIG_H) errors.h $(SYSTEM_H) $(TREE_H) tree-inline.h \
$(C_TREE_H) $(C_COMMON_H) $(TREE_SIMPLE_H) diagnostic.h $(HASHTAB_H) \
output.h varray.h langhooks.h tree-mudflap.h $(TM_H) coretypes.h \
*************** GTFILES = $(srcdir)/input.h $(srcdir)/co
*** 2214,2219 ****
--- 2214,2220 ----
$(srcdir)/tree-ssa-pre.c $(srcdir)/tree-iterator.c $(out_file) \
$(srcdir)/tree-alias-type.h $(srcdir)/tree-alias-common.h \
$(srcdir)/tree-alias-type.c $(srcdir)/tree-alias-common.c \
+ $(srcdir)/tree-simple.c \
@all_gtfiles@
GTFILES_FILES_LANGS = @all_gtfiles_files_langs@
Index: tree-must-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-must-alias.c,v
retrieving revision 1.1.2.14
diff -d -c -p -r1.1.2.14 tree-must-alias.c
*** tree-must-alias.c 11 Dec 2003 01:09:16 -0000 1.1.2.14
--- tree-must-alias.c 15 Dec 2003 03:21:21 -0000
*************** Software Foundation, 59 Temple Place - S
*** 40,56 ****
#include "tree-dump.h"
#include "timevar.h"
-
/* Local functions. */
! static void find_addressable_vars (sbitmap);
static void promote_var (tree, bitmap);
static inline int find_variable_in (varray_type, tree);
static inline void remove_element_from (varray_type, size_t);
/* Local variables. */
static FILE *dump_file;
static int dump_flags;
/* This pass finds must-alias relations exposed by constant propagation of
--- 40,73 ----
#include "tree-dump.h"
#include "timevar.h"
/* Local functions. */
! static void find_addressable_vars (void);
static void promote_var (tree, bitmap);
static inline int find_variable_in (varray_type, tree);
static inline void remove_element_from (varray_type, size_t);
+ static inline bool can_be_promoted (tree var);
/* Local variables. */
static FILE *dump_file;
static int dump_flags;
+ static sbitmap addresses_needed;
+
+
+ /* Return true if VAR can be promoted to a GIMPLE register. This function
+ assumes that the address of VAR is not taken by any statement in the
+ function. */
+
+ static inline bool
+ can_be_promoted (tree var)
+ {
+ var_ann_t ann = var_ann (var);
+
+ return (TREE_ADDRESSABLE (var)
+ && !TEST_BIT (addresses_needed, ann->uid)
+ && !ann->has_hidden_use
+ && !needs_to_live_in_memory (var));
+ }
/* This pass finds must-alias relations exposed by constant propagation of
*************** tree_compute_must_alias (tree fndecl, bi
*** 69,75 ****
enum tree_dump_index phase)
{
size_t i;
- sbitmap addresses_needed;
timevar_push (TV_TREE_MUST_ALIAS);
--- 86,91 ----
*************** tree_compute_must_alias (tree fndecl, bi
*** 83,109 ****
sbitmap_zero (addresses_needed);
/* Find variables that still need to have their address taken. */
! find_addressable_vars (addresses_needed);
! /* Now traverse the original list of addressable variables and remove
! those whose addresses are not needed anymore. */
for (i = 0; i < num_call_clobbered_vars; i++)
{
tree var = call_clobbered_var (i);
! var_ann_t ann = var_ann (var);
!
! /* We are only interested in disambiguating addressable locals. */
! if (TREE_ADDRESSABLE (var)
! && !ann->has_hidden_use
! /* FIXME Why exactly do we need to ignore pointers and arrays? */
! && !POINTER_TYPE_P (TREE_TYPE (var))
! && TREE_CODE (TREE_TYPE (var)) != ARRAY_TYPE
! && decl_function_context (var) == current_function_decl
! && !DECL_NONLOCAL (var)
! && !TEST_BIT (addresses_needed, ann->uid))
promote_var (var, vars_to_rename);
}
/* Free allocated memory. */
sbitmap_free (addresses_needed);
--- 99,123 ----
sbitmap_zero (addresses_needed);
/* Find variables that still need to have their address taken. */
! find_addressable_vars ();
! /* Promote call-clobbered variables whose addresses are not needed
! anymore. */
for (i = 0; i < num_call_clobbered_vars; i++)
{
tree var = call_clobbered_var (i);
! if (can_be_promoted (var))
promote_var (var, vars_to_rename);
}
+ /* Remove promoted variables from CALL_CLOBBERED_VARS. */
+ for (i = 0; i < num_call_clobbered_vars; i++)
+ if (!is_gimple_call_clobbered (call_clobbered_var (i)))
+ {
+ remove_element_from (call_clobbered_vars, i);
+ i--; /* Re-set the iterator to account for the removed element. */
+ }
+
/* Free allocated memory. */
sbitmap_free (addresses_needed);
*************** tree_compute_must_alias (tree fndecl, bi
*** 125,135 ****
variables that need to be renamed in a second SSA pass because of the
propagation of ADDR_EXPR values into INDIRECT_REF expressions.
! Return a bitmap indexed by variable UID that will be set if for all
! variables that still need to be addressable. */
static void
! find_addressable_vars (sbitmap addresses_needed)
{
basic_block bb;
--- 139,149 ----
variables that need to be renamed in a second SSA pass because of the
propagation of ADDR_EXPR values into INDIRECT_REF expressions.
! Variables that need to remain addressable are marked in the
! ADDRESSES_NEEDED bitmap. */
static void
! find_addressable_vars (void)
{
basic_block bb;
*************** find_addressable_vars (sbitmap addresses
*** 181,188 ****
continue;
SET_BIT (addresses_needed, var_ann (t)->uid);
}
-
- /* ??? Can and should this be marked for modification? */
}
}
}
--- 195,200 ----
*************** promote_var (tree var, bitmap vars_to_re
*** 199,209 ****
int ix;
var_ann_t ann = var_ann (var);
- /* FIXME: Apparently we always need TREE_ADDRESSABLE for aggregate
- types. Is this a backend quirk or do we actually need these? */
- if (!AGGREGATE_TYPE_P (TREE_TYPE (var)))
- TREE_ADDRESSABLE (var) = 0;
-
/* All VAR's aliases need to be renamed. */
if (ann->may_aliases)
{
--- 211,216 ----
*************** promote_var (tree var, bitmap vars_to_re
*** 216,225 ****
}
}
- ann->may_aliases = NULL;
- ann->is_call_clobbered = 0;
- ann->may_alias_global_mem = 0;
-
/* If the variable was an alias tag, remove it from every variable that
had it in its may-alias set. */
if (ann->is_alias_tag)
--- 223,228 ----
*************** promote_var (tree var, bitmap vars_to_re
*** 241,247 ****
if (ix >= 0)
{
remove_element_from (aliases, (size_t) ix);
! bitmap_set_bit (vars_to_rename, var_ann (aliased_var)->uid);
/* Completely remove the may-alias array if it's empty. */
if (VARRAY_ACTIVE_SIZE (aliases) == 0)
--- 244,276 ----
if (ix >= 0)
{
remove_element_from (aliases, (size_t) ix);
! bitmap_set_bit (vars_to_rename, aliased_ann->uid);
!
! /* If ALIASED_VAR cannot be promoted, bring over the
! may-alias from VAR. */
! if (ann->may_aliases
! && !can_be_promoted (aliased_var))
! {
! size_t j;
!
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "%s: Variable ",
! get_name (current_function_decl));
! print_generic_expr (dump_file, aliased_var, 0);
! fprintf (dump_file, " cannot be promoted. ");
! fprintf (dump_file, "Copying aliases from ");
! print_generic_expr (dump_file, var, 0);
! fprintf (dump_file, ".\n");
! }
!
! for (j = 0; j < VARRAY_ACTIVE_SIZE (ann->may_aliases); j++)
! {
! tree t = VARRAY_TREE (ann->may_aliases, j);
! if (!can_be_promoted (t))
! VARRAY_PUSH_TREE (aliases, t);
! }
! }
/* Completely remove the may-alias array if it's empty. */
if (VARRAY_ACTIVE_SIZE (aliases) == 0)
*************** promote_var (tree var, bitmap vars_to_re
*** 253,266 ****
ann->is_alias_tag = 0;
}
/* Add VAR to the list of variables to rename. */
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
- /* Remove VAR from CALL_CLOBBERED_VARS. */
- ix = find_variable_in (call_clobbered_vars, var);
- if (ix >= 0)
- remove_element_from (call_clobbered_vars, (size_t) ix);
-
/* Debugging dumps. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 282,295 ----
ann->is_alias_tag = 0;
}
+ ann->may_aliases = NULL;
+ ann->is_call_clobbered = 0;
+ ann->may_alias_global_mem = 0;
+ TREE_ADDRESSABLE (var) = 0;
+
/* Add VAR to the list of variables to rename. */
bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
/* Debugging dumps. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** find_variable_in (varray_type array, tre
*** 287,293 ****
/* Remove element I from ARRAY by swapping element I with the last element
! of ARRAY. Do nothing if I is -1. */
static inline void
remove_element_from (varray_type array, size_t i)
--- 316,322 ----
/* Remove element I from ARRAY by swapping element I with the last element
! of ARRAY. */
static inline void
remove_element_from (varray_type array, size_t i)
Index: tree-simple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.c,v
retrieving revision 1.1.4.65
diff -d -c -p -r1.1.4.65 tree-simple.c
*** tree-simple.c 10 Dec 2003 21:43:52 -0000 1.1.4.65
--- tree-simple.c 15 Dec 2003 03:21:21 -0000
*************** Boston, MA 02111-1307, USA. */
*** 23,34 ****
--- 23,36 ----
#include "config.h"
#include "system.h"
#include "coretypes.h"
+ #include "ggc.h"
#include "tm.h"
#include "tree.h"
#include "tree-simple.h"
#include "output.h"
#include "rtl.h"
#include "expr.h"
+ #include "bitmap.h"
/* GCC GIMPLE structure
*************** Boston, MA 02111-1307, USA. */
*** 164,170 ****
*/
static inline bool is_gimple_id (tree);
- static inline bool is_gimple_non_addressable_1 (tree t);
/* Validation of GIMPLE expressions. */
--- 166,171 ----
*************** is_gimple_reg_type (tree type)
*** 404,424 ****
&& TREE_CODE (type) != COMPLEX_TYPE);
}
- /* Helper for is_gimple_reg, is_gimple_non_addressable and
- is_gimple_call_clobbbered. It silently assumes that T is a gimple
- variable. */
! static inline
! bool is_gimple_non_addressable_1 (tree t)
{
! return (! TREE_STATIC (t)
! && ! DECL_EXTERNAL (t)
! && ! TREE_ADDRESSABLE (t)
! /* A volatile decl is not acceptable because we can't reuse it as
! needed. We need to copy it into a temp first. */
! && ! TREE_THIS_VOLATILE (t)
! && ! DECL_NONLOCAL (t)
! && decl_function_context (t) == current_function_decl);
}
/* Return nonzero if T is a scalar register variable. */
--- 405,486 ----
&& TREE_CODE (type) != COMPLEX_TYPE);
}
! /* Used to avoid calling struct_needs_to_live_in_memory repeatedly for the
! same type. */
!
! static GTY(()) bitmap types_checked = NULL;
! static GTY(()) bitmap types_in_memory = NULL;
!
!
! /* Return true if at least one of the fields in T is (or contains) an
! ARRAY_TYPE. */
!
! static bool
! struct_needs_to_live_in_memory (tree t)
{
! tree f;
!
! for (f = TYPE_FIELDS (t); f; f = TREE_CHAIN (f))
! {
! if (TREE_CODE (f) != FIELD_DECL)
! continue;
!
! /* If a field is an array, the structure must go in memory. */
! if (TREE_CODE (TREE_TYPE (f)) == ARRAY_TYPE)
! return true;
!
! /* Check nested structures. */
! if (AGGREGATE_TYPE_P (TREE_TYPE (f))
! && struct_needs_to_live_in_memory (TREE_TYPE (f)))
! return true;
! }
!
! return false;
! }
!
! /* Return true if T (assumed to be a DECL) must be assigned a memory
! location. */
!
! bool
! needs_to_live_in_memory (tree t)
! {
! /* First the quick checks. */
! if (TREE_STATIC (t)
! || DECL_EXTERNAL (t)
! || DECL_NONLOCAL (t)
! || TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE
! || (TREE_CODE (t) == RESULT_DECL
! && aggregate_value_p (t, current_function_decl))
! || decl_function_context (t) != current_function_decl)
! return true;
!
! /* Now, check for structures. A structure will need to live in memory if
! if at least one of its fields is of array type. */
! if (AGGREGATE_TYPE_P (TREE_TYPE (t)))
! {
! tree type = TREE_TYPE (t);
! unsigned int uid = TYPE_UID (type);
!
! if (types_checked == NULL)
! {
! types_checked = BITMAP_GGC_ALLOC ();
! types_in_memory = BITMAP_GGC_ALLOC ();
! }
!
! /* If we have not examined this type already, do so and
! cache the result. */
! if (!bitmap_bit_p (types_checked, uid))
! {
! bitmap_set_bit (types_checked, uid);
! if (struct_needs_to_live_in_memory (type))
! bitmap_set_bit (types_in_memory, uid);
! }
!
! return bitmap_bit_p (types_in_memory, uid);
! }
!
! return false;
}
/* Return nonzero if T is a scalar register variable. */
*************** is_gimple_reg (tree t)
*** 431,437 ****
return (is_gimple_variable (t)
&& is_gimple_reg_type (TREE_TYPE (t))
! && is_gimple_non_addressable_1 (t));
}
/* Return nonzero if T does not need to live in memory. */
--- 493,503 ----
return (is_gimple_variable (t)
&& is_gimple_reg_type (TREE_TYPE (t))
! /* A volatile decl is not acceptable because we can't reuse it as
! needed. We need to copy it into a temp first. */
! && ! TREE_THIS_VOLATILE (t)
! && ! TREE_ADDRESSABLE (t)
! && ! needs_to_live_in_memory (t));
}
/* Return nonzero if T does not need to live in memory. */
*************** is_gimple_non_addressable (tree t)
*** 443,449 ****
t = SSA_NAME_VAR (t);
return (is_gimple_variable (t)
! && is_gimple_non_addressable_1 (t));
}
/* Return true if T may be clobbered by function calls. */
--- 509,516 ----
t = SSA_NAME_VAR (t);
return (is_gimple_variable (t)
! && ! TREE_ADDRESSABLE (t)
! && ! needs_to_live_in_memory (t));
}
/* Return true if T may be clobbered by function calls. */
*************** is_gimple_call_clobbered (tree t)
*** 455,461 ****
t = SSA_NAME_VAR (t);
return (is_gimple_variable (t)
! && !is_gimple_non_addressable_1 (t));
}
/* Return nonzero if T is a GIMPLE rvalue, i.e. an identifier or a
--- 522,529 ----
t = SSA_NAME_VAR (t);
return (is_gimple_variable (t)
! && (TREE_ADDRESSABLE (t)
! || needs_to_live_in_memory (t)));
}
/* Return nonzero if T is a GIMPLE rvalue, i.e. an identifier or a
*************** recalculate_side_effects (tree t)
*** 654,656 ****
--- 722,726 ----
break;
}
}
+
+ #include "gt-tree-simple.h"
Index: tree-simple.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-simple.h,v
retrieving revision 1.1.4.44
diff -d -c -p -r1.1.4.44 tree-simple.h
*** tree-simple.h 7 Dec 2003 10:07:45 -0000 1.1.4.44
--- tree-simple.h 15 Dec 2003 03:21:21 -0000
*************** bool is_gimple_non_addressable (tree t);
*** 75,80 ****
--- 75,83 ----
/* Returns true iff T is a variable that may be modified by function
calls. */
bool is_gimple_call_clobbered (tree t);
+ /* Returns true iff T (assumed to be a variable) needs to be assigned a
+ memory location. */
+ bool needs_to_live_in_memory (tree t);
void recalculate_side_effects (tree);
Index: tree-sra.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-sra.c,v
retrieving revision 1.1.2.6
diff -d -c -p -r1.1.2.6 tree-sra.c
*** tree-sra.c 5 Dec 2003 23:02:24 -0000 1.1.2.6
--- tree-sra.c 15 Dec 2003 03:21:21 -0000
*************** can_be_scalarized_p (tree var)
*** 214,220 ****
}
return false;
}
!
nfields++;
if (nfields > MAX_NFIELDS_FOR_SRA)
--- 214,235 ----
}
return false;
}
!
! /* FIXME: We should handle COMPLEX_TYPEs. Structures with
! __complex__ fields are tested in the libstdc++ testsuite:
! 26_numerics/complex_inserters_extractors.cc. */
! if (TREE_CODE (TREE_TYPE (field)) == COMPLEX_TYPE)
! {
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "Cannot scalarize variable ");
! print_generic_expr (dump_file, var, 0);
! fprintf (dump_file, " because it contains a __complex__ field, ");
! print_generic_expr (dump_file, field, 0);
! fprintf (dump_file, "\n");
! }
! return false;
! }
nfields++;
if (nfields > MAX_NFIELDS_FOR_SRA)