Re: [RFC][PATCH] Extend store ccp

[Diego Novillo <dnovillo at google dot com>]

On 6/19/07 3:50 AM, Revital1 Eres wrote:

> -      
> -      /* Note that for propagation purposes, we are only interested in
> -        visiting statements that load the exact same memory reference
> -        stored here.  Those statements will have the exact same list
> -        of virtual uses, so it is enough to set the output of this
> -        statement to be its first virtual definition.  */
> +      /* If we propagate constants from stores to loads by walking the
> +         virtual use-def chain than each store on the chain backward from

s/than/then/

> +         a load to it's exact store should have only one vuse operand

s/it's/its/

> +         and thus only one vdef.  This is the reason why when walking
> +         forward from the store to all it's uses in the purpose of adding

s/it's/its/

> +         ssa edges for each such exact use; we will want to handle those
> +         stores which have one vdef which means passing their first vdef
> +         will be sufficient.  In case we propagate immediate stores; we
> +         are only interested in visiting statements that load the exact
> +         same memory reference stored here.  Those statements will have
> +         the exact same list of virtual uses, so it is enough to set the
> +         output of this statement to be its first virtual definition.  */

Need an example here.  The description is rather hard to follow.

> -/* We have just defined a new value for VAR.  If IS_VARYING is true,
> -   add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
> +static bool
> +do_store_ccp (void)
> +{
> +  return (flag_tree_store_ccp != 0);
> +}

No.  This will return 'true' every time we run CCP.  We only want this
to return 'true' when flag_tree_store_ccp is set *and* we are running
pass_store_ccp.

> +
> +/* Given STMT add it to the edge worklist.  If IS_VARYING is true,
> +   add all the uses of stmt's lhs to VARYING_SSA_EDGES, otherwise add

s/lhs/LHS/

> +      /* Walk the virtual def-use chain to find all the real uses of
> +         a memory reference.   For example consider the following example:
> +
> +         1) arr[i].x = tmp1;
> +         ...
> +         2) arr[i].y = tmp2;
> +         ...
> +         3) reg1 = arr[i].x;
> +         ...
> +         4) arr[i].z = tmp2;
> +         ...
> +         5) reg2 = arr[i].x;
> +
> +         When the propogator visit stmt no. 1 it will add an edge for

s/propogator/propagator/
s/visit/visits/

Put the VDEFs and VUSEs in that example for clarity.

> +         statements 3 and 5.  */
> +      do
>         {
> -         STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
> -         if (is_varying)
> -           VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt);
> -         else
> -           VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt);
> +         /* Look at the DEF for the VUSE and see if it matches this DEF.  */
> +
> +         if (has_zero_uses (new_var))
> +           return;
> +         FOR_EACH_IMM_USE_FAST (use_p, iter, new_var)

Blank line before FOR_EACH_IMM_USE_FAST

> +
> +         /* Each store on the chain backward from a load to it's

s/it's/its/

> +            exact store should have only one vuse operand and thus only
> +            one vdef.  This is the reason why when traversing forward

s/vuse/VUSE/
s/vdef/VDEF/

> +            from the store to all it's uses it's enough to handle only
> +            those stores which have only one vdef.  */

This comment is a bit hard to parse.  Perhaps it would help if you write
an example with the VDEFs/VUSEs.

> +  do
> +    {
> +      if (TREE_CODE (*use->use) != SSA_NAME)

USE_FROM_PTR (use)

> +        return NULL_TREE;
> +      /* Look at the DEF for the VUSE and see if it matches this USE

Blank line before comment.

> +         and if it's RHS is an SSA_NAME.  Don't try to deal with

s/it's/its/

> +         PHI_NODEs.  */
> +      def = SSA_NAME_DEF_STMT (*use->use);

USE_FROM_PTR (use)

> +      if (TREE_CODE (def) != GIMPLE_MODIFY_STMT)
> +       return NULL_TREE;
> +
> +      if (!handled_component_p (GIMPLE_STMT_OPERAND (def, 0)))
> +       return NULL_TREE;
> +
> +      base2 = get_ref_base_and_extent (GIMPLE_STMT_OPERAND (def, 0), &offset2,
> +                                      &size2, &maxsize2);

Add a local variable 'tree def_lhs = GIMPLE_STMT_OPERAND (def, 0)'.

> +      /* If the base of the DEF does not match that of the USE it may

Likewise.

> +         be a clobber.  Bail out in this case.  */
> +      if (!operand_equal_p (base, base2, 0))
> +       return NULL_TREE;
> +
> +      if (offset_overlaps_with_access (offset, size, offset2, maxsize2))
> +       {
> +         /* If the DEF is not exact and matches, bail out.  */
> +         if (maxsize2 != size2 || size2 != size || offset2 != offset)
> +           return NULL_TREE;
> +
> +         /* For now just handle a distance of one.  If the RHS of the DEF
> +            is another ref, we could recurse here.
> +            ???  Recurse here?  */

A distance of one?  What do you mean in this comment?

> +         return *use->use;

Call USE_FROM_PTR.

> +          /* Walk the virtual use-def chain to analyze memory references.
> +             For example in the following code the algorithm would propagate
> +             Z into 0.

s/"Propagate Z into 0"/"Propagate 0 into all VUSEs of Z"/