[PATCH] Fix PR tree-optimization/17724

[PATCH] Fix PR tree-optimization/17724

[Jakub Jelinek]

[-- Attachment #1: Type: text/plain, Size: 1900 bytes --]

Hi!

The fold_all_builtin patch to gimplify results of ccp_fold_builtin
uncovered what it seems to be a latent problem - some basic block removals
don't recompute dominators of their neighbouring basic blocks.
Particularly in one of the attached testcases bb1->bb3, bb1->bb4 and
bb3->bb4 are EH edges:
         +---+
         |bb0|
         +---+
          / \
        /    \
       /      \
      v        v
    +---+    +---+
    |bb1|--->|bb2|
    +---+    +---+
     / \       |
    /   \      |
   /     \     |
  v       v    |
+---+   +---+  |
|bb3|-->|bb4|  |
+---+   +---+  |
  \            |
   \         +---+
    -------->|bb5|
             +---+
               |
              ---
               -
strcpy which due to the missing throw () in the testcase can throw
is replaced by code that can't throw, thus the EH edges are removed
(by tree_purge_dead_eh_edges) and in the end cleanup_tree_cfg
kicks in.  This in turn calls delete_unreachable_blocks that deletes
bb3 and bb4 basic blocks.
The problem is that immediate dominator of bb5 before all of this was
bb0, but after bb3 and bb4 basic blocks are removed, immediate dominator
is bb2; there is nothing that updates the dominator info of bb5 though.

Attached are 3 patches, first and third patch were bootstrapped and
regtested on i386-redhat-linux, the second one doesn't work but is
included for completeness what I tried.

The first patch calls free_dominance_info in cleanup_tree_cfg whenever
delete_unreachable_blocks deleted some basic blocks.  It should be safe, but
might be expensive.

The second patch tried to recompute dominators in a routine called
from delete_basic_block, but apparently some callers of delete_basic_block
don't expect the recomputation.

The third one recomputes dominators (and post-dominators) of neighbours
of unreachable basic blocks after they are deleted by
delete_unreachable_blocks.

	Jakub

[-- Attachment #2: delete-unreachable-blocks1.patch --]
[-- Type: text/plain, Size: 5463 bytes --]

2004-10-07  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/17724
	* tree-cfg.c (tree_purge_dead_eh_edges): Recompute dominator for the
	EH block.
	(cleanup_tree_cfg): Free dominators if any delete_unreachable_blocks
	deleted some basic block.

	* g++.dg/opt/pr17724-1.C: New test.
	* g++.dg/opt/pr17724-2.C: New test.
	* g++.dg/opt/pr17724-3.C: New test.
	* g++.dg/opt/pr17724-4.C: New test.
	* g++.dg/opt/pr17724-5.C: New test.
	* g++.dg/opt/pr17724-6.C: New test.

--- gcc/tree-cfg.c.jj	2004-10-02 10:46:07.000000000 +0200
+++ gcc/tree-cfg.c	2004-10-02 11:19:53.042030301 +0200
@@ -713,11 +713,13 @@ bool
 cleanup_tree_cfg (void)
 {
-  bool retval = false;
+  bool retval;
+  bool blocks_deleted;
 
   timevar_push (TV_TREE_CLEANUP_CFG);
 
   retval = cleanup_control_flow ();
-  retval |= delete_unreachable_blocks ();
+  blocks_deleted = delete_unreachable_blocks ();
+  retval |= blocks_deleted;
 
   /* thread_jumps() sometimes leaves further transformation
      opportunities for itself, so iterate on it until nothing
@@ -743,6 +745,13 @@ cleanup_tree_cfg (void)
     }
 #endif
 
+  /* If blocks were deleted, the dominance info might be outdated.  */
+  if (blocks_deleted)
+    {
+      free_dominance_info (CDI_DOMINATORS);
+      free_dominance_info (CDI_POST_DOMINATORS);
+    }
+
   /* Merging the blocks creates no new opportunities for the other
      optimizations, so do it here.  */
   merge_seq_blocks ();
@@ -5089,7 +5098,11 @@ tree_purge_dead_eh_edges (basic_block bb
     {
       if (e->flags & EDGE_EH)
 	{
+	  basic_block dest = e->dest, dom;
+
 	  ssa_remove_edge (e);
+	  dom = recount_dominator (CDI_DOMINATORS, dest);
+	  set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 	  changed = true;
 	}
       else
--- gcc/testsuite/g++.dg/opt/pr17724-4.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-4.C	2004-10-02 11:29:21.803990546 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern "C" char *strcpy (char* d, const char* s);
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-6.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-6.C	2004-10-02 11:28:39.000000000 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern char *strcpy (char* d, const char* s);
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-1.C.jj	2004-10-02 11:13:45.797278812 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-1.C	2004-10-02 11:13:45.797278812 +0200
@@ -0,0 +1,23 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+namespace N { char *strcpy (char *, const char *); }
+extern "C" char *strcpy (char *, const char *) throw ();
+inline char *N::strcpy (char *s, const char *t) { return ::strcpy (s, t); }
+
+struct S { ~S (); };
+int foo ();
+
+int
+main ()
+{
+  S s;
+  int a;
+  char b[64];
+  N::strcpy (b, "ABCDEFGHIJKLM");
+  while ((a = foo ()) != -1)
+    if (a)
+      return -1;
+  return 0;
+}
--- gcc/testsuite/g++.dg/opt/pr17724-2.C.jj	2004-10-02 11:13:45.797278812 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-2.C	2004-10-02 11:13:45.797278812 +0200
@@ -0,0 +1,23 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+namespace N { char *strcpy (char *, const char *); }
+extern "C" char *strcpy (char *, const char *);
+inline char *N::strcpy (char *s, const char *t) { return ::strcpy (s, t); }
+
+struct S { ~S (); };
+int foo ();
+
+int
+main ()
+{
+  S s;
+  int a;
+  char b[64];
+  N::strcpy (b, "ABCDEFGHIJKLM");
+  while ((a = foo ()) != -1)
+    if (a)
+      return -1;
+  return 0;
+}
--- gcc/testsuite/g++.dg/opt/pr17724-3.C.jj	2004-10-02 11:27:29.650919752 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-3.C	2004-10-02 11:29:13.933389195 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern "C" char *strcpy (char* d, const char* s) throw ();
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-5.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-5.C	2004-10-02 11:29:29.275662780 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern char *strcpy (char* d, const char* s) throw ();
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}

[-- Attachment #3: delete-unreachable-blocks2.patch --]
[-- Type: text/plain, Size: 5738 bytes --]

2004-10-07  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/17724
	* tree-cfg.c (tree_purge_dead_eh_edges): Recompute dominator for the
	EH block.
	(remove_phi_nodes_and_edges_for_unreachab): Recompute dominators
	and post-dominators for predecessors and successors.

	* g++.dg/opt/pr17724-1.C: New test.
	* g++.dg/opt/pr17724-2.C: New test.
	* g++.dg/opt/pr17724-3.C: New test.
	* g++.dg/opt/pr17724-4.C: New test.
	* g++.dg/opt/pr17724-5.C: New test.
	* g++.dg/opt/pr17724-6.C: New test.

--- gcc/tree-cfg.c	2004-10-02 11:19:53.042030301 +0200
+++ gcc/tree-cfg.c	2004-10-02 23:17:12.229321933 +0200
@@ -1784,6 +1784,8 @@
 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
 {
   tree phi;
+  basic_block *succs = NULL;
+  int nsuccs = 0;
 
   /* Since this block is no longer reachable, we can just delete all
      of its PHI nodes.  */
@@ -1795,9 +1797,32 @@
       phi = next;
     }
 
+  if (dom_computed[CDI_DOMINATORS])
+    succs = xmalloc (sizeof (basic_block *) * EDGE_COUNT (bb->succs));
+
   /* Remove edges to BB's successors.  */
   while (EDGE_COUNT (bb->succs) > 0)
-    ssa_remove_edge (EDGE_SUCC (bb, 0));
+    {
+      if (succs != NULL
+	  && EDGE_SUCC (bb, 0)->dest != bb
+	  && EDGE_COUNT (EDGE_SUCC (bb, 0)->dest->preds) > 1)
+	succs[nsuccs++] = EDGE_SUCC (bb, 0)->dest;
+      ssa_remove_edge (EDGE_SUCC (bb, 0));
+    }
+
+  if (succs)
+    {
+      int i;
+
+      for (i = 0; i < nsuccs; ++i)
+	{
+	  basic_block dom = recount_dominator (CDI_DOMINATORS, succs[i]);
+
+	  if (dom != get_immediate_dominator (CDI_DOMINATORS, succs[i]))
+	    set_immediate_dominator (CDI_DOMINATORS, succs[i], dom);
+	}
+      free (succs);
+    }
 }
 
 
@@ -5089,7 +5114,12 @@
     {
       if (e->flags & EDGE_EH)
 	{
+	  basic_block dest = e->dest, dom;
+
 	  ssa_remove_edge (e);
+	  dom = recount_dominator (CDI_DOMINATORS, dest);
+	  if (dom != get_immediate_dominator (CDI_DOMINATORS, dest))
+	    set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 	  changed = true;
 	}
       else
--- gcc/testsuite/g++.dg/opt/pr17724-4.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-4.C	2004-10-02 11:29:21.803990546 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern "C" char *strcpy (char* d, const char* s);
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-6.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-6.C	2004-10-02 11:28:39.000000000 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern char *strcpy (char* d, const char* s);
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-1.C.jj	2004-10-02 11:13:45.797278812 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-1.C	2004-10-02 11:13:45.797278812 +0200
@@ -0,0 +1,23 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+namespace N { char *strcpy (char *, const char *); }
+extern "C" char *strcpy (char *, const char *) throw ();
+inline char *N::strcpy (char *s, const char *t) { return ::strcpy (s, t); }
+
+struct S { ~S (); };
+int foo ();
+
+int
+main ()
+{
+  S s;
+  int a;
+  char b[64];
+  N::strcpy (b, "ABCDEFGHIJKLM");
+  while ((a = foo ()) != -1)
+    if (a)
+      return -1;
+  return 0;
+}
--- gcc/testsuite/g++.dg/opt/pr17724-2.C.jj	2004-10-02 11:13:45.797278812 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-2.C	2004-10-02 11:13:45.797278812 +0200
@@ -0,0 +1,23 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+namespace N { char *strcpy (char *, const char *); }
+extern "C" char *strcpy (char *, const char *);
+inline char *N::strcpy (char *s, const char *t) { return ::strcpy (s, t); }
+
+struct S { ~S (); };
+int foo ();
+
+int
+main ()
+{
+  S s;
+  int a;
+  char b[64];
+  N::strcpy (b, "ABCDEFGHIJKLM");
+  while ((a = foo ()) != -1)
+    if (a)
+      return -1;
+  return 0;
+}
--- gcc/testsuite/g++.dg/opt/pr17724-3.C.jj	2004-10-02 11:27:29.650919752 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-3.C	2004-10-02 11:29:13.933389195 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern "C" char *strcpy (char* d, const char* s) throw ();
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-5.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-5.C	2004-10-02 11:29:29.275662780 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern char *strcpy (char* d, const char* s) throw ();
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}

[-- Attachment #4: delete-unreachable-blocks3.patch --]
[-- Type: text/plain, Size: 7084 bytes --]

2004-10-07  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/17724
	* tree-cfg.c (tree_purge_dead_eh_edges): Recompute dominator for the
	EH block.
	(cleanup_tree_cfg): Remove unnecessary retval initialization.
	* cfgcleanup.c (delete_unreachable_blocks): Recompute dominators
	and post-dominators for predecessors and successors of deleted
	unreachable basic blocks.

	* g++.dg/opt/pr17724-1.C: New test.
	* g++.dg/opt/pr17724-2.C: New test.
	* g++.dg/opt/pr17724-3.C: New test.
	* g++.dg/opt/pr17724-4.C: New test.
	* g++.dg/opt/pr17724-5.C: New test.
	* g++.dg/opt/pr17724-6.C: New test.

--- gcc/cfgcleanup.c.jj	2004-09-28 04:19:43.000000000 -0400
+++ gcc/cfgcleanup.c	2004-10-07 12:30:11.000000000 -0400
@@ -2029,9 +2029,18 @@ delete_unreachable_blocks (void)
 {
   bool changed = false;
   basic_block b, next_bb;
+  basic_block *succs = NULL, *preds = NULL;
+  int nsuccs = 0, npreds = 0, i;
+  edge_iterator ei;
+  edge e;
 
   find_unreachable_blocks ();
 
+  if (dom_computed[CDI_DOMINATORS])
+    succs = xmalloc (sizeof (basic_block *) * n_basic_blocks);
+  if (dom_computed[CDI_POST_DOMINATORS])
+    preds = xmalloc (sizeof (basic_block *) * n_basic_blocks);
+
   /* Delete all unreachable basic blocks.  */
 
   for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
@@ -2040,6 +2049,22 @@ delete_unreachable_blocks (void)
 
       if (!(b->flags & BB_REACHABLE))
 	{
+	  if (succs)
+	    FOR_EACH_EDGE (e, ei, b->succs)
+	      if ((e->dest->flags & (BB_REACHABLE | BB_VISITED))
+	          == BB_REACHABLE)
+                {
+	          succs[nsuccs++] = e->dest;
+	          e->dest->flags |= BB_VISITED;
+                }
+	  if (preds)
+	    FOR_EACH_EDGE (e, ei, b->preds)
+	      if ((e->src->flags & (BB_REACHABLE | BB_VISITED))
+	          == BB_REACHABLE)
+                {
+	          preds[npreds++] = e->src;
+	          e->src->flags |= BB_VISITED;
+                }
 	  delete_basic_block (b);
 	  changed = true;
 	}
@@ -2047,6 +2072,33 @@ delete_unreachable_blocks (void)
 
   if (changed)
     tidy_fallthru_edges ();
+
+  if (succs)
+    {
+      for (i = 0; i < nsuccs; ++i)
+        {
+          basic_block dom = recount_dominator (CDI_DOMINATORS, succs[i]);
+
+          succs[i]->flags &= ~BB_VISITED;
+          if (dom != get_immediate_dominator (CDI_DOMINATORS, succs[i]))
+            set_immediate_dominator (CDI_DOMINATORS, succs[i], dom);
+        }
+      free (succs);        
+    }
+
+  if (preds)
+    {
+      for (i = 0; i < npreds; ++i)
+        {
+          basic_block dom = recount_dominator (CDI_POST_DOMINATORS, preds[i]);
+
+          preds[i]->flags &= ~BB_VISITED;
+          if (dom != get_immediate_dominator (CDI_POST_DOMINATORS, preds[i]))
+            set_immediate_dominator (CDI_POST_DOMINATORS, preds[i], dom);
+        }
+      free (preds);        
+    }
+
   return changed;
 }
 
--- gcc/tree-cfg.c.jj	2004-10-02 04:46:07.000000000 -0400
+++ gcc/tree-cfg.c	2004-10-07 12:28:44.000000000 -0400
@@ -5089,7 +5089,12 @@ tree_purge_dead_eh_edges (basic_block bb
     {
       if (e->flags & EDGE_EH)
 	{
+	  basic_block dest = e->dest, dom;
+
 	  ssa_remove_edge (e);
+	  dom = recount_dominator (CDI_DOMINATORS, dest);
+	  if (dom != get_immediate_dominator (CDI_DOMINATORS, dest))
+	    set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 	  changed = true;
 	}
       else
--- gcc/testsuite/g++.dg/opt/pr17724-4.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-4.C	2004-10-02 11:29:21.803990546 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern "C" char *strcpy (char* d, const char* s);
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-6.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-6.C	2004-10-02 11:28:39.000000000 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern char *strcpy (char* d, const char* s);
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-1.C.jj	2004-10-02 11:13:45.797278812 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-1.C	2004-10-02 11:13:45.797278812 +0200
@@ -0,0 +1,23 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+namespace N { char *strcpy (char *, const char *); }
+extern "C" char *strcpy (char *, const char *) throw ();
+inline char *N::strcpy (char *s, const char *t) { return ::strcpy (s, t); }
+
+struct S { ~S (); };
+int foo ();
+
+int
+main ()
+{
+  S s;
+  int a;
+  char b[64];
+  N::strcpy (b, "ABCDEFGHIJKLM");
+  while ((a = foo ()) != -1)
+    if (a)
+      return -1;
+  return 0;
+}
--- gcc/testsuite/g++.dg/opt/pr17724-2.C.jj	2004-10-02 11:13:45.797278812 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-2.C	2004-10-02 11:13:45.797278812 +0200
@@ -0,0 +1,23 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+namespace N { char *strcpy (char *, const char *); }
+extern "C" char *strcpy (char *, const char *);
+inline char *N::strcpy (char *s, const char *t) { return ::strcpy (s, t); }
+
+struct S { ~S (); };
+int foo ();
+
+int
+main ()
+{
+  S s;
+  int a;
+  char b[64];
+  N::strcpy (b, "ABCDEFGHIJKLM");
+  while ((a = foo ()) != -1)
+    if (a)
+      return -1;
+  return 0;
+}
--- gcc/testsuite/g++.dg/opt/pr17724-3.C.jj	2004-10-02 11:27:29.650919752 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-3.C	2004-10-02 11:29:13.933389195 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern "C" char *strcpy (char* d, const char* s) throw ();
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}
--- gcc/testsuite/g++.dg/opt/pr17724-5.C.jj	2004-10-02 11:27:29.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-5.C	2004-10-02 11:29:29.275662780 +0200
@@ -0,0 +1,24 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+extern char *strcpy (char* d, const char* s) throw ();
+
+class A { public: A (); ~A (); };
+
+inline char * B (char *s, const char *t)
+{ return ::strcpy (s, t); }
+
+class C { int D (void); int E; };
+
+int C::D (void)
+{
+  A a;
+  try
+    {
+      char z[22];
+      if (this->E) B (z, "");
+      return 0;
+    }
+  catch (int &f) { return -1; }
+}

Re: [PATCH] Fix PR tree-optimization/17724

[Kazu Hirata]

Hi Jakub,

> The first patch calls free_dominance_info in cleanup_tree_cfg whenever
> delete_unreachable_blocks deleted some basic blocks.  It should be safe, but
> might be expensive.

I guess so.  thread_jumps, which is called right after
delete_unreachable_blocks in cleanup_tree_cfg, tries to maintain the
dominator info, so if you are freeing it, you might want to remove the
code to maintain it in thread_jumps.

Kazu Hirata

Re: [PATCH] Fix PR tree-optimization/17724

[Jakub Jelinek]

On Thu, Oct 07, 2004 at 06:15:56PM -0400, Kazu Hirata wrote:
> Hi Jakub,
> 
> > The first patch calls free_dominance_info in cleanup_tree_cfg whenever
> > delete_unreachable_blocks deleted some basic blocks.  It should be safe, but
> > might be expensive.
> 
> I guess so.  thread_jumps, which is called right after
> delete_unreachable_blocks in cleanup_tree_cfg, tries to maintain the
> dominator info, so if you are freeing it, you might want to remove the
> code to maintain it in thread_jumps.

Yeah, my preferred patch is 3 (recomputing some dominators in
delete_unreachable_blocks).  Possibly if that turns out to be too expensive
when there are too many basic blocks as predecessors or successors of
unreachable blocks (that aren't unreachable themselves), we could add
later on some ceiling (the one 3rd of basic blocks below is completely
arbitrary), e.g.
  if (nsuccs * 3 > n_basic_blocks)
    free_dominance_info (CDI_DOMINATORS);
  else
    for (i = 0; i < nsuccs; ++i)
      recompute one by one;

	Jakub

Re: [PATCH] Fix PR tree-optimization/17724

[Jeffrey A Law]

On Thu, 2004-10-07 at 23:31, Jakub Jelinek wrote:
> On Thu, Oct 07, 2004 at 06:15:56PM -0400, Kazu Hirata wrote:
> > Hi Jakub,
> > 
> > > The first patch calls free_dominance_info in cleanup_tree_cfg whenever
> > > delete_unreachable_blocks deleted some basic blocks.  It should be safe, but
> > > might be expensive.
> > 
> > I guess so.  thread_jumps, which is called right after
> > delete_unreachable_blocks in cleanup_tree_cfg, tries to maintain the
> > dominator info, so if you are freeing it, you might want to remove the
> > code to maintain it in thread_jumps.
> 
> Yeah, my preferred patch is 3 (recomputing some dominators in
> delete_unreachable_blocks).  Possibly if that turns out to be too expensive
> when there are too many basic blocks as predecessors or successors of
> unreachable blocks (that aren't unreachable themselves), we could add
> later on some ceiling (the one 3rd of basic blocks below is completely
> arbitrary), e.g.
>   if (nsuccs * 3 > n_basic_blocks)
>     free_dominance_info (CDI_DOMINATORS);
>   else
>     for (i = 0; i < nsuccs; ++i)
>       recompute one by one;
Well, if you want a testcase you might peek at 15524; it's spending
over 20% of its time in the tree CFG cleanup code.  I haven't looked
into what it's doing that is so bloody bad, but it's clearly doing
something goofy (I'm up to my eyeballs in driving down the time for
DOM for that testcase right now :-)

Anyway, the only tidbit I could pass along is that the CFG cleanup
time has basically been unchanged, even with Kazu's recent work.

Jeff

Re: [PATCH] Fix PR tree-optimization/17724

[Andrew Pinski]

On Oct 8, 2004, at 3:20 PM, Jeffrey A Law wrote:

> Well, if you want a testcase you might peek at 15524; it's spending
> over 20% of its time in the tree CFG cleanup code.  I haven't looked
> into what it's doing that is so bloody bad, but it's clearly doing
> something goofy (I'm up to my eyeballs in driving down the time for
> DOM for that testcase right now :-)
>
> Anyway, the only tidbit I could pass along is that the CFG cleanup
> time has basically been unchanged, even with Kazu's recent work.

I filed PR 17895 with a slightly modified testcase from PR 15524
which shows that we spend 90% of the time in tree CFG cleanup.

The modification is removing the function call from each of the
case statement.

Thanks,
Andrew Pinski 

Re: [PATCH] Fix PR tree-optimization/17724

[Diego Novillo]

On Thu, 2004-10-07 at 16:04, Jakub Jelinek wrote:

> The third one recomputes dominators (and post-dominators) of neighbours
> of unreachable basic blocks after they are deleted by
> delete_unreachable_blocks.
> 
I like this one.  It looks OK and safe, so let's go with it.


Thanks.  Diego.

Re: [PATCH] Fix PR tree-optimization/17724

[Zdenek Dvorak]

Hello,

> > The third one recomputes dominators (and post-dominators) of neighbours
> > of unreachable basic blocks after they are deleted by
> > delete_unreachable_blocks.
> > 
> I like this one.  It looks OK and safe, so let's go with it.
> 
> 
> Thanks.  Diego.

could you please give me some time to look at the problem before you
commit the patch(es)?  It seems to me that it is wrong (or at least not
necessary).

Zdenek

Re: [PATCH] Fix PR tree-optimization/17724

[Zdenek Dvorak]

Hello,

> ----- Forwarded message from Diego Novillo <dnovillo@redhat.com> -----
> 
> Date: Fri, 08 Oct 2004 19:28:08 -0400
> From: Diego Novillo <dnovillo@redhat.com>
> To: Jakub Jelinek <jakub@redhat.com>
> Cc: Richard Henderson <rth@redhat.com>,
>         "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>
> Subject: Re: [PATCH] Fix PR tree-optimization/17724
> 
> On Thu, 2004-10-07 at 16:04, Jakub Jelinek wrote:
> 
> > The third one recomputes dominators (and post-dominators) of neighbours
> > of unreachable basic blocks after they are deleted by
> > delete_unreachable_blocks.
> > 
> I like this one.  It looks OK and safe, so let's go with it.
> 
> 
> Thanks.  Diego.
>
> ----- End forwarded message -----

this does not seem to be the right fix to me:

1) Change to delete_unreachable_blocks is not necessary.  As long as
   dominators are set correctly before delete_unreachable_blocks,
   they are also set correctly after it (since removal of unreachable
   blocks cannot affect any path from entry to basic block bb, and
   immediate dominator is determined from exactly these paths).

2) Change in tree_purge_dead_eh_edges also is not OK.
   tree_purge_dead_eh_edges may remove basically arbitrary edge.
   After removal of the edge, just locally updating the dominators
   of the destination of the edge is not sufficient, since also
   immediate dominators of other blocks may get changed.

3) The attempts to update postdominators are just wasted time, since
   we do not try to update those anywhere else (making updating of
   postdominators work would require changes on many more places,
   and so far it is not needed anywhere).

So the real problem for the bug is that tree_purge_dead_eh_edges
breaks the information about dominators irrepairably (at least in the
current state; it would be of course possible to write code to update
dominators after edge removal incrementally, but it would be relatively
complicated and I am not entirely sure it would pay up in the compile
time).  The right fix is simply to call free_dominance_info in
tree_purge_dead_eh_edges when the edge is removed.

Zdenek

[PATCH] Fix PR tree-optimization/17724

[Jakub Jelinek]

Hi!

This patch seems to fix the testcase (bootstrap/regtest still pending),
though I'm not sure if it is the right thing or the dominator should be
recomputed somewhere else (either at lower level, e.g. in remove_edge
or ssa_remove_edge, or in tree_purge_dead_eh_edges callers, or in
cleanup_tree_cfg).

2004-09-30  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/17724
	* tree-cfg.c (tree_purge_dead_eh_edges): Recompute dominator for the
	EH block.

	* g++.dg/opt/pr17724-1.C: New test.
	* g++.dg/opt/pr17724-2.C: New test.

--- gcc/tree-cfg.c.jj	2004-09-28 10:19:49.000000000 +0200
+++ gcc/tree-cfg.c	2004-09-30 00:16:27.722706542 +0200
@@ -5067,7 +5067,11 @@ tree_purge_dead_eh_edges (basic_block bb
     {
       if (e->flags & EDGE_EH)
 	{
+	  basic_block dest = e->dest, dom;
+
 	  ssa_remove_edge (e);
+	  dom = recount_dominator (CDI_DOMINATORS, dest);
+	  set_immediate_dominator (CDI_DOMINATORS, dest, dom);
 	  changed = true;
 	}
       else
--- gcc/testsuite/g++.dg/opt/pr17724-1.C.jj	2004-09-30 00:20:11.520994862 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-1.C	2004-09-30 00:20:24.014777890 +0200
@@ -0,0 +1,23 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+namespace N { char *strcpy (char *, const char *); }
+extern "C" char *strcpy (char *, const char *) throw ();
+inline char *N::strcpy (char *s, const char *t) { return ::strcpy (s, t); }
+
+struct S { ~S (); };
+int foo ();
+
+int
+main ()
+{
+  S s;
+  int a;
+  char b[64];
+  N::strcpy (b, "ABCDEFGHIJKLM");
+  while ((a = foo ()) != -1)
+    if (a)
+      return -1;
+  return 0;
+}
--- gcc/testsuite/g++.dg/opt/pr17724-2.C.jj	2004-09-30 00:20:11.000000000 +0200
+++ gcc/testsuite/g++.dg/opt/pr17724-2.C	2004-09-30 00:20:04.000000000 +0200
@@ -0,0 +1,23 @@
+// PR tree-optimization/17724
+// { dg-do compile }
+// { dg-options "-O2" }
+
+namespace N { char *strcpy (char *, const char *); }
+extern "C" char *strcpy (char *, const char *);
+inline char *N::strcpy (char *s, const char *t) { return ::strcpy (s, t); }
+
+struct S { ~S (); };
+int foo ();
+
+int
+main ()
+{
+  S s;
+  int a;
+  char b[64];
+  N::strcpy (b, "ABCDEFGHIJKLM");
+  while ((a = foo ()) != -1)
+    if (a)
+      return -1;
+  return 0;
+}

	Jakub