This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Improve alias analysis for anonymous memory (aka HEAP vars)
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 1 Jul 2009 14:24:21 +0200 (CEST)
- Subject: [PATCH] Improve alias analysis for anonymous memory (aka HEAP vars)
This patch improves how we handle anonymous memory (malloc results) in
points-to analysis. New anonymous memory is strictly local to the
allocating function if no pointer to that memory escapes. Currently
all anonymous memory is considered global which prevents disambiguations
against most function calls.
The idea is to delay deciding whether the anonymous memory (or rather
the HEAP variable) is global until after we completed computing the
escaped solution.
With DCE fixed to not cause calls that do not read from memory to
make previous stores necessary this also fixes a piece of PR19831.
Left for that PR is a way to delete a dead malloc/free pair. It
didn't fit into an existing pass (I tried DCE, builtin-folding and
forwprop) - at least if you want to catch the cases with remaining
allocation failure checks.
As usual a load of testcases need adjustments because they were
written without enough care.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
Richard.
2009-07-01 Richard Guenther <rguenther@suse.de>
PR tree-optimization/19831
* tree-ssa-dce.c (propagate_necessity): Calls to functions
that only act as barriers do not make any previous stores
necessary.
* tree-ssa-structalias.c (handle_lhs_call): Delay making
HEAP variables global, do not add a constraint from nonlocal.
(find_func_aliases): Handle escapes through return statements.
(compute_points_to_sets): Make escaped HEAP variables global.
* gcc.dg/tree-ssa/20041122-1.c: Enable TBAA, scan FRE dump,
make allocated memory escape. Un-XFAIL.
* gcc.dg/vect/pr21591.c: Make allocated memory escape.
* gcc.dg/vect/pr31699.c: Likewise.
* gcc.dg/tree-ssa/ssa-dce-7.c: New testcase.
libmudflap/
* testsuite/libmudflap.c/fail11-frag.c: Make allocated memory
escape.
* testsuite/libmudflap.c/fail12-frag.c: Likewise.
* testsuite/libmudflap.c/fail16-frag.c: Likewise.
* testsuite/libmudflap.c/fail31-frag.c: Likewise.
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c 2009-07-01 12:33:27.000000000 +0200
***************
*** 1,6 ****
/* { dg-do compile } */
! /* { dg-options "-O1 -fdump-tree-dom2" } */
!
__extension__ typedef __SIZE_TYPE__ size_t;
extern void *xmalloc (size_t) __attribute__ ((__malloc__));
--- 1,5 ----
/* { dg-do compile } */
! /* { dg-options "-O1 -fstrict-aliasing -fdump-tree-fre" } */
__extension__ typedef __SIZE_TYPE__ size_t;
extern void *xmalloc (size_t) __attribute__ ((__malloc__));
*************** struct basic_block_def
*** 17,26 ****
typedef struct basic_block_def *basic_block;
extern int n_basic_blocks;
extern edge frob ();
! void
! find_unreachable_blocks (int frobit)
{
! basic_block *tos, *worklist, bb;
tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
edge e = frob();
if (!(e->dest->flags & 4))
--- 16,25 ----
typedef struct basic_block_def *basic_block;
extern int n_basic_blocks;
extern edge frob ();
! basic_block *
! find_unreachable_blocks (void)
{
! basic_block *tos, *worklist;
tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
edge e = frob();
if (!(e->dest->flags & 4))
*************** find_unreachable_blocks (int frobit)
*** 28,38 ****
e->dest->flags |= 4;
*tos++ = e->dest;
}
}
/* If the aliasing code does its job properly, then we should be
able to determine that modifying e->dest->flags does not
! modify e or e->dest. The net result is that we only need one
! load of e->dest. */
! /* { dg-final { scan-tree-dump-times "->dest" 1 "dom2" { xfail *-*-* } } } */
! /* { dg-final { cleanup-tree-dump "dom2" } } */
--- 27,38 ----
e->dest->flags |= 4;
*tos++ = e->dest;
}
+ return worklist;
}
/* If the aliasing code does its job properly, then we should be
able to determine that modifying e->dest->flags does not
! modify e or e->dest if we can assert strict-aliasing rules.
! The net result is that we only need one load of e->dest. */
! /* { dg-final { scan-tree-dump-times "->dest" 1 "fre" } } */
! /* { dg-final { cleanup-tree-dump "fre" } } */
Index: trunk/gcc/tree-ssa-dce.c
===================================================================
*** trunk.orig/gcc/tree-ssa-dce.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/gcc/tree-ssa-dce.c 2009-07-01 12:34:00.000000000 +0200
*************** propagate_necessity (struct edge_list *e
*** 676,683 ****
--- 676,694 ----
if (is_gimple_call (stmt))
{
+ tree callee = gimple_call_fndecl (stmt);
unsigned i;
+ /* Calls to functions that are merely acting as barriers
+ or that only store to memory do not make any previous
+ stores necessary. */
+ if (callee != NULL_TREE
+ && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
+ && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
+ || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
+ || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE))
+ continue;
+
/* Calls implicitly load from memory, their arguments
in addition may explicitly perform memory loads. */
mark_all_reaching_defs_necessary (stmt);
Index: trunk/gcc/tree-ssa-structalias.c
===================================================================
*** trunk.orig/gcc/tree-ssa-structalias.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/gcc/tree-ssa-structalias.c 2009-07-01 12:33:27.000000000 +0200
*************** handle_lhs_call (tree lhs, int flags, VE
*** 3473,3479 ****
{
varinfo_t vi;
vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
! make_copy_constraint (vi, nonlocal_id);
}
else if (VEC_length (ce_s, rhsc) > 0)
{
--- 3473,3481 ----
{
varinfo_t vi;
vi = make_constraint_from_heapvar (get_vi_for_tree (lhs), "HEAP");
! /* We delay marking allocated storage global until we know if
! it escapes. */
! vi->is_global_var = 0;
}
else if (VEC_length (ce_s, rhsc) > 0)
{
*************** find_func_aliases (gimple origt)
*** 3910,3915 ****
--- 3912,3924 ----
{
make_escape_constraint (gimple_assign_rhs1 (t));
}
+ /* Handle escapes through return. */
+ else if (gimple_code (t) == GIMPLE_RETURN
+ && gimple_return_retval (t) != NULL_TREE
+ && could_have_pointers (gimple_return_retval (t)))
+ {
+ make_escape_constraint (gimple_return_retval (t));
+ }
/* Handle asms conservatively by adding escape constraints to everything. */
else if (gimple_code (t) == GIMPLE_ASM)
{
*************** compute_points_to_sets (void)
*** 5350,5355 ****
--- 5359,5365 ----
struct scc_info *si;
basic_block bb;
unsigned i;
+ varinfo_t vi;
timevar_push (TV_TREE_PTA);
*************** compute_points_to_sets (void)
*** 5447,5452 ****
--- 5457,5469 ----
points-to solution queries. */
cfun->gimple_df->escaped.escaped = 0;
+ /* Mark escaped HEAP variables as global. */
+ for (i = 0; VEC_iterate (varinfo_t, varmap, i, vi); ++i)
+ if (vi->is_heap_var
+ && !vi->is_global_var)
+ 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)
{
Index: trunk/gcc/testsuite/gcc.dg/vect/pr21591.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/vect/pr21591.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/vect/pr21591.c 2009-07-01 12:33:27.000000000 +0200
*************** struct a
*** 10,15 ****
--- 10,17 ----
struct a *malloc1(__SIZE_TYPE__) __attribute__((malloc));
void free(void*);
+ struct a *p, *q, *r;
+
void f(void)
{
struct a *a = malloc1(sizeof(struct a));
*************** void f(void)
*** 26,34 ****
{
a->a1[i] = b->a1[i] + c->a1[i];
}
! free(a);
! free(b);
! free(c);
}
/* { dg-final { scan-tree-dump-times "vectorized 2 loops" 1 "vect" } } */
--- 28,36 ----
{
a->a1[i] = b->a1[i] + c->a1[i];
}
! p = a;
! q = b;
! r = c;
}
/* { dg-final { scan-tree-dump-times "vectorized 2 loops" 1 "vect" } } */
Index: trunk/gcc/testsuite/gcc.dg/vect/pr31699.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/vect/pr31699.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/vect/pr31699.c 2009-07-01 12:33:27.000000000 +0200
***************
*** 7,19 ****
float x[256];
__attribute__ ((noinline))
! void foo(void)
{
double *z = malloc (sizeof(double) * 256);
int i;
for (i=0; i<256; ++i)
z[i] = x[i] + 1.0f;
}
--- 7,21 ----
float x[256];
__attribute__ ((noinline))
! double *foo(void)
{
double *z = malloc (sizeof(double) * 256);
int i;
for (i=0; i<256; ++i)
z[i] = x[i] + 1.0f;
+
+ return z;
}
Index: trunk/libmudflap/testsuite/libmudflap.c/fail11-frag.c
===================================================================
*** trunk.orig/libmudflap/testsuite/libmudflap.c/fail11-frag.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/libmudflap/testsuite/libmudflap.c/fail11-frag.c 2009-07-01 12:33:27.000000000 +0200
***************
*** 1,11 ****
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
int i = 10;
char *x = (char *) malloc (i * sizeof (char));
!
while (i--)
{
++x;
--- 1,12 ----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+ char *y;
int main ()
{
int i = 10;
char *x = (char *) malloc (i * sizeof (char));
! y = x;
while (i--)
{
++x;
Index: trunk/libmudflap/testsuite/libmudflap.c/fail12-frag.c
===================================================================
*** trunk.orig/libmudflap/testsuite/libmudflap.c/fail12-frag.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/libmudflap/testsuite/libmudflap.c/fail12-frag.c 2009-07-01 12:33:27.000000000 +0200
***************
*** 1,11 ****
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main ()
{
int i = 10;
int *x = (int *) malloc (i * sizeof (int));
!
while (i--)
{
++x;
--- 1,12 ----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+ int *y;
int main ()
{
int i = 10;
int *x = (int *) malloc (i * sizeof (int));
! y = x;
while (i--)
{
++x;
Index: trunk/libmudflap/testsuite/libmudflap.c/fail16-frag.c
===================================================================
*** trunk.orig/libmudflap/testsuite/libmudflap.c/fail16-frag.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/libmudflap/testsuite/libmudflap.c/fail16-frag.c 2009-07-01 12:33:27.000000000 +0200
***************
*** 1,6 ****
--- 1,7 ----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+ void *p;
int main ()
{
struct base {
*************** struct derived {
*** 15,21 ****
struct base *bp;
bp = (struct base *) malloc (sizeof (struct base));;
!
bp->basic = 10;
((struct derived *)bp)->extra = 'x';
return 0;
--- 16,22 ----
struct base *bp;
bp = (struct base *) malloc (sizeof (struct base));;
! p = bp;
bp->basic = 10;
((struct derived *)bp)->extra = 'x';
return 0;
Index: trunk/libmudflap/testsuite/libmudflap.c/fail31-frag.c
===================================================================
*** trunk.orig/libmudflap/testsuite/libmudflap.c/fail31-frag.c 2009-07-01 12:27:09.000000000 +0200
--- trunk/libmudflap/testsuite/libmudflap.c/fail31-frag.c 2009-07-01 12:33:27.000000000 +0200
*************** int main ()
*** 8,18 ****
int z = h (4, 10);
return 0;
}
!
int h (int i, int j)
{
int k[i];
k[j] = i;
return j;
}
--- 8,19 ----
int z = h (4, 10);
return 0;
}
! int *p;
int h (int i, int j)
{
int k[i];
k[j] = i;
+ p = k;
return j;
}
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-7.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-7.c 2009-07-01 12:33:27.000000000 +0200
***************
*** 0 ****
--- 1,33 ----
+ /* { dg-do link } */
+ /* { dg-options "-O -fdump-tree-optimized" } */
+
+ extern void link_error (void);
+ void foo(int n)
+ {
+ int * f = (int*) __builtin_malloc (n * sizeof (int));
+ int * ff = (int*) __builtin_malloc (n * sizeof (int));
+ int i;
+
+ for (i = 0; i < n; ++i)
+ {
+ f[i] = 1;
+ ff[i] = 2;
+ if (f[i] != 1)
+ link_error ();
+ if (ff[i] != 2)
+ link_error ();
+ }
+
+ __builtin_free (f);
+ __builtin_free (ff);
+ }
+ int main()
+ {
+ return 0;
+ }
+
+ /* We should have removed the calls to link_error () and all stores
+ to the allocated memory. */
+
+ /* { dg-final { scan-tree-dump-times "\\\*D" 0 "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */