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]

PATCH to expand_end_loop for better optimization



The expand_end_loop function attempts to move exit tests to the end of
loops.  This allows duplicate_loop_exit_test to duplicate the test.
The point of all this is that then (at least the first) instructions
in the loop body itself are guaranteed to be executed, which allows
the loop optimizer to move more code out of loops.

However, expand_end_loop was, for some reason, refusing to treat
unconditional jumps out of the loop as part of the exit test, once 
it had seen a conditional jump.  I corrected this, and cleaned up the
code a bit as well.

Here's an example:

  int x;
  int y;

  int f()
  {
    int i = 2;
    while (x && y)
      {
	x--;
	i = 3;
      }

    return i;
  }

Without the attached patch, we get the following code for f:

  f:
	  pushl %ebp
	  movl %esp,%ebp
	  movl $2,%edx
	  movl x,%eax
	  testl %eax,%eax
	  je .L3
	  movl y,%ecx
	  .p2align 4,,7
  .L6:
	  testl %ecx,%ecx
	  je .L3
	  decl %eax
	  movl %eax,x
	  movl $3,%edx    # i = 3
	  testl %eax,%eax
	  jne .L6
  .L3:
	  movl %edx,%eax
	  movl %ebp,%esp
	  popl %ebp
	  ret

Note that `i = 3' is executed on every iteration.  With the patch,
however, we are able to move the load out of the loop, thus:

  f:
	  pushl %ebp
	  movl %esp,%ebp
	  movl $2,%eax
	  movl x,%edx
	  testl %edx,%edx
	  je .L3
	  movl y,%ecx
	  testl %ecx,%ecx
	  je .L3
	  movl $3,%eax     # i = 3
	  .p2align 4,,7
  .L4:
	  decl %edx
	  movl %edx,x
	  je .L3
	  testl %ecx,%ecx
	  jne .L4
  .L3:
	  movl %ebp,%esp
	  popl %ebp
	  ret

Jeff, is this OK?

-- 
Mark Mitchell 			mark@markmitchell.com
Mark Mitchell Consulting	http://www.markmitchell.com

Fri Jul 17 00:03:45 1998  Mark Mitchell  <mark@markmitchell.com>

	* stmt.c (expand_end_loop): Tidy.  Allow unconditional
	jumps out of the loop to be treated as part of the exit test.

Index: stmt.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/stmt.c,v
retrieving revision 1.45
diff -c -p -r1.45 stmt.c
*** stmt.c	1998/07/13 22:21:01	1.45
--- stmt.c	1998/07/17 06:45:06
*************** expand_loop_continue_here ()
*** 1911,1923 ****
  void
  expand_end_loop ()
  {
!   register rtx insn;
!   register rtx start_label;
!   rtx last_test_insn = 0;
!   int num_insns = 0;
!     
!   insn = get_last_insn ();
!   start_label = loop_stack->data.loop.start_label;
  
    /* Mark the continue-point at the top of the loop if none elsewhere.  */
    if (start_label == loop_stack->data.loop.continue_label)
--- 1911,1918 ----
  void
  expand_end_loop ()
  {
!   rtx start_label = loop_stack->data.loop.start_label;
!   rtx insn = get_last_insn ();
  
    /* Mark the continue-point at the top of the loop if none elsewhere.  */
    if (start_label == loop_stack->data.loop.continue_label)
*************** expand_end_loop ()
*** 1938,1944 ****
           if (test) goto end_label;
  	 body;
  	 goto start_label;
! 	 end_label;
  	 
       transform it to look like:
  
--- 1933,1939 ----
           if (test) goto end_label;
  	 body;
  	 goto start_label;
! 	 end_label:
  	 
       transform it to look like:
  
*************** expand_end_loop ()
*** 1948,1957 ****
  	 start_label:
  	 if (test) goto end_label;
  	 goto newstart_label;
! 	 end_label;
  
       Here, the `test' may actually consist of some reasonably complex
       code, terminating in a test.  */
    if (optimize
        &&
        ! (GET_CODE (insn) == JUMP_INSN
--- 1943,1953 ----
  	 start_label:
  	 if (test) goto end_label;
  	 goto newstart_label;
! 	 end_label:
  
       Here, the `test' may actually consist of some reasonably complex
       code, terminating in a test.  */
+ 
    if (optimize
        &&
        ! (GET_CODE (insn) == JUMP_INSN
*************** expand_end_loop ()
*** 1960,1965 ****
--- 1956,1963 ----
  	 && GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE))
      {
        int eh_regions = 0;
+       int num_insns = 0;
+       rtx last_test_insn = NULL_RTX;
  
        /* Scan insns from the top of the loop looking for a qualified
  	 conditional exit.  */
*************** expand_end_loop ()
*** 2035,2066 ****
  
  	        So we don't look for tests within an EH region.  */
  	    continue;
- 
- 	  if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == SET
- 	      && SET_DEST (PATTERN (insn)) == pc_rtx
- 	      && GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE
- 	      && ((GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == LABEL_REF
- 		   && ((XEXP (XEXP (SET_SRC (PATTERN (insn)), 1), 0)
- 			== loop_stack->data.loop.end_label)
- 		       || (XEXP (XEXP (SET_SRC (PATTERN (insn)), 1), 0)
- 			   == loop_stack->data.loop.alt_end_label)))
- 		  || (GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 2)) == LABEL_REF
- 		      && ((XEXP (XEXP (SET_SRC (PATTERN (insn)), 2), 0)
- 			   == loop_stack->data.loop.end_label)
- 			  || (XEXP (XEXP (SET_SRC (PATTERN (insn)), 2), 0)
- 			      == loop_stack->data.loop.alt_end_label)))))
- 	    last_test_insn = insn;
  
! 	  if (last_test_insn == 0 && GET_CODE (insn) == JUMP_INSN
  	      && GET_CODE (PATTERN (insn)) == SET
! 	      && SET_DEST (PATTERN (insn)) == pc_rtx
! 	      && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF
! 	      && ((XEXP (SET_SRC (PATTERN (insn)), 0)
! 		   == loop_stack->data.loop.end_label)
! 		  || (XEXP (SET_SRC (PATTERN (insn)), 0)
! 		      == loop_stack->data.loop.alt_end_label)))
! 	    /* Include BARRIER.  */
! 	    last_test_insn = NEXT_INSN (insn);
  	}
  
        if (last_test_insn != 0 && last_test_insn != get_last_insn ())
--- 2033,2079 ----
  
  	        So we don't look for tests within an EH region.  */
  	    continue;
  
! 	  if (GET_CODE (insn) == JUMP_INSN 
  	      && GET_CODE (PATTERN (insn)) == SET
! 	      && SET_DEST (PATTERN (insn)) == pc_rtx)
! 	    {
! 	      /* This is indeed a jump.  */
! 	      rtx dest1 = NULL_RTX;
! 	      rtx dest2 = NULL_RTX;
! 	      rtx potential_last_test;
! 	      if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
! 		{
! 		  /* A conditional jump.  */
! 		  dest1 = XEXP (SET_SRC (PATTERN (insn)), 1);
! 		  dest2 = XEXP (SET_SRC (PATTERN (insn)), 2);
! 		  potential_last_test = insn;
! 		}
! 	      else
! 		{
! 		  /* An unconditional jump.  */
! 		  dest1 = SET_SRC (PATTERN (insn));
! 		  /* Include the BARRIER after the JUMP.  */
! 		  potential_last_test = NEXT_INSN (insn);
! 		}
! 
! 	      do {
! 		if (dest1 && GET_CODE (dest1) == LABEL_REF
! 		    && ((XEXP (dest1, 0) 
! 			 == loop_stack->data.loop.alt_end_label)
! 			|| (XEXP (dest1, 0) 
! 			    == loop_stack->data.loop.end_label)))
! 		  {
! 		    last_test_insn = potential_last_test;
! 		    break;
! 		  }
! 
! 		/* If this was a conditional jump, there may be
! 		   another label at which we should look.  */
! 		dest1 = dest2;
! 		dest2 = NULL_RTX;
! 	      } while (dest1);
! 	    }
  	}
  
        if (last_test_insn != 0 && last_test_insn != get_last_insn ())


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