Improve loop detection and loop header copying

[law at redhat dot com]

I've run across a number of "interesting" problems while analyzing SPEC's
perl performance problems when using the tree-ssa compiler.   At the root
of our problems appears to be bad register allocation and block placement
due to odd branch prediction & frequency information.

Needless to say these are not easy problems to analyze.

This patch fixes one specific issue (loop header copying).  As it turns out
this patch alone does not help perl in any way shape or form, but it does
appear to be a minor help for other benchmarks.

--

There is a fundamental difference between tree-ssa and mainline in regards
to loops.   tree-ssa uses loop analysis to create LOOP_BEGIN/LOOP_END notes
while mainline creates LOOP_BEGIN/LOOP_END notes when it expands source level
looping constructs.

The notes created by tree-ssa actually reflect reality more accurately and
that's generally been a good thing :-)  However, loop header copying is 
highly sensitive to the placement of the LOOP_END note.  The net result is
the tree-ssa code is not copying loop headers nearly as often as the mainline
code.

My original direction to fix this was to take the loop header copying code
from the rtlopt branch which doesn't need the loop notes to perform this
optimization.  However, that turned out to be an amazingly bad idea as
nearly every benchmark got notably worse, primarily because the rtlopt
header copying is *extremely* conservative.  This is probably still the
right long term direction since ultimately loop notes must die! :-)

However, in the near term I've decided to just tweak our existing loop
header copying code so that it's not so dependent on the location of the
LOOP_END note.  Instead of looking for the LOOP_END note, we look for
a branch back to the top of the loop.



Bootstrapped and regression tested i686-pc-linux-gnu.

	* jump.c (duplicate_loop_exit_test): Allow copying of the loop
	exit test even if we do not find the LOOP_END note.

Index: jump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/jump.c,v
retrieving revision 1.210.2.18
diff -c -p -r1.210.2.18 jump.c
*** jump.c	30 Jan 2004 13:14:05 -0000	1.210.2.18
--- jump.c	4 Feb 2004 18:57:12 -0000
*************** mark_all_labels (rtx f)
*** 289,299 ****
  }
  
  /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an 
unconditional
!    jump.  Assume that this unconditional jump is to the exit test code.  If
!    the code is sufficiently simple, make a copy of it before INSN,
!    followed by a jump to the exit of the loop.  Then delete the unconditional
!    jump after INSN.
  
     Return 1 if we made the change, else 0.
  
     This is only safe immediately after a regscan pass because it uses the
--- 289,308 ----
  }
  
  /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an 
unconditional
!    jump.  Assume that this unconditional jump is to the exit test code.
  
+    Search the exit code for a conditional branch back to the first code
+    label after LOOP_START. 
+ 
+    If such a conditional jump is found and the exit code is sufficiently
+    simple, then make a copy of it before LOOP_START followed by a jump to
+    fall-thru path of the exit code.  Then delete the unconditional jump after
+    LOOP_START.
+ 
+    Note that if the loop exit code has multiple paths back to the start
+    of the loop, then we only copy the first path.  I.e. the fall-thru
+    path of the exit code can still be part of the semantic loop.
+    
     Return 1 if we made the change, else 0.
  
     This is only safe immediately after a regscan pass because it uses the
*************** duplicate_loop_exit_test (rtx loop_start
*** 356,361 ****
--- 365,384 ----
  	    return 0;
  	  break;
  	default:
+ 	  break;
+ 	}
+ 
+       /* If this is a conditional jump back to the first label after
+ 	 LOOP_START, then we stop our search.  */
+       if (GET_CODE (insn) == JUMP_INSN
+ 	  && JUMP_LABEL (insn)
+ 	  && JUMP_LABEL (insn) == NEXT_INSN (NEXT_INSN (NEXT_INSN (loop_start)))
+ 	  && any_condjump_p (insn)
+ 	  && onlyjump_p (insn))
+ 	{
+ 	  /* Advance INSN over the conditional jump since we want to
+ 	     copy the jump.  */
+ 	  insn = NEXT_INSN (insn);
  	  break;
  	}
      }