Improve DSE in the presence of calls

[Easwaran Raman <eraman at google dot com>]

Hi,
 This patch improves RTL DSE by not assuming that calls read all
memory locations. With this patch, calls are assumed to read any
non-frame memory and any stack variables that can potentially escape.
This patch partly addresses PR rtl-optimization/44194. Bootstraps and
no test regressions. OK for trunk?

Thanks,
Easwaran

2011-04-22  Easwaran Raman  <eraman@google.com>

PR rtl-optimization/44194
	* dse.c (header files): Include tree-flow.h.
	(group_info): Add fields.
	(globals): Add a new variable kill_on_calls.
	(get_group_info): Initialize added fields.
	(dse_step0): Initialize kill_on_calls.
	(can_escape): New function.
	(record_store): Pass EXPR corresponding to MEM to
	set_usage_bits.
	(dse_step2_nospill): Set kill_on_calls based on
	group->escaped_*.
	(scan_reads_nospill): Handle call instructions.
	(find_insn_before_first_wild_read): Remove the function.
	(dse_step3_scan): Remove call to find_insn_before_first_wild_read.
	(dse_step5_nospill): Do not kill everything on call.

testsuite/ChangeLog:

2011-04-22  Easwaran Raman  <eraman@google.com>

PR rtl-optimization/44194
	* gcc.dg/pr44194-1.c: New test.

Index: gcc/testsuite/gcc.dg/pr44194-1.c
===================================================================
--- gcc/testsuite/gcc.dg/pr44194-1.c	(revision 0)
+++ gcc/testsuite/gcc.dg/pr44194-1.c	(revision 0)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-rtl-dse1" } */
+#include <stdint.h>
+
+struct twoints { uint64_t a, b; } foo();
+void bar(uint64_t a, uint64_t b);
+
+void func() {
+  struct twoints s = foo();
+  bar(s.a, s.b);
+}
+/* { dg-final { scan-rtl-dump "global deletions = 2"  "dse1" } } */
+/* { dg-final { cleanup-rtl-dump "dse1" } } */
Index: gcc/dse.c
===================================================================
--- gcc/dse.c	(revision 172844)
+++ gcc/dse.c	(working copy)
@@ -48,6 +48,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "dbgcnt.h"
 #include "target.h"
 #include "params.h"
+#include "tree-flow.h"
 
 /* This file contains three techniques for performing Dead Store
    Elimination (dse).
@@ -501,6 +502,11 @@ struct group_info
      deleted.  */
   bitmap store1_n, store1_p, store2_n, store2_p;
 
+  /* These bitmaps keep track of offsets in this group escape this function.
+     An offset escapes if it corresponds to a named variable whose
+     addressable flag is set.  */
+  bitmap escaped_n, escaped_p;
+
   /* The positions in this bitmap have the same assignments as the in,
      out, gen and kill bitmaps.  This bitmap is all zeros except for
      the positions that are occupied by stores for this group.  */
@@ -588,6 +594,9 @@ static int spill_deleted;
 
 static bitmap all_blocks;
 
+/* Locations that are killed by calls in the global phase.  */
+static bitmap kill_on_calls;
+
 /* The number of bits used in the global bitmaps.  */
 static unsigned int current_position;
 
@@ -692,6 +701,8 @@ get_group_info (rtx base)
 	  gi->store1_p = BITMAP_ALLOC (NULL);
 	  gi->store2_n = BITMAP_ALLOC (NULL);
 	  gi->store2_p = BITMAP_ALLOC (NULL);
+	  gi->escaped_p = BITMAP_ALLOC (NULL);
+	  gi->escaped_n = BITMAP_ALLOC (NULL);
 	  gi->group_kill = BITMAP_ALLOC (NULL);
 	  gi->process_globally = false;
 	  gi->offset_map_size_n = 0;
@@ -714,6 +725,8 @@ get_group_info (rtx base)
       gi->store1_p = BITMAP_ALLOC (NULL);
       gi->store2_n = BITMAP_ALLOC (NULL);
       gi->store2_p = BITMAP_ALLOC (NULL);
+      gi->escaped_p = BITMAP_ALLOC (NULL);
+      gi->escaped_n = BITMAP_ALLOC (NULL);
       gi->group_kill = BITMAP_ALLOC (NULL);
       gi->process_globally = false;
       gi->frame_related =
@@ -739,6 +752,7 @@ dse_step0 (void)
   spill_deleted = 0;
 
   scratch = BITMAP_ALLOC (NULL);
+  kill_on_calls = BITMAP_ALLOC (NULL);
 
   rtx_store_info_pool
     = create_alloc_pool ("rtx_store_info_pool",
@@ -881,31 +895,48 @@ delete_dead_store_insn (insn_info_t insn_info)
   insn_info->wild_read = false;
 }
 
+/* Check if EXPR can possibly escape the current function scope.  */
+static bool
+can_escape (tree expr)
+{
+  tree base;
+  if (!expr)
+    return true;
+  base = get_base_address (expr);
+  if (DECL_P (base)
+      && !may_be_aliased (base))
+    return false;
+  return true;
+}
 
 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
    OFFSET and WIDTH.  */
 
 static void
-set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width)
+set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width,
+                tree expr)
 {
   HOST_WIDE_INT i;
-
+  bool expr_escapes = can_escape (expr);
   if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
     for (i=offset; i<offset+width; i++)
       {
 	bitmap store1;
 	bitmap store2;
+        bitmap escaped;
 	int ai;
 	if (i < 0)
 	  {
 	    store1 = group->store1_n;
 	    store2 = group->store2_n;
+	    escaped = group->escaped_n;
 	    ai = -i;
 	  }
 	else
 	  {
 	    store1 = group->store1_p;
 	    store2 = group->store2_p;
+	    escaped = group->escaped_p;
 	    ai = i;
 	  }
 
@@ -924,6 +955,8 @@ static void
 		  group->offset_map_size_p = ai;
 	      }
 	  }
+        if (expr_escapes)
+          bitmap_set_bit (escaped, ai);
       }
 }
 
@@ -1355,9 +1388,10 @@ record_store (rtx body, bb_info_t bb_info)
 
       group_info_t group
 	= VEC_index (group_info_t, rtx_group_vec, group_id);
+      tree expr = MEM_EXPR (mem);
 
       store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
-      set_usage_bits (group, offset, width);
+      set_usage_bits (group, offset, width, expr);
 
       if (dump_file)
 	fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
@@ -2788,7 +2822,6 @@ dse_step2_nospill (void)
   /* Position 0 is unused because 0 is used in the maps to mean
      unused.  */
   current_position = 1;
-
   FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
     {
       bitmap_iterator bi;
@@ -2804,12 +2837,16 @@ dse_step2_nospill (void)
       EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
 	{
 	  bitmap_set_bit (group->group_kill, current_position);
+          if (bitmap_bit_p (group->escaped_n, j))
+	    bitmap_set_bit (kill_on_calls, current_position);
 	  group->offset_map_n[j] = current_position++;
 	  group->process_globally = true;
 	}
       EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
 	{
 	  bitmap_set_bit (group->group_kill, current_position);
+          if (bitmap_bit_p (group->escaped_p, j))
+	    bitmap_set_bit (kill_on_calls, current_position);
 	  group->offset_map_p[j] = current_position++;
 	  group->process_globally = true;
 	}
@@ -3040,7 +3077,21 @@ scan_reads_nospill (insn_info_t insn_info, bitmap
 	    bitmap_and_compl_into (gen, group->group_kill);
 	  }
     }
-
+  if (CALL_P (insn_info->insn))
+    {
+      /* Kill all non-frame related stores.  Kill all stores of variables that
+         escape.  */
+      if (kill)
+        bitmap_ior_into (kill, kill_on_calls);
+      bitmap_and_compl_into (gen, kill_on_calls);
+      FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
+	if (group->process_globally && !group->frame_related)
+	  {
+	    if (kill)
+	      bitmap_ior_into (kill, group->group_kill);
+	    bitmap_and_compl_into (gen, group->group_kill);
+	  }
+    }
   while (read_info)
     {
       FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
@@ -3125,35 +3176,6 @@ scan_reads_spill (read_info_t read_info, bitmap ge
 }
 
 
-/* Return the insn in BB_INFO before the first wild read or if there
-   are no wild reads in the block, return the last insn.  */
-
-static insn_info_t
-find_insn_before_first_wild_read (bb_info_t bb_info)
-{
-  insn_info_t insn_info = bb_info->last_insn;
-  insn_info_t last_wild_read = NULL;
-
-  while (insn_info)
-    {
-      if (insn_info->wild_read)
-	{
-	  last_wild_read = insn_info->prev_insn;
-	  /* Block starts with wild read.  */
-	  if (!last_wild_read)
-	    return NULL;
-	}
-
-      insn_info = insn_info->prev_insn;
-    }
-
-  if (last_wild_read)
-    return last_wild_read;
-  else
-    return bb_info->last_insn;
-}
-
-
 /* Scan the insns in BB_INFO starting at PTR and going to the top of
    the block in order to build the gen and kill sets for the block.
    We start at ptr which may be the last insn in the block or may be
@@ -3167,11 +3189,7 @@ dse_step3_scan (bool for_spills, basic_block bb)
   bb_info_t bb_info = bb_table[bb->index];
   insn_info_t insn_info;
 
-  if (for_spills)
-    /* There are no wild reads in the spill case.  */
-    insn_info = bb_info->last_insn;
-  else
-    insn_info = find_insn_before_first_wild_read (bb_info);
+  insn_info = bb_info->last_insn;
 
   /* In the spill case or in the no_spill case if there is no wild
      read in the block, we will need a kill set.  */
@@ -3558,18 +3576,7 @@ dse_step5_nospill (void)
 	      && (!deleted))
 	    {
 	      scan_stores_nospill (insn_info->store_rec, v, NULL);
-	      if (insn_info->wild_read)
-		{
-		  if (dump_file)
-		    fprintf (dump_file, "wild read\n");
-		  bitmap_clear (v);
-		}
-	      else if (insn_info->read_rec)
-		{
-		  if (dump_file)
-		    fprintf (dump_file, "regular read\n");
-		  scan_reads_nospill (insn_info, v, NULL);
-		}
+              scan_reads_nospill (insn_info, v, NULL);
 	    }
 
 	  insn_info = insn_info->prev_insn;