[patch] Do not destroy dominance info during loop recognition

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

as noticed by Steven, the dominance information is destroyed and
recomputed during recognition of loops, from purely historical reasons.
This patch makes the dominance information to be updated instead.

The patch uncovered a latent bug in iterate_fix_dominators --
iterate_fix_dominators used to return wrong results in some cases,
because the old values of the immediate dominators were not cleaned
up, and the dataflow did not necessarily have to converge to the
right solution (only some conservative approximation of it).
This problem also caused PR 16690 on lno branch.  It is fixed in
an obvious way -- by cleaning up the old information.

Bootstrapped (with -funroll-loops -funswitch-loops to increase testing
coverage) & regtested on i686.

Zdenek

	* cfgloop.c (update_latch_info): Update dominator of the new block.
	(canonicalize_loop_headers, flow_loops_find): Do not free dominance
	info.
	* dominance.c (verify_dominators): Check that the dominance tree is
	connected.
	(recount_dominator): Ignore unreachable blocks.
	(iterate_fix_dominators): Cleanup old dominance information before
	recomputing it.

Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.35
diff -c -3 -p -r1.35 cfgloop.c
*** cfgloop.c	21 Jul 2004 02:04:00 -0000	1.35
--- cfgloop.c	22 Jul 2004 05:58:05 -0000
*************** update_latch_info (basic_block jump)
*** 575,580 ****
--- 575,581 ----
    HEADER_BLOCK (jump) = 0;
    alloc_aux_for_edge (jump->pred, sizeof (int));
    LATCH_EDGE (jump->pred) = 0;
+   set_immediate_dominator (CDI_DOMINATORS, jump, jump->pred->src);
  }
  
  /* A callback for make_forwarder block, to redirect all edges except for
*************** canonicalize_loop_headers (void)
*** 606,614 ****
    basic_block header;
    edge e;
  
-   /* Compute the dominators.  */
-   calculate_dominance_info (CDI_DOMINATORS);
- 
    alloc_aux_for_blocks (sizeof (int));
    alloc_aux_for_edges (sizeof (int));
  
--- 607,612 ----
*************** canonicalize_loop_headers (void)
*** 638,645 ****
  	HEADER_BLOCK (header) = num_latches;
      }
  
-   free_dominance_info (CDI_DOMINATORS);
- 
    if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest))
      {
        basic_block bb;
--- 636,641 ----
*************** canonicalize_loop_headers (void)
*** 711,716 ****
--- 707,716 ----
  
    free_aux_for_blocks ();
    free_aux_for_edges ();
+ 
+ #ifdef ENABLE_CHECKING
+   verify_dominators (CDI_DOMINATORS);
+ #endif
  }
  
  /* Find all the natural loops in the function and save in LOOPS structure and
*************** flow_loops_find (struct loops *loops, in
*** 747,758 ****
    dfs_order = NULL;
    rc_order = NULL;
  
    /* Join loops with shared headers.  */
    canonicalize_loop_headers ();
  
-   /* Compute the dominators.  */
-   calculate_dominance_info (CDI_DOMINATORS);
- 
    /* Count the number of loop headers.  This should be the
       same as the number of natural loops.  */
    headers = sbitmap_alloc (last_basic_block);
--- 747,758 ----
    dfs_order = NULL;
    rc_order = NULL;
  
+   /* Ensure that the dominators are computed.  */
+   calculate_dominance_info (CDI_DOMINATORS);
+ 
    /* Join loops with shared headers.  */
    canonicalize_loop_headers ();
  
    /* Count the number of loop headers.  This should be the
       same as the number of natural loops.  */
    headers = sbitmap_alloc (last_basic_block);
*************** flow_loops_find (struct loops *loops, in
*** 880,889 ****
  
        loops->num = num_loops;
      }
-   else
-     {
-       free_dominance_info (CDI_DOMINATORS);
-     }
  
    sbitmap_free (headers);
  
--- 880,885 ----
Index: dominance.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/dominance.c,v
retrieving revision 1.25
diff -c -3 -p -r1.25 dominance.c
*** dominance.c	14 Jul 2004 18:27:19 -0000	1.25
--- dominance.c	22 Jul 2004 05:58:05 -0000
*************** verify_dominators (enum cdi_direction di
*** 824,829 ****
--- 824,843 ----
  	  err = 1;
  	}
      }
+ 
+   if (dir == CDI_DOMINATORS
+       && dom_computed[dir] >= DOM_NO_FAST_QUERY)
+     {
+       FOR_EACH_BB (bb)
+ 	{
+ 	  if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
+ 	    {
+ 	      error ("ENTRY does not dominate bb %d", bb->index);
+ 	      err = 1;
+ 	    }
+ 	}
+     }
+ 
    if (err)
      abort ();
  }
*************** recount_dominator (enum cdi_direction di
*** 846,851 ****
--- 860,870 ----
      {
        for (e = bb->pred; e; e = e->pred_next)
  	{
+ 	  /* Ignore the predecessors that either are not reachable from
+ 	     the entry block, or whose dominator was not determined yet.  */
+ 	  if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR))
+ 	    continue;
+ 
  	  if (!dominated_by_p (dir, e->src, bb))
  	    dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
  	}
*************** iterate_fix_dominators (enum cdi_directi
*** 873,878 ****
--- 892,900 ----
    if (!dom_computed[dir])
      abort ();
  
+   for (i = 0; i < n; i++)
+     set_immediate_dominator (dir, bbs[i], NULL);
+ 
    while (changed)
      {
        changed = 0;
*************** iterate_fix_dominators (enum cdi_directi
*** 887,892 ****
--- 909,918 ----
  	    }
  	}
      }
+ 
+   for (i = 0; i < n; i++)
+     if (!get_immediate_dominator (dir, bbs[i]))
+       abort ();
  }
  
  void