re PR middle-end/19698 (Infinite loop in update_life_info)

	PR middle-end/19698
	* function.h (struct function): New field `max_loop_depth'.
	* cfgloop.c (establish_preds): Update maximum loop depth seen so far.
	(flow_loops_find): Reset the max loop depth count before finding loops.
	* flow.c (MAX_LIVENESS_ROUNDS): New constant.
	(update_life_info_in_dirty_blocks): Remove 2002-05-28 workaround.
	(calculate_global_regs_live): Make sure the loop will terminate
	when the initial sets are not empty.

From-SVN: r95299

4 files changed, 149 insertions, 18 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 7b15518..eb1a9be 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,14 @@
+2005-02-19  Steven Bosscher  <stevenb@suse.de>
+
+	PR middle-end/19698 
+	* function.h (struct function): New field `max_loop_depth'.
+	* cfgloop.c (establish_preds): Update maximum loop depth seen so far.
+	(flow_loops_find): Reset the max loop depth count before finding loops.
+	* flow.c (MAX_LIVENESS_ROUNDS): New constant.
+	(update_life_info_in_dirty_blocks): Remove 2002-05-28 workaround.
+	(calculate_global_regs_live): Make sure the loop will terminate
+	when the initial sets are not empty.
+
 2005-02-19  Zack Weinberg  <zack@codesourcery.com>
 
 	* mklibgcc.in: If libgcc_eh.a would be empty, put a dummy
@@ -125,8 +136,8 @@
 2005-02-18  Andrew Pinski  <pinskia@physics.uc.edu>
 
 	PR middle-end/20030
-	* fold-const.c (fold_indirect_ref_1): Use the correct index for zero access,
-	the lower bound of the array type if it exists.
+	* fold-const.c (fold_indirect_ref_1): Use the correct index for zero
+	access, the lower bound of the array type if it exists.
 
 2005-02-18  Alexandre Oliva  <aoliva@redhat.com>
 
@@ -764,7 +775,7 @@
 	* libgcc2.c (__divsc3, __divdc3, __divxc3, __divtc3,
 	__mulsc3, __muldc3, __mulxc3, __multc3): New.
 	* libgcc2.h: Declare them.
- 	* libgcc-std.ver: Export them.
+	* libgcc-std.ver: Export them.
 	* mklibgcc.in (lib2funcs): Build them.
 
 2005-02-11  Steven Bosscher  <stevenb@suse.de>
diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index 4fb687c..40a6de4 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -25,6 +25,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "rtl.h"
 #include "hard-reg-set.h"
 #include "obstack.h"
+#include "function.h"
 #include "basic-block.h"
 #include "toplev.h"
 #include "cfgloop.h"
@@ -510,6 +511,10 @@ establish_preds (struct loop *loop)
   struct loop *ploop, *father = loop->outer;
 
   loop->depth = father->depth + 1;
+
+  /* Remember the current loop depth if it is the largest seen so far.  */
+  cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
+
   if (loop->pred)
     free (loop->pred);
   loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
@@ -819,6 +824,10 @@ flow_loops_find (struct loops *loops, int flags)
 
   memset (loops, 0, sizeof *loops);
 
+  /* We are going to recount the maximum loop depth,
+     so throw away the last count.  */
+  cfun->max_loop_depth = 0;
+
   /* Taking care of this degenerate case makes the rest of
      this code simpler.  */
   if (n_basic_blocks == 0)
@@ -1213,7 +1222,7 @@ remove_bb_from_loops (basic_block bb)
      loop->pred[i]->num_nodes--;
    bb->loop_father = NULL;
    bb->loop_depth = 0;
- }
+}
 
 /* Finds nearest common ancestor in loop tree for given loops.  */
 struct loop *
diff --git a/gcc/flow.c b/gcc/flow.c
index 503dc0d..172541d 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -165,6 +165,11 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #endif
 #endif
 
+/* This is the maximum number of times we process any given block if the
+   latest loop depth count is smaller than this number.  Only used for the
+   failure strategy to avoid infinite loops in calculate_global_regs_live.  */
+#define MAX_LIVENESS_ROUNDS 20
+
 /* Nonzero if the second flow pass has completed.  */
 int flow2_completed;
 
@@ -729,21 +734,10 @@ update_life_info_in_dirty_blocks (enum update_life_extent extent, int prop_flags
   sbitmap_zero (update_life_blocks);
   FOR_EACH_BB (bb)
     {
-      if (extent == UPDATE_LIFE_LOCAL)
+      if (bb->flags & BB_DIRTY)
 	{
-	  if (bb->flags & BB_DIRTY)
-	    {
-	      SET_BIT (update_life_blocks, bb->index);
-	      n++;
-	    }
-	}
-      else
-	{
-	  /* ??? Bootstrap with -march=pentium4 fails to terminate
-	     with only a partial life update.  */
 	  SET_BIT (update_life_blocks, bb->index);
-	  if (bb->flags & BB_DIRTY)
-	    n++;
+	  n++;
 	}
     }
 
@@ -1010,6 +1004,9 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
 {
   basic_block *queue, *qhead, *qtail, *qend, bb;
   regset tmp, new_live_at_end, invalidated_by_call;
+  regset registers_made_dead;
+  bool failure_strategy_required = false;
+  int *block_accesses;
 
   /* The registers that are modified within this in block.  */
   regset *local_sets;
@@ -1030,6 +1027,7 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
   tmp = ALLOC_REG_SET (&reg_obstack);
   new_live_at_end = ALLOC_REG_SET (&reg_obstack);
   invalidated_by_call = ALLOC_REG_SET (&reg_obstack);
+  registers_made_dead = ALLOC_REG_SET (&reg_obstack);
 
   /* Inconveniently, this is only readily available in hard reg set form.  */
   for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
@@ -1070,6 +1068,8 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
 	}
     }
 
+  block_accesses = xcalloc (last_basic_block, sizeof (int));
+  
   /* We clean aux when we remove the initially-enqueued bbs, but we
      don't enqueue ENTRY and EXIT initially, so clean them upfront and
      unconditionally.  */
@@ -1095,7 +1095,41 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
      from GLOBAL_LIVE_AT_START.  In the former case, the register
      could go away only if it disappeared from GLOBAL_LIVE_AT_START
      for one of the successor blocks.  By induction, that cannot
-     occur.  */
+     occur.
+
+     ??? This reasoning doesn't work if we start from non-empty initial
+     GLOBAL_LIVE_AT_START sets.  And there are actually two problems:
+       1) Updating may not terminate (endless oscillation).
+       2) Even if it does (and it usually does), the resulting information
+	  may be inaccurate.  Consider for example the following case:
+
+	  a = ...;
+	  while (...) {...}  -- 'a' not mentioned at all
+	  ... = a;
+
+	  If the use of 'a' is deleted between two calculations of liveness
+	  information and the initial sets are not cleared, the information
+	  about a's liveness will get stuck inside the loop and the set will
+	  appear not to be dead.
+
+     We do not attempt to solve 2) -- the information is conservatively
+     correct (i.e. we never claim that something live is dead) and the
+     amount of optimization opportunities missed due to this problem is
+     not significant.
+
+     1) is more serious.  In order to fix it, we monitor the number of times
+     each block is processed.  Once one of the blocks has been processed more
+     times than the maximum number of rounds, we use the following strategy:
+     When a register disappears from one of the sets, we add it to a MAKE_DEAD
+     set, remove all registers in this set from all GLOBAL_LIVE_AT_* sets and
+     add the blocks with changed sets into the queue.  Thus we are guaranteed
+     to terminate (the worst case corresponds to all registers in MADE_DEAD,
+     in which case the original reasoning above is valid), but in general we
+     only fix up a few offending registers.
+
+     The maximum number of rounds for computing liveness is the largest of
+     MAX_LIVENESS_ROUNDS and the latest loop depth count for this function.  */
+
   while (qhead != qtail)
     {
       int rescan, changed;
@@ -1108,6 +1142,17 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
 	qhead = queue;
       bb->aux = NULL;
 
+      /* Should we start using the failure strategy?  */
+      if (bb != ENTRY_BLOCK_PTR)
+	{
+	  int max_liveness_rounds =
+	    MAX (MAX_LIVENESS_ROUNDS, cfun->max_loop_depth);
+
+	  block_accesses[bb->index]++;
+	  if (block_accesses[bb->index] > max_liveness_rounds)
+	    failure_strategy_required = true;
+	}
+
       /* Begin by propagating live_at_start from the successor blocks.  */
       CLEAR_REG_SET (new_live_at_end);
 
@@ -1263,6 +1308,62 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
 	  if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
 	    continue;
 
+	  if (failure_strategy_required)
+	    {
+	      /* Get the list of registers that were removed from the
+	         bb->global_live_at_start set.  */
+	      bitmap_and_compl (tmp, bb->global_live_at_start,
+				new_live_at_end);
+	      if (!bitmap_empty_p (tmp))
+		{
+		  bool pbb_changed;
+		  basic_block pbb;
+                
+		  /* It should not happen that one of registers we have
+		     removed last time is disappears again before any other
+		     register does.  */
+		  pbb_changed = bitmap_ior_into (registers_made_dead, tmp);
+		  gcc_assert (pbb_changed);
+
+		  /* Now remove the registers from all sets.  */
+		  FOR_EACH_BB (pbb)
+		    {
+		      pbb_changed = false;
+
+		      pbb_changed
+			|= bitmap_and_compl_into (pbb->global_live_at_start,
+						  registers_made_dead);
+		      pbb_changed
+			|= bitmap_and_compl_into (pbb->global_live_at_end,
+						  registers_made_dead);
+		      if (!pbb_changed)
+			continue;
+
+		      /* Note the (possible) change.  */
+		      if (blocks_out)
+			SET_BIT (blocks_out, pbb->index);
+
+		      /* Makes sure to really rescan the block.  */
+		      if (local_sets[pbb->index - (INVALID_BLOCK + 1)])
+			{
+			  FREE_REG_SET (local_sets[pbb->index - (INVALID_BLOCK + 1)]);
+			  FREE_REG_SET (cond_local_sets[pbb->index - (INVALID_BLOCK + 1)]);
+			  local_sets[pbb->index - (INVALID_BLOCK + 1)] = 0;
+			}
+
+		      /* Add it to the queue.  */
+		      if (pbb->aux == NULL)
+			{
+			  *qtail++ = pbb;
+			  if (qtail == qend)
+			    qtail = queue;
+			  pbb->aux = pbb;
+			}
+		    }
+		  continue;
+		}
+	    } /* end of failure_strategy_required */
+
 	  COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
 	}
 
@@ -1284,6 +1385,7 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
   FREE_REG_SET (tmp);
   FREE_REG_SET (new_live_at_end);
   FREE_REG_SET (invalidated_by_call);
+  FREE_REG_SET (registers_made_dead);
 
   if (blocks_out)
     {
@@ -1303,6 +1405,7 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
 	}
     }
 
+  free (block_accesses);
   free (queue);
   free (cond_local_sets);
   free (local_sets);
diff --git a/gcc/function.h b/gcc/function.h
index f760075..ef0f55a 100644
--- a/gcc/function.h
+++ b/gcc/function.h
@@ -284,12 +284,20 @@ struct function GTY(())
   int no_debugging_symbols;
   rtvec original_arg_vector;
   tree original_decl_initial;
+
   /* Highest label number in current function.  */
   int inl_max_label_num;
 
   /* Function sequence number for profiling, debugging, etc.  */
   int funcdef_no;
 
+  /* For flow.c.  */
+
+  /* Highest loop depth seen so far in loop analysis.  Used in flow.c
+     for the "failure strategy" when doing liveness analysis starting
+     with non-empty initial sets.  */
+  int max_loop_depth;
+
   /* For md files.  */
 
   /* tm.h can use this to store whatever it likes.  */