This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][alias-improvements] Use the alias-oracle for PRE phi-translation
On Tue, 17 Feb 2009, Daniel Berlin wrote:
> On Mon, Feb 16, 2009 at 11:21 AM, Richard Guenther <rguenther@suse.de> wrote:
> >
> > I have been sitting on this patch for a long time now, and as issues with
> > it fixed itself a while ago I'd at least post it. On the branch currently
> > gcc.dg/tree-ssa/pr35286.c fails because phi-translation for load-PRE
> > is stuck at the store to g2 when translating the load of g1.a. This
> > is obviously a candidate for the oracle - thus the patch below which
> > also has to deal with value_dies_in_block_x which no longer can be
> > as simple as before.
> >
> > The odds with the patch are that we even more often re-build reference
> > trees from the SCCVN IL (which we cannot avoid easily without either
> > loosing some precision wrt TBAA or with duplicating all the oracle
> > for dealing with the SCCVN IL directly). It also, of course, looks
> > somewhat expensive though ...
>
> The expensive part is that it could be called multiple times with the
> same info as antic computation iterates, even though the result
> doesn't change between iterations.
> The easy solution here is to cache the result of where a
> translate_vuse_through_block and value_dies_in_block_x so we only
> compute it once.
> (note that value_dies_in_block_x can be cached for non-vuse cases too,
> it's just not expensive to compute for them)
I have added a cache for value_dies_in_block_x as below and am currently
re-bootstrapping and testing.
Richard.
2009-02-20 Richard Guenther <rguenther@suse.de>
* tree-ssa-sccvn.h (get_ref_from_reference_ops): Declare.
* tree-ssa-sccvn.c (get_ref_from_reference_ops): Export.
* tree-ssa-pre.c (struct bb_bitmap_sets): Add expr_dies bitmap.
(EXPR_DIES): New.
(translate_vuse_through_block): Use the oracle.
(phi_translate_1): Adjust.
(value_dies_in_block_x): Use the oracle. Cache the outcome
in EXPR_DIES.
* gcc.c-torture/execute/20090113-1.c: New testcase.
* gcc.c-torture/execute/20090113-1.c: Likewise.
Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c.orig 2009-02-20 14:20:49.000000000 +0100
--- gcc/tree-ssa-pre.c 2009-02-20 14:21:35.000000000 +0100
*************** typedef struct bb_bitmap_sets
*** 377,382 ****
--- 377,385 ----
the current iteration. */
bitmap_set_t new_sets;
+ /* A cache for value_dies_in_block_x. */
+ bitmap expr_dies;
+
/* True if we have visited this block during ANTIC calculation. */
unsigned int visited:1;
*************** typedef struct bb_bitmap_sets
*** 392,398 ****
#define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
#define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
! #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
#define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
--- 395,402 ----
#define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
#define PA_IN(BB) ((bb_value_sets_t) ((BB)->aux))->pa_in
#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
! #define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
! #define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
#define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
*************** do_unary:
*** 1245,1264 ****
it has the value it would have in BLOCK. */
static tree
! translate_vuse_through_block (tree vuse,
basic_block phiblock,
basic_block block)
{
gimple phi = SSA_NAME_DEF_STMT (vuse);
! if (gimple_code (phi) == GIMPLE_PHI
! && gimple_bb (phi) == phiblock)
{
! edge e = find_edge (block, gimple_bb (phi));
! if (e)
! return PHI_ARG_DEF (phi, e->dest_idx);
}
! return vuse;
}
/* Like find_leader, but checks for the value existing in SET1 *or*
--- 1249,1291 ----
it has the value it would have in BLOCK. */
static tree
! translate_vuse_through_block (VEC (vn_reference_op_s, heap) *operands,
! tree vuse,
basic_block phiblock,
basic_block block)
{
gimple phi = SSA_NAME_DEF_STMT (vuse);
! tree ref;
!
! if (gimple_bb (phi) != phiblock)
! return vuse;
!
! if (gimple_code (phi) == GIMPLE_PHI)
! {
! edge e = find_edge (block, phiblock);
! return PHI_ARG_DEF (phi, e->dest_idx);
! }
!
! if (!(ref = get_ref_from_reference_ops (operands)))
! return NULL_TREE;
!
! /* Use the alias-oracle to find either the PHI node in this block,
! the first VUSE used in this block that is equivalent to vuse or
! the first VUSE which definition in this block kills the value. */
! while (!stmt_may_clobber_ref_p (phi, ref))
{
! vuse = gimple_vuse (phi);
! phi = SSA_NAME_DEF_STMT (vuse);
! if (gimple_bb (phi) != phiblock)
! return vuse;
! if (gimple_code (phi) == GIMPLE_PHI)
! {
! edge e = find_edge (block, phiblock);
! return PHI_ARG_DEF (phi, e->dest_idx);
! }
}
! return NULL_TREE;
}
/* Like find_leader, but checks for the value existing in SET1 *or*
*************** phi_translate_1 (pre_expr expr, bitmap_s
*** 1623,1629 ****
}
if (vuse)
! newvuse = translate_vuse_through_block (vuse, phiblock, pred);
changed |= newvuse != vuse;
if (changed)
--- 1650,1664 ----
}
if (vuse)
! {
! newvuse = translate_vuse_through_block (newoperands,
! vuse, phiblock, pred);
! if (newvuse == NULL_TREE)
! {
! VEC_free (vn_reference_op_s, heap, newoperands);
! return NULL;
! }
! }
changed |= newvuse != vuse;
if (changed)
*************** static bool
*** 1835,1852 ****
value_dies_in_block_x (pre_expr expr, basic_block block)
{
tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
! /* Conservatively, a value dies if it's vuse is defined in this
! block, unless they come from phi nodes (which are merge operations,
! rather than stores. */
! if (vuse)
! {
! gimple def = SSA_NAME_DEF_STMT (vuse);
! if (gimple_bb (def) == block
! && gimple_code (def) != GIMPLE_PHI)
! return true;
}
! return false;
}
--- 1870,1941 ----
value_dies_in_block_x (pre_expr expr, basic_block block)
{
tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
+ vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
+ gimple def;
+ tree ref = NULL_TREE;
+ gimple_stmt_iterator gsi;
+ unsigned id = get_expression_id (expr);
+ bool res = false;
+
+ if (!vuse)
+ return false;
+
+ /* Lookup a previously calculated result. */
+ if (EXPR_DIES (block)
+ && bitmap_bit_p (EXPR_DIES (block), id * 2))
+ return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
+
+ /* A memory expression {e, VUSE} dies in the block if there is a
+ statement that may clobber e. If, starting statement walk from the
+ top of the basic block, a statement uses VUSE there can be no kill
+ inbetween that use and the original statement that loaded {e, VUSE},
+ so we can stop walking. */
+ for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ tree def_vuse, def_vdef;
+ def = gsi_stmt (gsi);
+ def_vuse = gimple_vuse (def);
+ def_vdef = gimple_vdef (def);
+
+ /* Not a memory statement. */
+ if (!def_vuse)
+ continue;
+
+ /* Not a may-def. */
+ if (!def_vdef)
+ {
+ /* A load with the same VUSE, we're done. */
+ if (def_vuse == vuse)
+ break;
! continue;
! }
!
! /* Init ref only if we really need it. */
! if (ref == NULL_TREE)
! {
! if (!(ref = get_ref_from_reference_ops (refx->operands)))
! {
! res = true;
! break;
! }
! }
! /* If the statement may clobber expr, it dies. */
! if (stmt_may_clobber_ref_p (def, ref))
! {
! res = true;
! break;
! }
}
!
! /* Remember the result. */
! if (!EXPR_DIES (block))
! EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
! bitmap_set_bit (EXPR_DIES (block), id * 2);
! if (res)
! bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
!
! return res;
}
Index: gcc/testsuite/gcc.c-torture/execute/20090113-1.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.c-torture/execute/20090113-1.c 2009-02-20 14:20:58.000000000 +0100
***************
*** 0 ****
--- 1,61 ----
+ typedef struct descriptor_dimension
+ {
+ int stride;
+ int lbound;
+ int ubound;
+ } descriptor_dimension;
+ typedef struct {
+ int *data;
+ int dtype;
+ descriptor_dimension dim[7];
+ } gfc_array_i4;
+
+ void
+ msum_i4 (gfc_array_i4 * const retarray,
+ gfc_array_i4 * const array,
+ const int * const pdim)
+ {
+ int count[7];
+ int extent[7];
+ int * dest;
+ const int * base;
+ int dim;
+ int n;
+ int len;
+
+ dim = (*pdim) - 1;
+ len = array->dim[dim].ubound + 1 - array->dim[dim].lbound;
+
+ for (n = 0; n < dim; n++)
+ {
+ extent[n] = array->dim[n].ubound + 1 - array->dim[n].lbound;
+ count[n] = 0;
+ }
+
+ dest = retarray->data;
+ base = array->data;
+
+ do
+ {
+ int result = 0;
+
+ for (n = 0; n < len; n++, base++)
+ result += *base;
+ *dest = result;
+
+ count[0]++;
+ dest += 1;
+ }
+ while (count[0] != extent[0]);
+ }
+
+ int main()
+ {
+ int rdata[3];
+ int adata[9];
+ gfc_array_i4 retarray = { rdata, 265, { { 1, 1, 3 } } };
+ gfc_array_i4 array = { adata, 266, { { 1, 1, 3 }, { 3, 1, 3 } } };
+ int dim = 2;
+ msum_i4 (&retarray, &array, &dim);
+ return 0;
+ }
Index: gcc/testsuite/gcc.c-torture/execute/20090113-2.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.c-torture/execute/20090113-2.c 2009-02-20 14:20:58.000000000 +0100
***************
*** 0 ****
--- 1,160 ----
+ struct obstack {};
+ struct bitmap_head_def;
+ typedef struct bitmap_head_def *bitmap;
+ typedef const struct bitmap_head_def *const_bitmap;
+ typedef unsigned long BITMAP_WORD;
+ typedef struct bitmap_obstack
+ {
+ struct bitmap_element_def *elements;
+ struct bitmap_head_def *heads;
+ struct obstack obstack;
+ } bitmap_obstack;
+ typedef struct bitmap_element_def
+ {
+ struct bitmap_element_def *next;
+ struct bitmap_element_def *prev;
+ unsigned int indx;
+ BITMAP_WORD bits[((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u))];
+ } bitmap_element;
+
+ struct bitmap_descriptor;
+
+ typedef struct bitmap_head_def {
+ bitmap_element *first;
+ bitmap_element *current;
+ unsigned int indx;
+ bitmap_obstack *obstack;
+ } bitmap_head;
+
+ bitmap_element bitmap_zero_bits;
+
+ typedef struct
+ {
+ bitmap_element *elt1;
+ bitmap_element *elt2;
+ unsigned word_no;
+ BITMAP_WORD bits;
+ } bitmap_iterator;
+
+ static void __attribute__((noinline))
+ bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map,
+ unsigned start_bit, unsigned *bit_no)
+ {
+ bi->elt1 = map->first;
+ bi->elt2 = ((void *)0);
+
+ while (1)
+ {
+ if (!bi->elt1)
+ {
+ bi->elt1 = &bitmap_zero_bits;
+ break;
+ }
+
+ if (bi->elt1->indx >= start_bit / (((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u)) * (8 * 8 * 1u)))
+ break;
+ bi->elt1 = bi->elt1->next;
+ }
+
+ if (bi->elt1->indx != start_bit / (((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u)) * (8 * 8 * 1u)))
+ start_bit = bi->elt1->indx * (((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u)) * (8 * 8 * 1u));
+
+ bi->word_no = start_bit / (8 * 8 * 1u) % ((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u));
+ bi->bits = bi->elt1->bits[bi->word_no];
+ bi->bits >>= start_bit % (8 * 8 * 1u);
+
+ start_bit += !bi->bits;
+
+ *bit_no = start_bit;
+ }
+
+ static void __attribute__((noinline))
+ bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
+ {
+ bi->bits >>= 1;
+ *bit_no += 1;
+ }
+
+ static unsigned char __attribute__((noinline))
+ bmp_iter_set_tail (bitmap_iterator *bi, unsigned *bit_no)
+ {
+ while (!(bi->bits & 1))
+ {
+ bi->bits >>= 1;
+ *bit_no += 1;
+ }
+ return 1;
+ }
+
+ static __inline__ unsigned char
+ bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
+ {
+ unsigned bno = *bit_no;
+ BITMAP_WORD bits = bi->bits;
+ bitmap_element *elt1;
+
+ if (bits)
+ {
+ while (!(bits & 1))
+ {
+ bits >>= 1;
+ bno += 1;
+ }
+ *bit_no = bno;
+ return 1;
+ }
+
+ *bit_no = ((bno + 64 - 1) / 64 * 64);
+ bi->word_no++;
+
+ elt1 = bi->elt1;
+ while (1)
+ {
+ while (bi->word_no != 2)
+ {
+ bi->bits = elt1->bits[bi->word_no];
+ if (bi->bits)
+ {
+ bi->elt1 = elt1;
+ return bmp_iter_set_tail (bi, bit_no);
+ }
+ *bit_no += 64;
+ bi->word_no++;
+ }
+
+ elt1 = elt1->next;
+ if (!elt1)
+ {
+ bi->elt1 = elt1;
+ return 0;
+ }
+ *bit_no = elt1->indx * (2 * 64);
+ bi->word_no = 0;
+ }
+ }
+
+ extern void abort (void);
+
+ static void __attribute__((noinline)) catchme(int i)
+ {
+ if (i != 0 && i != 64)
+ abort ();
+ }
+ static void __attribute__((noinline)) foobar (bitmap_head *chain)
+ {
+ bitmap_iterator rsi;
+ unsigned int regno;
+ for (bmp_iter_set_init (&(rsi), (chain), (0), &(regno));
+ bmp_iter_set (&(rsi), &(regno));
+ bmp_iter_next (&(rsi), &(regno)))
+ catchme(regno);
+ }
+
+ int main()
+ {
+ bitmap_element elem = { (void *)0, (void *)0, 0, { 1, 1 } };
+ bitmap_head live_throughout = { &elem, &elem, 0, (void *)0 };
+ foobar (&live_throughout);
+ return 0;
+ }
+
Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c.orig 2009-02-20 14:20:49.000000000 +0100
--- gcc/tree-ssa-sccvn.c 2009-02-20 14:20:58.000000000 +0100
*************** copy_reference_ops_from_ref (tree ref, V
*** 607,613 ****
Returns NULL_TREE if the ops were not handled.
This routine needs to be kept in sync with copy_reference_ops_from_ref. */
! static tree
get_ref_from_reference_ops (VEC(vn_reference_op_s, heap) *ops)
{
vn_reference_op_t op;
--- 607,613 ----
Returns NULL_TREE if the ops were not handled.
This routine needs to be kept in sync with copy_reference_ops_from_ref. */
! tree
get_ref_from_reference_ops (VEC(vn_reference_op_s, heap) *ops)
{
vn_reference_op_t op;
Index: gcc/tree-ssa-sccvn.h
===================================================================
*** gcc/tree-ssa-sccvn.h.orig 2009-02-20 14:20:49.000000000 +0100
--- gcc/tree-ssa-sccvn.h 2009-02-20 14:20:58.000000000 +0100
*************** vn_nary_op_t vn_nary_op_insert_pieces (u
*** 175,180 ****
--- 175,181 ----
tree, tree, unsigned int);
void copy_reference_ops_from_ref (tree, VEC(vn_reference_op_s, heap) **);
void copy_reference_ops_from_call (gimple, VEC(vn_reference_op_s, heap) **);
+ tree get_ref_from_reference_ops (VEC(vn_reference_op_s, heap) *ops);
tree vn_reference_lookup_pieces (tree,
VEC (vn_reference_op_s, heap) *,
vn_reference_t *, bool);