This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: DSE calls to builtins (memset, etc)


On Sat, Aug 16, 2014 at 11:21 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> here is a patch extending DSE to handle calls to memset, memcpy and memmove.
> A number of alias functions didn't have a version taking an ao_ref*, so I
> added those. Instead of naming things _1, _2, etc I took advantage of C++
> and overloaded. I kept ref_maybe_used_by_call_p so we are still updating the
> stats, but I am not sure how reliable they are, for instance there are a
> number of direct calls to refs_may_alias_p_1 that skip the stats in
> refs_may_alias_p (so I didn't add counters to the new refs_may_alias_p
> overload).
>
> The piece of code I removed from dse_optimize_stmt was dead, the test has
> already been done in dse_possible_dead_store_p (and I ran
> bootstrap+testsuite with an assertion to confirm).
>
> I only listed 3 builtins, but it should be easy to add more. The condition
> about the third argument is unnecessary for now, but copied from
> tree-ssa-alias.c to make it easier to add more builtins like strcpy.
>
> Bootstrap+testsuite (really all languages) on x86_64-linux-gnu.

Comments below

> 2014-08-18  Marc Glisse  <marc.glisse@inria.fr>
>
>         PR tree-optimization/62112
> gcc/
>         tree-ssa-alias.c (ref_may_alias_global_p, refs_may_alias_p,
>         ref_maybe_used_by_stmt_p): New overloads.
>         (ref_maybe_used_by_call_p): Take ao_ref* instead of tree.
>         (stmt_kills_ref_p_1): Rename...
>         (stmt_kills_ref_p): ... to this.
>         tree-ssa-alias.h (ref_may_alias_global_p, ref_maybe_used_by_stmt_p,
>         stmt_kills_ref_p): Declare.
>         tree-ssa-dse.c (dse_possible_dead_store_p): New argument, use it.
>         Move the self-assignment case...
>         (dse_optimize_stmt): ... here. Handle builtin calls. Remove dead
> code.
> gcc/testsuite/
>         gcc.dg/tree-ssa/pr62112-1.c: New file.
>         gcc.dg/tree-ssa/pr62112-2.c: Likewise.
>
> --
> Marc Glisse
> Index: gcc/testsuite/gcc.dg/tree-ssa/pr62112-1.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/pr62112-1.c   (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr62112-1.c   (working copy)
> @@ -0,0 +1,23 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-dse1-details" } */
> +
> +void f(){
> +  char*p=__builtin_malloc(42);
> +  __builtin_memset(p,3,10);
> +  __builtin_memset(p,7,33);
> +}
> +char*g;
> +void h(){
> +  char*p=__builtin_malloc(42);
> +  g=__builtin_memset(p,3,10);
> +  __builtin_free(p);
> +}
> +char*i(){
> +  char*p=__builtin_malloc(42);
> +  __builtin_memset(p,3,10);
> +  __builtin_memset(p,7,33);
> +  return p;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Deleted dead store" 4 "dse1" } } */
> +/* { dg-final { cleanup-tree-dump "dse1" } } */
> Index: gcc/testsuite/gcc.dg/tree-ssa/pr62112-2.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/pr62112-2.c   (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr62112-2.c   (working copy)
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-dse1-details" } */
> +
> +char*g;
> +char* f(){
> +  char*p=__builtin_malloc(42);
> +  __builtin_memset(p,3,33);
> +  __builtin_memset(p,7,10);
> +  return p;
> +}
> +void h(){
> +  char*p=__builtin_malloc(42);
> +  g=__builtin_memset(p,3,10);
> +}
> +
> +/* { dg-final { scan-tree-dump-not "Deleted dead store" "dse1" } } */
> +/* { dg-final { cleanup-tree-dump "dse1" } } */
> Index: gcc/tree-ssa-alias.c
> ===================================================================
> --- gcc/tree-ssa-alias.c        (revision 214066)
> +++ gcc/tree-ssa-alias.c        (working copy)
> @@ -326,31 +326,39 @@ ptr_deref_may_alias_ref_p_1 (tree ptr, a
>      return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0));
>    else if (DECL_P (base))
>      return ptr_deref_may_alias_decl_p (ptr, base);
>
>    return true;
>  }
>
>  /* Return true whether REF may refer to global memory.  */
>
>  bool
> -ref_may_alias_global_p (tree ref)
> +ref_may_alias_global_p (ao_ref *ref)
>  {
> -  tree base = get_base_address (ref);
> +  tree base = ao_ref_base (ref);
>    if (DECL_P (base))
>      return is_global_var (base);
>    else if (TREE_CODE (base) == MEM_REF
>            || TREE_CODE (base) == TARGET_MEM_REF)
>      return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
>    return true;
>  }
>
> +bool
> +ref_may_alias_global_p (tree ref)
> +{
> +  ao_ref r;
> +  ao_ref_init (&r, ref);
> +  return ref_may_alias_global_p (&r);
> +}
> +

I'd do two wrapers then since get_base_address is way cheaper
than doing ao_ref_base.  Thus, split out the code doing the
actual job into a static ref_may_alias_global_1?

>  /* Return true whether STMT may clobber global memory.  */
>
>  bool
>  stmt_may_clobber_global_p (gimple stmt)
>  {
>    tree lhs;
>
>    if (!gimple_vdef (stmt))
>      return false;
>
> @@ -1406,20 +1414,28 @@ refs_may_alias_p_1 (ao_ref *ref1, ao_ref
>                                       tbaa_p);
>
>    /* We really do not want to end up here, but returning true is safe.  */
>  #ifdef ENABLE_CHECKING
>    gcc_unreachable ();
>  #else
>    return true;
>  #endif
>  }
>
> +static bool
> +refs_may_alias_p (tree ref1, ao_ref *ref2)
> +{
> +  ao_ref r1;
> +  ao_ref_init (&r1, ref1);
> +  return refs_may_alias_p_1 (&r1, ref2, true);
> +}
> +
>  bool
>  refs_may_alias_p (tree ref1, tree ref2)
>  {
>    ao_ref r1, r2;
>    bool res;
>    ao_ref_init (&r1, ref1);
>    ao_ref_init (&r2, ref2);
>    res = refs_may_alias_p_1 (&r1, &r2, true);
>    if (res)
>      ++alias_stats.refs_may_alias_p_may_alias;
> @@ -1762,39 +1778,37 @@ process_args:
>           ao_ref_init (&r, op);
>           if (refs_may_alias_p_1 (&r, ref, true))
>             return true;
>         }
>      }
>
>    return false;
>  }
>
>  static bool
> -ref_maybe_used_by_call_p (gimple call, tree ref)
> +ref_maybe_used_by_call_p (gimple call, ao_ref *ref)
>  {
> -  ao_ref r;
>    bool res;
> -  ao_ref_init (&r, ref);
> -  res = ref_maybe_used_by_call_p_1 (call, &r);
> +  res = ref_maybe_used_by_call_p_1 (call, ref);
>    if (res)
>      ++alias_stats.ref_maybe_used_by_call_p_may_alias;
>    else
>      ++alias_stats.ref_maybe_used_by_call_p_no_alias;
>    return res;
>  }
>
>
>  /* If the statement STMT may use the memory reference REF return
>     true, otherwise return false.  */
>
>  bool
> -ref_maybe_used_by_stmt_p (gimple stmt, tree ref)
> +ref_maybe_used_by_stmt_p (gimple stmt, ao_ref *ref)
>  {
>    if (is_gimple_assign (stmt))
>      {
>        tree rhs;
>
>        /* All memory assign statements are single.  */
>        if (!gimple_assign_single_p (stmt))
>         return false;
>
>        rhs = gimple_assign_rhs1 (stmt);
> @@ -1803,41 +1817,48 @@ ref_maybe_used_by_stmt_p (gimple stmt, t
>           || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
>         return false;
>
>        return refs_may_alias_p (rhs, ref);
>      }
>    else if (is_gimple_call (stmt))
>      return ref_maybe_used_by_call_p (stmt, ref);
>    else if (gimple_code (stmt) == GIMPLE_RETURN)
>      {
>        tree retval = gimple_return_retval (stmt);
> -      tree base;
>        if (retval
>           && TREE_CODE (retval) != SSA_NAME
>           && !is_gimple_min_invariant (retval)
>           && refs_may_alias_p (retval, ref))
>         return true;
>        /* If ref escapes the function then the return acts as a use.  */
> -      base = get_base_address (ref);
> +      tree base = ao_ref_base (ref);
>        if (!base)
>         ;
>        else if (DECL_P (base))
>         return is_global_var (base);
>        else if (TREE_CODE (base) == MEM_REF
>                || TREE_CODE (base) == TARGET_MEM_REF)
>         return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
>        return false;
>      }
>
>    return true;
>  }
>
> +bool
> +ref_maybe_used_by_stmt_p (gimple stmt, tree ref)
> +{
> +  ao_ref r;
> +  ao_ref_init (&r, ref);
> +  return ref_maybe_used_by_stmt_p (stmt, &r);
> +}
> +
>  /* If the call in statement CALL may clobber the memory reference REF
>     return true, otherwise return false.  */
>
>  bool
>  call_may_clobber_ref_p_1 (gimple call, ao_ref *ref)
>  {
>    tree base;
>    tree callee;
>
>    /* If the call is pure or const it cannot clobber anything.  */
> @@ -2162,22 +2183,22 @@ bool
>  stmt_may_clobber_ref_p (gimple stmt, tree ref)
>  {
>    ao_ref r;
>    ao_ref_init (&r, ref);
>    return stmt_may_clobber_ref_p_1 (stmt, &r);
>  }
>
>  /* If STMT kills the memory reference REF return true, otherwise
>     return false.  */
>
> -static bool
> -stmt_kills_ref_p_1 (gimple stmt, ao_ref *ref)
> +bool
> +stmt_kills_ref_p (gimple stmt, ao_ref *ref)
>  {
>    if (!ao_ref_base (ref))
>      return false;
>
>    if (gimple_has_lhs (stmt)
>        && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
>        /* The assignment is not necessarily carried out if it can throw
>          and we can catch it in the current function where we could inspect
>          the previous value.
>          ???  We only need to care about the RHS throwing.  For aggregate
> @@ -2350,21 +2371,21 @@ stmt_kills_ref_p_1 (gimple stmt, ao_ref
>           }
>      }
>    return false;
>  }
>
>  bool
>  stmt_kills_ref_p (gimple stmt, tree ref)
>  {
>    ao_ref r;
>    ao_ref_init (&r, ref);
> -  return stmt_kills_ref_p_1 (stmt, &r);
> +  return stmt_kills_ref_p (stmt, &r);
>  }
>
>
>  /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
>     TARGET or a statement clobbering the memory reference REF in which
>     case false is returned.  The walk starts with VUSE, one argument of PHI.
> */
>
>  static bool
>  maybe_skip_until (gimple phi, tree target, ao_ref *ref,
>                   tree vuse, unsigned int *cnt, bitmap *visited,
> Index: gcc/tree-ssa-alias.h
> ===================================================================
> --- gcc/tree-ssa-alias.h        (revision 214066)
> +++ gcc/tree-ssa-alias.h        (working copy)
> @@ -94,31 +94,34 @@ struct ao_ref
>
>
>  /* In tree-ssa-alias.c  */
>  extern void ao_ref_init (ao_ref *, tree);
>  extern void ao_ref_init_from_ptr_and_size (ao_ref *, tree, tree);
>  extern tree ao_ref_base (ao_ref *);
>  extern alias_set_type ao_ref_alias_set (ao_ref *);
>  extern bool ptr_deref_may_alias_global_p (tree);
>  extern bool ptr_derefs_may_alias_p (tree, tree);
>  extern bool ref_may_alias_global_p (tree);
> +extern bool ref_may_alias_global_p (ao_ref *);
>  extern bool refs_may_alias_p (tree, tree);
>  extern bool refs_may_alias_p_1 (ao_ref *, ao_ref *, bool);
>  extern bool refs_anti_dependent_p (tree, tree);
>  extern bool refs_output_dependent_p (tree, tree);
>  extern bool ref_maybe_used_by_stmt_p (gimple, tree);
> +extern bool ref_maybe_used_by_stmt_p (gimple, ao_ref *);
>  extern bool stmt_may_clobber_global_p (gimple);
>  extern bool stmt_may_clobber_ref_p (gimple, tree);
>  extern bool stmt_may_clobber_ref_p_1 (gimple, ao_ref *);
>  extern bool call_may_clobber_ref_p (gimple, tree);
>  extern bool call_may_clobber_ref_p_1 (gimple, ao_ref *);
>  extern bool stmt_kills_ref_p (gimple, tree);
> +extern bool stmt_kills_ref_p (gimple, ao_ref *);
>  extern tree get_continuation_for_phi (gimple, ao_ref *,
>                                       unsigned int *, bitmap *, bool,
>                                       void *(*)(ao_ref *, tree, void *,
> bool),
>                                       void *);
>  extern void *walk_non_aliased_vuses (ao_ref *, tree,
>                                      void *(*)(ao_ref *, tree,
>                                                unsigned int, void *),
>                                      void *(*)(ao_ref *, tree, void *,
> bool),
>                                      void *);
>  extern unsigned int walk_aliased_vdefs (ao_ref *, tree,
> Index: gcc/tree-ssa-dse.c
> ===================================================================
> --- gcc/tree-ssa-dse.c  (revision 214066)
> +++ gcc/tree-ssa-dse.c  (working copy)
> @@ -75,39 +75,32 @@ along with GCC; see the file COPYING3.
>     fact, they are the same transformation applied to different views of
>     the CFG.  */
>
>
>  /* Bitmap of blocks that have had EH statements cleaned.  We should
>     remove their dead edges eventually.  */
>  static bitmap need_eh_cleanup;
>
>
>  /* A helper of dse_optimize_stmt.
> -   Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that
> -   may prove STMT to be dead.
> +   Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate
> +   statement *USE_STMT that may prove STMT to be dead.
>     Return TRUE if the above conditions are met, otherwise FALSE.  */
>
>  static bool
> -dse_possible_dead_store_p (gimple stmt, gimple *use_stmt)
> +dse_possible_dead_store_p (ao_ref *ref, gimple stmt, gimple *use_stmt)
>  {
>    gimple temp;
>    unsigned cnt = 0;
>
>    *use_stmt = NULL;
>
> -  /* Self-assignments are zombies.  */
> -  if (operand_equal_p (gimple_assign_rhs1 (stmt), gimple_assign_lhs (stmt),
> 0))
> -    {
> -      *use_stmt = stmt;
> -      return true;
> -    }
> -
>    /* Find the first dominated statement that clobbers (part of) the
>       memory stmt stores to with no intermediate statement that may use
>       part of the memory stmt stores.  That is, find a store that may
>       prove stmt to be a dead store.  */
>    temp = stmt;
>    do
>      {
>        gimple use_stmt, defvar_def;
>        imm_use_iterator ui;
>        bool fail = false;
> @@ -157,22 +150,21 @@ dse_possible_dead_store_p (gimple stmt,
>               /* Do not consider the PHI as use if it dominates the
>                  stmt defining the virtual operand we are processing,
>                  we have processed it already in this case.  */
>               if (gimple_bb (defvar_def) != gimple_bb (use_stmt)
>                   && !dominated_by_p (CDI_DOMINATORS,
>                                       gimple_bb (defvar_def),
>                                       gimple_bb (use_stmt)))
>                 temp = use_stmt;
>             }
>           /* If the statement is a use the store is not dead.  */
> -         else if (ref_maybe_used_by_stmt_p (use_stmt,
> -                                            gimple_assign_lhs (stmt)))
> +         else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
>             {
>               fail = true;
>               BREAK_FROM_IMM_USE_STMT (ui);
>             }
>           /* If this is a store, remember it or bail out if we have
>              multiple ones (the will be in different CFG parts then).  */
>           else if (gimple_vdef (use_stmt))
>             {
>               if (temp)
>                 {
> @@ -184,29 +176,29 @@ dse_possible_dead_store_p (gimple stmt,
>         }
>
>        if (fail)
>         return false;
>
>        /* If we didn't find any definition this means the store is dead
>           if it isn't a store to global reachable memory.  In this case
>          just pretend the stmt makes itself dead.  Otherwise fail.  */
>        if (!temp)
>         {
> -         if (stmt_may_clobber_global_p (stmt))
> +         if (ref_may_alias_global_p (ref))
>             return false;
>
>           temp = stmt;
>           break;
>         }
>      }
>    /* Continue walking until we reach a kill.  */
> -  while (!stmt_kills_ref_p (temp, gimple_assign_lhs (stmt)));
> +  while (!stmt_kills_ref_p (temp, ref));
>
>    *use_stmt = temp;
>
>    return true;
>  }
>
>
>  /* Attempt to eliminate dead stores in the statement referenced by BSI.
>
>     A dead store is a store into a memory location which will later be
> @@ -221,75 +213,119 @@ dse_possible_dead_store_p (gimple stmt,
>  static void
>  dse_optimize_stmt (gimple_stmt_iterator *gsi)
>  {
>    gimple stmt = gsi_stmt (*gsi);
>
>    /* If this statement has no virtual defs, then there is nothing
>       to do.  */
>    if (!gimple_vdef (stmt))
>      return;
>
> -  /* We know we have virtual definitions.  If this is a GIMPLE_ASSIGN
> -     that's not also a function call, then record it into our table.  */
> -  if (is_gimple_call (stmt) && gimple_call_fndecl (stmt))
> -    return;
> -
>    /* Don't return early on *this_2(D) ={v} {CLOBBER}.  */
>    if (gimple_has_volatile_ops (stmt)
>        && (!gimple_clobber_p (stmt)
>           || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
>      return;
>
> +  /* We know we have virtual definitions.  We can handle assignments and
> +     some builtin calls.  */
> +  if (is_gimple_call (stmt))

  if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))

which also does argument verification

> +    {
> +      tree callee = gimple_call_fndecl (stmt);
> +      if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
> +       return;
> +      switch (DECL_FUNCTION_CODE (callee))
> +       {
> +         case BUILT_IN_MEMCPY:
> +         case BUILT_IN_MEMMOVE:
> +         case BUILT_IN_MEMSET:
> +           {
> +             gimple use_stmt;
> +             ao_ref ref;
> +             tree size = NULL_TREE;
> +             int nargs = gimple_call_num_args (stmt);
> +             if (nargs < 2)
> +               return;
> +             if (nargs == 3)
> +               size = gimple_call_arg (stmt, 2);
> +             tree ptr = gimple_call_arg (stmt, 0);
> +             ao_ref_init_from_ptr_and_size (&ref, ptr, size);
> +             if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
> +               return;
> +
> +             if (dump_file && (dump_flags & TDF_DETAILS))
> +               {
> +                 fprintf (dump_file, "  Deleted dead store '");

dead call

> +                 print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags,
> 0);
> +                 fprintf (dump_file, "'\n");
> +               }
> +
> +             tree lhs = gimple_call_lhs (stmt);
> +             if (lhs)
> +               {
> +                 gimple new_stmt = gimple_build_assign (lhs, ptr);
> +                 unlink_stmt_vdef (stmt);
> +                 gsi_replace (gsi, new_stmt, true);

You may need eh cleanup here as well.

Bonus points if you make gsi_replace return whether
maybe_clean_or_replace_eh_stmt returned true.

> +               }
> +             else
> +               {
> +                 /* Then we need to fix the operand of the consuming stmt.
> */
> +                 unlink_stmt_vdef (stmt);
> +
> +                 /* Remove the dead store.  */
> +                 basic_block bb = gimple_bb (stmt);
> +                 if (gsi_remove (gsi, true))
> +                   bitmap_set_bit (need_eh_cleanup, bb->index);
> +               }
> +             break;
> +           }
> +         default:
> +           return;
> +       }
> +    }
> +
>    if (is_gimple_assign (stmt))
>      {
>        gimple use_stmt;
>
> -      if (!dse_possible_dead_store_p (stmt, &use_stmt))
> -       return;
> +      /* Self-assignments are zombies.  */
> +      if (operand_equal_p (gimple_assign_rhs1 (stmt),
> +                          gimple_assign_lhs (stmt), 0))
> +       use_stmt = stmt;
> +      else
> +       {
> +         ao_ref ref;
> +         ao_ref_init (&ref, gimple_assign_lhs (stmt));
> +         if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
> +           return;
> +       }
>
>        /* Now we know that use_stmt kills the LHS of stmt.  */
>
>        /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
>          another clobber stmt.  */
>        if (gimple_clobber_p (stmt)
>           && !gimple_clobber_p (use_stmt))
>         return;
>
> -      basic_block bb;
> -
> -      /* If use_stmt is or might be a nop assignment, e.g. for
> -          struct { ... } S a, b, *p; ...
> -          b = a; b = b;
> -        or
> -          b = a; b = *p; where p might be &b,
> -        or
> -           *p = a; *p = b; where p might be &b,
> -        or
> -           *p = *u; *p = *v; where p might be v, then USE_STMT
> -         acts as a use as well as definition, so store in STMT
> -         is not dead.  */
> -      if (stmt != use_stmt
> -         && ref_maybe_used_by_stmt_p (use_stmt, gimple_assign_lhs (stmt)))
> -       return;
> -

I don't see how you can remove this code?

Otherwise looks good to me.

Thanks,
RIchard.

>        if (dump_file && (dump_flags & TDF_DETAILS))
>         {
>           fprintf (dump_file, "  Deleted dead store '");
>           print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
>           fprintf (dump_file, "'\n");
>         }
>
>        /* Then we need to fix the operand of the consuming stmt.  */
>        unlink_stmt_vdef (stmt);
>
>        /* Remove the dead store.  */
> -      bb = gimple_bb (stmt);
> +      basic_block bb = gimple_bb (stmt);
>        if (gsi_remove (gsi, true))
>         bitmap_set_bit (need_eh_cleanup, bb->index);
>
>        /* And release any SSA_NAMEs set in this statement back to the
>          SSA_NAME manager.  */
>        release_defs (stmt);
>      }
>  }
>
>  class dse_dom_walker : public dom_walker
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]