From mboxrd@z Thu Jan  1 00:00:00 1970
From: Jan Hubicka <jh@suse.cz>
To: Brad Lucier <lucier@math.purdue.edu>, gcc-patches@gcc.gnu.org
Cc: jh@suse.cz, gcc@gcc.gnu.org
Subject: Re: Timing information for CFG manipulations
Date: Tue, 16 Oct 2001 07:22:00 -0000
Message-id: <20011016162246.B32633@atrey.karlin.mff.cuni.cz>
References: <200110140332.f9E3W6I16651@banach.math.purdue.edu>
X-SW-Source: 2001-10/msg00903.html

>  cfg construction      : 269.67 (34%) usr   0.32 ( 0%) sys 270.02 (26%) wall

Attached patch should solve this problem.
It avoids the worst case quadratic scenario on removing edges.

Bootstrapped/regtested i386.

Honza

Index: cfg.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cfg.c,v
retrieving revision 1.10
diff -c -3 -p -r1.10 cfg.c
*** cfg.c	2001/10/11 03:15:24	1.10
--- cfg.c	2001/10/16 14:20:55
*************** struct basic_block_def entry_exit_blocks
*** 117,122 ****
--- 117,123 ----
  };
  
  void debug_flow_info			PARAMS ((void));
+ static void free_edge			PARAMS ((edge));
  
  /* Called once at intialization time.  */
  
*************** init_flow ()
*** 142,164 ****
      }
  }
  
  /* Free the memory associated with the edge structures.  */
  
  void
  clear_edges ()
  {
    int i;
  
    for (i = 0; i < n_basic_blocks; ++i)
      {
        basic_block bb = BASIC_BLOCK (i);
  
!       while (bb->succ)
! 	remove_edge (bb->succ);
      }
  
!   while (ENTRY_BLOCK_PTR->succ)
!     remove_edge (ENTRY_BLOCK_PTR->succ);
  
    if (n_edges)
      abort ();
--- 143,195 ----
      }
  }
  
+ /* Helper function for remove_edge and clear_edges.  Frees edge structure
+    without actually unlinking it from the pred/succ lists.  */
+ 
+ static void
+ free_edge (e)
+      edge e;
+ {
+   n_edges--;
+   memset (e, 0, sizeof (*e));
+   e->succ_next = first_deleted_edge;
+   first_deleted_edge = e;
+ }
+ 
  /* Free the memory associated with the edge structures.  */
  
  void
  clear_edges ()
  {
    int i;
+   edge e;
  
    for (i = 0; i < n_basic_blocks; ++i)
      {
        basic_block bb = BASIC_BLOCK (i);
+       edge e = bb->succ;
  
!       while (e)
! 	{
! 	  edge next = e->succ_next;
! 
! 	  free_edge (e);
! 	  e = next;
! 	}
!       bb->succ = NULL;
!       bb->pred = NULL;
      }
  
!   e = ENTRY_BLOCK_PTR->succ;
!   while (e)
!     {
!       edge next = e->succ_next;
! 
!       free_edge (e);
!       e = next;
!     }
!   EXIT_BLOCK_PTR->pred = NULL;
!   ENTRY_BLOCK_PTR->succ = NULL;
  
    if (n_edges)
      abort ();
*************** remove_edge (e)
*** 335,344 ****
    else
      dest->pred = e->pred_next;
  
!   n_edges--;
!   memset (e, 0, sizeof (*e));
!   e->succ_next = first_deleted_edge;
!   first_deleted_edge = e;
  }
  
  /* Redirect an edge's successor from one block to another.  */
--- 366,372 ----
    else
      dest->pred = e->pred_next;
  
!   free_edge (e);
  }
  
  /* Redirect an edge's successor from one block to another.  */