Overhaul middle-end handling of restrict

[Michael Matz <matz at suse dot de>]

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.

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),