This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH]: Structure aliasing, part 1


On Wed, Mar 09, 2005 at 10:07:45AM -0500, Daniel Berlin wrote:

> 	* tree-flow-inline.h (ref_contains_array_ref): New function.
> 	(lookup_subvars_for_var): Ditto.
> 	(get_subvars_for_var): Ditto.
> 	(var_can_have_subvars): Ditto.
> 	(okay_component_ref_for_subvars): Ditto.
> 
> 	* tree-flow.h (mem_tag_kind): Add STRUCT_FIELD.
> 	(struct subvar): New type.
> 
> 	* tree-optimize.c (init_tree_optimization_passes): Call
> 	pass_create_structure_vars.
> 
> 	* tree-ssa-alias.c: Include vec.h.
> 	(init_alias_info): Don't auto-clear call clobbered on struct-field
> 	tags.
> 	(compute_flow_insensitive_aliasing): Handle subvars.
> 	(group_aliases): Handle STRUCT_FIELD aliases.
> 	(setup_pointers_and_addressables): Ditto.
> 	Don't mark variables non-addressable if they still have
> 	addressable subvars.
> 	Also mark subvars addressable when the real variable is marked
> 	addressable. 
> 	(add_pointed_to_var): Try to prune the pointed-to set by only
> 	pointing to subvars when possible.
> 	Otherwise, make sure we set addresses_needed and pt_vars to
> 	properly include subvars.
> 	(bitpos_of_field): New function.
> 	(push_fields_onto_fieldstack): Ditto.
> 	(get_or_create_used_part_for): Ditto.
> 	(create_overlap_variables_for): Ditto.
> 	(find_used_portions): Ditto.
> 	(create_structure_vars): Ditto.
> 	(pass_create_structure_vars): New structure.
> 
> 	* tree-ssa-operands.c (finalize_ssa_v_must_defs): Remove assert.
> 	(get_expr_operands): Handle subvars.  Also try to turn
> 	COMPONENT_REF accesses into must-defs now that we can accurately
> 	portray it.
> 	(note_addressable): Try to only mark as addressable those subvars
> 	we know a COMPONENT_REF touches.
> 
> 	* tree-vect-analyze.c (vect_object_analysis): Add new parameter.
> 	Handle subvar storing.
> 	(vect_address_analysis): Update caller of vect_object_analysis.
> 
> 	* tree-vect-transform.c (vect_create_data_ref_ptr): Copy subvars.
> 
> 	* tree-vectorizer.h (struct _stmt_vec_info): Add subvars member.
> 	(STMT_VINFO_SUBVARS): New macro.
> 
> 	* doc/invoke.texi: Document fdump-tree-svars.
> 
> 	* doc/tree-ssa.texi: Document structural alias analysis.
> 	
This has been long overdue.  Thanks! There are various places
that need blank lines around and comments that need reformatting.


> +/* Return the underlying variable for REF, if REF is something we can create
> +   subvars for.  If the return value is a SSA_VAR_P, POFFSET will be the
>
This is confusing.  How about, "If REF is a COMPONENT_REF for a
structure that can have sub-variables, return the sub-variable
corresponding to the field referenced by REF."

> +static inline tree
> +okay_component_ref_for_subvars (tree ref, HOST_WIDE_INT *poffset,
> +				HOST_WIDE_INT *psize)
>
Hmm, do we really want this in tree-flow-inline.h?  How about
moving it to tree-dfa.c?


> @@ -347,6 +347,7 @@ init_tree_optimization_passes (void)
>  
>    p = &pass_all_optimizations.sub;
>    NEXT_PASS (pass_referenced_vars);
> +  NEXT_PASS (pass_create_structure_vars);
>
How about creating structure vars after SRA?  Do we really need
to create sub-vars for all structures this hearly?

> +	      /* Since VAR is now a regular GIMPLE register, we will need
> +		 to rename VAR into SSA afterwards.  */
> +	      bitmap_set_bit (vars_to_rename, v_ann->uid);
> +
> +	      if (var_can_have_subvars (var)
> +		  && (svars = get_subvars_for_var (var)))
> +		{
> +		  subvar_t sv;
> +
> +		  for (sv = svars; sv; sv = sv->next)
> +		    {	      
> +		      var_ann_t svann = var_ann (sv->var);
> +		      if (bitmap_bit_p (ai->addresses_needed, svann->uid))
> +			okay_to_mark = false;
> +		      bitmap_set_bit (vars_to_rename, svann->uid);
> +		    }
> +		}
>
Could you factor the operations we do on the sub-vars?
All these loops inside the main logic make things harder to
follow.

> +  if (TREE_CODE (addrop) == COMPONENT_REF
> +      && (ref = okay_component_ref_for_subvars (addrop, &offset ,&size)))
s/ ,&size/, &size/

> -  if (pt_var && SSA_VAR_P (pt_var))
> +      for (sv = svars; sv; sv = sv->next)
> +	{
> +	  if (offset == sv->offset && size == sv->size)
> +	    bitmap_set_bit (pi->pt_vars, var_ann (sv->var)->uid);
> +	  else if (offset >= sv->offset && offset < (sv->offset + sv->size))
> +	    bitmap_set_bit (pi->pt_vars, var_ann (sv->var)->uid);
> +	  else if (offset < sv->offset 
> +		   && (offset + size > sv->offset))
> +	    bitmap_set_bit (pi->pt_vars, var_ann (sv->var)->uid);
>
This needs commenting.  All three alternatives do the same thing.
Perhaps it's better if we just move the three predicates into
one?

> +/* This structure is simply used during pushing fields onto the fieldstack
> +   to track the offset of the field, since bitpos_of_field gives it relative
> +   to it's immediate containing type, and we want it relative to the ultimate
>
s/it's/its/

> +/* Return the position, in bits, of FIELD_DECL from the beginning of it's
>
Likewise.

> +/* Given an aggregate VAR, create the subvariables that represent it's
>
Likewise.

> +      /* Not all fields have DECL_SIZE set for some reason.  Also, we can't
> +	 handle variable sized fields, or fields that are arrays.
> +	 We *could* handle fields that are arrays, but this would require some
> +	 additional hacking to tree-ssa-operands.c so ARRAY_REF's like
> +	 a.b.c[5] were handled correctly (The ARRAY_REF will be handled first,
> +	 so we need to go looking to see if it's part of a structure reference
> +	 at that point, rather than where we do now)*/
>
Hmm?  I think I can parse this, but it sounds confusing.
Needs reformatting too.

> +	  /* We need to copy the various flags from var to sv->var, so that
> +	     they are is_global_var iff the original variable was.  */
> +
> +	  if (DECL_EXTERNAL (var))
> +	    DECL_EXTERNAL (sv->var) = 1;
>
I'd prefer DECL_EXTERNAL (sv->var) = DECL_EXTERNAL (var).

> +	  if (TREE_PUBLIC (var))
> +	    TREE_PUBLIC  (sv->var) = 1;
> +	  if (TREE_STATIC (var))
> +	    TREE_STATIC (sv->var) = 1;
> +	  if (TREE_READONLY (fo->field))
> +	    TREE_READONLY (sv->var) = 1;
> +
Likewise.

> +	  TREE_ADDRESSABLE (sv->var) = 1;
>
Oh?  Why are the SFTs always addressable?  I can see most of them
being so, but are they always?

> +  return NULL_TREE;
> +}
> +/* We are about to create some new referenced variables, and we need the
> +   before size.  */
> +
Spacing after closing brace.

> +static size_t old_referenced_vars;
> +
> +
> +/* Create structure field variables for structures used in this function.  */
> +
> +static void
> +create_structure_vars (void)
> +{
> +  basic_block bb;
> +  size_t i;
> +
> +  old_referenced_vars = num_referenced_vars;
> +  used_portions = xcalloc (num_referenced_vars, sizeof (used_part_t));
> +  
> +  FOR_EACH_BB (bb)
> +    {
> +      block_stmt_iterator bsi;
> +      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
> +	{
> +	  walk_tree_without_duplicates (bsi_stmt_ptr (bsi), 
> +					find_used_portions,
> +					NULL);
> +	}
> +    }
>
This is why I think we probably want to do this after SRA.  Let
the initial scalar cleanup passes remove unreachable code and all
that and then go fishing.  Perhaps we can save ourselves some
work by doing:

	FOR_EACH_BB (bb)
	  {
	    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
	      if (NUM_VUSES > 0 || NUM_VMAY_DEFS || NUM_VMUST_DEFS)
	        walk_tree_without_duplicates...
	  }

> +  for (i = 0; i < old_referenced_vars; i++)
> +    {
> +      tree var = referenced_var (i);
> +      /* The C++ FE creates vars without DECL_SIZE set, for some reason.  */
> +      if (var 	  
> +	  && DECL_SIZE (var)
> +	  && var_can_have_subvars (var)
> +	  && var_ann (var)->mem_tag_kind == NOT_A_TAG
> +	  && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
> +	create_overlap_variables_for (var);
> +    }
>
And if VAR is something that we can SRA away, we save ourselves
the trouble of creating sub-vars for it.

> +  free (used_portions);
> +}
> +struct tree_opt_pass pass_create_structure_vars = 
> +{
>
Spacing after closing brace.

> -      if (code == COMPONENT_REF)
> -	get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
> -      return;
> -
> +      {
> +	tree ref;
> +	HOST_WIDE_INT offset, size;
> + 	/* This component ref becomes an access to all of the subvariables
> +	   it can touch,  if we can determine that, but *NOT* the real one.
> +	   If we can't determine which fields we could touch, the recursion
> +	   will eventually get to a variable and add *all* of it's subvars, or
> +	   whatever is the minimum correct subset.  */
> +
> +	ref = okay_component_ref_for_subvars (expr, &offset, &size);
> +	if (ref)
> +	  {	  
> +	    subvar_t svars = get_subvars_for_var (ref);
> +	    subvar_t sv;
> +	    for (sv = svars; sv; sv = sv->next)
> +	      {
> +		
> +		if (offset == sv->offset && size == sv->size)
> +		    add_stmt_operand (&sv->var, s_ann, flags);
> +		else if (offset >= sv->offset 
> +			 && offset < (sv->offset + sv->size))
> +		  add_stmt_operand (&sv->var, s_ann, flags & ~opf_kill_def);
> +		else if (offset < sv->offset
> +			 && (offset + size > sv->offset))
> +		  add_stmt_operand (&sv->var, s_ann, flags & ~opf_kill_def);
> +	      }
> +	  }
>
Question for future work.  Instead of having to traverse the
sub-variables, would it be worth it to have a more direct mapping
mechanism?  I'm thinking either hashing the fields or using field
uids.  Everything inside get_*_operands is always on relatively
hot paths so I don't know if the additional hash table hackery
would help or make things worse.

How are our timings wrt operand scanning?  Memory usage?

> +Optimizations wishing to create new variables based on existing
> +structure variables need to make sure to either mark the new variables
> +for renaming,  or copy the subvars.
> +
>
I've no idea what you're trying to say here.


All in all, the patch looks good.  It should go in mainline after
addressing the above comments.


Diego.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]