[PATCH][alias-improvements] Use the alias-oracle for PRE phi-translation
Daniel Berlin
dberlin@dberlin.org
Fri Feb 20 22:57:00 GMT 2009
Looks fine to me assuming it passes and doesn't add 300% to PRE time anyway :)
> 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);
>
More information about the Gcc-patches
mailing list