Patchwork Overhaul middle-end handling of restrict

login
register
mail settings
Submitter Michael Matz
Date Nov. 21, 2013, 6:03 p.m.
Message ID <alpine.LNX.2.00.1311211832370.11100@wotan.suse.de>
Download mbox | patch
Permalink /patch/293210/
State New
Headers show

Comments

Michael Matz - Nov. 21, 2013, 6:03 p.m.
Hello,

after much pondering about the issue we came up with this design to 
handle restrict more generally.  Without a completely different way of 
representing conflicts (or non-conflicts) of memory references we're bound 
to somehow encode the necessary information into the points-to set (or in 
any case information related to pointer ssa names).  This in turn means 
that the location sensitive nature of restrict needs to be made explicit 
in the IL, i.e. we basically need some starting point when a pointer 
becomes restrict (ADD_RESTRICT), and also an ending point (DEL_RESTRICT), 
which must act as barrier for other memory accesses (if it wouldn't some 
transformations could move references from outside restrict regions into 
the restrict region making them disasmbiguable with the restrict 
references, introducing a bug).

We also need to use our points-to solver to propagate restrict tags 
conservatively, postprocessing the information to remove too conservative 
estimates afterwards per SSA name.

And if we want to use restrict based disambiguation we also need to 
transfer the barriers into RTL barriers (I'm using an asm with an explicit 
MEM to refer to the pointer in question, so not all memory is clobbered).
There's some potential for improvement here by removing useless 
ADD_RESTRICT / DEL_RESTRICT pairs.

There's another improvement when enlargening the set of SSA names to be 
considered for postprocessin.  Right now only the result of ADD_RESTRICT 
assigns are handled, that can be improved to also process SSA names that 
trivial depend on such (i.e. are offsetted and themself restrict typed).

That facility is used to implement restrict parameters to functions, 
replacing the current ad-hoc way in the points-to solver.  Other uses 
should be done under control of the frontends, as only those know the 
semantics for real.

I have a patch that more aggressively creates ADD_RESTRICT/DEL_RESTRICT 
pairs (basically whenever there's an assignment from non-restrict pointers 
to a restrict pointer, on the grounds that this "invents" a new restrict 
set), but that breaks C programs that we don't want to break (I consider 
them invalid, but there's disagreement).

Some older incarnations of this were bootstrapped, but this specific patch 
is only now in regstrapping on x86_64-linux.  Okay for trunk if that 
passes?


Ciao,
Michael.
---------------------------
	* tree.def (ADD_RESTRICT): New tree code.
	* cfgexpand.c (expand_debug_expr): Handle it.
	* expr.c (expand_pointer_clobber): New function.
	(expand_expr_real_2): Use it to handle ADD_RESTRICT.
	* expr.h (expand_pointer_clobber): Declare.
	* function.c (gimplify_parameters): Return a second gimple_seq,
	handle restrict parameters.
	* function.h (gimplify_parameters): Adjust.
	* gimple-pretty-print.c (dump_binary_rhs): Handle ADD_RESTRICT.
	* gimplify.c (gimplify_body): Append second gimple_seq,
	adjust call to gimplify_parameters.
	* internal-fn.def (DEL_RESTRICT): New internal function code.
	* internal-fn.c (expand_DEL_RESTRICT): New function.
	* tree-cfg.c (verify_gimple_assign_binary): Check ADD_RESTRICT.
	* tree-inline.c (estimate_operator_cost): Handle ADD_RESTRICT.
	* tree-pretty-print.c (dump_generic_node): Ditto.
	* tree-ssa-dce.c (propagate_necessity): DEL_RESTRICT calls
	are only clobbers.
	* tree-ssa-structalias.c (build_fake_var_decl_uid): New static
	function.
	(build_fake_var_decl): Rewrite in terms of above.
	(make_heapvar): Take uid parameter.
	(make_constraint_from_restrict_uid): New.
	(make_constraint_from_restrict): Use above.
	(make_constraint_from_global_restrict): Explicitely set global flag.
	(handle_lhs_call): Adjust call to make_heapvar.
	(find_func_aliases_for_internal_call): New.
	(find_func_aliases_for_call): Use it.
	(find_func_aliases): Handle ADD_RESTRICT.
	(intra_create_variable_infos): Remove any explicit handling
	of restrict parameters.
	(set_uids_in_ptset): Update instead of overwrite 
	vars_contains_escaped_heap flag.
	(find_what_var_points_to_1): Renamed from ...
	(find_what_var_points_to): ... this, which is now wrapper
	postprocessing points-to flags.
	(compute_points_to_sets): Ignore DEL_RESTRICT calls.
Xinliang David Li - Nov. 22, 2013, 1:14 a.m.
On Thu, Nov 21, 2013 at 10:03 AM, Michael Matz <matz@suse.de> wrote:
> Hello,
>
> after much pondering about the issue we came up with this design to
> handle restrict more generally.  Without a completely different way of
> representing conflicts (or non-conflicts) of memory references we're bound
> to somehow encode the necessary information into the points-to set (or in
> any case information related to pointer ssa names).  This in turn means
> that the location sensitive nature of restrict needs to be made explicit
> in the IL, i.e. we basically need some starting point when a pointer
> becomes restrict (ADD_RESTRICT), and also an ending point (DEL_RESTRICT),
> which must act as barrier for other memory accesses (if it wouldn't some
> transformations could move references from outside restrict regions into
> the restrict region making them disasmbiguable with the restrict
> references, introducing a bug).
>

Can you use block/scope information to address this ? References from
enclosing scopes can be considered possible aliases.

David

> We also need to use our points-to solver to propagate restrict tags
> conservatively, postprocessing the information to remove too conservative
> estimates afterwards per SSA name.
>
> And if we want to use restrict based disambiguation we also need to
> transfer the barriers into RTL barriers (I'm using an asm with an explicit
> MEM to refer to the pointer in question, so not all memory is clobbered).
> There's some potential for improvement here by removing useless
> ADD_RESTRICT / DEL_RESTRICT pairs.
>
> There's another improvement when enlargening the set of SSA names to be
> considered for postprocessin.  Right now only the result of ADD_RESTRICT
> assigns are handled, that can be improved to also process SSA names that
> trivial depend on such (i.e. are offsetted and themself restrict typed).
>
> That facility is used to implement restrict parameters to functions,
> replacing the current ad-hoc way in the points-to solver.  Other uses
> should be done under control of the frontends, as only those know the
> semantics for real.
>
> I have a patch that more aggressively creates ADD_RESTRICT/DEL_RESTRICT
> pairs (basically whenever there's an assignment from non-restrict pointers
> to a restrict pointer, on the grounds that this "invents" a new restrict
> set), but that breaks C programs that we don't want to break (I consider
> them invalid, but there's disagreement).
>
> Some older incarnations of this were bootstrapped, but this specific patch
> is only now in regstrapping on x86_64-linux.  Okay for trunk if that
> passes?




>
>
> Ciao,
> Michael.
> ---------------------------
>         * tree.def (ADD_RESTRICT): New tree code.
>         * cfgexpand.c (expand_debug_expr): Handle it.
>         * expr.c (expand_pointer_clobber): New function.
>         (expand_expr_real_2): Use it to handle ADD_RESTRICT.
>         * expr.h (expand_pointer_clobber): Declare.
>         * function.c (gimplify_parameters): Return a second gimple_seq,
>         handle restrict parameters.
>         * function.h (gimplify_parameters): Adjust.
>         * gimple-pretty-print.c (dump_binary_rhs): Handle ADD_RESTRICT.
>         * gimplify.c (gimplify_body): Append second gimple_seq,
>         adjust call to gimplify_parameters.
>         * internal-fn.def (DEL_RESTRICT): New internal function code.
>         * internal-fn.c (expand_DEL_RESTRICT): New function.
>         * tree-cfg.c (verify_gimple_assign_binary): Check ADD_RESTRICT.
>         * tree-inline.c (estimate_operator_cost): Handle ADD_RESTRICT.
>         * tree-pretty-print.c (dump_generic_node): Ditto.
>         * tree-ssa-dce.c (propagate_necessity): DEL_RESTRICT calls
>         are only clobbers.
>         * tree-ssa-structalias.c (build_fake_var_decl_uid): New static
>         function.
>         (build_fake_var_decl): Rewrite in terms of above.
>         (make_heapvar): Take uid parameter.
>         (make_constraint_from_restrict_uid): New.
>         (make_constraint_from_restrict): Use above.
>         (make_constraint_from_global_restrict): Explicitely set global flag.
>         (handle_lhs_call): Adjust call to make_heapvar.
>         (find_func_aliases_for_internal_call): New.
>         (find_func_aliases_for_call): Use it.
>         (find_func_aliases): Handle ADD_RESTRICT.
>         (intra_create_variable_infos): Remove any explicit handling
>         of restrict parameters.
>         (set_uids_in_ptset): Update instead of overwrite
>         vars_contains_escaped_heap flag.
>         (find_what_var_points_to_1): Renamed from ...
>         (find_what_var_points_to): ... this, which is now wrapper
>         postprocessing points-to flags.
>         (compute_points_to_sets): Ignore DEL_RESTRICT calls.
>
> Index: cfgexpand.c
> ===================================================================
> --- cfgexpand.c (revision 205123)
> +++ cfgexpand.c (working copy)
> @@ -3785,6 +3785,7 @@ expand_debug_expr (tree exp)
>        /* Fall through.  */
>
>      adjust_mode:
> +    case ADD_RESTRICT:
>      case PAREN_EXPR:
>      case NOP_EXPR:
>      case CONVERT_EXPR:
> Index: expr.c
> ===================================================================
> --- expr.c      (revision 205123)
> +++ expr.c      (working copy)
> @@ -7988,6 +7988,41 @@ expand_cond_expr_using_cmove (tree treeo
>    return NULL_RTX;
>  }
>
> +/* Given a memory pointer PTR, expand an RTL asm statement
> +   that merely clobbers memory reachable from that pointer
> +   via arbitrary offsets.  */
> +
> +void
> +expand_pointer_clobber (tree ptr, location_t loc)
> +{
> +  tree ref = build_simple_mem_ref (ptr);
> +  rtx op = expand_expr (ref, NULL_RTX, BLKmode, EXPAND_MEMORY);
> +  rtx body;
> +
> +  op = validize_mem (op);
> +
> +  /* There's no way to construct a tree expression doing exactly what
> +     we need (representing a reference to arbitrarily memory reachable
> +     from a given pointer, i.e. with arbitrary offsets.  Hence
> +     construct that by massaging the MEM attributes.  */
> +  clear_mem_offset (op);
> +  clear_mem_size (op);
> +  PUT_MODE (op, BLKmode);
> +
> +  rtvec argvec = rtvec_alloc (0);
> +  rtvec constraintvec = rtvec_alloc (0);
> +  rtvec labelvec = rtvec_alloc (0);
> +
> +  body = gen_rtx_ASM_OPERANDS (BLKmode,
> +                              ggc_strdup (""),
> +                              ggc_strdup ("=m"), 0, argvec, constraintvec,
> +                              labelvec, loc);
> +
> +  MEM_VOLATILE_P (body) = 1;
> +
> +  emit_insn (gen_rtx_SET (VOIDmode, op, body));
> +}
> +
>  rtx
>  expand_expr_real_2 (sepops ops, rtx target, enum machine_mode tmode,
>                     enum expand_modifier modifier)
> @@ -8047,6 +8082,13 @@ expand_expr_real_2 (sepops ops, rtx targ
>
>    switch (code)
>      {
> +    case ADD_RESTRICT:
> +      /* We can handle add_restrict like a conversion, treeop1 will be
> +         ignored.  But do create a barrier to contain the restrict
> +        section.  */
> +      expand_pointer_clobber (treeop0, loc);
> +
> +      /* FALLTHRU.  */
>      case NON_LVALUE_EXPR:
>      case PAREN_EXPR:
>      CASE_CONVERT:
> Index: expr.h
> ===================================================================
> --- expr.h      (revision 205123)
> +++ expr.h      (working copy)
> @@ -719,6 +719,8 @@ extern rtx extract_low_bits (enum machin
>  extern rtx expand_mult (enum machine_mode, rtx, rtx, rtx, int);
>  extern rtx expand_mult_highpart_adjust (enum machine_mode, rtx, rtx, rtx, rtx, int);
>
> +extern void expand_pointer_clobber (tree, location_t);
> +
>  extern rtx assemble_static_space (unsigned HOST_WIDE_INT);
>  extern int safe_from_p (const_rtx, tree, int);
>  extern bool split_comparison (enum rtx_code, enum machine_mode,
> Index: function.c
> ===================================================================
> --- function.c  (revision 205123)
> +++ function.c  (working copy)
> @@ -3595,10 +3595,11 @@ gimplify_parm_type (tree *tp, int *walk_
>  /* Gimplify the parameter list for current_function_decl.  This involves
>     evaluating SAVE_EXPRs of variable sized parameters and generating code
>     to implement callee-copies reference parameters.  Returns a sequence of
> -   statements to add to the beginning of the function.  */
> +   statements to add to the beginning of the function and another
> +   sequence to add to the end of the function (via *STMT_AFTER).  */
>
>  gimple_seq
> -gimplify_parameters (void)
> +gimplify_parameters (gimple_seq *stmts_after)
>  {
>    struct assign_parm_data_all all;
>    tree parm;
> @@ -3606,6 +3607,7 @@ gimplify_parameters (void)
>    vec<tree> fnargs;
>    unsigned i;
>
> +  *stmts_after = NULL;
>    assign_parms_initialize_all (&all);
>    fnargs = assign_parms_augmented_arg_list (&all);
>
> @@ -3690,6 +3692,17 @@ gimplify_parameters (void)
>               DECL_HAS_VALUE_EXPR_P (parm) = 1;
>             }
>         }
> +      if (POINTER_TYPE_P (TREE_TYPE (parm))
> +         && TYPE_RESTRICT (TREE_TYPE (parm))
> +         && !DECL_HAS_VALUE_EXPR_P (parm))
> +       {
> +         tree t = fold_build2 (ADD_RESTRICT, TREE_TYPE (parm), parm,
> +                               build_int_cst (integer_type_node,
> +                                              allocate_decl_uid ()));
> +         gimplify_assign (parm, t, &stmts);
> +         gimple g = gimple_build_call_internal (IFN_DEL_RESTRICT, 1, parm);
> +         gimple_seq_add_stmt (stmts_after, g);
> +       }
>      }
>
>    fnargs.release ();
> Index: function.h
> ===================================================================
> --- function.h  (revision 205123)
> +++ function.h  (working copy)
> @@ -841,6 +841,6 @@ extern void preserve_temp_slots (rtx);
>  extern int aggregate_value_p (const_tree, const_tree);
>  extern void push_function_context (void);
>  extern void pop_function_context (void);
> -extern gimple_seq gimplify_parameters (void);
> +extern gimple_seq gimplify_parameters (gimple_seq *);
>
>  #endif  /* GCC_FUNCTION_H */
> Index: gimple-pretty-print.c
> ===================================================================
> --- gimple-pretty-print.c       (revision 205123)
> +++ gimple-pretty-print.c       (working copy)
> @@ -348,6 +348,7 @@ dump_binary_rhs (pretty_printer *buffer,
>      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_WIDEN_MULT_EVEN_EXPR:
> Index: gimplify.c
> ===================================================================
> --- gimplify.c  (revision 205123)
> +++ gimplify.c  (working copy)
> @@ -1005,8 +1005,9 @@ gimplify_bind_expr (tree *expr_p, gimple
>           && !DECL_HARD_REGISTER (t)
>           && !TREE_THIS_VOLATILE (t)
>           && !DECL_HAS_VALUE_EXPR_P (t)
> -         /* Only care for variables that have to be in memory.  Others
> -            will be rewritten into SSA names, hence moved to the top-level.  */
> +         /* Only care for variables that have to be in memory.
> +            Others will be rewritten into SSA names, hence moved
> +            to the top-level.  */
>           && !is_gimple_reg (t)
>           && flag_stack_reuse != SR_NONE)
>         {
> @@ -8356,7 +8357,7 @@ gimple
>  gimplify_body (tree fndecl, bool do_parms)
>  {
>    location_t saved_location = input_location;
> -  gimple_seq parm_stmts, seq;
> +  gimple_seq parm_stmts, parm_stmts_after, seq;
>    gimple outer_bind;
>    struct gimplify_ctx gctx;
>    struct cgraph_node *cgn;
> @@ -8393,7 +8394,8 @@ gimplify_body (tree fndecl, bool do_parm
>
>    /* Resolve callee-copies.  This has to be done before processing
>       the body so that DECL_VALUE_EXPR gets processed correctly.  */
> -  parm_stmts = do_parms ? gimplify_parameters () : NULL;
> +  parm_stmts_after = NULL;
> +  parm_stmts = do_parms ? gimplify_parameters (&parm_stmts_after) : NULL;
>
>    /* Gimplify the function's body.  */
>    seq = NULL;
> @@ -8432,6 +8434,10 @@ gimplify_body (tree fndecl, bool do_parm
>             DECL_IGNORED_P (parm) = 0;
>           }
>      }
> +  /* Same for statements that need to come after the body.  */
> +  if (!gimple_seq_empty_p (parm_stmts_after))
> +    gimplify_seq_add_seq (gimple_bind_body_ptr (outer_bind),
> +                         parm_stmts_after);
>
>    if (nonlocal_vlas)
>      {
> Index: internal-fn.c
> ===================================================================
> --- internal-fn.c       (revision 205123)
> +++ internal-fn.c       (working copy)
> @@ -148,6 +148,16 @@ expand_UBSAN_NULL (gimple stmt ATTRIBUTE
>    gcc_unreachable ();
>  }
>
> +/* Expand the DEL_RESTRICT internal function into a RTL
> +   asm that merely clobbers memory reachable via the pointer.  */
> +
> +static void
> +expand_DEL_RESTRICT (gimple stmt)
> +{
> +  tree ptr = gimple_call_arg (stmt, 0);
> +  expand_pointer_clobber (ptr, gimple_location (stmt));
> +}
> +
>  /* Routines to expand each internal function, indexed by function number.
>     Each routine has the prototype:
>
> Index: internal-fn.def
> ===================================================================
> --- internal-fn.def     (revision 205123)
> +++ internal-fn.def     (working copy)
> @@ -45,3 +45,4 @@ DEF_INTERNAL_FN (GOMP_SIMD_VF, ECF_CONST
>  DEF_INTERNAL_FN (GOMP_SIMD_LAST_LANE, ECF_CONST | ECF_LEAF | ECF_NOTHROW)
>  DEF_INTERNAL_FN (ANNOTATE,  ECF_CONST | ECF_LEAF | ECF_NOTHROW)
>  DEF_INTERNAL_FN (UBSAN_NULL, ECF_LEAF | ECF_NOTHROW)
> +DEF_INTERNAL_FN (DEL_RESTRICT,  /*ECF_LEAF |*/ ECF_NOTHROW)
> Index: tree-cfg.c
> ===================================================================
> --- tree-cfg.c  (revision 205123)
> +++ tree-cfg.c  (working copy)
> @@ -3627,6 +3627,21 @@ verify_gimple_assign_binary (gimple stmt
>         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:
> Index: tree-inline.c
> ===================================================================
> --- tree-inline.c       (revision 205123)
> +++ tree-inline.c       (working copy)
> @@ -3580,6 +3580,7 @@ estimate_operator_cost (enum tree_code c
>      case COMPLEX_EXPR:
>      case PAREN_EXPR:
>      case VIEW_CONVERT_EXPR:
> +    case ADD_RESTRICT:
>        return 0;
>
>      /* Assign cost of 1 to usual operations.
> Index: tree-pretty-print.c
> ===================================================================
> --- tree-pretty-print.c (revision 205123)
> +++ tree-pretty-print.c (working copy)
> @@ -1927,6 +1927,14 @@ dump_generic_node (pretty_printer *buffe
>        pp_greater (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: tree-ssa-dce.c
> ===================================================================
> --- tree-ssa-dce.c      (revision 205123)
> +++ tree-ssa-dce.c      (working copy)
> @@ -828,6 +828,10 @@ propagate_necessity (bool aggressive)
>                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
>                 continue;
>
> +             if (gimple_call_internal_p (stmt)
> +                 && gimple_call_internal_fn (stmt) == IFN_DEL_RESTRICT)
> +               continue;
> +
>               /* Calls implicitly load from memory, their arguments
>                  in addition may explicitly perform memory loads.  */
>               mark_all_reaching_defs_necessary (stmt);
> Index: tree-ssa-structalias.c
> ===================================================================
> --- tree-ssa-structalias.c      (revision 205123)
> +++ tree-ssa-structalias.c      (working copy)
> @@ -3741,31 +3741,43 @@ make_transitive_closure_constraints (var
>  /* Temporary storage for fake var decls.  */
>  struct obstack fake_var_decl_obstack;
>
> -/* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
> +/* 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 (tree type)
> +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) = allocate_decl_uid ();
> +  DECL_UID (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.  */
> +/* 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)
> +make_heapvar (const char *name, int uid)
>  {
>    varinfo_t vi;
>    tree heapvar;
>
> -  heapvar = build_fake_var_decl (ptr_type_node);
> +  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);
> @@ -3781,22 +3793,34 @@ make_heapvar (const char *name)
>    return vi;
>  }
>
> -/* Create a new artificial heap variable with NAME and make a
> +/* 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 varinfo_t
> -make_constraint_from_restrict (varinfo_t lhs, const char *name)
> +make_constraint_from_restrict_uid (varinfo_t lhs, const char *name, int uid)
>  {
> -  varinfo_t vi = make_heapvar (name);
> -  vi->is_global_var = 1;
> -  vi->may_have_pointers = 1;
> +  varinfo_t vi;
> +  vi = make_heapvar (name, uid);
>    make_constraint_from (lhs, vi->id);
> +  vi->is_global_var = 0;
> +  /*vi->is_special_var = 1;*/
> +  vi->may_have_pointers = 1;
>    return vi;
>  }
>
>  /* Create a new artificial heap variable with NAME and make a
>     constraint from it to LHS.  Set flags according to a tag used
> +   for tracking restrict pointers.  */
> +
> +static varinfo_t
> +make_constraint_from_restrict (varinfo_t lhs, const char *name)
> +{
> +  return make_constraint_from_restrict_uid (lhs, name, -1);
> +}
> +
> +/* Create a new artificial heap variable with NAME and make a
> +   constraint from it to LHS.  Set flags according to a tag used
>     for tracking restrict pointers and make the artificial heap
>     point to global memory.  */
>
> @@ -3804,6 +3828,7 @@ static varinfo_t
>  make_constraint_from_global_restrict (varinfo_t lhs, const char *name)
>  {
>    varinfo_t vi = make_constraint_from_restrict (lhs, name);
> +  vi->is_global_var = 1;
>    make_copy_constraint (vi, nonlocal_id);
>    return vi;
>  }
> @@ -3999,7 +4024,7 @@ handle_lhs_call (gimple stmt, tree lhs,
>        varinfo_t vi;
>        struct constraint_expr tmpc;
>        rhsc.create (0);
> -      vi = make_heapvar ("HEAP");
> +      vi = make_heapvar ("HEAP", -1);
>        /* We marking allocated storage local, we deal with it becoming
>           global by escaping and setting of vars_contains_escaped_heap.  */
>        DECL_EXTERNAL (vi->decl) = 0;
> @@ -4490,6 +4515,28 @@ find_func_aliases_for_builtin_call (gimp
>    return false;
>  }
>
> +/* Create constraints for the internal call T.  Return true if the call
> +   was handled, otherwise false.  */
> +
> +static bool
> +find_func_aliases_for_internal_call (gimple t)
> +{
> +  switch (gimple_call_internal_fn (t))
> +    {
> +    case IFN_DEL_RESTRICT:
> +      {
> +       /* DEL_RESTRICT is a barrier for what its argument points to.  */
> +       tree ptr = gimple_call_arg (t, 0);
> +       make_constraint_to (get_call_clobber_vi (t)->id, ptr);
> +       return true;
> +      }
> +
> +    default:
> +      /* Fallthru to general call handling.  */;
> +    }
> +  return false;
> +}
> +
>  /* Create constraints for the call T.  */
>
>  static void
> @@ -4505,6 +4552,10 @@ find_func_aliases_for_call (gimple t)
>        && find_func_aliases_for_builtin_call (t))
>      return;
>
> +  if (gimple_call_internal_p (t)
> +      && find_func_aliases_for_internal_call (t))
> +    return;
> +
>    fi = get_fi_for_callee (t);
>    if (!in_ipa_mode
>        || (fndecl && !fi->is_fn_info))
> @@ -4715,6 +4766,16 @@ find_func_aliases (gimple origt)
>             /* Truth value results are not pointer (parts).  Or at least
>                very very unreasonable obfuscation of a part.  */
>             ;
> +         else if (gimple_assign_rhs_code (t) == ADD_RESTRICT)
> +           {
> +             /* Add the specified restrict tag and merge from
> +                the incoming pointer.  */
> +             make_constraint_from_restrict_uid (get_vi_for_tree (lhsop),
> +                                                "RESTRICT_TAG",
> +                                                TREE_INT_CST_LOW
> +                                                  (gimple_assign_rhs2 (t)));
> +             get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
> +           }
>           else
>             {
>               /* All other operations are merges.  */
> @@ -5852,50 +5913,10 @@ intra_create_variable_infos (void)
>      {
>        varinfo_t p = get_vi_for_tree (t);
>
> -      /* For restrict qualified pointers to objects passed by
> -         reference build a real representative for the pointed-to object.
> -        Treat restrict qualified references the same.  */
> -      if (TYPE_RESTRICT (TREE_TYPE (t))
> -         && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
> -             || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
> -         && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
> -       {
> -         struct constraint_expr lhsc, rhsc;
> -         varinfo_t vi;
> -         tree heapvar = build_fake_var_decl (TREE_TYPE (TREE_TYPE (t)));
> -         DECL_EXTERNAL (heapvar) = 1;
> -         vi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS");
> -         insert_vi_for_tree (heapvar, vi);
> -         lhsc.var = p->id;
> -         lhsc.type = SCALAR;
> -         lhsc.offset = 0;
> -         rhsc.var = vi->id;
> -         rhsc.type = ADDRESSOF;
> -         rhsc.offset = 0;
> -         process_constraint (new_constraint (lhsc, rhsc));
> -         for (; vi; vi = vi_next (vi))
> -           if (vi->may_have_pointers)
> -             {
> -               if (vi->only_restrict_pointers)
> -                 make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
> -               else
> -                 make_copy_constraint (vi, nonlocal_id);
> -             }
> -         continue;
> -       }
> -
> -      if (POINTER_TYPE_P (TREE_TYPE (t))
> -         && TYPE_RESTRICT (TREE_TYPE (t)))
> -       make_constraint_from_global_restrict (p, "PARM_RESTRICT");
> -      else
> +      for (; p; p = vi_next (p))
>         {
> -         for (; p; p = vi_next (p))
> -           {
> -             if (p->only_restrict_pointers)
> -               make_constraint_from_global_restrict (p, "PARM_RESTRICT");
> -             else if (p->may_have_pointers)
> -               make_constraint_from (p, nonlocal_id);
> -           }
> +         if (p->may_have_pointers)
> +           make_constraint_from (p, nonlocal_id);
>         }
>      }
>
> @@ -6022,7 +6043,7 @@ set_uids_in_ptset (bitmap into, bitmap f
>               && bitmap_bit_p (escaped_vi->solution, i)))
>         {
>           pt->vars_contains_escaped = true;
> -         pt->vars_contains_escaped_heap = vi->is_heap_var;
> +         pt->vars_contains_escaped_heap |= vi->is_heap_var;
>         }
>
>        if (TREE_CODE (vi->decl) == VAR_DECL
> @@ -6045,10 +6066,10 @@ set_uids_in_ptset (bitmap into, bitmap f
>  }
>
>
> -/* Compute the points-to solution *PT for the variable VI.  */
> +/* Compute the points-to solution *PT for the variable VI, part one.  */
>
>  static struct pt_solution
> -find_what_var_points_to (varinfo_t orig_vi)
> +find_what_var_points_to_1 (varinfo_t orig_vi)
>  {
>    unsigned int i;
>    bitmap_iterator bi;
> @@ -6096,7 +6117,7 @@ find_what_var_points_to (varinfo_t orig_
>             /* Nobody cares.  */
>             ;
>           else if (vi->id == anything_id
> -                  || vi->id == integer_id)
> +                   || vi->id == integer_id)
>             pt->anything = 1;
>         }
>      }
> @@ -6126,6 +6147,71 @@ find_what_var_points_to (varinfo_t orig_
>    return *pt;
>  }
>
> +/* Compute the points-to solution *PT for the variable VI, part two.
> +   This modifies the points-to solution to cater for restrict pointers.
> +
> +   Restrict is modelled as a may-be restrict problem together with
> +   a must-be restrict problem.  From the must-be restrict solution we
> +   can later deduce non-aliasing (if the points-to sets don't intersect
> +   the two references can't alias).  The may-be restrict problem provides
> +   a sort of conservative cap for that such that a pointer p1 that is even
> +   remotely related to a restrict pointer r2 points to a superset of what
> +   p1 points to.  In particular we want to handle this situation:
> +
> +      1 int * restrict p1 = ...;
> +      2 temp = p1;
> +      3 int * restrict p2;
> +      4 p2 = temp;
> +
> +      Suppose that 'temp' is address taken, so (2) is a store and
> +      (4) a load.  We want to make sure that p1 and p2 are tagged
> +      the same (remember we're not handling just the C language
> +      definition of restrict).  To ensure this we need to look through
> +      memory (and even handle second level effects, like when a restrict
> +      pointer is stored into a global variable).
> +
> +   That's why we use the points-to solver for the may-be restrict problem
> +   (which handles memory conservatively correct).  The must-be restrict
> +   part then is formulated as a post-processing on the conservatively
> +   correct points-to solution.  For a set of variables their solution
> +   is pruned.  This pruned solution is returned here.  */
> +
> +static struct pt_solution
> +find_what_var_points_to (varinfo_t vi)
> +{
> +  struct pt_solution pt;
> +
> +  pt = find_what_var_points_to_1 (vi);
> +
> +  if (vi->decl && TREE_CODE (vi->decl) == SSA_NAME)
> +    {
> +      gimple g = SSA_NAME_DEF_STMT (vi->decl);
> +      if (g && is_gimple_assign (g)
> +         && gimple_assign_rhs_code (g) == ADD_RESTRICT)
> +       {
> +         /* Restrict pointers only point to their tags.  For now
> +            we leave also the other decls in the points-to set:
> +            changing the set would imply possibly unsharing the bitmap,
> +            and furthermore it's actually good to have precise
> +            decls in there in some cases, e.g. if it's local variables.
> +
> +            In effect this means removing the nonlocal flags.  To
> +            not regard stores via such pointers as inherently useless
> +            we need to set the vars_contains_escaped_heap flag, if the
> +            input contained some nonlocals.  */
> +         if (pt.vars_contains_nonlocal
> +             || pt.nonlocal
> +             || pt.vars_contains_escaped)
> +           pt.vars_contains_escaped_heap = 1;
> +         pt.nonlocal = 0;
> +         pt.vars_contains_escaped = 0;
> +         pt.vars_contains_nonlocal = 0;
> +       }
> +    }
> +
> +  return pt;
> +}
> +
>  /* Given a pointer variable P, fill in its points-to set.  */
>
>  static void
> @@ -6866,10 +6952,14 @@ compute_points_to_sets (void)
>               *pt = find_what_var_points_to (vi);
>               /* Escaped (and thus nonlocal) variables are always
>                  implicitly used by calls.  */
> -             /* ???  ESCAPED can be empty even though NONLOCAL
> -                always escaped.  */
> -             pt->nonlocal = 1;
> -             pt->escaped = 1;
> +             if (!gimple_call_internal_p (stmt)
> +                 || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
> +               {
> +                 /* ???  ESCAPED can be empty even though NONLOCAL
> +                    always escaped.  */
> +                 pt->nonlocal = 1;
> +                 pt->escaped = 1;
> +               }
>             }
>           else
>             {
> @@ -6887,10 +6977,14 @@ compute_points_to_sets (void)
>               *pt = find_what_var_points_to (vi);
>               /* Escaped (and thus nonlocal) variables are always
>                  implicitly clobbered by calls.  */
> -             /* ???  ESCAPED can be empty even though NONLOCAL
> -                always escaped.  */
> -             pt->nonlocal = 1;
> -             pt->escaped = 1;
> +             if (!gimple_call_internal_p (stmt)
> +                 || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
> +               {
> +                 /* ???  ESCAPED can be empty even though NONLOCAL
> +                    always escaped.  */
> +                 pt->nonlocal = 1;
> +                 pt->escaped = 1;
> +               }
>             }
>           else
>             {
> Index: tree.def
> ===================================================================
> --- tree.def    (revision 205123)
> +++ tree.def    (working copy)
> @@ -977,6 +977,8 @@ DEFTREECODE (WITH_SIZE_EXPR, "with_size_
>     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),
Richard Guenther - Nov. 22, 2013, 10:19 a.m.
On Thu, 21 Nov 2013, Xinliang David Li wrote:

> On Thu, Nov 21, 2013 at 10:03 AM, Michael Matz <matz@suse.de> wrote:
> > Hello,
> >
> > after much pondering about the issue we came up with this design to
> > handle restrict more generally.  Without a completely different way of
> > representing conflicts (or non-conflicts) of memory references we're bound
> > to somehow encode the necessary information into the points-to set (or in
> > any case information related to pointer ssa names).  This in turn means
> > that the location sensitive nature of restrict needs to be made explicit
> > in the IL, i.e. we basically need some starting point when a pointer
> > becomes restrict (ADD_RESTRICT), and also an ending point (DEL_RESTRICT),
> > which must act as barrier for other memory accesses (if it wouldn't some
> > transformations could move references from outside restrict regions into
> > the restrict region making them disasmbiguable with the restrict
> > references, introducing a bug).
> >
> 
> Can you use block/scope information to address this ? References from
> enclosing scopes can be considered possible aliases.

Apart from the issue that LTO drops all BLOCKs this makes the middle-end
feature too much tied to the C family frontends and their definition
of restrict.  It also requires BLOCK lookup / matching at the time
of the alias query (which generally deals with "refs" which may
end up not refering to any BLOCK or to different BLOCKs than the
GIMPLE they are used in).

It also suddenly makes having (correct) BLOCK info cause code generation
differences.

That said, you would somehow need to remember the BLOCK a restrict
"tag" is live in which doesn't make it a good fit for the current
alias-info we associate with SSA names.  If you don't allow
disambiguations against refs in nested BLOCKs then a single
"tag" decl with its associated BLOCK is enough to remember
(thus one additional pointer).

But well - I always wondered how other compilers implement support
for restrict (and how restricted that support is, and how strictly
following the standard).

The only other scheme I can come up with is to allow non-dependences
to be recorded and maintained throughout the compilation and have
frontends create them.

Richard.

> David
> 
> > We also need to use our points-to solver to propagate restrict tags
> > conservatively, postprocessing the information to remove too conservative
> > estimates afterwards per SSA name.
> >
> > And if we want to use restrict based disambiguation we also need to
> > transfer the barriers into RTL barriers (I'm using an asm with an explicit
> > MEM to refer to the pointer in question, so not all memory is clobbered).
> > There's some potential for improvement here by removing useless
> > ADD_RESTRICT / DEL_RESTRICT pairs.
> >
> > There's another improvement when enlargening the set of SSA names to be
> > considered for postprocessin.  Right now only the result of ADD_RESTRICT
> > assigns are handled, that can be improved to also process SSA names that
> > trivial depend on such (i.e. are offsetted and themself restrict typed).
> >
> > That facility is used to implement restrict parameters to functions,
> > replacing the current ad-hoc way in the points-to solver.  Other uses
> > should be done under control of the frontends, as only those know the
> > semantics for real.
> >
> > I have a patch that more aggressively creates ADD_RESTRICT/DEL_RESTRICT
> > pairs (basically whenever there's an assignment from non-restrict pointers
> > to a restrict pointer, on the grounds that this "invents" a new restrict
> > set), but that breaks C programs that we don't want to break (I consider
> > them invalid, but there's disagreement).
> >
> > Some older incarnations of this were bootstrapped, but this specific patch
> > is only now in regstrapping on x86_64-linux.  Okay for trunk if that
> > passes?
> 
> 
> 
> 
> >
> >
> > Ciao,
> > Michael.
> > ---------------------------
> >         * tree.def (ADD_RESTRICT): New tree code.
> >         * cfgexpand.c (expand_debug_expr): Handle it.
> >         * expr.c (expand_pointer_clobber): New function.
> >         (expand_expr_real_2): Use it to handle ADD_RESTRICT.
> >         * expr.h (expand_pointer_clobber): Declare.
> >         * function.c (gimplify_parameters): Return a second gimple_seq,
> >         handle restrict parameters.
> >         * function.h (gimplify_parameters): Adjust.
> >         * gimple-pretty-print.c (dump_binary_rhs): Handle ADD_RESTRICT.
> >         * gimplify.c (gimplify_body): Append second gimple_seq,
> >         adjust call to gimplify_parameters.
> >         * internal-fn.def (DEL_RESTRICT): New internal function code.
> >         * internal-fn.c (expand_DEL_RESTRICT): New function.
> >         * tree-cfg.c (verify_gimple_assign_binary): Check ADD_RESTRICT.
> >         * tree-inline.c (estimate_operator_cost): Handle ADD_RESTRICT.
> >         * tree-pretty-print.c (dump_generic_node): Ditto.
> >         * tree-ssa-dce.c (propagate_necessity): DEL_RESTRICT calls
> >         are only clobbers.
> >         * tree-ssa-structalias.c (build_fake_var_decl_uid): New static
> >         function.
> >         (build_fake_var_decl): Rewrite in terms of above.
> >         (make_heapvar): Take uid parameter.
> >         (make_constraint_from_restrict_uid): New.
> >         (make_constraint_from_restrict): Use above.
> >         (make_constraint_from_global_restrict): Explicitely set global flag.
> >         (handle_lhs_call): Adjust call to make_heapvar.
> >         (find_func_aliases_for_internal_call): New.
> >         (find_func_aliases_for_call): Use it.
> >         (find_func_aliases): Handle ADD_RESTRICT.
> >         (intra_create_variable_infos): Remove any explicit handling
> >         of restrict parameters.
> >         (set_uids_in_ptset): Update instead of overwrite
> >         vars_contains_escaped_heap flag.
> >         (find_what_var_points_to_1): Renamed from ...
> >         (find_what_var_points_to): ... this, which is now wrapper
> >         postprocessing points-to flags.
> >         (compute_points_to_sets): Ignore DEL_RESTRICT calls.
> >
> > Index: cfgexpand.c
> > ===================================================================
> > --- cfgexpand.c (revision 205123)
> > +++ cfgexpand.c (working copy)
> > @@ -3785,6 +3785,7 @@ expand_debug_expr (tree exp)
> >        /* Fall through.  */
> >
> >      adjust_mode:
> > +    case ADD_RESTRICT:
> >      case PAREN_EXPR:
> >      case NOP_EXPR:
> >      case CONVERT_EXPR:
> > Index: expr.c
> > ===================================================================
> > --- expr.c      (revision 205123)
> > +++ expr.c      (working copy)
> > @@ -7988,6 +7988,41 @@ expand_cond_expr_using_cmove (tree treeo
> >    return NULL_RTX;
> >  }
> >
> > +/* Given a memory pointer PTR, expand an RTL asm statement
> > +   that merely clobbers memory reachable from that pointer
> > +   via arbitrary offsets.  */
> > +
> > +void
> > +expand_pointer_clobber (tree ptr, location_t loc)
> > +{
> > +  tree ref = build_simple_mem_ref (ptr);
> > +  rtx op = expand_expr (ref, NULL_RTX, BLKmode, EXPAND_MEMORY);
> > +  rtx body;
> > +
> > +  op = validize_mem (op);
> > +
> > +  /* There's no way to construct a tree expression doing exactly what
> > +     we need (representing a reference to arbitrarily memory reachable
> > +     from a given pointer, i.e. with arbitrary offsets.  Hence
> > +     construct that by massaging the MEM attributes.  */
> > +  clear_mem_offset (op);
> > +  clear_mem_size (op);
> > +  PUT_MODE (op, BLKmode);
> > +
> > +  rtvec argvec = rtvec_alloc (0);
> > +  rtvec constraintvec = rtvec_alloc (0);
> > +  rtvec labelvec = rtvec_alloc (0);
> > +
> > +  body = gen_rtx_ASM_OPERANDS (BLKmode,
> > +                              ggc_strdup (""),
> > +                              ggc_strdup ("=m"), 0, argvec, constraintvec,
> > +                              labelvec, loc);
> > +
> > +  MEM_VOLATILE_P (body) = 1;
> > +
> > +  emit_insn (gen_rtx_SET (VOIDmode, op, body));
> > +}
> > +
> >  rtx
> >  expand_expr_real_2 (sepops ops, rtx target, enum machine_mode tmode,
> >                     enum expand_modifier modifier)
> > @@ -8047,6 +8082,13 @@ expand_expr_real_2 (sepops ops, rtx targ
> >
> >    switch (code)
> >      {
> > +    case ADD_RESTRICT:
> > +      /* We can handle add_restrict like a conversion, treeop1 will be
> > +         ignored.  But do create a barrier to contain the restrict
> > +        section.  */
> > +      expand_pointer_clobber (treeop0, loc);
> > +
> > +      /* FALLTHRU.  */
> >      case NON_LVALUE_EXPR:
> >      case PAREN_EXPR:
> >      CASE_CONVERT:
> > Index: expr.h
> > ===================================================================
> > --- expr.h      (revision 205123)
> > +++ expr.h      (working copy)
> > @@ -719,6 +719,8 @@ extern rtx extract_low_bits (enum machin
> >  extern rtx expand_mult (enum machine_mode, rtx, rtx, rtx, int);
> >  extern rtx expand_mult_highpart_adjust (enum machine_mode, rtx, rtx, rtx, rtx, int);
> >
> > +extern void expand_pointer_clobber (tree, location_t);
> > +
> >  extern rtx assemble_static_space (unsigned HOST_WIDE_INT);
> >  extern int safe_from_p (const_rtx, tree, int);
> >  extern bool split_comparison (enum rtx_code, enum machine_mode,
> > Index: function.c
> > ===================================================================
> > --- function.c  (revision 205123)
> > +++ function.c  (working copy)
> > @@ -3595,10 +3595,11 @@ gimplify_parm_type (tree *tp, int *walk_
> >  /* Gimplify the parameter list for current_function_decl.  This involves
> >     evaluating SAVE_EXPRs of variable sized parameters and generating code
> >     to implement callee-copies reference parameters.  Returns a sequence of
> > -   statements to add to the beginning of the function.  */
> > +   statements to add to the beginning of the function and another
> > +   sequence to add to the end of the function (via *STMT_AFTER).  */
> >
> >  gimple_seq
> > -gimplify_parameters (void)
> > +gimplify_parameters (gimple_seq *stmts_after)
> >  {
> >    struct assign_parm_data_all all;
> >    tree parm;
> > @@ -3606,6 +3607,7 @@ gimplify_parameters (void)
> >    vec<tree> fnargs;
> >    unsigned i;
> >
> > +  *stmts_after = NULL;
> >    assign_parms_initialize_all (&all);
> >    fnargs = assign_parms_augmented_arg_list (&all);
> >
> > @@ -3690,6 +3692,17 @@ gimplify_parameters (void)
> >               DECL_HAS_VALUE_EXPR_P (parm) = 1;
> >             }
> >         }
> > +      if (POINTER_TYPE_P (TREE_TYPE (parm))
> > +         && TYPE_RESTRICT (TREE_TYPE (parm))
> > +         && !DECL_HAS_VALUE_EXPR_P (parm))
> > +       {
> > +         tree t = fold_build2 (ADD_RESTRICT, TREE_TYPE (parm), parm,
> > +                               build_int_cst (integer_type_node,
> > +                                              allocate_decl_uid ()));
> > +         gimplify_assign (parm, t, &stmts);
> > +         gimple g = gimple_build_call_internal (IFN_DEL_RESTRICT, 1, parm);
> > +         gimple_seq_add_stmt (stmts_after, g);
> > +       }
> >      }
> >
> >    fnargs.release ();
> > Index: function.h
> > ===================================================================
> > --- function.h  (revision 205123)
> > +++ function.h  (working copy)
> > @@ -841,6 +841,6 @@ extern void preserve_temp_slots (rtx);
> >  extern int aggregate_value_p (const_tree, const_tree);
> >  extern void push_function_context (void);
> >  extern void pop_function_context (void);
> > -extern gimple_seq gimplify_parameters (void);
> > +extern gimple_seq gimplify_parameters (gimple_seq *);
> >
> >  #endif  /* GCC_FUNCTION_H */
> > Index: gimple-pretty-print.c
> > ===================================================================
> > --- gimple-pretty-print.c       (revision 205123)
> > +++ gimple-pretty-print.c       (working copy)
> > @@ -348,6 +348,7 @@ dump_binary_rhs (pretty_printer *buffer,
> >      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_WIDEN_MULT_EVEN_EXPR:
> > Index: gimplify.c
> > ===================================================================
> > --- gimplify.c  (revision 205123)
> > +++ gimplify.c  (working copy)
> > @@ -1005,8 +1005,9 @@ gimplify_bind_expr (tree *expr_p, gimple
> >           && !DECL_HARD_REGISTER (t)
> >           && !TREE_THIS_VOLATILE (t)
> >           && !DECL_HAS_VALUE_EXPR_P (t)
> > -         /* Only care for variables that have to be in memory.  Others
> > -            will be rewritten into SSA names, hence moved to the top-level.  */
> > +         /* Only care for variables that have to be in memory.
> > +            Others will be rewritten into SSA names, hence moved
> > +            to the top-level.  */
> >           && !is_gimple_reg (t)
> >           && flag_stack_reuse != SR_NONE)
> >         {
> > @@ -8356,7 +8357,7 @@ gimple
> >  gimplify_body (tree fndecl, bool do_parms)
> >  {
> >    location_t saved_location = input_location;
> > -  gimple_seq parm_stmts, seq;
> > +  gimple_seq parm_stmts, parm_stmts_after, seq;
> >    gimple outer_bind;
> >    struct gimplify_ctx gctx;
> >    struct cgraph_node *cgn;
> > @@ -8393,7 +8394,8 @@ gimplify_body (tree fndecl, bool do_parm
> >
> >    /* Resolve callee-copies.  This has to be done before processing
> >       the body so that DECL_VALUE_EXPR gets processed correctly.  */
> > -  parm_stmts = do_parms ? gimplify_parameters () : NULL;
> > +  parm_stmts_after = NULL;
> > +  parm_stmts = do_parms ? gimplify_parameters (&parm_stmts_after) : NULL;
> >
> >    /* Gimplify the function's body.  */
> >    seq = NULL;
> > @@ -8432,6 +8434,10 @@ gimplify_body (tree fndecl, bool do_parm
> >             DECL_IGNORED_P (parm) = 0;
> >           }
> >      }
> > +  /* Same for statements that need to come after the body.  */
> > +  if (!gimple_seq_empty_p (parm_stmts_after))
> > +    gimplify_seq_add_seq (gimple_bind_body_ptr (outer_bind),
> > +                         parm_stmts_after);
> >
> >    if (nonlocal_vlas)
> >      {
> > Index: internal-fn.c
> > ===================================================================
> > --- internal-fn.c       (revision 205123)
> > +++ internal-fn.c       (working copy)
> > @@ -148,6 +148,16 @@ expand_UBSAN_NULL (gimple stmt ATTRIBUTE
> >    gcc_unreachable ();
> >  }
> >
> > +/* Expand the DEL_RESTRICT internal function into a RTL
> > +   asm that merely clobbers memory reachable via the pointer.  */
> > +
> > +static void
> > +expand_DEL_RESTRICT (gimple stmt)
> > +{
> > +  tree ptr = gimple_call_arg (stmt, 0);
> > +  expand_pointer_clobber (ptr, gimple_location (stmt));
> > +}
> > +
> >  /* Routines to expand each internal function, indexed by function number.
> >     Each routine has the prototype:
> >
> > Index: internal-fn.def
> > ===================================================================
> > --- internal-fn.def     (revision 205123)
> > +++ internal-fn.def     (working copy)
> > @@ -45,3 +45,4 @@ DEF_INTERNAL_FN (GOMP_SIMD_VF, ECF_CONST
> >  DEF_INTERNAL_FN (GOMP_SIMD_LAST_LANE, ECF_CONST | ECF_LEAF | ECF_NOTHROW)
> >  DEF_INTERNAL_FN (ANNOTATE,  ECF_CONST | ECF_LEAF | ECF_NOTHROW)
> >  DEF_INTERNAL_FN (UBSAN_NULL, ECF_LEAF | ECF_NOTHROW)
> > +DEF_INTERNAL_FN (DEL_RESTRICT,  /*ECF_LEAF |*/ ECF_NOTHROW)
> > Index: tree-cfg.c
> > ===================================================================
> > --- tree-cfg.c  (revision 205123)
> > +++ tree-cfg.c  (working copy)
> > @@ -3627,6 +3627,21 @@ verify_gimple_assign_binary (gimple stmt
> >         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:
> > Index: tree-inline.c
> > ===================================================================
> > --- tree-inline.c       (revision 205123)
> > +++ tree-inline.c       (working copy)
> > @@ -3580,6 +3580,7 @@ estimate_operator_cost (enum tree_code c
> >      case COMPLEX_EXPR:
> >      case PAREN_EXPR:
> >      case VIEW_CONVERT_EXPR:
> > +    case ADD_RESTRICT:
> >        return 0;
> >
> >      /* Assign cost of 1 to usual operations.
> > Index: tree-pretty-print.c
> > ===================================================================
> > --- tree-pretty-print.c (revision 205123)
> > +++ tree-pretty-print.c (working copy)
> > @@ -1927,6 +1927,14 @@ dump_generic_node (pretty_printer *buffe
> >        pp_greater (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: tree-ssa-dce.c
> > ===================================================================
> > --- tree-ssa-dce.c      (revision 205123)
> > +++ tree-ssa-dce.c      (working copy)
> > @@ -828,6 +828,10 @@ propagate_necessity (bool aggressive)
> >                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
> >                 continue;
> >
> > +             if (gimple_call_internal_p (stmt)
> > +                 && gimple_call_internal_fn (stmt) == IFN_DEL_RESTRICT)
> > +               continue;
> > +
> >               /* Calls implicitly load from memory, their arguments
> >                  in addition may explicitly perform memory loads.  */
> >               mark_all_reaching_defs_necessary (stmt);
> > Index: tree-ssa-structalias.c
> > ===================================================================
> > --- tree-ssa-structalias.c      (revision 205123)
> > +++ tree-ssa-structalias.c      (working copy)
> > @@ -3741,31 +3741,43 @@ make_transitive_closure_constraints (var
> >  /* Temporary storage for fake var decls.  */
> >  struct obstack fake_var_decl_obstack;
> >
> > -/* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
> > +/* 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 (tree type)
> > +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) = allocate_decl_uid ();
> > +  DECL_UID (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.  */
> > +/* 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)
> > +make_heapvar (const char *name, int uid)
> >  {
> >    varinfo_t vi;
> >    tree heapvar;
> >
> > -  heapvar = build_fake_var_decl (ptr_type_node);
> > +  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);
> > @@ -3781,22 +3793,34 @@ make_heapvar (const char *name)
> >    return vi;
> >  }
> >
> > -/* Create a new artificial heap variable with NAME and make a
> > +/* 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 varinfo_t
> > -make_constraint_from_restrict (varinfo_t lhs, const char *name)
> > +make_constraint_from_restrict_uid (varinfo_t lhs, const char *name, int uid)
> >  {
> > -  varinfo_t vi = make_heapvar (name);
> > -  vi->is_global_var = 1;
> > -  vi->may_have_pointers = 1;
> > +  varinfo_t vi;
> > +  vi = make_heapvar (name, uid);
> >    make_constraint_from (lhs, vi->id);
> > +  vi->is_global_var = 0;
> > +  /*vi->is_special_var = 1;*/
> > +  vi->may_have_pointers = 1;
> >    return vi;
> >  }
> >
> >  /* Create a new artificial heap variable with NAME and make a
> >     constraint from it to LHS.  Set flags according to a tag used
> > +   for tracking restrict pointers.  */
> > +
> > +static varinfo_t
> > +make_constraint_from_restrict (varinfo_t lhs, const char *name)
> > +{
> > +  return make_constraint_from_restrict_uid (lhs, name, -1);
> > +}
> > +
> > +/* Create a new artificial heap variable with NAME and make a
> > +   constraint from it to LHS.  Set flags according to a tag used
> >     for tracking restrict pointers and make the artificial heap
> >     point to global memory.  */
> >
> > @@ -3804,6 +3828,7 @@ static varinfo_t
> >  make_constraint_from_global_restrict (varinfo_t lhs, const char *name)
> >  {
> >    varinfo_t vi = make_constraint_from_restrict (lhs, name);
> > +  vi->is_global_var = 1;
> >    make_copy_constraint (vi, nonlocal_id);
> >    return vi;
> >  }
> > @@ -3999,7 +4024,7 @@ handle_lhs_call (gimple stmt, tree lhs,
> >        varinfo_t vi;
> >        struct constraint_expr tmpc;
> >        rhsc.create (0);
> > -      vi = make_heapvar ("HEAP");
> > +      vi = make_heapvar ("HEAP", -1);
> >        /* We marking allocated storage local, we deal with it becoming
> >           global by escaping and setting of vars_contains_escaped_heap.  */
> >        DECL_EXTERNAL (vi->decl) = 0;
> > @@ -4490,6 +4515,28 @@ find_func_aliases_for_builtin_call (gimp
> >    return false;
> >  }
> >
> > +/* Create constraints for the internal call T.  Return true if the call
> > +   was handled, otherwise false.  */
> > +
> > +static bool
> > +find_func_aliases_for_internal_call (gimple t)
> > +{
> > +  switch (gimple_call_internal_fn (t))
> > +    {
> > +    case IFN_DEL_RESTRICT:
> > +      {
> > +       /* DEL_RESTRICT is a barrier for what its argument points to.  */
> > +       tree ptr = gimple_call_arg (t, 0);
> > +       make_constraint_to (get_call_clobber_vi (t)->id, ptr);
> > +       return true;
> > +      }
> > +
> > +    default:
> > +      /* Fallthru to general call handling.  */;
> > +    }
> > +  return false;
> > +}
> > +
> >  /* Create constraints for the call T.  */
> >
> >  static void
> > @@ -4505,6 +4552,10 @@ find_func_aliases_for_call (gimple t)
> >        && find_func_aliases_for_builtin_call (t))
> >      return;
> >
> > +  if (gimple_call_internal_p (t)
> > +      && find_func_aliases_for_internal_call (t))
> > +    return;
> > +
> >    fi = get_fi_for_callee (t);
> >    if (!in_ipa_mode
> >        || (fndecl && !fi->is_fn_info))
> > @@ -4715,6 +4766,16 @@ find_func_aliases (gimple origt)
> >             /* Truth value results are not pointer (parts).  Or at least
> >                very very unreasonable obfuscation of a part.  */
> >             ;
> > +         else if (gimple_assign_rhs_code (t) == ADD_RESTRICT)
> > +           {
> > +             /* Add the specified restrict tag and merge from
> > +                the incoming pointer.  */
> > +             make_constraint_from_restrict_uid (get_vi_for_tree (lhsop),
> > +                                                "RESTRICT_TAG",
> > +                                                TREE_INT_CST_LOW
> > +                                                  (gimple_assign_rhs2 (t)));
> > +             get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
> > +           }
> >           else
> >             {
> >               /* All other operations are merges.  */
> > @@ -5852,50 +5913,10 @@ intra_create_variable_infos (void)
> >      {
> >        varinfo_t p = get_vi_for_tree (t);
> >
> > -      /* For restrict qualified pointers to objects passed by
> > -         reference build a real representative for the pointed-to object.
> > -        Treat restrict qualified references the same.  */
> > -      if (TYPE_RESTRICT (TREE_TYPE (t))
> > -         && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
> > -             || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
> > -         && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
> > -       {
> > -         struct constraint_expr lhsc, rhsc;
> > -         varinfo_t vi;
> > -         tree heapvar = build_fake_var_decl (TREE_TYPE (TREE_TYPE (t)));
> > -         DECL_EXTERNAL (heapvar) = 1;
> > -         vi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS");
> > -         insert_vi_for_tree (heapvar, vi);
> > -         lhsc.var = p->id;
> > -         lhsc.type = SCALAR;
> > -         lhsc.offset = 0;
> > -         rhsc.var = vi->id;
> > -         rhsc.type = ADDRESSOF;
> > -         rhsc.offset = 0;
> > -         process_constraint (new_constraint (lhsc, rhsc));
> > -         for (; vi; vi = vi_next (vi))
> > -           if (vi->may_have_pointers)
> > -             {
> > -               if (vi->only_restrict_pointers)
> > -                 make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
> > -               else
> > -                 make_copy_constraint (vi, nonlocal_id);
> > -             }
> > -         continue;
> > -       }
> > -
> > -      if (POINTER_TYPE_P (TREE_TYPE (t))
> > -         && TYPE_RESTRICT (TREE_TYPE (t)))
> > -       make_constraint_from_global_restrict (p, "PARM_RESTRICT");
> > -      else
> > +      for (; p; p = vi_next (p))
> >         {
> > -         for (; p; p = vi_next (p))
> > -           {
> > -             if (p->only_restrict_pointers)
> > -               make_constraint_from_global_restrict (p, "PARM_RESTRICT");
> > -             else if (p->may_have_pointers)
> > -               make_constraint_from (p, nonlocal_id);
> > -           }
> > +         if (p->may_have_pointers)
> > +           make_constraint_from (p, nonlocal_id);
> >         }
> >      }
> >
> > @@ -6022,7 +6043,7 @@ set_uids_in_ptset (bitmap into, bitmap f
> >               && bitmap_bit_p (escaped_vi->solution, i)))
> >         {
> >           pt->vars_contains_escaped = true;
> > -         pt->vars_contains_escaped_heap = vi->is_heap_var;
> > +         pt->vars_contains_escaped_heap |= vi->is_heap_var;
> >         }
> >
> >        if (TREE_CODE (vi->decl) == VAR_DECL
> > @@ -6045,10 +6066,10 @@ set_uids_in_ptset (bitmap into, bitmap f
> >  }
> >
> >
> > -/* Compute the points-to solution *PT for the variable VI.  */
> > +/* Compute the points-to solution *PT for the variable VI, part one.  */
> >
> >  static struct pt_solution
> > -find_what_var_points_to (varinfo_t orig_vi)
> > +find_what_var_points_to_1 (varinfo_t orig_vi)
> >  {
> >    unsigned int i;
> >    bitmap_iterator bi;
> > @@ -6096,7 +6117,7 @@ find_what_var_points_to (varinfo_t orig_
> >             /* Nobody cares.  */
> >             ;
> >           else if (vi->id == anything_id
> > -                  || vi->id == integer_id)
> > +                   || vi->id == integer_id)
> >             pt->anything = 1;
> >         }
> >      }
> > @@ -6126,6 +6147,71 @@ find_what_var_points_to (varinfo_t orig_
> >    return *pt;
> >  }
> >
> > +/* Compute the points-to solution *PT for the variable VI, part two.
> > +   This modifies the points-to solution to cater for restrict pointers.
> > +
> > +   Restrict is modelled as a may-be restrict problem together with
> > +   a must-be restrict problem.  From the must-be restrict solution we
> > +   can later deduce non-aliasing (if the points-to sets don't intersect
> > +   the two references can't alias).  The may-be restrict problem provides
> > +   a sort of conservative cap for that such that a pointer p1 that is even
> > +   remotely related to a restrict pointer r2 points to a superset of what
> > +   p1 points to.  In particular we want to handle this situation:
> > +
> > +      1 int * restrict p1 = ...;
> > +      2 temp = p1;
> > +      3 int * restrict p2;
> > +      4 p2 = temp;
> > +
> > +      Suppose that 'temp' is address taken, so (2) is a store and
> > +      (4) a load.  We want to make sure that p1 and p2 are tagged
> > +      the same (remember we're not handling just the C language
> > +      definition of restrict).  To ensure this we need to look through
> > +      memory (and even handle second level effects, like when a restrict
> > +      pointer is stored into a global variable).
> > +
> > +   That's why we use the points-to solver for the may-be restrict problem
> > +   (which handles memory conservatively correct).  The must-be restrict
> > +   part then is formulated as a post-processing on the conservatively
> > +   correct points-to solution.  For a set of variables their solution
> > +   is pruned.  This pruned solution is returned here.  */
> > +
> > +static struct pt_solution
> > +find_what_var_points_to (varinfo_t vi)
> > +{
> > +  struct pt_solution pt;
> > +
> > +  pt = find_what_var_points_to_1 (vi);
> > +
> > +  if (vi->decl && TREE_CODE (vi->decl) == SSA_NAME)
> > +    {
> > +      gimple g = SSA_NAME_DEF_STMT (vi->decl);
> > +      if (g && is_gimple_assign (g)
> > +         && gimple_assign_rhs_code (g) == ADD_RESTRICT)
> > +       {
> > +         /* Restrict pointers only point to their tags.  For now
> > +            we leave also the other decls in the points-to set:
> > +            changing the set would imply possibly unsharing the bitmap,
> > +            and furthermore it's actually good to have precise
> > +            decls in there in some cases, e.g. if it's local variables.
> > +
> > +            In effect this means removing the nonlocal flags.  To
> > +            not regard stores via such pointers as inherently useless
> > +            we need to set the vars_contains_escaped_heap flag, if the
> > +            input contained some nonlocals.  */
> > +         if (pt.vars_contains_nonlocal
> > +             || pt.nonlocal
> > +             || pt.vars_contains_escaped)
> > +           pt.vars_contains_escaped_heap = 1;
> > +         pt.nonlocal = 0;
> > +         pt.vars_contains_escaped = 0;
> > +         pt.vars_contains_nonlocal = 0;
> > +       }
> > +    }
> > +
> > +  return pt;
> > +}
> > +
> >  /* Given a pointer variable P, fill in its points-to set.  */
> >
> >  static void
> > @@ -6866,10 +6952,14 @@ compute_points_to_sets (void)
> >               *pt = find_what_var_points_to (vi);
> >               /* Escaped (and thus nonlocal) variables are always
> >                  implicitly used by calls.  */
> > -             /* ???  ESCAPED can be empty even though NONLOCAL
> > -                always escaped.  */
> > -             pt->nonlocal = 1;
> > -             pt->escaped = 1;
> > +             if (!gimple_call_internal_p (stmt)
> > +                 || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
> > +               {
> > +                 /* ???  ESCAPED can be empty even though NONLOCAL
> > +                    always escaped.  */
> > +                 pt->nonlocal = 1;
> > +                 pt->escaped = 1;
> > +               }
> >             }
> >           else
> >             {
> > @@ -6887,10 +6977,14 @@ compute_points_to_sets (void)
> >               *pt = find_what_var_points_to (vi);
> >               /* Escaped (and thus nonlocal) variables are always
> >                  implicitly clobbered by calls.  */
> > -             /* ???  ESCAPED can be empty even though NONLOCAL
> > -                always escaped.  */
> > -             pt->nonlocal = 1;
> > -             pt->escaped = 1;
> > +             if (!gimple_call_internal_p (stmt)
> > +                 || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
> > +               {
> > +                 /* ???  ESCAPED can be empty even though NONLOCAL
> > +                    always escaped.  */
> > +                 pt->nonlocal = 1;
> > +                 pt->escaped = 1;
> > +               }
> >             }
> >           else
> >             {
> > Index: tree.def
> > ===================================================================
> > --- tree.def    (revision 205123)
> > +++ tree.def    (working copy)
> > @@ -977,6 +977,8 @@ DEFTREECODE (WITH_SIZE_EXPR, "with_size_
> >     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),
> 
>
Xinliang David Li - Nov. 22, 2013, 4:39 p.m.
On Fri, Nov 22, 2013 at 2:19 AM, Richard Biener <rguenther@suse.de> wrote:
> On Thu, 21 Nov 2013, Xinliang David Li wrote:
>
>> On Thu, Nov 21, 2013 at 10:03 AM, Michael Matz <matz@suse.de> wrote:
>> > Hello,
>> >
>> > after much pondering about the issue we came up with this design to
>> > handle restrict more generally.  Without a completely different way of
>> > representing conflicts (or non-conflicts) of memory references we're bound
>> > to somehow encode the necessary information into the points-to set (or in
>> > any case information related to pointer ssa names).  This in turn means
>> > that the location sensitive nature of restrict needs to be made explicit
>> > in the IL, i.e. we basically need some starting point when a pointer
>> > becomes restrict (ADD_RESTRICT), and also an ending point (DEL_RESTRICT),
>> > which must act as barrier for other memory accesses (if it wouldn't some
>> > transformations could move references from outside restrict regions into
>> > the restrict region making them disasmbiguable with the restrict
>> > references, introducing a bug).
>> >
>>
>> Can you use block/scope information to address this ? References from
>> enclosing scopes can be considered possible aliases.
>
> Apart from the issue that LTO drops all BLOCKs this makes the middle-end
> feature too much tied to the C family frontends and their definition
> of restrict.  It also requires BLOCK lookup / matching at the time
> of the alias query (which generally deals with "refs" which may
> end up not refering to any BLOCK or to different BLOCKs than the
> GIMPLE they are used in).

Can the aliaser capture the scope info and maintain its own minimal
block tree? Each ref will have a unique scope id.  Code duplication
transformations need to propagate info properly.

>
> It also suddenly makes having (correct) BLOCK info cause code generation
> differences.

Is it an issue if it is not affected by with -g is specified or not?

>
> That said, you would somehow need to remember the BLOCK a restrict
> "tag" is live in which doesn't make it a good fit for the current
> alias-info we associate with SSA names.  If you don't allow
> disambiguations against refs in nested BLOCKs then a single
> "tag" decl with its associated BLOCK is enough to remember
> (thus one additional pointer).
>
> But well - I always wondered how other compilers implement support
> for restrict (and how restricted that support is, and how strictly
> following the standard).
>
> The only other scheme I can come up with is to allow non-dependences
> to be recorded and maintained throughout the compilation and have
> frontends create them.

It has been a while, but I recall one compiler does similar things --
pretty early in the middle end before blocks are stripped, per-scope
pointer analysis/tracking is done for scopes with restrict pointer
uses. When that is done, alias pairs that can be disambiguated are
recorded, and this information is maintained throughout (including
inline tranformation).

thanks,

David

>
> Richard.
>
>> David
>>
>> > We also need to use our points-to solver to propagate restrict tags
>> > conservatively, postprocessing the information to remove too conservative
>> > estimates afterwards per SSA name.
>> >
>> > And if we want to use restrict based disambiguation we also need to
>> > transfer the barriers into RTL barriers (I'm using an asm with an explicit
>> > MEM to refer to the pointer in question, so not all memory is clobbered).
>> > There's some potential for improvement here by removing useless
>> > ADD_RESTRICT / DEL_RESTRICT pairs.
>> >
>> > There's another improvement when enlargening the set of SSA names to be
>> > considered for postprocessin.  Right now only the result of ADD_RESTRICT
>> > assigns are handled, that can be improved to also process SSA names that
>> > trivial depend on such (i.e. are offsetted and themself restrict typed).
>> >
>> > That facility is used to implement restrict parameters to functions,
>> > replacing the current ad-hoc way in the points-to solver.  Other uses
>> > should be done under control of the frontends, as only those know the
>> > semantics for real.
>> >
>> > I have a patch that more aggressively creates ADD_RESTRICT/DEL_RESTRICT
>> > pairs (basically whenever there's an assignment from non-restrict pointers
>> > to a restrict pointer, on the grounds that this "invents" a new restrict
>> > set), but that breaks C programs that we don't want to break (I consider
>> > them invalid, but there's disagreement).
>> >
>> > Some older incarnations of this were bootstrapped, but this specific patch
>> > is only now in regstrapping on x86_64-linux.  Okay for trunk if that
>> > passes?
>>
>>
>>
>>
>> >
>> >
>> > Ciao,
>> > Michael.
>> > ---------------------------
>> >         * tree.def (ADD_RESTRICT): New tree code.
>> >         * cfgexpand.c (expand_debug_expr): Handle it.
>> >         * expr.c (expand_pointer_clobber): New function.
>> >         (expand_expr_real_2): Use it to handle ADD_RESTRICT.
>> >         * expr.h (expand_pointer_clobber): Declare.
>> >         * function.c (gimplify_parameters): Return a second gimple_seq,
>> >         handle restrict parameters.
>> >         * function.h (gimplify_parameters): Adjust.
>> >         * gimple-pretty-print.c (dump_binary_rhs): Handle ADD_RESTRICT.
>> >         * gimplify.c (gimplify_body): Append second gimple_seq,
>> >         adjust call to gimplify_parameters.
>> >         * internal-fn.def (DEL_RESTRICT): New internal function code.
>> >         * internal-fn.c (expand_DEL_RESTRICT): New function.
>> >         * tree-cfg.c (verify_gimple_assign_binary): Check ADD_RESTRICT.
>> >         * tree-inline.c (estimate_operator_cost): Handle ADD_RESTRICT.
>> >         * tree-pretty-print.c (dump_generic_node): Ditto.
>> >         * tree-ssa-dce.c (propagate_necessity): DEL_RESTRICT calls
>> >         are only clobbers.
>> >         * tree-ssa-structalias.c (build_fake_var_decl_uid): New static
>> >         function.
>> >         (build_fake_var_decl): Rewrite in terms of above.
>> >         (make_heapvar): Take uid parameter.
>> >         (make_constraint_from_restrict_uid): New.
>> >         (make_constraint_from_restrict): Use above.
>> >         (make_constraint_from_global_restrict): Explicitely set global flag.
>> >         (handle_lhs_call): Adjust call to make_heapvar.
>> >         (find_func_aliases_for_internal_call): New.
>> >         (find_func_aliases_for_call): Use it.
>> >         (find_func_aliases): Handle ADD_RESTRICT.
>> >         (intra_create_variable_infos): Remove any explicit handling
>> >         of restrict parameters.
>> >         (set_uids_in_ptset): Update instead of overwrite
>> >         vars_contains_escaped_heap flag.
>> >         (find_what_var_points_to_1): Renamed from ...
>> >         (find_what_var_points_to): ... this, which is now wrapper
>> >         postprocessing points-to flags.
>> >         (compute_points_to_sets): Ignore DEL_RESTRICT calls.
>> >
>> > Index: cfgexpand.c
>> > ===================================================================
>> > --- cfgexpand.c (revision 205123)
>> > +++ cfgexpand.c (working copy)
>> > @@ -3785,6 +3785,7 @@ expand_debug_expr (tree exp)
>> >        /* Fall through.  */
>> >
>> >      adjust_mode:
>> > +    case ADD_RESTRICT:
>> >      case PAREN_EXPR:
>> >      case NOP_EXPR:
>> >      case CONVERT_EXPR:
>> > Index: expr.c
>> > ===================================================================
>> > --- expr.c      (revision 205123)
>> > +++ expr.c      (working copy)
>> > @@ -7988,6 +7988,41 @@ expand_cond_expr_using_cmove (tree treeo
>> >    return NULL_RTX;
>> >  }
>> >
>> > +/* Given a memory pointer PTR, expand an RTL asm statement
>> > +   that merely clobbers memory reachable from that pointer
>> > +   via arbitrary offsets.  */
>> > +
>> > +void
>> > +expand_pointer_clobber (tree ptr, location_t loc)
>> > +{
>> > +  tree ref = build_simple_mem_ref (ptr);
>> > +  rtx op = expand_expr (ref, NULL_RTX, BLKmode, EXPAND_MEMORY);
>> > +  rtx body;
>> > +
>> > +  op = validize_mem (op);
>> > +
>> > +  /* There's no way to construct a tree expression doing exactly what
>> > +     we need (representing a reference to arbitrarily memory reachable
>> > +     from a given pointer, i.e. with arbitrary offsets.  Hence
>> > +     construct that by massaging the MEM attributes.  */
>> > +  clear_mem_offset (op);
>> > +  clear_mem_size (op);
>> > +  PUT_MODE (op, BLKmode);
>> > +
>> > +  rtvec argvec = rtvec_alloc (0);
>> > +  rtvec constraintvec = rtvec_alloc (0);
>> > +  rtvec labelvec = rtvec_alloc (0);
>> > +
>> > +  body = gen_rtx_ASM_OPERANDS (BLKmode,
>> > +                              ggc_strdup (""),
>> > +                              ggc_strdup ("=m"), 0, argvec, constraintvec,
>> > +                              labelvec, loc);
>> > +
>> > +  MEM_VOLATILE_P (body) = 1;
>> > +
>> > +  emit_insn (gen_rtx_SET (VOIDmode, op, body));
>> > +}
>> > +
>> >  rtx
>> >  expand_expr_real_2 (sepops ops, rtx target, enum machine_mode tmode,
>> >                     enum expand_modifier modifier)
>> > @@ -8047,6 +8082,13 @@ expand_expr_real_2 (sepops ops, rtx targ
>> >
>> >    switch (code)
>> >      {
>> > +    case ADD_RESTRICT:
>> > +      /* We can handle add_restrict like a conversion, treeop1 will be
>> > +         ignored.  But do create a barrier to contain the restrict
>> > +        section.  */
>> > +      expand_pointer_clobber (treeop0, loc);
>> > +
>> > +      /* FALLTHRU.  */
>> >      case NON_LVALUE_EXPR:
>> >      case PAREN_EXPR:
>> >      CASE_CONVERT:
>> > Index: expr.h
>> > ===================================================================
>> > --- expr.h      (revision 205123)
>> > +++ expr.h      (working copy)
>> > @@ -719,6 +719,8 @@ extern rtx extract_low_bits (enum machin
>> >  extern rtx expand_mult (enum machine_mode, rtx, rtx, rtx, int);
>> >  extern rtx expand_mult_highpart_adjust (enum machine_mode, rtx, rtx, rtx, rtx, int);
>> >
>> > +extern void expand_pointer_clobber (tree, location_t);
>> > +
>> >  extern rtx assemble_static_space (unsigned HOST_WIDE_INT);
>> >  extern int safe_from_p (const_rtx, tree, int);
>> >  extern bool split_comparison (enum rtx_code, enum machine_mode,
>> > Index: function.c
>> > ===================================================================
>> > --- function.c  (revision 205123)
>> > +++ function.c  (working copy)
>> > @@ -3595,10 +3595,11 @@ gimplify_parm_type (tree *tp, int *walk_
>> >  /* Gimplify the parameter list for current_function_decl.  This involves
>> >     evaluating SAVE_EXPRs of variable sized parameters and generating code
>> >     to implement callee-copies reference parameters.  Returns a sequence of
>> > -   statements to add to the beginning of the function.  */
>> > +   statements to add to the beginning of the function and another
>> > +   sequence to add to the end of the function (via *STMT_AFTER).  */
>> >
>> >  gimple_seq
>> > -gimplify_parameters (void)
>> > +gimplify_parameters (gimple_seq *stmts_after)
>> >  {
>> >    struct assign_parm_data_all all;
>> >    tree parm;
>> > @@ -3606,6 +3607,7 @@ gimplify_parameters (void)
>> >    vec<tree> fnargs;
>> >    unsigned i;
>> >
>> > +  *stmts_after = NULL;
>> >    assign_parms_initialize_all (&all);
>> >    fnargs = assign_parms_augmented_arg_list (&all);
>> >
>> > @@ -3690,6 +3692,17 @@ gimplify_parameters (void)
>> >               DECL_HAS_VALUE_EXPR_P (parm) = 1;
>> >             }
>> >         }
>> > +      if (POINTER_TYPE_P (TREE_TYPE (parm))
>> > +         && TYPE_RESTRICT (TREE_TYPE (parm))
>> > +         && !DECL_HAS_VALUE_EXPR_P (parm))
>> > +       {
>> > +         tree t = fold_build2 (ADD_RESTRICT, TREE_TYPE (parm), parm,
>> > +                               build_int_cst (integer_type_node,
>> > +                                              allocate_decl_uid ()));
>> > +         gimplify_assign (parm, t, &stmts);
>> > +         gimple g = gimple_build_call_internal (IFN_DEL_RESTRICT, 1, parm);
>> > +         gimple_seq_add_stmt (stmts_after, g);
>> > +       }
>> >      }
>> >
>> >    fnargs.release ();
>> > Index: function.h
>> > ===================================================================
>> > --- function.h  (revision 205123)
>> > +++ function.h  (working copy)
>> > @@ -841,6 +841,6 @@ extern void preserve_temp_slots (rtx);
>> >  extern int aggregate_value_p (const_tree, const_tree);
>> >  extern void push_function_context (void);
>> >  extern void pop_function_context (void);
>> > -extern gimple_seq gimplify_parameters (void);
>> > +extern gimple_seq gimplify_parameters (gimple_seq *);
>> >
>> >  #endif  /* GCC_FUNCTION_H */
>> > Index: gimple-pretty-print.c
>> > ===================================================================
>> > --- gimple-pretty-print.c       (revision 205123)
>> > +++ gimple-pretty-print.c       (working copy)
>> > @@ -348,6 +348,7 @@ dump_binary_rhs (pretty_printer *buffer,
>> >      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_WIDEN_MULT_EVEN_EXPR:
>> > Index: gimplify.c
>> > ===================================================================
>> > --- gimplify.c  (revision 205123)
>> > +++ gimplify.c  (working copy)
>> > @@ -1005,8 +1005,9 @@ gimplify_bind_expr (tree *expr_p, gimple
>> >           && !DECL_HARD_REGISTER (t)
>> >           && !TREE_THIS_VOLATILE (t)
>> >           && !DECL_HAS_VALUE_EXPR_P (t)
>> > -         /* Only care for variables that have to be in memory.  Others
>> > -            will be rewritten into SSA names, hence moved to the top-level.  */
>> > +         /* Only care for variables that have to be in memory.
>> > +            Others will be rewritten into SSA names, hence moved
>> > +            to the top-level.  */
>> >           && !is_gimple_reg (t)
>> >           && flag_stack_reuse != SR_NONE)
>> >         {
>> > @@ -8356,7 +8357,7 @@ gimple
>> >  gimplify_body (tree fndecl, bool do_parms)
>> >  {
>> >    location_t saved_location = input_location;
>> > -  gimple_seq parm_stmts, seq;
>> > +  gimple_seq parm_stmts, parm_stmts_after, seq;
>> >    gimple outer_bind;
>> >    struct gimplify_ctx gctx;
>> >    struct cgraph_node *cgn;
>> > @@ -8393,7 +8394,8 @@ gimplify_body (tree fndecl, bool do_parm
>> >
>> >    /* Resolve callee-copies.  This has to be done before processing
>> >       the body so that DECL_VALUE_EXPR gets processed correctly.  */
>> > -  parm_stmts = do_parms ? gimplify_parameters () : NULL;
>> > +  parm_stmts_after = NULL;
>> > +  parm_stmts = do_parms ? gimplify_parameters (&parm_stmts_after) : NULL;
>> >
>> >    /* Gimplify the function's body.  */
>> >    seq = NULL;
>> > @@ -8432,6 +8434,10 @@ gimplify_body (tree fndecl, bool do_parm
>> >             DECL_IGNORED_P (parm) = 0;
>> >           }
>> >      }
>> > +  /* Same for statements that need to come after the body.  */
>> > +  if (!gimple_seq_empty_p (parm_stmts_after))
>> > +    gimplify_seq_add_seq (gimple_bind_body_ptr (outer_bind),
>> > +                         parm_stmts_after);
>> >
>> >    if (nonlocal_vlas)
>> >      {
>> > Index: internal-fn.c
>> > ===================================================================
>> > --- internal-fn.c       (revision 205123)
>> > +++ internal-fn.c       (working copy)
>> > @@ -148,6 +148,16 @@ expand_UBSAN_NULL (gimple stmt ATTRIBUTE
>> >    gcc_unreachable ();
>> >  }
>> >
>> > +/* Expand the DEL_RESTRICT internal function into a RTL
>> > +   asm that merely clobbers memory reachable via the pointer.  */
>> > +
>> > +static void
>> > +expand_DEL_RESTRICT (gimple stmt)
>> > +{
>> > +  tree ptr = gimple_call_arg (stmt, 0);
>> > +  expand_pointer_clobber (ptr, gimple_location (stmt));
>> > +}
>> > +
>> >  /* Routines to expand each internal function, indexed by function number.
>> >     Each routine has the prototype:
>> >
>> > Index: internal-fn.def
>> > ===================================================================
>> > --- internal-fn.def     (revision 205123)
>> > +++ internal-fn.def     (working copy)
>> > @@ -45,3 +45,4 @@ DEF_INTERNAL_FN (GOMP_SIMD_VF, ECF_CONST
>> >  DEF_INTERNAL_FN (GOMP_SIMD_LAST_LANE, ECF_CONST | ECF_LEAF | ECF_NOTHROW)
>> >  DEF_INTERNAL_FN (ANNOTATE,  ECF_CONST | ECF_LEAF | ECF_NOTHROW)
>> >  DEF_INTERNAL_FN (UBSAN_NULL, ECF_LEAF | ECF_NOTHROW)
>> > +DEF_INTERNAL_FN (DEL_RESTRICT,  /*ECF_LEAF |*/ ECF_NOTHROW)
>> > Index: tree-cfg.c
>> > ===================================================================
>> > --- tree-cfg.c  (revision 205123)
>> > +++ tree-cfg.c  (working copy)
>> > @@ -3627,6 +3627,21 @@ verify_gimple_assign_binary (gimple stmt
>> >         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:
>> > Index: tree-inline.c
>> > ===================================================================
>> > --- tree-inline.c       (revision 205123)
>> > +++ tree-inline.c       (working copy)
>> > @@ -3580,6 +3580,7 @@ estimate_operator_cost (enum tree_code c
>> >      case COMPLEX_EXPR:
>> >      case PAREN_EXPR:
>> >      case VIEW_CONVERT_EXPR:
>> > +    case ADD_RESTRICT:
>> >        return 0;
>> >
>> >      /* Assign cost of 1 to usual operations.
>> > Index: tree-pretty-print.c
>> > ===================================================================
>> > --- tree-pretty-print.c (revision 205123)
>> > +++ tree-pretty-print.c (working copy)
>> > @@ -1927,6 +1927,14 @@ dump_generic_node (pretty_printer *buffe
>> >        pp_greater (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: tree-ssa-dce.c
>> > ===================================================================
>> > --- tree-ssa-dce.c      (revision 205123)
>> > +++ tree-ssa-dce.c      (working copy)
>> > @@ -828,6 +828,10 @@ propagate_necessity (bool aggressive)
>> >                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
>> >                 continue;
>> >
>> > +             if (gimple_call_internal_p (stmt)
>> > +                 && gimple_call_internal_fn (stmt) == IFN_DEL_RESTRICT)
>> > +               continue;
>> > +
>> >               /* Calls implicitly load from memory, their arguments
>> >                  in addition may explicitly perform memory loads.  */
>> >               mark_all_reaching_defs_necessary (stmt);
>> > Index: tree-ssa-structalias.c
>> > ===================================================================
>> > --- tree-ssa-structalias.c      (revision 205123)
>> > +++ tree-ssa-structalias.c      (working copy)
>> > @@ -3741,31 +3741,43 @@ make_transitive_closure_constraints (var
>> >  /* Temporary storage for fake var decls.  */
>> >  struct obstack fake_var_decl_obstack;
>> >
>> > -/* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
>> > +/* 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 (tree type)
>> > +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) = allocate_decl_uid ();
>> > +  DECL_UID (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.  */
>> > +/* 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)
>> > +make_heapvar (const char *name, int uid)
>> >  {
>> >    varinfo_t vi;
>> >    tree heapvar;
>> >
>> > -  heapvar = build_fake_var_decl (ptr_type_node);
>> > +  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);
>> > @@ -3781,22 +3793,34 @@ make_heapvar (const char *name)
>> >    return vi;
>> >  }
>> >
>> > -/* Create a new artificial heap variable with NAME and make a
>> > +/* 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 varinfo_t
>> > -make_constraint_from_restrict (varinfo_t lhs, const char *name)
>> > +make_constraint_from_restrict_uid (varinfo_t lhs, const char *name, int uid)
>> >  {
>> > -  varinfo_t vi = make_heapvar (name);
>> > -  vi->is_global_var = 1;
>> > -  vi->may_have_pointers = 1;
>> > +  varinfo_t vi;
>> > +  vi = make_heapvar (name, uid);
>> >    make_constraint_from (lhs, vi->id);
>> > +  vi->is_global_var = 0;
>> > +  /*vi->is_special_var = 1;*/
>> > +  vi->may_have_pointers = 1;
>> >    return vi;
>> >  }
>> >
>> >  /* Create a new artificial heap variable with NAME and make a
>> >     constraint from it to LHS.  Set flags according to a tag used
>> > +   for tracking restrict pointers.  */
>> > +
>> > +static varinfo_t
>> > +make_constraint_from_restrict (varinfo_t lhs, const char *name)
>> > +{
>> > +  return make_constraint_from_restrict_uid (lhs, name, -1);
>> > +}
>> > +
>> > +/* Create a new artificial heap variable with NAME and make a
>> > +   constraint from it to LHS.  Set flags according to a tag used
>> >     for tracking restrict pointers and make the artificial heap
>> >     point to global memory.  */
>> >
>> > @@ -3804,6 +3828,7 @@ static varinfo_t
>> >  make_constraint_from_global_restrict (varinfo_t lhs, const char *name)
>> >  {
>> >    varinfo_t vi = make_constraint_from_restrict (lhs, name);
>> > +  vi->is_global_var = 1;
>> >    make_copy_constraint (vi, nonlocal_id);
>> >    return vi;
>> >  }
>> > @@ -3999,7 +4024,7 @@ handle_lhs_call (gimple stmt, tree lhs,
>> >        varinfo_t vi;
>> >        struct constraint_expr tmpc;
>> >        rhsc.create (0);
>> > -      vi = make_heapvar ("HEAP");
>> > +      vi = make_heapvar ("HEAP", -1);
>> >        /* We marking allocated storage local, we deal with it becoming
>> >           global by escaping and setting of vars_contains_escaped_heap.  */
>> >        DECL_EXTERNAL (vi->decl) = 0;
>> > @@ -4490,6 +4515,28 @@ find_func_aliases_for_builtin_call (gimp
>> >    return false;
>> >  }
>> >
>> > +/* Create constraints for the internal call T.  Return true if the call
>> > +   was handled, otherwise false.  */
>> > +
>> > +static bool
>> > +find_func_aliases_for_internal_call (gimple t)
>> > +{
>> > +  switch (gimple_call_internal_fn (t))
>> > +    {
>> > +    case IFN_DEL_RESTRICT:
>> > +      {
>> > +       /* DEL_RESTRICT is a barrier for what its argument points to.  */
>> > +       tree ptr = gimple_call_arg (t, 0);
>> > +       make_constraint_to (get_call_clobber_vi (t)->id, ptr);
>> > +       return true;
>> > +      }
>> > +
>> > +    default:
>> > +      /* Fallthru to general call handling.  */;
>> > +    }
>> > +  return false;
>> > +}
>> > +
>> >  /* Create constraints for the call T.  */
>> >
>> >  static void
>> > @@ -4505,6 +4552,10 @@ find_func_aliases_for_call (gimple t)
>> >        && find_func_aliases_for_builtin_call (t))
>> >      return;
>> >
>> > +  if (gimple_call_internal_p (t)
>> > +      && find_func_aliases_for_internal_call (t))
>> > +    return;
>> > +
>> >    fi = get_fi_for_callee (t);
>> >    if (!in_ipa_mode
>> >        || (fndecl && !fi->is_fn_info))
>> > @@ -4715,6 +4766,16 @@ find_func_aliases (gimple origt)
>> >             /* Truth value results are not pointer (parts).  Or at least
>> >                very very unreasonable obfuscation of a part.  */
>> >             ;
>> > +         else if (gimple_assign_rhs_code (t) == ADD_RESTRICT)
>> > +           {
>> > +             /* Add the specified restrict tag and merge from
>> > +                the incoming pointer.  */
>> > +             make_constraint_from_restrict_uid (get_vi_for_tree (lhsop),
>> > +                                                "RESTRICT_TAG",
>> > +                                                TREE_INT_CST_LOW
>> > +                                                  (gimple_assign_rhs2 (t)));
>> > +             get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
>> > +           }
>> >           else
>> >             {
>> >               /* All other operations are merges.  */
>> > @@ -5852,50 +5913,10 @@ intra_create_variable_infos (void)
>> >      {
>> >        varinfo_t p = get_vi_for_tree (t);
>> >
>> > -      /* For restrict qualified pointers to objects passed by
>> > -         reference build a real representative for the pointed-to object.
>> > -        Treat restrict qualified references the same.  */
>> > -      if (TYPE_RESTRICT (TREE_TYPE (t))
>> > -         && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
>> > -             || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
>> > -         && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
>> > -       {
>> > -         struct constraint_expr lhsc, rhsc;
>> > -         varinfo_t vi;
>> > -         tree heapvar = build_fake_var_decl (TREE_TYPE (TREE_TYPE (t)));
>> > -         DECL_EXTERNAL (heapvar) = 1;
>> > -         vi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS");
>> > -         insert_vi_for_tree (heapvar, vi);
>> > -         lhsc.var = p->id;
>> > -         lhsc.type = SCALAR;
>> > -         lhsc.offset = 0;
>> > -         rhsc.var = vi->id;
>> > -         rhsc.type = ADDRESSOF;
>> > -         rhsc.offset = 0;
>> > -         process_constraint (new_constraint (lhsc, rhsc));
>> > -         for (; vi; vi = vi_next (vi))
>> > -           if (vi->may_have_pointers)
>> > -             {
>> > -               if (vi->only_restrict_pointers)
>> > -                 make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
>> > -               else
>> > -                 make_copy_constraint (vi, nonlocal_id);
>> > -             }
>> > -         continue;
>> > -       }
>> > -
>> > -      if (POINTER_TYPE_P (TREE_TYPE (t))
>> > -         && TYPE_RESTRICT (TREE_TYPE (t)))
>> > -       make_constraint_from_global_restrict (p, "PARM_RESTRICT");
>> > -      else
>> > +      for (; p; p = vi_next (p))
>> >         {
>> > -         for (; p; p = vi_next (p))
>> > -           {
>> > -             if (p->only_restrict_pointers)
>> > -               make_constraint_from_global_restrict (p, "PARM_RESTRICT");
>> > -             else if (p->may_have_pointers)
>> > -               make_constraint_from (p, nonlocal_id);
>> > -           }
>> > +         if (p->may_have_pointers)
>> > +           make_constraint_from (p, nonlocal_id);
>> >         }
>> >      }
>> >
>> > @@ -6022,7 +6043,7 @@ set_uids_in_ptset (bitmap into, bitmap f
>> >               && bitmap_bit_p (escaped_vi->solution, i)))
>> >         {
>> >           pt->vars_contains_escaped = true;
>> > -         pt->vars_contains_escaped_heap = vi->is_heap_var;
>> > +         pt->vars_contains_escaped_heap |= vi->is_heap_var;
>> >         }
>> >
>> >        if (TREE_CODE (vi->decl) == VAR_DECL
>> > @@ -6045,10 +6066,10 @@ set_uids_in_ptset (bitmap into, bitmap f
>> >  }
>> >
>> >
>> > -/* Compute the points-to solution *PT for the variable VI.  */
>> > +/* Compute the points-to solution *PT for the variable VI, part one.  */
>> >
>> >  static struct pt_solution
>> > -find_what_var_points_to (varinfo_t orig_vi)
>> > +find_what_var_points_to_1 (varinfo_t orig_vi)
>> >  {
>> >    unsigned int i;
>> >    bitmap_iterator bi;
>> > @@ -6096,7 +6117,7 @@ find_what_var_points_to (varinfo_t orig_
>> >             /* Nobody cares.  */
>> >             ;
>> >           else if (vi->id == anything_id
>> > -                  || vi->id == integer_id)
>> > +                   || vi->id == integer_id)
>> >             pt->anything = 1;
>> >         }
>> >      }
>> > @@ -6126,6 +6147,71 @@ find_what_var_points_to (varinfo_t orig_
>> >    return *pt;
>> >  }
>> >
>> > +/* Compute the points-to solution *PT for the variable VI, part two.
>> > +   This modifies the points-to solution to cater for restrict pointers.
>> > +
>> > +   Restrict is modelled as a may-be restrict problem together with
>> > +   a must-be restrict problem.  From the must-be restrict solution we
>> > +   can later deduce non-aliasing (if the points-to sets don't intersect
>> > +   the two references can't alias).  The may-be restrict problem provides
>> > +   a sort of conservative cap for that such that a pointer p1 that is even
>> > +   remotely related to a restrict pointer r2 points to a superset of what
>> > +   p1 points to.  In particular we want to handle this situation:
>> > +
>> > +      1 int * restrict p1 = ...;
>> > +      2 temp = p1;
>> > +      3 int * restrict p2;
>> > +      4 p2 = temp;
>> > +
>> > +      Suppose that 'temp' is address taken, so (2) is a store and
>> > +      (4) a load.  We want to make sure that p1 and p2 are tagged
>> > +      the same (remember we're not handling just the C language
>> > +      definition of restrict).  To ensure this we need to look through
>> > +      memory (and even handle second level effects, like when a restrict
>> > +      pointer is stored into a global variable).
>> > +
>> > +   That's why we use the points-to solver for the may-be restrict problem
>> > +   (which handles memory conservatively correct).  The must-be restrict
>> > +   part then is formulated as a post-processing on the conservatively
>> > +   correct points-to solution.  For a set of variables their solution
>> > +   is pruned.  This pruned solution is returned here.  */
>> > +
>> > +static struct pt_solution
>> > +find_what_var_points_to (varinfo_t vi)
>> > +{
>> > +  struct pt_solution pt;
>> > +
>> > +  pt = find_what_var_points_to_1 (vi);
>> > +
>> > +  if (vi->decl && TREE_CODE (vi->decl) == SSA_NAME)
>> > +    {
>> > +      gimple g = SSA_NAME_DEF_STMT (vi->decl);
>> > +      if (g && is_gimple_assign (g)
>> > +         && gimple_assign_rhs_code (g) == ADD_RESTRICT)
>> > +       {
>> > +         /* Restrict pointers only point to their tags.  For now
>> > +            we leave also the other decls in the points-to set:
>> > +            changing the set would imply possibly unsharing the bitmap,
>> > +            and furthermore it's actually good to have precise
>> > +            decls in there in some cases, e.g. if it's local variables.
>> > +
>> > +            In effect this means removing the nonlocal flags.  To
>> > +            not regard stores via such pointers as inherently useless
>> > +            we need to set the vars_contains_escaped_heap flag, if the
>> > +            input contained some nonlocals.  */
>> > +         if (pt.vars_contains_nonlocal
>> > +             || pt.nonlocal
>> > +             || pt.vars_contains_escaped)
>> > +           pt.vars_contains_escaped_heap = 1;
>> > +         pt.nonlocal = 0;
>> > +         pt.vars_contains_escaped = 0;
>> > +         pt.vars_contains_nonlocal = 0;
>> > +       }
>> > +    }
>> > +
>> > +  return pt;
>> > +}
>> > +
>> >  /* Given a pointer variable P, fill in its points-to set.  */
>> >
>> >  static void
>> > @@ -6866,10 +6952,14 @@ compute_points_to_sets (void)
>> >               *pt = find_what_var_points_to (vi);
>> >               /* Escaped (and thus nonlocal) variables are always
>> >                  implicitly used by calls.  */
>> > -             /* ???  ESCAPED can be empty even though NONLOCAL
>> > -                always escaped.  */
>> > -             pt->nonlocal = 1;
>> > -             pt->escaped = 1;
>> > +             if (!gimple_call_internal_p (stmt)
>> > +                 || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
>> > +               {
>> > +                 /* ???  ESCAPED can be empty even though NONLOCAL
>> > +                    always escaped.  */
>> > +                 pt->nonlocal = 1;
>> > +                 pt->escaped = 1;
>> > +               }
>> >             }
>> >           else
>> >             {
>> > @@ -6887,10 +6977,14 @@ compute_points_to_sets (void)
>> >               *pt = find_what_var_points_to (vi);
>> >               /* Escaped (and thus nonlocal) variables are always
>> >                  implicitly clobbered by calls.  */
>> > -             /* ???  ESCAPED can be empty even though NONLOCAL
>> > -                always escaped.  */
>> > -             pt->nonlocal = 1;
>> > -             pt->escaped = 1;
>> > +             if (!gimple_call_internal_p (stmt)
>> > +                 || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
>> > +               {
>> > +                 /* ???  ESCAPED can be empty even though NONLOCAL
>> > +                    always escaped.  */
>> > +                 pt->nonlocal = 1;
>> > +                 pt->escaped = 1;
>> > +               }
>> >             }
>> >           else
>> >             {
>> > Index: tree.def
>> > ===================================================================
>> > --- tree.def    (revision 205123)
>> > +++ tree.def    (working copy)
>> > @@ -977,6 +977,8 @@ DEFTREECODE (WITH_SIZE_EXPR, "with_size_
>> >     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),
>>
>>
>
> --
> Richard Biener <rguenther@suse.de>
> SUSE / SUSE Labs
> SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
> GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer
Tobias Burnus - Nov. 22, 2013, 9:40 p.m.
Michael Matz wrote:
> after much pondering about the issue we came up with this design to
> handle restrict more generally.

Cool! Thanks for the last-minute patch.

If I understand the patch correctly, it does handle the problem of 
inlining restrict pointers correctly – which was previously a 
missed-optimization. (Both for Fortran but also for C/C++ with 
__restrict__, e.g. PR58526)


However, I do not quite see whether it also handles Fortran's derived 
types correctly; namely the problem where a derived type has, e.g., an 
allocatable component (= restrict pointer) but where the type is then 
used for a variable with target attribute, which turns also the type's 
components into nonrestrict pointers. That's the infamous PR45586.

My possibly wrong impression is that it doesn't yet fix that issue, but 
that it paves the way to doing so. Am I correct?


> --- internal-fn.def	(revision 205123)
> +++ internal-fn.def	(working copy)

> +DEF_INTERNAL_FN (DEL_RESTRICT,  /*ECF_LEAF |*/ ECF_NOTHROW)

PR 58723, I'd guess ;-)
(ICE due to internal_fn ending up into the cgraph.)

Tobias
Richard Guenther - Nov. 25, 2013, 2 p.m.
On Thu, 21 Nov 2013, Michael Matz wrote:

> Hello,
> 
> after much pondering about the issue we came up with this design to 
> handle restrict more generally.  Without a completely different way of 
> representing conflicts (or non-conflicts) of memory references we're bound 
> to somehow encode the necessary information into the points-to set (or in 
> any case information related to pointer ssa names).  This in turn means 
> that the location sensitive nature of restrict needs to be made explicit 
> in the IL, i.e. we basically need some starting point when a pointer 
> becomes restrict (ADD_RESTRICT), and also an ending point (DEL_RESTRICT), 
> which must act as barrier for other memory accesses (if it wouldn't some 
> transformations could move references from outside restrict regions into 
> the restrict region making them disasmbiguable with the restrict 
> references, introducing a bug).

As far as naming goes DEL_RESTRICT is somewhat confusing and I'd prefer
__builtin_memory_barrier (void *p) which acts as a memory barrier
for all _objects_ pointed to by p ("objects" as in p may point at
and one after memory blocks covered by declarations and dynamic
memory allocation).

> We also need to use our points-to solver to propagate restrict tags 
> conservatively, postprocessing the information to remove too conservative 
> estimates afterwards per SSA name.

An other way to say this is that we need both conservative propagation for
may-restrict and conservative propagation for must-restrict to be able
to disambiguate accesses via restrict vs. accesses via non-restrict 
qualified pointers.

> And if we want to use restrict based disambiguation we also need to 
> transfer the barriers into RTL barriers (I'm using an asm with an explicit 
> MEM to refer to the pointer in question, so not all memory is clobbered).
> There's some potential for improvement here by removing useless 
> ADD_RESTRICT / DEL_RESTRICT pairs.
> 
> There's another improvement when enlargening the set of SSA names to be 
> considered for postprocessin.  Right now only the result of ADD_RESTRICT 
> assigns are handled, that can be improved to also process SSA names that 
> trivial depend on such (i.e. are offsetted and themself restrict typed).
> 
> That facility is used to implement restrict parameters to functions, 
> replacing the current ad-hoc way in the points-to solver.  Other uses 
> should be done under control of the frontends, as only those know the 
> semantics for real.
> 
> I have a patch that more aggressively creates ADD_RESTRICT/DEL_RESTRICT 
> pairs (basically whenever there's an assignment from non-restrict pointers 
> to a restrict pointer, on the grounds that this "invents" a new restrict 
> set), but that breaks C programs that we don't want to break (I consider 
> them invalid, but there's disagreement).
> 
> Some older incarnations of this were bootstrapped, but this specific patch 
> is only now in regstrapping on x86_64-linux.  Okay for trunk if that 
> passes?

I understand that this removes the "hacks" implemented for handling
Fortran array descriptors and thus the change has to be accompanied
by a change to the Fortran frontend to create its own ADD_RESTRICT
and barrier calls.

More comments inline (eventually).

> Ciao,
> Michael.
> ---------------------------
> 	* tree.def (ADD_RESTRICT): New tree code.
> 	* cfgexpand.c (expand_debug_expr): Handle it.
> 	* expr.c (expand_pointer_clobber): New function.
> 	(expand_expr_real_2): Use it to handle ADD_RESTRICT.
> 	* expr.h (expand_pointer_clobber): Declare.
> 	* function.c (gimplify_parameters): Return a second gimple_seq,
> 	handle restrict parameters.
> 	* function.h (gimplify_parameters): Adjust.
> 	* gimple-pretty-print.c (dump_binary_rhs): Handle ADD_RESTRICT.
> 	* gimplify.c (gimplify_body): Append second gimple_seq,
> 	adjust call to gimplify_parameters.
> 	* internal-fn.def (DEL_RESTRICT): New internal function code.
> 	* internal-fn.c (expand_DEL_RESTRICT): New function.
> 	* tree-cfg.c (verify_gimple_assign_binary): Check ADD_RESTRICT.
> 	* tree-inline.c (estimate_operator_cost): Handle ADD_RESTRICT.
> 	* tree-pretty-print.c (dump_generic_node): Ditto.
> 	* tree-ssa-dce.c (propagate_necessity): DEL_RESTRICT calls
> 	are only clobbers.
> 	* tree-ssa-structalias.c (build_fake_var_decl_uid): New static
> 	function.
> 	(build_fake_var_decl): Rewrite in terms of above.
> 	(make_heapvar): Take uid parameter.
> 	(make_constraint_from_restrict_uid): New.
> 	(make_constraint_from_restrict): Use above.
> 	(make_constraint_from_global_restrict): Explicitely set global flag.
> 	(handle_lhs_call): Adjust call to make_heapvar.
> 	(find_func_aliases_for_internal_call): New.
> 	(find_func_aliases_for_call): Use it.
> 	(find_func_aliases): Handle ADD_RESTRICT.
> 	(intra_create_variable_infos): Remove any explicit handling
> 	of restrict parameters.
> 	(set_uids_in_ptset): Update instead of overwrite 
> 	vars_contains_escaped_heap flag.
> 	(find_what_var_points_to_1): Renamed from ...
> 	(find_what_var_points_to): ... this, which is now wrapper
> 	postprocessing points-to flags.
> 	(compute_points_to_sets): Ignore DEL_RESTRICT calls.
> 
> Index: cfgexpand.c
> ===================================================================
> --- cfgexpand.c	(revision 205123)
> +++ cfgexpand.c	(working copy)
> @@ -3785,6 +3785,7 @@ expand_debug_expr (tree exp)
>        /* Fall through.  */
>  
>      adjust_mode:
> +    case ADD_RESTRICT:
>      case PAREN_EXPR:
>      case NOP_EXPR:
>      case CONVERT_EXPR:
> Index: expr.c
> ===================================================================
> --- expr.c	(revision 205123)
> +++ expr.c	(working copy)
> @@ -7988,6 +7988,41 @@ expand_cond_expr_using_cmove (tree treeo
>    return NULL_RTX;
>  }
>  
> +/* Given a memory pointer PTR, expand an RTL asm statement
> +   that merely clobbers memory reachable from that pointer
> +   via arbitrary offsets.  */
> +
> +void
> +expand_pointer_clobber (tree ptr, location_t loc)

With introducing __builtin_memory_barrier this can be renamed
to expand_memory_barrier (), "pointer clobber" sounds like if it
clobbers the pointer.

> +{
> +  tree ref = build_simple_mem_ref (ptr);
> +  rtx op = expand_expr (ref, NULL_RTX, BLKmode, EXPAND_MEMORY);
> +  rtx body;
> +
> +  op = validize_mem (op);

I'd even go that far to expand 'ptr', legitimize its address
and build a MEM yourself here, ...

> +  /* There's no way to construct a tree expression doing exactly what
> +     we need (representing a reference to arbitrarily memory reachable
> +     from a given pointer, i.e. with arbitrary offsets.  Hence
> +     construct that by massaging the MEM attributes.  */
> +  clear_mem_offset (op);
> +  clear_mem_size (op);
> +  PUT_MODE (op, BLKmode);

... setting mem-attrs properly instead of clearing parts of them
afterwards.

> +  rtvec argvec = rtvec_alloc (0);
> +  rtvec constraintvec = rtvec_alloc (0);
> +  rtvec labelvec = rtvec_alloc (0);
> +
> +  body = gen_rtx_ASM_OPERANDS (BLKmode,
> +			       ggc_strdup (""),
> +			       ggc_strdup ("=m"), 0, argvec, constraintvec,
> +			       labelvec, loc);
> +
> +  MEM_VOLATILE_P (body) = 1;
> +
> +  emit_insn (gen_rtx_SET (VOIDmode, op, body));
> +}
> +
>  rtx
>  expand_expr_real_2 (sepops ops, rtx target, enum machine_mode tmode,
>  		    enum expand_modifier modifier)
> @@ -8047,6 +8082,13 @@ expand_expr_real_2 (sepops ops, rtx targ
>  
>    switch (code)
>      {
> +    case ADD_RESTRICT:
> +      /* We can handle add_restrict like a conversion, treeop1 will be
> +         ignored.  But do create a barrier to contain the restrict
> +	 section.  */
> +      expand_pointer_clobber (treeop0, loc);
> +
> +      /* FALLTHRU.  */
>      case NON_LVALUE_EXPR:
>      case PAREN_EXPR:
>      CASE_CONVERT:
> Index: expr.h
> ===================================================================
> --- expr.h	(revision 205123)
> +++ expr.h	(working copy)
> @@ -719,6 +719,8 @@ extern rtx extract_low_bits (enum machin
>  extern rtx expand_mult (enum machine_mode, rtx, rtx, rtx, int);
>  extern rtx expand_mult_highpart_adjust (enum machine_mode, rtx, rtx, rtx, rtx, int);
>  
> +extern void expand_pointer_clobber (tree, location_t);
> +
>  extern rtx assemble_static_space (unsigned HOST_WIDE_INT);
>  extern int safe_from_p (const_rtx, tree, int);
>  extern bool split_comparison (enum rtx_code, enum machine_mode,
> Index: function.c
> ===================================================================
> --- function.c	(revision 205123)
> +++ function.c	(working copy)
> @@ -3595,10 +3595,11 @@ gimplify_parm_type (tree *tp, int *walk_
>  /* Gimplify the parameter list for current_function_decl.  This involves
>     evaluating SAVE_EXPRs of variable sized parameters and generating code
>     to implement callee-copies reference parameters.  Returns a sequence of
> -   statements to add to the beginning of the function.  */
> +   statements to add to the beginning of the function and another
> +   sequence to add to the end of the function (via *STMT_AFTER).  */
>  
>  gimple_seq
> -gimplify_parameters (void)
> +gimplify_parameters (gimple_seq *stmts_after)
>  {
>    struct assign_parm_data_all all;
>    tree parm;
> @@ -3606,6 +3607,7 @@ gimplify_parameters (void)
>    vec<tree> fnargs;
>    unsigned i;
>  
> +  *stmts_after = NULL;
>    assign_parms_initialize_all (&all);
>    fnargs = assign_parms_augmented_arg_list (&all);
>  
> @@ -3690,6 +3692,17 @@ gimplify_parameters (void)
>  	      DECL_HAS_VALUE_EXPR_P (parm) = 1;
>  	    }
>  	}
> +      if (POINTER_TYPE_P (TREE_TYPE (parm))
> +	  && TYPE_RESTRICT (TREE_TYPE (parm))
> +	  && !DECL_HAS_VALUE_EXPR_P (parm))

Thus not for restrict qualified args of nested functions?

> +	{
> +	  tree t = fold_build2 (ADD_RESTRICT, TREE_TYPE (parm), parm,
> +				build_int_cst (integer_type_node,
> +					       allocate_decl_uid ()));
> +	  gimplify_assign (parm, t, &stmts);
> +	  gimple g = gimple_build_call_internal (IFN_DEL_RESTRICT, 1, parm);
> +	  gimple_seq_add_stmt (stmts_after, g);
> +	}
>      }
>  
>    fnargs.release ();
> Index: function.h
> ===================================================================
> --- function.h	(revision 205123)
> +++ function.h	(working copy)
> @@ -841,6 +841,6 @@ extern void preserve_temp_slots (rtx);
>  extern int aggregate_value_p (const_tree, const_tree);
>  extern void push_function_context (void);
>  extern void pop_function_context (void);
> -extern gimple_seq gimplify_parameters (void);
> +extern gimple_seq gimplify_parameters (gimple_seq *);
>  
>  #endif  /* GCC_FUNCTION_H */
> Index: gimple-pretty-print.c
> ===================================================================
> --- gimple-pretty-print.c	(revision 205123)
> +++ gimple-pretty-print.c	(working copy)
> @@ -348,6 +348,7 @@ dump_binary_rhs (pretty_printer *buffer,
>      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_WIDEN_MULT_EVEN_EXPR:
> Index: gimplify.c
> ===================================================================
> --- gimplify.c	(revision 205123)
> +++ gimplify.c	(working copy)
> @@ -1005,8 +1005,9 @@ gimplify_bind_expr (tree *expr_p, gimple
>  	  && !DECL_HARD_REGISTER (t)
>  	  && !TREE_THIS_VOLATILE (t)
>  	  && !DECL_HAS_VALUE_EXPR_P (t)
> -	  /* Only care for variables that have to be in memory.  Others
> -	     will be rewritten into SSA names, hence moved to the top-level.  */
> +	  /* Only care for variables that have to be in memory.
> +	     Others will be rewritten into SSA names, hence moved
> +	     to the top-level.  */

spurious change.

>  	  && !is_gimple_reg (t)
>  	  && flag_stack_reuse != SR_NONE)
>  	{
> @@ -8356,7 +8357,7 @@ gimple
>  gimplify_body (tree fndecl, bool do_parms)
>  {
>    location_t saved_location = input_location;
> -  gimple_seq parm_stmts, seq;
> +  gimple_seq parm_stmts, parm_stmts_after, seq;
>    gimple outer_bind;
>    struct gimplify_ctx gctx;
>    struct cgraph_node *cgn;
> @@ -8393,7 +8394,8 @@ gimplify_body (tree fndecl, bool do_parm
>  
>    /* Resolve callee-copies.  This has to be done before processing
>       the body so that DECL_VALUE_EXPR gets processed correctly.  */
> -  parm_stmts = do_parms ? gimplify_parameters () : NULL;
> +  parm_stmts_after = NULL;
> +  parm_stmts = do_parms ? gimplify_parameters (&parm_stmts_after) : NULL;
>  
>    /* Gimplify the function's body.  */
>    seq = NULL;
> @@ -8432,6 +8434,10 @@ gimplify_body (tree fndecl, bool do_parm
>  	    DECL_IGNORED_P (parm) = 0;
>  	  }
>      }
> +  /* Same for statements that need to come after the body.  */
> +  if (!gimple_seq_empty_p (parm_stmts_after))
> +    gimplify_seq_add_seq (gimple_bind_body_ptr (outer_bind),
> +			  parm_stmts_after);

I don't really like adding ADD_RESTRICT in the gimplifier ... we've
shortly discussed retaining the current restrict parameter handling
in PTA and just fix shortcomings of the current handling in selected
frontends (Fortran) as well as during inlining itself (note: we don't
really need to assign restrict tags upfront due to the use of barriers
which became inevitable)

>    if (nonlocal_vlas)
>      {
> Index: internal-fn.c
> ===================================================================
> --- internal-fn.c	(revision 205123)
> +++ internal-fn.c	(working copy)
> @@ -148,6 +148,16 @@ expand_UBSAN_NULL (gimple stmt ATTRIBUTE
>    gcc_unreachable ();
>  }
>  
> +/* Expand the DEL_RESTRICT internal function into a RTL
> +   asm that merely clobbers memory reachable via the pointer.  */
> +
> +static void
> +expand_DEL_RESTRICT (gimple stmt)
> +{
> +  tree ptr = gimple_call_arg (stmt, 0);
> +  expand_pointer_clobber (ptr, gimple_location (stmt));
> +}
> +
>  /* Routines to expand each internal function, indexed by function number.
>     Each routine has the prototype:
>  
> Index: internal-fn.def
> ===================================================================
> --- internal-fn.def	(revision 205123)
> +++ internal-fn.def	(working copy)
> @@ -45,3 +45,4 @@ DEF_INTERNAL_FN (GOMP_SIMD_VF, ECF_CONST
>  DEF_INTERNAL_FN (GOMP_SIMD_LAST_LANE, ECF_CONST | ECF_LEAF | ECF_NOTHROW)
>  DEF_INTERNAL_FN (ANNOTATE,  ECF_CONST | ECF_LEAF | ECF_NOTHROW)
>  DEF_INTERNAL_FN (UBSAN_NULL, ECF_LEAF | ECF_NOTHROW)
> +DEF_INTERNAL_FN (DEL_RESTRICT,  /*ECF_LEAF |*/ ECF_NOTHROW)
> Index: tree-cfg.c
> ===================================================================
> --- tree-cfg.c	(revision 205123)
> +++ tree-cfg.c	(working copy)
> @@ -3627,6 +3627,21 @@ verify_gimple_assign_binary (gimple stmt
>  	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:
> Index: tree-inline.c
> ===================================================================
> --- tree-inline.c	(revision 205123)
> +++ tree-inline.c	(working copy)
> @@ -3580,6 +3580,7 @@ estimate_operator_cost (enum tree_code c
>      case COMPLEX_EXPR:
>      case PAREN_EXPR:
>      case VIEW_CONVERT_EXPR:
> +    case ADD_RESTRICT:
>        return 0;
>  
>      /* Assign cost of 1 to usual operations.

I suppose you want to add DEL_RESTRICT to is_simple_builtin
(or better add is_simple_internal_fn and handle internal fns properly
in estimate_num_insns).

> Index: tree-pretty-print.c
> ===================================================================
> --- tree-pretty-print.c	(revision 205123)
> +++ tree-pretty-print.c	(working copy)
> @@ -1927,6 +1927,14 @@ dump_generic_node (pretty_printer *buffe
>        pp_greater (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: tree-ssa-dce.c
> ===================================================================
> --- tree-ssa-dce.c	(revision 205123)
> +++ tree-ssa-dce.c	(working copy)
> @@ -828,6 +828,10 @@ propagate_necessity (bool aggressive)
>  		      || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
>  		continue;
>  
> +	      if (gimple_call_internal_p (stmt)
> +		  && gimple_call_internal_fn (stmt) == IFN_DEL_RESTRICT)
> +		continue;
> +
>  	      /* Calls implicitly load from memory, their arguments
>  	         in addition may explicitly perform memory loads.  */
>  	      mark_all_reaching_defs_necessary (stmt);
> Index: tree-ssa-structalias.c
> ===================================================================
> --- tree-ssa-structalias.c	(revision 205123)
> +++ tree-ssa-structalias.c	(working copy)
> @@ -3741,31 +3741,43 @@ make_transitive_closure_constraints (var
>  /* Temporary storage for fake var decls.  */
>  struct obstack fake_var_decl_obstack;
>  
> -/* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
> +/* 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 (tree type)
> +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) = allocate_decl_uid ();
> +  DECL_UID (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.  */
> +/* 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)
> +make_heapvar (const char *name, int uid)
>  {
>    varinfo_t vi;
>    tree heapvar;
>    
> -  heapvar = build_fake_var_decl (ptr_type_node);
> +  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);
> @@ -3781,22 +3793,34 @@ make_heapvar (const char *name)
>    return vi;
>  }
>  
> -/* Create a new artificial heap variable with NAME and make a
> +/* 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 varinfo_t
> -make_constraint_from_restrict (varinfo_t lhs, const char *name)
> +make_constraint_from_restrict_uid (varinfo_t lhs, const char *name, int uid)
>  {
> -  varinfo_t vi = make_heapvar (name);
> -  vi->is_global_var = 1;
> -  vi->may_have_pointers = 1;
> +  varinfo_t vi;
> +  vi = make_heapvar (name, uid);
>    make_constraint_from (lhs, vi->id);
> +  vi->is_global_var = 0;
> +  /*vi->is_special_var = 1;*/
> +  vi->may_have_pointers = 1;
>    return vi;
>  }
>  
>  /* Create a new artificial heap variable with NAME and make a
>     constraint from it to LHS.  Set flags according to a tag used
> +   for tracking restrict pointers.  */
> +
> +static varinfo_t
> +make_constraint_from_restrict (varinfo_t lhs, const char *name)
> +{
> +  return make_constraint_from_restrict_uid (lhs, name, -1);
> +}
> +
> +/* Create a new artificial heap variable with NAME and make a
> +   constraint from it to LHS.  Set flags according to a tag used
>     for tracking restrict pointers and make the artificial heap
>     point to global memory.  */
>  
> @@ -3804,6 +3828,7 @@ static varinfo_t
>  make_constraint_from_global_restrict (varinfo_t lhs, const char *name)
>  {
>    varinfo_t vi = make_constraint_from_restrict (lhs, name);
> +  vi->is_global_var = 1;
>    make_copy_constraint (vi, nonlocal_id);
>    return vi;
>  }
> @@ -3999,7 +4024,7 @@ handle_lhs_call (gimple stmt, tree lhs,
>        varinfo_t vi;
>        struct constraint_expr tmpc;
>        rhsc.create (0);
> -      vi = make_heapvar ("HEAP");
> +      vi = make_heapvar ("HEAP", -1);
>        /* We marking allocated storage local, we deal with it becoming
>           global by escaping and setting of vars_contains_escaped_heap.  */
>        DECL_EXTERNAL (vi->decl) = 0;
> @@ -4490,6 +4515,28 @@ find_func_aliases_for_builtin_call (gimp
>    return false;
>  }
>  
> +/* Create constraints for the internal call T.  Return true if the call
> +   was handled, otherwise false.  */
> +
> +static bool
> +find_func_aliases_for_internal_call (gimple t)
> +{
> +  switch (gimple_call_internal_fn (t))
> +    {
> +    case IFN_DEL_RESTRICT:
> +      {
> +	/* DEL_RESTRICT is a barrier for what its argument points to.  */
> +	tree ptr = gimple_call_arg (t, 0);
> +	make_constraint_to (get_call_clobber_vi (t)->id, ptr);
> +	return true;
> +      }
> +
> +    default:
> +      /* Fallthru to general call handling.  */;
> +    }
> +  return false;
> +}
> + 
>  /* Create constraints for the call T.  */
>  
>  static void
> @@ -4505,6 +4552,10 @@ find_func_aliases_for_call (gimple t)
>        && find_func_aliases_for_builtin_call (t))
>      return;
>  
> +  if (gimple_call_internal_p (t)
> +      && find_func_aliases_for_internal_call (t))
> +    return;
> +
>    fi = get_fi_for_callee (t);
>    if (!in_ipa_mode
>        || (fndecl && !fi->is_fn_info))
> @@ -4715,6 +4766,16 @@ find_func_aliases (gimple origt)
>  	    /* Truth value results are not pointer (parts).  Or at least
>  	       very very unreasonable obfuscation of a part.  */
>  	    ;
> +	  else if (gimple_assign_rhs_code (t) == ADD_RESTRICT)
> +	    {
> +	      /* Add the specified restrict tag and merge from
> +	         the incoming pointer.  */
> +	      make_constraint_from_restrict_uid (get_vi_for_tree (lhsop),
> +						 "RESTRICT_TAG",
> +						 TREE_INT_CST_LOW
> +						   (gimple_assign_rhs2 (t)));
> +	      get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
> +	    }
>  	  else
>  	    {
>  	      /* All other operations are merges.  */
> @@ -5852,50 +5913,10 @@ intra_create_variable_infos (void)
>      {
>        varinfo_t p = get_vi_for_tree (t);
>  
> -      /* For restrict qualified pointers to objects passed by
> -         reference build a real representative for the pointed-to object.
> -	 Treat restrict qualified references the same.  */
> -      if (TYPE_RESTRICT (TREE_TYPE (t))
> -	  && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
> -	      || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
> -	  && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
> -	{
> -	  struct constraint_expr lhsc, rhsc;
> -	  varinfo_t vi;
> -	  tree heapvar = build_fake_var_decl (TREE_TYPE (TREE_TYPE (t)));
> -	  DECL_EXTERNAL (heapvar) = 1;
> -	  vi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS");
> -	  insert_vi_for_tree (heapvar, vi);
> -	  lhsc.var = p->id;
> -	  lhsc.type = SCALAR;
> -	  lhsc.offset = 0;
> -	  rhsc.var = vi->id;
> -	  rhsc.type = ADDRESSOF;
> -	  rhsc.offset = 0;
> -	  process_constraint (new_constraint (lhsc, rhsc));
> -	  for (; vi; vi = vi_next (vi))
> -	    if (vi->may_have_pointers)
> -	      {
> -		if (vi->only_restrict_pointers)
> -		  make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
> -		else
> -		  make_copy_constraint (vi, nonlocal_id);
> -	      }
> -	  continue;
> -	}
> -
> -      if (POINTER_TYPE_P (TREE_TYPE (t))
> -	  && TYPE_RESTRICT (TREE_TYPE (t)))
> -	make_constraint_from_global_restrict (p, "PARM_RESTRICT");
> -      else
> +      for (; p; p = vi_next (p))
>  	{
> -	  for (; p; p = vi_next (p))
> -	    {
> -	      if (p->only_restrict_pointers)
> -		make_constraint_from_global_restrict (p, "PARM_RESTRICT");
> -	      else if (p->may_have_pointers)
> -		make_constraint_from (p, nonlocal_id);
> -	    }
> +	  if (p->may_have_pointers)
> +	    make_constraint_from (p, nonlocal_id);
>  	}

So retain the above code.

>      }
>  
> @@ -6022,7 +6043,7 @@ set_uids_in_ptset (bitmap into, bitmap f
>  	      && bitmap_bit_p (escaped_vi->solution, i)))
>  	{
>  	  pt->vars_contains_escaped = true;
> -	  pt->vars_contains_escaped_heap = vi->is_heap_var;
> +	  pt->vars_contains_escaped_heap |= vi->is_heap_var;
>  	}

why that?

>        if (TREE_CODE (vi->decl) == VAR_DECL
> @@ -6045,10 +6066,10 @@ set_uids_in_ptset (bitmap into, bitmap f
>  }
>  
>  
> -/* Compute the points-to solution *PT for the variable VI.  */
> +/* Compute the points-to solution *PT for the variable VI, part one.  */
>  
>  static struct pt_solution
> -find_what_var_points_to (varinfo_t orig_vi)
> +find_what_var_points_to_1 (varinfo_t orig_vi)
>  {
>    unsigned int i;
>    bitmap_iterator bi;
> @@ -6096,7 +6117,7 @@ find_what_var_points_to (varinfo_t orig_
>  	    /* Nobody cares.  */
>  	    ;
>  	  else if (vi->id == anything_id
> -		   || vi->id == integer_id)
> +		    || vi->id == integer_id)
>  	    pt->anything = 1;
>  	}
>      }

Spurious change

> @@ -6126,6 +6147,71 @@ find_what_var_points_to (varinfo_t orig_
>    return *pt;
>  }
>  
> +/* Compute the points-to solution *PT for the variable VI, part two.
> +   This modifies the points-to solution to cater for restrict pointers.
> +   
> +   Restrict is modelled as a may-be restrict problem together with
> +   a must-be restrict problem.  From the must-be restrict solution we
> +   can later deduce non-aliasing (if the points-to sets don't intersect
> +   the two references can't alias).  The may-be restrict problem provides
> +   a sort of conservative cap for that such that a pointer p1 that is even
> +   remotely related to a restrict pointer r2 points to a superset of what
> +   p1 points to.  In particular we want to handle this situation:
> +
> +      1 int * restrict p1 = ...;
> +      2 temp = p1;
> +      3 int * restrict p2;
> +      4 p2 = temp;
> +
> +      Suppose that 'temp' is address taken, so (2) is a store and
> +      (4) a load.  We want to make sure that p1 and p2 are tagged
> +      the same (remember we're not handling just the C language
> +      definition of restrict).  To ensure this we need to look through
> +      memory (and even handle second level effects, like when a restrict
> +      pointer is stored into a global variable).
> +
> +   That's why we use the points-to solver for the may-be restrict problem
> +   (which handles memory conservatively correct).  The must-be restrict
> +   part then is formulated as a post-processing on the conservatively
> +   correct points-to solution.  For a set of variables their solution
> +   is pruned.  This pruned solution is returned here.  */
> +
> +static struct pt_solution
> +find_what_var_points_to (varinfo_t vi)
> +{
> +  struct pt_solution pt;
> +
> +  pt = find_what_var_points_to_1 (vi);
> +
> +  if (vi->decl && TREE_CODE (vi->decl) == SSA_NAME)
> +    {
> +      gimple g = SSA_NAME_DEF_STMT (vi->decl);
> +      if (g && is_gimple_assign (g)
> +	  && gimple_assign_rhs_code (g) == ADD_RESTRICT)
> +	{
> +	  /* Restrict pointers only point to their tags.  For now
> +	     we leave also the other decls in the points-to set:
> +	     changing the set would imply possibly unsharing the bitmap,
> +	     and furthermore it's actually good to have precise
> +	     decls in there in some cases, e.g. if it's local variables.
> +
> +	     In effect this means removing the nonlocal flags.  To
> +	     not regard stores via such pointers as inherently useless
> +	     we need to set the vars_contains_escaped_heap flag, if the
> +	     input contained some nonlocals.  */
> +	  if (pt.vars_contains_nonlocal
> +	      || pt.nonlocal
> +	      || pt.vars_contains_escaped)
> +	    pt.vars_contains_escaped_heap = 1;
> +	  pt.nonlocal = 0;
> +	  pt.vars_contains_escaped = 0;
> +	  pt.vars_contains_nonlocal = 0;
> +	}
> +    }
> +
> +  return pt;
> +}
> +
>  /* Given a pointer variable P, fill in its points-to set.  */
>  
>  static void
> @@ -6866,10 +6952,14 @@ compute_points_to_sets (void)
>  	      *pt = find_what_var_points_to (vi);
>  	      /* Escaped (and thus nonlocal) variables are always
>  	         implicitly used by calls.  */
> -	      /* ???  ESCAPED can be empty even though NONLOCAL
> -		 always escaped.  */
> -	      pt->nonlocal = 1;
> -	      pt->escaped = 1;
> +	      if (!gimple_call_internal_p (stmt)
> +		  || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
> +		{
> +		  /* ???  ESCAPED can be empty even though NONLOCAL
> +		     always escaped.  */
> +		  pt->nonlocal = 1;
> +		  pt->escaped = 1;
> +		}
>  	    }
>  	  else
>  	    {
> @@ -6887,10 +6977,14 @@ compute_points_to_sets (void)
>  	      *pt = find_what_var_points_to (vi);
>  	      /* Escaped (and thus nonlocal) variables are always
>  	         implicitly clobbered by calls.  */
> -	      /* ???  ESCAPED can be empty even though NONLOCAL
> -		 always escaped.  */
> -	      pt->nonlocal = 1;
> -	      pt->escaped = 1;
> +	      if (!gimple_call_internal_p (stmt)
> +		  || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
> +		{
> +		  /* ???  ESCAPED can be empty even though NONLOCAL
> +		     always escaped.  */
> +		  pt->nonlocal = 1;
> +		  pt->escaped = 1;
> +		}
>  	    }
>  	  else
>  	    {
> Index: tree.def
> ===================================================================
> --- tree.def	(revision 205123)
> +++ tree.def	(working copy)
> @@ -977,6 +977,8 @@ DEFTREECODE (WITH_SIZE_EXPR, "with_size_
>     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),


Otherwise the patch looks sensible to me.

Thanks,
Richard.
Richard Guenther - Nov. 25, 2013, 2:08 p.m.
On Fri, 22 Nov 2013, Xinliang David Li wrote:

> On Fri, Nov 22, 2013 at 2:19 AM, Richard Biener <rguenther@suse.de> wrote:
> > On Thu, 21 Nov 2013, Xinliang David Li wrote:
> >
> >> On Thu, Nov 21, 2013 at 10:03 AM, Michael Matz <matz@suse.de> wrote:
> >> > Hello,
> >> >
> >> > after much pondering about the issue we came up with this design to
> >> > handle restrict more generally.  Without a completely different way of
> >> > representing conflicts (or non-conflicts) of memory references we're bound
> >> > to somehow encode the necessary information into the points-to set (or in
> >> > any case information related to pointer ssa names).  This in turn means
> >> > that the location sensitive nature of restrict needs to be made explicit
> >> > in the IL, i.e. we basically need some starting point when a pointer
> >> > becomes restrict (ADD_RESTRICT), and also an ending point (DEL_RESTRICT),
> >> > which must act as barrier for other memory accesses (if it wouldn't some
> >> > transformations could move references from outside restrict regions into
> >> > the restrict region making them disasmbiguable with the restrict
> >> > references, introducing a bug).
> >> >
> >>
> >> Can you use block/scope information to address this ? References from
> >> enclosing scopes can be considered possible aliases.
> >
> > Apart from the issue that LTO drops all BLOCKs this makes the middle-end
> > feature too much tied to the C family frontends and their definition
> > of restrict.  It also requires BLOCK lookup / matching at the time
> > of the alias query (which generally deals with "refs" which may
> > end up not refering to any BLOCK or to different BLOCKs than the
> > GIMPLE they are used in).
> 
> Can the aliaser capture the scope info and maintain its own minimal
> block tree? Each ref will have a unique scope id.  Code duplication
> transformations need to propagate info properly.

Well, certainly.  You would need an additional place to refer to
the scope id from a GIMPLE stmt (or the tree memory reference).

> >
> > It also suddenly makes having (correct) BLOCK info cause code generation
> > differences.
> 
> Is it an issue if it is not affected by with -g is specified or not?

Too many negates for me in this sentence.  To re-iterate, -g and -g0
need to create the same code.  Also stmts may get BLOCKs assigned
that they don't really belong to (harmless now, fatal after using
BLOCKs for disambiguation).

> >
> > That said, you would somehow need to remember the BLOCK a restrict
> > "tag" is live in which doesn't make it a good fit for the current
> > alias-info we associate with SSA names.  If you don't allow
> > disambiguations against refs in nested BLOCKs then a single
> > "tag" decl with its associated BLOCK is enough to remember
> > (thus one additional pointer).
> >
> > But well - I always wondered how other compilers implement support
> > for restrict (and how restricted that support is, and how strictly
> > following the standard).
> >
> > The only other scheme I can come up with is to allow non-dependences
> > to be recorded and maintained throughout the compilation and have
> > frontends create them.
> 
> It has been a while, but I recall one compiler does similar things --
> pretty early in the middle end before blocks are stripped, per-scope
> pointer analysis/tracking is done for scopes with restrict pointer
> uses. When that is done, alias pairs that can be disambiguated are
> recorded, and this information is maintained throughout (including
> inline tranformation).

Yeah, that's probably the best method - the issue is reliably
maintaining the information.  And of course doing the analysis itself
on a IL that might not be best suited for the analysis.

At some point we should think about adding a facility to maintain
non-alias info as that would also speed up repeated queries and
allows more costly analysis done (and not repeated).

Thanks,
Richard.
Michael Matz - Nov. 25, 2013, 2:19 p.m.
Hi,

On Fri, 22 Nov 2013, Xinliang David Li wrote:

> > Apart from the issue that LTO drops all BLOCKs this makes the middle-end
> > feature too much tied to the C family frontends and their definition
> > of restrict.  It also requires BLOCK lookup / matching at the time
> > of the alias query (which generally deals with "refs" which may
> > end up not refering to any BLOCK or to different BLOCKs than the
> > GIMPLE they are used in).
> 
> Can the aliaser capture the scope info and maintain its own minimal
> block tree?

It could (somewhen in the future).  A BLOCK based scheme (in the 
middle-end) still wouldn't allow implementing restrict-like semantics of 
other languages, though.  I think that's really a dead end, apart of all 
the practical problems with it right now.

> > The only other scheme I can come up with is to allow non-dependences 
> > to be recorded and maintained throughout the compilation and have 
> > frontends create them.
> 
> It has been a while, but I recall one compiler does similar things -- 
> pretty early in the middle end before blocks are stripped, per-scope 
> pointer analysis/tracking is done for scopes with restrict pointer uses. 
> When that is done, alias pairs that can be disambiguated are recorded, 
> and this information is maintained throughout (including inline 
> tranformation).

Yeah, that's something we should try to implement for the next GCC 
version.  It's really the more natural way to express the whole problem.


Ciao,
Michael.

Patch

Index: cfgexpand.c
===================================================================
--- cfgexpand.c	(revision 205123)
+++ cfgexpand.c	(working copy)
@@ -3785,6 +3785,7 @@  expand_debug_expr (tree exp)
       /* Fall through.  */
 
     adjust_mode:
+    case ADD_RESTRICT:
     case PAREN_EXPR:
     case NOP_EXPR:
     case CONVERT_EXPR:
Index: expr.c
===================================================================
--- expr.c	(revision 205123)
+++ expr.c	(working copy)
@@ -7988,6 +7988,41 @@  expand_cond_expr_using_cmove (tree treeo
   return NULL_RTX;
 }
 
+/* Given a memory pointer PTR, expand an RTL asm statement
+   that merely clobbers memory reachable from that pointer
+   via arbitrary offsets.  */
+
+void
+expand_pointer_clobber (tree ptr, location_t loc)
+{
+  tree ref = build_simple_mem_ref (ptr);
+  rtx op = expand_expr (ref, NULL_RTX, BLKmode, EXPAND_MEMORY);
+  rtx body;
+
+  op = validize_mem (op);
+
+  /* There's no way to construct a tree expression doing exactly what
+     we need (representing a reference to arbitrarily memory reachable
+     from a given pointer, i.e. with arbitrary offsets.  Hence
+     construct that by massaging the MEM attributes.  */
+  clear_mem_offset (op);
+  clear_mem_size (op);
+  PUT_MODE (op, BLKmode);
+
+  rtvec argvec = rtvec_alloc (0);
+  rtvec constraintvec = rtvec_alloc (0);
+  rtvec labelvec = rtvec_alloc (0);
+
+  body = gen_rtx_ASM_OPERANDS (BLKmode,
+			       ggc_strdup (""),
+			       ggc_strdup ("=m"), 0, argvec, constraintvec,
+			       labelvec, loc);
+
+  MEM_VOLATILE_P (body) = 1;
+
+  emit_insn (gen_rtx_SET (VOIDmode, op, body));
+}
+
 rtx
 expand_expr_real_2 (sepops ops, rtx target, enum machine_mode tmode,
 		    enum expand_modifier modifier)
@@ -8047,6 +8082,13 @@  expand_expr_real_2 (sepops ops, rtx targ
 
   switch (code)
     {
+    case ADD_RESTRICT:
+      /* We can handle add_restrict like a conversion, treeop1 will be
+         ignored.  But do create a barrier to contain the restrict
+	 section.  */
+      expand_pointer_clobber (treeop0, loc);
+
+      /* FALLTHRU.  */
     case NON_LVALUE_EXPR:
     case PAREN_EXPR:
     CASE_CONVERT:
Index: expr.h
===================================================================
--- expr.h	(revision 205123)
+++ expr.h	(working copy)
@@ -719,6 +719,8 @@  extern rtx extract_low_bits (enum machin
 extern rtx expand_mult (enum machine_mode, rtx, rtx, rtx, int);
 extern rtx expand_mult_highpart_adjust (enum machine_mode, rtx, rtx, rtx, rtx, int);
 
+extern void expand_pointer_clobber (tree, location_t);
+
 extern rtx assemble_static_space (unsigned HOST_WIDE_INT);
 extern int safe_from_p (const_rtx, tree, int);
 extern bool split_comparison (enum rtx_code, enum machine_mode,
Index: function.c
===================================================================
--- function.c	(revision 205123)
+++ function.c	(working copy)
@@ -3595,10 +3595,11 @@  gimplify_parm_type (tree *tp, int *walk_
 /* Gimplify the parameter list for current_function_decl.  This involves
    evaluating SAVE_EXPRs of variable sized parameters and generating code
    to implement callee-copies reference parameters.  Returns a sequence of
-   statements to add to the beginning of the function.  */
+   statements to add to the beginning of the function and another
+   sequence to add to the end of the function (via *STMT_AFTER).  */
 
 gimple_seq
-gimplify_parameters (void)
+gimplify_parameters (gimple_seq *stmts_after)
 {
   struct assign_parm_data_all all;
   tree parm;
@@ -3606,6 +3607,7 @@  gimplify_parameters (void)
   vec<tree> fnargs;
   unsigned i;
 
+  *stmts_after = NULL;
   assign_parms_initialize_all (&all);
   fnargs = assign_parms_augmented_arg_list (&all);
 
@@ -3690,6 +3692,17 @@  gimplify_parameters (void)
 	      DECL_HAS_VALUE_EXPR_P (parm) = 1;
 	    }
 	}
+      if (POINTER_TYPE_P (TREE_TYPE (parm))
+	  && TYPE_RESTRICT (TREE_TYPE (parm))
+	  && !DECL_HAS_VALUE_EXPR_P (parm))
+	{
+	  tree t = fold_build2 (ADD_RESTRICT, TREE_TYPE (parm), parm,
+				build_int_cst (integer_type_node,
+					       allocate_decl_uid ()));
+	  gimplify_assign (parm, t, &stmts);
+	  gimple g = gimple_build_call_internal (IFN_DEL_RESTRICT, 1, parm);
+	  gimple_seq_add_stmt (stmts_after, g);
+	}
     }
 
   fnargs.release ();
Index: function.h
===================================================================
--- function.h	(revision 205123)
+++ function.h	(working copy)
@@ -841,6 +841,6 @@  extern void preserve_temp_slots (rtx);
 extern int aggregate_value_p (const_tree, const_tree);
 extern void push_function_context (void);
 extern void pop_function_context (void);
-extern gimple_seq gimplify_parameters (void);
+extern gimple_seq gimplify_parameters (gimple_seq *);
 
 #endif  /* GCC_FUNCTION_H */
Index: gimple-pretty-print.c
===================================================================
--- gimple-pretty-print.c	(revision 205123)
+++ gimple-pretty-print.c	(working copy)
@@ -348,6 +348,7 @@  dump_binary_rhs (pretty_printer *buffer,
     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_WIDEN_MULT_EVEN_EXPR:
Index: gimplify.c
===================================================================
--- gimplify.c	(revision 205123)
+++ gimplify.c	(working copy)
@@ -1005,8 +1005,9 @@  gimplify_bind_expr (tree *expr_p, gimple
 	  && !DECL_HARD_REGISTER (t)
 	  && !TREE_THIS_VOLATILE (t)
 	  && !DECL_HAS_VALUE_EXPR_P (t)
-	  /* Only care for variables that have to be in memory.  Others
-	     will be rewritten into SSA names, hence moved to the top-level.  */
+	  /* Only care for variables that have to be in memory.
+	     Others will be rewritten into SSA names, hence moved
+	     to the top-level.  */
 	  && !is_gimple_reg (t)
 	  && flag_stack_reuse != SR_NONE)
 	{
@@ -8356,7 +8357,7 @@  gimple
 gimplify_body (tree fndecl, bool do_parms)
 {
   location_t saved_location = input_location;
-  gimple_seq parm_stmts, seq;
+  gimple_seq parm_stmts, parm_stmts_after, seq;
   gimple outer_bind;
   struct gimplify_ctx gctx;
   struct cgraph_node *cgn;
@@ -8393,7 +8394,8 @@  gimplify_body (tree fndecl, bool do_parm
 
   /* Resolve callee-copies.  This has to be done before processing
      the body so that DECL_VALUE_EXPR gets processed correctly.  */
-  parm_stmts = do_parms ? gimplify_parameters () : NULL;
+  parm_stmts_after = NULL;
+  parm_stmts = do_parms ? gimplify_parameters (&parm_stmts_after) : NULL;
 
   /* Gimplify the function's body.  */
   seq = NULL;
@@ -8432,6 +8434,10 @@  gimplify_body (tree fndecl, bool do_parm
 	    DECL_IGNORED_P (parm) = 0;
 	  }
     }
+  /* Same for statements that need to come after the body.  */
+  if (!gimple_seq_empty_p (parm_stmts_after))
+    gimplify_seq_add_seq (gimple_bind_body_ptr (outer_bind),
+			  parm_stmts_after);
 
   if (nonlocal_vlas)
     {
Index: internal-fn.c
===================================================================
--- internal-fn.c	(revision 205123)
+++ internal-fn.c	(working copy)
@@ -148,6 +148,16 @@  expand_UBSAN_NULL (gimple stmt ATTRIBUTE
   gcc_unreachable ();
 }
 
+/* Expand the DEL_RESTRICT internal function into a RTL
+   asm that merely clobbers memory reachable via the pointer.  */
+
+static void
+expand_DEL_RESTRICT (gimple stmt)
+{
+  tree ptr = gimple_call_arg (stmt, 0);
+  expand_pointer_clobber (ptr, gimple_location (stmt));
+}
+
 /* Routines to expand each internal function, indexed by function number.
    Each routine has the prototype:
 
Index: internal-fn.def
===================================================================
--- internal-fn.def	(revision 205123)
+++ internal-fn.def	(working copy)
@@ -45,3 +45,4 @@  DEF_INTERNAL_FN (GOMP_SIMD_VF, ECF_CONST
 DEF_INTERNAL_FN (GOMP_SIMD_LAST_LANE, ECF_CONST | ECF_LEAF | ECF_NOTHROW)
 DEF_INTERNAL_FN (ANNOTATE,  ECF_CONST | ECF_LEAF | ECF_NOTHROW)
 DEF_INTERNAL_FN (UBSAN_NULL, ECF_LEAF | ECF_NOTHROW)
+DEF_INTERNAL_FN (DEL_RESTRICT,  /*ECF_LEAF |*/ ECF_NOTHROW)
Index: tree-cfg.c
===================================================================
--- tree-cfg.c	(revision 205123)
+++ tree-cfg.c	(working copy)
@@ -3627,6 +3627,21 @@  verify_gimple_assign_binary (gimple stmt
 	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:
Index: tree-inline.c
===================================================================
--- tree-inline.c	(revision 205123)
+++ tree-inline.c	(working copy)
@@ -3580,6 +3580,7 @@  estimate_operator_cost (enum tree_code c
     case COMPLEX_EXPR:
     case PAREN_EXPR:
     case VIEW_CONVERT_EXPR:
+    case ADD_RESTRICT:
       return 0;
 
     /* Assign cost of 1 to usual operations.
Index: tree-pretty-print.c
===================================================================
--- tree-pretty-print.c	(revision 205123)
+++ tree-pretty-print.c	(working copy)
@@ -1927,6 +1927,14 @@  dump_generic_node (pretty_printer *buffe
       pp_greater (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: tree-ssa-dce.c
===================================================================
--- tree-ssa-dce.c	(revision 205123)
+++ tree-ssa-dce.c	(working copy)
@@ -828,6 +828,10 @@  propagate_necessity (bool aggressive)
 		      || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
 		continue;
 
+	      if (gimple_call_internal_p (stmt)
+		  && gimple_call_internal_fn (stmt) == IFN_DEL_RESTRICT)
+		continue;
+
 	      /* Calls implicitly load from memory, their arguments
 	         in addition may explicitly perform memory loads.  */
 	      mark_all_reaching_defs_necessary (stmt);
Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c	(revision 205123)
+++ tree-ssa-structalias.c	(working copy)
@@ -3741,31 +3741,43 @@  make_transitive_closure_constraints (var
 /* Temporary storage for fake var decls.  */
 struct obstack fake_var_decl_obstack;
 
-/* Build a fake VAR_DECL acting as referrer to a DECL_UID.  */
+/* 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 (tree type)
+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) = allocate_decl_uid ();
+  DECL_UID (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.  */
+/* 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)
+make_heapvar (const char *name, int uid)
 {
   varinfo_t vi;
   tree heapvar;
   
-  heapvar = build_fake_var_decl (ptr_type_node);
+  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);
@@ -3781,22 +3793,34 @@  make_heapvar (const char *name)
   return vi;
 }
 
-/* Create a new artificial heap variable with NAME and make a
+/* 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 varinfo_t
-make_constraint_from_restrict (varinfo_t lhs, const char *name)
+make_constraint_from_restrict_uid (varinfo_t lhs, const char *name, int uid)
 {
-  varinfo_t vi = make_heapvar (name);
-  vi->is_global_var = 1;
-  vi->may_have_pointers = 1;
+  varinfo_t vi;
+  vi = make_heapvar (name, uid);
   make_constraint_from (lhs, vi->id);
+  vi->is_global_var = 0;
+  /*vi->is_special_var = 1;*/
+  vi->may_have_pointers = 1;
   return vi;
 }
 
 /* Create a new artificial heap variable with NAME and make a
    constraint from it to LHS.  Set flags according to a tag used
+   for tracking restrict pointers.  */
+
+static varinfo_t
+make_constraint_from_restrict (varinfo_t lhs, const char *name)
+{
+  return make_constraint_from_restrict_uid (lhs, name, -1);
+}
+
+/* Create a new artificial heap variable with NAME and make a
+   constraint from it to LHS.  Set flags according to a tag used
    for tracking restrict pointers and make the artificial heap
    point to global memory.  */
 
@@ -3804,6 +3828,7 @@  static varinfo_t
 make_constraint_from_global_restrict (varinfo_t lhs, const char *name)
 {
   varinfo_t vi = make_constraint_from_restrict (lhs, name);
+  vi->is_global_var = 1;
   make_copy_constraint (vi, nonlocal_id);
   return vi;
 }
@@ -3999,7 +4024,7 @@  handle_lhs_call (gimple stmt, tree lhs,
       varinfo_t vi;
       struct constraint_expr tmpc;
       rhsc.create (0);
-      vi = make_heapvar ("HEAP");
+      vi = make_heapvar ("HEAP", -1);
       /* We marking allocated storage local, we deal with it becoming
          global by escaping and setting of vars_contains_escaped_heap.  */
       DECL_EXTERNAL (vi->decl) = 0;
@@ -4490,6 +4515,28 @@  find_func_aliases_for_builtin_call (gimp
   return false;
 }
 
+/* Create constraints for the internal call T.  Return true if the call
+   was handled, otherwise false.  */
+
+static bool
+find_func_aliases_for_internal_call (gimple t)
+{
+  switch (gimple_call_internal_fn (t))
+    {
+    case IFN_DEL_RESTRICT:
+      {
+	/* DEL_RESTRICT is a barrier for what its argument points to.  */
+	tree ptr = gimple_call_arg (t, 0);
+	make_constraint_to (get_call_clobber_vi (t)->id, ptr);
+	return true;
+      }
+
+    default:
+      /* Fallthru to general call handling.  */;
+    }
+  return false;
+}
+ 
 /* Create constraints for the call T.  */
 
 static void
@@ -4505,6 +4552,10 @@  find_func_aliases_for_call (gimple t)
       && find_func_aliases_for_builtin_call (t))
     return;
 
+  if (gimple_call_internal_p (t)
+      && find_func_aliases_for_internal_call (t))
+    return;
+
   fi = get_fi_for_callee (t);
   if (!in_ipa_mode
       || (fndecl && !fi->is_fn_info))
@@ -4715,6 +4766,16 @@  find_func_aliases (gimple origt)
 	    /* Truth value results are not pointer (parts).  Or at least
 	       very very unreasonable obfuscation of a part.  */
 	    ;
+	  else if (gimple_assign_rhs_code (t) == ADD_RESTRICT)
+	    {
+	      /* Add the specified restrict tag and merge from
+	         the incoming pointer.  */
+	      make_constraint_from_restrict_uid (get_vi_for_tree (lhsop),
+						 "RESTRICT_TAG",
+						 TREE_INT_CST_LOW
+						   (gimple_assign_rhs2 (t)));
+	      get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc);
+	    }
 	  else
 	    {
 	      /* All other operations are merges.  */
@@ -5852,50 +5913,10 @@  intra_create_variable_infos (void)
     {
       varinfo_t p = get_vi_for_tree (t);
 
-      /* For restrict qualified pointers to objects passed by
-         reference build a real representative for the pointed-to object.
-	 Treat restrict qualified references the same.  */
-      if (TYPE_RESTRICT (TREE_TYPE (t))
-	  && ((DECL_BY_REFERENCE (t) && POINTER_TYPE_P (TREE_TYPE (t)))
-	      || TREE_CODE (TREE_TYPE (t)) == REFERENCE_TYPE)
-	  && !type_contains_placeholder_p (TREE_TYPE (TREE_TYPE (t))))
-	{
-	  struct constraint_expr lhsc, rhsc;
-	  varinfo_t vi;
-	  tree heapvar = build_fake_var_decl (TREE_TYPE (TREE_TYPE (t)));
-	  DECL_EXTERNAL (heapvar) = 1;
-	  vi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS");
-	  insert_vi_for_tree (heapvar, vi);
-	  lhsc.var = p->id;
-	  lhsc.type = SCALAR;
-	  lhsc.offset = 0;
-	  rhsc.var = vi->id;
-	  rhsc.type = ADDRESSOF;
-	  rhsc.offset = 0;
-	  process_constraint (new_constraint (lhsc, rhsc));
-	  for (; vi; vi = vi_next (vi))
-	    if (vi->may_have_pointers)
-	      {
-		if (vi->only_restrict_pointers)
-		  make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT");
-		else
-		  make_copy_constraint (vi, nonlocal_id);
-	      }
-	  continue;
-	}
-
-      if (POINTER_TYPE_P (TREE_TYPE (t))
-	  && TYPE_RESTRICT (TREE_TYPE (t)))
-	make_constraint_from_global_restrict (p, "PARM_RESTRICT");
-      else
+      for (; p; p = vi_next (p))
 	{
-	  for (; p; p = vi_next (p))
-	    {
-	      if (p->only_restrict_pointers)
-		make_constraint_from_global_restrict (p, "PARM_RESTRICT");
-	      else if (p->may_have_pointers)
-		make_constraint_from (p, nonlocal_id);
-	    }
+	  if (p->may_have_pointers)
+	    make_constraint_from (p, nonlocal_id);
 	}
     }
 
@@ -6022,7 +6043,7 @@  set_uids_in_ptset (bitmap into, bitmap f
 	      && bitmap_bit_p (escaped_vi->solution, i)))
 	{
 	  pt->vars_contains_escaped = true;
-	  pt->vars_contains_escaped_heap = vi->is_heap_var;
+	  pt->vars_contains_escaped_heap |= vi->is_heap_var;
 	}
 
       if (TREE_CODE (vi->decl) == VAR_DECL
@@ -6045,10 +6066,10 @@  set_uids_in_ptset (bitmap into, bitmap f
 }
 
 
-/* Compute the points-to solution *PT for the variable VI.  */
+/* Compute the points-to solution *PT for the variable VI, part one.  */
 
 static struct pt_solution
-find_what_var_points_to (varinfo_t orig_vi)
+find_what_var_points_to_1 (varinfo_t orig_vi)
 {
   unsigned int i;
   bitmap_iterator bi;
@@ -6096,7 +6117,7 @@  find_what_var_points_to (varinfo_t orig_
 	    /* Nobody cares.  */
 	    ;
 	  else if (vi->id == anything_id
-		   || vi->id == integer_id)
+		    || vi->id == integer_id)
 	    pt->anything = 1;
 	}
     }
@@ -6126,6 +6147,71 @@  find_what_var_points_to (varinfo_t orig_
   return *pt;
 }
 
+/* Compute the points-to solution *PT for the variable VI, part two.
+   This modifies the points-to solution to cater for restrict pointers.
+   
+   Restrict is modelled as a may-be restrict problem together with
+   a must-be restrict problem.  From the must-be restrict solution we
+   can later deduce non-aliasing (if the points-to sets don't intersect
+   the two references can't alias).  The may-be restrict problem provides
+   a sort of conservative cap for that such that a pointer p1 that is even
+   remotely related to a restrict pointer r2 points to a superset of what
+   p1 points to.  In particular we want to handle this situation:
+
+      1 int * restrict p1 = ...;
+      2 temp = p1;
+      3 int * restrict p2;
+      4 p2 = temp;
+
+      Suppose that 'temp' is address taken, so (2) is a store and
+      (4) a load.  We want to make sure that p1 and p2 are tagged
+      the same (remember we're not handling just the C language
+      definition of restrict).  To ensure this we need to look through
+      memory (and even handle second level effects, like when a restrict
+      pointer is stored into a global variable).
+
+   That's why we use the points-to solver for the may-be restrict problem
+   (which handles memory conservatively correct).  The must-be restrict
+   part then is formulated as a post-processing on the conservatively
+   correct points-to solution.  For a set of variables their solution
+   is pruned.  This pruned solution is returned here.  */
+
+static struct pt_solution
+find_what_var_points_to (varinfo_t vi)
+{
+  struct pt_solution pt;
+
+  pt = find_what_var_points_to_1 (vi);
+
+  if (vi->decl && TREE_CODE (vi->decl) == SSA_NAME)
+    {
+      gimple g = SSA_NAME_DEF_STMT (vi->decl);
+      if (g && is_gimple_assign (g)
+	  && gimple_assign_rhs_code (g) == ADD_RESTRICT)
+	{
+	  /* Restrict pointers only point to their tags.  For now
+	     we leave also the other decls in the points-to set:
+	     changing the set would imply possibly unsharing the bitmap,
+	     and furthermore it's actually good to have precise
+	     decls in there in some cases, e.g. if it's local variables.
+
+	     In effect this means removing the nonlocal flags.  To
+	     not regard stores via such pointers as inherently useless
+	     we need to set the vars_contains_escaped_heap flag, if the
+	     input contained some nonlocals.  */
+	  if (pt.vars_contains_nonlocal
+	      || pt.nonlocal
+	      || pt.vars_contains_escaped)
+	    pt.vars_contains_escaped_heap = 1;
+	  pt.nonlocal = 0;
+	  pt.vars_contains_escaped = 0;
+	  pt.vars_contains_nonlocal = 0;
+	}
+    }
+
+  return pt;
+}
+
 /* Given a pointer variable P, fill in its points-to set.  */
 
 static void
@@ -6866,10 +6952,14 @@  compute_points_to_sets (void)
 	      *pt = find_what_var_points_to (vi);
 	      /* Escaped (and thus nonlocal) variables are always
 	         implicitly used by calls.  */
-	      /* ???  ESCAPED can be empty even though NONLOCAL
-		 always escaped.  */
-	      pt->nonlocal = 1;
-	      pt->escaped = 1;
+	      if (!gimple_call_internal_p (stmt)
+		  || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
+		{
+		  /* ???  ESCAPED can be empty even though NONLOCAL
+		     always escaped.  */
+		  pt->nonlocal = 1;
+		  pt->escaped = 1;
+		}
 	    }
 	  else
 	    {
@@ -6887,10 +6977,14 @@  compute_points_to_sets (void)
 	      *pt = find_what_var_points_to (vi);
 	      /* Escaped (and thus nonlocal) variables are always
 	         implicitly clobbered by calls.  */
-	      /* ???  ESCAPED can be empty even though NONLOCAL
-		 always escaped.  */
-	      pt->nonlocal = 1;
-	      pt->escaped = 1;
+	      if (!gimple_call_internal_p (stmt)
+		  || gimple_call_internal_fn (stmt) != IFN_DEL_RESTRICT)
+		{
+		  /* ???  ESCAPED can be empty even though NONLOCAL
+		     always escaped.  */
+		  pt->nonlocal = 1;
+		  pt->escaped = 1;
+		}
 	    }
 	  else
 	    {
Index: tree.def
===================================================================
--- tree.def	(revision 205123)
+++ tree.def	(working copy)
@@ -977,6 +977,8 @@  DEFTREECODE (WITH_SIZE_EXPR, "with_size_
    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),