Re: optimization/8492: [3.3 regression] GCC spins forever compiling loop

[Eric Botcazou <ebotcazou at libertysurf dot fr>]

> I think deleting unreachable blocks is cheap enought to do in the case
> conditional jump was eliminated.

Ok. But then the GCSE code needs to be (at least partially) re-initialized 
because the number of basic blocks may change. I've attached a naive patch I 
wrote some time ago: while fixing the PR (and doing some housekeeping work), 
it introduces many regressions because of this problem.

> Alternatively we may prevent first local cprop pass from modifying CFG.

I don't know enough of the global organization of optimization passes to 
comment. Will the optimizations missed at that point be caught elsewhere ?

-- 
Eric Botcazou
--- gcse.c.orig	Sun Dec  1 09:28:09 2002
+++ gcse.c	Sun Dec  1 11:00:05 2002
@@ -606,13 +606,13 @@
 static void find_used_regs	PARAMS ((rtx *, void *));
 static int try_replace_reg	PARAMS ((rtx, rtx, rtx));
 static struct expr *find_avail_set PARAMS ((int, rtx));
-static int cprop_jump		PARAMS ((basic_block, rtx, rtx, rtx, rtx));
 static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
 static int load_killed_in_block_p    PARAMS ((basic_block, int, rtx, int));
 static void canon_list_insert        PARAMS ((rtx, rtx, void *));
 static int cprop_insn		PARAMS ((rtx, int));
 static int cprop		PARAMS ((int));
 static int one_cprop_pass	PARAMS ((int, int));
+static bool constprop_jump	PARAMS ((basic_block, rtx, rtx, rtx, rtx));
 static bool constprop_register	PARAMS ((rtx, rtx, rtx, int));
 static struct expr *find_bypass_set PARAMS ((int, int));
 static int bypass_block		    PARAMS ((basic_block, rtx, rtx));
@@ -701,7 +701,7 @@
 static rtx gcse_emit_move_after		PARAMS ((rtx, rtx, rtx));
 static bool do_local_cprop		PARAMS ((rtx, rtx, int, rtx*));
 static bool adjust_libcall_notes	PARAMS ((rtx, rtx, rtx, rtx*));
-static void local_cprop_pass		PARAMS ((int));
+static bool local_cprop_pass		PARAMS ((int));
 
 /* Entry point for global common subexpression elimination.
    F is the first instruction in the function.  */
@@ -3674,6 +3674,11 @@
 static sbitmap *cprop_avin;
 static sbitmap *cprop_avout;
 
+/* Note whether or not the CFG was modified between two points.  This may
+   happen during the local cprop pass if we changed any jumps.  */
+
+static bool cfg_was_modified;
+
 /* Allocate vars used for copy/const propagation.  N_BLOCKS is the number of
    basic blocks.  N_SETS is the number of sets.  */
 
@@ -3964,7 +3969,7 @@
   return success;
 }
 
-/* Find a set of REGNOs that are available on entry to INSN's block.  Returns
+/* Find a SET of REGNO that is available on entry to INSN's block.  Returns
    NULL no such set is found.  */
 
 static struct expr *
@@ -4034,15 +4039,15 @@
   return set1;
 }
 
-/* Subroutine of cprop_insn that tries to propagate constants into
+/* Subroutine of constprop_register that tries to propagate constants into
    JUMP_INSNS.  JUMP must be a conditional jump.  If SETCC is non-NULL
    it is the instruction that immediately preceeds JUMP, and must be a
    single SET of a register.  FROM is what we will try to replace,
-   SRC is the constant we will try to substitute for it.  Returns nonzero
+   SRC is the constant we will try to substitute for it.  Returns TRUE
    if a change was made.  */
 
-static int
-cprop_jump (bb, setcc, jump, from, src)
+static bool
+constprop_jump (bb, setcc, jump, from, src)
      basic_block bb;
      rtx setcc;
      rtx jump;
@@ -4071,7 +4076,7 @@
   /* If no simplification can be made, then try the next
      register.  */
   if (rtx_equal_p (new, new_set) || rtx_equal_p (new, SET_SRC (set)))
-    return 0;
+    return false;
 
   /* If this is now a no-op delete it, otherwise this must be a valid insn.  */
   if (new == pc_rtx)
@@ -4082,9 +4087,9 @@
          to one computed by setcc.  */
       if (setcc 
 	  && modified_in_p (new, setcc))
-	return 0;
+	return false;
       if (! validate_change (jump, &SET_SRC (set), new, 0))
-	return 0;
+	return false;
 
       /* If this has turned into an unconditional jump,
 	 then put a barrier after it so that the unreachable
@@ -4110,11 +4115,17 @@
       print_rtl (gcse_file, src);
       fprintf (gcse_file, "\n");
     }
-  purge_dead_edges (bb);
 
-  return 1;
+  cfg_was_modified |= purge_dead_edges (bb);
+
+  return true;
 }
 
+/* Perform constant propagation on INSN.  FROM is what we will try to
+   replace, TO is the constant we will try to substitute for it.  If
+   ALTER_JUMPS is non-zero, propagate constants into JUMP_INSNS too.
+   Returns TRUE if a change was made.  */
+
 static bool
 constprop_register (insn, from, to, alter_jumps)
      rtx insn;
@@ -4132,14 +4143,14 @@
     {
       rtx dest = SET_DEST (sset);
       if ((REG_P (dest) || CC0_P (dest))
-	  && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
-	return 1;
+	  && constprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
+	return true;
     }
 
   /* Handle normal insns next.  */
   if (GET_CODE (insn) == INSN
       && try_replace_reg (from, to, insn))
-    return 1;
+    return true;
 
   /* Try to propagate a CONST_INT into a conditional jump.
      We're pretty specific about what we will handle in this
@@ -4148,8 +4159,9 @@
      Right now the insn in question must look like
      (set (pc) (if_then_else ...))  */
   else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
-    return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
-  return 0;
+    return constprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
+
+  return false;
 }
 
 /* Perform constant and copy propagation on INSN.
@@ -4332,6 +4344,7 @@
    their REG_EQUAL notes need updating to reflect that OLDREG has been
    replaced with NEWVAL in INSN.  Return true if all substitutions could
    be made.  */
+
 static bool
 adjust_libcall_notes (oldreg, newval, insn, libcall_sp)
      rtx oldreg, newval, insn, *libcall_sp;
@@ -4369,7 +4382,11 @@
 
 #define MAX_NESTED_LIBCALLS 9
 
-static void
+/* Perform one local copy/constant propagation pass.  ALTER_JUMPS is
+   non-zero if we are allowed to modify JUMP_INSNS.  Return TRUE if
+   the CFG was modified.  */
+
+static bool
 local_cprop_pass (alter_jumps)
      int alter_jumps;
 {
@@ -4377,6 +4394,8 @@
   struct reg_use *reg_used;
   rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp;
 
+  cfg_was_modified = false;
+
   cselib_init ();
   libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS];
   *libcall_sp = 0;
@@ -4414,6 +4433,8 @@
       cselib_process_insn (insn);
     }
   cselib_finish ();
+ 
+  return cfg_was_modified;
 }
 
 /* Forward propagate copies.  This includes copies and constants.  Return
@@ -4463,22 +4484,25 @@
   return changed;
 }
 
-/* Perform one copy/constant propagation pass.
-   F is the first insn in the function.
-   PASS is the pass count.  */
+/* Perform one copy/constant propagation pass.  PASS is the
+   pass count, ALTER_JUMPS is non-zero if we are allowed to
+   modify JUMP_INSNS.  Return nonzero if a change was made.  */
 
 static int
 one_cprop_pass (pass, alter_jumps)
      int pass;
      int alter_jumps;
 {
+  bool do_cleanup_cfg;
   int changed = 0;
 
   const_prop_count = 0;
   copy_prop_count = 0;
 
-  local_cprop_pass (alter_jumps);
-
+  do_cleanup_cfg = local_cprop_pass (alter_jumps);
+  if (do_cleanup_cfg)
+    cleanup_cfg (0);
+  
   alloc_hash_table (max_cuid, &set_hash_table, 1);
   compute_hash_table (&set_hash_table);
   if (gcse_file)