This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [C,C++,Ada,Java,F77] opt/5076 and opt/2847
On Wed, Jan 30, 2002 at 11:43:15AM -0800, Mark Mitchell wrote:
> OK, I agree; this is broken. I think your marker idea is the
> best bet at this point.
Here's what I applied. It's slightly less gross than my first attempt.
Tested on alphaev6 and i686 linux (with ada) and ia64 linux (without ada).
It doesn't apply cleanly to the 3.0 branch. I'll work on that Friday.
r~
* rtl.h (NOTE_INSN_LOOP_END_TOP_COND): New.
* rtl.c (note_insn_name): Update.
* emit-rtl.c (remove_unnecessary_notes): Kill it.
* stmt.c (expand_end_loop): Kill jump opt code. Use LOOP_END_TOP_COND
to perform loop rotation.
(expand_exit_loop_top_cond): New.
* tree.h (expand_exit_loop_top_cond): Declare it.
* c-semantics.c (genrtl_while_stmt): Use it.
(genrtl_for_stmt): Likewise.
* ada/trans.c (tree_transform) [N_Loop_Statement]: Use
expand_exit_loop_top_cond.
* f/ste.c (ffeste_begin_iterdo_): Use expand_exit_loop_top_cond.
(ffeste_R819B): Likewise.
Index: gcc/c-semantics.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/c-semantics.c,v
retrieving revision 1.38
diff -c -p -d -u -r1.38 gcc/c-semantics.c
--- gcc/c-semantics.c 2002/01/22 16:05:50 1.38
+++ gcc/c-semantics.c 2002/01/31 02:01:29
@@ -427,7 +427,7 @@ genrtl_while_stmt (t)
cond = expand_cond (WHILE_COND (t));
emit_line_note (input_filename, lineno);
- expand_exit_loop_if_false (0, cond);
+ expand_exit_loop_top_cond (0, cond);
genrtl_do_pushlevel ();
expand_stmt (WHILE_BODY (t));
@@ -529,7 +529,7 @@ genrtl_for_stmt (t)
/* Expand the condition. */
emit_line_note (input_filename, lineno);
if (cond)
- expand_exit_loop_if_false (0, cond);
+ expand_exit_loop_top_cond (0, cond);
/* Expand the body. */
genrtl_do_pushlevel ();
Index: gcc/emit-rtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/emit-rtl.c,v
retrieving revision 1.246
diff -c -p -d -u -r1.246 gcc/emit-rtl.c
--- gcc/emit-rtl.c 2002/01/29 00:45:55 1.246
+++ gcc/emit-rtl.c 2002/01/31 02:01:29
@@ -3562,6 +3562,7 @@ remove_unnecessary_notes ()
switch (NOTE_LINE_NUMBER (insn))
{
case NOTE_INSN_DELETED:
+ case NOTE_INSN_LOOP_END_TOP_COND:
remove_insn (insn);
break;
Index: gcc/rtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.c,v
retrieving revision 1.106
diff -c -p -d -u -r1.106 gcc/rtl.c
--- gcc/rtl.c 2002/01/10 00:56:56 1.106
+++ gcc/rtl.c 2002/01/31 02:01:29
@@ -263,7 +263,7 @@ const char * const note_insn_name[NOTE_I
"NOTE_INSN_BLOCK_BEG", "NOTE_INSN_BLOCK_END",
"NOTE_INSN_LOOP_BEG", "NOTE_INSN_LOOP_END",
"NOTE_INSN_LOOP_CONT", "NOTE_INSN_LOOP_VTOP",
- "NOTE_INSN_FUNCTION_END",
+ "NOTE_INSN_LOOP_END_TOP_COND", "NOTE_INSN_FUNCTION_END",
"NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
"NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
"NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
Index: gcc/rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.327
diff -c -p -d -u -r1.327 gcc/rtl.h
--- gcc/rtl.h 2002/01/27 18:29:33 1.327
+++ gcc/rtl.h 2002/01/31 02:01:29
@@ -682,6 +682,12 @@ enum insn_note
/* Generated at the start of a duplicated exit test. */
NOTE_INSN_LOOP_VTOP,
+ /* Generated at the end of a conditional at the top of the loop.
+ This is used to perform a lame form of loop rotation in lieu
+ of actually understanding the loop structure. The note is
+ discarded after rotation is complete. */
+ NOTE_INSN_LOOP_END_TOP_COND,
+
/* This kind of note is generated at the end of the function body,
just before the return insn or return label. In an optimizing
compilation it is deleted by the first jump optimization, after
Index: gcc/stmt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/stmt.c,v
retrieving revision 1.243
diff -c -p -d -r1.243 gcc/stmt.c
*** gcc/stmt.c 2002/01/22 14:33:34 1.243
--- gcc/stmt.c 2002/01/31 01:57:58
*************** void
*** 2642,2946 ****
expand_end_loop ()
{
rtx start_label = loop_stack->data.loop.start_label;
! rtx insn = get_last_insn ();
! int needs_end_jump = 1;
/* Mark the continue-point at the top of the loop if none elsewhere. */
if (start_label == loop_stack->data.loop.continue_label)
emit_note_before (NOTE_INSN_LOOP_CONT, start_label);
do_pending_stack_adjust ();
-
- /* If optimizing, perhaps reorder the loop.
- First, try to use a condjump near the end.
- expand_exit_loop_if_false ends loops with unconditional jumps,
- like this:
-
- if (test) goto label;
- optional: cleanup
- goto loop_stack->data.loop.end_label
- barrier
- label:
! If we find such a pattern, we can end the loop earlier. */
!
! if (optimize
! && GET_CODE (insn) == CODE_LABEL
! && LABEL_NAME (insn) == NULL
! && GET_CODE (PREV_INSN (insn)) == BARRIER)
! {
! rtx label = insn;
! rtx jump = PREV_INSN (PREV_INSN (label));
!
! if (GET_CODE (jump) == JUMP_INSN
! && GET_CODE (PATTERN (jump)) == SET
! && SET_DEST (PATTERN (jump)) == pc_rtx
! && GET_CODE (SET_SRC (PATTERN (jump))) == LABEL_REF
! && (XEXP (SET_SRC (PATTERN (jump)), 0)
! == loop_stack->data.loop.end_label))
! {
! rtx prev;
!
! /* The test might be complex and reference LABEL multiple times,
! like the loop in loop_iterations to set vtop. To handle this,
! we move LABEL. */
! insn = PREV_INSN (label);
! reorder_insns (label, label, start_label);
!
! for (prev = PREV_INSN (jump);; prev = PREV_INSN (prev))
! {
! /* We ignore line number notes, but if we see any other note,
! in particular NOTE_INSN_BLOCK_*, NOTE_INSN_EH_REGION_*,
! NOTE_INSN_LOOP_*, we disable this optimization. */
! if (GET_CODE (prev) == NOTE)
! {
! if (NOTE_LINE_NUMBER (prev) < 0)
! break;
! continue;
! }
! if (GET_CODE (prev) == CODE_LABEL)
! break;
! if (GET_CODE (prev) == JUMP_INSN)
! {
! if (GET_CODE (PATTERN (prev)) == SET
! && SET_DEST (PATTERN (prev)) == pc_rtx
! && GET_CODE (SET_SRC (PATTERN (prev))) == IF_THEN_ELSE
! && (GET_CODE (XEXP (SET_SRC (PATTERN (prev)), 1))
! == LABEL_REF)
! && XEXP (XEXP (SET_SRC (PATTERN (prev)), 1), 0) == label)
! {
! XEXP (XEXP (SET_SRC (PATTERN (prev)), 1), 0)
! = start_label;
! emit_note_after (NOTE_INSN_LOOP_END, prev);
! needs_end_jump = 0;
! }
! break;
! }
! }
! }
! }
!
! /* If the loop starts with a loop exit, roll that to the end where
it will optimize together with the jump back.
-
- We look for the conditional branch to the exit, except that once
- we find such a branch, we don't look past 30 instructions.
! In more detail, if the loop presently looks like this (in pseudo-C):
! start_label:
! if (test) goto end_label;
! body;
! goto start_label;
! end_label:
transform it to look like:
! goto start_label;
! newstart_label:
! body;
! 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
! && needs_end_jump
! &&
! ! (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))
! {
! 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. */
! for (insn = NEXT_INSN (loop_stack->data.loop.start_label); insn;
! insn = NEXT_INSN (insn))
! {
! if (GET_CODE (insn) == NOTE)
! {
! if (optimize < 2
! && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
! || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
! /* The code that actually moves the exit test will
! carefully leave BLOCK notes in their original
! location. That means, however, that we can't debug
! the exit test itself. So, we refuse to move code
! containing BLOCK notes at low optimization levels. */
! break;
! if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG)
! ++eh_regions;
! else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
! {
! --eh_regions;
! if (eh_regions < 0)
! /* We've come to the end of an EH region, but
! never saw the beginning of that region. That
! means that an EH region begins before the top
! of the loop, and ends in the middle of it. The
! existence of such a situation violates a basic
! assumption in this code, since that would imply
! that even when EH_REGIONS is zero, we might
! move code out of an exception region. */
! abort ();
! }
! /* We must not walk into a nested loop. */
! if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
! break;
! /* We already know this INSN is a NOTE, so there's no
! point in looking at it to see if it's a JUMP. */
! continue;
! }
! if (GET_CODE (insn) == JUMP_INSN || GET_CODE (insn) == INSN)
! num_insns++;
! if (last_test_insn && num_insns > 30)
break;
!
! if (eh_regions > 0)
! /* We don't want to move a partial EH region. Consider:
!
! while ( ( { try {
! if (cond ()) 0;
! else {
! bar();
! 1;
! }
! } catch (...) {
! 1;
! } )) {
! body;
! }
!
! This isn't legal C++, but here's what it's supposed to
! mean: if cond() is true, stop looping. Otherwise,
! call bar, and keep looping. In addition, if cond
! throws an exception, catch it and keep looping. Such
! constructs are certainy legal in LISP.
! We should not move the `if (cond()) 0' test since then
! the EH-region for the try-block would be broken up.
! (In this case we would the EH_BEG note for the `try'
! and `if cond()' but not the call to bar() or the
! EH_END note.)
! 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 ())
{
! /* We found one. Move everything from there up
! to the end of the loop, and add a jump into the loop
! to jump to there. */
! rtx newstart_label = gen_label_rtx ();
! rtx start_move = start_label;
! rtx next_insn;
!
! /* If the start label is preceded by a NOTE_INSN_LOOP_CONT note,
! then we want to move this note also. */
! if (GET_CODE (PREV_INSN (start_move)) == NOTE
! && (NOTE_LINE_NUMBER (PREV_INSN (start_move))
! == NOTE_INSN_LOOP_CONT))
! start_move = PREV_INSN (start_move);
!
! emit_label_after (newstart_label, PREV_INSN (start_move));
!
! /* Actually move the insns. Start at the beginning, and
! keep copying insns until we've copied the
! last_test_insn. */
for (insn = start_move; insn; insn = next_insn)
{
/* Figure out which insn comes after this one. We have
to do this before we move INSN. */
! if (insn == last_test_insn)
! /* We've moved all the insns. */
! next_insn = NULL_RTX;
! else
! next_insn = NEXT_INSN (insn);
if (GET_CODE (insn) == NOTE
&& (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
- /* We don't want to move NOTE_INSN_BLOCK_BEGs or
- NOTE_INSN_BLOCK_ENDs because the correct generation
- of debugging information depends on these appearing
- in the same order in the RTL and in the tree
- structure, where they are represented as BLOCKs.
- So, we don't move block notes. Of course, moving
- the code inside the block is likely to make it
- impossible to debug the instructions in the exit
- test, but such is the price of optimization. */
continue;
- /* Move the INSN. */
reorder_insns (insn, insn, get_last_insn ());
}
-
- emit_jump_insn_after (gen_jump (start_label),
- PREV_INSN (newstart_label));
- emit_barrier_after (PREV_INSN (newstart_label));
- start_label = newstart_label;
}
- }
! if (needs_end_jump)
! {
! emit_jump (start_label);
! emit_note (NULL, NOTE_INSN_LOOP_END);
}
emit_label (loop_stack->data.loop.end_label);
POPSTACK (loop_stack);
--- 2642,2784 ----
expand_end_loop ()
{
rtx start_label = loop_stack->data.loop.start_label;
! rtx etc_note;
! int eh_regions, debug_blocks;
/* Mark the continue-point at the top of the loop if none elsewhere. */
if (start_label == loop_stack->data.loop.continue_label)
emit_note_before (NOTE_INSN_LOOP_CONT, start_label);
do_pending_stack_adjust ();
! /* If the loop starts with a loop exit, roll that to the end where
it will optimize together with the jump back.
! If the loop presently looks like this (in pseudo-C):
! LOOP_BEG
! start_label:
! if (test) goto end_label;
! LOOP_END_TOP_COND
! body;
! goto start_label;
! end_label:
transform it to look like:
! LOOP_BEG
! goto start_label;
! top_label:
! body;
! start_label:
! if (test) goto end_label;
! goto top_label;
! end_label:
! We rely on the presence of NOTE_INSN_LOOP_END_TOP_COND to mark
! the end of the entry condtional. Without this, our lexical scan
! can't tell the difference between an entry conditional and a
! body conditional that exits the loop. Mistaking the two means
! that we can misplace the NOTE_INSN_LOOP_CONT note, which can
! screw up loop unrolling.
! Things will be oh so much better when loop optimization is done
! off of a proper control flow graph... */
! /* Scan insns from the top of the loop looking for the END_TOP_COND note. */
! eh_regions = debug_blocks = 0;
! for (etc_note = start_label; etc_note ; etc_note = NEXT_INSN (etc_note))
! if (GET_CODE (etc_note) == NOTE)
! {
! if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_LOOP_END_TOP_COND)
! break;
! /* We must not walk into a nested loop. */
! else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_LOOP_BEG)
! {
! etc_note = NULL_RTX;
break;
! }
! /* At the same time, scan for EH region notes, as we don't want
! to scrog region nesting. This shouldn't happen, but... */
! else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_EH_REGION_BEG)
! eh_regions++;
! else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_EH_REGION_END)
! {
! if (--eh_regions < 0)
! /* We've come to the end of an EH region, but never saw the
! beginning of that region. That means that an EH region
! begins before the top of the loop, and ends in the middle
! of it. The existence of such a situation violates a basic
! assumption in this code, since that would imply that even
! when EH_REGIONS is zero, we might move code out of an
! exception region. */
! abort ();
! }
! /* Likewise for debug scopes. In this case we'll either (1) move
! all of the notes if they are properly nested or (2) leave the
! notes alone and only rotate the loop at high optimization
! levels when we expect to scrog debug info. */
! else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_BLOCK_BEG)
! debug_blocks++;
! else if (NOTE_LINE_NUMBER (etc_note) == NOTE_INSN_BLOCK_END)
! debug_blocks--;
! }
! if (etc_note
! && optimize
! && eh_regions == 0
! && (debug_blocks == 0 || optimize >= 2)
! && NEXT_INSN (etc_note) != NULL_RTX
! && ! any_condjump_p (get_last_insn ()))
! {
! /* We found one. Move everything from START to ETC to the end
! of the loop, and add a jump from the top of the loop. */
! rtx top_label = gen_label_rtx ();
! rtx start_move = start_label;
! /* If the start label is preceded by a NOTE_INSN_LOOP_CONT note,
! then we want to move this note also. */
! if (GET_CODE (PREV_INSN (start_move)) == NOTE
! && NOTE_LINE_NUMBER (PREV_INSN (start_move)) == NOTE_INSN_LOOP_CONT)
! start_move = PREV_INSN (start_move);
! emit_label_before (top_label, start_move);
! /* Actually move the insns. If the debug scopes are nested, we
! can move everything at once. Otherwise we have to move them
! one by one and squeeze out the block notes. */
! if (debug_blocks == 0)
! reorder_insns (start_move, etc_note, get_last_insn ());
! else
{
! rtx insn, next_insn;
for (insn = start_move; insn; insn = next_insn)
{
/* Figure out which insn comes after this one. We have
to do this before we move INSN. */
! next_insn = (insn == etc_note ? NULL : NEXT_INSN (insn));
if (GET_CODE (insn) == NOTE
&& (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
|| NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
continue;
reorder_insns (insn, insn, get_last_insn ());
}
}
! /* Add the jump from the top of the loop. */
! emit_jump_insn_before (gen_jump (start_label), top_label);
! emit_barrier_before (top_label);
! start_label = top_label;
}
+
+ emit_jump (start_label);
+ emit_note (NULL, NOTE_INSN_LOOP_END);
emit_label (loop_stack->data.loop.end_label);
POPSTACK (loop_stack);
*************** expand_exit_loop_if_false (whichloop, co
*** 3025,3030 ****
--- 2863,2884 ----
NULL_RTX);
emit_label (label);
+ return 1;
+ }
+
+ /* Like expand_exit_loop_if_false except also emit a note marking
+ the end of the conditional. Should only be used immediately
+ after expand_loop_start. */
+
+ int
+ expand_exit_loop_top_cond (whichloop, cond)
+ struct nesting *whichloop;
+ tree cond;
+ {
+ if (! expand_exit_loop_if_false (whichloop, cond))
+ return 0;
+
+ emit_note (NULL, NOTE_INSN_LOOP_END_TOP_COND);
return 1;
}
Index: gcc/tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.301
diff -c -p -d -u -r1.301 gcc/tree.h
--- gcc/tree.h 2002/01/29 17:19:56 1.301
+++ gcc/tree.h 2002/01/31 02:01:30
@@ -2751,7 +2751,9 @@ extern void expand_end_null_loop PARAMS
extern int expand_continue_loop PARAMS ((struct nesting *));
extern int expand_exit_loop PARAMS ((struct nesting *));
extern int expand_exit_loop_if_false PARAMS ((struct nesting *,
- tree));
+ tree));
+extern int expand_exit_loop_top_cond PARAMS ((struct nesting *,
+ tree));
extern int expand_exit_something PARAMS ((void));
extern void expand_return PARAMS ((tree));
Index: gcc/ada/trans.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ada/trans.c,v
retrieving revision 1.10
diff -c -p -d -u -r1.10 gcc/ada/trans.c
--- gcc/ada/trans.c 2001/12/19 00:31:41 1.10
+++ gcc/ada/trans.c 2002/01/31 02:01:31
@@ -2350,7 +2350,7 @@ tree_transform (gnat_node)
if (Present (gnat_top_condition))
gnu_top_condition = gnat_to_gnu (gnat_top_condition);
- expand_exit_loop_if_false (0, gnu_top_condition);
+ expand_exit_loop_top_cond (0, gnu_top_condition);
/* Make the loop body into its own block, so any allocated
storage will be released every iteration. This is needed
Index: gcc/f/ste.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/f/ste.c,v
retrieving revision 1.25
diff -c -p -d -u -r1.25 gcc/f/ste.c
--- gcc/f/ste.c 2001/10/17 22:34:53 1.25
+++ gcc/f/ste.c 2002/01/31 02:01:31
@@ -706,7 +706,7 @@ ffeste_begin_iterdo_ (ffestw block, tree
convert (TREE_TYPE (niters),
ffecom_integer_zero_node)));
- expand_exit_loop_if_false (0, expr);
+ expand_exit_loop_top_cond (0, expr);
}
if (block)
@@ -2816,7 +2816,7 @@ ffeste_R819B (ffestw block, ffelab label
ffeste_end_stmt_ ();
ffestw_set_do_hook (block, loop);
- expand_exit_loop_if_false (0, result);
+ expand_exit_loop_top_cond (0, result);
}
else
ffestw_set_do_hook (block, expand_start_loop (1));
- References:
- [C,C++,Ada,Java,F77] opt/5076 and opt/2847
- Re: [C,C++,Ada,Java,F77] opt/5076 and opt/2847
- Re: [C,C++,Ada,Java,F77] opt/5076 and opt/2847
- Re: [C,C++,Ada,Java,F77] opt/5076 and opt/2847
- Re: [C,C++,Ada,Java,F77] opt/5076 and opt/2847
- Re: [C,C++,Ada,Java,F77] opt/5076 and opt/2847