This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: New loop unroller broken?
- From: David Edelsohn <dje at watson dot ibm dot com>
- To: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Cc: Dale Johannesen <dalej at apple dot com>, Andrew Pinski <pinskia at physics dot uc dot edu>, Ulrich Weigand <weigand at i1 dot informatik dot uni-erlangen dot de>, Mircea Namolau <namolaru at il dot ibm dot com>, gcc at gcc dot gnu dot org
- Date: Fri, 23 Jan 2004 14:14:59 -0500
- Subject: Re: New loop unroller broken?
- References: <20040122225123.GA7014@atrey.karlin.mff.cuni.cz>
Mircea Namolaru asked me to forward the appended reply.
David
------- Forwarded Message
1. We have another patch for enabling the new unroller to handle loops
previously optimized by doloop optimizations.
I haven't still tried your patch, but from the code it seems that removes
only the branch at the end of unrolled copies, while preserving the
increment of the count register. For PowerPC the effect will generally be
the undoing of the doloop optimization for the unrolled loop because the
count register is a special register.
If some conditions are met (no other uses of the count register in the
loop beside its increment and the count register not live on exit from the
loop), its increment can also be discarded from the unrolled copies. This
requires the adjustment of its initialization and some changes in the
generation of copies before the unrolled loop is entered. Our patch does
this.
We are evaluating the performance impact of this patch on PowerPC. Before
submitting it the code needs to be brought to a more suitable form (adding
comments, removal of some duplicated code, enabling the case when the
branches can be discarded but not the increments). I've attached our
changes below. Comments welcomed.
2. We have worked (almost finished, but not part of the above mentioned
patch) at two other things that can be easily done during the
unrolling. BTW, the first one is done by the old unroller.
The first one regards basic induction variables. After the unrolling we
will have:
i = i + 1 (copy1)
....
i = i + 1 (copy 2)
....
i = i + 1 (copy 3)
This can be rewritten as:
j = i + 1
...
k = i + 2
...
l = i + 3
This will give opportunities for the scheduling as now there are no data
dependencies between these instructions.
The second one regards array accesses. After the unrolling, for an access
to an array ("a[i]") we have in fact the following pattern (where "i" is
incremented with one in each iteration):
access a[i] (copy 1)
....
access a[i+1] (copy 2)
....
access a[i+2] (copy 3)
We may compute the address of a[i] and have the following code:
addr =&a[i]
access addr
....
access 4(addr)
....
access 8(addr)
In this from the aliasing will be able to detect that a[i] in different
iterations are not referring the same address and thus provide additional
opportunities for scheduling. Beside this if there are no other uses of "i"
in the loop beside the array accesses, "i" is no longer needed and its
increment can be discarded.
Mircea
gdiff -c3p loop-unroll.c.20031210 loop-unroll.c
*** loop-unroll.c.20031210 Fri Jan 23 14:30:56 2004
--- loop-unroll.c Fri Jan 23 14:24:15 2004
*************** Software Foundation, 59 Temple Place - S
*** 31,36 ****
--- 31,39 ----
#include "output.h"
#include "expr.h"
+ /* We need to use the macro exact_log2 */
+ #include "toplev.h"
+
/* This pass performs loop unrolling and peeling. We only perform these
optimizations on innermost loops (with single exception) because
the impact on performance is greatest here, and we want to avoid
*************** static void unroll_loop_stupid (struct l
*** 82,87 ****
--- 85,96 ----
static void unroll_loop_constant_iterations (struct loops *, struct loop *);
static void unroll_loop_runtime_iterations (struct loops *, struct loop *);
+ bool is_bct_cond(rtx);
+ void expand_bct(edge, int);
+ bool is_reg_used_in_insn_chain(rtx, rtx, rtx);
+ bool single_reg_use(struct loop *,struct loop_desc *);
+
+
/* Unroll and/or peel (depending on FLAGS) LOOPS. */
void
unroll_and_peel_loops (struct loops *loops, int flags)
*************** peel_loop_completely (struct loops *loop
*** 425,436 ****
--- 434,452 ----
free (wont_exit);
+ if (is_bct_cond(loop->desc.out_edge->src->end))
+ for (i = 0; i < n_remove_edges; i++)
+ expand_bct(remove_edges[i], 0);
+
/* Remove the exit edges. */
for (i = 0; i < n_remove_edges; i++)
remove_path (loops, remove_edges[i]);
free (remove_edges);
}
+ if (is_bct_cond(loop->desc.out_edge->src->end))
+ expand_bct(desc->in_edge, 0);
+
/* Now remove the unreachable part of the last iteration and cancel
the loop. */
remove_path (loops, desc->in_edge);
*************** decide_unroll_constant_iterations (struc
*** 495,500 ****
--- 511,528 ----
return;
}
+
+ if (is_bct_cond(loop->desc.out_edge->src->end))
+ {
+ /* tests to see that the only use of the count reg is in the exit insn */
+ if(!single_reg_use(loop, &loop->desc))
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, ";; Not unrolling loop (constant), count register has uses\n");
+ return;
+ }
+ }
+
/* Success; now compute number of iterations to unroll. We alter
nunroll so that as few as possible copies of loop body are
necessary, while still not decreasing the number of unrollings
*************** unroll_loop_constant_iterations (struct
*** 574,579 ****
--- 602,633 ----
remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
n_remove_edges = 0;
+ if (is_bct_cond(desc->out_edge->src->end))
+ {
+ rtx ini_var;
+ /* basic_block exit_bb; */
+
+ rtx init_code;
+ int n_peel,new_bct_value;
+ /* rtx count; */
+
+
+ /* Get expression for number of iterations. */
+ start_sequence ();
+
+ n_peel = (niter+1) % (max_unroll+1);
+ new_bct_value = ( niter+1 - n_peel ) / (max_unroll+1) ;
+ ini_var = GEN_INT (new_bct_value);
+
+ emit_move_insn (desc->var, ini_var);
+ init_code = get_insns ();
+ end_sequence ();
+
+ /* emit_insn_after (init_code, set_bct_ini); */
+ loop_split_edge_with (loop_preheader_edge (loop), init_code, loops);
+
+ }
+
if (desc->postincr)
{
/* Counter is incremented after the exit test; leave exit test
*************** unroll_loop_constant_iterations (struct
*** 637,642 ****
--- 691,700 ----
free (wont_exit);
+ if (is_bct_cond(loop->desc.out_edge->src->end))
+ for (i = 0; i < n_remove_edges; i++)
+ expand_bct(remove_edges[i], 0);
+
/* Remove the edges. */
for (i = 0; i < n_remove_edges; i++)
remove_path (loops, remove_edges[i]);
*************** decide_unroll_runtime_iterations (struct
*** 710,715 ****
--- 768,784 ----
return;
}
+ if (is_bct_cond(loop->desc.out_edge->src->end))
+ {
+ /* tests to see that the only use of the count reg is in the exit insn */
+ if(!single_reg_use(loop, &loop->desc))
+ {
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, ";; Not unrolling loop (runtime), count register has uses\n");
+ return;
+ }
+ }
+
/* Success; now force nunroll to be power of 2, as we are unable to
cope with overflows in computation of number of iterations. */
for (i = 1; 2 * i <= nunroll; i *= 2);
*************** unroll_loop_runtime_iterations (struct l
*** 817,822 ****
--- 886,916 ----
GEN_INT (max_unroll),
NULL_RTX, 0, OPTAB_LIB_WIDEN);
+ if (is_bct_cond(desc->out_edge->src->end))
+ {
+ rtx count, count2,count_unroll_mod;
+ int count_unroll;
+
+ /* start_sequence (); */
+
+ count = count_loop_iterations (desc, NULL, NULL);
+
+ count_unroll = loop->lpt_decision.times+1;
+ /* count = expand_simple_binop (GET_MODE (desc->var), DIV,
+ count, count_unroll,
+ 0, 0, OPTAB_LIB_WIDEN); */
+ count_unroll_mod = GEN_INT(exact_log2(count_unroll));
+ count = expand_simple_binop (GET_MODE (desc->var), LSHIFTRT,
+ count, count_unroll_mod,
+ 0, 0, OPTAB_LIB_WIDEN);
+
+ count2 = expand_simple_binop (GET_MODE (desc->var), PLUS,
+ count, GEN_INT (2),
+ 0, 0, OPTAB_LIB_WIDEN);
+
+ emit_move_insn (desc->var, count2);
+ }
+
init_code = get_insns ();
end_sequence ();
*************** unroll_loop_runtime_iterations (struct l
*** 862,869 ****
j = n_peel - i - (extra_zero_check ? 0 : 1);
p = REG_BR_PROB_BASE / (i + 2);
! preheader = loop_split_edge_with (loop_preheader_edge (loop),
! NULL_RTX, loops);
label = block_label (preheader);
start_sequence ();
do_compare_rtx_and_jump (copy_rtx (niter), GEN_INT (j), EQ, 0,
--- 956,975 ----
j = n_peel - i - (extra_zero_check ? 0 : 1);
p = REG_BR_PROB_BASE / (i + 2);
! if (is_bct_cond(desc->out_edge->src->end) && (j == 0))
! {
! basic_block lastbb = loop_preheader_edge(loop)->src;
! rtx split_after;
!
! while (!is_bct_cond(lastbb->end)) lastbb = lastbb->pred->src;
!
! split_after = PREV_INSN (lastbb->end);
!
! preheader = split_loop_bb (loops, lastbb , split_after)->dest;
! }
! else
! preheader = loop_split_edge_with (loop_preheader_edge (loop),
! NULL_RTX, loops);
label = block_label (preheader);
start_sequence ();
do_compare_rtx_and_jump (copy_rtx (niter), GEN_INT (j), EQ, 0,
*************** unroll_loop_runtime_iterations (struct l
*** 933,938 ****
--- 1039,1048 ----
free (wont_exit);
+ if (is_bct_cond(loop->desc.out_edge->src->end))
+ for (i = 0; i < n_remove_edges; i++)
+ expand_bct(remove_edges[i], 0);
+
/* Remove the edges. */
for (i = 0; i < n_remove_edges; i++)
remove_path (loops, remove_edges[i]);
*************** unroll_loop_stupid (struct loops *loops,
*** 1170,1172 ****
--- 1280,1462 ----
fprintf (rtl_dump_file, ";; Unrolled loop %d times, %i insns\n",
nunroll, num_loop_insns (loop));
}
+
+ /* Expand a bct instruction in a branch and an increment.
+ See doloop_condition_get in doloop,c */
+ void expand_bct(edge e, int flag_inc)
+ {
+ /* The canonical doloop pattern we expect is:
+
+ (parallel [(set (pc) (if_then_else (condition)
+ (label_ref (label))
+ (pc)))
+ (set (reg) (plus (reg) (const_int -1)))
+ (additional clobbers and uses)])
+
+ The branch must be the
+ first entry of the parallel (also required by jump.c),
+ and the second entry of the parallel must be a set of
+ the loop counter register. */
+
+ rtx bct_insn = e->src->end;
+ rtx cmp, jump_cmp;
+ rtx inc, insn_inc;
+ rtx seq;
+ rtx pattern = PATTERN(bct_insn);
+
+
+ if (!is_bct_cond(bct_insn))
+ return;
+
+ cmp = XVECEXP (pattern, 0, 0);
+ inc = XVECEXP (pattern, 0, 1);
+
+ start_sequence ();
+ if (flag_inc)
+ insn_inc = emit_insn (inc);
+ jump_cmp = emit_jump_insn (cmp);
+
+ seq = get_insns ();
+ end_sequence ();
+ emit_insn_after (seq, bct_insn);
+
+ delete_insn (bct_insn);
+ return;
+ }
+
+ /* tests to see that the only use of desc->var is in the exit insn */
+
+ /* check if the reg REG is used in rtx X */
+ static bool
+ is_reg_used (rtx x, rtx reg)
+ {
+ enum rtx_code code;
+ /* rtx note; */
+ const char *fmt;
+ int i, j;
+ int reg1,reg2;
+
+ retry:
+ if (x == 0)
+ return false;
+
+ switch (code = GET_CODE (x))
+ {
+
+ case SUBREG:
+ x = SUBREG_REG (x);
+ if (GET_CODE (x) != REG)
+ goto retry;
+ /* Fall through. */
+
+ case REG:
+ reg1=REGNO (x);
+ reg2=REGNO (reg);
+ return (x == reg || reg1 == reg2);
+
+ case PC:
+ case CC0:
+ case CONST:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case SYMBOL_REF:
+ case ADDR_VEC:
+ case ADDR_DIFF_VEC:
+ case LABEL_REF:
+ return false;
+
+ case CLOBBER:
+ /* If we are clobbering a MEM, mark any registers inside the address
+ as being used. */
+ if (GET_CODE (XEXP (x, 0)) == MEM)
+ return is_reg_used (XEXP (XEXP (x, 0), 0), reg);
+ else
+ return false;
+
+ case SET:
+ if (GET_CODE (SET_DEST (x)) == MEM)
+ {
+ return( is_reg_used ( XEXP (x,0), reg) ||
+ is_reg_used ( SET_SRC (x) , reg));
+ } return is_reg_used ( SET_SRC (x) , reg);
+
+ case ASM_OPERANDS:
+ /* If the asm is volatile, then this insn cannot be deleted,
+ and so the inputs *must* be live. */
+
+ /* Iterate over just the inputs, not the constraints as well. */
+ for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
+ return is_reg_used (ASM_OPERANDS_INPUT (x, i),reg);
+
+ case CALL_INSN:
+ break;
+
+ default:
+ break;
+ }
+
+ /* ... fall through ... */
+ /* Recursively scan the operands of this expression. */
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e'){
+ if(is_reg_used (XEXP (x, i), reg))
+ return true;
+ }
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--){
+ if(is_reg_used (XVECEXP (x, i, j), reg))
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ /* check if the reg REG is used in any insn in the INSN_CHAIN
+ returns true if the reg is used, otherwise false. */
+ bool
+ is_reg_used_in_insn_chain(rtx reg, rtx from, rtx to )
+ {
+ rtx insn;
+ for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
+ {
+
+ if(is_reg_used(insn,reg))
+ return true;
+ }
+ return false;
+ }
+
+ bool
+ single_reg_use(struct loop *loop,struct loop_desc *desc)
+ {
+ basic_block *body;
+ int nbbs;
+ int i;
+ rtx head_insn,end_insn;
+ basic_block exit_bb;
+
+ body = get_loop_body (loop);
+ nbbs = loop->num_nodes;
+ exit_bb = desc->out_edge->src;
+
+ for(i=0;i<nbbs;i++)
+ {
+ head_insn = body[i]->head;
+ end_insn = body[i]->end;
+
+ if (body[i] == exit_bb)
+ end_insn = PREV_INSN(end_insn);
+
+ if (is_reg_used_in_insn_chain(desc->var,head_insn,end_insn))
+ return false;
+
+ }
+ return true;
+
+ }
+
gdiff -c3p cfgloopanal.c.20031210 cfgloopanal.c
*** cfgloopanal.c.20031210 Fri Jan 23 14:30:29 2004
--- cfgloopanal.c Fri Jan 23 14:27:23 2004
*************** static rtx variable_initial_value (rtx,
*** 45,50 ****
--- 45,57 ----
static rtx variable_initial_values (edge, rtx, enum machine_mode);
static bool simple_condition_p (struct loop *, rtx, regset,
struct loop_desc *);
+ bool
+ is_bct_cond(rtx);
+ rtx
+ get_var_set_from_bct(rtx);
+
+ extern int flag_unroll_loops_bct;
+
static basic_block simple_increment (struct loops *, struct loop *, rtx *,
struct loop_desc *);
static rtx count_strange_loop_iterations (rtx, rtx, enum rtx_code,
*************** blocks_single_set_registers (basic_block
*** 162,167 ****
--- 169,178 ----
insn = NEXT_INSN (insn))
{
rtx set = single_set (insn);
+
+ if (!set && is_bct_cond (insn))
+ set = get_var_set_from_bct(insn);
+
if (!set)
continue;
if (!REG_P (SET_DEST (set)))
*************** simple_increment (struct loops *loops, s
*** 313,318 ****
--- 324,333 ----
/* mod_insn must be a simple increment/decrement. */
set = single_set (mod_insn);
+
+ if (!set && is_bct_cond (mod_insn))
+ set = get_var_set_from_bct(mod_insn);
+
if (!set)
abort ();
if (!rtx_equal_p (SET_DEST (set), desc->var))
*************** count_loop_iterations (struct loop_desc
*** 836,843 ****
/* Normalize difference so the value is always first examined
and later incremented. */
! if (!desc->postincr)
! exp = simplify_gen_binary (MINUS, mode, exp, stride);
/* Determine delta caused by exit condition. */
switch (cond)
--- 851,858 ----
/* Normalize difference so the value is always first examined
and later incremented. */
! if ((!is_bct_cond(desc->out_edge->src->end)) && (!desc->postincr))
! exp = simplify_gen_binary (MINUS, mode, exp, stride);
/* Determine delta caused by exit condition. */
switch (cond)
*************** expected_loop_iterations (const struct l
*** 1412,1415 ****
--- 1427,1522 ----
return (freq_latch + freq_in - 1) / freq_in;
}
+ }
+
+ /* Similar with the doloop_condition_get */
+ bool
+ is_bct_cond(rtx insn)
+ {
+ rtx cmp;
+ rtx inc;
+ rtx reg;
+ rtx condition;
+ rtx pattern = PATTERN(insn);
+ rtx set_src,set_add;
+
+
+ /* The canonical doloop pattern we expect is:
+
+ (parallel [(set (pc) (if_then_else (condition)
+ (label_ref (label))
+ (pc)))
+ (set (reg) (plus (reg) (const_int -1)))
+ (additional clobbers and uses)])
+
+ Some machines (IA-64) make the decrement conditional on
+ the condition as well, so we don't bother verifying the
+ actual decrement. In summary, the branch must be the
+ first entry of the parallel (also required by jump.c),
+ and the second entry of the parallel must be a set of
+ the loop counter register. */
+
+ #ifndef HAVE_doloop_end
+ return false;
+ #endif
+
+ if (GET_CODE (insn) != JUMP_INSN)
+ return false;
+
+ if (GET_CODE (pattern) != PARALLEL)
+ return false;
+
+ cmp = XVECEXP (pattern, 0, 0);
+ inc = XVECEXP (pattern, 0, 1);
+
+ /* Check for (set (reg) (something)). */
+ if (GET_CODE (inc) != SET || ! REG_P (SET_DEST (inc)))
+ return false;
+
+ /* Extract loop counter register. */
+ reg = SET_DEST (inc);
+
+ set_src = SET_SRC (inc);
+ if (GET_CODE (set_src) != PLUS)
+ return false;
+ if (!rtx_equal_p (XEXP (set_src, 0), reg))
+ return false;
+
+ set_add = XEXP (set_src, 1);
+ if (!(CONSTANT_P (set_add)))
+ return false;
+
+ if(INTVAL(set_add)!=-1)
+ return false;
+
+ /* Check for (set (pc) (if_then_else (condition)
+ (label_ref (label))
+ (pc))). */
+ if (GET_CODE (cmp) != SET
+ || SET_DEST (cmp) != pc_rtx
+ || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
+ || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
+ || XEXP (SET_SRC (cmp), 2) != pc_rtx)
+ return false;
+
+ /* Extract loop termination condition. */
+ condition = XEXP (SET_SRC (cmp), 0);
+
+ if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE && GET_CODE (condition) != EQ)
+ || GET_CODE (XEXP (condition, 1)) != CONST_INT)
+ return false;
+
+ if (XEXP (condition, 0) != reg)
+ return false;
+
+ return true;
+ }
+
+ rtx
+ get_var_set_from_bct(rtx mod_insn)
+ {
+ if (!is_bct_cond (mod_insn))
+ abort ();
+
+ return XVECEXP (PATTERN(mod_insn), 0, 1);
}
------- End of Forwarded Message