Re: RFC: Add ADD_RESTRICT tree code

[Richard Guenther <richard dot guenther at gmail dot com>]

On Wed, Oct 12, 2011 at 7:16 PM, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> this adds a mean to retain restrict information without relying on
> restrict casts. ?In the patch it's emitted by the gimplifier when it sees
> a norestrict->restrict cast (which from then on is useless), at which
> point also the tag of that restrict pointer is generated. ?That's later
> used by the aliasing machinery to associate it with a restrict tag uid.
>
> In particular it will be possible to associate pointers coming from
> different inline instance of the same function with the same restrict tag,
> and hence make them conflict.
>
> This patch will fix the currently XFAILed tree-ssa/restrict-4.c again, as
> well as fix PR 50419. ?It also still fixes the original testcase of
> PR 49279. ?But it will break the checked in testcase for this bug report.
> I believe the checked in testcase is invalid as follows:
>
> struct S { int a; int *__restrict p; };
>
> int
> foo (int *p, int *q)
> {
> ?struct S s, *t;
> ?s.a = 1;
> ?s.p = p; ? ? ? // 1
> ?t = wrap(&s); ?// 2 t=&s in effect, but GCC doesn't see this
> ?t->p = q; ? ? ?// 3
> ?s.p[0] = 0; ? ?// 4
> ?t->p[0] = 1; ? // 5
> ?return s.p[0]; // 6
> }
>
> Assignment 2 means that t->p points to s.p. ?Assignment 3 changes t->p and
> s.p, but the change to s.p doesn't occur through a pointer based on t->p
> or any other restrict pointer, in fact it doesn't occur through any
> explicit initialization or assignment, but rather through in indirect
> access via a different pointer. ?Hence the accesses to the same memory
> object at s.p[0] and t->p[0] were undefined because both accesses weren't
> through pointers based on each other.

Ick, that actually shows a bug in points-to handling (well, in
pt_solutions_same_restrict_base handling).  While we correctly
see that p escapes though wrap() and that t points to ESCAPED
we don't check in

bool
pt_solutions_same_restrict_base (struct pt_solution *pt1,
                                 struct pt_solution *pt2)
{
  /* If we deal with points-to solutions of two restrict qualified
     pointers solely rely on the pointed-to variable bitmap intersection.
     For two pointers that are based on each other the bitmaps will
     intersect.  */
  if (pt1->vars_contains_restrict
      && pt2->vars_contains_restrict)
    {
      gcc_assert (pt1->vars && pt2->vars);
      return bitmap_intersect_p (pt1->vars, pt2->vars);
    }

whether the solutions overlap in the ESCAPED bit (remember
ESCAPED contents are not expanded into the pointers pt->vars
bitmaps but just noted as the pt->escaped flag).  We ignore
pt->nonlocal as well, but that was by design ... so, re-try with

Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c      (revision 179962)
+++ tree-ssa-structalias.c      (working copy)
@@ -6079,12 +6079,15 @@ pt_solutions_intersect_1 (struct pt_solu
     return true;

   /* If either points to unknown global memory and the other points to
-     any global memory they alias.  */
-  if ((pt1->nonlocal
-       && (pt2->nonlocal
-          || pt2->vars_contains_global))
-      || (pt2->nonlocal
-         && pt1->vars_contains_global))
+     any global memory they alias.  If both points-to sets are based
+     off a restrict qualified pointer ignore any overlaps with NONLOCAL.  */
+  if (!(pt1->vars_contains_restrict
+       && pt2->vars_contains_restrict)
+      && ((pt1->nonlocal
+          && (pt2->nonlocal
+              || pt2->vars_contains_global))
+         || (pt2->nonlocal
+             && pt1->vars_contains_global)))
     return true;

   /* Check the escaped solution if required.  */
@@ -6148,18 +6151,7 @@ bool
 pt_solutions_same_restrict_base (struct pt_solution *pt1,
                                 struct pt_solution *pt2)
 {
-  /* If we deal with points-to solutions of two restrict qualified
-     pointers solely rely on the pointed-to variable bitmap intersection.
-     For two pointers that are based on each other the bitmaps will
-     intersect.  */
-  if (pt1->vars_contains_restrict
-      && pt2->vars_contains_restrict)
-    {
-      gcc_assert (pt1->vars && pt2->vars);
-      return bitmap_intersect_p (pt1->vars, pt2->vars);
-    }
-
-  return true;
+  return pt_solutions_intersect (pt1, pt2);
 }



> I expect some bike shedding about the name of the tree code, hence only
> RFC, no Changelog or anything. ?It's only ligthly tested in so far as it's
> currently in the target libs of a regstrap on x86_64-linux.
>
>
> Ciao,
> Michael.
>
> Index: tree-pretty-print.c
> ===================================================================
> *** tree-pretty-print.c (revision 179855)
> --- tree-pretty-print.c (working copy)
> *************** dump_generic_node (pretty_printer *buffe
> *** 1708,1713 ****
> --- 1708,1721 ----
> ? ? ? ?pp_character (buffer, '>');
> ? ? ? ?break;
>
> + ? ? case ADD_RESTRICT:
> + ? ? ? pp_string (buffer, "ADD_RESTRICT <");
> + ? ? ? dump_generic_node (buffer, TREE_OPERAND (node, 0), spc, flags, false);
> + ? ? ? pp_string (buffer, ", ");
> + ? ? ? dump_generic_node (buffer, TREE_OPERAND (node, 1), spc, flags, false);
> + ? ? ? pp_character (buffer, '>');
> + ? ? ? break;
> +
> ? ? ?case ABS_EXPR:
> ? ? ? ?pp_string (buffer, "ABS_EXPR <");
> ? ? ? ?dump_generic_node (buffer, TREE_OPERAND (node, 0), spc, flags, false);
> Index: expr.c
> ===================================================================
> *** expr.c ? ? ?(revision 179855)
> --- expr.c ? ? ?(working copy)
> *************** expand_expr_real_2 (sepops ops, rtx targ
> *** 7782,7787 ****
> --- 7782,7790 ----
>
> ? ?switch (code)
> ? ? ?{
> + ? ? case ADD_RESTRICT:
> + ? ? ? /* We can handle add_restrict like a conversion, treeop1 will be ignored.
> + ? ? ? ? ?FALLTHRU. ?*/
> ? ? ?case NON_LVALUE_EXPR:
> ? ? ?case PAREN_EXPR:
> ? ? ?CASE_CONVERT:
> Index: gimple-pretty-print.c
> ===================================================================
> *** gimple-pretty-print.c ? ? ? (revision 179855)
> --- gimple-pretty-print.c ? ? ? (working copy)
> *************** dump_binary_rhs (pretty_printer *buffer,
> *** 334,339 ****
> --- 334,340 ----
> ? ? ?case COMPLEX_EXPR:
> ? ? ?case MIN_EXPR:
> ? ? ?case MAX_EXPR:
> + ? ? case ADD_RESTRICT:
> ? ? ?case VEC_WIDEN_MULT_HI_EXPR:
> ? ? ?case VEC_WIDEN_MULT_LO_EXPR:
> ? ? ?case VEC_PACK_TRUNC_EXPR:
> Index: gimplify.c
> ===================================================================
> *** gimplify.c ?(revision 179855)
> --- gimplify.c ?(working copy)
> *************** gimplify_modify_expr (tree *expr_p, gimp
> *** 4525,4530 ****
> --- 4525,4537 ----
> ? ? ? ?STRIP_USELESS_TYPE_CONVERSION (*from_p);
> ? ? ? ?if (!useless_type_conversion_p (TREE_TYPE (*to_p), TREE_TYPE (*from_p)))
> ? ? ? ?*from_p = fold_convert_loc (loc, TREE_TYPE (*to_p), *from_p);
> + ? ? ? else if (POINTER_TYPE_P (TREE_TYPE (*from_p))
> + ? ? ? ? ? ? ?&& TYPE_RESTRICT (TREE_TYPE (*to_p))
> + ? ? ? ? ? ? ?&& !TYPE_RESTRICT (TREE_TYPE (*from_p)))
> + ? ? ? *from_p = fold_build2_loc (loc, ADD_RESTRICT, TREE_TYPE (*to_p),
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?*from_p,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?build_int_cst (integer_type_node,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? allocate_decl_uid ()));
> ? ? ?}
>
> ? ?/* See if any simplifications can be done based on what the RHS is. ?*/
> Index: tree.def
> ===================================================================
> *** tree.def ? ?(revision 179855)
> --- tree.def ? ?(working copy)
> *************** DEFTREECODE (WITH_SIZE_EXPR, "with_size_
> *** 961,966 ****
> --- 961,968 ----
> ? ? generated by the builtin targetm.vectorize.mask_for_load_builtin_decl. ?*/
> ?DEFTREECODE (REALIGN_LOAD_EXPR, "realign_load", tcc_expression, 3)
>
> + DEFTREECODE (ADD_RESTRICT, "add_restrict", tcc_binary, 2)
> +
> ?/* Low-level memory addressing. ?Operands are BASE (address of static or
> ? ? global variable or register), OFFSET (integer constant),
> ? ? INDEX (register), STEP (integer constant), INDEX2 (register),
> Index: tree-inline.c
> ===================================================================
> *** tree-inline.c ? ? ? (revision 179855)
> --- tree-inline.c ? ? ? (working copy)
> *************** estimate_operator_cost (enum tree_code c
> *** 3279,3284 ****
> --- 3279,3285 ----
> ? ? ?case COMPLEX_EXPR:
> ? ? ?case PAREN_EXPR:
> ? ? ?case VIEW_CONVERT_EXPR:
> + ? ? case ADD_RESTRICT:
> ? ? ? ?return 0;
>
> ? ? ?/* Assign cost of 1 to usual operations.
> Index: tree-ssa-structalias.c
> ===================================================================
> *** tree-ssa-structalias.c ? ? ?(revision 179855)
> --- tree-ssa-structalias.c ? ? ?(working copy)
> *************** make_transitive_closure_constraints (var
> *** 3602,3632 ****
> ?/* Temporary storage for fake var decls. ?*/
> ?struct obstack fake_var_decl_obstack;
>
> ! /* Build a fake VAR_DECL acting as referrer to a DECL_UID. ?*/
>
> ?static tree
> ! build_fake_var_decl (tree type)
> ?{
> ? ?tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
> ? ?memset (decl, 0, sizeof (struct tree_var_decl));
> ? ?TREE_SET_CODE (decl, VAR_DECL);
> ? ?TREE_TYPE (decl) = type;
> ! ? DECL_UID (decl) = allocate_decl_uid ();
> ? ?SET_DECL_PT_UID (decl, -1);
> ? ?layout_decl (decl, 0);
> ? ?return decl;
> ?}
>
> ! /* Create a new artificial heap variable with NAME.
> ! ? ?Return the created variable. ?*/
>
> ?static varinfo_t
> ! make_heapvar (const char *name)
> ?{
> ? ?varinfo_t vi;
> ? ?tree heapvar;
>
> ! ? heapvar = build_fake_var_decl (ptr_type_node);
> ? ?DECL_EXTERNAL (heapvar) = 1;
>
> ? ?vi = new_var_info (heapvar, name);
> --- 3602,3644 ----
> ?/* Temporary storage for fake var decls. ?*/
> ?struct obstack fake_var_decl_obstack;
>
> ! /* Build a fake VAR_DECL with DECL_UID being UID (which probably has
> ! ? ?to be ultimately allocated by allocate_decl_uid()). ?*/
>
> ?static tree
> ! build_fake_var_decl_uid (tree type, int uid)
> ?{
> ? ?tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl);
> ? ?memset (decl, 0, sizeof (struct tree_var_decl));
> ? ?TREE_SET_CODE (decl, VAR_DECL);
> ? ?TREE_TYPE (decl) = type;
> ! ? DECL_UID (decl) = uid;
> ? ?SET_DECL_PT_UID (decl, -1);
> ? ?layout_decl (decl, 0);
> ? ?return decl;
> ?}
>
> ! /* Build a fake VAR_DECL acting as referrer to a DECL_UID. ?*/
> !
> ! static tree
> ! build_fake_var_decl (tree type)
> ! {
> ! ? return build_fake_var_decl_uid (type, allocate_decl_uid ());
> ! }
> !
> ! /* Create a new artificial heap variable with NAME and UID.
> ! ? ?If UID is -1 allocate a new one. ?Return the created variable. ?*/
>
> ?static varinfo_t
> ! make_heapvar (const char *name, int uid)
> ?{
> ? ?varinfo_t vi;
> ? ?tree heapvar;
>
> ! ? if (uid == -1)
> ! ? ? heapvar = build_fake_var_decl (ptr_type_node);
> ! ? else
> ! ? ? heapvar = build_fake_var_decl_uid (ptr_type_node, uid);
> ? ?DECL_EXTERNAL (heapvar) = 1;
>
> ? ?vi = new_var_info (heapvar, name);
> *************** make_heapvar (const char *name)
> *** 3642,3657 ****
> ? ?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 (name);
> ? ?make_constraint_from (lhs, vi->id);
> !
> ! ? return vi;
> ?}
>
> ?/* Create a new artificial heap variable with NAME and make a
> --- 3654,3673 ----
> ? ?return vi;
> ?}
>
> ! /* Create a new artificial heap variable with NAME and UID and make a
> ! ? ?constraint from it to LHS. ?Set flags according to a tag used
> ! ? ?for tracking restrict pointers. ?*/
>
> ! static void
> ! make_constraint_from_restrict_uid (varinfo_t lhs, const char *name, int uid)
> ?{
> ! ? varinfo_t vi;
> ! ? vi = make_heapvar (name, uid);
> ? ?make_constraint_from (lhs, vi->id);
> ! ? vi->is_restrict_var = 1;
> ! ? vi->is_global_var = 0;
> ! ? vi->is_special_var = 1;
> ! ? vi->may_have_pointers = 0;
> ?}
>
> ?/* Create a new artificial heap variable with NAME and make a
> *************** make_constraint_from_heapvar (varinfo_t
> *** 3661,3672 ****
> ?static void
> ?make_constraint_from_restrict (varinfo_t lhs, const char *name)
> ?{
> ! ? varinfo_t vi;
> ! ? vi = make_constraint_from_heapvar (lhs, name);
> ! ? vi->is_restrict_var = 1;
> ! ? vi->is_global_var = 0;
> ! ? vi->is_special_var = 1;
> ! ? vi->may_have_pointers = 0;
> ?}
>
> ?/* In IPA mode there are varinfos for different aspects of reach
> --- 3677,3683 ----
> ?static void
> ?make_constraint_from_restrict (varinfo_t lhs, const char *name)
> ?{
> ! ? make_constraint_from_restrict_uid (lhs, name, -1);
> ?}
>
> ?/* In IPA mode there are varinfos for different aspects of reach
> *************** handle_lhs_call (gimple stmt, tree lhs,
> *** 3846,3852 ****
> ? ? ? ?varinfo_t vi;
> ? ? ? ?struct constraint_expr tmpc;
> ? ? ? ?rhsc = NULL;
> ! ? ? ? vi = make_heapvar ("HEAP");
> ? ? ? ?/* We delay marking allocated storage global until we know if
> ? ? ? ? ? it escapes. ?*/
> ? ? ? ?DECL_EXTERNAL (vi->decl) = 0;
> --- 3857,3863 ----
> ? ? ? ?varinfo_t vi;
> ? ? ? ?struct constraint_expr tmpc;
> ? ? ? ?rhsc = NULL;
> ! ? ? ? vi = make_heapvar ("HEAP", -1);
> ? ? ? ?/* We delay marking allocated storage global until we know if
> ? ? ? ? ? it escapes. ?*/
> ? ? ? ?DECL_EXTERNAL (vi->decl) = 0;
> *************** find_func_aliases (gimple origt)
> *** 4494,4499 ****
> --- 4505,4515 ----
> ? ? ? ? ?&& (!in_ipa_mode
> ? ? ? ? ? ? ?|| DECL_EXTERNAL (lhsop) || TREE_PUBLIC (lhsop)))
> ? ? ? ?make_escape_constraint (rhsop);
> + ? ? ? /* Add the specified restrict tag. ?*/
> + ? ? ? else if (gimple_assign_rhs_code (t) == ADD_RESTRICT)
> + ? ? ? make_constraint_from_restrict_uid (get_vi_for_tree (lhsop),
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?"RESTRICT_TAG",
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?TREE_INT_CST_LOW (gimple_assign_rhs2 (t)));
> ? ? ?}
> ? ?/* Handle escapes through return. ?*/
> ? ?else if (gimple_code (t) == GIMPLE_RETURN
> Index: tree-cfg.c
> ===================================================================
> *** tree-cfg.c ?(revision 179855)
> --- tree-cfg.c ?(working copy)
> *************** do_pointer_plus_expr_check:
> *** 3567,3572 ****
> --- 3567,3587 ----
> ? ? ? ?return false;
> ? ? ? ?}
>
> + ? ? case ADD_RESTRICT:
> + ? ? ? {
> + ? ? ? if (!POINTER_TYPE_P (rhs1_type)
> + ? ? ? ? ? || !useless_type_conversion_p (lhs_type, rhs1_type)
> + ? ? ? ? ? || !useless_type_conversion_p (integer_type_node, rhs2_type))
> + ? ? ? ? {
> + ? ? ? ? ? error ("Invalid use of add_restrict");
> + ? ? ? ? ? debug_generic_stmt (lhs_type);
> + ? ? ? ? ? debug_generic_stmt (rhs1_type);
> + ? ? ? ? ? debug_generic_stmt (rhs2_type);
> + ? ? ? ? ? return true;
> + ? ? ? ? }
> + ? ? ? return false;
> + ? ? ? }
> +
> ? ? ?case TRUTH_ANDIF_EXPR:
> ? ? ?case TRUTH_ORIF_EXPR:
> ? ? ?case TRUTH_AND_EXPR:
>