PATCH to expand_end_loop for better optimization
Mark Mitchell
mark@markmitchell.com
Fri Jul 17 01:00:00 GMT 1998
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 ())
More information about the Gcc-patches
mailing list