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]

[PATCH] Make SFTs in var_ann a VEC


This patch makes var_ann->subvars a VEC, avoiding to GC allocate
struct subvar (which only holds a tree and a next pointer) for each 
subvar.  This reduces GC overhead and possibly memoy and compile-time
(which is the reason I consider this for stage3).  It also has the
nice side-effect that SFTs for fields with lower offset now have lower
numbers.  It also opens up the possibility to do binary searchs on
the vector where it comes up as necessary.

Bootstrapped and tested on x86_64-unknown-linux-gnu, I'll leave some
time for people to veto on this.

Thanks,
Richard.


2007-10-28  Richard Guenther  <rguenther@suse.de>

	* tree-flow.h (subvar_t): Make it a VEC.
	(struct subvar): Remove.
	(struct var_ann_d): Use VEC(tree,gc) to store subvars.
	* tree-flow-inline.h (get_subvar_at): Adjust iterators over
	variable subvars.
	* tree-into-ssa.c (mark_sym_for_renaming): Likewise.
	* tree-nrv.c (dest_safe_for_nrv_p): Likewise.
	* tree-ssa-alias.c (mark_aliases_call_clobbered): Likewise.
	(set_initial_properties): Likewise.
	(setup_pointers_and_addressables): Likewise.
	(new_type_alias): Likewise.
	(create_overlap_variables_for): Likewise.
	* tree-dfa.c (dump_subvars_for): Likewise.
	* tree-ssa-operands.c (add_vars_for_offset): Likewise.
	(get_expr_operands): Likewise.
	(add_to_addressable_set): Likewise.
	* tree-ssa-structalias.c (set_uids_in_ptset): Likewise.

	* gcc.dg/tree-ssa/alias-15.c: Adjust pattern.

Index: tree-into-ssa.c
===================================================================
*** tree-into-ssa.c	(revision 129695)
--- tree-into-ssa.c	(working copy)
*************** mark_sym_for_renaming (tree sym)
*** 2793,2801 ****
      subvar_t svars;
      if (var_can_have_subvars (sym) && (svars = get_subvars_for_var (sym)))
        {
! 	subvar_t sv;
! 	for (sv = svars; sv; sv = sv->next)
! 	  mark_sym_for_renaming (sv->var);
        }
    }
  
--- 2793,2803 ----
      subvar_t svars;
      if (var_can_have_subvars (sym) && (svars = get_subvars_for_var (sym)))
        {
!         unsigned int i;
! 	tree subvar;
! 
! 	for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
! 	  mark_sym_for_renaming (subvar);
        }
    }
  
Index: tree-nrv.c
===================================================================
*** tree-nrv.c	(revision 129695)
--- tree-nrv.c	(working copy)
*************** struct tree_opt_pass pass_nrv = 
*** 249,255 ****
  static bool
  dest_safe_for_nrv_p (tree dest)
  {
!   subvar_t subvar;
  
    while (handled_component_p (dest))
      dest = TREE_OPERAND (dest, 0);
--- 249,257 ----
  static bool
  dest_safe_for_nrv_p (tree dest)
  {
!   subvar_t sv;
!   unsigned int i;
!   tree subvar;
  
    while (handled_component_p (dest))
      dest = TREE_OPERAND (dest, 0);
*************** dest_safe_for_nrv_p (tree dest)
*** 262,270 ****
  
    if (is_call_clobbered (dest))
      return false;
!   for (subvar = get_subvars_for_var (dest); subvar; subvar = subvar->next)
!     if (is_call_clobbered (subvar->var))
        return false;
    return true;
  }
  
--- 264,275 ----
  
    if (is_call_clobbered (dest))
      return false;
! 
!   sv = get_subvars_for_var (dest);
!   for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
!     if (is_call_clobbered (subvar))
        return false;
+ 
    return true;
  }
  
Index: tree-flow-inline.h
===================================================================
*** tree-flow-inline.h	(revision 129695)
--- tree-flow-inline.h	(working copy)
*************** get_subvars_for_var (tree var)
*** 1609,1619 ****
  static inline tree
  get_subvar_at (tree var, unsigned HOST_WIDE_INT offset)
  {
!   subvar_t sv;
! 
!   for (sv = get_subvars_for_var (var); sv; sv = sv->next)
!     if (SFT_OFFSET (sv->var) == offset)
!       return sv->var;
  
    return NULL_TREE;
  }
--- 1609,1622 ----
  static inline tree
  get_subvar_at (tree var, unsigned HOST_WIDE_INT offset)
  {
!   subvar_t sv = get_subvars_for_var (var);
!   unsigned int i;
!   tree subvar;
! 
!   /* ???  Binary search would be possible here.  */
!   for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
!     if (SFT_OFFSET (subvar) == offset)
!       return subvar;
  
    return NULL_TREE;
  }
Index: tree-dfa.c
===================================================================
*** tree-dfa.c	(revision 129695)
--- tree-dfa.c	(working copy)
*************** void
*** 276,290 ****
  dump_subvars_for (FILE *file, tree var)
  {
    subvar_t sv = get_subvars_for_var (var);
  
    if (!sv)
      return;
  
    fprintf (file, "{ ");
  
!   for (; sv; sv = sv->next)
      {
!       print_generic_expr (file, sv->var, dump_flags);
        fprintf (file, " ");
      }
  
--- 276,292 ----
  dump_subvars_for (FILE *file, tree var)
  {
    subvar_t sv = get_subvars_for_var (var);
+   tree subvar;
+   unsigned int i;
  
    if (!sv)
      return;
  
    fprintf (file, "{ ");
  
!   for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
      {
!       print_generic_expr (file, subvar, dump_flags);
        fprintf (file, " ");
      }
  
Index: tree-flow.h
===================================================================
*** tree-flow.h	(revision 129695)
--- tree-flow.h	(working copy)
*************** enum noalias_state {
*** 308,325 ****
  };
  
  
! struct subvar;
! typedef struct subvar *subvar_t;
! 
! /* This structure represents a fake sub-variable for a structure field.  */
! struct subvar GTY(())
! {
!   /* Fake variable.  */
!   tree var;
! 
!   /* Next subvar for this structure.  */
!   subvar_t next;
! };
  
  struct var_ann_d GTY(())
  {
--- 308,314 ----
  };
  
  
! typedef VEC(tree,gc) *subvar_t;
  
  struct var_ann_d GTY(())
  {
*************** struct var_ann_d GTY(())
*** 384,392 ****
       current version of this variable (an SSA_NAME).  */
    tree current_def;
  
!   /* If this variable is a structure, this fields holds a list of
!      symbols representing each of the fields of the structure.  */
!   subvar_t subvars;
  
    /* Mask of values saying the reasons why this variable has escaped
       the function.  */
--- 373,381 ----
       current version of this variable (an SSA_NAME).  */
    tree current_def;
  
!   /* If this variable is a structure, this fields holds an array
!      of symbols representing each of the fields of the structure.  */
!   VEC(tree,gc) *subvars;
  
    /* Mask of values saying the reasons why this variable has escaped
       the function.  */
Index: tree-ssa-operands.c
===================================================================
*** tree-ssa-operands.c	(revision 129695)
--- tree-ssa-operands.c	(working copy)
*************** add_vars_for_offset (tree full_ref, tree
*** 1421,1440 ****
      {      
        bool added = false;
        subvar_t sv = get_subvars_for_var (SFT_PARENT_VAR (var));
!       for (; sv; sv = sv->next)
  	{
  	  /* Once we hit the end of the parts that could touch,
  	     stop looking.  */
  	  if (size != -1
! 	      && SFT_OFFSET (var) + offset + size <= SFT_OFFSET (sv->var))
  	    break;
! 	  if (overlap_subvar (SFT_OFFSET (var) + offset, size, sv->var, NULL))
  	    {
  	      added = true;
  	      if (is_def)
! 		append_vdef (sv->var);
  	      else
! 		append_vuse (sv->var);
  	    }
  	}
        return added;
--- 1421,1443 ----
      {      
        bool added = false;
        subvar_t sv = get_subvars_for_var (SFT_PARENT_VAR (var));
!       unsigned int i;
!       tree subvar;
! 
!       for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
  	{
  	  /* Once we hit the end of the parts that could touch,
  	     stop looking.  */
  	  if (size != -1
! 	      && SFT_OFFSET (var) + offset + size <= SFT_OFFSET (subvar))
  	    break;
! 	  if (overlap_subvar (SFT_OFFSET (var) + offset, size, subvar, NULL))
  	    {
  	      added = true;
  	      if (is_def)
! 		append_vdef (subvar);
  	      else
! 		append_vuse (subvar);
  	    }
  	}
        return added;
*************** get_expr_operands (tree stmt, tree *expr
*** 2092,2100 ****
  	if (var_can_have_subvars (expr)
  	    && (svars = get_subvars_for_var (expr)))
  	  {
! 	    subvar_t sv;
! 	    for (sv = svars; sv; sv = sv->next)
! 	      add_stmt_operand (&sv->var, s_ann, flags);
  	  }
  	else
  	  add_stmt_operand (expr_p, s_ann, flags);
--- 2095,2104 ----
  	if (var_can_have_subvars (expr)
  	    && (svars = get_subvars_for_var (expr)))
  	  {
! 	    unsigned int i;
! 	    tree subvar;
! 	    for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
! 	      add_stmt_operand (&subvar, s_ann, flags);
  	  }
  	else
  	  add_stmt_operand (expr_p, s_ann, flags);
*************** get_expr_operands (tree stmt, tree *expr
*** 2137,2154 ****
  	ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
  	if (SSA_VAR_P (ref) && get_subvars_for_var (ref))
  	  {
- 	    subvar_t sv;
  	    subvar_t svars = get_subvars_for_var (ref);
  
! 	    for (sv = svars; sv; sv = sv->next)
  	      {
  		bool exact;		
  
! 		if (overlap_subvar (offset, maxsize, sv->var, &exact))
  		  {
  	            int subvar_flags = flags;
  		    none = false;
! 		    add_stmt_operand (&sv->var, s_ann, subvar_flags);
  		  }
  	      }
  
--- 2141,2159 ----
  	ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
  	if (SSA_VAR_P (ref) && get_subvars_for_var (ref))
  	  {
  	    subvar_t svars = get_subvars_for_var (ref);
+ 	    unsigned int i;
+ 	    tree subvar;
  
! 	    for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
  	      {
  		bool exact;		
  
! 		if (overlap_subvar (offset, maxsize, subvar, &exact))
  		  {
  	            int subvar_flags = flags;
  		    none = false;
! 		    add_stmt_operand (&subvar, s_ann, subvar_flags);
  		  }
  	      }
  
*************** add_to_addressable_set (tree ref, bitmap
*** 2710,2720 ****
        if (var_can_have_subvars (var)
  	  && (svars = get_subvars_for_var (var)))
  	{
! 	  subvar_t sv;
! 	  for (sv = svars; sv; sv = sv->next)
  	    {
! 	      bitmap_set_bit (*addresses_taken, DECL_UID (sv->var));
! 	      TREE_ADDRESSABLE (sv->var) = 1;
  	    }
  	}
        else
--- 2715,2726 ----
        if (var_can_have_subvars (var)
  	  && (svars = get_subvars_for_var (var)))
  	{
! 	  unsigned int i;
! 	  tree subvar;
! 	  for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
  	    {
! 	      bitmap_set_bit (*addresses_taken, DECL_UID (subvar));
! 	      TREE_ADDRESSABLE (subvar) = 1;
  	    }
  	}
        else
Index: tree-ssa-alias.c
===================================================================
*** tree-ssa-alias.c	(revision 129695)
--- tree-ssa-alias.c	(working copy)
*************** mark_aliases_call_clobbered (tree tag, V
*** 422,432 ****
      {
        EXECUTE_IF_SET_IN_BITMAP (queued, 0, i, bi)
  	{
! 	  subvar_t svars;
! 	  svars = get_subvars_for_var (referenced_var (i));
! 	  for (; svars; svars = svars->next)
! 	    if (!unmodifiable_var_p (svars->var))
! 	       mark_call_clobbered (svars->var, ta->escape_mask);
  	}
        bitmap_clear (queued);
      }
--- 422,434 ----
      {
        EXECUTE_IF_SET_IN_BITMAP (queued, 0, i, bi)
  	{
! 	  subvar_t svars = get_subvars_for_var (referenced_var (i));
! 	  unsigned int i;
! 	  tree subvar;
! 
! 	  for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
! 	    if (!unmodifiable_var_p (subvar))
! 	       mark_call_clobbered (subvar, ta->escape_mask);
  	}
        bitmap_clear (queued);
      }
*************** set_initial_properties (struct alias_inf
*** 600,610 ****
  		{
  		  EXECUTE_IF_SET_IN_BITMAP (queued, 0, j, bi)
  		    {
! 		      subvar_t svars;
! 		      svars = get_subvars_for_var (referenced_var (j));
! 		      for (; svars; svars = svars->next)
! 			if (!unmodifiable_var_p (svars->var))
! 			  mark_call_clobbered (svars->var, pi->escape_mask);
  		    }
  		  bitmap_clear (queued);
  		}
--- 602,614 ----
  		{
  		  EXECUTE_IF_SET_IN_BITMAP (queued, 0, j, bi)
  		    {
! 		      subvar_t svars = get_subvars_for_var (referenced_var (j));
! 		      unsigned int i;
! 		      tree subvar;
! 
! 		      for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
! 			if (!unmodifiable_var_p (subvar))
! 			  mark_call_clobbered (subvar, pi->escape_mask);
  		    }
  		  bitmap_clear (queued);
  		}
*************** setup_pointers_and_addressables (struct 
*** 2644,2657 ****
  	      if (var_can_have_subvars (var)
  		  && (svars = get_subvars_for_var (var)))
  		{
! 		  subvar_t sv;
  
! 		  for (sv = svars; sv; sv = sv->next)
  		    {	      
  		      if (bitmap_bit_p (gimple_addressable_vars (cfun),
! 					DECL_UID (sv->var)))
  			okay_to_mark = false;
! 		      mark_sym_for_renaming (sv->var);
  		    }
  		}
  
--- 2648,2662 ----
  	      if (var_can_have_subvars (var)
  		  && (svars = get_subvars_for_var (var)))
  		{
! 		  unsigned int i;
! 		  tree subvar;
  
! 		  for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
  		    {	      
  		      if (bitmap_bit_p (gimple_addressable_vars (cfun),
! 					DECL_UID (subvar)))
  			okay_to_mark = false;
! 		      mark_sym_for_renaming (subvar);
  		    }
  		}
  
*************** new_type_alias (tree ptr, tree var, tree
*** 3574,3581 ****
    HOST_WIDE_INT offset, size, maxsize;
    tree ref;
    VEC (tree, heap) *overlaps = NULL;
!   subvar_t sv;
!   unsigned int len;
  
    gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
    gcc_assert (!MTAG_P (var));
--- 3579,3587 ----
    HOST_WIDE_INT offset, size, maxsize;
    tree ref;
    VEC (tree, heap) *overlaps = NULL;
!   unsigned int len, i;
!   tree subvar;
! 
  
    gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
    gcc_assert (!MTAG_P (var));
*************** new_type_alias (tree ptr, tree var, tree
*** 3591,3602 ****
    if (var_can_have_subvars (ref)
        && (svars = get_subvars_for_var (ref)))
      {
!       for (sv = svars; sv; sv = sv->next)
  	{
            bool exact;
  
!           if (overlap_subvar (offset, maxsize, sv->var, &exact))
!             VEC_safe_push (tree, heap, overlaps, sv->var);
          }
        gcc_assert (overlaps != NULL);
      }
--- 3597,3608 ----
    if (var_can_have_subvars (ref)
        && (svars = get_subvars_for_var (ref)))
      {
!       for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
  	{
            bool exact;
  
!           if (overlap_subvar (offset, maxsize, subvar, &exact))
!             VEC_safe_push (tree, heap, overlaps, subvar);
          }
        gcc_assert (overlaps != NULL);
      }
*************** new_type_alias (tree ptr, tree var, tree
*** 3610,3617 ****
  	 On mem-ssa branch, the scanning for virtual operands have been
  	 split from the rest of tree-ssa-operands, so it should be much
  	 easier to fix this problem correctly once mem-ssa is merged.  */
!       for (sv = svars; sv; sv = sv->next)
! 	VEC_safe_push (tree, heap, overlaps, sv->var);
  
        gcc_assert (overlaps != NULL);
      }
--- 3616,3623 ----
  	 On mem-ssa branch, the scanning for virtual operands have been
  	 split from the rest of tree-ssa-operands, so it should be much
  	 easier to fix this problem correctly once mem-ssa is merged.  */
!       for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i)
! 	VEC_safe_push (tree, heap, overlaps, subvar);
  
        gcc_assert (overlaps != NULL);
      }
*************** create_overlap_variables_for (tree var)
*** 3873,3887 ****
        
        /* Otherwise, create the variables.  */
        subvars = lookup_subvars_for_var (var);
!       
        sort_fieldstack (fieldstack);
  
!       for (i = VEC_length (fieldoff_s, fieldstack);
! 	   VEC_iterate (fieldoff_s, fieldstack, --i, fo);)
  	{
- 	  subvar_t sv;
  	  HOST_WIDE_INT fosize;
! 	  tree currfotype;
  
  	  fosize = TREE_INT_CST_LOW (fo->size);
  	  currfotype = fo->type;
--- 3879,3892 ----
        
        /* Otherwise, create the variables.  */
        subvars = lookup_subvars_for_var (var);
!       *subvars = VEC_alloc (tree, gc, VEC_length (fieldoff_s, fieldstack));
!  
        sort_fieldstack (fieldstack);
  
!       for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); ++i)
  	{
  	  HOST_WIDE_INT fosize;
! 	  tree currfotype, subvar;
  
  	  fosize = TREE_INT_CST_LOW (fo->size);
  	  currfotype = fo->type;
*************** create_overlap_variables_for (tree var)
*** 3900,3925 ****
  		  && fosize == lastfosize
  		  && currfotype == lastfotype))
  	    continue;
! 	  sv = GGC_NEW (struct subvar);
! 	  sv->next = *subvars;
! 	  sv->var =
! 	    create_sft (var, fo->type, fo->offset, fosize, fo->alias_set);
  
  	  if (dump_file)
  	    {
  	      fprintf (dump_file, "structure field tag %s created for var %s",
! 		       get_name (sv->var), get_name (var));
  	      fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
! 		       SFT_OFFSET (sv->var));
  	      fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
! 		       SFT_SIZE (sv->var));
  	      fprintf (dump_file, "\n");
  	    }
  	  
  	  lastfotype = currfotype;
  	  lastfooffset = fo->offset;
  	  lastfosize = fosize;
- 	  *subvars = sv;
  	}
  
        /* Once we have created subvars, the original is no longer call
--- 3905,3928 ----
  		  && fosize == lastfosize
  		  && currfotype == lastfotype))
  	    continue;
! 	  subvar = create_sft (var, fo->type, fo->offset,
! 			       fosize, fo->alias_set);
! 	  VEC_quick_push (tree, *subvars, subvar);
  
  	  if (dump_file)
  	    {
  	      fprintf (dump_file, "structure field tag %s created for var %s",
! 		       get_name (subvar), get_name (var));
  	      fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
! 		       SFT_OFFSET (subvar));
  	      fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
! 		       SFT_SIZE (subvar));
  	      fprintf (dump_file, "\n");
  	    }
  	  
  	  lastfotype = currfotype;
  	  lastfooffset = fo->offset;
  	  lastfosize = fosize;
  	}
  
        /* Once we have created subvars, the original is no longer call
Index: tree-ssa-structalias.c
===================================================================
*** tree-ssa-structalias.c	(revision 129695)
--- tree-ssa-structalias.c	(working copy)
*************** set_uids_in_ptset (tree ptr, bitmap into
*** 4702,4708 ****
  {
    unsigned int i;
    bitmap_iterator bi;
-   subvar_t sv;
    alias_set_type ptr_alias_set = get_alias_set (TREE_TYPE (ptr));
  
    EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
--- 4702,4707 ----
*************** set_uids_in_ptset (tree ptr, bitmap into
*** 4717,4726 ****
  
        if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
  	{
  	  /* Variables containing unions may need to be converted to
  	     their SFT's, because SFT's can have unions and we cannot.  */
! 	  for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
! 	    bitmap_set_bit (into, DECL_UID (sv->var));
  	}
        else if (TREE_CODE (vi->decl) == VAR_DECL
  	       || TREE_CODE (vi->decl) == PARM_DECL
--- 4716,4729 ----
  
        if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
  	{
+ 	  unsigned int i;
+ 	  tree subvar;
+ 	  subvar_t sv = get_subvars_for_var (vi->decl);
+ 
  	  /* Variables containing unions may need to be converted to
  	     their SFT's, because SFT's can have unions and we cannot.  */
! 	  for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
! 	    bitmap_set_bit (into, DECL_UID (subvar));
  	}
        else if (TREE_CODE (vi->decl) == VAR_DECL
  	       || TREE_CODE (vi->decl) == PARM_DECL
Index: testsuite/gcc.dg/tree-ssa/alias-15.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/alias-15.c	(revision 129695)
--- testsuite/gcc.dg/tree-ssa/alias-15.c	(working copy)
*************** int test2(void)
*** 15,20 ****
    return p->b[3] - m.b.b[3];
  }
  
! /* { dg-final { scan-tree-dump "SFT.1 created for var m offset 128" "salias" } } */
! /* { dg-final { scan-tree-dump-times "VUSE <SFT.1_" 2 "salias" } } */
  /* { dg-final { cleanup-tree-dump "salias" } } */
--- 15,20 ----
    return p->b[3] - m.b.b[3];
  }
  
! /* { dg-final { scan-tree-dump "SFT.5 created for var m offset 128" "salias" } } */
! /* { dg-final { scan-tree-dump-times "VUSE <SFT.5_" 2 "salias" } } */
  /* { dg-final { cleanup-tree-dump "salias" } } */


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