| Message ID | alpine.LNX.2.00.1311211832370.11100@wotan.suse.de |
|---|---|
| State | New |
| Headers | show |
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),
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), > >
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
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
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.
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.
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.
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),