[PATCH] Fix PR37221, missed loop unrolling due to degenerate PHI

[Richard Guenther <rguenther at suse dot de>]

This fixes the complete loop-unrolling cascade in PR37221 which is
hindred by a degenerate PHI produced by a previous unrolling.  This
confuses SCEV analysis so that it can no longer figure out the
number of iterations of the next loop.

Fixed as follows.

Bootstrapped and tested on x86_64-unknown-linux-gnu.  Sebastian, does
this look ok?

Thanks,
Richard.

2009-03-31  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/37221
	* tree-flow.h (degenerate_phi_result): Declare.
	* tree-ssa-dom.c (degenerate_phi_result): Export.
	* tree-scalar-evolution.c (analyze_initial_condition): If
	the initial condition is defined by a degenerate PHI node
	use the degenerate value.

	* gcc.c-torture/compile/20090331-1.c: New testcase.

Index: gcc/tree-flow.h
===================================================================
*** gcc/tree-flow.h.orig	2009-03-31 13:28:36.000000000 +0200
--- gcc/tree-flow.h	2009-03-31 13:28:50.000000000 +0200
*************** bool simplify_stmt_using_ranges (gimple_
*** 919,924 ****
--- 919,925 ----
  extern void dump_dominator_optimization_stats (FILE *);
  extern void debug_dominator_optimization_stats (void);
  int loop_depth_of_name (tree);
+ tree degenerate_phi_result (gimple);
  
  /* In tree-ssa-copy.c  */
  extern void merge_alias_info (tree, tree);
Index: gcc/tree-ssa-dom.c
===================================================================
*** gcc/tree-ssa-dom.c.orig	2009-03-31 13:28:36.000000000 +0200
--- gcc/tree-ssa-dom.c	2009-03-31 13:28:50.000000000 +0200
*************** avail_expr_eq (const void *p1, const voi
*** 2475,2481 ****
  /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
     NULL.  */
  
! static tree
  degenerate_phi_result (gimple phi)
  {
    tree lhs = gimple_phi_result (phi);
--- 2475,2481 ----
  /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
     NULL.  */
  
! tree
  degenerate_phi_result (gimple phi)
  {
    tree lhs = gimple_phi_result (phi);
Index: gcc/tree-scalar-evolution.c
===================================================================
*** gcc/tree-scalar-evolution.c.orig	2009-03-31 13:28:36.000000000 +0200
--- gcc/tree-scalar-evolution.c	2009-03-31 13:39:34.000000000 +0200
*************** analyze_initial_condition (gimple loop_p
*** 1577,1582 ****
--- 1577,1596 ----
    if (init_cond == chrec_not_analyzed_yet)
      init_cond = chrec_dont_know;
  
+   /* During early loop unrolling we do not have fully constant propagated IL.
+      Handle degenerate PHIs here to not miss important unrollings.  */
+   if (TREE_CODE (init_cond) == SSA_NAME)
+     {
+       gimple def = SSA_NAME_DEF_STMT (init_cond);
+       tree res;
+       if (gimple_code (def) == GIMPLE_PHI
+ 	  && (res = degenerate_phi_result (def)) != NULL_TREE
+ 	  /* Only allow invariants here, otherwise we may break
+ 	     loop-closed SSA form.  */
+ 	  && is_gimple_min_invariant (res))
+ 	init_cond = res;
+     }
+ 
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "  (init_cond = ");
Index: gcc/testsuite/gcc.c-torture/compile/20090331-1.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.c-torture/compile/20090331-1.c	2009-03-31 13:29:39.000000000 +0200
***************
*** 0 ****
--- 1,26 ----
+ struct re_pattern_buffer {
+     unsigned char *buffer;
+     unsigned long int allocated;
+ };
+ void byte_regex_compile (struct re_pattern_buffer *bufp,
+ 			 unsigned char *begalt, unsigned char *b)
+ {
+   unsigned char *pfrom;
+   unsigned char *pto;
+ 
+   while ((unsigned long) (b - bufp->buffer + 3) > bufp->allocated)
+     {
+       unsigned char *old_buffer = bufp->buffer;
+       bufp->allocated <<= 1;
+       if (old_buffer != bufp->buffer)
+ 	{
+ 	  int incr = bufp->buffer - old_buffer;
+ 	  b += incr;
+ 	}
+     }
+   pfrom = b;
+   pto = b + 3;
+   while (pfrom != begalt)
+     *--pto = *--pfrom;
+ }
+