Path to speed up flow_loop_tree_node_add

[Michael Hayes <m dot hayes at elec dot canterbury dot ac dot nz>]

This patch avoids the quadratic worst case performance of the previous
algorithm.  OK to commit?

Michael.

2000-02-12  Michael Hayes  <m.hayes@elec.canterbury.ac.nz>

	* flow.c (flow_loop_tree_node_add): Use better algorithm by passing
 	previously inserted node instead of root node.	Caller changed.

Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.219
diff -c -3 -p -r1.219 flow.c
*** flow.c	2000/02/10 16:45:22	1.219
--- flow.c	2000/02/12 03:49:36
*************** flow_loop_pre_header_find (header, dom)
*** 6716,6756 ****
  }
  
  
! /* Add LOOP to the loop hierarchy tree so that it is a sibling or a
!    descendant of ROOT.  */
  static void
! flow_loop_tree_node_add (root, loop)
!      struct loop *root;
       struct loop *loop;
  {
-   struct loop *outer;
  
!   if (! loop)
!     return;
  
!   for (outer = root; outer; outer = outer->next)
      {
!       if (flow_loop_nested_p (outer, loop))
  	{
! 	  if (outer->inner)
! 	    {
! 	      /* Add LOOP as a sibling or descendent of OUTER->INNER.  */
! 	      flow_loop_tree_node_add (outer->inner, loop);
! 	    }
! 	  else
! 	    {
! 	      /* Add LOOP as child of OUTER.  */
! 	      outer->inner = loop;
! 	      loop->outer = outer;
! 	      loop->next = NULL;
! 	    }
  	  return;
  	}
      }
!   /* Add LOOP as a sibling of ROOT.  */
!   loop->next = root->next;
!   root->next = loop;
!   loop->outer = root->outer;
  }
  
  
--- 6715,6749 ----
  }
  
  
! /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
!    previously added.  The insertion algorithm assumes that the loops
!    are added in the order found by a depth first search of the CFG.  */
  static void
! flow_loop_tree_node_add (prevloop, loop)
!      struct loop *prevloop;
       struct loop *loop;
  {
  
!   if (flow_loop_nested_p (prevloop, loop))
!     {
!       prevloop->inner = loop;
!       loop->outer = prevloop;
!       return;
!     }
  
!   while (prevloop->outer)
      {
!       if (flow_loop_nested_p (prevloop->outer, loop))
  	{
! 	  prevloop->next = loop;
! 	  loop->outer = prevloop->outer;
  	  return;
  	}
+       prevloop = prevloop->outer;
      }
!   
!   prevloop->next = loop;
!   loop->outer = NULL;
  }
  
  
*************** flow_loops_tree_build (loops)
*** 6774,6780 ****
  
    /* Add the remaining loops to the tree.  */
    for (i = 1; i < num_loops; i++)
!     flow_loop_tree_node_add (loops->tree, &loops->array[i]);
  }
  
  
--- 6767,6773 ----
  
    /* Add the remaining loops to the tree.  */
    for (i = 1; i < num_loops; i++)
!     flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
  }