This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: New loop unroller broken?
Hello,
> >>Zdenek do you know where the problem is and how to fix it for 3.4
> >
> >no (well, yes, but not with the patch acceptable in this stage).
>
> Why not? This is a performance regression on at least one major target.
I have changed my mind :-). This patch should fix the problem in a
reasonably simple way, by enabling the new loop unroller to handle the
loops previously optimized by doloop. I must give it some testing
before submitting it, of course (at least on ppc and ia64).
Zdenek
* Makefile.in (cfgrtl.o, cfgloopanal.o): Add LOOP_H dependency.
* cfgloop.h (struct loop_desc): New field real_postincr.
* cfgloopanal.c: Include loop.h.
(single_set_or_doloop_decrement): New function.
(blocks_single_set_registers, simple_increment, simple_loop_exit_p):
Handle doloop jumps.
* cfgrtl.c: Include loop.h.
(try_redirect_by_replacing_jump): Handle doloop jumps.
* doloop.c (doloop_condition_get): Export.
* loop-unroll.c (decide_unroll_constant_iterations,
unroll_loop_constant_iterations, unroll_loop_runtime_iterations):
Use real_postincr instead of postincr.
* loop.h (doloop_condition_get): Declare.
* rtl.h (single_set_or_doloop_decrement): Declare.
* toplev.c (rest_of_handle_loop_optimize): Run doloop_optimize in the
first pass.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1223.2.3
diff -c -3 -p -r1.1223.2.3 Makefile.in
*** Makefile.in 21 Jan 2004 04:01:04 -0000 1.1223.2.3
--- Makefile.in 22 Jan 2004 22:41:16 -0000
*************** cfghooks.o: cfghooks.c $(CONFIG_H) $(SYS
*** 1686,1692 ****
$(BASIC_BLOCK_H) cfglayout.h
cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) flags.h \
insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
! function.h except.h $(GGC_H) $(TM_P_H) insn-config.h $(EXPR_H)
cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h insn-config.h $(RECOG_H) $(GGC_H) $(TM_P_H)
cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) flags.h \
--- 1686,1692 ----
$(BASIC_BLOCK_H) cfglayout.h
cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) flags.h \
insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
! function.h except.h $(GGC_H) $(TM_P_H) insn-config.h $(EXPR_H) $(LOOP_H)
cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h insn-config.h $(RECOG_H) $(GGC_H) $(TM_P_H)
cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) flags.h \
*************** cfgcleanup.o : cfgcleanup.c $(CONFIG_H)
*** 1698,1704 ****
$(PARAMS_H)
cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) coretypes.h $(TM_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h flags.h
! cfgloopanal.o : cfgloopanal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h $(EXPR_H) coretypes.h $(TM_H)
cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h cfglayout.h output.h coretypes.h $(TM_H)
--- 1698,1704 ----
$(PARAMS_H)
cfgloop.o : cfgloop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) coretypes.h $(TM_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h flags.h
! cfgloopanal.o : cfgloopanal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(LOOP_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h $(EXPR_H) coretypes.h $(TM_H)
cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h cfgloop.h cfglayout.h output.h coretypes.h $(TM_H)
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.12
diff -c -3 -p -r1.12 cfgloop.h
*** cfgloop.h 30 Dec 2003 10:40:51 -0000 1.12
--- cfgloop.h 22 Jan 2004 22:41:16 -0000
*************** struct lpt_decision
*** 40,45 ****
--- 40,47 ----
struct loop_desc
{
int postincr; /* 1 if increment/decrement is done after loop exit condition. */
+ int real_postincr; /* The same as postincr, but false if the loop ends with a doloop
+ pattern. */
rtx stride; /* Value added to VAR in each iteration. */
rtx var; /* Loop control variable. */
enum machine_mode inner_mode;
Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopanal.c,v
retrieving revision 1.18
diff -c -3 -p -r1.18 cfgloopanal.c
*** cfgloopanal.c 30 Dec 2003 10:40:51 -0000 1.18
--- cfgloopanal.c 22 Jan 2004 22:41:16 -0000
*************** Software Foundation, 59 Temple Place - S
*** 28,33 ****
--- 28,34 ----
#include "cfgloop.h"
#include "expr.h"
#include "output.h"
+ #include "loop.h"
struct unmark_altered_insn_data;
static void unmark_altered (rtx, rtx, regset);
*************** unmark_altered_insn (rtx what, rtx by AT
*** 143,148 ****
--- 144,202 ----
data->regs[rn] = NULL;
}
+ /* Finds a single set in INSN. If INSN is a doloop instruction, the decrement
+ is returned (in case it is a conditional set, its then branch if
+ THEN_BRANCH, else its else branch). */
+
+ rtx
+ single_set_or_doloop_decrement (rtx insn, bool then_branch ATTRIBUTE_UNUSED)
+ {
+ rtx set;
+
+ if (!INSN_P (insn))
+ return NULL_RTX;
+
+ set = single_set (insn);
+ if (set)
+ return set;
+
+ #ifdef HAVE_doloop_end
+ {
+ rtx rhs, lhs, cond;
+ rtx pattern;
+ pattern = PATTERN (insn);
+ if (!doloop_condition_get (pattern))
+ return NULL_RTX;
+
+ /* We have verified that this is a doloop pattern. I.e. it is a parallel
+ where the second element is the decrement. */
+ set = XVECEXP (pattern, 0, 1);
+
+ /* IA64 has the decrement conditional, i.e. done only when the loop does not
+ end. Separate the set. We match
+
+ (set (x (if_then_else (ne x 0) (plus x -1) x))) here. */
+
+ lhs = XEXP (set, 0);
+ rhs = XEXP (set, 1);
+ if (GET_CODE (set) != IF_THEN_ELSE)
+ return set;
+
+ cond = XEXP (rhs, 0);
+ if (GET_CODE (cond) != NE
+ || !rtx_equal_p (XEXP (cond, 0), lhs)
+ || !rtx_equal_p (XEXP (cond, 1), const0_rtx))
+ return set;
+
+ rhs = XEXP (rhs, then_branch ? 1 : 2);
+
+ return gen_rtx_SET (GET_MODE (lhs), lhs, rhs);
+ }
+ #else
+ return NULL_RTX;
+ #endif
+ }
+
/* Marks registers that have just single simple set in BBS; the relevant
insn is returned in REGS. */
static void
*************** blocks_single_set_registers (basic_block
*** 160,166 ****
insn != NEXT_INSN (BB_END (bbs[i]));
insn = NEXT_INSN (insn))
{
! rtx set = single_set (insn);
if (!set)
continue;
if (!REG_P (SET_DEST (set)))
--- 214,220 ----
insn != NEXT_INSN (BB_END (bbs[i]));
insn = NEXT_INSN (insn))
{
! rtx set = single_set_or_doloop_decrement (insn, true);
if (!set)
continue;
if (!REG_P (SET_DEST (set)))
*************** simple_increment (struct loop *loop, rtx
*** 311,317 ****
return NULL;
/* mod_insn must be a simple increment/decrement. */
! set = single_set (mod_insn);
if (!set)
abort ();
if (!rtx_equal_p (SET_DEST (set), desc->var))
--- 365,371 ----
return NULL;
/* mod_insn must be a simple increment/decrement. */
! set = single_set_or_doloop_decrement (mod_insn, true);
if (!set)
abort ();
if (!rtx_equal_p (SET_DEST (set), desc->var))
*************** simple_loop_exit_p (struct loop *loop, e
*** 1006,1012 ****
return false;
/* OK, it is simple loop. Now just fill in remaining info. */
! desc->postincr = !dominated_by_p (CDI_DOMINATORS, exit_bb, mod_bb);
desc->neg = !fallthru_out;
/* Find initial value of var and alternative values for lim. */
--- 1060,1078 ----
return false;
/* OK, it is simple loop. Now just fill in remaining info. */
! #ifdef HAVE_doloop_end
! if (doloop_condition_get (PATTERN (BB_END (exit_bb))))
! {
! desc->postincr = true;
! desc->real_postincr = false;
! }
! else
! #endif
! {
! desc->postincr = !dominated_by_p (CDI_DOMINATORS, exit_bb, mod_bb);
! desc->real_postincr = desc->postincr;
! }
!
desc->neg = !fallthru_out;
/* Find initial value of var and alternative values for lim. */
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.103.2.1
diff -c -3 -p -r1.103.2.1 cfgrtl.c
*** cfgrtl.c 18 Jan 2004 21:46:32 -0000 1.103.2.1
--- cfgrtl.c 22 Jan 2004 22:41:16 -0000
*************** Software Foundation, 59 Temple Place - S
*** 56,61 ****
--- 56,62 ----
#include "insn-config.h"
#include "cfglayout.h"
#include "expr.h"
+ #include "loop.h"
/* Stubs in case we don't have a return insn. */
#ifndef HAVE_return
*************** try_redirect_by_replacing_jump (edge e,
*** 695,716 ****
edge tmp;
rtx set;
int fallthru = 0;
/* Verify that all targets will be TARGET. */
for (tmp = src->succ; tmp; tmp = tmp->succ_next)
if (tmp->dest != target && tmp != e)
break;
! if (tmp || !onlyjump_p (insn))
return false;
! if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
return false;
! /* Avoid removing branch with side effects. */
! set = single_set (insn);
! if (!set || side_effects_p (set))
return false;
/* In case we zap a conditional jump, we'll need to kill
the cc0 setter too. */
kill_from = insn;
--- 696,750 ----
edge tmp;
rtx set;
int fallthru = 0;
+ bool doloop_p;
+ rtx doloop_set = NULL_RTX;
+ #ifdef HAVE_doloop_end
+ bool then_branch;
+ rtx tgt;
+
+ doloop_p = (INSN_P (insn)
+ && doloop_condition_get (PATTERN (insn)) != NULL_RTX);
+ if (doloop_p)
+ {
+ /* Get the set to be emitted for the removed jump. */
+ then_branch = (e->flags & EDGE_FALLTHRU) != 0;
+ doloop_set = single_set_or_doloop_decrement (insn, then_branch);
+
+ start_sequence ();
+ tgt = force_operand (XEXP (doloop_set, 1), XEXP (doloop_set, 0));
+ if (tgt != XEXP (doloop_set, 0))
+ emit_move_insn (XEXP (doloop_set, 0), tgt);
+
+ doloop_set = get_insns ();
+ end_sequence ();
+ }
+
+ #else
+ doloop_p = false;
+ #endif
/* Verify that all targets will be TARGET. */
for (tmp = src->succ; tmp; tmp = tmp->succ_next)
if (tmp->dest != target && tmp != e)
break;
! if (tmp)
return false;
!
! if (!onlyjump_p (insn) && !doloop_p)
return false;
! if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
return false;
+ /* Avoid removing branch with side effects, unless it is a doloop pattern. */
+ if (!doloop_p)
+ {
+ set = single_set (insn);
+ if (!set || side_effects_p (set))
+ return false;
+ }
+
/* In case we zap a conditional jump, we'll need to kill
the cc0 setter too. */
kill_from = insn;
*************** try_redirect_by_replacing_jump (edge e,
*** 752,762 ****
--- 786,802 ----
}
else
delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)));
+
+ if (doloop_set)
+ emit_insn_after (doloop_set, BB_END (src));
}
/* If this already is simplejump, redirect it. */
else if (simplejump_p (insn))
{
+ if (doloop_set)
+ abort ();
+
if (e->dest == target)
return false;
if (rtl_dump_file)
*************** try_redirect_by_replacing_jump (edge e,
*** 789,794 ****
--- 829,837 ----
delete_insn_chain (kill_from, insn);
+
+ if (doloop_set)
+ emit_insn_before (doloop_set, BB_END (src));
/* Recognize a tablejump that we are converting to a
simple jump and remove its associated CODE_LABEL
Index: doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.29
diff -c -3 -p -r1.29 doloop.c
*** doloop.c 29 Jun 2003 15:19:13 -0000 1.29
--- doloop.c 22 Jan 2004 22:41:16 -0000
*************** Software Foundation, 59 Temple Place - S
*** 60,66 ****
#ifdef HAVE_doloop_end
- static rtx doloop_condition_get (rtx);
static unsigned HOST_WIDE_INT doloop_iterations_max (const struct loop_info *,
enum machine_mode, int);
static int doloop_valid_p (const struct loop *, rtx);
--- 60,65 ----
*************** static int doloop_modify_runtime (const
*** 71,77 ****
/* Return the loop termination condition for PATTERN or zero
if it is not a decrement and branch jump insn. */
! static rtx
doloop_condition_get (rtx pattern)
{
rtx cmp;
--- 70,76 ----
/* Return the loop termination condition for PATTERN or zero
if it is not a decrement and branch jump insn. */
! rtx
doloop_condition_get (rtx pattern)
{
rtx cmp;
Index: loop-unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-unroll.c,v
retrieving revision 1.13
diff -c -3 -p -r1.13 loop-unroll.c
*** loop-unroll.c 30 Dec 2003 10:40:54 -0000 1.13
--- loop-unroll.c 22 Jan 2004 22:41:16 -0000
*************** decide_unroll_constant_iterations (struc
*** 504,510 ****
{
unsigned exit_mod = loop->desc.niter % (i + 1);
! if (loop->desc.postincr)
n_copies = exit_mod + i + 1;
else if (exit_mod != (unsigned) i || loop->desc.may_be_zero)
n_copies = exit_mod + i + 2;
--- 504,510 ----
{
unsigned exit_mod = loop->desc.niter % (i + 1);
! if (loop->desc.real_postincr)
n_copies = exit_mod + i + 1;
else if (exit_mod != (unsigned) i || loop->desc.may_be_zero)
n_copies = exit_mod + i + 2;
*************** unroll_loop_constant_iterations (struct
*** 569,575 ****
remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
n_remove_edges = 0;
! if (desc->postincr)
{
/* Counter is incremented after the exit test; leave exit test
in the first copy, so that the loops that start with test
--- 569,575 ----
remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
n_remove_edges = 0;
! if (desc->real_postincr)
{
/* Counter is incremented after the exit test; leave exit test
in the first copy, so that the loops that start with test
*************** unroll_loop_runtime_iterations (struct l
*** 777,783 ****
}
free (body);
! if (desc->postincr)
{
/* Leave exit in first copy (for explanation why see comment in
unroll_loop_constant_iterations). */
--- 777,783 ----
}
free (body);
! if (desc->real_postincr)
{
/* Leave exit in first copy (for explanation why see comment in
unroll_loop_constant_iterations). */
Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.69
diff -c -3 -p -r1.69 loop.h
*** loop.h 27 Sep 2003 17:18:24 -0000 1.69
--- loop.h 22 Jan 2004 22:41:16 -0000
*************** extern rtx loop_insn_sink (const struct
*** 428,431 ****
--- 428,432 ----
extern rtx loop_insn_hoist (const struct loop *, rtx);
/* Forward declarations for non-static functions declared in doloop.c. */
+ extern rtx doloop_condition_get (rtx);
extern int doloop_optimize (const struct loop *);
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.h,v
retrieving revision 1.448.4.1
diff -c -3 -p -r1.448.4.1 rtl.h
*** rtl.h 17 Jan 2004 22:13:53 -0000 1.448.4.1
--- rtl.h 22 Jan 2004 22:41:16 -0000
*************** typedef struct replace_label_data
*** 1673,1678 ****
--- 1673,1679 ----
bool update_label_nuses;
} replace_label_data;
+ extern rtx single_set_or_doloop_decrement (rtx, bool);
extern int rtx_addr_can_trap_p (rtx);
extern bool nonzero_address_p (rtx);
extern int rtx_unstable_p (rtx);
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.863.4.2
diff -c -3 -p -r1.863.4.2 toplev.c
*** toplev.c 17 Jan 2004 12:27:01 -0000 1.863.4.2
--- toplev.c 22 Jan 2004 22:41:16 -0000
*************** rest_of_handle_gcse (tree decl, rtx insn
*** 2986,2992 ****
static void
rest_of_handle_loop_optimize (tree decl, rtx insns)
{
! int do_unroll, do_prefetch;
timevar_push (TV_LOOP);
delete_dead_jumptables ();
--- 2986,2992 ----
static void
rest_of_handle_loop_optimize (tree decl, rtx insns)
{
! int do_unroll, do_prefetch, do_bct;
timevar_push (TV_LOOP);
delete_dead_jumptables ();
*************** rest_of_handle_loop_optimize (tree decl,
*** 3001,3014 ****
else
do_unroll = flag_old_unroll_loops ? LOOP_UNROLL : LOOP_AUTO_UNROLL;
do_prefetch = flag_prefetch_loop_arrays ? LOOP_PREFETCH : 0;
if (flag_rerun_loop_opt)
{
cleanup_barriers ();
! /* We only want to perform unrolling once. */
! loop_optimize (insns, rtl_dump_file, do_unroll);
do_unroll = 0;
/* The first call to loop_optimize makes some instructions
trivially dead. We delete those instructions now in the
--- 3001,3019 ----
else
do_unroll = flag_old_unroll_loops ? LOOP_UNROLL : LOOP_AUTO_UNROLL;
do_prefetch = flag_prefetch_loop_arrays ? LOOP_PREFETCH : 0;
+ do_bct = LOOP_BCT;
if (flag_rerun_loop_opt)
{
cleanup_barriers ();
! /* We only want to perform unrolling once. We also want to do doloop
! optimization now, before the optimizations like induction variable
! elimination make it too complicated to calculate the number of
! iterations. */
! loop_optimize (insns, rtl_dump_file, do_unroll | do_bct);
do_unroll = 0;
+ do_bct = 0;
/* The first call to loop_optimize makes some instructions
trivially dead. We delete those instructions now in the
*************** rest_of_handle_loop_optimize (tree decl,
*** 3021,3027 ****
reg_scan (insns, max_reg_num (), 1);
}
cleanup_barriers ();
! loop_optimize (insns, rtl_dump_file, do_unroll | LOOP_BCT | do_prefetch);
/* Loop can create trivially dead instructions. */
delete_trivially_dead_insns (insns, max_reg_num ());
--- 3026,3032 ----
reg_scan (insns, max_reg_num (), 1);
}
cleanup_barriers ();
! loop_optimize (insns, rtl_dump_file, do_unroll | do_bct | do_prefetch);
/* Loop can create trivially dead instructions. */
delete_trivially_dead_insns (insns, max_reg_num ());