[PATCH][RFC] Function annotations for noclobber/noescape arguments

[Richard Guenther <rguenther at suse dot de>]

On top of http://gcc.gnu.org/ml/gcc-patches/2009-11/msg01026.html
and http://gcc.gnu.org/ml/gcc-patches/2009-11/msg01027.html this 
implements the ability to annotate functions with information
about their arguments and return value.  The current implementation
encodes this information in a single string (thus it's easily
parsable and doesn't consume much attribute space).

You can mark parameters 1) unused, 2) pointed-to read-only,
3) not escaping, 4) only once dereferenced (thus, access only
*p, not **p)

You can mark return values as being a direct copy of arguments
or as non-aliasing (similar to the malloc attribute).

Bootstrapped and tested on x86_64-unknown-linux-gnu, queued for stage1,
comments appreciated.

I realize it misses documentation, I'll defer that until after
the unavoidable bikeshedding on the syntax.

Richard.

2009-11-23  Richard Guenther  <rguenther@suse.de>

	* c-common.c (struct c_common_attributes): Add fnspec attribute.
	(handle_fnspec_attribute): New function.
	* gimple.h (gimple_call_return_flags): Declare.
	(gimple_call_arg_flags): Likewise.
	* gimple.c (gimple_call_arg_flags): New function.
	(gimple_call_return_flags): Likewise.
	* tree.h (EAF_DIRECT, EAF_NOCLOBBER, EAF_NOESCAPE, EAF_UNUSED):
	New argument flags.
	(ERF_RETURN_ARG_MASK, ERF_RETURNS_ARG, ERF_NOALIAS): New function
	return value flags.
	* tree-ssa-alias.c (ref_maybe_used_by_call_p_1): Skip unused args.
	* tree-ssa-structalias.c (make_constraint_from_heapvar): Split
	main work to ...
	(make_heapvar_for): ... this new function.
	(handle_rhs_call): Handle fnspec attribute argument specifiers.
	(handle_lhs_call): Likewise.
	(find_func_aliases): Adjust.

	* gcc.dg/tree-ssa/ipa-fnann-1.c: New testcase.
	* gcc.dg/tree-ssa/ipa-fnann-2.c: Likewise.

Index: trunk/gcc/c-common.c
===================================================================
*** trunk.orig/gcc/c-common.c	2009-11-18 14:49:27.000000000 +0100
--- trunk/gcc/c-common.c	2009-11-23 14:54:12.000000000 +0100
*************** static tree handle_type_generic_attribut
*** 530,535 ****
--- 530,536 ----
  static tree handle_alloc_size_attribute (tree *, tree, tree, int, bool *);
  static tree handle_target_attribute (tree *, tree, tree, int, bool *);
  static tree handle_optimize_attribute (tree *, tree, tree, int, bool *);
+ static tree handle_fnspec_attribute (tree *, tree, tree, int, bool *);
  
  static void check_function_nonnull (tree, int, tree *);
  static void check_nonnull_arg (void *, tree, unsigned HOST_WIDE_INT);
*************** const struct attribute_spec c_common_att
*** 829,834 ****
--- 830,837 ----
  			      handle_target_attribute },
    { "optimize",               1, -1, true, false, false,
  			      handle_optimize_attribute },
+   { "fnspec",	 	      1, 1, false, true, true,
+ 			      handle_fnspec_attribute },
    { NULL,                     0, 0, false, false, false, NULL }
  };
  
*************** handle_alloc_size_attribute (tree *node,
*** 7103,7108 ****
--- 7106,7129 ----
      }
    return NULL_TREE;
  }
+ 
+ /* Handle a "fnspec" attribute; arguments as in
+    struct attribute_spec.handler.  */
+ 
+ static tree
+ handle_fnspec_attribute (tree *node ATTRIBUTE_UNUSED, tree ARG_UNUSED (name),
+ 			 tree args,
+ 			 int ARG_UNUSED (flags), bool *no_add_attrs)
+ {
+   if (!args
+       || TREE_CODE (TREE_VALUE (args)) != STRING_CST)
+     {
+       warning (OPT_Wattributes,
+ 	       "fnspec attribute without string argument");
+       *no_add_attrs = true;
+     }
+   return NULL_TREE;
+ }
  
  /* Handle a "returns_twice" attribute; arguments as in
     struct attribute_spec.handler.  */
Index: trunk/gcc/gimple.c
===================================================================
*** trunk.orig/gcc/gimple.c	2009-11-23 12:14:54.000000000 +0100
--- trunk/gcc/gimple.c	2009-11-23 14:57:02.000000000 +0100
*************** gimple_call_flags (const_gimple stmt)
*** 1752,1757 ****
--- 1752,1846 ----
    return flags;
  }
  
+ /* Detects argument flags for argument number ARG on call STMT.  */
+ 
+ int
+ gimple_call_arg_flags (const_gimple stmt, unsigned arg)
+ {
+   tree decl;
+   tree attr = NULL_TREE;
+ 
+   decl = gimple_call_fndecl (stmt);
+   if (decl != NULL_TREE)
+     attr = lookup_attribute ("fnspec", DECL_ATTRIBUTES (decl));
+   if (!attr)
+     {
+       tree type = TREE_TYPE (TREE_TYPE (gimple_call_fn (stmt)));
+       attr = lookup_attribute ("fnspec", TYPE_ATTRIBUTES (type));
+     }
+   if (!attr)
+     return 0;
+ 
+   attr = TREE_VALUE (TREE_VALUE (attr));
+   if (1 + arg >= (unsigned) TREE_STRING_LENGTH (attr))
+     return 0;
+ 
+   switch (TREE_STRING_POINTER (attr)[1 + arg])
+     {
+     case 'x':
+     case 'X':
+       return EAF_UNUSED;
+ 
+     case 'R':
+       return EAF_DIRECT | EAF_NOCLOBBER | EAF_NOESCAPE;
+ 
+     case 'r':
+       return EAF_NOCLOBBER | EAF_NOESCAPE;
+ 
+     case 'W':
+       return EAF_DIRECT | EAF_NOESCAPE;
+ 
+     case 'w':
+       return EAF_NOESCAPE;
+ 
+     case '.':
+     default:
+       return 0;
+     }
+ }
+ 
+ /* Detects return flags for the call STMT.  */
+ 
+ int
+ gimple_call_return_flags (const_gimple stmt)
+ {
+   tree decl;
+   tree attr = NULL_TREE;
+ 
+   if (gimple_call_flags (stmt) & ECF_MALLOC)
+     return ERF_NOALIAS;
+ 
+   decl = gimple_call_fndecl (stmt);
+   if (decl != NULL_TREE)
+     attr = lookup_attribute ("fnspec", DECL_ATTRIBUTES (decl));
+   if (!attr)
+     {
+       tree type = TREE_TYPE (TREE_TYPE (gimple_call_fn (stmt)));
+       attr = lookup_attribute ("fnspec", TYPE_ATTRIBUTES (type));
+     }
+   if (!attr)
+     return 0;
+ 
+   attr = TREE_VALUE (TREE_VALUE (attr));
+   if (TREE_STRING_LENGTH (attr) < 1)
+     return 0;
+ 
+   switch (TREE_STRING_POINTER (attr)[0])
+     {
+     case '1':
+     case '2':
+     case '3':
+     case '4':
+       return ERF_RETURNS_ARG | (TREE_STRING_POINTER (attr)[0] - '1');
+ 
+     case 'm':
+       return ERF_NOALIAS;
+ 
+     case '.':
+     default:
+       return 0;
+     }
+ }
  
  /* Return true if GS is a copy assignment.  */
  
Index: trunk/gcc/gimple.h
===================================================================
*** trunk.orig/gcc/gimple.h	2009-11-23 12:14:54.000000000 +0100
--- trunk/gcc/gimple.h	2009-11-23 12:15:45.000000000 +0100
*************** void gimple_seq_free (gimple_seq);
*** 853,858 ****
--- 853,860 ----
  void gimple_seq_add_seq (gimple_seq *, gimple_seq);
  gimple_seq gimple_seq_copy (gimple_seq);
  int gimple_call_flags (const_gimple);
+ int gimple_call_return_flags (const_gimple);
+ int gimple_call_arg_flags (const_gimple, unsigned);
  void gimple_call_reset_alias_info (gimple);
  bool gimple_assign_copy_p (gimple);
  bool gimple_assign_ssa_name_copy_p (gimple);
Index: trunk/gcc/tree-ssa-alias.c
===================================================================
*** trunk.orig/gcc/tree-ssa-alias.c	2009-11-23 12:14:54.000000000 +0100
--- trunk/gcc/tree-ssa-alias.c	2009-11-23 12:15:03.000000000 +0100
*************** process_args:
*** 1028,1033 ****
--- 1028,1037 ----
    for (i = 0; i < gimple_call_num_args (call); ++i)
      {
        tree op = gimple_call_arg (call, i);
+       int flags = gimple_call_arg_flags (call, i);
+ 
+       if (flags & EAF_UNUSED)
+ 	continue;
  
        if (TREE_CODE (op) == WITH_SIZE_EXPR)
  	op = TREE_OPERAND (op, 0);
Index: trunk/gcc/tree-ssa-structalias.c
===================================================================
*** trunk.orig/gcc/tree-ssa-structalias.c	2009-11-23 12:14:55.000000000 +0100
--- trunk/gcc/tree-ssa-structalias.c	2009-11-23 13:10:26.000000000 +0100
*************** make_transitive_closure_constraints (var
*** 3487,3497 ****
    process_constraint (new_constraint (lhs, rhs));
  }
  
! /* Create a new artificial heap variable with NAME and make a
!    constraint from it to LHS.  Return the created variable.  */
  
  static varinfo_t
! make_constraint_from_heapvar (varinfo_t lhs, const char *name)
  {
    varinfo_t vi;
    tree heapvar = heapvar_lookup (lhs->decl, lhs->offset);
--- 3487,3497 ----
    process_constraint (new_constraint (lhs, rhs));
  }
  
! /* Create a new artificial heap variable with NAME.
!    Return the created variable.  */
  
  static varinfo_t
! make_heapvar_for (varinfo_t lhs, const char *name)
  {
    varinfo_t vi;
    tree heapvar = heapvar_lookup (lhs->decl, lhs->offset);
*************** make_constraint_from_heapvar (varinfo_t
*** 3523,3528 ****
--- 3523,3538 ----
    vi->is_full_var = true;
    insert_vi_for_tree (heapvar, vi);
  
+   return vi;
+ }
+ 
+ /* Create a new artificial heap variable with NAME and make a
+    constraint from it to LHS.  Return the created variable.  */
+ 
+ static varinfo_t
+ make_constraint_from_heapvar (varinfo_t lhs, const char *name)
+ {
+   varinfo_t vi = make_heapvar_for (lhs, name);
    make_constraint_from (lhs, vi->id);
  
    return vi;
*************** handle_rhs_call (gimple stmt, VEC(ce_s,
*** 3551,3567 ****
  {
    struct constraint_expr rhsc;
    unsigned i;
  
    for (i = 0; i < gimple_call_num_args (stmt); ++i)
      {
        tree arg = gimple_call_arg (stmt, i);
  
!       /* Find those pointers being passed, and make sure they end up
! 	 pointing to anything.  */
!       if (could_have_pointers (arg))
  	make_escape_constraint (arg);
      }
  
    /* The static chain escapes as well.  */
    if (gimple_call_chain (stmt))
      make_escape_constraint (gimple_call_chain (stmt));
--- 3561,3621 ----
  {
    struct constraint_expr rhsc;
    unsigned i;
+   bool returns_uses = false;
  
    for (i = 0; i < gimple_call_num_args (stmt); ++i)
      {
        tree arg = gimple_call_arg (stmt, i);
+       int flags = gimple_call_arg_flags (stmt, i);
  
!       /* If the argument is not used or it does not contain pointers
! 	 we can ignore it.  */
!       if ((flags & EAF_UNUSED)
! 	  || !could_have_pointers (arg))
! 	continue;
! 
!       /* As we compute ESCAPED context-insensitive we do not gain
!          any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE
! 	 set.  The argument would still get clobbered through the
! 	 escape solution.
! 	 ???  We might get away with less (and more precise) constraints
! 	 if using a temporary for transitively closing things.  */
!       if ((flags & EAF_NOCLOBBER)
! 	   && (flags & EAF_NOESCAPE))
! 	{
! 	  varinfo_t uses = get_call_use_vi (stmt);
! 	  if (!(flags & EAF_DIRECT))
! 	    make_transitive_closure_constraints (uses);
! 	  make_constraint_to (uses->id, arg);
! 	  returns_uses = true;
! 	}
!       else if (flags & EAF_NOESCAPE)
! 	{
! 	  varinfo_t uses = get_call_use_vi (stmt);
! 	  varinfo_t clobbers = get_call_clobber_vi (stmt);
! 	  if (!(flags & EAF_DIRECT))
! 	    {
! 	      make_transitive_closure_constraints (uses);
! 	      make_transitive_closure_constraints (clobbers);
! 	    }
! 	  make_constraint_to (uses->id, arg);
! 	  make_constraint_to (clobbers->id, arg);
! 	  returns_uses = true;
! 	}
!       else
  	make_escape_constraint (arg);
      }
  
+   /* If we added to the calls uses solution make sure we account for
+      pointers to it to be returned.  */
+   if (returns_uses)
+     {
+       rhsc.var = get_call_use_vi (stmt)->id;
+       rhsc.offset = 0;
+       rhsc.type = SCALAR;
+       VEC_safe_push (ce_s, heap, *results, &rhsc);
+     }
+ 
    /* The static chain escapes as well.  */
    if (gimple_call_chain (stmt))
      make_escape_constraint (gimple_call_chain (stmt));
*************** handle_rhs_call (gimple stmt, VEC(ce_s,
*** 3594,3631 ****
     the LHS point to global and escaped variables.  */
  
  static void
! handle_lhs_call (tree lhs, int flags, VEC(ce_s, heap) *rhsc)
  {
    VEC(ce_s, heap) *lhsc = NULL;
  
    get_constraint_for (lhs, &lhsc);
! 
!   if (flags & ECF_MALLOC)
      {
        varinfo_t vi;
!       vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
        /* We delay marking allocated storage global until we know if
           it escapes.  */
        DECL_EXTERNAL (vi->decl) = 0;
        vi->is_global_var = 0;
      }
!   else if (VEC_length (ce_s, rhsc) > 0)
!     {
!       /* If the store is to a global decl make sure to
! 	 add proper escape constraints.  */
!       lhs = get_base_address (lhs);
!       if (lhs
! 	  && DECL_P (lhs)
! 	  && is_global_var (lhs))
! 	{
! 	  struct constraint_expr tmpc;
! 	  tmpc.var = escaped_id;
! 	  tmpc.offset = 0;
! 	  tmpc.type = SCALAR;
! 	  VEC_safe_push (ce_s, heap, lhsc, &tmpc);
! 	}
!       process_all_all_constraints (lhsc, rhsc);
!     }
    VEC_free (ce_s, heap, lhsc);
  }
  
--- 3648,3703 ----
     the LHS point to global and escaped variables.  */
  
  static void
! handle_lhs_call (gimple stmt, tree lhs, int flags, VEC(ce_s, heap) *rhsc)
  {
    VEC(ce_s, heap) *lhsc = NULL;
  
    get_constraint_for (lhs, &lhsc);
!   /* If the store is to a global decl make sure to
!      add proper escape constraints.  */
!   lhs = get_base_address (lhs);
!   if (lhs
!       && DECL_P (lhs)
!       && is_global_var (lhs))
!     {
!       struct constraint_expr tmpc;
!       tmpc.var = escaped_id;
!       tmpc.offset = 0;
!       tmpc.type = SCALAR;
!       VEC_safe_push (ce_s, heap, lhsc, &tmpc);
!     }
! 
!   /* If the call returns an argument unmodified override the rhs
!      constraints.  */
!   flags = gimple_call_return_flags (stmt);
!   if (flags & ERF_RETURNS_ARG
!       && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt))
!     {
!       tree arg;
!       rhsc = NULL;
!       arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK);
!       get_constraint_for (arg, &rhsc);
!       process_all_all_constraints (lhsc, rhsc);
!       VEC_free (ce_s, heap, rhsc);
!     }
!   else if (flags & ERF_NOALIAS)
      {
        varinfo_t vi;
!       struct constraint_expr tmpc;
!       rhsc = NULL;
!       vi = make_heapvar_for (get_vi_for_tree (lhs), "HEAP");
        /* We delay marking allocated storage global until we know if
           it escapes.  */
        DECL_EXTERNAL (vi->decl) = 0;
        vi->is_global_var = 0;
+       tmpc.var = vi->id;
+       tmpc.offset = 0;
+       tmpc.type = ADDRESSOF;
+       VEC_safe_push (ce_s, heap, rhsc, &tmpc);
      }
! 
!   process_all_all_constraints (lhsc, rhsc);
! 
    VEC_free (ce_s, heap, lhsc);
  }
  
*************** find_func_aliases (gimple origt)
*** 3922,3928 ****
  	    handle_rhs_call (t, &rhsc);
  	  if (gimple_call_lhs (t)
  	      && could_have_pointers (gimple_call_lhs (t)))
! 	    handle_lhs_call (gimple_call_lhs (t), flags, rhsc);
  	  VEC_free (ce_s, heap, rhsc);
  	}
        else
--- 3994,4000 ----
  	    handle_rhs_call (t, &rhsc);
  	  if (gimple_call_lhs (t)
  	      && could_have_pointers (gimple_call_lhs (t)))
! 	    handle_lhs_call (t, gimple_call_lhs (t), flags, rhsc);
  	  VEC_free (ce_s, heap, rhsc);
  	}
        else
Index: trunk/gcc/tree.h
===================================================================
*** trunk.orig/gcc/tree.h	2009-11-18 14:49:27.000000000 +0100
--- trunk/gcc/tree.h	2009-11-23 12:15:03.000000000 +0100
*************** extern tree build_duplicate_type (tree);
*** 5085,5090 ****
--- 5085,5114 ----
  extern int flags_from_decl_or_type (const_tree);
  extern int call_expr_flags (const_tree);
  
+ /* Call argument flags.  */
+ 
+ /* Nonzero if the argument is not dereferenced recursively, thus only
+    directly reachable memory is read or written.  */
+ #define EAF_DIRECT		(1 << 0)
+ /* Nonzero if memory reached by the argument is not clobbered.  */
+ #define EAF_NOCLOBBER		(1 << 1)
+ /* Nonzero if the argument does not escape.  */
+ #define EAF_NOESCAPE		(1 << 2)
+ /* Nonzero if the argument is not used by the function.  */
+ #define EAF_UNUSED		(1 << 3)
+ 
+ /* Call return flags.  */
+ 
+ /* Mask for the argument number that is returned.  Lower two bits of
+    the return flags, encodes argument slots zero to three.  */
+ #define ERF_RETURN_ARG_MASK	(3)
+ /* Nonzero if the return value is equal to the argument number
+    flags & ERF_RETURN_ARG_MASK.  */
+ #define ERF_RETURNS_ARG		(1 << 2)
+ /* Nonzero if the return value does not alias with anything.  Functions
+    with the malloc attribute have this set on their return value.  */
+ #define ERF_NOALIAS		(1 << 3)
+ 
  extern int setjmp_call_p (const_tree);
  extern bool gimple_alloca_call_p (const_gimple);
  extern bool alloca_call_p (const_tree);
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ipa-fnann-1.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ipa-fnann-1.c	2009-11-23 13:01:35.000000000 +0100
***************
*** 0 ****
--- 1,27 ----
+ /* { dg-do run } */
+ /* { dg-options "-O1" } */
+ 
+ extern void link_error (void);
+ extern void abort (void);
+ 
+ char * __attribute__((noinline,noclone,fnspec("1r")))
+ foo (char *x)
+ {
+   if (x[0] != '\0')
+     abort ();
+   return x;
+ }
+ 
+ int main()
+ {
+   char x[4];
+   char *p;
+   x[0] = '\0';
+   p = foo (x);
+   if (x[0] != '\0')
+     link_error ();
+   *p = '\1';
+   if (x[0] != '\1')
+     abort ();
+   return 0;
+ }
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ipa-fnann-2.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ipa-fnann-2.c	2009-11-23 13:51:31.000000000 +0100
***************
*** 0 ****
--- 1,41 ----
+ /* { dg-do run } */
+ /* { dg-options "-O1 -fdump-tree-optimized" } */
+ 
+ extern void link_error (void);
+ extern void abort (void);
+ 
+ struct List {
+     struct List *next;
+     struct List *prev;
+ };
+ 
+ void __attribute__((noinline,noclone,fnspec(".W")))
+ foo (struct List *x)
+ {
+   x->next = x;
+ }
+ 
+ int main()
+ {
+   struct List head, mid, tail;
+   head.prev = (void *)0;
+   head.next = &mid;
+   mid.prev = &head;
+   mid.next = &tail;
+   tail.prev = &mid;
+   tail.next = (void *)0;
+   foo (&tail);
+   if (mid.next != &tail)
+     link_error ();
+   if (tail.next != &tail)
+     abort ();
+   return 0;
+ }
+ 
+ /* We should have DSEd all stores to mid and head as they are not used.  */
+ 
+ /* { dg-final { scan-tree-dump-not "mid.prev =" "optimized" } } */
+ /* { dg-final { scan-tree-dump-not "mid.next =" "optimized" } } */
+ /* { dg-final { scan-tree-dump-not "head.prev =" "optimized" } } */
+ /* { dg-final { scan-tree-dump-not "head.next =" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */