points-to analysis is currently not able to disambiguate global
memory as-of function activation (aka 'nonlocal') against memory
that is allocated inside the function. This is because we glob
them together to make users of ptr_deref_may_alias_global_p
happy (an odd function which asks whether a store through a pointer
touches memory that survives returning from the function).
The following fixes that by tracking "escaped global memory"
separately.
This is also required to make the restrict stuff disambiguate
restrict vs. non-restrict parameters (if we want that).
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
Richard.
2013-11-15 Richard Biener <rguent...@suse.de>
PR tree-optimization/50262
* tree-ssa-alias.h (struct pt_solution): Split
vars_contains_global into vars_contains_nonlocal,
vars_contains_escaped and vars_contains_escaped_heap.
(label_visit): Expand comment.
(handle_lhs_call): Adjust comment.
(set_uids_in_ptset): Set the new flags appropriately.
(pt_solution_set): Adjust.
(pt_solution_set_var): Likewise.
(pt_solution_ior_into): Likewise.
(pt_solution_includes_global): Likewise.
(pt_solutions_intersect_1): Optimize escaped handling.
(compute_points_to_sets): Remove heap variable globalization.
(ipa_escaped_pt): Adjust initializer.
(pass_data_ipa_pta): Do not run TODO_update_ssa.
* gimple-pretty-print.c (pp_points_to_solution): Print split
flags.
* tree-ssa-alias.c (dump_points_to_solution): Likewise.
* gcc.dg/tree-ssa/alias-28.c: New testcase.
* gcc.dg/strlenopt-1.c: Adjust.
* gcc.dg/strlenopt-1f.c: Likewise.
Index: gcc/tree-ssa-alias.h
===================================================================
*** gcc/tree-ssa-alias.h.orig 2013-11-15 11:30:48.000000000 +0100
--- gcc/tree-ssa-alias.h 2013-11-15 11:39:05.605000787 +0100
*************** struct GTY(()) pt_solution
*** 48,56 ****
unsigned int null : 1;
! /* Nonzero if the pt_vars bitmap includes a global variable. */
! unsigned int vars_contains_global : 1;
!
/* Set of variables that this pointer may point to. */
bitmap vars;
--- 48,60 ----
unsigned int null : 1;
! /* Nonzero if the vars bitmap includes a variable included in 'nonlocal'.
*/
! unsigned int vars_contains_nonlocal : 1;
! /* Nonzero if the vars bitmap includes a variable included in 'escaped'. */
! unsigned int vars_contains_escaped : 1;
! /* Nonzero if the vars bitmap includes a anonymous heap variable that
! escaped the function and thus became global. */
! unsigned int vars_contains_escaped_heap : 1;
/* Set of variables that this pointer may point to. */
bitmap vars;
Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c.orig 2013-11-15 11:30:48.000000000 +0100
--- gcc/tree-ssa-structalias.c 2013-11-15 11:54:59.265926419 +0100
*************** condense_visit (constraint_graph_t graph
*** 2063,2069 ****
si->scc_stack.safe_push (n);
}
! /* Label pointer equivalences. */
static void
label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
--- 2063,2086 ----
si->scc_stack.safe_push (n);
}
! /* Label pointer equivalences.
!
! This performs a value numbering of the constraint graph to
! discover which variables will always have the same points-to sets
! under the current set of constraints.
!
! The way it value numbers is to store the set of points-to bits
! generated by the constraints and graph edges. This is just used as a
! hash and equality comparison. The *actual set of points-to bits* is
! completely irrelevant, in that we don't care about being able to
! extract them later.
!
! The equality values (currently bitmaps) just have to satisfy a few
! constraints, the main ones being:
! 1. The combining operation must be order independent.
! 2. The end result of a given set of operations must be unique iff the
! combination of input values is unique
! 3. Hashable. */
static void
label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
*************** handle_lhs_call (gimple stmt, tree lhs,
*** 3979,3986 ****
struct constraint_expr tmpc;
rhsc.create (0);
vi = make_heapvar ("HEAP");
! /* We delay marking allocated storage global until we know if
! it escapes. */
DECL_EXTERNAL (vi->decl) = 0;
vi->is_global_var = 0;
/* If this is not a real malloc call assume the memory was
--- 3996,4003 ----
struct constraint_expr tmpc;
rhsc.create (0);
vi = make_heapvar ("HEAP");
! /* 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;
vi->is_global_var = 0;
/* If this is not a real malloc call assume the memory was
*************** set_uids_in_ptset (bitmap into, bitmap f
*** 5983,5988 ****
--- 6000,6008 ----
{
unsigned int i;
bitmap_iterator bi;
+ varinfo_t escaped_vi = get_varinfo (find (escaped_id));
+ bool everything_escaped
+ = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution,
anything_id);
EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
*************** set_uids_in_ptset (bitmap into, bitmap f
*** 5993,5998 ****
--- 6013,6026 ----
if (vi->is_artificial_var && !vi->is_heap_var)
continue;
+ if (everything_escaped
+ || (escaped_vi->solution
+ && bitmap_bit_p (escaped_vi->solution, i)))
+ {
+ pt->vars_contains_escaped = true;
+ pt->vars_contains_escaped_heap = vi->is_heap_var;
+ }
+
if (TREE_CODE (vi->decl) == VAR_DECL
|| TREE_CODE (vi->decl) == PARM_DECL
|| TREE_CODE (vi->decl) == RESULT_DECL)
*************** set_uids_in_ptset (bitmap into, bitmap f
*** 6007,6013 ****
set contains global variables. */
bitmap_set_bit (into, DECL_PT_UID (vi->decl));
if (vi->is_global_var)
! pt->vars_contains_global = true;
}
}
}
--- 6035,6041 ----
set contains global variables. */
bitmap_set_bit (into, DECL_PT_UID (vi->decl));
if (vi->is_global_var)
! pt->vars_contains_nonlocal = true;
}
}
}
*************** pt_solution_reset (struct pt_solution *p
*** 6164,6174 ****
it contains restrict tag variables. */
void
! pt_solution_set (struct pt_solution *pt, bitmap vars, bool
vars_contains_global)
{
memset (pt, 0, sizeof (struct pt_solution));
pt->vars = vars;
! pt->vars_contains_global = vars_contains_global;
}
/* Set the points-to solution *PT to point only to the variable VAR. */
--- 6192,6206 ----
it contains restrict tag variables. */
void
! pt_solution_set (struct pt_solution *pt, bitmap vars,
! bool vars_contains_nonlocal)
{
memset (pt, 0, sizeof (struct pt_solution));
pt->vars = vars;
! pt->vars_contains_nonlocal = vars_contains_nonlocal;
! pt->vars_contains_escaped
! = (cfun->gimple_df->escaped.anything
! || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars));
}
/* Set the points-to solution *PT to point only to the variable VAR. */
*************** pt_solution_set_var (struct pt_solution
*** 6179,6185 ****
memset (pt, 0, sizeof (struct pt_solution));
pt->vars = BITMAP_GGC_ALLOC ();
bitmap_set_bit (pt->vars, DECL_PT_UID (var));
! pt->vars_contains_global = is_global_var (var);
}
/* Computes the union of the points-to solutions *DEST and *SRC and
--- 6211,6220 ----
memset (pt, 0, sizeof (struct pt_solution));
pt->vars = BITMAP_GGC_ALLOC ();
bitmap_set_bit (pt->vars, DECL_PT_UID (var));
! pt->vars_contains_nonlocal = is_global_var (var);
! pt->vars_contains_escaped
! = (cfun->gimple_df->escaped.anything
! || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var)));
}
/* Computes the union of the points-to solutions *DEST and *SRC and
*************** pt_solution_ior_into (struct pt_solution
*** 6202,6208 ****
dest->escaped |= src->escaped;
dest->ipa_escaped |= src->ipa_escaped;
dest->null |= src->null;
! dest->vars_contains_global |= src->vars_contains_global;
if (!src->vars)
return;
--- 6237,6245 ----
dest->escaped |= src->escaped;
dest->ipa_escaped |= src->ipa_escaped;
dest->null |= src->null;
! dest->vars_contains_nonlocal |= src->vars_contains_nonlocal;
! dest->vars_contains_escaped |= src->vars_contains_escaped;
! dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap;
if (!src->vars)
return;
*************** pt_solution_includes_global (struct pt_s
*** 6259,6267 ****
{
if (pt->anything
|| pt->nonlocal
! || pt->vars_contains_global)
return true;
if (pt->escaped)
return pt_solution_includes_global (&cfun->gimple_df->escaped);
--- 6296,6309 ----
{
if (pt->anything
|| pt->nonlocal
! || pt->vars_contains_nonlocal
! /* The following is a hack to make the malloc escape hack work.
! In reality we'd need different sets for escaped-through-return
! and escaped-to-callees and passes would need to be updated. */
! || pt->vars_contains_escaped_heap)
return true;
+ /* 'escaped' is also a placeholder so we have to look into it. */
if (pt->escaped)
return pt_solution_includes_global (&cfun->gimple_df->escaped);
*************** pt_solutions_intersect_1 (struct pt_solu
*** 6331,6358 ****
any global memory they alias. */
if ((pt1->nonlocal
&& (pt2->nonlocal
! || pt2->vars_contains_global))
|| (pt2->nonlocal
! && pt1->vars_contains_global))
return true;
! /* Check the escaped solution if required. */
! if ((pt1->escaped || pt2->escaped)
! && !pt_solution_empty_p (&cfun->gimple_df->escaped))
! {
! /* If both point to escaped memory and that solution
! is not empty they alias. */
! if (pt1->escaped && pt2->escaped)
! return true;
!
! /* If either points to escaped memory see if the escaped solution
! intersects with the other. */
! if ((pt1->escaped
! && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt2))
! || (pt2->escaped
! && pt_solutions_intersect_1 (&cfun->gimple_df->escaped, pt1)))
! return true;
! }
/* Check the escaped solution if required.
??? Do we need to check the local against the IPA escaped sets? */
--- 6373,6391 ----
any global memory they alias. */
if ((pt1->nonlocal
&& (pt2->nonlocal
! || pt2->vars_contains_nonlocal))
|| (pt2->nonlocal
! && pt1->vars_contains_nonlocal))
return true;
! /* If either points to all escaped memory and the other points to
! any escaped memory they alias. */
! if ((pt1->escaped
! && (pt2->escaped
! || pt2->vars_contains_escaped))
! || (pt2->escaped
! && pt1->vars_contains_escaped))
! return true;
/* Check the escaped solution if required.
??? Do we need to check the local against the IPA escaped sets? */
*************** compute_points_to_sets (void)
*** 6800,6813 ****
points-to solution queries. */
cfun->gimple_df->escaped.escaped = 0;
- /* Mark escaped HEAP variables as global. */
- FOR_EACH_VEC_ELT (varmap, i, vi)
- if (vi
- && vi->is_heap_var
- && !vi->is_global_var)
- DECL_EXTERNAL (vi->decl) = vi->is_global_var
- = pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);
-
/* Compute the points-to sets for pointer SSA_NAMEs. */
for (i = 0; i < num_ssa_names; ++i)
{
--- 6833,6838 ----
*************** gate_ipa_pta (void)
*** 7054,7060 ****
/* IPA PTA solutions for ESCAPED. */
struct pt_solution ipa_escaped_pt
! = { true, false, false, false, false, false, NULL };
/* Associate node with varinfo DATA. Worker for
cgraph_for_node_and_aliases. */
--- 7079,7085 ----
/* IPA PTA solutions for ESCAPED. */
struct pt_solution ipa_escaped_pt
! = { true, false, false, false, false, false, false, false, NULL };
/* Associate node with varinfo DATA. Worker for
cgraph_for_node_and_aliases. */
*************** const pass_data pass_data_ipa_pta =
*** 7412,7418 ****
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
! TODO_update_ssa, /* todo_flags_finish */
};
class pass_ipa_pta : public simple_ipa_opt_pass
--- 7437,7443 ----
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
! 0, /* todo_flags_finish */
};
class pass_ipa_pta : public simple_ipa_opt_pass
Index: gcc/gimple-pretty-print.c
===================================================================
*** gcc/gimple-pretty-print.c.orig 2013-11-15 11:30:48.000000000 +0100
--- gcc/gimple-pretty-print.c 2013-11-15 11:39:05.609000833 +0100
*************** pp_points_to_solution (pretty_printer *b
*** 622,629 ****
pp_space (buffer);
}
pp_right_brace (buffer);
! if (pt->vars_contains_global)
! pp_string (buffer, " (glob)");
}
}
--- 622,639 ----
pp_space (buffer);
}
pp_right_brace (buffer);
! if (pt->vars_contains_nonlocal
! && pt->vars_contains_escaped_heap)
! pp_string (buffer, " (nonlocal, escaped heap)");
! else if (pt->vars_contains_nonlocal
! && pt->vars_contains_escaped)
! pp_string (buffer, " (nonlocal, escaped)");
! else if (pt->vars_contains_nonlocal)
! pp_string (buffer, " (nonlocal)");
! else if (pt->vars_contains_escaped_heap)
! pp_string (buffer, " (escaped heap)");
! else if (pt->vars_contains_escaped)
! pp_string (buffer, " (escaped)");
}
}
Index: gcc/testsuite/gcc.dg/tree-ssa/alias-28.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/alias-28.c 2013-11-15 11:39:05.609000833
+0100
***************
*** 0 ****
--- 1,26 ----
+ /* { dg-do run } */
+ /* { dg-options "-O3" } */
+
+ extern void abort (void);
+ extern void *malloc(__SIZE_TYPE__);
+
+ int * __attribute__((noinline,noclone))
+ foo (int *p)
+ {
+ int *q = (int *) malloc (sizeof (int));
+ *p = 1;
+ *q = 2;
+ if (*p != 1)
+ __link_error ();
+ *p = 3;
+ return q;
+ }
+
+ int main()
+ {
+ int i;
+ int *p = foo (&i);
+ if (i != 3 || *p != 2)
+ abort ();
+ return 0;
+ }
Index: gcc/tree-ssa-alias.c
===================================================================
*** gcc/tree-ssa-alias.c.orig 2013-11-15 11:30:48.000000000 +0100
--- gcc/tree-ssa-alias.c 2013-11-15 11:39:05.610000845 +0100
*************** dump_points_to_solution (FILE *file, str
*** 452,459 ****
{
fprintf (file, ", points-to vars: ");
dump_decl_set (file, pt->vars);
! if (pt->vars_contains_global)
! fprintf (file, " (includes global vars)");
}
}
--- 452,469 ----
{
fprintf (file, ", points-to vars: ");
dump_decl_set (file, pt->vars);
! if (pt->vars_contains_nonlocal
! && pt->vars_contains_escaped_heap)
! fprintf (file, " (nonlocal, escaped heap)");
! else if (pt->vars_contains_nonlocal
! && pt->vars_contains_escaped)
! fprintf (file, " (nonlocal, escaped)");
! else if (pt->vars_contains_nonlocal)
! fprintf (file, " (nonlocal)");
! else if (pt->vars_contains_escaped_heap)
! fprintf (file, " (escaped heap)");
! else if (pt->vars_contains_escaped)
! fprintf (file, " (escaped)");
}
}
Index: gcc/testsuite/gcc.dg/strlenopt-1.c
===================================================================
*** gcc/testsuite/gcc.dg/strlenopt-1.c.orig 2011-09-28 10:16:34.000000000
+0200
--- gcc/testsuite/gcc.dg/strlenopt-1.c 2013-11-15 11:57:50.154900805 +0100
*************** foo (char *p, char *r)
*** 16,24 ****
is immediately overwritten. */
strcat (q, "/");
strcat (q, "abcde");
! /* Due to inefficient PTA (PR50262) the above calls invalidate
! string length of r, so it is optimized just into strcpy instead
! of memcpy. */
strcat (q, r);
return q;
}
--- 16,22 ----
is immediately overwritten. */
strcat (q, "/");
strcat (q, "abcde");
! /* This can also be optimized into memcpy. */
strcat (q, r);
return q;
}
*************** main ()
*** 39,46 ****
}
/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */
! /* { dg-final { scan-tree-dump-times "memcpy \\(" 3 "strlen" } } */
! /* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */
--- 37,44 ----
}
/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */
! /* { dg-final { scan-tree-dump-times "memcpy \\(" 4 "strlen" } } */
! /* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */
Index: gcc/testsuite/gcc.dg/strlenopt-1f.c
===================================================================
*** gcc/testsuite/gcc.dg/strlenopt-1f.c.orig 2013-06-11 09:32:59.000000000
+0200
--- gcc/testsuite/gcc.dg/strlenopt-1f.c 2013-11-15 11:58:16.805208659 +0100
***************
*** 6,13 ****
#include "strlenopt-1.c"
/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */
! /* { dg-final { scan-tree-dump-times "__memcpy_chk \\(" 3 "strlen" } } */
! /* { dg-final { scan-tree-dump-times "__strcpy_chk \\(" 1 "strlen" } } */
/* { dg-final { scan-tree-dump-times "__strcat_chk \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "__stpcpy_chk \\(" 0 "strlen" } } */
--- 6,13 ----
#include "strlenopt-1.c"
/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */
! /* { dg-final { scan-tree-dump-times "__memcpy_chk \\(" 4 "strlen" } } */
! /* { dg-final { scan-tree-dump-times "__strcpy_chk \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "__strcat_chk \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */
/* { dg-final { scan-tree-dump-times "__stpcpy_chk \\(" 0 "strlen" } } */
