[PATCH][RFC] Reduce the number of fields in field-sensitive PTA
Daniel Berlin
dberlin@dberlin.org
Fri Jul 4 21:04:00 GMT 2008
This is fine.
On Wed, Jul 2, 2008 at 10:56 AM, Richard Guenther <rguenther@suse.de> wrote:
>
> This removes most of the sub-fields generated by field-sensitive PTA.
> It does so by globbing adjacent non-pointer fields into a single
> sub-variable. This should get rid of a significant fraction of
> sub-fields (assuming that usually structs contain data, not pointers).
>
> This should not weaken the PTA analysis (remember that for the
> resulting points-to sets all sub-fields map back to their decl).
>
> The patch changes the dump of vars to decl.offset+size, so you now see
>
> CALLUSED = { f f.256+64 f.128+128 f.64+64 i q }
>
> in the dumps.
>
> Bootstrap & regtest on x86_64-unknown-linux-gnu running.
>
> Ok for trunk? With this we should be able to reduce the default
> of max-fields-for-field-sensitive to something more sane, say 10.
>
> Thanks,
> Richard.
>
> 2008-07-02 Richard Guenther <rguenther@suse.de>
>
> * tree-ssa-structalias.c (struct variable_info): Remove has_union.
> (new_var_info): Deal with it.
> (solution_set_add): Likewise.
> (bitpos_of_field): Make signed, fix.
> (struct fieldoff): Remove type and decl fields. Make size field
> unsigned HOST_WIDE_INT. Add has_unknown_size and may_have_pointers
> flags.
> (fieldoff_compare): Deal with it.
> (push_fields_onto_fieldstack): Remove has_union argument, glob
> adjacent non-pointer fields together.
> (create_function_info_for): Do not set has_union.
> (create_variable_info_for): Simplify.
>
> Index: trunk/gcc/tree-ssa-structalias.c
> ===================================================================
> *** trunk.orig/gcc/tree-ssa-structalias.c 2008-07-02
> 16:16:49.000000000 +0200
> --- trunk/gcc/tree-ssa-structalias.c 2008-07-02 16:36:01.000000000 +0200
> *************** struct variable_info
> *** 220,228 ****
> /* True for variables whose size is not known or variable. */
> unsigned int is_unknown_size_var:1;
>
> - /* True for variables that have unions somewhere in them. */
> - unsigned int has_union:1;
> -
> /* True if this is a heap variable. */
> unsigned int is_heap_var:1;
>
> --- 220,225 ----
> *************** new_var_info (tree t, unsigned int id, c
> *** 375,381 ****
> ret->is_heap_var = false;
> ret->is_special_var = false;
> ret->is_unknown_size_var = false;
> - ret->has_union = false;
> var = t;
> if (TREE_CODE (var) == SSA_NAME)
> var = SSA_NAME_VAR (var);
> --- 372,377 ----
> *************** solution_set_add (bitmap set, unsigned H
> *** 768,774 ****
> bitmap_set_bit (result, v->id);
> }
> else if (get_varinfo (i)->is_artificial_var
> - || get_varinfo (i)->has_union
> || get_varinfo (i)->is_unknown_size_var)
> {
> bitmap_set_bit (result, i);
> --- 764,769 ----
> *************** could_have_pointers (tree t)
> *** 2628,2643 ****
> /* Return the position, in bits, of FIELD_DECL from the beginning of its
> structure. */
>
> ! static unsigned HOST_WIDE_INT
> bitpos_of_field (const tree fdecl)
> {
>
> ! if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
> ! || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
> return -1;
>
> ! return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
> ! + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
> }
>
>
> --- 2623,2638 ----
> /* Return the position, in bits, of FIELD_DECL from the beginning of its
> structure. */
>
> ! static HOST_WIDE_INT
> bitpos_of_field (const tree fdecl)
> {
>
> ! if (!host_integerp (DECL_FIELD_OFFSET (fdecl), 0)
> ! || !host_integerp (DECL_FIELD_BIT_OFFSET (fdecl), 0))
> return -1;
>
> ! return (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (fdecl)) * 8
> ! + TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (fdecl)));
> }
>
>
> *************** insert_into_field_list_sorted (varinfo_t
> *** 3963,3979 ****
>
> struct fieldoff
> {
> ! /* Type of the field. */
> ! tree type;
>
> /* Size, in bits, of the field. */
> ! tree size;
>
> ! /* Field. */
> ! tree decl;
>
> ! /* Offset from the base of the base containing object to this field. */
> ! HOST_WIDE_INT offset;
> };
> typedef struct fieldoff fieldoff_s;
>
> --- 3958,3972 ----
>
> struct fieldoff
> {
> ! /* Offset from the base of the base containing object to this field. */
> ! HOST_WIDE_INT offset;
>
> /* Size, in bits, of the field. */
> ! unsigned HOST_WIDE_INT size;
>
> ! unsigned has_unknown_size : 1;
>
> ! unsigned may_have_pointers : 1;
> };
> typedef struct fieldoff fieldoff_s;
>
> *************** fieldoff_compare (const void *pa, const
> *** 3994,4003 ****
> else if (foa->offset > fob->offset)
> return 1;
>
> ! foasize = TREE_INT_CST_LOW (foa->size);
> ! fobsize = TREE_INT_CST_LOW (fob->size);
> if (foasize < fobsize)
> ! return - 1;
> else if (foasize > fobsize)
> return 1;
> return 0;
> --- 3987,3996 ----
> else if (foa->offset > fob->offset)
> return 1;
>
> ! foasize = foa->size;
> ! fobsize = fob->size;
> if (foasize < fobsize)
> ! return -1;
> else if (foasize > fobsize)
> return 1;
> return 0;
> *************** var_can_have_subvars (const_tree v)
> *** 4041,4054 ****
>
> OFFSET is used to keep track of the offset in this entire
> structure, rather than just the immediately containing structure.
> ! Returns the number of fields pushed.
> ! ! HAS_UNION is set to true if we find a union type as a field of
> ! TYPE. */
>
> static int
> push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
> ! HOST_WIDE_INT offset, bool *has_union)
> {
> tree field;
> int count = 0;
> --- 4034,4044 ----
>
> OFFSET is used to keep track of the offset in this entire
> structure, rather than just the immediately containing structure.
> ! Returns the number of fields pushed. */
>
> static int
> push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack,
> ! HOST_WIDE_INT offset)
> {
> tree field;
> int count = 0;
> *************** push_fields_onto_fieldstack (tree type,
> *** 4067,4085 ****
> {
> bool push = false;
> int pushed = 0;
>
> ! if (has_union
> ! && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
> ! || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE))
> ! *has_union = true;
> ! ! if (!var_can_have_subvars (field))
> push = true;
> else if (!(pushed = push_fields_onto_fieldstack
> ! (TREE_TYPE (field),
> ! fieldstack,
> ! offset + bitpos_of_field (field),
> ! has_union))
> && (DECL_SIZE (field)
> && !integer_zerop (DECL_SIZE (field))))
> /* Empty structures may have actual size, like in C++. So
> --- 4057,4070 ----
> {
> bool push = false;
> int pushed = 0;
> + HOST_WIDE_INT foff = bitpos_of_field (field);
>
> ! if (!var_can_have_subvars (field)
> ! || TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE
> ! || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)
> push = true;
> else if (!(pushed = push_fields_onto_fieldstack
> ! (TREE_TYPE (field), fieldstack, offset + foff))
> && (DECL_SIZE (field)
> && !integer_zerop (DECL_SIZE (field))))
> /* Empty structures may have actual size, like in C++. So
> *************** push_fields_onto_fieldstack (tree type,
> *** 4089,4102 ****
>
> if (push)
> {
> ! fieldoff_s *pair;
>
> ! pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
> ! pair->type = TREE_TYPE (field);
> ! pair->size = DECL_SIZE (field);
> ! pair->decl = field;
> ! pair->offset = offset + bitpos_of_field (field);
> ! count++;
> }
> else
> count += pushed;
> --- 4074,4112 ----
>
> if (push)
> {
> ! fieldoff_s *pair = NULL;
> ! bool has_unknown_size = false;
>
> ! if (!VEC_empty (fieldoff_s, *fieldstack))
> ! pair = VEC_last (fieldoff_s, *fieldstack);
> ! ! if (!DECL_SIZE (field)
> ! || !host_integerp (DECL_SIZE (field), 1))
> ! has_unknown_size = true;
> ! ! /* If adjacent fields do not contain pointers merge them. */
> ! if (pair
> ! && !pair->may_have_pointers
> ! && !could_have_pointers (field)
> ! && !pair->has_unknown_size
> ! && !has_unknown_size
> ! && pair->offset + (HOST_WIDE_INT)pair->size == offset +
> foff)
> ! {
> ! pair = VEC_last (fieldoff_s, *fieldstack);
> ! pair->size += TREE_INT_CST_LOW (DECL_SIZE (field));
> ! }
> ! else
> ! {
> ! pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL);
> ! pair->offset = offset + foff;
> ! pair->has_unknown_size = has_unknown_size;
> ! if (!has_unknown_size)
> ! pair->size = TREE_INT_CST_LOW (DECL_SIZE (field));
> ! else
> ! pair->size = -1;
> ! pair->may_have_pointers = could_have_pointers (field);
> ! count++;
> ! }
> }
> else
> count += pushed;
> *************** create_function_info_for (tree decl, con
> *** 4162,4168 ****
> vi = new_var_info (decl, index, name);
> vi->decl = decl;
> vi->offset = 0;
> - vi->has_union = 0;
> vi->size = 1;
> vi->fullsize = count_num_arguments (decl, &is_varargs) + 1;
> insert_vi_for_tree (vi->decl, vi);
> --- 4172,4177 ----
> *************** create_function_info_for (tree decl, con
> *** 4207,4213 ****
> argvi->offset = i;
> argvi->size = 1;
> argvi->fullsize = vi->fullsize;
> - argvi->has_union = false;
> insert_into_field_list_sorted (vi, argvi);
> stats.total_vars ++;
> if (arg)
> --- 4216,4221 ----
> *************** create_function_info_for (tree decl, con
> *** 4243,4249 ****
> resultvi->offset = i;
> resultvi->size = 1;
> resultvi->fullsize = vi->fullsize;
> - resultvi->has_union = false;
> insert_into_field_list_sorted (vi, resultvi);
> stats.total_vars ++;
> if (DECL_RESULT (decl))
> --- 4251,4256 ----
> *************** create_variable_info_for (tree decl, con
> *** 4283,4307 ****
> varinfo_t vi;
> tree decltype = TREE_TYPE (decl);
> tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
> - bool notokay = false;
> - bool hasunion;
> bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
> VEC (fieldoff_s,heap) *fieldstack = NULL;
>
> if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
> return create_function_info_for (decl, name);
>
> ! hasunion = TREE_CODE (decltype) == UNION_TYPE
> ! || TREE_CODE (decltype) == QUAL_UNION_TYPE;
> ! if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
> ! {
> ! push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
> ! if (hasunion)
> ! {
> ! VEC_free (fieldoff_s, heap, fieldstack);
> ! notokay = true;
> ! }
> ! }
>
> /* If the variable doesn't have subvars, we may end up needing to
> sort the field list and create fake variables for all the
> --- 4290,4303 ----
> varinfo_t vi;
> tree decltype = TREE_TYPE (decl);
> tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype);
> bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
> VEC (fieldoff_s,heap) *fieldstack = NULL;
>
> if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode)
> return create_function_info_for (decl, name);
>
> ! if (var_can_have_subvars (decl) && use_field_sensitive)
> ! push_fields_onto_fieldstack (decltype, &fieldstack, 0);
>
> /* If the variable doesn't have subvars, we may end up needing to
> sort the field list and create fake variables for all the
> *************** create_variable_info_for (tree decl, con
> *** 4309,4319 ****
> vi = new_var_info (decl, index, name);
> vi->decl = decl;
> vi->offset = 0;
> - vi->has_union = hasunion;
> if (!declsize
> ! || TREE_CODE (declsize) != INTEGER_CST
> ! || TREE_CODE (decltype) == UNION_TYPE
> ! || TREE_CODE (decltype) == QUAL_UNION_TYPE)
> {
> vi->is_unknown_size_var = true;
> vi->fullsize = ~0;
> --- 4305,4312 ----
> vi = new_var_info (decl, index, name);
> vi->decl = decl;
> vi->offset = 0;
> if (!declsize
> ! || !host_integerp (declsize, 1))
> {
> vi->is_unknown_size_var = true;
> vi->fullsize = ~0;
> *************** create_variable_info_for (tree decl, con
> *** 4333,4339 ****
>
> stats.total_vars++;
> if (use_field_sensitive
> - && !notokay
> && !vi->is_unknown_size_var
> && var_can_have_subvars (decl)
> && VEC_length (fieldoff_s, fieldstack) > 1
> --- 4326,4331 ----
> *************** create_variable_info_for (tree decl, con
> *** 4341,4352 ****
> {
> unsigned int newindex = VEC_length (varinfo_t, varmap);
> fieldoff_s *fo = NULL;
> unsigned int i;
>
> for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo);
> i++)
> {
> ! if (! fo->size
> ! || TREE_CODE (fo->size) != INTEGER_CST
> || fo->offset < 0)
> {
> notokay = true;
> --- 4333,4344 ----
> {
> unsigned int newindex = VEC_length (varinfo_t, varmap);
> fieldoff_s *fo = NULL;
> + bool notokay = false;
> unsigned int i;
>
> for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo);
> i++)
> {
> ! if (fo->has_unknown_size
> || fo->offset < 0)
> {
> notokay = true;
> *************** create_variable_info_for (tree decl, con
> *** 4381,4387 ****
> return index;
> }
>
> ! vi->size = TREE_INT_CST_LOW (fo->size);
> vi->offset = fo->offset;
> for (i = VEC_length (fieldoff_s, fieldstack) - 1;
> i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
> --- 4373,4379 ----
> return index;
> }
>
> ! vi->size = fo->size;
> vi->offset = fo->offset;
> for (i = VEC_length (fieldoff_s, fieldstack) - 1;
> i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo);
> *************** create_variable_info_for (tree decl, con
> *** 4394,4416 ****
> newindex = VEC_length (varinfo_t, varmap);
> if (dump_file)
> {
> ! if (fo->decl)
> ! asprintf (&tempname, "%s.%s",
> ! vi->name, alias_get_name (fo->decl));
> ! else
> ! asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC,
> ! vi->name, fo->offset);
> newname = ggc_strdup (tempname);
> free (tempname);
> }
> newvi = new_var_info (decl, newindex, newname);
> newvi->offset = fo->offset;
> ! newvi->size = TREE_INT_CST_LOW (fo->size);
> newvi->fullsize = vi->fullsize;
> insert_into_field_list (vi, newvi);
> VEC_safe_push (varinfo_t, heap, varmap, newvi);
> if (is_global && (!flag_whole_program || !in_ipa_mode)
> ! && (!fo->decl || could_have_pointers (fo->decl)))
> make_constraint_from (newvi, escaped_id);
>
> stats.total_vars++;
> --- 4386,4405 ----
> newindex = VEC_length (varinfo_t, varmap);
> if (dump_file)
> {
> ! asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC
> ! "+" HOST_WIDE_INT_PRINT_DEC,
> ! vi->name, fo->offset, fo->size);
> newname = ggc_strdup (tempname);
> free (tempname);
> }
> newvi = new_var_info (decl, newindex, newname);
> newvi->offset = fo->offset;
> ! newvi->size = fo->size;
> newvi->fullsize = vi->fullsize;
> insert_into_field_list (vi, newvi);
> VEC_safe_push (varinfo_t, heap, varmap, newvi);
> if (is_global && (!flag_whole_program || !in_ipa_mode)
> ! && fo->may_have_pointers)
> make_constraint_from (newvi, escaped_id);
>
> stats.total_vars++;
>
More information about the Gcc-patches
mailing list