This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] PR19698 - Infinite loop in update_life_info


On Sunday 13 February 2005 19:43, Roger Sayle wrote:
> On Sun, 13 Feb 2005, Nathan Sidwell wrote:
> > 2005-02-13  Nathan Sidwell  <nathan@codesourcery.com>
> >
> >	* bitmap.h (bitmap_and_compl_into): Return bool.
> >	* bitmap.c (bitmap_and_compl_into): Return changed flag.
>
> This is OK for mainline.

Thanks Nathan and Roger! 

So I've dusted off the patch that has been submitted twice before
but never got a review.  I hope this time someone will have a look
at it, because it fixes a long-standing problem in flow.c.

Earlier submissions are in the following archived emails:
http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html 
http://gcc.gnu.org/ml/gcc-patches/2003-12/msg01946.html 

The attached version is a slightly modified version of the earlier
patches, in that I use the fact that we probably know the funcions
loop depth by the time we get to flow.c (because the tree loop
optimizers compute it too).  Otherwise it is only updated to make
it work with the modified bitmap code from Nathan - that was what
his patch was for today ;-)

I am very confident this patch is safe.  In the FSF releases, this
flow.c bug has been around since at least GCC 3.0.  The only GCC I
could find that does not fail, is the hammer-branch, and that is a
very well tested compiler (system compiler for SUSE for a long time
already).

I have booted and tested the patch on {x86_64,ia4}-suse-linux-gnu,
and I have verified that the test case from the PR now does not get
into an infinite loop, and that it does not do that because the new
failure strategy is used.

Thanks Nathan for helping out with the bitmap stuff.
OK for mainline?

Gr.
Steven

2005-02-13  Zdenek Dvorak  <dvorakz@suse.cz>
	    Nathan Sidwell  <nathan@codesourcery.com>	    
	    Steven Bosscher  <stevenb@suse.de>

	* 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.

Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.45
diff -u -3 -p -r1.45 cfgloop.c
--- cfgloop.c	15 Dec 2004 21:18:42 -0000	1.45
+++ cfgloop.c	13 Feb 2005 17:03:34 -0000
@@ -25,6 +25,7 @@ Software Foundation, 59 Temple Place - S
 #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, in
 
   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 *
Index: flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.616
diff -u -3 -p -r1.616 flow.c
--- flow.c	12 Feb 2005 15:17:52 -0000	1.616
+++ flow.c	13 Feb 2005 17:03:42 -0000
@@ -165,6 +165,11 @@ Software Foundation, 59 Temple Place - S
 #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 u
   sbitmap_zero (update_life_blocks);
   FOR_EACH_BB (bb)
     {
-      if (extent == UPDATE_LIFE_LOCAL)
-	{
-	  if (bb->flags & BB_DIRTY)
-	    {
-	      SET_BIT (update_life_blocks, bb->index);
-	      n++;
-	    }
-	}
-      else
+      if (bb->flags & BB_DIRTY)
 	{
-	  /* ??? 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 bloc
 {
   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 bloc
   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 bloc
 	}
     }
 
+  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 bloc
      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 bloc
 	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 bloc
 	  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 bloc
   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 bloc
 	}
     }
 
+  free (block_accesses);
   free (queue);
   free (cond_local_sets);
   free (local_sets);
Index: function.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/function.h,v
retrieving revision 1.139
diff -u -3 -p -r1.139 function.h
--- function.h	27 Jan 2005 18:22:20 -0000	1.139
+++ function.h	13 Feb 2005 17:03:44 -0000
@@ -284,12 +276,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.  */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]