Patchwork RFC: Add ADD_RESTRICT tree code

login
register
mail settings
Submitter Richard Guenther
Date Oct. 14, 2011, 10:13 a.m.
Message ID <CAFiYyc35zkBD7FJAYovuTWNYODDWMv_6Bp1mr9JmmmSPA304sg@mail.gmail.com>
Download mbox | patch
Permalink /patch/119760/
State New
Headers show

Comments

Richard Guenther - Oct. 14, 2011, 10:13 a.m.
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


> 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:
>

Patch

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);
 }