This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[CFG] Loop unrolling
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org, gcc-pdo at atrey dot karlin dot mff dot cuni dot cz
- Date: Fri, 3 May 2002 01:36:47 +0200
- Subject: [CFG] Loop unrolling
Hello.
This patch is a preparation for allowing simple loops to have more than one
exit (in fact it is just sufficient now to modify simple_loop_p to reckognize
them and everything should work).
It also fixes several bugs and simplifies the code a bit.
Bootstrapped on i686.
Zdenek Dvorak
Changelog:
* loop-new.c (remove_exit_edges): Removed.
(record_exit_edges): New.
(remove_path): Fix.
(unswitch_loop): Modified for new interface to
duplicate_loop_to_header_edge.
(duplicate_loop_to_header_edge): Removed possibility to remove exit
edges, allow to record them now instead. Minor cleanup.
* loop.h (duplicate_loop_to_header_edge): Declaration changed.
* unroll-new.c (peel_loop_completely, unroll_or_peel_loop): Fix
paradoxical loop handling.
(unroll_loop_constant_iterations, unroll_loop_runtime_iterations,
peel_loop_simple, unroll_loop_stupid): Modified for new interface
to duplicate_loop_to_header_edge.
Index: loop-new.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/Attic/loop-new.c,v
retrieving revision 1.1.2.17
diff -c -3 -p -r1.1.2.17 loop-new.c
*** loop-new.c 1 May 2002 20:45:31 -0000 1.1.2.17
--- loop-new.c 2 May 2002 21:02:09 -0000
*************** static void copy_loops_to PARAMS ((struc
*** 216,222 ****
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 void remove_exit_edges PARAMS ((basic_block *, int, basic_block));
static struct loop *unswitch_loop PARAMS ((struct loops *, struct loop *, basic_block));
static void remove_bbs PARAMS ((basic_block *, int));
static bool rpe_enum_p PARAMS ((basic_block, void *));
--- 216,221 ----
*************** static edge split_loop_bb PARAMS ((struc
*** 233,238 ****
--- 232,238 ----
static rtx reversed_condition PARAMS ((rtx));
static void scale_loop_frequencies PARAMS ((struct loop *, int, int));
static void scale_bbs_frequencies PARAMS ((basic_block *, int, int, int));
+ static void record_exit_edges PARAMS ((edge, basic_block *, int, edge *, int *, bool));
/* Initialize loop optimizer. */
*************** remove_path (loops, e)
*** 693,699 ****
}
}
}
! else
bord_bbs[n_bord_bbs++] = e->dest;
/* OK. Remove the path. */
--- 693,699 ----
}
}
}
! else if (e->dest != EXIT_BLOCK_PTR)
bord_bbs[n_bord_bbs++] = e->dest;
/* OK. Remove the path. */
*************** unswitch_loop (loops, loop, unswitch_on)
*** 988,994 ****
/* Make a copy. */
zero_bitmap = sbitmap_alloc (2);
sbitmap_zero (zero_bitmap);
! if (!duplicate_loop_to_header_edge (loop, entry, loops, 1, zero_bitmap, DLTHE_FLAG_UPDATE_DOMINATORS))
return NULL;
free (zero_bitmap);
--- 988,995 ----
/* Make a copy. */
zero_bitmap = sbitmap_alloc (2);
sbitmap_zero (zero_bitmap);
! if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
! zero_bitmap, NULL, NULL, NULL, 0))
return NULL;
free (zero_bitmap);
*************** copy_bbs (bbs, n, entry, latch_edge, new
*** 1226,1271 ****
RBI ((*new_bbs)[i])->duplicated = 0;
}
- /* Remove edges going out from BBS, except edge to HEADER. */
- static void
- remove_exit_edges (bbs, n, header)
- basic_block *bbs;
- int n;
- basic_block header;
- {
- basic_block bb;
- edge e;
- int i;
-
- /* duplicated is not supposed to be used for this, but I need
- something to mark blocks. */
- for (i = 0 ; i < n; i++)
- {
- bb = bbs[i];
- RBI (bb)->duplicated = 1;
- }
- RBI (header)->duplicated = 1;
-
- for (i = 0 ; i < n; i++)
- {
- edge succ_e;
- bb = bbs[i];
- for (e = bb->succ; e; e = succ_e)
- {
- succ_e = e->succ_next;
- if (!RBI (e->dest)->duplicated)
- loop_delete_branch_edge (e);
- }
- }
-
- for (i = 0 ; i < n; i++)
- {
- bb = bbs[i];
- RBI (bb)->duplicated = 0;
- }
- RBI (header)->duplicated = 0;
- }
-
/* Check whether LOOP's body can be duplicated. */
bool
can_duplicate_loop_p (loop)
--- 1227,1232 ----
*************** can_duplicate_loop_p (loop)
*** 1302,1319 ****
return true;
}
/* Duplicates body of LOOP to given edge E NDUPL times. Takes care of
updating LOOPS structure. E's destination must be LOOP header for this to
! work. Remove exit edges from copies corresponding to set bits in WONT_EXIT
! (bit 0 corresponds to original LOOP body). Returns false if
! duplication is impossible. */
int
! duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, flags)
struct loop *loop;
edge e;
struct loops *loops;
int ndupl;
sbitmap wont_exit;
int flags;
{
struct loop *target, *aloop;
--- 1263,1333 ----
return true;
}
+ /* Store edges created by copying ORIG edge (simply this ORIG edge if IS_ORIG)
+ (if ORIG is NULL, then all exit edges) into TO_REMOVE array. */
+ static void
+ record_exit_edges (orig, bbs, nbbs, to_remove, n_to_remove, is_orig)
+ edge orig;
+ basic_block *bbs;
+ int nbbs;
+ edge *to_remove;
+ int *n_to_remove;
+ bool is_orig;
+ {
+ sbitmap my_blocks;
+ int i;
+ edge e;
+
+ if (orig)
+ {
+ if (is_orig)
+ {
+ to_remove[(*n_to_remove)++] = orig;
+ return;
+ }
+
+ for (e = RBI (orig->src)->copy->succ; e; e = e->succ_next)
+ if (e->dest == orig->dest)
+ break;
+ if (!e)
+ abort ();
+
+ to_remove[(*n_to_remove)++] = e;
+ }
+ else
+ {
+ my_blocks = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (my_blocks);
+ for (i = 0; i < nbbs; i++)
+ SET_BIT (my_blocks, bbs[i]->index);
+
+ for (i = 0; i < nbbs; i++)
+ for (e = bbs[i]->succ; e; e = e->succ_next)
+ if (e->dest == EXIT_BLOCK_PTR ||
+ !TEST_BIT (my_blocks, e->dest->index))
+ to_remove[(*n_to_remove)++] = e;
+
+ free (my_blocks);
+ }
+ }
+
/* Duplicates body of LOOP to given edge E NDUPL times. Takes care of
updating LOOPS structure. E's destination must be LOOP header for this to
! work. Store edges created by copying ORIG edge (if NULL, then all exit
! edges) from copies corresponding to set bits in WONT_EXIT (bit 0 corresponds
! to original LOOP body) into TO_REMOVE array. Returns false if duplication
! is impossible. */
int
! duplicate_loop_to_header_edge (loop, e, loops, ndupl,
! wont_exit, orig, to_remove, n_to_remove, flags)
struct loop *loop;
edge e;
struct loops *loops;
int ndupl;
sbitmap wont_exit;
+ edge orig;
+ edge *to_remove;
+ int *n_to_remove;
int flags;
{
struct loop *target, *aloop;
*************** duplicate_loop_to_header_edge (loop, e,
*** 1323,1338 ****
basic_block *new_bbs, *bbs, *first_active;
basic_block new_bb, bb, first_active_latch = NULL;
edge ae, latch_edge, he;
! int i, j, n, more_active = 0;
int is_latch = (latch == e->src);
int k0, k, kk, freq_in, freq_e, freq_le;
- int loop_made_infinite;
if (e->dest != loop->header)
abort ();
if (ndupl <= 0)
abort ();
bbs = get_loop_body (loop);
/* Check whether duplication is possible. */
--- 1337,1360 ----
basic_block *new_bbs, *bbs, *first_active;
basic_block new_bb, bb, first_active_latch = NULL;
edge ae, latch_edge, he;
! int i, j, n;
int is_latch = (latch == e->src);
int k0, k, kk, freq_in, freq_e, freq_le;
if (e->dest != loop->header)
abort ();
if (ndupl <= 0)
abort ();
+ if (orig)
+ {
+ /* Orig must be edge out of the loop. */
+ if (!flow_bb_inside_loop_p (loop, orig->src))
+ abort ();
+ if (flow_bb_inside_loop_p (loop, orig->dest))
+ abort ();
+ }
+
bbs = get_loop_body (loop);
/* Check whether duplication is possible. */
*************** duplicate_loop_to_header_edge (loop, e,
*** 1407,1431 ****
abort ();
}
! /* Check whether we will create an infinite loop. */
! if (is_latch)
! {
! loop_made_infinite = 1;
! for (i = 0; i <= ndupl; i++)
! if (!TEST_BIT (wont_exit, i))
! {
! loop_made_infinite = 0;
! break;
! }
! }
! else
! loop_made_infinite = TEST_BIT (wont_exit, 0);
! /* We cannot handle infinite loops yet. It is relatively hard to do,
! as outer loops might become infinite too. */
! if (loop_made_infinite)
! abort ();
!
! /* Loop to that new bbs will belong. */
target = find_common_loop (e->src->loop_father, e->dest->loop_father);
/* Original loops. */
--- 1429,1435 ----
abort ();
}
! /* Loop the new bbs will belong to. */
target = find_common_loop (e->src->loop_father, e->dest->loop_father);
/* Original loops. */
*************** duplicate_loop_to_header_edge (loop, e,
*** 1442,1452 ****
n = loop->num_nodes;
first_active = xcalloc(n, sizeof (basic_block));
! if (is_latch && !TEST_BIT (wont_exit, 0))
{
memcpy (first_active, bbs, n * sizeof (basic_block));
first_active_latch = latch;
}
for (j = 0; j < ndupl; j++)
{
--- 1446,1460 ----
n = loop->num_nodes;
first_active = xcalloc(n, sizeof (basic_block));
! if (is_latch)
{
memcpy (first_active, bbs, n * sizeof (basic_block));
first_active_latch = latch;
}
+
+ /* Record exit edges in original loop body. */
+ if (TEST_BIT (wont_exit, 0))
+ record_exit_edges (orig, bbs, n, to_remove, n_to_remove, true);
for (j = 0; j < ndupl; j++)
{
*************** duplicate_loop_to_header_edge (loop, e,
*** 1458,1463 ****
--- 1466,1475 ----
if (is_latch)
loop->latch = RBI (latch)->copy;
+ /* Record exit edges in this copy. */
+ if (TEST_BIT (wont_exit, j + 1))
+ record_exit_edges (orig, new_bbs, n, to_remove, n_to_remove, false);
+
/* Set counts and frequencies. */
kk = (kk * k) / REG_BR_PROB_BASE;
for (i = 0; i < n; i++)
*************** duplicate_loop_to_header_edge (loop, e,
*** 1484,1499 ****
}
}
! /* Remove exit edges if needed. */
! if (TEST_BIT (wont_exit, j + 1))
! remove_exit_edges (new_bbs, n, header);
! else if (!first_active_latch)
{
memcpy (first_active, new_bbs, n * sizeof (basic_block));
first_active_latch = RBI (latch)->copy;
}
- else
- more_active = 1;
/* Update edge counts. */
for (i = 0; i < n; i++)
--- 1496,1506 ----
}
}
! if (!first_active_latch)
{
memcpy (first_active, new_bbs, n * sizeof (basic_block));
first_active_latch = RBI (latch)->copy;
}
/* Update edge counts. */
for (i = 0; i < n; i++)
*************** duplicate_loop_to_header_edge (loop, e,
*** 1504,1513 ****
REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
}
- /* Update loops info. */
- for (i = 0; i < n_orig_loops; i++)
- flow_loop_scan (loops, orig_loops[i]->copy, 0);
-
free (new_bbs);
/* Original loop header is dominated by latch copy
--- 1511,1516 ----
*************** duplicate_loop_to_header_edge (loop, e,
*** 1526,1535 ****
/* Now handle original loop. */
- /* Remove exit edges if needed. */
- if (TEST_BIT (wont_exit, 0))
- remove_exit_edges (bbs, n, latch_edge->dest);
-
/* Update edge counts. */
if (flags & DLTHE_FLAG_UPDATE_FREQ)
{
--- 1529,1534 ----
*************** duplicate_loop_to_header_edge (loop, e,
*** 1546,1595 ****
}
}
- if (!first_active_latch)
- {
- memcpy (first_active, bbs, n * sizeof (basic_block));
- first_active_latch = latch;
- }
- else
- more_active = 1;
-
/* Update dominators of other blocks if affected. */
! if (flags & DLTHE_FLAG_UPDATE_DOMINATORS)
{
! for (i = 0; i < n; i++)
! {
! basic_block dominated, dom_bb, *dom_bbs;
! int n_dom_bbs,j;
! bb = bbs[i];
! n_dom_bbs = get_dominated_by (loops->cfg.dom, bb, &dom_bbs);
! for (j = 0; j < n_dom_bbs; j++)
! {
! dominated = dom_bbs[j];
! if (flow_bb_inside_loop_p (loop, dominated))
! continue;
! if (more_active)
! {
! dom_bb = nearest_common_dominator (
! loops->cfg.dom, first_active[i], first_active_latch);
! }
! else
! dom_bb = first_active[i];
! set_immediate_dominator (loops->cfg.dom, dominated, dom_bb);
! }
! free (dom_bbs);
}
}
free (first_active);
free (bbs);
- /* Fill other info for father loops. */
- for (aloop = target; aloop->depth > 0; aloop = aloop->outer)
- flow_loop_scan (loops, aloop, 0);
-
return true;
-
}
--- 1545,1573 ----
}
}
/* Update dominators of other blocks if affected. */
! for (i = 0; i < n; i++)
{
! basic_block dominated, dom_bb, *dom_bbs;
! int n_dom_bbs,j;
! bb = bbs[i];
! n_dom_bbs = get_dominated_by (loops->cfg.dom, bb, &dom_bbs);
! for (j = 0; j < n_dom_bbs; j++)
! {
! dominated = dom_bbs[j];
! if (flow_bb_inside_loop_p (loop, dominated))
! continue;
! dom_bb = nearest_common_dominator (
! loops->cfg.dom, first_active[i], first_active_latch);
! set_immediate_dominator (loops->cfg.dom, dominated, dom_bb);
}
+ free (dom_bbs);
}
free (first_active);
free (bbs);
return true;
}
Index: loop.h
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/loop.h,v
retrieving revision 1.56.2.11
diff -c -3 -p -r1.56.2.11 loop.h
*** loop.h 1 May 2002 20:45:33 -0000 1.56.2.11
--- loop.h 2 May 2002 21:02:09 -0000
*************** struct loop_desc
*** 451,459 ****
};
bool can_duplicate_loop_p PARAMS ((struct loop *loop));
! #define DLTHE_FLAG_UPDATE_DOMINATORS 1
! #define DLTHE_FLAG_UPDATE_FREQ 2
! #define DLTHE_FLAG_ALL (DLTHE_FLAG_UPDATE_DOMINATORS \
! | DLTHE_FLAG_UPDATE_FREQ)
! int duplicate_loop_to_header_edge PARAMS ((struct loop *, edge, struct loops *, int, sbitmap, int));
void remove_path PARAMS ((struct loops *, edge));
--- 451,461 ----
};
bool can_duplicate_loop_p PARAMS ((struct loop *loop));
!
! #define DLTHE_FLAG_UPDATE_FREQ 1
! #define DLTHE_FLAG_ALL (DLTHE_FLAG_UPDATE_FREQ)
! 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));
+
Index: unroll-new.c
===================================================================
RCS file: /cvsroot/gcc/gcc/gcc/Attic/unroll-new.c,v
retrieving revision 1.1.2.18
diff -c -3 -p -r1.1.2.18 unroll-new.c
*** unroll-new.c 2 May 2002 17:48:43 -0000 1.1.2.18
--- unroll-new.c 2 May 2002 21:02:09 -0000
*************** peel_loop_completely (loops, loop, desc)
*** 571,594 ****
sbitmap wont_exit;
unsigned HOST_WIDE_INT npeel;
edge e;
rtx exp;
!
! exp = count_loop_iterations (desc);
! if (!exp || GET_CODE (exp) != CONST_INT)
! abort ();
! npeel = INTVAL (exp);
wont_exit = sbitmap_alloc (npeel + 2);
sbitmap_ones (wont_exit);
RESET_BIT (wont_exit, 0);
RESET_BIT (wont_exit, npeel + 1);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, npeel + 1, wont_exit, DLTHE_FLAG_ALL))
abort ();
free (wont_exit);
/* Now remove the loop. */
for (e = RBI (desc->in_edge->src)->copy->succ;
e->dest != RBI (desc->in_edge->dest)->copy;
--- 571,613 ----
sbitmap wont_exit;
unsigned HOST_WIDE_INT npeel;
edge e;
+ int n_remove_edges, i;
+ edge *remove_edges;
rtx exp;
! rtx test;
!
! test = test_for_iteration (desc, 0);
! if (test && test == const0_rtx)
! npeel = 0;
! else
! {
! exp = count_loop_iterations (desc);
! if (!exp || GET_CODE (exp) != CONST_INT)
! abort ();
! npeel = INTVAL (exp);
! }
wont_exit = sbitmap_alloc (npeel + 2);
sbitmap_ones (wont_exit);
RESET_BIT (wont_exit, 0);
RESET_BIT (wont_exit, npeel + 1);
+ remove_edges = xcalloc (npeel, sizeof (edge));
+ n_remove_edges = 0;
+
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, npeel + 1,
! wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
! DLTHE_FLAG_ALL))
abort ();
free (wont_exit);
+ /* Remove the exit edges. */
+ for (i = 0; i < n_remove_edges; i++)
+ remove_path (loops, remove_edges[i]);
+ free (remove_edges);
+
/* Now remove the loop. */
for (e = RBI (desc->in_edge->src)->copy->succ;
e->dest != RBI (desc->in_edge->dest)->copy;
*************** unroll_loop_constant_iterations (loops,
*** 613,618 ****
--- 632,639 ----
{
unsigned HOST_WIDE_INT niter, exit_mod;
sbitmap wont_exit;
+ int n_remove_edges, i;
+ edge *remove_edges;
rtx exp;
/* Normalization. */
*************** unroll_loop_constant_iterations (loops,
*** 628,633 ****
--- 649,657 ----
sbitmap_ones (wont_exit);
exit_mod = niter % (max_unroll + 1);
+ 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
*************** unroll_loop_constant_iterations (loops,
*** 641,647 ****
if (exit_mod
&& !duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, exit_mod, wont_exit, DLTHE_FLAG_ALL))
abort ();
}
else
--- 665,673 ----
if (exit_mod
&& !duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, exit_mod,
! wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
! DLTHE_FLAG_ALL))
abort ();
}
else
*************** unroll_loop_constant_iterations (loops,
*** 660,666 ****
RESET_BIT (wont_exit, 0);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, exit_mod + 1, wont_exit, DLTHE_FLAG_ALL))
abort ();
SET_BIT (wont_exit, 0);
--- 686,694 ----
RESET_BIT (wont_exit, 0);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, exit_mod + 1,
! wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
! DLTHE_FLAG_ALL))
abort ();
SET_BIT (wont_exit, 0);
*************** unroll_loop_constant_iterations (loops,
*** 671,680 ****
/* Now unroll the loop. */
if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
! loops, max_unroll, wont_exit, DLTHE_FLAG_ALL))
abort ();
free (wont_exit);
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Unrolled loop %d times, constant # of iterations\n",max_unroll);
--- 699,716 ----
/* Now unroll the loop. */
if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
! loops, max_unroll,
! wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
! DLTHE_FLAG_ALL))
abort ();
free (wont_exit);
+
+ /* Remove the edges. */
+ for (i = 0; i < n_remove_edges; i++)
+ remove_path (loops, remove_edges[i]);
+ free (remove_edges);
+
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Unrolled loop %d times, constant # of iterations\n",max_unroll);
*************** unroll_loop_runtime_iterations (loops, l
*** 696,702 ****
basic_block fake, preheader, *body, dom;
edge e;
sbitmap wont_exit;
! int may_exit_copy, n_peel;
/* Force max_unroll + 1 to be power of 2. */
for (i = 1; 2 * i <= max_unroll + 1; i *= 2);
--- 732,740 ----
basic_block fake, preheader, *body, dom;
edge e;
sbitmap wont_exit;
! int may_exit_copy, n_peel, n_remove_edges;
! edge *remove_edges;
! bool skip_first_test;
/* Force max_unroll + 1 to be power of 2. */
for (i = 1; 2 * i <= max_unroll + 1; i *= 2);
*************** unroll_loop_runtime_iterations (loops, l
*** 720,725 ****
--- 758,764 ----
/* Leave exit in first copy. */
may_exit_copy = 0;
n_peel = max_unroll;
+ skip_first_test = false;
}
else
{
*************** unroll_loop_runtime_iterations (loops, l
*** 729,734 ****
--- 768,774 ----
niter,
const1_rtx, NULL_RTX, 0, OPTAB_LIB_WIDEN);
n_peel = max_unroll + 1;
+ skip_first_test = true;
/* First check for zero is obviously unnecessary now; it might seem
we could do better by increasing it before AND; but we must have
guaranteed that exit condition will be checked in first iteration,
*************** unroll_loop_runtime_iterations (loops, l
*** 749,786 ****
fake = create_basic_block (n_basic_blocks, NULL, NULL);
loop_beg_label = block_label (fake);
for (i = 0; i < n_peel; i++)
{
start_sequence ();
niter = expand_simple_binop (GET_MODE (desc->var), MINUS,
niter, const1_rtx,
NULL_RTX, 0, OPTAB_LIB_WIDEN);
! do_compare_rtx_and_jump (copy_rtx (niter), const0_rtx, EQ, 0,
! GET_MODE (desc->var), NULL_RTX, NULL_RTX,
! loop_beg_label);
! JUMP_LABEL (get_last_insn ()) = loop_beg_label;
! LABEL_NUSES (loop_beg_label)++;
branch_code = gen_sequence ();
end_sequence ();
preheader =
loop_split_edge_with (loop_preheader_edge (loop), branch_code, loops);
- make_edge (preheader, fake, 0);
! wont_exit = sbitmap_alloc (2);
! sbitmap_zero (wont_exit);
/* We must be a bit careful here, as we might have negative
number of iterations. Also, in case of postincrement we do
not know whether we should not exit before reaching the loop. */
if (desc->postincr && (i || desc->cond == NE))
SET_BIT (wont_exit, 1);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, 1, wont_exit,
! DLTHE_FLAG_ALL))
abort ();
- free (wont_exit);
}
/* Now redirect the edges from fake. */
preheader =
--- 789,836 ----
fake = create_basic_block (n_basic_blocks, NULL, NULL);
loop_beg_label = block_label (fake);
+ remove_edges = xcalloc (max_unroll + n_peel, sizeof (edge));
+ n_remove_edges = 0;
+
+ wont_exit = sbitmap_alloc (2);
+
for (i = 0; i < n_peel; i++)
{
start_sequence ();
niter = expand_simple_binop (GET_MODE (desc->var), MINUS,
niter, const1_rtx,
NULL_RTX, 0, OPTAB_LIB_WIDEN);
! if (i || !skip_first_test)
! {
! do_compare_rtx_and_jump (copy_rtx (niter), const0_rtx, EQ, 0,
! GET_MODE (desc->var), NULL_RTX, NULL_RTX,
! loop_beg_label);
! JUMP_LABEL (get_last_insn ()) = loop_beg_label;
! LABEL_NUSES (loop_beg_label)++;
! }
branch_code = gen_sequence ();
end_sequence ();
preheader =
loop_split_edge_with (loop_preheader_edge (loop), branch_code, loops);
! if (i || !skip_first_test)
! make_edge (preheader, fake, 0);
!
/* We must be a bit careful here, as we might have negative
number of iterations. Also, in case of postincrement we do
not know whether we should not exit before reaching the loop. */
+ sbitmap_zero (wont_exit);
if (desc->postincr && (i || desc->cond == NE))
SET_BIT (wont_exit, 1);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, 1,
! wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
! DLTHE_FLAG_ALL))
abort ();
}
+ free (wont_exit);
/* Now redirect the edges from fake. */
preheader =
*************** unroll_loop_runtime_iterations (loops, l
*** 796,816 ****
dom = recount_dominator (loops->cfg.dom, preheader);
set_immediate_dominator (loops->cfg.dom, preheader, dom);
! if (desc->cond != NE || !desc->postincr)
! {
! /* Recount dominators for outer blocks. */
! body = get_loop_body (loop);
! for (i = 0; i < loop->num_nodes; i++)
! for (e = body[i]->succ; e; e = e->succ_next)
! {
! if (flow_bb_inside_loop_p (loop, e->dest))
! continue;
! set_immediate_dominator (loops->cfg.dom, e->dest,
! nearest_common_dominator (loops->cfg.dom,
! e->dest, dom));
! }
! free (body);
! }
/* Get rid of fake. */
flow_delete_block (fake);
--- 846,863 ----
dom = recount_dominator (loops->cfg.dom, preheader);
set_immediate_dominator (loops->cfg.dom, preheader, dom);
! /* Recount dominators for outer blocks. */
! body = get_loop_body (loop);
! for (i = 0; i < loop->num_nodes; i++)
! for (e = body[i]->succ; e; e = e->succ_next)
! {
! if (flow_bb_inside_loop_p (loop, e->dest))
! continue;
! set_immediate_dominator (loops->cfg.dom, e->dest,
! nearest_common_dominator (loops->cfg.dom,
! e->dest, dom));
! }
! free (body);
/* Get rid of fake. */
flow_delete_block (fake);
*************** unroll_loop_runtime_iterations (loops, l
*** 822,832 ****
RESET_BIT (wont_exit, may_exit_copy);
if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
! loops, max_unroll, wont_exit,
! DLTHE_FLAG_ALL))
abort ();
free (wont_exit);
if (rtl_dump_file)
fprintf (rtl_dump_file,
";; Unrolled loop %d times, counting # of iterations in runtime\n",
--- 869,886 ----
RESET_BIT (wont_exit, may_exit_copy);
if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
! loops, max_unroll,
! wont_exit, desc->out_edge, remove_edges, &n_remove_edges,
! DLTHE_FLAG_ALL))
abort ();
free (wont_exit);
+
+ /* Remove the edges. */
+ for (i = 0; i < n_remove_edges; i++)
+ remove_path (loops, remove_edges[i]);
+ free (remove_edges);
+
if (rtl_dump_file)
fprintf (rtl_dump_file,
";; Unrolled loop %d times, counting # of iterations in runtime\n",
*************** peel_loop_simple (loops, loop, npeel)
*** 848,854 ****
sbitmap_zero (wont_exit);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, npeel, wont_exit, DLTHE_FLAG_ALL))
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Peeling unsuccessful\n");
--- 902,908 ----
sbitmap_zero (wont_exit);
if (!duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
! loops, npeel, wont_exit, NULL, NULL, NULL, DLTHE_FLAG_ALL))
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Peeling unsuccessful\n");
*************** unroll_loop_stupid (loops, loop, nunroll
*** 876,882 ****
sbitmap_zero (wont_exit);
if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
! loops, nunroll, wont_exit, DLTHE_FLAG_ALL))
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Not unrolling loop, can't duplicate\n");
--- 930,936 ----
sbitmap_zero (wont_exit);
if (!duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
! loops, nunroll, wont_exit, NULL, NULL, NULL, DLTHE_FLAG_ALL))
{
if (rtl_dump_file)
fprintf (rtl_dump_file, ";; Not unrolling loop, can't duplicate\n");
*************** unroll_or_peel_loop (loops, loop, flags)
*** 976,994 ****
rtx exp = count_loop_iterations (&desc);
rtx test = test_for_iteration (&desc, 0);
! /* Bypass loops iterating 0 times. These should really be
! elliminated earlier, but we may create them by other transformations.
! CSE will kill them later. */
if (test && test == const0_rtx)
{
! if ((flags & UAP_UNROLL) && rtl_dump_file)
! fprintf (rtl_dump_file, ";; Not unrolling nor peeling loop, iterates 0 times\n");
}
!
! /* Loop with constant number of iterations? */
! if (!exp)
simple = false;
else if (GET_CODE (exp) == CONST_INT
&& test && test == const_true_rtx)
exact = true, niter = INTVAL (exp);
--- 1030,1047 ----
rtx exp = count_loop_iterations (&desc);
rtx test = test_for_iteration (&desc, 0);
! /* Loop iterating 0 times. These should really be elliminated earlier,
! but we may create them by other transformations. */
if (test && test == const0_rtx)
{
! flags |= UAP_PEEL;
! exact = true;
! niter = 0;
}
! else if (!exp)
simple = false;
+ /* Loop with constant number of iterations? */
else if (GET_CODE (exp) == CONST_INT
&& test && test == const_true_rtx)
exact = true, niter = INTVAL (exp);