This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[CFG] Unrolling fixes
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-pdo at atrey dot karlin dot mff dot cuni dot cz, gcc-patches at gcc dot gnu dot org
- Date: Tue, 14 May 2002 01:03:43 +0200
- Subject: [CFG] Unrolling fixes
Hello.
1) Finally makes us to consider
for (i=a;i<a+100;i++)
constant time iterating loop (as we promissed for ages :-)
This is not a final version -- I suspect changes I have made make the code
worse in many cases. I will fix this soon.
2) Fix several bugs
-- handle the fact that code from force_operand may contain jumps
-- fix a bug in force_operand
-- handle the case when cfg_layout_redirect_edge fails
-- several bugs in variable_initial_value
Changelog:
* basic_block.h (BB_SUPERBLOCK): New flag.
* cfglayout.c (break_superblocks): New static function.
(cfg_layout_finalize): Use it.
(cfg_layout_redirect_edge): Return false if fails.
* cfglayout.h (cfg_layout_redirect_edge): Declaration changed.
* cfgloopanal.c (loop_split_edge_with): Mark created block with
BB_SUPERBLOCK flag.
* expr.c (force_operand): Fix.
* loop-new.c (loop_delete_branch_edge): Return false if fails.
(remove_path): Turn into no-op ig loop_delete_branch_edge fails.
* loop.h (struct loop_desc): Add may_be_zero field that is true
if first iteration of loop does not have to pass.
(remove_path): Declaration changed.
* unroll-new.c (variable_initial_value, simple_condition_p,
simple_exit_p): Modified.
(constant_iterations): Extended to handle more loops.
(invariant_in_blocks_p): New.
(peel_loop_completely, unroll_loop_constant_iterations): Handle
may_be_zero flag.
(unroll_or_peel_loop): We no longer may lose simpleness when counting
iterations.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.127.2.25
diff -c -3 -p -r1.127.2.25 basic-block.h
*** basic-block.h 8 May 2002 12:02:37 -0000 1.127.2.25
--- basic-block.h 13 May 2002 19:54:54 -0000
*************** typedef struct basic_block_def {
*** 233,238 ****
--- 233,239 ----
#define BB_REACHABLE 4
/* Used by dfs_enumerate_from; keep this one zero! */
#define BB_VISITED 8
+ #define BB_SUPERBLOCK 16
/* Number of basic blocks in the current function. */
Index: cfglayout.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfglayout.c,v
retrieving revision 1.2.2.43
diff -c -3 -p -r1.2.2.43 cfglayout.c
*** cfglayout.c 12 May 2002 12:13:13 -0000 1.2.2.43
--- cfglayout.c 13 May 2002 19:54:58 -0000
*************** static void fixup_fallthru_exit_predeces
*** 50,55 ****
--- 50,56 ----
static void cleanup_unconditional_jumps PARAMS ((struct loops *));
static rtx unlink_insn_chain PARAMS ((rtx, rtx));
static rtx duplicate_insn_chain PARAMS ((rtx, rtx));
+ static void break_superblocks PARAMS ((void));
/* Map insn uid to lexical block. */
static varray_type insn_scopes;
*************** duplicate_insn_chain (from, to)
*** 852,864 ****
}
/* Redirect Edge to DEST. */
! void
cfg_layout_redirect_edge (e, dest)
edge e;
basic_block dest;
{
int old_index = dest->index;
basic_block src = e->src;
/* Avoid redirect_edge_and_branch from overactive optimizing. */
dest->index = n_basic_blocks + 1;
--- 853,866 ----
}
/* Redirect Edge to DEST. */
! bool
cfg_layout_redirect_edge (e, dest)
edge e;
basic_block dest;
{
int old_index = dest->index;
basic_block src = e->src;
+ bool ret;
/* Avoid redirect_edge_and_branch from overactive optimizing. */
dest->index = n_basic_blocks + 1;
*************** cfg_layout_redirect_edge (e, dest)
*** 876,884 ****
delete_insn (src->end);
}
redirect_edge_succ_nodup (e, dest);
}
else
! redirect_edge_and_branch (e, dest);
/* We don't want simplejumps in the insn stream during cfglayout. */
if (simplejump_p (src->end))
--- 878,888 ----
delete_insn (src->end);
}
redirect_edge_succ_nodup (e, dest);
+
+ ret = true;
}
else
! ret = redirect_edge_and_branch (e, dest);
/* We don't want simplejumps in the insn stream during cfglayout. */
if (simplejump_p (src->end))
*************** cfg_layout_redirect_edge (e, dest)
*** 888,893 ****
--- 892,899 ----
src->succ->flags |= EDGE_FALLTHRU;
}
dest->index = old_index;
+
+ return ret;
}
/* Create an duplicate of the basic block BB and redirect edge E into it. */
*************** cfg_layout_initialize (loops)
*** 995,1000 ****
--- 1001,1035 ----
verify_insn_chain ();
}
+ /* Splits superblocks. */
+ static void
+ break_superblocks ()
+ {
+ sbitmap superblocks;
+ int i, need;
+
+ superblocks = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (superblocks);
+
+ need = 0;
+
+ for (i = 0; i < n_basic_blocks; i++)
+ if (BASIC_BLOCK(i)->flags & BB_SUPERBLOCK)
+ {
+ BASIC_BLOCK(i)->flags &= ~BB_SUPERBLOCK;
+ SET_BIT (superblocks, i);
+ need = 1;
+ }
+
+ if (need)
+ {
+ rebuild_jump_labels (get_insns ());
+ find_many_sub_basic_blocks (superblocks);
+ }
+
+ free (superblocks);
+ }
+
/* Finalize the changes: reorder insn list according to the sequence, enter
compensation code, rebuild scope forest. */
*************** cfg_layout_finalize ()
*** 1011,1016 ****
--- 1046,1053 ----
scope_to_insns_finalize ();
free_aux_for_blocks ();
+
+ break_superblocks ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
Index: cfglayout.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfglayout.h,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 cfglayout.h
*** cfglayout.h 25 Feb 2002 16:50:24 -0000 1.1.2.6
--- cfglayout.h 13 May 2002 19:54:58 -0000
*************** extern bool cfg_layout_can_duplicate_bb_
*** 41,44 ****
extern basic_block cfg_layout_duplicate_bb PARAMS ((basic_block, edge));
extern void scope_to_insns_initialize PARAMS ((void));
extern void scope_to_insns_finalize PARAMS ((void));
! extern void cfg_layout_redirect_edge PARAMS ((edge, basic_block));
--- 41,44 ----
extern basic_block cfg_layout_duplicate_bb PARAMS ((basic_block, edge));
extern void scope_to_insns_initialize PARAMS ((void));
extern void scope_to_insns_finalize PARAMS ((void));
! extern bool cfg_layout_redirect_edge PARAMS ((edge, basic_block));
Index: cfgloopanal.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/cfgloopanal.c,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 cfgloopanal.c
*** cfgloopanal.c 4 May 2002 19:55:18 -0000 1.1.2.8
--- cfgloopanal.c 13 May 2002 19:54:59 -0000
*************** loop_split_edge_with (e, insns, loops)
*** 608,614 ****
new_bb = create_basic_block (n_basic_blocks, NULL, NULL);
add_bb_to_loop (new_bb, loop_c);
! new_bb->flags = 0;
new_e = make_edge (new_bb, dest, EDGE_FALLTHRU);
new_e->probability = REG_BR_PROB_BASE;
--- 608,614 ----
new_bb = create_basic_block (n_basic_blocks, NULL, NULL);
add_bb_to_loop (new_bb, loop_c);
! new_bb->flags = BB_SUPERBLOCK;
new_e = make_edge (new_bb, dest, EDGE_FALLTHRU);
new_e->probability = REG_BR_PROB_BASE;
Index: expr.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expr.c,v
retrieving revision 1.374.2.18
diff -c -3 -p -r1.374.2.18 expr.c
*** expr.c 8 May 2002 12:03:22 -0000 1.374.2.18
--- expr.c 13 May 2002 19:55:29 -0000
*************** force_operand (value, target)
*** 5456,5462 ****
{
if (!target)
target = gen_reg_rtx (GET_MODE (value));
! convert_move (force_operand (XEXP (value, 0), NULL), target,
code == ZERO_EXTEND);
return target;
}
--- 5456,5462 ----
{
if (!target)
target = gen_reg_rtx (GET_MODE (value));
! convert_move (target, force_operand (XEXP (value, 0), NULL),
code == ZERO_EXTEND);
return target;
}
Index: loop-new.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/loop-new.c,v
retrieving revision 1.1.2.20
diff -c -3 -p -r1.1.2.20 loop-new.c
*** loop-new.c 9 May 2002 15:14:00 -0000 1.1.2.20
--- loop-new.c 13 May 2002 19:55:37 -0000
*************** static struct loop * duplicate_loop PARA
*** 214,220 ****
static void duplicate_subloops PARAMS ((struct loops *, struct loop *, struct loop *));
static void copy_loops_to PARAMS ((struct loops *, struct loop **, int, struct loop *));
static void loop_redirect_edge PARAMS ((edge, basic_block));
! static void loop_delete_branch_edge PARAMS ((edge));
static void copy_bbs PARAMS ((basic_block *, int, edge, edge, basic_block **, struct loops *, edge *, edge *));
static struct loop *unswitch_loop PARAMS ((struct loops *, struct loop *, basic_block));
static void remove_bbs PARAMS ((basic_block *, int));
--- 214,220 ----
static void duplicate_subloops PARAMS ((struct loops *, struct loop *, struct loop *));
static void copy_loops_to PARAMS ((struct loops *, struct loop **, int, struct loop *));
static void loop_redirect_edge PARAMS ((edge, basic_block));
! static bool loop_delete_branch_edge PARAMS ((edge));
static void copy_bbs PARAMS ((basic_block *, int, edge, edge, basic_block **, struct loops *, edge *, edge *));
static struct loop *unswitch_loop PARAMS ((struct loops *, struct loop *, basic_block));
static void remove_bbs PARAMS ((basic_block *, int));
*************** find_branch (e, doms, bbs)
*** 658,664 ****
}
/* Removes path beginning at E. */
! void
remove_path (loops, e)
struct loops *loops;
edge e;
--- 658,664 ----
}
/* Removes path beginning at E. */
! bool
remove_path (loops, e)
struct loops *loops;
edge e;
*************** remove_path (loops, e)
*** 671,681 ****
/* First identify the branch. */
nrem = find_branch (e, loops->cfg.dom, &rem_bbs);
- /* Now cancel contained loops. */
- for (i = 0; i < nrem; i++)
- if (rem_bbs[i]->loop_father->header == rem_bbs[i])
- cancel_loop_tree (loops, rem_bbs[i]->loop_father);
-
/* Find blocks whose immediate dominators may be affected. */
n_dom_bbs = 0;
n_bord_bbs = 0;
--- 671,676 ----
*************** remove_path (loops, e)
*** 705,711 ****
/* OK. Remove the path. */
from = e->src;
! loop_delete_branch_edge (e);
remove_bbs (rem_bbs, nrem);
free (rem_bbs);
--- 700,713 ----
/* OK. Remove the path. */
from = e->src;
! if (!loop_delete_branch_edge (e))
! return false;
!
! /* Now cancel contained loops. */
! for (i = 0; i < nrem; i++)
! if (rem_bbs[i]->loop_father->header == rem_bbs[i])
! cancel_loop_tree (loops, rem_bbs[i]->loop_father);
!
remove_bbs (rem_bbs, nrem);
free (rem_bbs);
*************** remove_path (loops, e)
*** 737,742 ****
--- 739,746 ----
/* Fix loop placements. */
fix_loop_placements (from->loop_father);
+
+ return true;
}
/* Predicate for enumeration in add_loop. */
*************** loop_redirect_edge (e, dest)
*** 1113,1119 ****
}
/* Deletes edge if possible. */
! static void
loop_delete_branch_edge (e)
edge e;
{
--- 1117,1123 ----
}
/* Deletes edge if possible. */
! static bool
loop_delete_branch_edge (e)
edge e;
{
*************** loop_delete_branch_edge (e)
*** 1124,1144 ****
basic_block newdest;
/* Cannot handle more than two exit edges. */
if (src->succ->succ_next->succ_next)
! return;
/* Neither this. */
if (!any_condjump_p (src->end))
! return;
newdest = (e == src->succ
? src->succ->succ_next->dest : src->succ->dest);
if (newdest == EXIT_BLOCK_PTR)
! return;
! cfg_layout_redirect_edge (e, newdest);
}
else
{
/* Cannot happen -- we are duplicating loop! */
abort ();
}
}
/* Duplicates BBS. Newly created bbs are placed into NEW_BBS, edges to
--- 1128,1152 ----
basic_block newdest;
/* Cannot handle more than two exit edges. */
if (src->succ->succ_next->succ_next)
! return false;
/* Neither this. */
if (!any_condjump_p (src->end))
! return false;
!
newdest = (e == src->succ
? src->succ->succ_next->dest : src->succ->dest);
if (newdest == EXIT_BLOCK_PTR)
! return false;
!
! return cfg_layout_redirect_edge (e, newdest);
}
else
{
/* Cannot happen -- we are duplicating loop! */
abort ();
}
+
+ return false; /* To avoid warning, cannot get here. */
}
/* Duplicates BBS. Newly created bbs are placed into NEW_BBS, edges to
Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.56.2.14
diff -c -3 -p -r1.56.2.14 loop.h
*** loop.h 5 May 2002 12:55:06 -0000 1.56.2.14
--- loop.h 13 May 2002 19:55:39 -0000
*************** struct loop_desc
*** 444,449 ****
--- 444,450 ----
bool const_iter; /* True if it iterates constant number of times. */
unsigned HOST_WIDE_INT niter;
/* Number of iterations if it is constant. */
+ bool may_be_zero; /* If we cannot determine that the first iteration will pass. */
enum rtx_code cond; /* Exit condition. */
int neg; /* Set to 1 if loop ends when condition is satisfied. */
edge out_edge; /* The exit edge. */
*************** bool can_duplicate_loop_p PARAMS ((struc
*** 457,461 ****
int duplicate_loop_to_header_edge PARAMS ((struct loop *, edge, struct loops *, int,
sbitmap, edge, edge *, int *, int));
! void remove_path PARAMS ((struct loops *, edge));
--- 458,462 ----
int duplicate_loop_to_header_edge PARAMS ((struct loop *, edge, struct loops *, int,
sbitmap, edge, edge *, int *, int));
! bool remove_path PARAMS ((struct loops *, edge));
Index: unroll-new.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/unroll-new.c,v
retrieving revision 1.1.2.26
diff -c -3 -p -r1.1.2.26 unroll-new.c
*** unroll-new.c 6 May 2002 16:15:52 -0000 1.1.2.26
--- unroll-new.c 13 May 2002 19:55:41 -0000
*************** static bool simple_condition_p PARAMS ((
*** 47,60 ****
static basic_block simple_increment PARAMS ((struct loops *, struct loop *,
basic_block *,
struct loop_desc *));
! static rtx variable_initial_value PARAMS ((struct loop *, rtx));
static bool simple_loop_p PARAMS ((struct loops *, struct loop *,
struct loop_desc *));
static bool simple_loop_exit_p PARAMS ((struct loops *, struct loop *,
edge, basic_block *,
struct loop_desc *));
static bool constant_iterations PARAMS ((struct loop_desc *,
! unsigned HOST_WIDE_INT *));
static rtx count_loop_iterations PARAMS ((struct loop_desc *, bool));
static void unroll_or_peel_loop PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_simple PARAMS ((struct loops *, struct loop *, int));
--- 47,61 ----
static basic_block simple_increment PARAMS ((struct loops *, struct loop *,
basic_block *,
struct loop_desc *));
! static rtx variable_initial_value PARAMS ((rtx, basic_block, rtx, rtx *));
static bool simple_loop_p PARAMS ((struct loops *, struct loop *,
struct loop_desc *));
static bool simple_loop_exit_p PARAMS ((struct loops *, struct loop *,
edge, basic_block *,
struct loop_desc *));
static bool constant_iterations PARAMS ((struct loop_desc *,
! unsigned HOST_WIDE_INT *,
! bool *));
static rtx count_loop_iterations PARAMS ((struct loop_desc *, bool));
static void unroll_or_peel_loop PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_simple PARAMS ((struct loops *, struct loop *, int));
*************** static bool unroll_loop_runtime_iteratio
*** 69,74 ****
--- 70,76 ----
struct loop_desc *));
static rtx test_for_iteration PARAMS ((struct loop_desc *desc,
unsigned HOST_WIDE_INT));
+ static bool invariant_in_blocks_p PARAMS ((rtx, basic_block *, int));
/* Unroll and peel (depending on FLAGS) LOOPS. */
void
*************** unroll_and_peel_loops (loops, flags)
*** 102,107 ****
--- 104,125 ----
}
}
+ /* Checks whether EXPR is invariant in basic blocks BBS. */
+ static bool
+ invariant_in_blocks_p (expr, bbs, nbbs)
+ rtx expr;
+ basic_block *bbs;
+ int nbbs;
+ {
+ int i;
+
+ for (i = 0; i < nbbs; i++)
+ if (modified_between_p (expr, bbs[i]->head, NEXT_INSN (bbs[i]->end)))
+ return false;
+
+ return true;
+ }
+
/* Checks whether CONDITION is a simple comparison in that one of operands
is register and the other one is invariant in the LOOP. Fills var, lim
and cond fields in DESC. */
*************** simple_condition_p (loop, body, conditio
*** 112,119 ****
rtx condition;
struct loop_desc *desc;
{
! rtx op0, op1;
! int i;
/* Check condition. */
switch (GET_CODE (condition))
--- 130,137 ----
rtx condition;
struct loop_desc *desc;
{
! rtx op0, op1, set_insn;
! edge e = loop_preheader_edge (loop);
/* Check condition. */
switch (GET_CODE (condition))
*************** simple_condition_p (loop, body, conditio
*** 143,163 ****
op1 = XEXP (condition, 1);
/* One of operands must be invariant. */
! for (i = 0; i < loop->num_nodes; i++)
! if (modified_between_p (op0, body[i]->head, NEXT_INSN (body[i]->end)))
! break;
! if (i == loop->num_nodes)
{
/* And the other one must be a register. */
if (!REG_P (op1))
return false;
desc->var = op1;
desc->lim = op0;
! #if 0
! op0 = variable_initial_value (loop, op0);
! if (op0)
desc->lim = op0;
! #endif
desc->cond = swap_condition (GET_CODE (condition));
if (desc->cond == UNKNOWN)
return false;
--- 161,179 ----
op1 = XEXP (condition, 1);
/* One of operands must be invariant. */
! if (invariant_in_blocks_p (op0, body, loop->num_nodes))
{
/* And the other one must be a register. */
if (!REG_P (op1))
return false;
desc->var = op1;
desc->lim = op0;
!
! set_insn = e->src->end;
! while (REG_P (op0)
! && (op0 = variable_initial_value (set_insn, e->src, op0, &set_insn)))
desc->lim = op0;
!
desc->cond = swap_condition (GET_CODE (condition));
if (desc->cond == UNKNOWN)
return false;
*************** simple_condition_p (loop, body, conditio
*** 165,185 ****
}
/* Check the other operand. */
! for (i = 0; i < loop->num_nodes; i++)
! if (modified_between_p (op1, body[i]->head, NEXT_INSN (body[i]->end)))
! break;
! if (i != loop->num_nodes)
return false;
if (!REG_P (op0))
return false;
desc->var = op0;
desc->lim = op1;
! #if 0
! op1 = variable_initial_value (loop, op1);
! if (op1)
desc->lim = op1;
! #endif
desc->cond = GET_CODE (condition);
return true;
--- 181,199 ----
}
/* Check the other operand. */
! if (!invariant_in_blocks_p (op1, body, loop->num_nodes))
return false;
if (!REG_P (op0))
return false;
desc->var = op0;
desc->lim = op1;
!
! set_insn = e->src->end;
! while (REG_P (op1)
! && (op1 = variable_initial_value (set_insn, e->src, op1, &set_insn)))
desc->lim = op1;
!
desc->cond = GET_CODE (condition);
return true;
*************** simple_increment (loops, loop, body, des
*** 246,268 ****
return mod_bb;
}
! /* Tries to find initial value of VAR in LOOP. */
static rtx
! variable_initial_value (loop, var)
! struct loop *loop;
rtx var;
{
- edge e;
basic_block bb;
! rtx set, insn;
/* Go back through cfg. */
! e = loop_preheader_edge (loop);
! for (bb = e->src; bb->pred; bb = bb->pred->src)
{
! for (insn = bb->end;
! insn != bb->head;
! insn = PREV_INSN (insn))
if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
break;
--- 260,283 ----
return mod_bb;
}
! /* Tries to find initial value of VAR in INSN. This value must be valid in
! END_BB too. If SET_INSN is not NULL, insn in that var is set is placed
! here. */
static rtx
! variable_initial_value (insn, end_bb, var, set_insn)
! rtx insn;
! basic_block end_bb;
rtx var;
+ rtx *set_insn;
{
basic_block bb;
! rtx set;
/* Go back through cfg. */
! bb = BLOCK_FOR_INSN (insn);
! while (1)
{
! for (; insn != bb->head; insn = PREV_INSN (insn))
if (modified_between_p (var, PREV_INSN (insn), NEXT_INSN (insn)))
break;
*************** variable_initial_value (loop, var)
*** 273,279 ****
basic_block b;
rtx val;
rtx note;
!
set = single_set (insn);
if (!set)
return NULL;
--- 288,294 ----
basic_block b;
rtx val;
rtx note;
!
set = single_set (insn);
if (!set)
return NULL;
*************** variable_initial_value (loop, var)
*** 286,300 ****
val = XEXP (note, 0);
else
val = SET_SRC (set);
! if (modified_between_p (val, insn, bb->end))
return NULL;
! for (b = e->src; b != bb; b = b->pred->src)
! if (modified_between_p (val, b->head, b->end))
return NULL;
return val;
}
! if (bb->pred->pred_next)
return NULL;
}
return NULL;
--- 301,322 ----
val = XEXP (note, 0);
else
val = SET_SRC (set);
! if (modified_between_p (val, insn, NEXT_INSN (bb->end)))
return NULL;
! for (b = end_bb; b != bb; b = b->pred->src)
! if (modified_between_p (val, b->head, NEXT_INSN (b->end)))
return NULL;
+
+ if (set_insn)
+ *set_insn = insn;
return val;
}
!
! if (bb->pred->pred_next || bb->pred->src == ENTRY_BLOCK_PTR)
return NULL;
+
+ bb = bb->pred->src;
+ insn = bb->end;
}
return NULL;
*************** simple_loop_p (loops, loop, desc)
*** 339,365 ****
/* Counts constant number of iterations of the loop described by DESC;
returns false if impossible. */
static bool
! constant_iterations (desc, niter)
struct loop_desc *desc;
unsigned HOST_WIDE_INT *niter;
{
rtx test, expr;
test = test_for_iteration (desc, 0);
! if (test && test == const0_rtx)
{
*niter = 0;
return true;
}
if (!(expr = count_loop_iterations (desc, true)))
abort ();
! if (GET_CODE (expr) != CONST_INT)
! return false;
! *niter = INTVAL (expr);
! return true;
}
/* Tests whether exit at EXIT_EDGE from LOOP is simple. Returns simple loop
--- 361,402 ----
/* Counts constant number of iterations of the loop described by DESC;
returns false if impossible. */
static bool
! constant_iterations (desc, niter, may_be_zero)
struct loop_desc *desc;
unsigned HOST_WIDE_INT *niter;
+ bool *may_be_zero;
{
rtx test, expr;
test = test_for_iteration (desc, 0);
! if (test == const0_rtx)
{
*niter = 0;
+ *may_be_zero = false;
return true;
}
+ *may_be_zero = (test != const_true_rtx);
+
if (!(expr = count_loop_iterations (desc, true)))
abort ();
! if (GET_CODE (expr) == CONST_INT)
! {
! *niter = INTVAL (expr);
! return true;
! }
! if (!(expr = count_loop_iterations (desc, false)))
! abort ();
!
! if (GET_CODE (expr) == CONST_INT)
! {
! *niter = INTVAL (expr);
! return true;
! }
!
! return false;
}
/* Tests whether exit at EXIT_EDGE from LOOP is simple. Returns simple loop
*************** simple_loop_exit_p (loops, loop, exit_ed
*** 375,381 ****
basic_block mod_bb, exit_bb;
int fallthru_out;
rtx condition;
! edge ei;
exit_bb = exit_edge->src;
--- 412,418 ----
basic_block mod_bb, exit_bb;
int fallthru_out;
rtx condition;
! edge ei, e;
exit_bb = exit_edge->src;
*************** simple_loop_exit_p (loops, loop, exit_ed
*** 417,428 ****
desc->neg = !fallthru_out;
/* Find initial value of var. */
! desc->init = variable_initial_value (loop, desc->var);
/* Number of iterations. */
if (!count_loop_iterations (desc, false))
return false;
! desc->const_iter = constant_iterations (desc, &desc->niter);
if (rtl_dump_file)
{
--- 454,466 ----
desc->neg = !fallthru_out;
/* Find initial value of var. */
! e = loop_preheader_edge (loop);
! desc->init = variable_initial_value (e->src->end, e->src, desc->var, NULL);
/* Number of iterations. */
if (!count_loop_iterations (desc, false))
return false;
! desc->const_iter = constant_iterations (desc, &desc->niter, &desc->may_be_zero);
if (rtl_dump_file)
{
*************** peel_loop_completely (loops, loop, desc)
*** 655,660 ****
--- 693,700 ----
sbitmap_ones (wont_exit);
RESET_BIT (wont_exit, 0);
RESET_BIT (wont_exit, npeel + 1);
+ if (desc->may_be_zero)
+ RESET_BIT (wont_exit, 1);
remove_edges = xcalloc (npeel, sizeof (edge));
n_remove_edges = 0;
*************** unroll_loop_constant_iterations (loops,
*** 696,712 ****
{
unsigned HOST_WIDE_INT niter, exit_mod;
sbitmap wont_exit;
! int n_remove_edges, i;
edge *remove_edges;
niter = desc->niter;
! if (niter <= (unsigned) max_unroll)
! abort (); /* Should get into peeling instead. */
wont_exit = sbitmap_alloc (max_unroll + 1);
sbitmap_ones (wont_exit);
- exit_mod = niter % (max_unroll + 1);
remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
n_remove_edges = 0;
--- 736,784 ----
{
unsigned HOST_WIDE_INT niter, exit_mod;
sbitmap wont_exit;
! int n_remove_edges, i, n_copies;
edge *remove_edges;
+ int best_copies, best_unroll;
niter = desc->niter;
! if (niter <= (unsigned) max_unroll + 1)
! abort (); /* Should not get here. */
!
! /* Find good number of unrollings. */
! best_copies = 2 * max_unroll + 10;
!
! i = 2 * max_unroll + 2;
! if ((unsigned) i - 1 >= niter)
! i = niter - 2;
!
! for (; i >= max_unroll; i--)
! {
! exit_mod = niter % (i + 1);
!
! if (desc->postincr)
! n_copies = exit_mod + i + 1;
! else if (exit_mod != (unsigned) i || desc->may_be_zero)
! n_copies = exit_mod + i + 2;
! else
! n_copies = i + 1;
!
! if (n_copies < best_copies)
! {
! best_copies = n_copies;
! best_unroll = i;
! }
! }
!
! if (rtl_dump_file)
! fprintf (rtl_dump_file, ";; max_unroll %d (%d copies, initial %d).\n",
! best_unroll, best_copies, max_unroll);
! max_unroll = best_unroll;
!
! exit_mod = niter % (max_unroll + 1);
wont_exit = sbitmap_alloc (max_unroll + 1);
sbitmap_ones (wont_exit);
remove_edges = xcalloc (max_unroll + exit_mod + 1, sizeof (edge));
n_remove_edges = 0;
*************** unroll_loop_constant_iterations (loops,
*** 721,726 ****
--- 793,800 ----
/* Peel exit_mod iterations. */
RESET_BIT (wont_exit, 0);
+ if (desc->may_be_zero)
+ RESET_BIT (wont_exit, 1);
if (exit_mod
&& !duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
*************** unroll_loop_constant_iterations (loops,
*** 728,733 ****
--- 802,809 ----
wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
DLTHE_FLAG_ALL))
abort ();
+
+ SET_BIT (wont_exit, 1);
}
else
{
*************** unroll_loop_constant_iterations (loops,
*** 736,748 ****
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Condition on end of loop.\n");
! /* We know that niter >= max_unroll + 1; so we do not need to care of
case when we would exit before reaching the loop. So just peel
exit_mod + 1 iterations.
*/
! if (exit_mod != (unsigned) max_unroll)
{
RESET_BIT (wont_exit, 0);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
loops, exit_mod + 1,
--- 812,826 ----
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Condition on end of loop.\n");
! /* We know that niter >= max_unroll + 2; so we do not need to care of
case when we would exit before reaching the loop. So just peel
exit_mod + 1 iterations.
*/
! if (exit_mod != (unsigned) max_unroll || desc->may_be_zero)
{
RESET_BIT (wont_exit, 0);
+ if (desc->may_be_zero)
+ RESET_BIT (wont_exit, 1);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
loops, exit_mod + 1,
*************** unroll_loop_constant_iterations (loops,
*** 751,756 ****
--- 829,835 ----
abort ();
SET_BIT (wont_exit, 0);
+ SET_BIT (wont_exit, 1);
}
RESET_BIT (wont_exit, max_unroll);
*************** unroll_or_peel_loop (loops, loop, flags)
*** 1097,1103 ****
exact = false;
if (simple)
{
! /* Loop iterating 0 times. These should really be elliminated earlier,
but we may create them by other transformations. */
if (desc.const_iter && desc.niter == 0)
--- 1176,1182 ----
exact = false;
if (simple)
{
! /* Loop iterating 0 times. These should really be eliminated earlier,
but we may create them by other transformations. */
if (desc.const_iter && desc.niter == 0)
*************** unroll_or_peel_loop (loops, loop, flags)
*** 1148,1164 ****
will be effective, so disable it. */
if ((flags & UAP_PEEL) && rtl_dump_file)
fprintf (rtl_dump_file,
! ";; Not peeling loop, no evidence it will be profitable\n",
! niter, npeel);
flags &= ~UAP_PEEL;
- }
-
- /* We might have lost simpleness when counting loop iterations. */
- if (!simple && !(flags & UAP_UNROLL_ALL))
- {
- if ((flags & UAP_UNROLL) && rtl_dump_file)
- fprintf (rtl_dump_file, ";; Not unrolling loop, isn't simple\n");
- flags &= ~UAP_UNROLL;
}
/* Shortcut. */
--- 1227,1234 ----
will be effective, so disable it. */
if ((flags & UAP_PEEL) && rtl_dump_file)
fprintf (rtl_dump_file,
! ";; Not peeling loop, no evidence it will be profitable\n");
flags &= ~UAP_PEEL;
}
/* Shortcut. */