gcc-patches@gcc.gnu.org
[Top] [All Lists]

[PATCH] Improve DCE of trailing dead stores

Subject: [PATCH] Improve DCE of trailing dead stores
From: Richard Guenther
Date: Tue, 30 Jun 2009 17:20:41 +0200 CEST
This improves DCE of stores at the end of functions.  It removes the
need to mark aliased stores necessary by other stores by relying on
walking all reaching definitions (but only a single time, guaranteed
via the global visited bitmap) from each aliased load.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2009-06-30  Richard Guenther  <rguenther@xxxxxxx>

        * tree-ssa-dce.c (mark_all_reaching_defs_necessary_1): Always
        continue walking.
        (propagate_necessity): Do not mark reaching defs of stores
        as necessary.

        * gcc.dg/tree-ssa/ssa-dce-6.c: New testcase.

Index: gcc/tree-ssa-dce.c
===================================================================
*** gcc/tree-ssa-dce.c  (revision 149086)
--- gcc/tree-ssa-dce.c  (working copy)
*************** mark_all_reaching_defs_necessary_1 (ao_r
*** 550,558 ****
        return false;
      }
  
-   /* But can stop after the first necessary statement.  */
    mark_operand_necessary (vdef);
!   return true;
  }
  
  static void
--- 550,558 ----
        return false;
      }
  
    mark_operand_necessary (vdef);
! 
!   return false;
  }
  
  static void
*************** propagate_necessity (struct edge_list *e
*** 671,688 ****
             For 1) we mark all reaching may-defs as necessary, stopping
             at dominating kills.  For 2) we want to mark all dominating
             references necessary, but non-aliased ones which we handle
!            in 1).  Instead of doing so for each load we rely on the
!            worklist to eventually reach all dominating references and
!            instead just mark the immediately dominating references
!            as necessary (but skipping non-aliased ones).  */
  
          if (is_gimple_call (stmt))
            {
              unsigned i;
  
              /* Calls implicitly load from memory, their arguments
!                in addition may explicitly perform memory loads.
!                This also ensures propagation for case 2 for stores.  */
              mark_all_reaching_defs_necessary (stmt);
              for (i = 0; i < gimple_call_num_args (stmt); ++i)
                {
--- 671,685 ----
             For 1) we mark all reaching may-defs as necessary, stopping
             at dominating kills.  For 2) we want to mark all dominating
             references necessary, but non-aliased ones which we handle
!            in 1).  By keeping a global visited bitmap for references
!            we walk for 2) we avoid quadratic behavior for those.  */
  
          if (is_gimple_call (stmt))
            {
              unsigned i;
  
              /* Calls implicitly load from memory, their arguments
!                in addition may explicitly perform memory loads.  */
              mark_all_reaching_defs_necessary (stmt);
              for (i = 0; i < gimple_call_num_args (stmt); ++i)
                {
*************** propagate_necessity (struct edge_list *e
*** 696,702 ****
            }
          else if (gimple_assign_single_p (stmt))
            {
!             tree lhs, rhs;
              bool rhs_aliased = false;
              /* If this is a load mark things necessary.  */
              rhs = gimple_assign_rhs1 (stmt);
--- 693,699 ----
            }
          else if (gimple_assign_single_p (stmt))
            {
!             tree rhs;
              bool rhs_aliased = false;
              /* If this is a load mark things necessary.  */
              rhs = gimple_assign_rhs1 (stmt);
*************** propagate_necessity (struct edge_list *e
*** 708,719 ****
                  else
                    rhs_aliased = true;
                }
!             /* If this is an aliased store, mark things necessary.
!                This is where we make sure to propagate for case 2.  */
!             lhs = gimple_assign_lhs (stmt);
!             if (rhs_aliased
!                 || (TREE_CODE (lhs) != SSA_NAME
!                     && ref_may_be_aliased (lhs)))
                mark_all_reaching_defs_necessary (stmt);
            }
          else if (gimple_code (stmt) == GIMPLE_RETURN)
--- 705,711 ----
                  else
                    rhs_aliased = true;
                }
!             if (rhs_aliased)
                mark_all_reaching_defs_necessary (stmt);
            }
          else if (gimple_code (stmt) == GIMPLE_RETURN)
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-6.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-6.c   (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-6.c   (revision 0)
***************
*** 0 ****
--- 1,24 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-cddce1" } */
+ 
+ struct object { int field; };
+ void o(struct object *);
+ int globl;
+ void t(int x)
+ {
+   struct object a, b;
+   struct object *p;
+   o(&a);
+   if (x)
+     p = &a;
+   else
+     p = &b;
+   p->field = 1;
+   globl = 0;
+   return;
+ }
+ 
+ /* The global store should not prevent deleting the store to p->field.  */
+ 
+ /* { dg-final { scan-tree-dump-not "p_.->field" "cddce1" } } */
+ /* { dg-final { cleanup-tree-dump "cddce1" } } */

<Prev in Thread] Current Thread [Next in Thread>
  • [PATCH] Improve DCE of trailing dead stores, Richard Guenther <=