PRE and uninitialized variables

Hello,

first, this patch is not ready (it doesn't even bootstrap), I am posting 
it for comments. The idea is, when we do value numbering, while looking 
for the current value of a local variable, we may hit a clobber or reach 
the beginning of the function. In both cases, it seems to me that we could 
use a default definition as the value of the variable. This later allows 
the uninit pass to warn about the use of an uninitialized or clobbered 
variable (some passes can also optimize the code better). The part about 
clobbers passed regtesting, but the part about reaching the entry of the 
function fails bootstrap with:

Existing SSA name for symbol marked for renaming: __d_14(D)
internal compiler error: SSA corruption

when execute_update_addresses_taken is called after SRA. In the case I 
looked at, the new code was called on the lhs of an assignment (to check 
if both sides had the same value number). Creating new ssa_names in the 
middle of sccvn is probably a bad idea, although it doesn't help if I 
create them beforehand, maybe creating the default definition and leaving 
it unused means that no one feels responsible for cleaning it up? 
(TODO_update_ssa doesn't help)

I am quite restrictive in the conditions for the code to apply: 
is_gimple_reg_type, useless_type_conversion_p (uh? I forgot that one in 
the "reached entry" case...), I am not sure what I can do if the local 
variable is an aggregate and we are reading one field, maybe create an 
artificial variable just for the purpose of using its default definition?

Mostly, I would like to know if the approach makes sense. Is storing the 
default definition in SSA_VAL ok, or is there some way to use VN_TOP to 
mark undefinedness? Any pointer would be welcome...

 	* tree-ssa-sccvn.c (vn_reference_lookup_2): Handle function entry.
 	(vn_reference_lookup_3): Handle clobbers.
 	(init_scc_vn): Default definitions are their own definition.

PS: the testsuite for libgomp is looong, it almost doubles the time for 
the whole testsuite to complete on gcc112. It would be great if someone 
could split it into a few pieces that run in parallel.

On Sun, May 17, 2015 at 9:11 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> first, this patch is not ready (it doesn't even bootstrap), I am posting it
> for comments. The idea is, when we do value numbering, while looking for the
> current value of a local variable, we may hit a clobber or reach the
> beginning of the function. In both cases, it seems to me that we could use a
> default definition as the value of the variable. This later allows the
> uninit pass to warn about the use of an uninitialized or clobbered variable
> (some passes can also optimize the code better). The part about clobbers
> passed regtesting, but the part about reaching the entry of the function
> fails bootstrap with:
>
> Existing SSA name for symbol marked for renaming: __d_14(D)
> internal compiler error: SSA corruption
>
> when execute_update_addresses_taken is called after SRA. In the case I
> looked at, the new code was called on the lhs of an assignment (to check if
> both sides had the same value number).

Yeah - the tail-merging code should now be stripped off using the VN as
now PRE fully propagates all values.

 Creating new ssa_names in the middle
> of sccvn is probably a bad idea, although it doesn't help if I create them
> beforehand, maybe creating the default definition and leaving it unused
> means that no one feels responsible for cleaning it up? (TODO_update_ssa
> doesn't help)
>
> I am quite restrictive in the conditions for the code to apply:
> is_gimple_reg_type, useless_type_conversion_p (uh? I forgot that one in the
> "reached entry" case...), I am not sure what I can do if the local variable
> is an aggregate and we are reading one field, maybe create an artificial
> variable just for the purpose of using its default definition?
>
> Mostly, I would like to know if the approach makes sense. Is storing the
> default definition in SSA_VAL ok, or is there some way to use VN_TOP to mark
> undefinedness? Any pointer would be welcome...

You should use VN_TOP during VN.  Otherwise you'll miss optimization
opportunities.  Now the question is then what to use at eliminate() time.
To get useful warnings you'd need to distinguish which VN_TOP you
get?

Note that funneling in VN_TOP might be tricky ;)

Richard.

>         * tree-ssa-sccvn.c (vn_reference_lookup_2): Handle function entry.
>         (vn_reference_lookup_3): Handle clobbers.
>         (init_scc_vn): Default definitions are their own definition.
>
> PS: the testsuite for libgomp is looong, it almost doubles the time for the
> whole testsuite to complete on gcc112. It would be great if someone could
> split it into a few pieces that run in parallel.
>
> --
> Marc Glisse
> Index: gcc/testsuite/gcc.dg/uninit-clob.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/uninit-clob.c  (revision 0)
> +++ gcc/testsuite/gcc.dg/uninit-clob.c  (working copy)
> @@ -0,0 +1,13 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -Wuninitialized" } */
> +
> +int *p;
> +
> +int f(){
> +  {
> +    int q = 42;
> +    p = &q;
> +  }
> +  return *p; /* { dg-warning "uninitialized" "warning" } */
> +}
> +
> Index: gcc/testsuite/gcc.dg/uninit-sccvn.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/uninit-sccvn.c (revision 0)
> +++ gcc/testsuite/gcc.dg/uninit-sccvn.c (working copy)
> @@ -0,0 +1,12 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -Wuninitialized" } */
> +
> +int g, h;
> +void *p;
> +int f(int x){
> +  int a;
> +  g = 42;
> +  h = a;
> +  p = &a;
> +  return h; /* { dg-warning "uninitialized" "warning" } */
> +}
> Index: gcc/tree-ssa-sccvn.c
> ===================================================================
> --- gcc/tree-ssa-sccvn.c        (revision 223269)
> +++ gcc/tree-ssa-sccvn.c        (working copy)
> @@ -1553,26 +1553,33 @@ vn_reference_lookup_1 (vn_reference_t vr
>         *vnresult = (vn_reference_t)*slot;
>        return ((vn_reference_t)*slot)->result;
>      }
>
>    return NULL_TREE;
>  }
>
>  static tree *last_vuse_ptr;
>  static vn_lookup_kind vn_walk_kind;
>  static vn_lookup_kind default_vn_walk_kind;
> +static vn_reference_t
> +vn_reference_lookup_or_insert_for_pieces (tree vuse,
> +                                         alias_set_type set,
> +                                         tree type,
> +                                         vec<vn_reference_op_s,
> +                                               va_heap> operands,
> +                                         tree value);
>
>  /* Callback for walk_non_aliased_vuses.  Adjusts the vn_reference_t VR_
>     with the current VUSE and performs the expression lookup.  */
>
>  static void *
> -vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse,
> +vn_reference_lookup_2 (ao_ref *ref, tree vuse,
>                        unsigned int cnt, void *vr_)
>  {
>    vn_reference_t vr = (vn_reference_t)vr_;
>    vn_reference_s **slot;
>    hashval_t hash;
>
>    /* This bounds the stmt walks we perform on reference lookups
>       to O(1) instead of O(N) where N is the number of dominating
>       stores.  */
>    if (cnt > (unsigned) PARAM_VALUE
> (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS))
> @@ -1587,20 +1594,39 @@ vn_reference_lookup_2 (ao_ref *op ATTRIB
>    vr->vuse = vuse_ssa_val (vuse);
>    if (vr->vuse)
>      vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse);
>
>    hash = vr->hashcode;
>    slot = current_info->references->find_slot_with_hash (vr, hash,
> NO_INSERT);
>    if (!slot && current_info == optimistic_info)
>      slot = valid_info->references->find_slot_with_hash (vr, hash,
> NO_INSERT);
>    if (slot)
>      return *slot;
> +  if (gimple_nop_p (SSA_NAME_DEF_STMT (vuse)))
> +    {
> +      tree base = ao_ref_base (ref);
> +      if (TREE_CODE (base) == VAR_DECL
> +         && !is_global_var (base)
> +         && is_gimple_reg_type (vr->type))
> +       {
> +         tree val = ssa_default_def (cfun, base);
> +         if (!val)
> +           {
> +             val = get_or_create_ssa_default_def (cfun, base);
> +             VN_INFO_GET (val)->valnum = val;
> +             VN_INFO (val)->expr = NULL_TREE;
> +             VN_INFO (val)->value_id = 0;
> +           }
> +         return vn_reference_lookup_or_insert_for_pieces
> +                  (vuse, vr->set, vr->type, vr->operands, val);
> +       }
> +    }
>
>    return NULL;
>  }
>
>  /* Lookup an existing or insert a new vn_reference entry into the
>     value table for the VUSE, SET, TYPE, OPERANDS reference which
>     has the value VALUE which is either a constant or an SSA name.  */
>
>  static vn_reference_t
>  vn_reference_lookup_or_insert_for_pieces (tree vuse,
> @@ -1712,21 +1738,40 @@ vn_reference_lookup_3 (ao_ref *ref, tree
>    offset = ref->offset;
>    maxsize = ref->max_size;
>
>    /* If we cannot constrain the size of the reference we cannot
>       test if anything kills it.  */
>    if (maxsize == -1)
>      return (void *)-1;
>
>    /* We can't deduce anything useful from clobbers.  */
>    if (gimple_clobber_p (def_stmt))
> -    return (void *)-1;
> +    {
> +      if (TREE_CODE (base) == VAR_DECL
> +         && !is_global_var (base)
> +         && operand_equal_p (base, gimple_assign_lhs (def_stmt), 0)
> +         && is_gimple_reg_type (vr->type)
> +         && useless_type_conversion_p (vr->type, TREE_TYPE (base)))
> +       {
> +         tree val = ssa_default_def (cfun, base);
> +         if (!val)
> +           {
> +             val = get_or_create_ssa_default_def (cfun, base);
> +             VN_INFO_GET (val)->valnum = val;
> +             VN_INFO (val)->expr = NULL_TREE;
> +             VN_INFO (val)->value_id = 0;
> +           }
> +         return vn_reference_lookup_or_insert_for_pieces
> +                  (vuse, vr->set, vr->type, vr->operands, val);
> +       }
> +      return (void *)-1;
> +    }
>
>    /* def_stmt may-defs *ref.  See if we can derive a value for *ref
>       from that definition.
>       1) Memset.  */
>    if (is_gimple_reg_type (vr->type)
>        && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET)
>        && integer_zerop (gimple_call_arg (def_stmt, 1))
>        && tree_fits_uhwi_p (gimple_call_arg (def_stmt, 2))
>        && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR)
>      {
> @@ -4190,21 +4235,22 @@ init_scc_vn (void)
>
>    VN_TOP = create_tmp_var_raw (void_type_node, "vn_top");
>
>    /* Create the VN_INFO structures, and initialize value numbers to
>       TOP.  */
>    for (i = 0; i < num_ssa_names; i++)
>      {
>        tree name = ssa_name (i);
>        if (name)
>         {
> -         VN_INFO_GET (name)->valnum = VN_TOP;
> +         VN_INFO_GET (name)->valnum = SSA_NAME_IS_DEFAULT_DEF (name) ? name
> +                                                                     :
> VN_TOP;
>           VN_INFO (name)->expr = NULL_TREE;
>           VN_INFO (name)->value_id = 0;
>         }
>      }
>
>    renumber_gimple_stmt_uids ();
>
>    /* Create the valid and optimistic value numbering tables.  */
>    valid_info = XCNEW (struct vn_tables_s);
>    allocate_vn_table (valid_info);
>